1 // Copyright (c) 2018-2021 The Limenka 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 LIMENKA_SCRIPT_DESCRIPTOR_H
6 #define LIMENKA_SCRIPT_DESCRIPTOR_H
7 8 #include <outputtype.h>
9 #include <script/script.h>
10 #include <script/sign.h>
11 #include <script/signingprovider.h>
12 13 #include <optional>
14 #include <vector>
15 16 using ExtPubKeyMap = std::unordered_map<uint32_t, CExtPubKey>;
17 18 /** Cache for single descriptor's derived extended pubkeys */
19 class DescriptorCache {
20 private:
21 /** Map key expression index -> map of (key derivation index -> xpub) */
22 std::unordered_map<uint32_t, ExtPubKeyMap> m_derived_xpubs;
23 /** Map key expression index -> parent xpub */
24 ExtPubKeyMap m_parent_xpubs;
25 /** Map key expression index -> last hardened xpub */
26 ExtPubKeyMap m_last_hardened_xpubs;
27 28 public:
29 /** Cache a parent xpub
30 *
31 * @param[in] key_exp_pos Position of the key expression within the descriptor
32 * @param[in] xpub The CExtPubKey to cache
33 */
34 void CacheParentExtPubKey(uint32_t key_exp_pos, const CExtPubKey& xpub);
35 /** Retrieve a cached parent xpub
36 *
37 * @param[in] key_exp_pos Position of the key expression within the descriptor
38 * @param[out] xpub The CExtPubKey to get from cache
39 */
40 bool GetCachedParentExtPubKey(uint32_t key_exp_pos, CExtPubKey& xpub) const;
41 /** Cache an xpub derived at an index
42 *
43 * @param[in] key_exp_pos Position of the key expression within the descriptor
44 * @param[in] der_index Derivation index of the xpub
45 * @param[in] xpub The CExtPubKey to cache
46 */
47 void CacheDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index, const CExtPubKey& xpub);
48 /** Retrieve a cached xpub derived at an index
49 *
50 * @param[in] key_exp_pos Position of the key expression within the descriptor
51 * @param[in] der_index Derivation index of the xpub
52 * @param[out] xpub The CExtPubKey to get from cache
53 */
54 bool GetCachedDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index, CExtPubKey& xpub) const;
55 /** Cache a last hardened xpub
56 *
57 * @param[in] key_exp_pos Position of the key expression within the descriptor
58 * @param[in] xpub The CExtPubKey to cache
59 */
60 void CacheLastHardenedExtPubKey(uint32_t key_exp_pos, const CExtPubKey& xpub);
61 /** Retrieve a cached last hardened xpub
62 *
63 * @param[in] key_exp_pos Position of the key expression within the descriptor
64 * @param[out] xpub The CExtPubKey to get from cache
65 */
66 bool GetCachedLastHardenedExtPubKey(uint32_t key_exp_pos, CExtPubKey& xpub) const;
67 68 /** Retrieve all cached parent xpubs */
69 ExtPubKeyMap GetCachedParentExtPubKeys() const;
70 /** Retrieve all cached derived xpubs */
71 std::unordered_map<uint32_t, ExtPubKeyMap> GetCachedDerivedExtPubKeys() const;
72 /** Retrieve all cached last hardened xpubs */
73 ExtPubKeyMap GetCachedLastHardenedExtPubKeys() const;
74 75 /** Combine another DescriptorCache into this one.
76 * Returns a cache containing the items from the other cache unknown to current cache
77 */
78 DescriptorCache MergeAndDiff(const DescriptorCache& other);
79 };
80 81 /** \brief Interface for parsed descriptor objects.
82 *
83 * Descriptors are strings that describe a set of scriptPubKeys, together with
84 * all information necessary to solve them. By combining all information into
85 * one, they avoid the need to separately import keys and scripts.
86 *
87 * Descriptors may be ranged, which occurs when the public keys inside are
88 * specified in the form of HD chains (xpubs).
89 *
90 * Descriptors always represent public information - public keys and scripts -
91 * but in cases where private keys need to be conveyed along with a descriptor,
92 * they can be included inside by changing public keys to private keys (WIF
93 * format), and changing xpubs by xprvs.
94 *
95 * Reference documentation about the descriptor language can be found in
96 * doc/descriptors.md.
97 */
98 struct Descriptor {
99 virtual ~Descriptor() = default;
100 101 /** Whether the expansion of this descriptor depends on the position. */
102 virtual bool IsRange() const = 0;
103 104 /** Whether this descriptor has all information about signing ignoring lack of private keys.
105 * This is true for all descriptors except ones that use `raw` or `addr` constructions. */
106 virtual bool IsSolvable() const = 0;
107 108 /** Convert the descriptor back to a string, undoing parsing. */
109 virtual std::string ToString(bool compat_format=false) const = 0;
110 111 /** Whether this descriptor will return one scriptPubKey or multiple (aka is or is not combo) */
112 virtual bool IsSingleType() const = 0;
113 114 /** Convert the descriptor to a private string. This fails if the provided provider does not have the relevant private keys. */
115 virtual bool ToPrivateString(const SigningProvider& provider, std::string& out) const = 0;
116 117 /** Convert the descriptor to a normalized string. Normalized descriptors have the xpub at the last hardened step. This fails if the provided provider does not have the private keys to derive that xpub. */
118 virtual bool ToNormalizedString(const SigningProvider& provider, std::string& out, const DescriptorCache* cache = nullptr) const = 0;
119 120 /** Expand a descriptor at a specified position.
121 *
122 * @param[in] pos The position at which to expand the descriptor. If IsRange() is false, this is ignored.
123 * @param[in] provider The provider to query for private keys in case of hardened derivation.
124 * @param[out] output_scripts The expanded scriptPubKeys.
125 * @param[out] out Scripts and public keys necessary for solving the expanded scriptPubKeys (may be equal to `provider`).
126 * @param[out] write_cache Cache data necessary to evaluate the descriptor at this point without access to private keys.
127 */
128 virtual bool Expand(int pos, const SigningProvider& provider, std::vector<CScript>& output_scripts, FlatSigningProvider& out, DescriptorCache* write_cache = nullptr) const = 0;
129 130 /** Expand a descriptor at a specified position using cached expansion data.
131 *
132 * @param[in] pos The position at which to expand the descriptor. If IsRange() is false, this is ignored.
133 * @param[in] read_cache Cached expansion data.
134 * @param[out] output_scripts The expanded scriptPubKeys.
135 * @param[out] out Scripts and public keys necessary for solving the expanded scriptPubKeys (may be equal to `provider`).
136 */
137 virtual bool ExpandFromCache(int pos, const DescriptorCache& read_cache, std::vector<CScript>& output_scripts, FlatSigningProvider& out) const = 0;
138 139 /** Expand the private key for a descriptor at a specified position, if possible.
140 *
141 * @param[in] pos The position at which to expand the descriptor. If IsRange() is false, this is ignored.
142 * @param[in] provider The provider to query for the private keys.
143 * @param[out] out Any private keys available for the specified `pos`.
144 */
145 virtual void ExpandPrivate(int pos, const SigningProvider& provider, FlatSigningProvider& out) const = 0;
146 147 /** @return The OutputType of the scriptPubKey(s) produced by this descriptor. Or nullopt if indeterminate (multiple or none) */
148 virtual std::optional<OutputType> GetOutputType() const = 0;
149 150 /** Get the size of the scriptPubKey for this descriptor. */
151 virtual std::optional<int64_t> ScriptSize() const = 0;
152 153 /** Get the maximum size of a satisfaction for this descriptor, in weight units.
154 *
155 * @param use_max_sig Whether to assume ECDSA signatures will have a high-r.
156 */
157 virtual std::optional<int64_t> MaxSatisfactionWeight(bool use_max_sig) const = 0;
158 159 /** Get the maximum size number of stack elements for satisfying this descriptor. */
160 virtual std::optional<int64_t> MaxSatisfactionElems() const = 0;
161 162 /** Return all (extended) public keys for this descriptor, including any from subdescriptors.
163 *
164 * @param[out] pubkeys Any public keys
165 * @param[out] ext_pubs Any extended public keys
166 */
167 virtual void GetPubKeys(std::set<CPubKey>& pubkeys, std::set<CExtPubKey>& ext_pubs) const = 0;
168 };
169 170 /** Parse a `descriptor` string. Included private keys are put in `out`.
171 *
172 * If the descriptor has a checksum, it must be valid. If `require_checksum`
173 * is set, the checksum is mandatory - otherwise it is optional.
174 *
175 * If a parse error occurs, or the checksum is missing/invalid, or anything
176 * else is wrong, an empty vector is returned.
177 */
178 std::vector<std::unique_ptr<Descriptor>> Parse(const std::string& descriptor, FlatSigningProvider& out, std::string& error, bool require_checksum = false);
179 180 /** Get the checksum for a `descriptor`.
181 *
182 * - If it already has one, and it is correct, return the checksum in the input.
183 * - If it already has one that is wrong, return "".
184 * - If it does not already have one, return the checksum that would need to be added.
185 */
186 std::string GetDescriptorChecksum(const std::string& descriptor);
187 188 /**
189 * Simple wrapper to add the checksum at the end of the descriptor
190 */
191 std::string AddChecksum(const std::string& str);
192 193 /** Find a descriptor for the specified `script`, using information from `provider` where possible.
194 *
195 * A non-ranged descriptor which only generates the specified script will be returned in all
196 * circumstances.
197 *
198 * For public keys with key origin information, this information will be preserved in the returned
199 * descriptor.
200 *
201 * - If all information for solving `script` is present in `provider`, a descriptor will be returned
202 * which is IsSolvable() and encapsulates said information.
203 * - Failing that, if `script` corresponds to a known address type, an "addr()" descriptor will be
204 * returned (which is not IsSolvable()).
205 * - Failing that, a "raw()" descriptor is returned.
206 */
207 std::unique_ptr<Descriptor> InferDescriptor(const CScript& script, const SigningProvider& provider);
208 209 /** Unique identifier that may not change over time, unless explicitly marked as not backwards compatible.
210 * This is not part of BIP 380, not guaranteed to be interoperable and should not be exposed to the user.
211 */
212 uint256 DescriptorID(const Descriptor& desc);
213 214 #endif // LIMENKA_SCRIPT_DESCRIPTOR_H
215