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