Page MenuHomePhabricator

Implement O(1) OP_IF/NOTIF/ELSE/ENDIF logic
ClosedPublic

Authored by PiRK on Thu, Jan 7, 17:16.

Details

Reviewers
majcosta
Group Reviewers
Restricted Project
Commits
rABC4ace18ab6498: Implement O(1) OP_IF/NOTIF/ELSE/ENDIF logic
Summary

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

Test Plan

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

Diff Detail

Repository
rABC Bitcoin ABC
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.