Branch data 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 [ + - ]: 173 : 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 : 3 : void Init() {
39 : 3 : unsigned char keydata[32] = {1};
40 [ + + ]: 771 : for (size_t i = 0; i < 256; i++) {
41 : 768 : keydata[31] = i;
42 : 768 : CKey privkey;
43 [ + - ]: 768 : privkey.Set(keydata, keydata + 32, true);
44 [ + - ]: 768 : const Key pubkey = privkey.GetPubKey();
45 : :
46 [ + - ]: 768 : dummy_keys.push_back(pubkey);
47 [ + - ]: 768 : dummy_key_idx_map.emplace(pubkey, i);
48 [ + - + - : 768 : dummy_keys_map.insert({pubkey.GetID(), pubkey});
+ - ]
49 : :
50 : 768 : std::vector<unsigned char> sig;
51 [ + - + - ]: 768 : privkey.Sign(uint256S(""), sig);
52 [ + - ]: 768 : sig.push_back(1); // SIGHASH_ALL
53 [ + - + - : 768 : dummy_sigs.insert({pubkey, {sig, i & 1}});
+ - ]
54 : :
55 : 768 : std::vector<unsigned char> hash;
56 [ + - ]: 768 : hash.resize(32);
57 [ + - + - : 768 : CSHA256().Write(keydata, 32).Finalize(hash.data());
+ - ]
58 [ + - ]: 768 : sha256.push_back(hash);
59 [ + + + - : 768 : if (i & 1) sha256_preimages[hash] = std::vector<unsigned char>(keydata, keydata + 32);
+ - ]
60 [ + - + - : 768 : CHash256().Write(keydata).Finalize(hash);
+ - + - ]
61 [ + - ]: 768 : hash256.push_back(hash);
62 [ + + + - : 768 : if (i & 1) hash256_preimages[hash] = std::vector<unsigned char>(keydata, keydata + 32);
+ - ]
63 [ + - ]: 768 : hash.resize(20);
64 [ + - + - : 768 : CRIPEMD160().Write(keydata, 32).Finalize(hash.data());
+ - ]
65 [ + - ]: 768 : assert(hash.size() == 20);
66 [ + - ]: 768 : ripemd160.push_back(hash);
67 [ + + + - : 768 : if (i & 1) ripemd160_preimages[hash] = std::vector<unsigned char>(keydata, keydata + 32);
+ - ]
68 [ + - + - : 768 : CHash160().Write(keydata).Finalize(hash);
+ - + - ]
69 [ + - ]: 768 : hash160.push_back(hash);
70 [ + + + - : 768 : if (i & 1) hash160_preimages[hash] = std::vector<unsigned char>(keydata, keydata + 32);
+ - ]
71 : 768 : }
72 : 3 : }
73 : 173 : } TEST_DATA;
74 : 173 :
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 : 142635 : bool KeyCompare(const Key& a, const Key& b) const {
84 : 142635 : return a < b;
85 : : }
86 : :
87 : 30728 : std::optional<std::string> ToString(const Key& key) const
88 : : {
89 : 30728 : auto it = TEST_DATA.dummy_key_idx_map.find(key);
90 [ - + ]: 30728 : if (it == TEST_DATA.dummy_key_idx_map.end()) return {};
91 : 30728 : uint8_t idx = it->second;
92 [ + - ]: 30728 : return HexStr(Span{&idx, 1});
93 : 30728 : }
94 : :
95 : 48704 : std::vector<unsigned char> ToPKBytes(const Key& key) const
96 : : {
97 [ + - ]: 48704 : return {key.begin(), key.end()};
98 : 0 : }
99 : :
100 : 3037 : std::vector<unsigned char> ToPKHBytes(const Key& key) const
101 : : {
102 : 3037 : const auto h = Hash160(key);
103 [ + - ]: 3037 : return {h.begin(), h.end()};
104 : 0 : }
105 : :
106 : : template<typename I>
107 : 31558 : std::optional<Key> FromString(I first, I last) const {
108 [ + + ]: 31558 : if (last - first != 2) return {};
109 [ + - + - ]: 31555 : auto idx = ParseHex(std::string(first, last));
110 [ + + ]: 31555 : if (idx.size() != 1) return {};
111 [ - + ]: 31543 : return TEST_DATA.dummy_keys[idx[0]];
112 : 31558 : }
113 : :
114 : : template<typename I>
115 : 21975 : std::optional<Key> FromPKBytes(I first, I last) const {
116 : 21975 : CPubKey key;
117 : 21975 : key.Set(first, last);
118 [ - + ]: 21975 : if (!key.IsValid()) return {};
119 : 21975 : return key;
120 : 21975 : }
121 : :
122 : : template<typename I>
123 : 1461 : std::optional<Key> FromPKHBytes(I first, I last) const {
124 [ + - ]: 1461 : assert(last - first == 20);
125 : 1461 : CKeyID keyid;
126 : 1461 : std::copy(first, last, keyid.begin());
127 : 1461 : const auto it = TEST_DATA.dummy_keys_map.find(keyid);
128 [ - + ]: 1461 : if (it == TEST_DATA.dummy_keys_map.end()) return {};
129 : 1461 : return it->second;
130 : 1461 : }
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 : 7965 : bool KeyCompare(const Key& a, const Key& b) const {
142 : 7965 : return a.data < b.data;
143 : : }
144 : :
145 : 415 : const std::vector<unsigned char>& ToPKBytes(const Key& key) const
146 : : {
147 [ + - ]: 415 : assert(!key.is_hash);
148 : 415 : return key.data;
149 : : }
150 : :
151 : 224 : std::vector<unsigned char> ToPKHBytes(const Key& key) const
152 : : {
153 [ + - ]: 224 : if (key.is_hash) return key.data;
154 : 0 : const auto h = Hash160(key.data);
155 [ # # ]: 0 : return {h.begin(), h.end()};
156 : 224 : }
157 : :
158 : : template<typename I>
159 : 1148 : std::optional<Key> FromPKBytes(I first, I last) const
160 : : {
161 : 1148 : Key key;
162 [ + - ]: 1148 : key.data.assign(first, last);
163 : 1148 : key.is_hash = false;
164 [ + - ]: 1148 : return key;
165 : 1148 : }
166 : :
167 : : template<typename I>
168 : 462 : std::optional<Key> FromPKHBytes(I first, I last) const
169 : : {
170 : 462 : Key key;
171 [ + - ]: 462 : key.data.assign(first, last);
172 : 462 : key.is_hash = true;
173 [ + - ]: 462 : return key;
174 : 462 : }
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 : 1468 : bool CheckAfter(uint32_t value) const { return value % 2; }
182 : 1688 : 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 : 46872 : miniscript::Availability Sign(const CPubKey& key, std::vector<unsigned char>& sig) const {
186 : 46872 : const auto it = TEST_DATA.dummy_sigs.find(key);
187 [ - + ]: 46872 : if (it == TEST_DATA.dummy_sigs.end()) return miniscript::Availability::NO;
188 [ + + ]: 46872 : if (it->second.second) {
189 : : // Key is "available"
190 : 25088 : sig = it->second.first;
191 : 25088 : return miniscript::Availability::YES;
192 : : } else {
193 : 21784 : return miniscript::Availability::NO;
194 : : }
195 : 46872 : }
196 : :
197 : : //! Lookup generalization for all the hash satisfactions below
198 : 8066 : 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 : 8066 : const auto it = map.find(hash);
202 [ + + ]: 8066 : if (it == map.end()) return miniscript::Availability::NO;
203 : 5028 : preimage = it->second;
204 : 5028 : return miniscript::Availability::YES;
205 : 8066 : }
206 : 1994 : miniscript::Availability SatSHA256(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
207 : 1994 : return LookupHash(hash, preimage, TEST_DATA.sha256_preimages);
208 : : }
209 : 1618 : miniscript::Availability SatRIPEMD160(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
210 : 1618 : return LookupHash(hash, preimage, TEST_DATA.ripemd160_preimages);
211 : : }
212 : 2150 : miniscript::Availability SatHASH256(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
213 : 2150 : return LookupHash(hash, preimage, TEST_DATA.hash256_preimages);
214 : : }
215 : 2304 : miniscript::Availability SatHASH160(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
216 : 2304 : 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 : 6587 : bool CheckECDSASignature(const std::vector<unsigned char>& sig, const std::vector<unsigned char>& vchPubKey,
226 : : const CScript& scriptCode, SigVersion sigversion) const override
227 : : {
228 : 6587 : const CPubKey key{vchPubKey};
229 : 6587 : const auto it = TEST_DATA.dummy_sigs.find(key);
230 [ - + ]: 6587 : if (it == TEST_DATA.dummy_sigs.end()) return false;
231 : 6587 : return it->second.first == sig;
232 : 6587 : }
233 : 247 : bool CheckLockTime(const CScriptNum& nLockTime) const override { return nLockTime.GetInt64() & 1; }
234 : 253 : bool CheckSequence(const CScriptNum& nSequence) const override { return nSequence.GetInt64() & 1; }
235 : 173 : } CHECKER_CTX;
236 : :
237 : : //! Context to check for duplicates when instancing a Node.
238 : : struct KeyComparator {
239 : 66495 : bool KeyCompare(const CPubKey& a, const CPubKey& b) const {
240 : 66495 : return a < b;
241 : : }
242 : : } KEY_COMP;
243 : :
244 : : // A dummy scriptsig to pass to VerifyScript (we always use Segwit v0).
245 : 173 : 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 : 111636 : template<typename... Args> NodeRef MakeNodeRef(Args&&... args) {
255 : 111636 : 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 : 11213 : NodeInfo(Fragment frag): fragment(frag), k(0) {}
272 [ + - ]: 5512 : NodeInfo(Fragment frag, CPubKey key): fragment(frag), k(0), keys({key}) {}
273 : 2015 : NodeInfo(Fragment frag, uint32_t _k): fragment(frag), k(_k) {}
274 : 4743 : NodeInfo(Fragment frag, std::vector<unsigned char> h): fragment(frag), k(0), hash(std::move(h)) {}
275 : 86264 : NodeInfo(std::vector<Type> subt, Fragment frag): fragment(frag), k(0), subtypes(std::move(subt)) {}
276 : 3780 : NodeInfo(std::vector<Type> subt, Fragment frag, uint32_t _k): fragment(frag), k(_k), subtypes(std::move(subt)) {}
277 : 4724 : 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 [ + - ]: 173 : template<typename T, typename A>
282 : 29023 : T ConsumeIndex(FuzzedDataProvider& provider, A& col) {
283 [ + - - + : 29196 : const uint8_t i = provider.ConsumeIntegral<uint8_t>();
+ - + - ]
284 : 29023 : return col[i];
285 [ + - ]: 173 : }
286 : :
287 : 26940 : CPubKey ConsumePubKey(FuzzedDataProvider& provider) {
288 : 26767 : return ConsumeIndex<CPubKey>(provider, TEST_DATA.dummy_keys);
289 [ + - + - ]: 173 : }
290 : :
291 : 430 : std::vector<unsigned char> ConsumeSha256(FuzzedDataProvider& provider) {
292 : 430 : return ConsumeIndex<std::vector<unsigned char>>(provider, TEST_DATA.sha256);
293 : : }
294 : :
295 : 701 : std::vector<unsigned char> ConsumeHash256(FuzzedDataProvider& provider) {
296 : 701 : return ConsumeIndex<std::vector<unsigned char>>(provider, TEST_DATA.hash256);
297 : : }
298 : :
299 : 510 : std::vector<unsigned char> ConsumeRipemd160(FuzzedDataProvider& provider) {
300 : 510 : return ConsumeIndex<std::vector<unsigned char>>(provider, TEST_DATA.ripemd160);
301 : : }
302 : :
303 : 615 : std::vector<unsigned char> ConsumeHash160(FuzzedDataProvider& provider) {
304 : 615 : return ConsumeIndex<std::vector<unsigned char>>(provider, TEST_DATA.hash160);
305 : : }
306 : :
307 : 984 : std::optional<uint32_t> ConsumeTimeLock(FuzzedDataProvider& provider) {
308 : 984 : const uint32_t k = provider.ConsumeIntegral<uint32_t>();
309 [ + + - + ]: 984 : if (k == 0 || k >= 0x80000000) return {};
310 : 982 : return k;
311 : 984 : }
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 : 50242 : std::optional<NodeInfo> ConsumeNodeStable(FuzzedDataProvider& provider, Type type_needed) {
327 [ + + ]: 50242 : bool allow_B = (type_needed == ""_mst) || (type_needed << "B"_mst);
328 [ + + ]: 50242 : bool allow_K = (type_needed == ""_mst) || (type_needed << "K"_mst);
329 [ + + ]: 50242 : bool allow_V = (type_needed == ""_mst) || (type_needed << "V"_mst);
330 [ + + ]: 50242 : bool allow_W = (type_needed == ""_mst) || (type_needed << "W"_mst);
331 : :
332 [ + + + + : 50242 : switch (provider.ConsumeIntegral<uint8_t>()) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + ]
333 : : case 0:
334 [ + + ]: 8574 : if (!allow_B) return {};
335 [ + - ]: 8535 : return {{Fragment::JUST_0}};
336 : : case 1:
337 [ + + ]: 2679 : if (!allow_B) return {};
338 [ + - ]: 2678 : return {{Fragment::JUST_1}};
339 : : case 2:
340 [ + + ]: 1142 : if (!allow_K) return {};
341 [ + - ]: 1141 : return {{Fragment::PK_K, ConsumePubKey(provider)}};
342 : : case 3:
343 [ + + ]: 910 : if (!allow_K) return {};
344 [ + - ]: 909 : return {{Fragment::PK_H, ConsumePubKey(provider)}};
345 : : case 4: {
346 [ + + ]: 472 : if (!allow_B) return {};
347 : 471 : const auto k = ConsumeTimeLock(provider);
348 [ + + ]: 471 : if (!k) return {};
349 [ + - ]: 470 : return {{Fragment::OLDER, *k}};
350 : : }
351 : : case 5: {
352 [ + + ]: 514 : if (!allow_B) return {};
353 : 513 : const auto k = ConsumeTimeLock(provider);
354 [ + + ]: 513 : if (!k) return {};
355 [ + - ]: 512 : return {{Fragment::AFTER, *k}};
356 : : }
357 : : case 6:
358 [ + + ]: 431 : if (!allow_B) return {};
359 [ + - + - ]: 430 : return {{Fragment::SHA256, ConsumeSha256(provider)}};
360 : : case 7:
361 [ + + ]: 702 : if (!allow_B) return {};
362 [ + - + - ]: 701 : return {{Fragment::HASH256, ConsumeHash256(provider)}};
363 : : case 8:
364 [ + + ]: 511 : if (!allow_B) return {};
365 [ + - + - ]: 510 : return {{Fragment::RIPEMD160, ConsumeRipemd160(provider)}};
366 : : case 9:
367 [ + + ]: 616 : if (!allow_B) return {};
368 [ + - + - ]: 615 : return {{Fragment::HASH160, ConsumeHash160(provider)}};
369 : : case 10: {
370 [ + + ]: 2907 : if (!allow_B) return {};
371 : 2906 : const auto k = provider.ConsumeIntegral<uint8_t>();
372 : 2906 : const auto n_keys = provider.ConsumeIntegral<uint8_t>();
373 [ + + + - : 2906 : if (n_keys > 20 || k == 0 || k > n_keys) return {};
+ + ]
374 [ + - ]: 2904 : std::vector<CPubKey> keys{n_keys};
375 [ + + + - ]: 13728 : for (auto& key: keys) key = ConsumePubKey(provider);
376 [ + - - + ]: 2904 : return {{Fragment::MULTI, k, std::move(keys)}};
377 : 2904 : }
378 : : case 11:
379 [ + + + + : 2715 : if (!(allow_B || allow_K || allow_V)) return {};
+ + ]
380 [ + - + - : 2714 : return {{{"B"_mst, type_needed, type_needed}, Fragment::ANDOR}};
+ - ]
381 : : case 12:
382 [ + + + + : 5717 : if (!(allow_B || allow_K || allow_V)) return {};
+ + ]
383 [ + - + - : 5716 : return {{{"V"_mst, type_needed}, Fragment::AND_V}};
+ - ]
384 : : case 13:
385 [ + + ]: 1050 : if (!allow_B) return {};
386 [ + - + - : 1049 : return {{{"B"_mst, "W"_mst}, Fragment::AND_B}};
+ - ]
387 : : case 15:
388 [ + + ]: 841 : if (!allow_B) return {};
389 [ + - + - : 840 : return {{{"B"_mst, "W"_mst}, Fragment::OR_B}};
+ - ]
390 : : case 16:
391 [ + + ]: 745 : if (!allow_V) return {};
392 [ + - + - : 744 : return {{{"B"_mst, "V"_mst}, Fragment::OR_C}};
+ - ]
393 : : case 17:
394 [ + + ]: 1737 : if (!allow_B) return {};
395 [ + - + - : 1736 : return {{{"B"_mst, "B"_mst}, Fragment::OR_D}};
+ - ]
396 : : case 18:
397 [ + + + + : 3128 : if (!(allow_B || allow_K || allow_V)) return {};
+ + ]
398 [ + - + - : 3127 : return {{{type_needed, type_needed}, Fragment::OR_I}};
+ - ]
399 : : case 19: {
400 [ + + ]: 1396 : if (!allow_B) return {};
401 : 1395 : auto k = provider.ConsumeIntegral<uint8_t>();
402 : 1395 : auto n_subs = provider.ConsumeIntegral<uint8_t>();
403 [ + + + + ]: 1395 : if (k == 0 || k > n_subs) return {};
404 : 1392 : std::vector<Type> subtypes;
405 [ + - ]: 1392 : subtypes.reserve(n_subs);
406 [ + - + - ]: 1392 : subtypes.emplace_back("B"_mst);
407 [ + + + - : 3983 : for (size_t i = 1; i < n_subs; ++i) subtypes.emplace_back("W"_mst);
+ - ]
408 [ + - + - ]: 1392 : return {{std::move(subtypes), Fragment::THRESH, k}};
409 : 1392 : }
410 : : case 20:
411 [ + + ]: 2672 : if (!allow_W) return {};
412 [ + - + - : 2671 : return {{{"B"_mst}, Fragment::WRAP_A}};
+ - ]
413 : : case 21:
414 [ + + ]: 276 : if (!allow_W) return {};
415 [ + - + - : 275 : return {{{"B"_mst}, Fragment::WRAP_S}};
+ - ]
416 : : case 22:
417 [ + + ]: 1481 : if (!allow_B) return {};
418 [ + - + - : 1480 : return {{{"K"_mst}, Fragment::WRAP_C}};
+ - ]
419 : : case 23:
420 [ + + ]: 181 : if (!allow_B) return {};
421 [ + - + - : 180 : return {{{"V"_mst}, Fragment::WRAP_D}};
+ - ]
422 : : case 24:
423 [ + + ]: 5928 : if (!allow_V) return {};
424 [ + - + - : 5927 : return {{{"B"_mst}, Fragment::WRAP_V}};
+ - ]
425 : : case 25:
426 [ + + ]: 1179 : if (!allow_B) return {};
427 [ + - + - : 1178 : return {{{"B"_mst}, Fragment::WRAP_J}};
+ - ]
428 : : case 26:
429 [ + + ]: 1732 : if (!allow_B) return {};
430 [ + - + - : 1731 : return {{{"B"_mst}, Fragment::WRAP_N}};
+ - ]
431 : : default:
432 : 6 : break;
433 : : }
434 : 6 : return {};
435 : 50242 : }
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 : 1 : void Init()
450 : : {
451 : : /* Construct a set of interesting type requirements to reason with (sections of BKVWzondu). */
452 : 1 : std::vector<Type> types;
453 [ + + ]: 5 : for (int base = 0; base < 4; ++base) { /* select from B,K,V,W */
454 [ + + + - : 4 : Type type_base = base == 0 ? "B"_mst : base == 1 ? "K"_mst : base == 2 ? "V"_mst : "W"_mst;
+ + + - +
+ + - +
- ]
455 [ + + ]: 16 : for (int zo = 0; zo < 3; ++zo) { /* select from z,o,(none) */
456 [ + + + - : 12 : Type type_zo = zo == 0 ? "z"_mst : zo == 1 ? "o"_mst : ""_mst;
+ + + - +
- ]
457 [ + + ]: 36 : for (int n = 0; n < 2; ++n) { /* select from (none),n */
458 [ + + + + ]: 24 : if (zo == 0 && n == 1) continue; /* z conflicts with n */
459 [ + + + + ]: 20 : if (base == 3 && n == 1) continue; /* W conflicts with n */
460 [ + + + - : 18 : Type type_n = n == 0 ? ""_mst : "n"_mst;
+ - ]
461 [ + + ]: 54 : for (int d = 0; d < 2; ++d) { /* select from (none),d */
462 [ + + + + ]: 36 : if (base == 2 && d == 1) continue; /* V conflicts with d */
463 [ + + + - : 31 : Type type_d = d == 0 ? ""_mst : "d"_mst;
+ - ]
464 [ + + ]: 93 : for (int u = 0; u < 2; ++u) { /* select from (none),u */
465 [ + + + + ]: 62 : if (base == 2 && u == 1) continue; /* V conflicts with u */
466 [ + + + - : 57 : Type type_u = u == 0 ? ""_mst : "u"_mst;
+ - ]
467 [ + - + - : 57 : Type type = type_base | type_zo | type_n | type_d | type_u;
+ - + - ]
468 [ + - ]: 57 : types.push_back(type);
469 : 57 : }
470 : 31 : }
471 : 18 : }
472 : 12 : }
473 : 4 : }
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 : 129453 : auto is_super_of = [](const recipe& a, const recipe& b) {
482 [ + + ]: 129453 : if (a.first != b.first) return false;
483 [ + + ]: 13130 : if (a.second.size() != b.second.size()) return false;
484 [ + + ]: 45710 : for (size_t i = 0; i < a.second.size(); ++i) {
485 [ + + ]: 33327 : if (!(b.second[i] << a.second[i])) return false;
486 : 32656 : }
487 : 12383 : return true;
488 : 129453 : };
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 [ + - ]: 1 : std::sort(types.begin(), types.end());
496 : :
497 : : // Iterate over all possible fragments.
498 [ + + ]: 27 : for (int fragidx = 0; fragidx <= int(Fragment::MULTI); ++fragidx) {
499 : 26 : int sub_count = 0; //!< The minimum number of child nodes this recipe has.
500 : 26 : int sub_range = 1; //!< The maximum number of child nodes for this recipe is sub_count+sub_range-1.
501 : 26 : size_t data_size = 0;
502 : 26 : size_t n_keys = 0;
503 : 26 : uint32_t k = 0;
504 : 26 : Fragment frag{fragidx};
505 : :
506 : : // Based on the fragment, determine #subs/data/k/keys to pass to ComputeType. */
507 [ + + + + : 26 : switch (frag) {
+ + + - +
+ + ]
508 : : case Fragment::PK_K:
509 : : case Fragment::PK_H:
510 : 2 : n_keys = 1;
511 : 2 : break;
512 : : case Fragment::MULTI:
513 : 1 : n_keys = 1;
514 : 1 : k = 1;
515 : 1 : break;
516 : : case Fragment::OLDER:
517 : : case Fragment::AFTER:
518 : 2 : k = 1;
519 : 2 : break;
520 : : case Fragment::SHA256:
521 : : case Fragment::HASH256:
522 : 2 : data_size = 32;
523 : 2 : break;
524 : : case Fragment::RIPEMD160:
525 : : case Fragment::HASH160:
526 : 2 : data_size = 20;
527 : 2 : break;
528 : : case Fragment::JUST_0:
529 : : case Fragment::JUST_1:
530 : 2 : 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 : 7 : sub_count = 1;
539 : 7 : 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 : 6 : sub_count = 2;
547 : 6 : break;
548 : : case Fragment::ANDOR:
549 : 1 : sub_count = 3;
550 : 1 : break;
551 : : case Fragment::THRESH:
552 : : // Thresh logic is executed for 1 and 2 arguments. Larger numbers use ad-hoc code to extend.
553 : 1 : sub_count = 1;
554 : 1 : sub_range = 2;
555 : 1 : k = 1;
556 : 1 : break;
557 : : }
558 : :
559 : : // Iterate over the number of subnodes (sub_count...sub_count+sub_range-1).
560 : 26 : std::vector<Type> subt;
561 [ + + ]: 53 : for (int subs = sub_count; subs < sub_count + sub_range; ++subs) {
562 : : // Iterate over the possible subnode types (at most 3).
563 [ + + ]: 939 : for (Type x : types) {
564 [ + + ]: 26915 : for (Type y : types) {
565 [ + + ]: 1443251 : for (Type z : types) {
566 : : // Compute the resulting type of a node with the selected fragment / subnode types.
567 : 1418395 : subt.clear();
568 [ + + + - ]: 1418395 : if (subs > 0) subt.push_back(x);
569 [ + + + - ]: 1418395 : if (subs > 1) subt.push_back(y);
570 [ + + + - ]: 1418395 : if (subs > 2) subt.push_back(z);
571 [ + - ]: 1418395 : 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 [ + - + - : 1418395 : if ((res << "K"_mst) + (res << "V"_mst) + (res << "B"_mst) + (res << "W"_mst) != 1) continue;
+ - + - +
- + - + -
+ - + + ]
574 : :
575 [ + - ]: 5728 : recipe entry{frag, subt};
576 : 135181 : 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 [ + + ]: 332224 : for (Type s : types) {
580 [ + - + - : 326496 : if ((res & "BKVWzondu"_mst) << s) {
+ - + + ]
581 [ + - ]: 12753 : auto& recipes = table[s];
582 : : // If we don't already have a super-recipe to the new one, add it.
583 [ + - + + ]: 12753 : if (!std::any_of(recipes.begin(), recipes.end(), super_of_entry)) {
584 [ + - ]: 370 : recipes.push_back(entry);
585 : 370 : }
586 : 12753 : }
587 : : }
588 : :
589 [ + + ]: 5728 : if (subs <= 2) break;
590 [ - + + ]: 5728 : }
591 [ + + ]: 26459 : if (subs <= 1) break;
592 : : }
593 [ + + ]: 923 : if (subs <= 0) break;
594 : : }
595 : 27 : }
596 : 26 : }
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 [ + - + - : 1 : 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 : 2 : while (true) {
604 : 2 : size_t set_size = useful_types.size();
605 [ + + ]: 156 : for (const auto& [type, recipes] : table) {
606 [ + - + + ]: 98 : if (useful_types.count(type) != 0) {
607 [ + + ]: 562 : for (const auto& [_, subtypes] : recipes) {
608 [ + + + - ]: 1183 : for (auto subtype : subtypes) useful_types.insert(subtype);
609 : : }
610 : 56 : }
611 : : }
612 [ + + ]: 2 : if (useful_types.size() == set_size) break;
613 : : }
614 : : // Remove all rules that construct uninteresting types.
615 [ + + ]: 50 : for (auto type_it = table.begin(); type_it != table.end();) {
616 [ + - + + ]: 49 : if (useful_types.count(type_it->first) == 0) {
617 [ + - ]: 17 : type_it = table.erase(type_it);
618 : 17 : } else {
619 : 32 : ++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 : 1 : std::set<Type> constructible_types{};
629 : 467 : 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 : 2 : while (true) {
632 : 2 : size_t set_size = constructible_types.size();
633 : : // Iterate over all types we have recipes for.
634 [ + + ]: 130 : for (const auto& [type, recipes] : table) {
635 [ + - + + ]: 64 : if (!known_constructible(type)) {
636 : : // For not (yet known to be) constructible types, iterate over their recipes.
637 [ + + ]: 40 : 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 [ + - + - : 72 : if (std::all_of(subt.begin(), subt.end(), known_constructible)) {
+ + ]
641 [ + - ]: 30 : constructible_types.insert(type);
642 : 30 : break;
643 : : }
644 : : }
645 : 34 : }
646 : : }
647 [ + + ]: 2 : if (constructible_types.size() == set_size) break;
648 : : }
649 [ + + ]: 33 : for (auto type_it = table.begin(); type_it != table.end();) {
650 : : // Remove all recipes which involve non-constructible types.
651 [ + - + - : 64 : type_it->second.erase(std::remove_if(type_it->second.begin(), type_it->second.end(),
+ - + - ]
652 : 327 : [&](const recipe& rec) {
653 : 295 : return !std::all_of(rec.second.begin(), rec.second.end(), known_constructible);
654 : 32 : }), type_it->second.end());
655 : : // Delete types entirely which have no recipes left.
656 [ + + ]: 32 : if (type_it->second.empty()) {
657 [ + - ]: 2 : type_it = table.erase(type_it);
658 : 2 : } else {
659 : 30 : ++type_it;
660 : : }
661 : : }
662 : :
663 [ + + ]: 31 : 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 [ + - + - ]: 60 : std::sort(recipes.begin(), recipes.end(),
668 : 637 : [](const recipe& a, const recipe& b) {
669 [ + + ]: 637 : if (a.second.size() < b.second.size()) return true;
670 [ + + ]: 490 : if (a.second.size() > b.second.size()) return false;
671 : 266 : return a < b;
672 : 637 : }
673 : : );
674 : : }
675 : 1 : }
676 : 173 : } 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 : 68086 : std::optional<NodeInfo> ConsumeNodeSmart(FuzzedDataProvider& provider, Type type_needed) {
689 : : /** Table entry for the requested type. */
690 : 68086 : auto recipes_it = SMARTINFO.table.find(type_needed);
691 [ + - ]: 68086 : assert(recipes_it != SMARTINFO.table.end());
692 : : /** Pick one recipe from the available ones for that type. */
693 : 72735 : 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 [ + + + + : 68086 : switch (frag) {
+ + + + +
- ]
697 : : case Fragment::PK_K:
698 : : case Fragment::PK_H:
699 [ + - ]: 3462 : return {{frag, ConsumePubKey(provider)}};
700 : : case Fragment::MULTI: {
701 : 1820 : const auto n_keys = provider.ConsumeIntegralInRange<uint8_t>(1, 20);
702 : 1820 : const auto k = provider.ConsumeIntegralInRange<uint8_t>(1, n_keys);
703 [ + - ]: 1820 : std::vector<CPubKey> keys{n_keys};
704 [ + + + - ]: 12251 : for (auto& key: keys) key = ConsumePubKey(provider);
705 [ + - - + ]: 1820 : return {{frag, k, std::move(keys)}};
706 : 1820 : }
707 : : case Fragment::OLDER:
708 : : case Fragment::AFTER:
709 [ + - ]: 1033 : return {{frag, provider.ConsumeIntegralInRange<uint32_t>(1, 0x7FFFFFF)}};
710 : : case Fragment::SHA256:
711 [ + - + - ]: 900 : return {{frag, PickValue(provider, TEST_DATA.sha256)}};
712 : : case Fragment::HASH256:
713 [ + - + - ]: 559 : return {{frag, PickValue(provider, TEST_DATA.hash256)}};
714 : : case Fragment::RIPEMD160:
715 [ + - + - ]: 394 : return {{frag, PickValue(provider, TEST_DATA.ripemd160)}};
716 : : case Fragment::HASH160:
717 [ + - + - ]: 634 : 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 [ + - + - : 113792 : return {{subt, frag}};
+ - ]
735 : : case Fragment::THRESH: {
736 : : uint32_t children;
737 [ + + ]: 2388 : if (subt.size() < 2) {
738 : 1947 : children = subt.size();
739 : 1947 : } 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 : 441 : children = provider.ConsumeIntegralInRange<uint32_t>(2, MAX_OPS_PER_SCRIPT / 2);
743 : : }
744 : 2388 : auto k = provider.ConsumeIntegralInRange<uint32_t>(1, children);
745 : 2388 : std::vector<Type> subs = subt;
746 [ + + + - ]: 13293 : while (subs.size() < children) subs.push_back(subs.back());
747 [ + - + - : 4776 : return {{std::move(subs), frag, k}};
+ - ]
748 : 2388 : }
749 : : }
750 : :
751 : 0 : assert(false);
752 : 68086 : }
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 : 2157 : NodeRef GenNode(F ConsumeNode, Type root_type, bool strict_valid = false) {
764 : : /** A stack of miniscript Nodes being built up. */
765 : 2157 : std::vector<NodeRef> stack;
766 : : /** The queue of instructions. */
767 [ + - + - : 2157 : std::vector<std::pair<Type, std::optional<NodeInfo>>> todo{{root_type, {}}};
# # + - +
- # # ]
768 : : /** Predict the number of (static) script ops. */
769 : 2157 : 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 : 2157 : uint32_t scriptsize{1};
773 : :
774 [ + + + + ]: 231918 : while (!todo.empty()) {
775 : : // The expected type we have to construct.
776 : 229964 : auto type_needed = todo.back().first;
777 [ + + + + ]: 229964 : if (!todo.back().second) {
778 : : // Fragment/children have not been decided yet. Decide them.
779 [ + - + - ]: 118328 : auto node_info = ConsumeNode(type_needed);
780 [ + + + - ]: 118328 : 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 [ + - + - : 118251 : 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 [ + + + + ]: 118251 : if (scriptsize > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
786 [ + - + + : 118248 : switch (node_info->fragment) {
+ + + - +
+ + + + +
+ + + + +
+ + + + +
+ + + - +
+ + + + +
+ + + + +
+ + + +
+ ]
787 : : case Fragment::JUST_0:
788 : : case Fragment::JUST_1:
789 : 29304 : break;
790 : : case Fragment::PK_K:
791 : 3823 : break;
792 : : case Fragment::PK_H:
793 : 1689 : ops += 3;
794 : 1689 : break;
795 : : case Fragment::OLDER:
796 : : case Fragment::AFTER:
797 : 2015 : ops += 1;
798 : 2015 : break;
799 : : case Fragment::RIPEMD160:
800 : : case Fragment::SHA256:
801 : : case Fragment::HASH160:
802 : : case Fragment::HASH256:
803 : 4743 : ops += 4;
804 : 4743 : break;
805 : : case Fragment::ANDOR:
806 : 5171 : ops += 3;
807 : 5171 : break;
808 : : case Fragment::AND_V:
809 : 13681 : break;
810 : : case Fragment::AND_B:
811 : : case Fragment::OR_B:
812 : 3685 : ops += 1;
813 : 3685 : break;
814 : : case Fragment::OR_C:
815 : 1680 : ops += 2;
816 : 1680 : break;
817 : : case Fragment::OR_D:
818 : 3154 : ops += 3;
819 : 3154 : break;
820 : : case Fragment::OR_I:
821 : 6729 : ops += 3;
822 : 6729 : break;
823 : : case Fragment::THRESH:
824 [ + - ]: 3780 : ops += node_info->subtypes.size();
825 : 3780 : break;
826 : : case Fragment::MULTI:
827 : 4721 : ops += 1;
828 : 4721 : break;
829 : : case Fragment::WRAP_A:
830 : 11929 : ops += 2;
831 : 11929 : break;
832 : : case Fragment::WRAP_S:
833 : 1031 : ops += 1;
834 : 1031 : break;
835 : : case Fragment::WRAP_C:
836 : 3035 : ops += 1;
837 : 3035 : break;
838 : : case Fragment::WRAP_D:
839 : 323 : ops += 3;
840 : 323 : 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 : 12303 : break;
845 : : case Fragment::WRAP_J:
846 : 1997 : ops += 4;
847 : 1997 : break;
848 : : case Fragment::WRAP_N:
849 : 3455 : ops += 1;
850 : 3455 : break;
851 : : }
852 [ + + + + ]: 118248 : if (ops > MAX_OPS_PER_SCRIPT) return {};
853 [ + - + - : 118162 : auto subtypes = node_info->subtypes;
+ - ]
854 : 118162 : todo.back().second = std::move(node_info);
855 [ + - + - ]: 118162 : 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 [ + + + + ]: 242928 : for (size_t i = 0; i < subtypes.size(); ++i) {
859 [ + - + - : 124766 : todo.emplace_back(*(subtypes.rbegin() + i), std::nullopt);
+ - + - +
- ]
860 : 124766 : }
861 [ + + + + ]: 118328 : } 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 [ + - ]: 111636 : NodeInfo& info = *todo.back().second;
867 : : // Gather children from the back of stack.
868 : 111636 : std::vector<NodeRef> sub;
869 [ + - + - ]: 111636 : sub.reserve(info.subtypes.size());
870 [ + + + + ]: 219060 : for (size_t i = 0; i < info.subtypes.size(); ++i) {
871 [ + - + - ]: 107424 : sub.push_back(std::move(*(stack.end() - info.subtypes.size() + i)));
872 : 107424 : }
873 [ + - + - ]: 111636 : stack.erase(stack.end() - info.subtypes.size(), stack.end());
874 : : // Construct new NodeRef.
875 : 111636 : NodeRef node;
876 [ + + + + ]: 111636 : if (info.keys.empty()) {
877 [ + - + - ]: 101408 : node = MakeNodeRef(info.fragment, std::move(sub), std::move(info.hash), info.k);
878 : 101408 : } else {
879 [ - + - + ]: 10228 : assert(sub.empty());
880 [ - + - + ]: 10228 : assert(info.hash.empty());
881 [ + - + - ]: 10228 : node = MakeNodeRef(info.fragment, std::move(info.keys), info.k);
882 : : }
883 : : // Verify acceptability.
884 [ + - + - : 111636 : if (!node || (node->GetType() & "KVWB"_mst) == ""_mst) {
+ - + - +
+ + - + -
+ - + - +
- ]
885 [ + - # # ]: 27 : assert(!strict_valid);
886 : 27 : return {};
887 : : }
888 [ + - + + : 111609 : if (!(type_needed == ""_mst)) {
+ - - + ]
889 [ - + - + ]: 105161 : assert(node->GetType() << type_needed);
890 : 105161 : }
891 [ + - + + : 111609 : if (!node->IsValid()) return {};
+ - + + ]
892 : : // Update resource predictions.
893 [ + + + - : 111607 : if (node->fragment == Fragment::WRAP_V && node->subs[0]->GetType() << "x"_mst) {
+ + + + +
- + + ]
894 : 7353 : ops += 1;
895 : 7353 : scriptsize += 1;
896 : 7353 : }
897 [ + + + + ]: 111607 : if (ops > MAX_OPS_PER_SCRIPT) return {};
898 [ + + + + ]: 111601 : if (scriptsize > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
899 : : // Move it to the stack.
900 [ + - + - ]: 111599 : stack.push_back(std::move(node));
901 : 111599 : todo.pop_back();
902 [ + + + + ]: 111636 : }
903 : : }
904 [ + - + - ]: 1954 : assert(stack.size() == 1);
905 [ + - + - : 1954 : assert(stack[0]->GetStaticOps() == ops);
+ - ]
906 [ - + - + ]: 1954 : assert(stack[0]->ScriptSize() == scriptsize);
907 [ + - + - ]: 1954 : stack[0]->DuplicateKeyCheck(KEY_COMP);
908 : 1954 : return std::move(stack[0]);
909 : 2157 : }
910 : :
911 : : /** Perform various applicable tests on a miniscript Node. */
912 : 2797 : void TestNode(const NodeRef& node, FuzzedDataProvider& provider)
913 : : {
914 [ + + ]: 2797 : if (!node) return;
915 : :
916 : : // Check that it roundtrips to text representation
917 : 2594 : std::optional<std::string> str{node->ToString(PARSER_CTX)};
918 [ + - ]: 2594 : assert(str);
919 [ + + + + ]: 2594 : auto parsed = miniscript::FromString(*str, PARSER_CTX);
920 [ + + + - ]: 2594 : assert(parsed);
921 [ + - + - ]: 1954 : assert(*parsed == *node);
922 : :
923 : : // Check consistency between script size estimation and real size.
924 [ + + ]: 1954 : auto script = node->ToScript(PARSER_CTX);
925 [ + + + - : 2594 : 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 [ + - + - : 1954 : if (!(node->GetType() << "K"_mst)) {
+ + ]
930 [ + - + - ]: 1895 : bool ends_in_verify = !(node->GetType() << "x"_mst);
931 [ + - + + : 1895 : assert(ends_in_verify == (script.back() == OP_CHECKSIG || script.back() == OP_CHECKMULTISIG || script.back() == OP_EQUAL));
+ - + + +
- + - ]
932 : 1895 : }
933 : :
934 : : // The rest of the checks only apply when testing a valid top-level script.
935 [ + - + + ]: 1954 : if (!node->IsValidTopLevel()) return;
936 : :
937 : : // Check roundtrip to script
938 [ + + ]: 1634 : auto decoded = miniscript::FromScript(script, PARSER_CTX);
939 [ + + + - ]: 2274 : 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 [ + - + - : 1634 : assert(decoded->ToScript(PARSER_CTX) == script);
+ - ]
944 [ + - + - : 1634 : assert(decoded->GetType() == node->GetType());
+ - + - ]
945 : :
946 [ + - ]: 1634 : const auto node_ops{node->GetOps()};
947 [ + - + + : 1634 : 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 [ + - ]: 59 : int add = std::min<int>(
958 [ + - ]: 59 : MAX_OPS_PER_SCRIPT - *node_ops,
959 [ + - ]: 59 : MAX_STANDARD_P2WSH_SCRIPT_SIZE - node->ScriptSize());
960 [ + + + - ]: 5948 : for (int i = 0; i < add; ++i) script.push_back(OP_NOP);
961 : 59 : }
962 : :
963 : : // Run malleable satisfaction algorithm.
964 [ + + + + : 1634 : const CScript script_pubkey = CScript() << OP_0 << WitnessV0ScriptHash(script);
+ - + + +
+ + + ]
965 [ + - ]: 2274 : CScriptWitness witness_mal;
966 [ + + ]: 2274 : const bool mal_success = node->Satisfy(SATISFIER_CTX, witness_mal.stack, false) == miniscript::Availability::YES;
967 [ + - + - : 1634 : witness_mal.stack.push_back(std::vector<unsigned char>(script.begin(), script.end()));
+ - + - ]
968 : :
969 : : // Run non-malleable satisfaction algorithm.
970 [ + + ]: 1634 : CScriptWitness witness_nonmal;
971 [ + + ]: 2274 : const bool nonmal_success = node->Satisfy(SATISFIER_CTX, witness_nonmal.stack, true) == miniscript::Availability::YES;
972 [ + - + - : 1634 : witness_nonmal.stack.push_back(std::vector<unsigned char>(script.begin(), script.end()));
+ - + - ]
973 : :
974 [ + + ]: 1634 : if (nonmal_success) {
975 : : // Non-malleable satisfactions are bounded by GetStackSize().
976 [ + - + - : 320 : 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 [ + - ]: 320 : assert(mal_success);
979 [ + - + - ]: 320 : assert(witness_nonmal.stack == witness_mal.stack);
980 : :
981 : : // Test non-malleable satisfaction.
982 : : ScriptError serror;
983 [ + - ]: 320 : 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 [ + - + + : 320 : 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 [ + + + - : 320 : assert(res ||
+ - + - #
# # # +
- ]
989 : : (!node->CheckOpsLimit() && serror == ScriptError::SCRIPT_ERR_OP_COUNT) ||
990 : : (!node->CheckStackSize() && serror == ScriptError::SCRIPT_ERR_STACK_SIZE));
991 : 320 : }
992 : :
993 [ + + + + : 1634 : 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 [ + + ]: 862 : 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 [ + + + - : 542 : assert(res || serror == ScriptError::SCRIPT_ERR_OP_COUNT || serror == ScriptError::SCRIPT_ERR_STACK_SIZE);
+ - ]
1000 : 542 : }
1001 : :
1002 [ + + + + ]: 1314 : if (node->IsSane()) {
1003 : : // For sane nodes, the two algorithms behave identically.
1004 [ + - ]: 311 : assert(mal_success == nonmal_success);
1005 : 311 : }
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 [ + - ]: 16137 : bool satisfiable = node->IsSatisfiable([](const Node& node) -> bool {
1012 [ - + + + : 14503 : switch (node.fragment) {
+ + + + ]
1013 : : case Fragment::PK_K:
1014 : : case Fragment::PK_H: {
1015 : 4519 : auto it = TEST_DATA.dummy_sigs.find(node.keys[0]);
1016 [ + - ]: 4519 : assert(it != TEST_DATA.dummy_sigs.end());
1017 : 4519 : return it->second.second;
1018 : : }
1019 : : case Fragment::MULTI: {
1020 : 4373 : size_t sats = 0;
1021 [ + + ]: 23290 : for (const auto& key : node.keys) {
1022 : 18917 : auto it = TEST_DATA.dummy_sigs.find(key);
1023 [ + - ]: 18917 : assert(it != TEST_DATA.dummy_sigs.end());
1024 : 18917 : sats += it->second.second;
1025 : : }
1026 : 4373 : return sats >= node.k;
1027 : : }
1028 : : case Fragment::OLDER:
1029 : : case Fragment::AFTER:
1030 : 1578 : return node.k & 1;
1031 : : case Fragment::SHA256:
1032 : 997 : return TEST_DATA.sha256_preimages.count(node.data);
1033 : : case Fragment::HASH256:
1034 : 1075 : return TEST_DATA.hash256_preimages.count(node.data);
1035 : : case Fragment::RIPEMD160:
1036 : 809 : return TEST_DATA.ripemd160_preimages.count(node.data);
1037 : : case Fragment::HASH160:
1038 : 1152 : return TEST_DATA.hash160_preimages.count(node.data);
1039 : : default:
1040 : 0 : assert(false);
1041 : : }
1042 : : return false;
1043 : 14503 : });
1044 [ + - ]: 1634 : assert(mal_success == satisfiable);
1045 [ - + ]: 12397 : }
1046 : :
1047 : : } // namespace
1048 : :
1049 : 3 : void FuzzInit()
1050 : : {
1051 : 3 : ECC_Start();
1052 : 3 : TEST_DATA.Init();
1053 : 3 : }
1054 : :
1055 : 1 : void FuzzInitSmart()
1056 : : {
1057 : 1 : FuzzInit();
1058 : 1 : SMARTINFO.Init();
1059 : 1 : }
1060 : :
1061 : : /** Fuzz target that runs TestNode on nodes generated using ConsumeNodeStable. */
1062 [ + - - + ]: 1459 : FUZZ_TARGET(miniscript_stable, .init = FuzzInit)
1063 : : {
1064 : 1113 : FuzzedDataProvider provider(buffer.data(), buffer.size());
1065 [ + - + - ]: 52468 : TestNode(GenNode([&](Type needed_type) {
1066 : 50242 : return ConsumeNodeStable(provider, needed_type);
1067 : 1113 : }, ""_mst), provider);
1068 : 1113 : }
1069 : :
1070 : : /** Fuzz target that runs TestNode on nodes generated using ConsumeNodeSmart. */
1071 [ + - - + ]: 1390 : 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 : 1044 : FuzzedDataProvider provider(buffer.data(), buffer.size());
1077 [ + - + - ]: 70174 : TestNode(GenNode([&](Type needed_type) {
1078 : 68086 : return ConsumeNodeSmart(provider, needed_type);
1079 : 1044 : }, PickValue(provider, BASE_TYPES), true), provider);
1080 : 1044 : }
1081 : :
1082 : : /* Fuzz tests that test parsing from a string, and roundtripping via string. */
1083 [ + - - + ]: 1066 : FUZZ_TARGET(miniscript_string, .init = FuzzInit)
1084 : : {
1085 : 720 : FuzzedDataProvider provider(buffer.data(), buffer.size());
1086 : 720 : auto str = provider.ConsumeRemainingBytesAsString();
1087 [ + - ]: 720 : auto parsed = miniscript::FromString(str, PARSER_CTX);
1088 [ + - + + ]: 720 : if (!parsed) return;
1089 : :
1090 [ + - ]: 431 : const auto str2 = parsed->ToString(PARSER_CTX);
1091 [ + - ]: 431 : assert(str2);
1092 [ + - + - ]: 431 : auto parsed2 = miniscript::FromString(*str2, PARSER_CTX);
1093 [ + - + - ]: 431 : assert(parsed2);
1094 [ + - + - ]: 431 : assert(*parsed == *parsed2);
1095 [ - + ]: 720 : }
1096 : :
1097 : : /* Fuzz tests that test parsing from a script, and roundtripping via script. */
1098 [ - + ]: 1024 : FUZZ_TARGET(miniscript_script)
1099 : : {
1100 : 678 : FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
1101 : 678 : const std::optional<CScript> script = ConsumeDeserializable<CScript>(fuzzed_data_provider);
1102 [ + + ]: 678 : if (!script) return;
1103 : :
1104 [ + - + - ]: 667 : const auto ms = miniscript::FromScript(*script, SCRIPT_PARSER_CONTEXT);
1105 [ + - + + ]: 667 : if (!ms) return;
1106 : :
1107 [ + - + - : 298 : assert(ms->ToScript(SCRIPT_PARSER_CONTEXT) == *script);
+ - + - ]
1108 [ - + ]: 678 : }
|
