Merge bitcoin/bitcoin#23408: fuzz: Rework ConsumeScript

fa4baf0756c792630391ed456aaa15285ad6eb52 fuzz: Rework ConsumeScript (MarcoFalke)

Pull request description:

  This should make it easier for the fuzz engine to explore multisig code
  paths. See discussion in https://github.com/bitcoin/bitcoin/issues/23105

  The downside is that all fuzz inputs that use ConsumeScript are now
  invalidated and need to be re-generated.

  Another downside may be that most multisig scripts from ConsumeScript are
  using likely not fully valid pubkeys.

ACKs for top commit:
  jamesob:
    ACK https://github.com/bitcoin/bitcoin/pull/23408/commits/fa4baf0756c792630391ed456aaa15285ad6eb52

Tree-SHA512: 15814afdee76b05ff7a71c0f07bbd1b3cff30d709d5c1e68fd230c5f5d16e673e42709a4fab84d4a896bc27f972f917fe7c1d1b32c2bf4209658b18da97e478b

4 files changed, 61 insertions, 10 deletions

diff --git a/src/test/fuzz/script.cpp b/src/test/fuzz/script.cpp
index 74c576322a..0979967384 100644
--- a/src/test/fuzz/script.cpp
+++ b/src/test/fuzz/script.cpp
@@ -41,9 +41,7 @@ void initialize_script()
 FUZZ_TARGET_INIT(script, initialize_script)
 {
     FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
-    const std::optional<CScript> script_opt = ConsumeDeserializable<CScript>(fuzzed_data_provider);
-    if (!script_opt) return;
-    const CScript script{*script_opt};
+    const CScript script{ConsumeScript(fuzzed_data_provider)};
 
     CompressedScript compressed;
     if (CompressScript(script, compressed)) {
diff --git a/src/test/fuzz/signature_checker.cpp b/src/test/fuzz/signature_checker.cpp
index 6b86c8889d..c3f416632d 100644
--- a/src/test/fuzz/signature_checker.cpp
+++ b/src/test/fuzz/signature_checker.cpp
@@ -58,8 +58,8 @@ FUZZ_TARGET_INIT(signature_checker, initialize_signature_checker)
     FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
     const unsigned int flags = fuzzed_data_provider.ConsumeIntegral<unsigned int>();
     const SigVersion sig_version = fuzzed_data_provider.PickValueInArray({SigVersion::BASE, SigVersion::WITNESS_V0});
-    const auto script_1 = ConsumeScript(fuzzed_data_provider, 65536);
-    const auto script_2 = ConsumeScript(fuzzed_data_provider, 65536);
+    const auto script_1{ConsumeScript(fuzzed_data_provider)};
+    const auto script_2{ConsumeScript(fuzzed_data_provider)};
     std::vector<std::vector<unsigned char>> stack;
     (void)EvalScript(stack, script_1, flags, FuzzedSignatureChecker(fuzzed_data_provider), sig_version, nullptr);
     if (!IsValidFlagCombination(flags)) {
diff --git a/src/test/fuzz/util.cpp b/src/test/fuzz/util.cpp
index d83d2924bb..ae5f7a379e 100644
--- a/src/test/fuzz/util.cpp
+++ b/src/test/fuzz/util.cpp
@@ -267,7 +267,7 @@ CMutableTransaction ConsumeTransaction(FuzzedDataProvider& fuzzed_data_provider,
         const auto amount = fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(-10, 50 * COIN + 10);
         const auto script_pk = p2wsh_op_true ?
                                    P2WSH_OP_TRUE :
-                                   ConsumeScript(fuzzed_data_provider, /* max_length */ 128, /* maybe_p2wsh */ true);
+                                   ConsumeScript(fuzzed_data_provider, /*maybe_p2wsh=*/true);
         tx_mut.vout.emplace_back(amount, script_pk);
     }
     return tx_mut;
@@ -283,10 +283,63 @@ CScriptWitness ConsumeScriptWitness(FuzzedDataProvider& fuzzed_data_provider, co
     return ret;
 }
 
-CScript ConsumeScript(FuzzedDataProvider& fuzzed_data_provider, const std::optional<size_t>& max_length, const bool maybe_p2wsh) noexcept
+CScript ConsumeScript(FuzzedDataProvider& fuzzed_data_provider, const bool maybe_p2wsh) noexcept
 {
-    const std::vector<uint8_t> b = ConsumeRandomLengthByteVector(fuzzed_data_provider, max_length);
-    CScript r_script{b.begin(), b.end()};
+    CScript r_script{};
+    {
+        // Keep a buffer of bytes to allow the fuzz engine to produce smaller
+        // inputs to generate CScripts with repeated data.
+        static constexpr unsigned MAX_BUFFER_SZ{128};
+        std::vector<uint8_t> buffer(MAX_BUFFER_SZ, uint8_t{'a'});
+        while (fuzzed_data_provider.ConsumeBool()) {
+            CallOneOf(
+                fuzzed_data_provider,
+                [&] {
+                    // Insert byte vector directly to allow malformed or unparsable scripts
+                    r_script.insert(r_script.end(), buffer.begin(), buffer.begin() + fuzzed_data_provider.ConsumeIntegralInRange(0U, MAX_BUFFER_SZ));
+                },
+                [&] {
+                    // Push a byte vector from the buffer
+                    r_script << std::vector<uint8_t>{buffer.begin(), buffer.begin() + fuzzed_data_provider.ConsumeIntegralInRange(0U, MAX_BUFFER_SZ)};
+                },
+                [&] {
+                    // Push multisig
+                    // There is a special case for this to aid the fuzz engine
+                    // navigate the highly structured multisig format.
+                    r_script << fuzzed_data_provider.ConsumeIntegralInRange<int64_t>(0, 22);
+                    int num_data{fuzzed_data_provider.ConsumeIntegralInRange(1, 22)};
+                    std::vector<uint8_t> pubkey_comp{buffer.begin(), buffer.begin() + CPubKey::COMPRESSED_SIZE};
+                    pubkey_comp.front() = fuzzed_data_provider.ConsumeIntegralInRange(2, 3); // Set first byte for GetLen() to pass
+                    std::vector<uint8_t> pubkey_uncomp{buffer.begin(), buffer.begin() + CPubKey::SIZE};
+                    pubkey_uncomp.front() = fuzzed_data_provider.ConsumeIntegralInRange(4, 7); // Set first byte for GetLen() to pass
+                    while (num_data--) {
+                        auto& pubkey{fuzzed_data_provider.ConsumeBool() ? pubkey_uncomp : pubkey_comp};
+                        if (fuzzed_data_provider.ConsumeBool()) {
+                            pubkey.back() = num_data; // Make each pubkey different
+                        }
+                        r_script << pubkey;
+                    }
+                    r_script << fuzzed_data_provider.ConsumeIntegralInRange<int64_t>(0, 22);
+                },
+                [&] {
+                    // Mutate the buffer
+                    const auto vec{ConsumeRandomLengthByteVector(fuzzed_data_provider, /*max_length=*/MAX_BUFFER_SZ)};
+                    std::copy(vec.begin(), vec.end(), buffer.begin());
+                },
+                [&] {
+                    // Push an integral
+                    r_script << fuzzed_data_provider.ConsumeIntegral<int64_t>();
+                },
+                [&] {
+                    // Push an opcode
+                    r_script << ConsumeOpcodeType(fuzzed_data_provider);
+                },
+                [&] {
+                    // Push a scriptnum
+                    r_script << ConsumeScriptNum(fuzzed_data_provider);
+                });
+        }
+    }
     if (maybe_p2wsh && fuzzed_data_provider.ConsumeBool()) {
         uint256 script_hash;
         CSHA256().Write(r_script.data(), r_script.size()).Finalize(script_hash.begin());
diff --git a/src/test/fuzz/util.h b/src/test/fuzz/util.h
index 1bc6f1db45..40aaeac63f 100644
--- a/src/test/fuzz/util.h
+++ b/src/test/fuzz/util.h
@@ -132,7 +132,7 @@ template <typename WeakEnumType, size_t size>
 
 [[nodiscard]] CScriptWitness ConsumeScriptWitness(FuzzedDataProvider& fuzzed_data_provider, const size_t max_stack_elem_size = 32) noexcept;
 
-[[nodiscard]] CScript ConsumeScript(FuzzedDataProvider& fuzzed_data_provider, const std::optional<size_t>& max_length = std::nullopt, const bool maybe_p2wsh = false) noexcept;
+[[nodiscard]] CScript ConsumeScript(FuzzedDataProvider& fuzzed_data_provider, const bool maybe_p2wsh = false) noexcept;
 
 [[nodiscard]] uint32_t ConsumeSequence(FuzzedDataProvider& fuzzed_data_provider) noexcept;