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