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 }
1267