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  #include <test/fuzz/util/descriptor.h>
  6  
  7  #include <key.h>
  8  #include <key_io.h>
  9  #include <pubkey.h>
 10  #include <span.h>
 11  #include <util/strencodings.h>
 12  
 13  #include <ranges>
 14  #include <stack>
 15  #include <vector>
 16  
 17  void MockedDescriptorConverter::Init()
 18  {
 19      // The data to use as a private key or a seed for an xprv.
 20      std::array<std::byte, 32> key_data{std::byte{1}};
 21      // Generate keys of all kinds and store them in the keys array.
 22      for (size_t i{0}; i < TOTAL_KEYS_GENERATED; i++) {
 23          key_data[31] = std::byte(i);
 24  
 25          // If this is a "raw" key, generate a normal privkey. Otherwise generate
 26          // an extended one.
 27          if (IdIsCompPubKey(i) || IdIsUnCompPubKey(i) || IdIsXOnlyPubKey(i) || IdIsConstPrivKey(i)) {
 28              CKey privkey;
 29              privkey.Set(key_data.begin(), key_data.end(), !IdIsUnCompPubKey(i));
 30              if (IdIsCompPubKey(i) || IdIsUnCompPubKey(i)) {
 31                  CPubKey pubkey{privkey.GetPubKey()};
 32                  keys_str[i] = HexStr(pubkey);
 33              } else if (IdIsXOnlyPubKey(i)) {
 34                  const XOnlyPubKey pubkey{privkey.GetPubKey()};
 35                  keys_str[i] = HexStr(pubkey);
 36              } else {
 37                  keys_str[i] = EncodeSecret(privkey);
 38              }
 39          } else {
 40              CExtKey ext_privkey;
 41              ext_privkey.SetSeed(key_data);
 42              if (IdIsXprv(i)) {
 43                  keys_str[i] = EncodeExtKey(ext_privkey);
 44              } else {
 45                  const CExtPubKey ext_pubkey{ext_privkey.Neuter()};
 46                  keys_str[i] = EncodeExtPubKey(ext_pubkey);
 47              }
 48          }
 49      }
 50  }
 51  
 52  std::optional<uint8_t> MockedDescriptorConverter::IdxFromHex(std::string_view hex_characters) const {
 53      if (hex_characters.size() != 2) return {};
 54      auto idx = ParseHex(hex_characters);
 55      if (idx.size() != 1) return {};
 56      return idx[0];
 57  }
 58  
 59  std::optional<std::string> MockedDescriptorConverter::GetDescriptor(std::string_view mocked_desc) const {
 60      // The smallest fragment would be "pk(%00)"
 61      if (mocked_desc.size() < 7) return {};
 62  
 63      // The actual descriptor string to be returned.
 64      std::string desc;
 65      desc.reserve(mocked_desc.size());
 66  
 67      // Replace all occurrences of '%' followed by two hex characters with the corresponding key.
 68      for (size_t i = 0; i < mocked_desc.size();) {
 69          if (mocked_desc[i] == '%') {
 70              if (i + 3 >= mocked_desc.size()) return {};
 71              if (const auto idx = IdxFromHex(mocked_desc.substr(i + 1, 2))) {
 72                  desc += keys_str[*idx];
 73                  i += 3;
 74              } else {
 75                  return {};
 76              }
 77          } else {
 78              desc += mocked_desc[i++];
 79          }
 80      }
 81  
 82      return desc;
 83  }
 84  
 85  bool HasDeepDerivPath(std::span<const uint8_t> buff, const int max_depth)
 86  {
 87      auto depth{0};
 88      for (const auto& ch: buff) {
 89          if (ch == ',') {
 90              // A comma is always present between two key expressions, so we use that as a delimiter.
 91              depth = 0;
 92          } else if (ch == '/') {
 93              if (++depth > max_depth) return true;
 94          }
 95      }
 96      return false;
 97  }
 98  
 99  bool HasTooManySubFrag(std::span<const uint8_t> buff, const int max_subs, const size_t max_nested_subs)
100  {
101      // We use a stack because there may be many nested sub-frags.
102      std::stack<int> counts;
103      for (const auto& ch: buff) {
104          // The fuzzer may generate an input with a ton of parentheses. Rule out pathological cases.
105          if (counts.size() > max_nested_subs) return true;
106  
107          if (ch == '(') {
108              // A new fragment was opened, create a new sub-count for it and start as one since any fragment with
109              // parentheses has at least one sub.
110              counts.push(1);
111          } else if (ch == ',' && !counts.empty()) {
112              // When encountering a comma, account for an additional sub in the last opened fragment. If it exceeds the
113              // limit, bail.
114              if (++counts.top() > max_subs) return true;
115          } else if (ch == ')' && !counts.empty()) {
116              // Fragment closed! Drop its sub count and resume to counting the number of subs for its parent.
117              counts.pop();
118          }
119      }
120      return false;
121  }
122  
123  bool HasTooManyWrappers(std::span<const uint8_t> buff, const int max_wrappers)
124  {
125      // The number of nested wrappers. Nested wrappers are always characters which follow each other so we don't have to
126      // use a stack as we do above when counting the number of sub-fragments.
127      std::optional<int> count;
128  
129      // We want to detect nested wrappers. A wrapper is a character prepended to a fragment, separated by a colon. There
130      // may be more than one wrapper, in which case the colon is not repeated. For instance `jjjjj:pk()`.  To count
131      // wrappers we iterate in reverse and use the colon to detect the end of a wrapper expression and count how many
132      // characters there are since the beginning of the expression. We stop counting when we encounter a character
133      // indicating the beginning of a new expression.
134      for (const auto ch: buff | std::views::reverse) {
135          // A colon, start counting.
136          if (ch == ':') {
137              // The colon itself is not a wrapper so we start at 0.
138              count = 0;
139          } else if (count) {
140              // If we are counting wrappers, stop when we crossed the beginning of the wrapper expression. Otherwise keep
141              // counting and bail if we reached the limit.
142              // A wrapper may only ever occur as the first sub of a descriptor/miniscript expression ('('), as the
143              // first Taproot leaf in a pair ('{') or as the nth sub in each case (',').
144              if (ch == ',' || ch == '(' || ch == '{') {
145                  count.reset();
146              } else if (++*count > max_wrappers) {
147                  return true;
148              }
149          }
150      }
151  
152      return false;
153  }
154  
155  bool HasTooLargeLeafSize(std::span<const uint8_t> buff, const uint32_t max_leaf_size)
156  {
157      uint32_t leaf_len{0};
158      for (auto c : buff) {
159          if (c == '(' || c == ')' || c == ',' || c == '{' || c == '}') {
160              // Possibly start a fresh leaf, or a fresh function name (with
161              // wrappers), or terminate a prior leaf.
162              leaf_len = 0;
163          } else {
164              // Just treat everything else as a leaf. This will also reject long
165              // function names, but this should be fine if the max_leaf_size is
166              // set large enough.
167              if (++leaf_len > max_leaf_size) {
168                  return true;
169              }
170          }
171      }
172      return false;
173  }