1 // Copyright (c) 2023-present The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 5 #ifndef BITCOIN_TEST_FUZZ_UTIL_DESCRIPTOR_H
6 #define BITCOIN_TEST_FUZZ_UTIL_DESCRIPTOR_H
7 8 #include <array>
9 #include <cinttypes>
10 #include <cstddef>
11 #include <limits>
12 #include <optional>
13 #include <span>
14 #include <string>
15 #include <string_view>
16 17 /**
18 * Converts a mocked descriptor string to a valid one. Every key in a mocked descriptor is
19 * represented by 2 hex characters preceded by the '%' character. We parse the two hex characters
20 * as an index in a list of pre-generated keys. This list contains keys of the various types
21 * accepted in descriptor key expressions.
22 */
23 class MockedDescriptorConverter {
24 private:
25 //! Types are raw (un)compressed pubkeys, raw xonly pubkeys, raw privkeys (WIF), xpubs, xprvs.
26 static constexpr uint8_t KEY_TYPES_COUNT{6};
27 //! How many keys we'll generate in total.
28 static constexpr size_t TOTAL_KEYS_GENERATED{std::numeric_limits<uint8_t>::max() + 1};
29 //! 256 keys of various types.
30 std::array<std::string, TOTAL_KEYS_GENERATED> keys_str;
31 32 public:
33 // We derive the type of key to generate from the 1-byte id parsed from hex.
34 bool IdIsCompPubKey(uint8_t idx) const { return idx % KEY_TYPES_COUNT == 0; }
35 bool IdIsUnCompPubKey(uint8_t idx) const { return idx % KEY_TYPES_COUNT == 1; }
36 bool IdIsXOnlyPubKey(uint8_t idx) const { return idx % KEY_TYPES_COUNT == 2; }
37 bool IdIsConstPrivKey(uint8_t idx) const { return idx % KEY_TYPES_COUNT == 3; }
38 bool IdIsXpub(uint8_t idx) const { return idx % KEY_TYPES_COUNT == 4; }
39 bool IdIsXprv(uint8_t idx) const { return idx % KEY_TYPES_COUNT == 5; }
40 41 //! When initializing the target, populate the list of keys.
42 void Init();
43 44 //! Parse an id in the keys vectors from a 2-characters hex string.
45 std::optional<uint8_t> IdxFromHex(std::string_view hex_characters) const;
46 47 //! Get an actual descriptor string from a descriptor string whose keys were mocked.
48 std::optional<std::string> GetDescriptor(std::string_view mocked_desc) const;
49 };
50 51 //! Default maximum number of derivation indexes in a single derivation path when limiting its depth.
52 constexpr int MAX_DEPTH{2};
53 54 /**
55 * Whether the buffer, if it represents a valid descriptor, contains a derivation path deeper than
56 * a given maximum depth. Note this may also be hit for deriv paths in origins.
57 */
58 bool HasDeepDerivPath(std::span<const uint8_t> buff, int max_depth = MAX_DEPTH);
59 60 //! Default maximum number of sub-fragments.
61 constexpr int MAX_SUBS{1'000};
62 //! Maximum number of nested sub-fragments we'll allow in a descriptor.
63 constexpr size_t MAX_NESTED_SUBS{10'000};
64 65 /**
66 * Whether the buffer, if it represents a valid descriptor, contains a fragment with more
67 * sub-fragments than the given maximum.
68 */
69 bool HasTooManySubFrag(std::span<const uint8_t> buff, int max_subs = MAX_SUBS,
70 size_t max_nested_subs = MAX_NESTED_SUBS);
71 72 //! Default maximum number of wrappers per fragment.
73 constexpr int MAX_WRAPPERS{100};
74 75 /**
76 * Whether the buffer, if it represents a valid descriptor, contains a fragment with more
77 * wrappers than the given maximum.
78 */
79 bool HasTooManyWrappers(std::span<const uint8_t> buff, int max_wrappers = MAX_WRAPPERS);
80 81 /// Default maximum leaf size. This should be large enough to cover an extended
82 /// key, including paths "/", inside and outside of "[]".
83 constexpr uint32_t MAX_LEAF_SIZE{200};
84 85 /// Whether the expanded buffer (after calling GetDescriptor() in
86 /// MockedDescriptorConverter) has a leaf size too large.
87 bool HasTooLargeLeafSize(std::span<const uint8_t> buff, uint32_t max_leaf_size = MAX_LEAF_SIZE);
88 89 /// Deriving "expensive" descriptors will consume useful fuzz compute. The
90 /// compute is better spent on a smaller subset of descriptors, which still
91 /// covers all real end-user settings.
92 ///
93 /// Use this function after MockedDescriptorConverter::GetDescriptor()
94 inline bool IsTooExpensive(std::span<const uint8_t> buffer)
95 {
96 // Key derivation is expensive. Deriving deep derivation paths takes a lot of compute and we'd
97 // rather spend time elsewhere in this target, like on the actual descriptor syntax. So rule
98 // out strings which could correspond to a descriptor containing a too large derivation path.
99 if (HasDeepDerivPath(buffer)) return true;
100 101 // Some fragments can take a virtually unlimited number of sub-fragments (thresh, multi_a) but
102 // may perform quadratic operations on them. Limit the number of sub-fragments per fragment.
103 if (HasTooManySubFrag(buffer)) return true;
104 105 // The script building logic performs quadratic copies in the number of nested wrappers. Limit
106 // the number of nested wrappers per fragment.
107 if (HasTooManyWrappers(buffer)) return true;
108 109 // If any suspected leaf is too large, it will likely not represent a valid
110 // use-case. Also, possible base58 parsing in the leaf is quadratic. So
111 // limit the leaf size.
112 if (HasTooLargeLeafSize(buffer)) return true;
113 114 return false;
115 }
116 #endif // BITCOIN_TEST_FUZZ_UTIL_DESCRIPTOR_H
117