Commit message:

This optimization was first suggested by Sergio Demian Lerner in
https://bitslog.wordpress.com/2017/04/17/new-quadratic-delays-in-bitcoin-scripts/.
The implementation follows the suggested approach there, but with a slightly
simpler representation.

PR description:

While investigating what mechanisms are possible to maximize the per-opcode verification cost of scripts, I noticed that the logic for determining whether a particular opcode is to be executed is O(n) in the nesting depth. This issue was also pointed out by Sergio Demian Lerner in https://bitslog.wordpress.com/2017/04/17/new-quadratic-delays-in-bitcoin-scripts/, and this PR implements a variant of the O(1) algorithm suggested there.

This is not a problem currently, because even with a nesting depth of 100 (the maximum possible right now due to the 201 ops limit), the slowdown caused by this on my machine is around 70 ns per opcode (or 0.25 s per block) at worst, far lower than what is possible with other opcodes.

This PR mostly serves as a proof of concept that it's possible to avoid it, which may be relevant in discussions around increasing the opcode limits in future script versions. Without it, the execution time of scripts can grow quadratically with the nesting depth, which very quickly becomes unreasonable.

This is a backport of Core PR16902 [3/3]
https://github.com/bitcoin/bitcoin/pull/16902/commits/e6e622e5a0e22c2ac1b50b96af818e412d67ac54

Depends on D8836

ninja all check-all

Before this commit:

$ src/bench/bitcoin-bench -filter=VerifyNestedIfScript
# Benchmark, evals, iterations, total, min, max, median
VerifyNestedIfScript, 5, 100, 0.0473822, 9.28665e-05, 9.67629e-05, 9.47128e-05

After:

$ src/bench/bitcoin-bench -filter=VerifyNestedIfScript
# Benchmark, evals, iterations, total, min, max, median
VerifyNestedIfScript, 5, 100, 0.0138046, 2.68691e-05, 3.00776e-05, 2.70254e-05