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