fuzz: miniscript: higher sensitivity for max stack size limit under Tapscript

In order to exacerbate a mistake in the stack size tracking logic,
sometimes pad the witness to make the script execute at the brink of the
stack size limit. This way if the stack size is underestimated for a
script it would immediately fail `VerifyScript`.

1 files changed, 34 insertions, 16 deletions

diff --git a/src/test/fuzz/miniscript.cpp b/src/test/fuzz/miniscript.cpp
index eca79f65e6..835b6d8c6b 100644
--- a/src/test/fuzz/miniscript.cpp
+++ b/src/test/fuzz/miniscript.cpp
@@ -94,7 +94,7 @@ struct TestData {
     }
 
     //! Get the (Schnorr or ECDSA, depending on context) signature for this pubkey.
-    std::pair<std::vector<unsigned char>, bool>* GetSig(const MsCtx script_ctx, const Key& key) {
+    const std::pair<std::vector<unsigned char>, bool>* GetSig(const MsCtx script_ctx, const Key& key) const {
         if (!miniscript::IsTapscript(script_ctx)) {
             const auto it = dummy_sigs.find(key);
             if (it == dummy_sigs.end()) return nullptr;
@@ -1059,9 +1059,10 @@ void TestNode(const MsCtx script_ctx, const NodeRef& node, FuzzedDataProvider& p
     assert(decoded->ToScript(PARSER_CTX) == script);
     assert(decoded->GetType() == node->GetType());
 
-    const auto node_ops{node->GetOps()};
-    if (!IsTapscript(script_ctx) && provider.ConsumeBool() && node_ops && *node_ops < MAX_OPS_PER_SCRIPT
-        && node->ScriptSize() < MAX_STANDARD_P2WSH_SCRIPT_SIZE) {
+    // Optionally pad the script or the witness in order to increase the sensitivity of the tests of
+    // the resources limits logic.
+    CScriptWitness witness_mal, witness_nonmal;
+    if (provider.ConsumeBool()) {
         // Under P2WSH, optionally pad the script with OP_NOPs to max op the ops limit of the constructed script.
         // This makes the script obviously not actually miniscript-compatible anymore, but the
         // signatures constructed in this test don't commit to the script anyway, so the same
@@ -1071,10 +1072,25 @@ void TestNode(const MsCtx script_ctx, const NodeRef& node, FuzzedDataProvider& p
         // maximal.
         // Do not pad more than what would cause MAX_STANDARD_P2WSH_SCRIPT_SIZE to be reached, however,
         // as that also invalidates scripts.
-        int add = std::min<int>(
-            MAX_OPS_PER_SCRIPT - *node_ops,
-            MAX_STANDARD_P2WSH_SCRIPT_SIZE - node->ScriptSize());
-        for (int i = 0; i < add; ++i) script.push_back(OP_NOP);
+        const auto node_ops{node->GetOps()};
+        if (!IsTapscript(script_ctx) && node_ops && *node_ops < MAX_OPS_PER_SCRIPT
+            && node->ScriptSize() < MAX_STANDARD_P2WSH_SCRIPT_SIZE) {
+            int add = std::min<int>(
+                MAX_OPS_PER_SCRIPT - *node_ops,
+                MAX_STANDARD_P2WSH_SCRIPT_SIZE - node->ScriptSize());
+            for (int i = 0; i < add; ++i) script.push_back(OP_NOP);
+        }
+
+        // Under Tapscript, optionally pad the stack up to the limit minus the calculated maximum execution stack
+        // size to assert a Miniscript would never add more elements to the stack during execution than anticipated.
+        const auto node_exec_ss{node->GetExecStackSize()};
+        if (miniscript::IsTapscript(script_ctx) && node_exec_ss && *node_exec_ss < MAX_STACK_SIZE) {
+            unsigned add{(unsigned)MAX_STACK_SIZE - *node_exec_ss};
+            witness_mal.stack.resize(add);
+            witness_nonmal.stack.resize(add);
+            script.reserve(add);
+            for (unsigned i = 0; i < add; ++i) script.push_back(OP_NIP);
+        }
     }
 
     SATISFIER_CTX.script_ctx = script_ctx;
@@ -1084,26 +1100,26 @@ void TestNode(const MsCtx script_ctx, const NodeRef& node, FuzzedDataProvider& p
     const CScript script_pubkey{ScriptPubKey(script_ctx, script, builder)};
 
     // Run malleable satisfaction algorithm.
-    CScriptWitness witness_mal;
-    const bool mal_success = node->Satisfy(SATISFIER_CTX, witness_mal.stack, false) == miniscript::Availability::YES;
-    SatisfactionToWitness(script_ctx, witness_mal, script, builder);
+    std::vector<std::vector<unsigned char>> stack_mal;
+    const bool mal_success = node->Satisfy(SATISFIER_CTX, stack_mal, false) == miniscript::Availability::YES;
 
     // Run non-malleable satisfaction algorithm.
-    CScriptWitness witness_nonmal;
-    const bool nonmal_success = node->Satisfy(SATISFIER_CTX, witness_nonmal.stack, true) == miniscript::Availability::YES;
-    SatisfactionToWitness(script_ctx, witness_nonmal, script, builder);
+    std::vector<std::vector<unsigned char>> stack_nonmal;
+    const bool nonmal_success = node->Satisfy(SATISFIER_CTX, stack_nonmal, true) == miniscript::Availability::YES;
 
     if (nonmal_success) {
         // Non-malleable satisfactions are bounded by the satisfaction size plus:
         // - For P2WSH spends, the witness script
         // - For Tapscript spends, both the witness script and the control block
         const size_t max_stack_size{*node->GetStackSize() + 1 + miniscript::IsTapscript(script_ctx)};
-        assert(witness_nonmal.stack.size() <= max_stack_size);
+        assert(stack_nonmal.size() <= max_stack_size);
         // If a non-malleable satisfaction exists, the malleable one must also exist, and be identical to it.
         assert(mal_success);
-        assert(witness_nonmal.stack == witness_mal.stack);
+        assert(stack_nonmal == stack_mal);
 
         // Test non-malleable satisfaction.
+        witness_nonmal.stack.insert(witness_nonmal.stack.end(), std::make_move_iterator(stack_nonmal.begin()), std::make_move_iterator(stack_nonmal.end()));
+        SatisfactionToWitness(script_ctx, witness_nonmal, script, builder);
         ScriptError serror;
         bool res = VerifyScript(DUMMY_SCRIPTSIG, script_pubkey, &witness_nonmal, STANDARD_SCRIPT_VERIFY_FLAGS, CHECKER_CTX, &serror);
         // Non-malleable satisfactions are guaranteed to be valid if ValidSatisfactions().
@@ -1117,6 +1133,8 @@ void TestNode(const MsCtx script_ctx, const NodeRef& node, FuzzedDataProvider& p
 
     if (mal_success && (!nonmal_success || witness_mal.stack != witness_nonmal.stack)) {
         // Test malleable satisfaction only if it's different from the non-malleable one.
+        witness_mal.stack.insert(witness_mal.stack.end(), std::make_move_iterator(stack_mal.begin()), std::make_move_iterator(stack_mal.end()));
+        SatisfactionToWitness(script_ctx, witness_mal, script, builder);
         ScriptError serror;
         bool res = VerifyScript(DUMMY_SCRIPTSIG, script_pubkey, &witness_mal, STANDARD_SCRIPT_VERIFY_FLAGS, CHECKER_CTX, &serror);
         // Malleable satisfactions are not guaranteed to be valid under any conditions, but they can only