Computational Cost of Verifying Enforceable Contracts

This paper explores a new method for evaluating the cost of verifying a contract. We relate these costs to the number of computations an algorithm needs to check that a contract satisfies certain criteria. Two different criteria that facilitate enforcement of the contract are studied. Our findings indicate bounds on the computational costs as the size of the contract grows. If each computation costs the same, then the marginal cost of increasing the size of the contract is at most linearly increasing and at least constant for the two criteria.