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