Merge #16902: O(1) OP_IF/NOTIF/ELSE/ENDIF script implementation

e6e622e5a0e22c2ac1b50b96af818e412d67ac54 Implement O(1) OP_IF/NOTIF/ELSE/ENDIF logic (Pieter Wuille)
d0e8f4d5d8ddaccb37f98b7989fb944081e41ab8 [refactor] interpreter: define interface for vfExec (Anthony Towns)
89fb241c54fc85befacfa3703d8e21bf3b8a76eb Benchmark script verification with 100 nested IFs (Pieter Wuille)

Pull request 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 improves upon #14245 by completely removing the `vfExec` vector.

ACKs for top commit:
  jnewbery:
    Code review ACK e6e622e5a0e22c2ac1b50b96af818e412d67ac54
  MarcoFalke:
    ACK e6e622e5a0e22c2ac1b50b96af818e412d67ac54 🐴
  fjahr:
    ACK e6e622e5a0e22c2ac1b50b96af818e412d67ac54
  ajtowns:
    ACK e6e622e5a0e22c2ac1b50b96af818e412d67ac54
  laanwj:
    concept and code review ACK e6e622e5a0e22c2ac1b50b96af818e412d67ac54
  jonatack:
    ACK e6e622e5a0e22c2ac1b50b96af818e412d67ac54 code review, build, benches, fuzzing

Tree-SHA512: 1dcfac3411ff04773de461959298a177f951cb5f706caa2734073bcec62224d7cd103767cfeef85cd129813e70c14c74fa8f1e38e4da70ec38a0f615aab1f7f7

1 files changed, 23 insertions, 0 deletions

diff --git a/src/bench/verify_script.cpp b/src/bench/verify_script.cpp
index 31e166cc27..0b34ae3f95 100644
--- a/src/bench/verify_script.cpp
+++ b/src/bench/verify_script.cpp
@@ -71,4 +71,27 @@ static void VerifyScriptBench(benchmark::State& state)
     }
 }
 
+static void VerifyNestedIfScript(benchmark::State& state) {
+    std::vector<std::vector<unsigned char>> stack;
+    CScript script;
+    for (int i = 0; i < 100; ++i) {
+        script << OP_1 << OP_IF;
+    }
+    for (int i = 0; i < 1000; ++i) {
+        script << OP_1;
+    }
+    for (int i = 0; i < 100; ++i) {
+        script << OP_ENDIF;
+    }
+    while (state.KeepRunning()) {
+        auto stack_copy = stack;
+        ScriptError error;
+        bool ret = EvalScript(stack_copy, script, 0, BaseSignatureChecker(), SigVersion::BASE, &error);
+        assert(ret);
+    }
+}
+
+
 BENCHMARK(VerifyScriptBench, 6300);
+
+BENCHMARK(VerifyNestedIfScript, 100);