Static cost analysis

[obycode]

The stacks-node should be able to do some static analysis of contracts to get cost estimates without actually executing the contract. This is important for transaction selection and fee estimates.

[jcnelson]

I've been thinking about this. I think the system could compute on a per-AST-node basis what the minimum and maximum runtime costs will be for each child node and expose this to the mempool walk logic. The root node would be the entire contract; the first-level nodes would be functions and bare code; etc. The leaf nodes would be either Clarity native operations, or contract-calls to functions whose min/max runtime costs are already known from prior analysis.

Does this track with your thinking?

[obycode]

Yes, this is pretty much what I'm picturing as well. It could be done during contract deployment. Even better, we may be able to narrow the best-case/worst-case analysis as a function of the input with some symbolic execution.

[moodmosaic]

It's interesting, though I think path explosion could lead to slow analysis times in symbolic execution.

[jcnelson]

Because the predicate of every branch is necessarily decidable and finite, you could not only derive a decidable finite predicate for each halting state (I'm really excited about leveraging this for automatically generating contract unit tests, btw), but also determine the worst-case runtime cost to evaluate each such predicate at analysis time. Furthermore, the predicate could be structured so that a partial evaluation of the predicate would represent a set of halting states. This would mean that when you see an incoming contract-call transaction, the miner could have a budget for determining how much effort to expend finding out which halting state will be reached from inputs and chainstate. If the budget would be exceeded after computing a partial evaluation, then at least the miner would know what set of halting states could be reached (which would narrow down the min/max runtime costs to consider).

[moodmosaic]

leveraging this for automatically generating contract unit tests

We can leverage it to identify interesting cases and edge conditions that property tests might miss on their own by exhaustively exploring all possible execution paths, then derive property tests from it, creating a more targeted set.

[jcnelson]

Music to my ears :notes: