LCOV - code coverage report
Current view: top level - src/test/fuzz - miniscript.cpp (source / functions) Hit Total Coverage
Test: fuzz_coverage.info Lines: 14 702 2.0 %
Date: 2023-11-12 01:39:15 Functions: 9 106 8.5 %
Branches: 13 1267 1.0 %

           Branch data     Line data    Source code
       1                 :            : // Copyright (c) 2021-2022 The Bitcoin Core developers
       2                 :            : // Distributed under the MIT software license, see the accompanying
       3                 :            : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       4                 :            : 
       5                 :            : #include <core_io.h>
       6                 :            : #include <hash.h>
       7                 :            : #include <key.h>
       8                 :            : #include <script/miniscript.h>
       9                 :            : #include <script/script.h>
      10                 :            : #include <script/signingprovider.h>
      11                 :            : #include <test/fuzz/FuzzedDataProvider.h>
      12                 :            : #include <test/fuzz/fuzz.h>
      13                 :            : #include <test/fuzz/util.h>
      14                 :            : #include <util/strencodings.h>
      15                 :            : 
      16                 :            : namespace {
      17                 :            : 
      18                 :            : using Fragment = miniscript::Fragment;
      19                 :            : using NodeRef = miniscript::NodeRef<CPubKey>;
      20                 :            : using Node = miniscript::Node<CPubKey>;
      21                 :            : using Type = miniscript::Type;
      22                 :            : using MsCtx = miniscript::MiniscriptContext;
      23                 :            : using miniscript::operator"" _mst;
      24                 :            : 
      25                 :          2 : //! Some pre-computed data for more efficient string roundtrips and to simulate challenges.
      26                 :          0 : struct TestData {
      27                 :            :     typedef CPubKey Key;
      28                 :            : 
      29                 :            :     // Precomputed public keys, and a dummy signature for each of them.
      30                 :            :     std::vector<Key> dummy_keys;
      31                 :            :     std::map<Key, int> dummy_key_idx_map;
      32                 :            :     std::map<CKeyID, Key> dummy_keys_map;
      33                 :            :     std::map<Key, std::pair<std::vector<unsigned char>, bool>> dummy_sigs;
      34                 :            :     std::map<XOnlyPubKey, std::pair<std::vector<unsigned char>, bool>> schnorr_sigs;
      35                 :            : 
      36                 :            :     // Precomputed hashes of each kind.
      37                 :            :     std::vector<std::vector<unsigned char>> sha256;
      38                 :            :     std::vector<std::vector<unsigned char>> ripemd160;
      39                 :            :     std::vector<std::vector<unsigned char>> hash256;
      40                 :            :     std::vector<std::vector<unsigned char>> hash160;
      41                 :            :     std::map<std::vector<unsigned char>, std::vector<unsigned char>> sha256_preimages;
      42                 :            :     std::map<std::vector<unsigned char>, std::vector<unsigned char>> ripemd160_preimages;
      43                 :            :     std::map<std::vector<unsigned char>, std::vector<unsigned char>> hash256_preimages;
      44                 :            :     std::map<std::vector<unsigned char>, std::vector<unsigned char>> hash160_preimages;
      45                 :            : 
      46                 :            :     //! Set the precomputed data.
      47                 :          0 :     void Init() {
      48                 :          0 :         unsigned char keydata[32] = {1};
      49                 :            :         // All our signatures sign (and are required to sign) this constant message.
      50                 :          0 :         auto const MESSAGE_HASH{uint256S("f5cd94e18b6fe77dd7aca9e35c2b0c9cbd86356c80a71065")};
      51                 :            :         // We don't pass additional randomness when creating a schnorr signature.
      52                 :          0 :         auto const EMPTY_AUX{uint256S("")};
      53                 :            : 
      54         [ #  # ]:          0 :         for (size_t i = 0; i < 256; i++) {
      55                 :          0 :             keydata[31] = i;
      56                 :          0 :             CKey privkey;
      57         [ #  # ]:          0 :             privkey.Set(keydata, keydata + 32, true);
      58         [ #  # ]:          0 :             const Key pubkey = privkey.GetPubKey();
      59                 :            : 
      60         [ #  # ]:          0 :             dummy_keys.push_back(pubkey);
      61         [ #  # ]:          0 :             dummy_key_idx_map.emplace(pubkey, i);
      62 [ #  # ][ #  # ]:          0 :             dummy_keys_map.insert({pubkey.GetID(), pubkey});
                 [ #  # ]
      63         [ #  # ]:          0 :             XOnlyPubKey xonly_pubkey{pubkey};
      64         [ #  # ]:          0 :             dummy_key_idx_map.emplace(xonly_pubkey, i);
      65         [ #  # ]:          0 :             uint160 xonly_hash{Hash160(xonly_pubkey)};
      66         [ #  # ]:          0 :             dummy_keys_map.emplace(xonly_hash, pubkey);
      67                 :            : 
      68         [ #  # ]:          0 :             std::vector<unsigned char> sig, schnorr_sig(64);
      69         [ #  # ]:          0 :             privkey.Sign(MESSAGE_HASH, sig);
      70         [ #  # ]:          0 :             sig.push_back(1); // SIGHASH_ALL
      71 [ #  # ][ #  # ]:          0 :             dummy_sigs.insert({pubkey, {sig, i & 1}});
                 [ #  # ]
      72 [ #  # ][ #  # ]:          0 :             assert(privkey.SignSchnorr(MESSAGE_HASH, schnorr_sig, nullptr, EMPTY_AUX));
                 [ #  # ]
      73         [ #  # ]:          0 :             schnorr_sig.push_back(1); // Maximally-sized signature has sighash byte
      74 [ #  # ][ #  # ]:          0 :             schnorr_sigs.emplace(XOnlyPubKey{pubkey}, std::make_pair(std::move(schnorr_sig), i & 1));
                 [ #  # ]
      75                 :            : 
      76                 :          0 :             std::vector<unsigned char> hash;
      77         [ #  # ]:          0 :             hash.resize(32);
      78 [ #  # ][ #  # ]:          0 :             CSHA256().Write(keydata, 32).Finalize(hash.data());
                 [ #  # ]
      79         [ #  # ]:          0 :             sha256.push_back(hash);
      80 [ #  # ][ #  # ]:          0 :             if (i & 1) sha256_preimages[hash] = std::vector<unsigned char>(keydata, keydata + 32);
                 [ #  # ]
      81 [ #  # ][ #  # ]:          0 :             CHash256().Write(keydata).Finalize(hash);
         [ #  # ][ #  # ]
      82         [ #  # ]:          0 :             hash256.push_back(hash);
      83 [ #  # ][ #  # ]:          0 :             if (i & 1) hash256_preimages[hash] = std::vector<unsigned char>(keydata, keydata + 32);
                 [ #  # ]
      84         [ #  # ]:          0 :             hash.resize(20);
      85 [ #  # ][ #  # ]:          0 :             CRIPEMD160().Write(keydata, 32).Finalize(hash.data());
                 [ #  # ]
      86         [ #  # ]:          0 :             assert(hash.size() == 20);
      87         [ #  # ]:          0 :             ripemd160.push_back(hash);
      88 [ #  # ][ #  # ]:          0 :             if (i & 1) ripemd160_preimages[hash] = std::vector<unsigned char>(keydata, keydata + 32);
                 [ #  # ]
      89 [ #  # ][ #  # ]:          0 :             CHash160().Write(keydata).Finalize(hash);
         [ #  # ][ #  # ]
      90         [ #  # ]:          0 :             hash160.push_back(hash);
      91 [ #  # ][ #  # ]:          0 :             if (i & 1) hash160_preimages[hash] = std::vector<unsigned char>(keydata, keydata + 32);
                 [ #  # ]
      92                 :          0 :         }
      93                 :          0 :     }
      94                 :            : 
      95                 :            :     //! Get the (Schnorr or ECDSA, depending on context) signature for this pubkey.
      96                 :          0 :     const std::pair<std::vector<unsigned char>, bool>* GetSig(const MsCtx script_ctx, const Key& key) const {
      97         [ #  # ]:          0 :         if (!miniscript::IsTapscript(script_ctx)) {
      98                 :          0 :             const auto it = dummy_sigs.find(key);
      99         [ #  # ]:          0 :             if (it == dummy_sigs.end()) return nullptr;
     100                 :          0 :             return &it->second;
     101                 :            :         } else {
     102                 :          0 :             const auto it = schnorr_sigs.find(XOnlyPubKey{key});
     103         [ #  # ]:          0 :             if (it == schnorr_sigs.end()) return nullptr;
     104                 :          0 :             return &it->second;
     105                 :            :         }
     106                 :          0 :     }
     107                 :          2 : } TEST_DATA;
     108                 :            : 
     109                 :            : /**
     110                 :            :  * Context to parse a Miniscript node to and from Script or text representation.
     111                 :            :  * Uses an integer (an index in the dummy keys array from the test data) as keys in order
     112                 :            :  * to focus on fuzzing the Miniscript nodes' test representation, not the key representation.
     113                 :            :  */
     114                 :            : struct ParserContext {
     115                 :            :     typedef CPubKey Key;
     116                 :            : 
     117                 :            :     const MsCtx script_ctx;
     118                 :            : 
     119                 :          0 :     constexpr ParserContext(MsCtx ctx) noexcept : script_ctx(ctx) {}
     120                 :            : 
     121                 :          0 :     bool KeyCompare(const Key& a, const Key& b) const {
     122                 :          0 :         return a < b;
     123                 :            :     }
     124                 :            : 
     125                 :          0 :     std::optional<std::string> ToString(const Key& key) const
     126                 :            :     {
     127                 :          0 :         auto it = TEST_DATA.dummy_key_idx_map.find(key);
     128         [ #  # ]:          0 :         if (it == TEST_DATA.dummy_key_idx_map.end()) return {};
     129                 :          0 :         uint8_t idx = it->second;
     130                 :          0 :         return HexStr(Span{&idx, 1});
     131                 :          0 :     }
     132                 :            : 
     133                 :          0 :     std::vector<unsigned char> ToPKBytes(const Key& key) const {
     134         [ #  # ]:          0 :         if (!miniscript::IsTapscript(script_ctx)) {
     135         [ #  # ]:          0 :             return {key.begin(), key.end()};
     136                 :            :         }
     137                 :          0 :         const XOnlyPubKey xonly_pubkey{key};
     138         [ #  # ]:          0 :         return {xonly_pubkey.begin(), xonly_pubkey.end()};
     139                 :          0 :     }
     140                 :            : 
     141                 :          0 :     std::vector<unsigned char> ToPKHBytes(const Key& key) const {
     142         [ #  # ]:          0 :         if (!miniscript::IsTapscript(script_ctx)) {
     143                 :          0 :             const auto h = Hash160(key);
     144         [ #  # ]:          0 :             return {h.begin(), h.end()};
     145                 :            :         }
     146                 :          0 :         const auto h = Hash160(XOnlyPubKey{key});
     147         [ #  # ]:          0 :         return {h.begin(), h.end()};
     148                 :          0 :     }
     149                 :            : 
     150                 :            :     template<typename I>
     151                 :          0 :     std::optional<Key> FromString(I first, I last) const {
     152         [ #  # ]:          0 :         if (last - first != 2) return {};
     153 [ #  # ][ #  # ]:          0 :         auto idx = ParseHex(std::string(first, last));
     154         [ #  # ]:          0 :         if (idx.size() != 1) return {};
     155                 :          0 :         return TEST_DATA.dummy_keys[idx[0]];
     156                 :          0 :     }
     157                 :            : 
     158                 :            :     template<typename I>
     159                 :          0 :     std::optional<Key> FromPKBytes(I first, I last) const {
     160         [ #  # ]:          0 :         if (!miniscript::IsTapscript(script_ctx)) {
     161                 :          0 :             Key key{first, last};
     162         [ #  # ]:          0 :             if (key.IsValid()) return key;
     163                 :          0 :             return {};
     164                 :            :         }
     165         [ #  # ]:          0 :         if (last - first != 32) return {};
     166                 :          0 :         XOnlyPubKey xonly_pubkey;
     167                 :          0 :         std::copy(first, last, xonly_pubkey.begin());
     168                 :          0 :         return xonly_pubkey.GetEvenCorrespondingCPubKey();
     169                 :          0 :     }
     170                 :            : 
     171                 :            :     template<typename I>
     172                 :          0 :     std::optional<Key> FromPKHBytes(I first, I last) const {
     173         [ #  # ]:          0 :         assert(last - first == 20);
     174                 :          0 :         CKeyID keyid;
     175                 :          0 :         std::copy(first, last, keyid.begin());
     176                 :          0 :         const auto it = TEST_DATA.dummy_keys_map.find(keyid);
     177         [ #  # ]:          0 :         if (it == TEST_DATA.dummy_keys_map.end()) return {};
     178                 :          0 :         return it->second;
     179                 :          0 :     }
     180                 :            : 
     181                 :          0 :     MsCtx MsContext() const {
     182                 :          0 :         return script_ctx;
     183                 :            :     }
     184                 :            : };
     185                 :            : 
     186                 :            : //! Context that implements naive conversion from/to script only, for roundtrip testing.
     187                 :            : struct ScriptParserContext {
     188                 :            :     const MsCtx script_ctx;
     189                 :            : 
     190                 :          0 :     constexpr ScriptParserContext(MsCtx ctx) noexcept : script_ctx(ctx) {}
     191                 :            : 
     192                 :            :     //! For Script roundtrip we never need the key from a key hash.
     193                 :          0 :     struct Key {
     194                 :            :         bool is_hash;
     195                 :            :         std::vector<unsigned char> data;
     196                 :            :     };
     197                 :            : 
     198                 :          0 :     bool KeyCompare(const Key& a, const Key& b) const {
     199                 :          0 :         return a.data < b.data;
     200                 :            :     }
     201                 :            : 
     202                 :          0 :     const std::vector<unsigned char>& ToPKBytes(const Key& key) const
     203                 :            :     {
     204         [ #  # ]:          0 :         assert(!key.is_hash);
     205                 :          0 :         return key.data;
     206                 :            :     }
     207                 :            : 
     208                 :          0 :     std::vector<unsigned char> ToPKHBytes(const Key& key) const
     209                 :            :     {
     210         [ #  # ]:          0 :         if (key.is_hash) return key.data;
     211                 :          0 :         const auto h = Hash160(key.data);
     212         [ #  # ]:          0 :         return {h.begin(), h.end()};
     213                 :          0 :     }
     214                 :            : 
     215                 :            :     template<typename I>
     216                 :          0 :     std::optional<Key> FromPKBytes(I first, I last) const
     217                 :            :     {
     218                 :          0 :         Key key;
     219         [ #  # ]:          0 :         key.data.assign(first, last);
     220                 :          0 :         key.is_hash = false;
     221                 :          0 :         return key;
     222                 :          0 :     }
     223                 :            : 
     224                 :            :     template<typename I>
     225                 :          0 :     std::optional<Key> FromPKHBytes(I first, I last) const
     226                 :            :     {
     227                 :          0 :         Key key;
     228         [ #  # ]:          0 :         key.data.assign(first, last);
     229                 :          0 :         key.is_hash = true;
     230                 :          0 :         return key;
     231                 :          0 :     }
     232                 :            : 
     233                 :          0 :     MsCtx MsContext() const {
     234                 :          0 :         return script_ctx;
     235                 :            :     }
     236                 :            : };
     237                 :            : 
     238                 :            : //! Context to produce a satisfaction for a Miniscript node using the pre-computed data.
     239                 :            : struct SatisfierContext : ParserContext {
     240                 :            : 
     241                 :          0 :     constexpr SatisfierContext(MsCtx ctx) noexcept : ParserContext(ctx) {}
     242                 :            : 
     243                 :            :     // Timelock challenges satisfaction. Make the value (deterministically) vary to explore different
     244                 :            :     // paths.
     245                 :          0 :     bool CheckAfter(uint32_t value) const { return value % 2; }
     246                 :          0 :     bool CheckOlder(uint32_t value) const { return value % 2; }
     247                 :            : 
     248                 :            :     // Signature challenges fulfilled with a dummy signature, if it was one of our dummy keys.
     249                 :          0 :     miniscript::Availability Sign(const CPubKey& key, std::vector<unsigned char>& sig) const {
     250                 :          0 :         bool sig_available{false};
     251         [ #  # ]:          0 :         if (auto res = TEST_DATA.GetSig(script_ctx, key)) {
     252                 :          0 :             std::tie(sig, sig_available) = *res;
     253                 :          0 :         }
     254                 :          0 :         return sig_available ? miniscript::Availability::YES : miniscript::Availability::NO;
     255                 :            :     }
     256                 :            : 
     257                 :            :     //! Lookup generalization for all the hash satisfactions below
     258                 :          0 :     miniscript::Availability LookupHash(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage,
     259                 :            :                                         const std::map<std::vector<unsigned char>, std::vector<unsigned char>>& map) const
     260                 :            :     {
     261                 :          0 :         const auto it = map.find(hash);
     262         [ #  # ]:          0 :         if (it == map.end()) return miniscript::Availability::NO;
     263                 :          0 :         preimage = it->second;
     264                 :          0 :         return miniscript::Availability::YES;
     265                 :          0 :     }
     266                 :          0 :     miniscript::Availability SatSHA256(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
     267                 :          0 :         return LookupHash(hash, preimage, TEST_DATA.sha256_preimages);
     268                 :            :     }
     269                 :          0 :     miniscript::Availability SatRIPEMD160(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
     270                 :          0 :         return LookupHash(hash, preimage, TEST_DATA.ripemd160_preimages);
     271                 :            :     }
     272                 :          0 :     miniscript::Availability SatHASH256(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
     273                 :          0 :         return LookupHash(hash, preimage, TEST_DATA.hash256_preimages);
     274                 :            :     }
     275                 :          0 :     miniscript::Availability SatHASH160(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
     276                 :          0 :         return LookupHash(hash, preimage, TEST_DATA.hash160_preimages);
     277                 :            :     }
     278                 :            : };
     279                 :            : 
     280                 :            : //! Context to check a satisfaction against the pre-computed data.
     281                 :          0 : const struct CheckerContext: BaseSignatureChecker {
     282                 :            :     // Signature checker methods. Checks the right dummy signature is used.
     283                 :          0 :     bool CheckECDSASignature(const std::vector<unsigned char>& sig, const std::vector<unsigned char>& vchPubKey,
     284                 :            :                              const CScript& scriptCode, SigVersion sigversion) const override
     285                 :            :     {
     286                 :          0 :         const CPubKey key{vchPubKey};
     287                 :          0 :         const auto it = TEST_DATA.dummy_sigs.find(key);
     288         [ #  # ]:          0 :         if (it == TEST_DATA.dummy_sigs.end()) return false;
     289                 :          0 :         return it->second.first == sig;
     290                 :          0 :     }
     291                 :          0 :     bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion,
     292                 :            :                                ScriptExecutionData&, ScriptError*) const override {
     293                 :          0 :         XOnlyPubKey pk{pubkey};
     294                 :          0 :         auto it = TEST_DATA.schnorr_sigs.find(pk);
     295         [ #  # ]:          0 :         if (it == TEST_DATA.schnorr_sigs.end()) return false;
     296                 :          0 :         return it->second.first == sig;
     297                 :          0 :     }
     298                 :          0 :     bool CheckLockTime(const CScriptNum& nLockTime) const override { return nLockTime.GetInt64() & 1; }
     299                 :          0 :     bool CheckSequence(const CScriptNum& nSequence) const override { return nSequence.GetInt64() & 1; }
     300                 :            : } CHECKER_CTX;
     301                 :            : 
     302                 :            : //! Context to check for duplicates when instancing a Node.
     303                 :            : const struct KeyComparator {
     304                 :          0 :     bool KeyCompare(const CPubKey& a, const CPubKey& b) const {
     305                 :          0 :         return a < b;
     306                 :            :     }
     307                 :            : } KEY_COMP;
     308                 :            : 
     309                 :            : // A dummy scriptsig to pass to VerifyScript (we always use Segwit v0).
     310                 :          2 : const CScript DUMMY_SCRIPTSIG;
     311                 :            : 
     312                 :            : //! Public key to be used as internal key for dummy Taproot spends.
     313                 :          2 : const std::vector<unsigned char> NUMS_PK{ParseHex("50929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0")};
     314                 :            : 
     315                 :            : //! Construct a miniscript node as a shared_ptr.
     316                 :          0 : template<typename... Args> NodeRef MakeNodeRef(Args&&... args) {
     317                 :          0 :     return miniscript::MakeNodeRef<CPubKey>(miniscript::internal::NoDupCheck{}, std::forward<Args>(args)...);
     318                 :            : }
     319                 :            : 
     320                 :            : /** Information about a yet to be constructed Miniscript node. */
     321         [ #  # ]:          0 : struct NodeInfo {
     322                 :            :     //! The type of this node
     323                 :            :     Fragment fragment;
     324                 :            :     //! The timelock value for older() and after(), the threshold value for multi() and thresh()
     325                 :            :     uint32_t k;
     326         [ +  - ]:          2 :     //! Keys for this node, if it has some
     327                 :            :     std::vector<CPubKey> keys;
     328 [ +  - ][ -  + ]:          2 :     //! The hash value for this node, if it has one
         [ +  - ][ +  - ]
     329                 :            :     std::vector<unsigned char> hash;
     330         [ +  - ]:          2 :     //! The type requirements for the children of this node.
     331                 :            :     std::vector<Type> subtypes;
     332                 :          2 : 
     333                 :          0 :     NodeInfo(Fragment frag): fragment(frag), k(0) {}
     334 [ +  - ][ +  - ]:          2 :     NodeInfo(Fragment frag, CPubKey key): fragment(frag), k(0), keys({key}) {}
                 [ #  # ]
     335                 :          0 :     NodeInfo(Fragment frag, uint32_t _k): fragment(frag), k(_k) {}
     336                 :          0 :     NodeInfo(Fragment frag, std::vector<unsigned char> h): fragment(frag), k(0), hash(std::move(h)) {}
     337                 :          0 :     NodeInfo(std::vector<Type> subt, Fragment frag): fragment(frag), k(0), subtypes(std::move(subt)) {}
     338                 :          0 :     NodeInfo(std::vector<Type> subt, Fragment frag, uint32_t _k): fragment(frag), k(_k), subtypes(std::move(subt))  {}
     339                 :          0 :     NodeInfo(Fragment frag, uint32_t _k, std::vector<CPubKey> _keys): fragment(frag), k(_k), keys(std::move(_keys)) {}
     340                 :            : };
     341                 :            : 
     342                 :            : /** Pick an index in a collection from a single byte in the fuzzer's output. */
     343                 :            : template<typename T, typename A>
     344                 :          0 : T ConsumeIndex(FuzzedDataProvider& provider, A& col) {
     345                 :          0 :     const uint8_t i = provider.ConsumeIntegral<uint8_t>();
     346                 :          0 :     return col[i];
     347                 :            : }
     348                 :            : 
     349                 :          0 : CPubKey ConsumePubKey(FuzzedDataProvider& provider) {
     350                 :          0 :     return ConsumeIndex<CPubKey>(provider, TEST_DATA.dummy_keys);
     351                 :            : }
     352                 :            : 
     353                 :          0 : std::vector<unsigned char> ConsumeSha256(FuzzedDataProvider& provider) {
     354                 :          0 :     return ConsumeIndex<std::vector<unsigned char>>(provider, TEST_DATA.sha256);
     355                 :            : }
     356                 :            : 
     357                 :          0 : std::vector<unsigned char> ConsumeHash256(FuzzedDataProvider& provider) {
     358                 :          0 :     return ConsumeIndex<std::vector<unsigned char>>(provider, TEST_DATA.hash256);
     359                 :            : }
     360                 :            : 
     361                 :          0 : std::vector<unsigned char> ConsumeRipemd160(FuzzedDataProvider& provider) {
     362                 :          0 :     return ConsumeIndex<std::vector<unsigned char>>(provider, TEST_DATA.ripemd160);
     363                 :            : }
     364                 :            : 
     365                 :          0 : std::vector<unsigned char> ConsumeHash160(FuzzedDataProvider& provider) {
     366                 :          0 :     return ConsumeIndex<std::vector<unsigned char>>(provider, TEST_DATA.hash160);
     367                 :            : }
     368                 :            : 
     369                 :          0 : std::optional<uint32_t> ConsumeTimeLock(FuzzedDataProvider& provider) {
     370                 :          0 :     const uint32_t k = provider.ConsumeIntegral<uint32_t>();
     371 [ #  # ][ #  # ]:          0 :     if (k == 0 || k >= 0x80000000) return {};
     372                 :          0 :     return k;
     373                 :          0 : }
     374                 :            : 
     375                 :            : /**
     376                 :            :  * Consume a Miniscript node from the fuzzer's output.
     377                 :            :  *
     378                 :            :  * This version is intended to have a fixed, stable, encoding for Miniscript nodes:
     379                 :            :  *  - The first byte sets the type of the fragment. 0, 1 and all non-leaf fragments but thresh() are a
     380                 :            :  *    single byte.
     381                 :            :  *  - For the other leaf fragments, the following bytes depend on their type.
     382                 :            :  *    - For older() and after(), the next 4 bytes define the timelock value.
     383                 :            :  *    - For pk_k(), pk_h(), and all hashes, the next byte defines the index of the value in the test data.
     384                 :            :  *    - For multi(), the next 2 bytes define respectively the threshold and the number of keys. Then as many
     385                 :            :  *      bytes as the number of keys define the index of each key in the test data.
     386                 :            :  *    - For multi_a(), same as for multi() but the threshold and the keys count are encoded on two bytes.
     387                 :            :  *    - For thresh(), the next byte defines the threshold value and the following one the number of subs.
     388                 :            :  */
     389                 :          0 : std::optional<NodeInfo> ConsumeNodeStable(MsCtx script_ctx, FuzzedDataProvider& provider, Type type_needed) {
     390         [ #  # ]:          0 :     bool allow_B = (type_needed == ""_mst) || (type_needed << "B"_mst);
     391         [ #  # ]:          0 :     bool allow_K = (type_needed == ""_mst) || (type_needed << "K"_mst);
     392         [ #  # ]:          0 :     bool allow_V = (type_needed == ""_mst) || (type_needed << "V"_mst);
     393         [ #  # ]:          0 :     bool allow_W = (type_needed == ""_mst) || (type_needed << "W"_mst);
     394                 :            : 
     395   [ #  #  #  #  :          0 :     switch (provider.ConsumeIntegral<uint8_t>()) {
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
     396                 :            :         case 0:
     397         [ #  # ]:          0 :             if (!allow_B) return {};
     398                 :          0 :             return {{Fragment::JUST_0}};
     399                 :            :         case 1:
     400         [ #  # ]:          0 :             if (!allow_B) return {};
     401                 :          0 :             return {{Fragment::JUST_1}};
     402                 :            :         case 2:
     403         [ #  # ]:          0 :             if (!allow_K) return {};
     404                 :          0 :             return {{Fragment::PK_K, ConsumePubKey(provider)}};
     405                 :            :         case 3:
     406         [ #  # ]:          0 :             if (!allow_K) return {};
     407                 :          0 :             return {{Fragment::PK_H, ConsumePubKey(provider)}};
     408                 :            :         case 4: {
     409         [ #  # ]:          0 :             if (!allow_B) return {};
     410                 :          0 :             const auto k = ConsumeTimeLock(provider);
     411         [ #  # ]:          0 :             if (!k) return {};
     412                 :          0 :             return {{Fragment::OLDER, *k}};
     413                 :            :         }
     414                 :            :         case 5: {
     415         [ #  # ]:          0 :             if (!allow_B) return {};
     416                 :          0 :             const auto k = ConsumeTimeLock(provider);
     417         [ #  # ]:          0 :             if (!k) return {};
     418                 :          0 :             return {{Fragment::AFTER, *k}};
     419                 :            :         }
     420                 :            :         case 6:
     421         [ #  # ]:          0 :             if (!allow_B) return {};
     422         [ #  # ]:          0 :             return {{Fragment::SHA256, ConsumeSha256(provider)}};
     423                 :            :         case 7:
     424         [ #  # ]:          0 :             if (!allow_B) return {};
     425         [ #  # ]:          0 :             return {{Fragment::HASH256, ConsumeHash256(provider)}};
     426                 :            :         case 8:
     427         [ #  # ]:          0 :             if (!allow_B) return {};
     428         [ #  # ]:          0 :             return {{Fragment::RIPEMD160, ConsumeRipemd160(provider)}};
     429                 :            :         case 9:
     430         [ #  # ]:          0 :             if (!allow_B) return {};
     431         [ #  # ]:          0 :             return {{Fragment::HASH160, ConsumeHash160(provider)}};
     432                 :            :         case 10: {
     433 [ #  # ][ #  # ]:          0 :             if (!allow_B || IsTapscript(script_ctx)) return {};
     434                 :          0 :             const auto k = provider.ConsumeIntegral<uint8_t>();
     435                 :          0 :             const auto n_keys = provider.ConsumeIntegral<uint8_t>();
     436 [ #  # ][ #  # ]:          0 :             if (n_keys > 20 || k == 0 || k > n_keys) return {};
                 [ #  # ]
     437         [ #  # ]:          0 :             std::vector<CPubKey> keys{n_keys};
     438 [ #  # ][ #  # ]:          0 :             for (auto& key: keys) key = ConsumePubKey(provider);
     439         [ #  # ]:          0 :             return {{Fragment::MULTI, k, std::move(keys)}};
     440                 :          0 :         }
     441                 :            :         case 11:
     442 [ #  # ][ #  # ]:          0 :             if (!(allow_B || allow_K || allow_V)) return {};
                 [ #  # ]
     443 [ #  # ][ #  # ]:          0 :             return {{{"B"_mst, type_needed, type_needed}, Fragment::ANDOR}};
     444                 :            :         case 12:
     445 [ #  # ][ #  # ]:          0 :             if (!(allow_B || allow_K || allow_V)) return {};
                 [ #  # ]
     446 [ #  # ][ #  # ]:          0 :             return {{{"V"_mst, type_needed}, Fragment::AND_V}};
     447                 :            :         case 13:
     448         [ #  # ]:          0 :             if (!allow_B) return {};
     449 [ #  # ][ #  # ]:          0 :             return {{{"B"_mst, "W"_mst}, Fragment::AND_B}};
     450                 :            :         case 15:
     451         [ #  # ]:          0 :             if (!allow_B) return {};
     452 [ #  # ][ #  # ]:          0 :             return {{{"B"_mst, "W"_mst}, Fragment::OR_B}};
     453                 :            :         case 16:
     454         [ #  # ]:          0 :             if (!allow_V) return {};
     455 [ #  # ][ #  # ]:          0 :             return {{{"B"_mst, "V"_mst}, Fragment::OR_C}};
     456                 :            :         case 17:
     457         [ #  # ]:          0 :             if (!allow_B) return {};
     458 [ #  # ][ #  # ]:          0 :             return {{{"B"_mst, "B"_mst}, Fragment::OR_D}};
     459                 :            :         case 18:
     460 [ #  # ][ #  # ]:          0 :             if (!(allow_B || allow_K || allow_V)) return {};
                 [ #  # ]
     461 [ #  # ][ #  # ]:          0 :             return {{{type_needed, type_needed}, Fragment::OR_I}};
     462                 :            :         case 19: {
     463         [ #  # ]:          0 :             if (!allow_B) return {};
     464                 :          0 :             auto k = provider.ConsumeIntegral<uint8_t>();
     465                 :          0 :             auto n_subs = provider.ConsumeIntegral<uint8_t>();
     466 [ #  # ][ #  # ]:          0 :             if (k == 0 || k > n_subs) return {};
     467                 :          0 :             std::vector<Type> subtypes;
     468         [ #  # ]:          0 :             subtypes.reserve(n_subs);
     469 [ #  # ][ #  # ]:          0 :             subtypes.emplace_back("B"_mst);
     470 [ #  # ][ #  # ]:          0 :             for (size_t i = 1; i < n_subs; ++i) subtypes.emplace_back("W"_mst);
                 [ #  # ]
     471         [ #  # ]:          0 :             return {{std::move(subtypes), Fragment::THRESH, k}};
     472                 :          0 :         }
     473                 :            :         case 20:
     474         [ #  # ]:          0 :             if (!allow_W) return {};
     475 [ #  # ][ #  # ]:          0 :             return {{{"B"_mst}, Fragment::WRAP_A}};
     476                 :            :         case 21:
     477         [ #  # ]:          0 :             if (!allow_W) return {};
     478 [ #  # ][ #  # ]:          0 :             return {{{"B"_mst}, Fragment::WRAP_S}};
     479                 :            :         case 22:
     480         [ #  # ]:          0 :             if (!allow_B) return {};
     481 [ #  # ][ #  # ]:          0 :             return {{{"K"_mst}, Fragment::WRAP_C}};
     482                 :            :         case 23:
     483         [ #  # ]:          0 :             if (!allow_B) return {};
     484 [ #  # ][ #  # ]:          0 :             return {{{"V"_mst}, Fragment::WRAP_D}};
     485                 :            :         case 24:
     486         [ #  # ]:          0 :             if (!allow_V) return {};
     487 [ #  # ][ #  # ]:          0 :             return {{{"B"_mst}, Fragment::WRAP_V}};
     488                 :            :         case 25:
     489         [ #  # ]:          0 :             if (!allow_B) return {};
     490 [ #  # ][ #  # ]:          0 :             return {{{"B"_mst}, Fragment::WRAP_J}};
     491                 :            :         case 26:
     492         [ #  # ]:          0 :             if (!allow_B) return {};
     493 [ #  # ][ #  # ]:          0 :             return {{{"B"_mst}, Fragment::WRAP_N}};
     494                 :            :         case 27: {
     495 [ #  # ][ #  # ]:          0 :             if (!allow_B || !IsTapscript(script_ctx)) return {};
     496                 :          0 :             const auto k = provider.ConsumeIntegral<uint16_t>();
     497                 :          0 :             const auto n_keys = provider.ConsumeIntegral<uint16_t>();
     498 [ #  # ][ #  # ]:          0 :             if (n_keys > 999 || k == 0 || k > n_keys) return {};
                 [ #  # ]
     499         [ #  # ]:          0 :             std::vector<CPubKey> keys{n_keys};
     500 [ #  # ][ #  # ]:          0 :             for (auto& key: keys) key = ConsumePubKey(provider);
     501         [ #  # ]:          0 :             return {{Fragment::MULTI_A, k, std::move(keys)}};
     502                 :          0 :         }
     503                 :            :         default:
     504                 :          0 :             break;
     505                 :            :     }
     506                 :          0 :     return {};
     507                 :          0 : }
     508                 :            : 
     509                 :            : /* This structure contains a table which for each "target" Type a list of recipes
     510                 :            :  * to construct it, automatically inferred from the behavior of ComputeType.
     511                 :            :  * Note that the Types here are not the final types of the constructed Nodes, but
     512                 :            :  * just the subset that are required. For example, a recipe for the "Bo" type
     513                 :            :  * might construct a "Bondu" sha256() NodeInfo, but cannot construct a "Bz" older().
     514                 :            :  * Each recipe is a Fragment together with a list of required types for its subnodes.
     515                 :            :  */
     516                 :          0 : struct SmartInfo
     517                 :            : {
     518                 :            :     using recipe = std::pair<Fragment, std::vector<Type>>;
     519                 :            :     std::map<Type, std::vector<recipe>> wsh_table, tap_table;
     520                 :            : 
     521                 :          0 :     void Init()
     522                 :            :     {
     523                 :          0 :         Init(wsh_table, MsCtx::P2WSH);
     524                 :          0 :         Init(tap_table, MsCtx::TAPSCRIPT);
     525                 :          0 :     }
     526                 :            : 
     527                 :          0 :     void Init(std::map<Type, std::vector<recipe>>& table, MsCtx script_ctx)
     528                 :            :     {
     529                 :            :         /* Construct a set of interesting type requirements to reason with (sections of BKVWzondu). */
     530                 :          0 :         std::vector<Type> types;
     531         [ #  # ]:          0 :         for (int base = 0; base < 4; ++base) { /* select from B,K,V,W */
     532 [ #  # ][ #  # ]:          0 :             Type type_base = base == 0 ? "B"_mst : base == 1 ? "K"_mst : base == 2 ? "V"_mst : "W"_mst;
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     533         [ #  # ]:          0 :             for (int zo = 0; zo < 3; ++zo) { /* select from z,o,(none) */
     534 [ #  # ][ #  # ]:          0 :                 Type type_zo = zo == 0 ? "z"_mst : zo == 1 ? "o"_mst : ""_mst;
         [ #  # ][ #  # ]
                 [ #  # ]
     535         [ #  # ]:          0 :                 for (int n = 0; n < 2; ++n) { /* select from (none),n */
     536 [ #  # ][ #  # ]:          0 :                     if (zo == 0 && n == 1) continue; /* z conflicts with n */
     537 [ #  # ][ #  # ]:          0 :                     if (base == 3 && n == 1) continue; /* W conflicts with n */
     538 [ #  # ][ #  # ]:          0 :                     Type type_n = n == 0 ? ""_mst : "n"_mst;
                 [ #  # ]
     539         [ #  # ]:          0 :                     for (int d = 0; d < 2; ++d) { /* select from (none),d */
     540 [ #  # ][ #  # ]:          0 :                         if (base == 2 && d == 1) continue; /* V conflicts with d */
     541 [ #  # ][ #  # ]:          0 :                         Type type_d = d == 0 ? ""_mst : "d"_mst;
                 [ #  # ]
     542         [ #  # ]:          0 :                         for (int u = 0; u < 2; ++u) { /* select from (none),u */
     543 [ #  # ][ #  # ]:          0 :                             if (base == 2 && u == 1) continue; /* V conflicts with u */
     544 [ #  # ][ #  # ]:          0 :                             Type type_u = u == 0 ? ""_mst : "u"_mst;
                 [ #  # ]
     545 [ #  # ][ #  # ]:          0 :                             Type type = type_base | type_zo | type_n | type_d | type_u;
         [ #  # ][ #  # ]
     546         [ #  # ]:          0 :                             types.push_back(type);
     547                 :          0 :                         }
     548                 :          0 :                     }
     549                 :          0 :                 }
     550                 :          0 :             }
     551                 :          0 :         }
     552                 :            : 
     553                 :            :         /* We define a recipe a to be a super-recipe of recipe b if they use the same
     554                 :            :          * fragment, the same number of subexpressions, and each of a's subexpression
     555                 :            :          * types is a supertype of the corresponding subexpression type of b.
     556                 :            :          * Within the set of recipes for the construction of a given type requirement,
     557                 :            :          * no recipe should be a super-recipe of another (as the super-recipe is
     558                 :            :          * applicable in every place the sub-recipe is, the sub-recipe is redundant). */
     559                 :          0 :         auto is_super_of = [](const recipe& a, const recipe& b) {
     560         [ #  # ]:          0 :             if (a.first != b.first) return false;
     561         [ #  # ]:          0 :             if (a.second.size() != b.second.size()) return false;
     562         [ #  # ]:          0 :             for (size_t i = 0; i < a.second.size(); ++i) {
     563         [ #  # ]:          0 :                 if (!(b.second[i] << a.second[i])) return false;
     564                 :          0 :             }
     565                 :          0 :             return true;
     566                 :          0 :         };
     567                 :            : 
     568                 :            :         /* Sort the type requirements. Subtypes will always sort later (e.g. Bondu will
     569                 :            :          * sort after Bo or Bu). As we'll be constructing recipes using these types, in
     570                 :            :          * order, in what follows, we'll construct super-recipes before sub-recipes.
     571                 :            :          * That means we never need to go back and delete a sub-recipe because a
     572                 :            :          * super-recipe got added. */
     573         [ #  # ]:          0 :         std::sort(types.begin(), types.end());
     574                 :            : 
     575                 :            :         // Iterate over all possible fragments.
     576         [ #  # ]:          0 :         for (int fragidx = 0; fragidx <= int(Fragment::MULTI_A); ++fragidx) {
     577                 :          0 :             int sub_count = 0; //!< The minimum number of child nodes this recipe has.
     578                 :          0 :             int sub_range = 1; //!< The maximum number of child nodes for this recipe is sub_count+sub_range-1.
     579                 :          0 :             size_t data_size = 0;
     580                 :          0 :             size_t n_keys = 0;
     581                 :          0 :             uint32_t k = 0;
     582                 :          0 :             Fragment frag{fragidx};
     583                 :            : 
     584                 :            :             // Only produce recipes valid in the given context.
     585 [ #  # ][ #  # ]:          0 :             if ((!miniscript::IsTapscript(script_ctx) && frag == Fragment::MULTI_A)
                 [ #  # ]
     586 [ #  # ][ #  # ]:          0 :                 || (miniscript::IsTapscript(script_ctx) && frag == Fragment::MULTI)) {
                 [ #  # ]
     587                 :          0 :                 continue;
     588                 :            :             }
     589                 :            : 
     590                 :            :             // Based on the fragment, determine #subs/data/k/keys to pass to ComputeType. */
     591   [ #  #  #  #  :          0 :             switch (frag) {
          #  #  #  #  #  
                   #  # ]
     592                 :            :                 case Fragment::PK_K:
     593                 :            :                 case Fragment::PK_H:
     594                 :          0 :                     n_keys = 1;
     595                 :          0 :                     break;
     596                 :            :                 case Fragment::MULTI:
     597                 :            :                 case Fragment::MULTI_A:
     598                 :          0 :                     n_keys = 1;
     599                 :          0 :                     k = 1;
     600                 :          0 :                     break;
     601                 :            :                 case Fragment::OLDER:
     602                 :            :                 case Fragment::AFTER:
     603                 :          0 :                     k = 1;
     604                 :          0 :                     break;
     605                 :            :                 case Fragment::SHA256:
     606                 :            :                 case Fragment::HASH256:
     607                 :          0 :                     data_size = 32;
     608                 :          0 :                     break;
     609                 :            :                 case Fragment::RIPEMD160:
     610                 :            :                 case Fragment::HASH160:
     611                 :          0 :                     data_size = 20;
     612                 :          0 :                     break;
     613                 :            :                 case Fragment::JUST_0:
     614                 :            :                 case Fragment::JUST_1:
     615                 :          0 :                     break;
     616                 :            :                 case Fragment::WRAP_A:
     617                 :            :                 case Fragment::WRAP_S:
     618                 :            :                 case Fragment::WRAP_C:
     619                 :            :                 case Fragment::WRAP_D:
     620                 :            :                 case Fragment::WRAP_V:
     621                 :            :                 case Fragment::WRAP_J:
     622                 :            :                 case Fragment::WRAP_N:
     623                 :          0 :                     sub_count = 1;
     624                 :          0 :                     break;
     625                 :            :                 case Fragment::AND_V:
     626                 :            :                 case Fragment::AND_B:
     627                 :            :                 case Fragment::OR_B:
     628                 :            :                 case Fragment::OR_C:
     629                 :            :                 case Fragment::OR_D:
     630                 :            :                 case Fragment::OR_I:
     631                 :          0 :                     sub_count = 2;
     632                 :          0 :                     break;
     633                 :            :                 case Fragment::ANDOR:
     634                 :          0 :                     sub_count = 3;
     635                 :          0 :                     break;
     636                 :            :                 case Fragment::THRESH:
     637                 :            :                     // Thresh logic is executed for 1 and 2 arguments. Larger numbers use ad-hoc code to extend.
     638                 :          0 :                     sub_count = 1;
     639                 :          0 :                     sub_range = 2;
     640                 :          0 :                     k = 1;
     641                 :          0 :                     break;
     642                 :            :             }
     643                 :            : 
     644                 :            :             // Iterate over the number of subnodes (sub_count...sub_count+sub_range-1).
     645                 :          0 :             std::vector<Type> subt;
     646         [ #  # ]:          0 :             for (int subs = sub_count; subs < sub_count + sub_range; ++subs) {
     647                 :            :                 // Iterate over the possible subnode types (at most 3).
     648         [ #  # ]:          0 :                 for (Type x : types) {
     649         [ #  # ]:          0 :                     for (Type y : types) {
     650         [ #  # ]:          0 :                         for (Type z : types) {
     651                 :            :                             // Compute the resulting type of a node with the selected fragment / subnode types.
     652                 :          0 :                             subt.clear();
     653 [ #  # ][ #  # ]:          0 :                             if (subs > 0) subt.push_back(x);
     654 [ #  # ][ #  # ]:          0 :                             if (subs > 1) subt.push_back(y);
     655 [ #  # ][ #  # ]:          0 :                             if (subs > 2) subt.push_back(z);
     656         [ #  # ]:          0 :                             Type res = miniscript::internal::ComputeType(frag, x, y, z, subt, k, data_size, subs, n_keys, script_ctx);
     657                 :            :                             // Continue if the result is not a valid node.
     658 [ #  # ][ #  # ]:          0 :                             if ((res << "K"_mst) + (res << "V"_mst) + (res << "B"_mst) + (res << "W"_mst) != 1) continue;
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
     659                 :            : 
     660         [ #  # ]:          0 :                             recipe entry{frag, subt};
     661                 :          0 :                             auto super_of_entry = [&](const recipe& rec) { return is_super_of(rec, entry); };
     662                 :            :                             // Iterate over all supertypes of res (because if e.g. our selected fragment/subnodes result
     663                 :            :                             // in a Bondu, they can form a recipe that is also applicable for constructing a B, Bou, Bdu, ...).
     664         [ #  # ]:          0 :                             for (Type s : types) {
     665 [ #  # ][ #  # ]:          0 :                                 if ((res & "BKVWzondu"_mst) << s) {
         [ #  # ][ #  # ]
     666         [ #  # ]:          0 :                                     auto& recipes = table[s];
     667                 :            :                                     // If we don't already have a super-recipe to the new one, add it.
     668 [ #  # ][ #  # ]:          0 :                                     if (!std::any_of(recipes.begin(), recipes.end(), super_of_entry)) {
     669         [ #  # ]:          0 :                                         recipes.push_back(entry);
     670                 :          0 :                                     }
     671                 :          0 :                                 }
     672                 :            :                             }
     673                 :            : 
     674         [ #  # ]:          0 :                             if (subs <= 2) break;
     675      [ #  #  # ]:          0 :                         }
     676         [ #  # ]:          0 :                         if (subs <= 1) break;
     677                 :            :                     }
     678         [ #  # ]:          0 :                     if (subs <= 0) break;
     679                 :            :                 }
     680                 :          0 :             }
     681                 :          0 :         }
     682                 :            : 
     683                 :            :         /* Find which types are useful. The fuzzer logic only cares about constructing
     684                 :            :          * B,V,K,W nodes, so any type that isn't needed in any recipe (directly or
     685                 :            :          * indirectly) for the construction of those is uninteresting. */
     686 [ #  # ][ #  # ]:          0 :         std::set<Type> useful_types{"B"_mst, "V"_mst, "K"_mst, "W"_mst};
         [ #  # ][ #  # ]
                 [ #  # ]
     687                 :            :         // Find the transitive closure by adding types until the set of types does not change.
     688                 :          0 :         while (true) {
     689                 :          0 :             size_t set_size = useful_types.size();
     690         [ #  # ]:          0 :             for (const auto& [type, recipes] : table) {
     691 [ #  # ][ #  # ]:          0 :                 if (useful_types.count(type) != 0) {
     692         [ #  # ]:          0 :                     for (const auto& [_, subtypes] : recipes) {
     693 [ #  # ][ #  # ]:          0 :                         for (auto subtype : subtypes) useful_types.insert(subtype);
     694                 :            :                     }
     695                 :          0 :                 }
     696                 :            :             }
     697         [ #  # ]:          0 :             if (useful_types.size() == set_size) break;
     698                 :            :         }
     699                 :            :         // Remove all rules that construct uninteresting types.
     700         [ #  # ]:          0 :         for (auto type_it = table.begin(); type_it != table.end();) {
     701 [ #  # ][ #  # ]:          0 :             if (useful_types.count(type_it->first) == 0) {
     702         [ #  # ]:          0 :                 type_it = table.erase(type_it);
     703                 :          0 :             } else {
     704                 :          0 :                 ++type_it;
     705                 :            :             }
     706                 :            :         }
     707                 :            : 
     708                 :            :         /* Find which types are constructible. A type is constructible if there is a leaf
     709                 :            :          * node recipe for constructing it, or a recipe whose subnodes are all constructible.
     710                 :            :          * Types can be non-constructible because they have no recipes to begin with,
     711                 :            :          * because they can only be constructed using recipes that involve otherwise
     712                 :            :          * non-constructible types, or because they require infinite recursion. */
     713                 :          0 :         std::set<Type> constructible_types{};
     714                 :          0 :         auto known_constructible = [&](Type type) { return constructible_types.count(type) != 0; };
     715                 :            :         // Find the transitive closure by adding types until the set of types does not change.
     716                 :          0 :         while (true) {
     717                 :          0 :             size_t set_size = constructible_types.size();
     718                 :            :             // Iterate over all types we have recipes for.
     719         [ #  # ]:          0 :             for (const auto& [type, recipes] : table) {
     720 [ #  # ][ #  # ]:          0 :                 if (!known_constructible(type)) {
     721                 :            :                     // For not (yet known to be) constructible types, iterate over their recipes.
     722         [ #  # ]:          0 :                     for (const auto& [_, subt] : recipes) {
     723                 :            :                         // If any recipe involves only (already known to be) constructible types,
     724                 :            :                         // add the recipe's type to the set.
     725 [ #  # ][ #  # ]:          0 :                         if (std::all_of(subt.begin(), subt.end(), known_constructible)) {
                 [ #  # ]
     726         [ #  # ]:          0 :                             constructible_types.insert(type);
     727                 :          0 :                             break;
     728                 :            :                         }
     729                 :            :                     }
     730                 :          0 :                 }
     731                 :            :             }
     732         [ #  # ]:          0 :             if (constructible_types.size() == set_size) break;
     733                 :            :         }
     734         [ #  # ]:          0 :         for (auto type_it = table.begin(); type_it != table.end();) {
     735                 :            :             // Remove all recipes which involve non-constructible types.
     736 [ #  # ][ #  # ]:          0 :             type_it->second.erase(std::remove_if(type_it->second.begin(), type_it->second.end(),
         [ #  # ][ #  # ]
     737                 :          0 :                 [&](const recipe& rec) {
     738                 :          0 :                     return !std::all_of(rec.second.begin(), rec.second.end(), known_constructible);
     739                 :          0 :                 }), type_it->second.end());
     740                 :            :             // Delete types entirely which have no recipes left.
     741         [ #  # ]:          0 :             if (type_it->second.empty()) {
     742         [ #  # ]:          0 :                 type_it = table.erase(type_it);
     743                 :          0 :             } else {
     744                 :          0 :                 ++type_it;
     745                 :            :             }
     746                 :            :         }
     747                 :            : 
     748         [ #  # ]:          0 :         for (auto& [type, recipes] : table) {
     749                 :            :             // Sort recipes for determinism, and place those using fewer subnodes first.
     750                 :            :             // This avoids runaway expansion (when reaching the end of the fuzz input,
     751                 :            :             // all zeroes are read, resulting in the first available recipe being picked).
     752 [ #  # ][ #  # ]:          0 :             std::sort(recipes.begin(), recipes.end(),
     753                 :          0 :                 [](const recipe& a, const recipe& b) {
     754         [ #  # ]:          0 :                     if (a.second.size() < b.second.size()) return true;
     755         [ #  # ]:          0 :                     if (a.second.size() > b.second.size()) return false;
     756                 :          0 :                     return a < b;
     757                 :          0 :                 }
     758                 :            :             );
     759                 :            :         }
     760                 :          0 :     }
     761                 :          2 : } SMARTINFO;
     762                 :            : 
     763                 :            : /**
     764                 :            :  * Consume a Miniscript node from the fuzzer's output.
     765                 :            :  *
     766                 :            :  * This is similar to ConsumeNodeStable, but uses a precomputed table with permitted
     767                 :            :  * fragments/subnode type for each required type. It is intended to more quickly explore
     768                 :            :  * interesting miniscripts, at the cost of higher implementation complexity (which could
     769                 :            :  * cause it miss things if incorrect), and with less regard for stability of the seeds
     770                 :            :  * (as improvements to the tables or changes to the typing rules could invalidate
     771                 :            :  * everything).
     772                 :            :  */
     773                 :          0 : std::optional<NodeInfo> ConsumeNodeSmart(MsCtx script_ctx, FuzzedDataProvider& provider, Type type_needed) {
     774                 :            :     /** Table entry for the requested type. */
     775         [ #  # ]:          0 :     const auto& table{IsTapscript(script_ctx) ? SMARTINFO.tap_table : SMARTINFO.wsh_table};
     776                 :          0 :     auto recipes_it = table.find(type_needed);
     777         [ #  # ]:          0 :     assert(recipes_it != table.end());
     778                 :            :     /** Pick one recipe from the available ones for that type. */
     779                 :          0 :     const auto& [frag, subt] = PickValue(provider, recipes_it->second);
     780                 :            : 
     781                 :            :     // Based on the fragment the recipe uses, fill in other data (k, keys, data).
     782   [ #  #  #  #  :          0 :     switch (frag) {
          #  #  #  #  #  
                   #  # ]
     783                 :            :         case Fragment::PK_K:
     784                 :            :         case Fragment::PK_H:
     785                 :          0 :             return {{frag, ConsumePubKey(provider)}};
     786                 :            :         case Fragment::MULTI: {
     787                 :          0 :             const auto n_keys = provider.ConsumeIntegralInRange<uint8_t>(1, 20);
     788                 :          0 :             const auto k = provider.ConsumeIntegralInRange<uint8_t>(1, n_keys);
     789         [ #  # ]:          0 :             std::vector<CPubKey> keys{n_keys};
     790 [ #  # ][ #  # ]:          0 :             for (auto& key: keys) key = ConsumePubKey(provider);
     791         [ #  # ]:          0 :             return {{frag, k, std::move(keys)}};
     792                 :          0 :         }
     793                 :            :         case Fragment::MULTI_A: {
     794                 :          0 :             const auto n_keys = provider.ConsumeIntegralInRange<uint16_t>(1, 999);
     795                 :          0 :             const auto k = provider.ConsumeIntegralInRange<uint16_t>(1, n_keys);
     796         [ #  # ]:          0 :             std::vector<CPubKey> keys{n_keys};
     797 [ #  # ][ #  # ]:          0 :             for (auto& key: keys) key = ConsumePubKey(provider);
     798         [ #  # ]:          0 :             return {{frag, k, std::move(keys)}};
     799                 :          0 :         }
     800                 :            :         case Fragment::OLDER:
     801                 :            :         case Fragment::AFTER:
     802                 :          0 :             return {{frag, provider.ConsumeIntegralInRange<uint32_t>(1, 0x7FFFFFF)}};
     803                 :            :         case Fragment::SHA256:
     804         [ #  # ]:          0 :             return {{frag, PickValue(provider, TEST_DATA.sha256)}};
     805                 :            :         case Fragment::HASH256:
     806         [ #  # ]:          0 :             return {{frag, PickValue(provider, TEST_DATA.hash256)}};
     807                 :            :         case Fragment::RIPEMD160:
     808         [ #  # ]:          0 :             return {{frag, PickValue(provider, TEST_DATA.ripemd160)}};
     809                 :            :         case Fragment::HASH160:
     810         [ #  # ]:          0 :             return {{frag, PickValue(provider, TEST_DATA.hash160)}};
     811                 :            :         case Fragment::JUST_0:
     812                 :            :         case Fragment::JUST_1:
     813                 :            :         case Fragment::WRAP_A:
     814                 :            :         case Fragment::WRAP_S:
     815                 :            :         case Fragment::WRAP_C:
     816                 :            :         case Fragment::WRAP_D:
     817                 :            :         case Fragment::WRAP_V:
     818                 :            :         case Fragment::WRAP_J:
     819                 :            :         case Fragment::WRAP_N:
     820                 :            :         case Fragment::AND_V:
     821                 :            :         case Fragment::AND_B:
     822                 :            :         case Fragment::OR_B:
     823                 :            :         case Fragment::OR_C:
     824                 :            :         case Fragment::OR_D:
     825                 :            :         case Fragment::OR_I:
     826                 :            :         case Fragment::ANDOR:
     827 [ #  # ][ #  # ]:          0 :             return {{subt, frag}};
     828                 :            :         case Fragment::THRESH: {
     829                 :            :             uint32_t children;
     830         [ #  # ]:          0 :             if (subt.size() < 2) {
     831                 :          0 :                 children = subt.size();
     832                 :          0 :             } else {
     833                 :            :                 // If we hit a thresh with 2 subnodes, artificially extend it to any number
     834                 :            :                 // (2 or larger) by replicating the type of the last subnode.
     835                 :          0 :                 children = provider.ConsumeIntegralInRange<uint32_t>(2, MAX_OPS_PER_SCRIPT / 2);
     836                 :            :             }
     837                 :          0 :             auto k = provider.ConsumeIntegralInRange<uint32_t>(1, children);
     838                 :          0 :             std::vector<Type> subs = subt;
     839 [ #  # ][ #  # ]:          0 :             while (subs.size() < children) subs.push_back(subs.back());
     840 [ #  # ][ #  # ]:          0 :             return {{std::move(subs), frag, k}};
     841                 :          0 :         }
     842                 :            :     }
     843                 :            : 
     844                 :          0 :     assert(false);
     845                 :          0 : }
     846                 :            : 
     847                 :            : /**
     848                 :            :  * Generate a Miniscript node based on the fuzzer's input.
     849                 :            :  *
     850                 :            :  * - ConsumeNode is a function object taking a Type, and returning an std::optional<NodeInfo>.
     851                 :            :  * - root_type is the required type properties of the constructed NodeRef.
     852                 :            :  * - strict_valid sets whether ConsumeNode is expected to guarantee a NodeInfo that results in
     853                 :            :  *   a NodeRef whose Type() matches the type fed to ConsumeNode.
     854                 :            :  */
     855                 :            : template<typename F>
     856                 :          0 : NodeRef GenNode(MsCtx script_ctx, F ConsumeNode, Type root_type, bool strict_valid = false) {
     857                 :            :     /** A stack of miniscript Nodes being built up. */
     858                 :          0 :     std::vector<NodeRef> stack;
     859                 :            :     /** The queue of instructions. */
     860 [ #  # ][ #  # ]:          0 :     std::vector<std::pair<Type, std::optional<NodeInfo>>> todo{{root_type, {}}};
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
     861                 :            :     /** Predict the number of (static) script ops. */
     862                 :          0 :     uint32_t ops{0};
     863                 :            :     /** Predict the total script size (every unexplored subnode is counted as one, as every leaf is
     864                 :            :      *  at least one script byte). */
     865                 :          0 :     uint32_t scriptsize{1};
     866                 :            : 
     867 [ #  # ][ #  # ]:          0 :     while (!todo.empty()) {
     868                 :            :         // The expected type we have to construct.
     869                 :          0 :         auto type_needed = todo.back().first;
     870 [ #  # ][ #  # ]:          0 :         if (!todo.back().second) {
     871                 :            :             // Fragment/children have not been decided yet. Decide them.
     872 [ #  # ][ #  # ]:          0 :             auto node_info = ConsumeNode(type_needed);
     873 [ #  # ][ #  # ]:          0 :             if (!node_info) return {};
     874                 :            :             // Update predicted resource limits. Since every leaf Miniscript node is at least one
     875                 :            :             // byte long, we move one byte from each child to their parent. A similar technique is
     876                 :            :             // used in the miniscript::internal::Parse function to prevent runaway string parsing.
     877 [ #  # ][ #  # ]:          0 :             scriptsize += miniscript::internal::ComputeScriptLen(node_info->fragment, ""_mst, node_info->subtypes.size(), node_info->k, node_info->subtypes.size(),
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
     878                 :          0 :                                                                  node_info->keys.size(), script_ctx) - 1;
     879 [ #  # ][ #  # ]:          0 :             if (scriptsize > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
     880   [ #  #  #  #  :          0 :             switch (node_info->fragment) {
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
           #  #  # ][ #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                      # ]
     881                 :            :             case Fragment::JUST_0:
     882                 :            :             case Fragment::JUST_1:
     883                 :          0 :                 break;
     884                 :            :             case Fragment::PK_K:
     885                 :          0 :                 break;
     886                 :            :             case Fragment::PK_H:
     887                 :          0 :                 ops += 3;
     888                 :          0 :                 break;
     889                 :            :             case Fragment::OLDER:
     890                 :            :             case Fragment::AFTER:
     891                 :          0 :                 ops += 1;
     892                 :          0 :                 break;
     893                 :            :             case Fragment::RIPEMD160:
     894                 :            :             case Fragment::SHA256:
     895                 :            :             case Fragment::HASH160:
     896                 :            :             case Fragment::HASH256:
     897                 :          0 :                 ops += 4;
     898                 :          0 :                 break;
     899                 :            :             case Fragment::ANDOR:
     900                 :          0 :                 ops += 3;
     901                 :          0 :                 break;
     902                 :            :             case Fragment::AND_V:
     903                 :          0 :                 break;
     904                 :            :             case Fragment::AND_B:
     905                 :            :             case Fragment::OR_B:
     906                 :          0 :                 ops += 1;
     907                 :          0 :                 break;
     908                 :            :             case Fragment::OR_C:
     909                 :          0 :                 ops += 2;
     910                 :          0 :                 break;
     911                 :            :             case Fragment::OR_D:
     912                 :          0 :                 ops += 3;
     913                 :          0 :                 break;
     914                 :            :             case Fragment::OR_I:
     915                 :          0 :                 ops += 3;
     916                 :          0 :                 break;
     917                 :            :             case Fragment::THRESH:
     918                 :          0 :                 ops += node_info->subtypes.size();
     919                 :          0 :                 break;
     920                 :            :             case Fragment::MULTI:
     921                 :          0 :                 ops += 1;
     922                 :          0 :                 break;
     923                 :            :             case Fragment::MULTI_A:
     924                 :          0 :                 ops += node_info->keys.size() + 1;
     925                 :          0 :                 break;
     926                 :            :             case Fragment::WRAP_A:
     927                 :          0 :                 ops += 2;
     928                 :          0 :                 break;
     929                 :            :             case Fragment::WRAP_S:
     930                 :          0 :                 ops += 1;
     931                 :          0 :                 break;
     932                 :            :             case Fragment::WRAP_C:
     933                 :          0 :                 ops += 1;
     934                 :          0 :                 break;
     935                 :            :             case Fragment::WRAP_D:
     936                 :          0 :                 ops += 3;
     937                 :          0 :                 break;
     938                 :            :             case Fragment::WRAP_V:
     939                 :            :                 // We don't account for OP_VERIFY here; that will be corrected for when the actual
     940                 :            :                 // node is constructed below.
     941                 :          0 :                 break;
     942                 :            :             case Fragment::WRAP_J:
     943                 :          0 :                 ops += 4;
     944                 :          0 :                 break;
     945                 :            :             case Fragment::WRAP_N:
     946                 :          0 :                 ops += 1;
     947                 :          0 :                 break;
     948                 :            :             }
     949 [ #  # ][ #  # ]:          0 :             if (ops > MAX_OPS_PER_SCRIPT) return {};
     950 [ #  # ][ #  # ]:          0 :             auto subtypes = node_info->subtypes;
     951                 :          0 :             todo.back().second = std::move(node_info);
     952 [ #  # ][ #  # ]:          0 :             todo.reserve(todo.size() + subtypes.size());
     953                 :            :             // As elements on the todo stack are processed back to front, construct
     954                 :            :             // them in reverse order (so that the first subnode is generated first).
     955 [ #  # ][ #  # ]:          0 :             for (size_t i = 0; i < subtypes.size(); ++i) {
     956 [ #  # ][ #  # ]:          0 :                 todo.emplace_back(*(subtypes.rbegin() + i), std::nullopt);
         [ #  # ][ #  # ]
     957                 :          0 :             }
     958 [ #  # ][ #  # ]:          0 :         } else {
     959                 :            :             // The back of todo has fragment and number of children decided, and
     960                 :            :             // those children have been constructed at the back of stack. Pop
     961                 :            :             // that entry off todo, and use it to construct a new NodeRef on
     962                 :            :             // stack.
     963                 :          0 :             NodeInfo& info = *todo.back().second;
     964                 :            :             // Gather children from the back of stack.
     965                 :          0 :             std::vector<NodeRef> sub;
     966 [ #  # ][ #  # ]:          0 :             sub.reserve(info.subtypes.size());
     967 [ #  # ][ #  # ]:          0 :             for (size_t i = 0; i < info.subtypes.size(); ++i) {
     968 [ #  # ][ #  # ]:          0 :                 sub.push_back(std::move(*(stack.end() - info.subtypes.size() + i)));
     969                 :          0 :             }
     970 [ #  # ][ #  # ]:          0 :             stack.erase(stack.end() - info.subtypes.size(), stack.end());
     971                 :            :             // Construct new NodeRef.
     972                 :          0 :             NodeRef node;
     973 [ #  # ][ #  # ]:          0 :             if (info.keys.empty()) {
     974 [ #  # ][ #  # ]:          0 :                 node = MakeNodeRef(script_ctx, info.fragment, std::move(sub), std::move(info.hash), info.k);
     975                 :          0 :             } else {
     976 [ #  # ][ #  # ]:          0 :                 assert(sub.empty());
     977 [ #  # ][ #  # ]:          0 :                 assert(info.hash.empty());
     978 [ #  # ][ #  # ]:          0 :                 node = MakeNodeRef(script_ctx, info.fragment, std::move(info.keys), info.k);
     979                 :            :             }
     980                 :            :             // Verify acceptability.
     981 [ #  # ][ #  # ]:          0 :             if (!node || (node->GetType() & "KVWB"_mst) == ""_mst) {
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
     982 [ #  # ][ #  # ]:          0 :                 assert(!strict_valid);
     983                 :          0 :                 return {};
     984                 :            :             }
     985 [ #  # ][ #  # ]:          0 :             if (!(type_needed == ""_mst)) {
         [ #  # ][ #  # ]
     986 [ #  # ][ #  # ]:          0 :                 assert(node->GetType() << type_needed);
     987                 :          0 :             }
     988 [ #  # ][ #  # ]:          0 :             if (!node->IsValid()) return {};
         [ #  # ][ #  # ]
     989                 :            :             // Update resource predictions.
     990 [ #  # ][ #  # ]:          0 :             if (node->fragment == Fragment::WRAP_V && node->subs[0]->GetType() << "x"_mst) {
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
     991                 :          0 :                 ops += 1;
     992                 :          0 :                 scriptsize += 1;
     993                 :          0 :             }
     994 [ #  # ][ #  # ]:          0 :             if (!miniscript::IsTapscript(script_ctx) && ops > MAX_OPS_PER_SCRIPT) return {};
         [ #  # ][ #  # ]
     995 [ #  # ][ #  # ]:          0 :             if (scriptsize > miniscript::internal::MaxScriptSize(script_ctx)) {
         [ #  # ][ #  # ]
     996                 :          0 :                 return {};
     997                 :            :             }
     998                 :            :             // Move it to the stack.
     999 [ #  # ][ #  # ]:          0 :             stack.push_back(std::move(node));
    1000                 :          0 :             todo.pop_back();
    1001 [ #  # ][ #  # ]:          0 :         }
    1002                 :            :     }
    1003 [ #  # ][ #  # ]:          0 :     assert(stack.size() == 1);
    1004 [ #  # ][ #  # ]:          0 :     assert(stack[0]->GetStaticOps() == ops);
                 [ #  # ]
    1005 [ #  # ][ #  # ]:          0 :     assert(stack[0]->ScriptSize() == scriptsize);
    1006 [ #  # ][ #  # ]:          0 :     stack[0]->DuplicateKeyCheck(KEY_COMP);
    1007                 :          0 :     return std::move(stack[0]);
    1008                 :          0 : }
    1009                 :            : 
    1010                 :            : //! The spk for this script under the given context. If it's a Taproot output also record the spend data.
    1011                 :          0 : CScript ScriptPubKey(MsCtx ctx, const CScript& script, TaprootBuilder& builder)
    1012                 :            : {
    1013 [ #  # ][ #  # ]:          0 :     if (!miniscript::IsTapscript(ctx)) return CScript() << OP_0 << WitnessV0ScriptHash(script);
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
    1014                 :            : 
    1015                 :            :     // For Taproot outputs we always use a tree with a single script and a dummy internal key.
    1016                 :          0 :     builder.Add(0, script, TAPROOT_LEAF_TAPSCRIPT);
    1017                 :          0 :     builder.Finalize(XOnlyPubKey{NUMS_PK});
    1018         [ #  # ]:          0 :     return GetScriptForDestination(builder.GetOutput());
    1019                 :          0 : }
    1020                 :            : 
    1021                 :            : //! Fill the witness with the data additional to the script satisfaction.
    1022                 :          0 : void SatisfactionToWitness(MsCtx ctx, CScriptWitness& witness, const CScript& script, TaprootBuilder& builder) {
    1023                 :            :     // For P2WSH, it's only the witness script.
    1024                 :          0 :     witness.stack.emplace_back(script.begin(), script.end());
    1025         [ #  # ]:          0 :     if (!miniscript::IsTapscript(ctx)) return;
    1026                 :            :     // For Tapscript we also need the control block.
    1027         [ #  # ]:          0 :     witness.stack.push_back(*builder.GetSpendData().scripts.begin()->second.begin());
    1028                 :          0 : }
    1029                 :            : 
    1030                 :            : /** Perform various applicable tests on a miniscript Node. */
    1031                 :          0 : void TestNode(const MsCtx script_ctx, const NodeRef& node, FuzzedDataProvider& provider)
    1032                 :            : {
    1033         [ #  # ]:          0 :     if (!node) return;
    1034                 :            : 
    1035                 :            :     // Check that it roundtrips to text representation
    1036                 :          0 :     const ParserContext parser_ctx{script_ctx};
    1037                 :          0 :     std::optional<std::string> str{node->ToString(parser_ctx)};
    1038         [ #  # ]:          0 :     assert(str);
    1039         [ #  # ]:          0 :     auto parsed = miniscript::FromString(*str, parser_ctx);
    1040         [ #  # ]:          0 :     assert(parsed);
    1041 [ #  # ][ #  # ]:          0 :     assert(*parsed == *node);
    1042                 :            : 
    1043                 :            :     // Check consistency between script size estimation and real size.
    1044         [ #  # ]:          0 :     auto script = node->ToScript(parser_ctx);
    1045 [ #  # ][ #  # ]:          0 :     assert(node->ScriptSize() == script.size());
                 [ #  # ]
    1046                 :            : 
    1047                 :            :     // Check consistency of "x" property with the script (type K is excluded, because it can end
    1048                 :            :     // with a push of a key, which could match these opcodes).
    1049 [ #  # ][ #  # ]:          0 :     if (!(node->GetType() << "K"_mst)) {
                 [ #  # ]
    1050 [ #  # ][ #  # ]:          0 :         bool ends_in_verify = !(node->GetType() << "x"_mst);
    1051 [ #  # ][ #  # ]:          0 :         assert(ends_in_verify == (script.back() == OP_CHECKSIG || script.back() == OP_CHECKMULTISIG || script.back() == OP_EQUAL || script.back() == OP_NUMEQUAL));
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
    1052                 :          0 :     }
    1053                 :            : 
    1054                 :            :     // The rest of the checks only apply when testing a valid top-level script.
    1055 [ #  # ][ #  # ]:          0 :     if (!node->IsValidTopLevel()) return;
    1056                 :            : 
    1057                 :            :     // Check roundtrip to script
    1058         [ #  # ]:          0 :     auto decoded = miniscript::FromScript(script, parser_ctx);
    1059         [ #  # ]:          0 :     assert(decoded);
    1060                 :            :     // Note we can't use *decoded == *node because the miniscript representation may differ, so we check that:
    1061                 :            :     // - The script corresponding to that decoded form matches exactly
    1062                 :            :     // - The type matches exactly
    1063 [ #  # ][ #  # ]:          0 :     assert(decoded->ToScript(parser_ctx) == script);
                 [ #  # ]
    1064 [ #  # ][ #  # ]:          0 :     assert(decoded->GetType() == node->GetType());
         [ #  # ][ #  # ]
    1065                 :            : 
    1066                 :            :     // Optionally pad the script or the witness in order to increase the sensitivity of the tests of
    1067                 :            :     // the resources limits logic.
    1068 [ #  # ][ #  # ]:          0 :     CScriptWitness witness_mal, witness_nonmal;
    1069 [ #  # ][ #  # ]:          0 :     if (provider.ConsumeBool()) {
    1070                 :            :         // Under P2WSH, optionally pad the script with OP_NOPs to max op the ops limit of the constructed script.
    1071                 :            :         // This makes the script obviously not actually miniscript-compatible anymore, but the
    1072                 :            :         // signatures constructed in this test don't commit to the script anyway, so the same
    1073                 :            :         // miniscript satisfier will work. This increases the sensitivity of the test to the ops
    1074                 :            :         // counting logic being too low, especially for simple scripts.
    1075                 :            :         // Do this optionally because we're not solely interested in cases where the number of ops is
    1076                 :            :         // maximal.
    1077                 :            :         // Do not pad more than what would cause MAX_STANDARD_P2WSH_SCRIPT_SIZE to be reached, however,
    1078                 :            :         // as that also invalidates scripts.
    1079         [ #  # ]:          0 :         const auto node_ops{node->GetOps()};
    1080 [ #  # ][ #  # ]:          0 :         if (!IsTapscript(script_ctx) && node_ops && *node_ops < MAX_OPS_PER_SCRIPT
                 [ #  # ]
    1081 [ #  # ][ #  # ]:          0 :             && node->ScriptSize() < MAX_STANDARD_P2WSH_SCRIPT_SIZE) {
    1082         [ #  # ]:          0 :             int add = std::min<int>(
    1083                 :          0 :                 MAX_OPS_PER_SCRIPT - *node_ops,
    1084         [ #  # ]:          0 :                 MAX_STANDARD_P2WSH_SCRIPT_SIZE - node->ScriptSize());
    1085 [ #  # ][ #  # ]:          0 :             for (int i = 0; i < add; ++i) script.push_back(OP_NOP);
    1086                 :          0 :         }
    1087                 :            : 
    1088                 :            :         // Under Tapscript, optionally pad the stack up to the limit minus the calculated maximum execution stack
    1089                 :            :         // size to assert a Miniscript would never add more elements to the stack during execution than anticipated.
    1090         [ #  # ]:          0 :         const auto node_exec_ss{node->GetExecStackSize()};
    1091 [ #  # ][ #  # ]:          0 :         if (miniscript::IsTapscript(script_ctx) && node_exec_ss && *node_exec_ss < MAX_STACK_SIZE) {
                 [ #  # ]
    1092                 :          0 :             unsigned add{(unsigned)MAX_STACK_SIZE - *node_exec_ss};
    1093         [ #  # ]:          0 :             witness_mal.stack.resize(add);
    1094         [ #  # ]:          0 :             witness_nonmal.stack.resize(add);
    1095         [ #  # ]:          0 :             script.reserve(add);
    1096 [ #  # ][ #  # ]:          0 :             for (unsigned i = 0; i < add; ++i) script.push_back(OP_NIP);
    1097                 :          0 :         }
    1098                 :          0 :     }
    1099                 :            : 
    1100                 :          0 :     const SatisfierContext satisfier_ctx{script_ctx};
    1101                 :            : 
    1102                 :            :     // Get the ScriptPubKey for this script, filling spend data if it's Taproot.
    1103         [ #  # ]:          0 :     TaprootBuilder builder;
    1104         [ #  # ]:          0 :     const CScript script_pubkey{ScriptPubKey(script_ctx, script, builder)};
    1105                 :            : 
    1106                 :            :     // Run malleable satisfaction algorithm.
    1107                 :          0 :     std::vector<std::vector<unsigned char>> stack_mal;
    1108         [ #  # ]:          0 :     const bool mal_success = node->Satisfy(satisfier_ctx, stack_mal, false) == miniscript::Availability::YES;
    1109                 :            : 
    1110                 :            :     // Run non-malleable satisfaction algorithm.
    1111                 :          0 :     std::vector<std::vector<unsigned char>> stack_nonmal;
    1112         [ #  # ]:          0 :     const bool nonmal_success = node->Satisfy(satisfier_ctx, stack_nonmal, true) == miniscript::Availability::YES;
    1113                 :            : 
    1114         [ #  # ]:          0 :     if (nonmal_success) {
    1115                 :            :         // Non-malleable satisfactions are bounded by the satisfaction size plus:
    1116                 :            :         // - For P2WSH spends, the witness script
    1117                 :            :         // - For Tapscript spends, both the witness script and the control block
    1118         [ #  # ]:          0 :         const size_t max_stack_size{*node->GetStackSize() + 1 + miniscript::IsTapscript(script_ctx)};
    1119         [ #  # ]:          0 :         assert(stack_nonmal.size() <= max_stack_size);
    1120                 :            :         // If a non-malleable satisfaction exists, the malleable one must also exist, and be identical to it.
    1121         [ #  # ]:          0 :         assert(mal_success);
    1122 [ #  # ][ #  # ]:          0 :         assert(stack_nonmal == stack_mal);
    1123                 :            :         // Compute witness size (excluding script push, control block, and witness count encoding).
    1124 [ #  # ][ #  # ]:          0 :         const size_t wit_size = GetSerializeSize(stack_nonmal, PROTOCOL_VERSION) - GetSizeOfCompactSize(stack_nonmal.size());
    1125 [ #  # ][ #  # ]:          0 :         assert(wit_size <= *node->GetWitnessSize());
    1126                 :            : 
    1127                 :            :         // Test non-malleable satisfaction.
    1128 [ #  # ][ #  # ]:          0 :         witness_nonmal.stack.insert(witness_nonmal.stack.end(), std::make_move_iterator(stack_nonmal.begin()), std::make_move_iterator(stack_nonmal.end()));
                 [ #  # ]
    1129         [ #  # ]:          0 :         SatisfactionToWitness(script_ctx, witness_nonmal, script, builder);
    1130                 :            :         ScriptError serror;
    1131         [ #  # ]:          0 :         bool res = VerifyScript(DUMMY_SCRIPTSIG, script_pubkey, &witness_nonmal, STANDARD_SCRIPT_VERIFY_FLAGS, CHECKER_CTX, &serror);
    1132                 :            :         // Non-malleable satisfactions are guaranteed to be valid if ValidSatisfactions().
    1133 [ #  # ][ #  # ]:          0 :         if (node->ValidSatisfactions()) assert(res);
                 [ #  # ]
    1134                 :            :         // More detailed: non-malleable satisfactions must be valid, or could fail with ops count error (if CheckOpsLimit failed),
    1135                 :            :         // or with a stack size error (if CheckStackSize check failed).
    1136 [ #  # ][ #  # ]:          0 :         assert(res ||
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
                 [ #  # ]
    1137                 :            :                (!node->CheckOpsLimit() && serror == ScriptError::SCRIPT_ERR_OP_COUNT) ||
    1138                 :            :                (!node->CheckStackSize() && serror == ScriptError::SCRIPT_ERR_STACK_SIZE));
    1139                 :          0 :     }
    1140                 :            : 
    1141 [ #  # ][ #  # ]:          0 :     if (mal_success && (!nonmal_success || witness_mal.stack != witness_nonmal.stack)) {
                 [ #  # ]
    1142                 :            :         // Test malleable satisfaction only if it's different from the non-malleable one.
    1143 [ #  # ][ #  # ]:          0 :         witness_mal.stack.insert(witness_mal.stack.end(), std::make_move_iterator(stack_mal.begin()), std::make_move_iterator(stack_mal.end()));
                 [ #  # ]
    1144         [ #  # ]:          0 :         SatisfactionToWitness(script_ctx, witness_mal, script, builder);
    1145                 :            :         ScriptError serror;
    1146         [ #  # ]:          0 :         bool res = VerifyScript(DUMMY_SCRIPTSIG, script_pubkey, &witness_mal, STANDARD_SCRIPT_VERIFY_FLAGS, CHECKER_CTX, &serror);
    1147                 :            :         // Malleable satisfactions are not guaranteed to be valid under any conditions, but they can only
    1148                 :            :         // fail due to stack or ops limits.
    1149 [ #  # ][ #  # ]:          0 :         assert(res || serror == ScriptError::SCRIPT_ERR_OP_COUNT || serror == ScriptError::SCRIPT_ERR_STACK_SIZE);
                 [ #  # ]
    1150                 :          0 :     }
    1151                 :            : 
    1152 [ #  # ][ #  # ]:          0 :     if (node->IsSane()) {
    1153                 :            :         // For sane nodes, the two algorithms behave identically.
    1154         [ #  # ]:          0 :         assert(mal_success == nonmal_success);
    1155                 :          0 :     }
    1156                 :            : 
    1157                 :            :     // Verify that if a node is policy-satisfiable, the malleable satisfaction
    1158                 :            :     // algorithm succeeds. Given that under IsSane() both satisfactions
    1159                 :            :     // are identical, this implies that for such nodes, the non-malleable
    1160                 :            :     // satisfaction will also match the expected policy.
    1161                 :          0 :     const auto is_key_satisfiable = [script_ctx](const CPubKey& pubkey) -> bool {
    1162                 :          0 :         auto sig_ptr{TEST_DATA.GetSig(script_ctx, pubkey)};
    1163         [ #  # ]:          0 :         return sig_ptr != nullptr && sig_ptr->second;
    1164                 :            :     };
    1165         [ #  # ]:          0 :     bool satisfiable = node->IsSatisfiable([&](const Node& node) -> bool {
    1166   [ #  #  #  #  :          0 :         switch (node.fragment) {
             #  #  #  # ]
    1167                 :            :         case Fragment::PK_K:
    1168                 :            :         case Fragment::PK_H:
    1169                 :          0 :             return is_key_satisfiable(node.keys[0]);
    1170                 :            :         case Fragment::MULTI:
    1171                 :            :         case Fragment::MULTI_A: {
    1172                 :          0 :             size_t sats = std::count_if(node.keys.begin(), node.keys.end(), [&](const auto& key) {
    1173                 :          0 :                 return size_t(is_key_satisfiable(key));
    1174                 :            :             });
    1175                 :          0 :             return sats >= node.k;
    1176                 :            :         }
    1177                 :            :         case Fragment::OLDER:
    1178                 :            :         case Fragment::AFTER:
    1179                 :          0 :             return node.k & 1;
    1180                 :            :         case Fragment::SHA256:
    1181                 :          0 :             return TEST_DATA.sha256_preimages.count(node.data);
    1182                 :            :         case Fragment::HASH256:
    1183                 :          0 :             return TEST_DATA.hash256_preimages.count(node.data);
    1184                 :            :         case Fragment::RIPEMD160:
    1185                 :          0 :             return TEST_DATA.ripemd160_preimages.count(node.data);
    1186                 :            :         case Fragment::HASH160:
    1187                 :          0 :             return TEST_DATA.hash160_preimages.count(node.data);
    1188                 :            :         default:
    1189                 :          0 :             assert(false);
    1190                 :            :         }
    1191                 :            :         return false;
    1192                 :          0 :     });
    1193         [ #  # ]:          0 :     assert(mal_success == satisfiable);
    1194         [ #  # ]:          0 : }
    1195                 :            : 
    1196                 :            : } // namespace
    1197                 :            : 
    1198                 :          0 : void FuzzInit()
    1199                 :            : {
    1200                 :          0 :     ECC_Start();
    1201                 :          0 :     TEST_DATA.Init();
    1202                 :          0 : }
    1203                 :            : 
    1204                 :          0 : void FuzzInitSmart()
    1205                 :            : {
    1206                 :          0 :     FuzzInit();
    1207                 :          0 :     SMARTINFO.Init();
    1208                 :          0 : }
    1209                 :            : 
    1210                 :            : /** Fuzz target that runs TestNode on nodes generated using ConsumeNodeStable. */
    1211         [ +  - ]:          4 : FUZZ_TARGET(miniscript_stable, .init = FuzzInit)
    1212                 :            : {
    1213                 :            :     // Run it under both P2WSH and Tapscript contexts.
    1214         [ #  # ]:          0 :     for (const auto script_ctx: {MsCtx::P2WSH, MsCtx::TAPSCRIPT}) {
    1215                 :          0 :         FuzzedDataProvider provider(buffer.data(), buffer.size());
    1216 [ #  # ][ #  # ]:          0 :         TestNode(script_ctx, GenNode(script_ctx, [&](Type needed_type) {
    1217                 :          0 :             return ConsumeNodeStable(script_ctx, provider, needed_type);
    1218                 :          0 :         }, ""_mst), provider);
    1219                 :            :     }
    1220                 :          0 : }
    1221                 :            : 
    1222                 :            : /** Fuzz target that runs TestNode on nodes generated using ConsumeNodeSmart. */
    1223         [ +  - ]:          4 : FUZZ_TARGET(miniscript_smart, .init = FuzzInitSmart)
    1224                 :            : {
    1225                 :            :     /** The set of types we aim to construct nodes for. Together they cover all. */
    1226                 :            :     static constexpr std::array<Type, 4> BASE_TYPES{"B"_mst, "V"_mst, "K"_mst, "W"_mst};
    1227                 :            : 
    1228                 :          0 :     FuzzedDataProvider provider(buffer.data(), buffer.size());
    1229                 :          0 :     const auto script_ctx{(MsCtx)provider.ConsumeBool()};
    1230 [ #  # ][ #  # ]:          0 :     TestNode(script_ctx, GenNode(script_ctx, [&](Type needed_type) {
    1231                 :          0 :         return ConsumeNodeSmart(script_ctx, provider, needed_type);
    1232                 :          0 :     }, PickValue(provider, BASE_TYPES), true), provider);
    1233                 :          0 : }
    1234                 :            : 
    1235                 :            : /* Fuzz tests that test parsing from a string, and roundtripping via string. */
    1236         [ +  - ]:          4 : FUZZ_TARGET(miniscript_string, .init = FuzzInit)
    1237                 :            : {
    1238         [ #  # ]:          0 :     if (buffer.empty()) return;
    1239                 :          0 :     FuzzedDataProvider provider(buffer.data(), buffer.size());
    1240                 :          0 :     auto str = provider.ConsumeBytesAsString(provider.remaining_bytes() - 1);
    1241         [ #  # ]:          0 :     const ParserContext parser_ctx{(MsCtx)provider.ConsumeBool()};
    1242         [ #  # ]:          0 :     auto parsed = miniscript::FromString(str, parser_ctx);
    1243         [ #  # ]:          0 :     if (!parsed) return;
    1244                 :            : 
    1245         [ #  # ]:          0 :     const auto str2 = parsed->ToString(parser_ctx);
    1246         [ #  # ]:          0 :     assert(str2);
    1247         [ #  # ]:          0 :     auto parsed2 = miniscript::FromString(*str2, parser_ctx);
    1248         [ #  # ]:          0 :     assert(parsed2);
    1249 [ #  # ][ #  # ]:          0 :     assert(*parsed == *parsed2);
    1250         [ #  # ]:          0 : }
    1251                 :            : 
    1252                 :            : /* Fuzz tests that test parsing from a script, and roundtripping via script. */
    1253 [ +  - ][ +  - ]:          6 : FUZZ_TARGET(miniscript_script)
    1254                 :            : {
    1255                 :          0 :     FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
    1256                 :          0 :     const std::optional<CScript> script = ConsumeDeserializable<CScript>(fuzzed_data_provider);
    1257         [ #  # ]:          0 :     if (!script) return;
    1258                 :            : 
    1259         [ #  # ]:          0 :     const ScriptParserContext script_parser_ctx{(MsCtx)fuzzed_data_provider.ConsumeBool()};
    1260         [ #  # ]:          0 :     const auto ms = miniscript::FromScript(*script, script_parser_ctx);
    1261         [ #  # ]:          0 :     if (!ms) return;
    1262                 :            : 
    1263 [ #  # ][ #  # ]:          0 :     assert(ms->ToScript(script_parser_ctx) == *script);
                 [ #  # ]
    1264         [ #  # ]:          0 : }

Generated by: LCOV version 1.14