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