Line data Source code
1 : // Copyright (c) 2018-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 <script/descriptor.h>
6 :
7 : #include <key_io.h>
8 : #include <pubkey.h>
9 : #include <script/script.h>
10 : #include <script/standard.h>
11 :
12 : #include <span.h>
13 : #include <util/bip32.h>
14 : #include <util/spanparsing.h>
15 : #include <util/strencodings.h>
16 : #include <util/system.h>
17 : #include <util/vector.h>
18 :
19 : #include <memory>
20 : #include <optional>
21 : #include <string>
22 : #include <vector>
23 :
24 : namespace {
25 :
26 : ////////////////////////////////////////////////////////////////////////////
27 : // Checksum //
28 : ////////////////////////////////////////////////////////////////////////////
29 :
30 : // This section implements a checksum algorithm for descriptors with the
31 : // following properties:
32 : // * Mistakes in a descriptor string are measured in "symbol errors". The higher
33 : // the number of symbol errors, the harder it is to detect:
34 : // * An error substituting a character from 0123456789()[],'/*abcdefgh@:$%{} for
35 : // another in that set always counts as 1 symbol error.
36 : // * Note that hex encoded keys are covered by these characters. Xprvs and
37 : // xpubs use other characters too, but already have their own checksum
38 : // mechanism.
39 : // * Function names like "multi()" use other characters, but mistakes in
40 : // these would generally result in an unparsable descriptor.
41 : // * A case error always counts as 1 symbol error.
42 : // * Any other 1 character substitution error counts as 1 or 2 symbol errors.
43 : // * Any 1 symbol error is always detected.
44 : // * Any 2 or 3 symbol error in a descriptor of up to 49154 characters is always detected.
45 : // * Any 4 symbol error in a descriptor of up to 507 characters is always detected.
46 : // * Any 5 symbol error in a descriptor of up to 77 characters is always detected.
47 : // * Is optimized to minimize the chance a 5 symbol error in a descriptor up to 387 characters is undetected
48 : // * Random errors have a chance of 1 in 2**40 of being undetected.
49 : //
50 : // These properties are achieved by expanding every group of 3 (non checksum) characters into
51 : // 4 GF(32) symbols, over which a cyclic code is defined.
52 :
53 : /*
54 : * Interprets c as 8 groups of 5 bits which are the coefficients of a degree 8 polynomial over GF(32),
55 : * multiplies that polynomial by x, computes its remainder modulo a generator, and adds the constant term val.
56 : *
57 : * This generator is G(x) = x^8 + {30}x^7 + {23}x^6 + {15}x^5 + {14}x^4 + {10}x^3 + {6}x^2 + {12}x + {9}.
58 : * It is chosen to define an cyclic error detecting code which is selected by:
59 : * - Starting from all BCH codes over GF(32) of degree 8 and below, which by construction guarantee detecting
60 : * 3 errors in windows up to 19000 symbols.
61 : * - Taking all those generators, and for degree 7 ones, extend them to degree 8 by adding all degree-1 factors.
62 : * - Selecting just the set of generators that guarantee detecting 4 errors in a window of length 512.
63 : * - Selecting one of those with best worst-case behavior for 5 errors in windows of length up to 512.
64 : *
65 : * The generator and the constants to implement it can be verified using this Sage code:
66 : * B = GF(2) # Binary field
67 : * BP.<b> = B[] # Polynomials over the binary field
68 : * F_mod = b**5 + b**3 + 1
69 : * F.<f> = GF(32, modulus=F_mod, repr='int') # GF(32) definition
70 : * FP.<x> = F[] # Polynomials over GF(32)
71 : * E_mod = x**3 + x + F.fetch_int(8)
72 : * E.<e> = F.extension(E_mod) # Extension field definition
73 : * alpha = e**2743 # Choice of an element in extension field
74 : * for p in divisors(E.order() - 1): # Verify alpha has order 32767.
75 : * assert((alpha**p == 1) == (p % 32767 == 0))
76 : * G = lcm([(alpha**i).minpoly() for i in [1056,1057,1058]] + [x + 1])
77 : * print(G) # Print out the generator
78 : * for i in [1,2,4,8,16]: # Print out {1,2,4,8,16}*(G mod x^8), packed in hex integers.
79 : * v = 0
80 : * for coef in reversed((F.fetch_int(i)*(G % x**8)).coefficients(sparse=True)):
81 : * v = v*32 + coef.integer_representation()
82 : * print("0x%x" % v)
83 : */
84 61671137 : uint64_t PolyMod(uint64_t c, int val)
85 : {
86 61671137 : uint8_t c0 = c >> 35;
87 61671137 : c = ((c & 0x7ffffffff) << 5) ^ val;
88 61671137 : if (c0 & 1) c ^= 0xf5dee51989;
89 61671137 : if (c0 & 2) c ^= 0xa9fdca3312;
90 61671137 : if (c0 & 4) c ^= 0x1bab10e32d;
91 61671137 : if (c0 & 8) c ^= 0x3706b1677a;
92 61671137 : if (c0 & 16) c ^= 0x644d626ffd;
93 61671137 : return c;
94 : }
95 :
96 255031 : std::string DescriptorChecksum(const Span<const char>& span)
97 : {
98 : /** A character set designed such that:
99 : * - The most common 'unprotected' descriptor characters (hex, keypaths) are in the first group of 32.
100 : * - Case errors cause an offset that's a multiple of 32.
101 : * - As many alphabetic characters are in the same group (while following the above restrictions).
102 : *
103 : * If p(x) gives the position of a character c in this character set, every group of 3 characters
104 : * (a,b,c) is encoded as the 4 symbols (p(a) & 31, p(b) & 31, p(c) & 31, (p(a) / 32) + 3 * (p(b) / 32) + 9 * (p(c) / 32).
105 : * This means that changes that only affect the lower 5 bits of the position, or only the higher 2 bits, will just
106 : * affect a single symbol.
107 : *
108 : * As a result, within-group-of-32 errors count as 1 symbol, as do cross-group errors that don't affect
109 : * the position within the groups.
110 : */
111 256003 : static std::string INPUT_CHARSET =
112 972 : "0123456789()[],'/*abcdefgh@:$%{}"
113 : "IJKLMNOPQRSTUVWXYZ&+-.;<=>?!^_|~"
114 : "ijklmnopqrstuvwxyzABCDEFGH`#\"\\ ";
115 :
116 : /** The character set for the checksum itself (same as bech32). */
117 255031 : static std::string CHECKSUM_CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l";
118 :
119 255031 : uint64_t c = 1;
120 255031 : int cls = 0;
121 255031 : int clscount = 0;
122 44887081 : for (auto ch : span) {
123 44632051 : auto pos = INPUT_CHARSET.find(ch);
124 44632051 : if (pos == std::string::npos) return "";
125 44632050 : c = PolyMod(c, pos & 31); // Emit a symbol for the position inside the group, for every character.
126 44632050 : cls = cls * 3 + (pos >> 5); // Accumulate the group numbers
127 44632050 : if (++clscount == 3) {
128 : // Emit an extra symbol representing the group numbers, for every 3 characters.
129 14795561 : c = PolyMod(c, cls);
130 14795561 : cls = 0;
131 14795561 : clscount = 0;
132 14795561 : }
133 : }
134 255030 : if (clscount > 0) c = PolyMod(c, cls);
135 2295270 : for (int j = 0; j < 8; ++j) c = PolyMod(c, 0); // Shift further to determine the checksum.
136 255030 : c ^= 1; // Prevent appending zeroes from not affecting the checksum.
137 :
138 255030 : std::string ret(8, ' ');
139 2295270 : for (int j = 0; j < 8; ++j) ret[j] = CHECKSUM_CHARSET[(c >> (5 * (7 - j))) & 31];
140 255030 : return ret;
141 510061 : }
142 :
143 248571 : std::string AddChecksum(const std::string& str) { return str + "#" + DescriptorChecksum(str); }
144 :
145 : ////////////////////////////////////////////////////////////////////////////
146 : // Internal representation //
147 : ////////////////////////////////////////////////////////////////////////////
148 :
149 : typedef std::vector<uint32_t> KeyPath;
150 :
151 : /** Interface for public key objects in descriptors. */
152 : struct PubkeyProvider
153 : {
154 : protected:
155 : //! Index of this key expression in the descriptor
156 : //! E.g. If this PubkeyProvider is key1 in multi(2, key1, key2, key3), then m_expr_index = 0
157 : uint32_t m_expr_index;
158 :
159 : public:
160 508879 : explicit PubkeyProvider(uint32_t exp_index) : m_expr_index(exp_index) {}
161 :
162 508879 : virtual ~PubkeyProvider() = default;
163 :
164 : /** Derive a public key.
165 : * read_cache is the cache to read keys from (if not nullptr)
166 : * write_cache is the cache to write keys to (if not nullptr)
167 : * Caches are not exclusive but this is not tested. Currently we use them exclusively
168 : */
169 : virtual bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const = 0;
170 :
171 : /** Whether this represent multiple public keys at different positions. */
172 : virtual bool IsRange() const = 0;
173 :
174 : /** Get the size of the generated public key(s) in bytes (33 or 65). */
175 : virtual size_t GetSize() const = 0;
176 :
177 : /** Get the descriptor string form. */
178 : virtual std::string ToString() const = 0;
179 :
180 : /** Get the descriptor string form including private data (if available in arg). */
181 : virtual bool ToPrivateString(const SigningProvider& arg, std::string& out) const = 0;
182 :
183 : /** Get the descriptor string form with the xpub at the last hardened derivation,
184 : * and always use h for hardened derivation.
185 : */
186 : virtual bool ToNormalizedString(const SigningProvider& arg, std::string& out, const DescriptorCache* cache = nullptr) const = 0;
187 :
188 : /** Derive a private key, if private data is available in arg. */
189 : virtual bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const = 0;
190 : };
191 :
192 : class OriginPubkeyProvider final : public PubkeyProvider
193 : {
194 : KeyOriginInfo m_origin;
195 : std::unique_ptr<PubkeyProvider> m_provider;
196 : bool m_apostrophe;
197 :
198 121917 : std::string OriginString(bool normalized=false) const
199 : {
200 121917 : return HexStr(m_origin.fingerprint) + FormatHDKeypath(m_origin.path, /*apostrophe=*/!normalized && m_apostrophe);
201 0 : }
202 :
203 : public:
204 504574 : OriginPubkeyProvider(uint32_t exp_index, KeyOriginInfo info, std::unique_ptr<PubkeyProvider> provider, bool apostrophe) : PubkeyProvider(exp_index), m_origin(std::move(info)), m_provider(std::move(provider)), m_apostrophe(apostrophe) {}
205 196207 : bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override
206 : {
207 196207 : if (!m_provider->GetPubKey(pos, arg, key, info, read_cache, write_cache)) return false;
208 196157 : std::copy(std::begin(m_origin.fingerprint), std::end(m_origin.fingerprint), info.fingerprint);
209 196157 : info.path.insert(info.path.begin(), m_origin.path.begin(), m_origin.path.end());
210 196157 : return true;
211 196207 : }
212 811 : bool IsRange() const override { return m_provider->IsRange(); }
213 70 : size_t GetSize() const override { return m_provider->GetSize(); }
214 121839 : std::string ToString() const override { return "[" + OriginString() + "]" + m_provider->ToString(); }
215 64 : bool ToPrivateString(const SigningProvider& arg, std::string& ret) const override
216 : {
217 64 : std::string sub;
218 64 : if (!m_provider->ToPrivateString(arg, sub)) return false;
219 30 : ret = "[" + OriginString() + "]" + std::move(sub);
220 30 : return true;
221 64 : }
222 48 : bool ToNormalizedString(const SigningProvider& arg, std::string& ret, const DescriptorCache* cache) const override
223 : {
224 48 : std::string sub;
225 48 : if (!m_provider->ToNormalizedString(arg, sub, cache)) return false;
226 : // If m_provider is a BIP32PubkeyProvider, we may get a string formatted like a OriginPubkeyProvider
227 : // In that case, we need to strip out the leading square bracket and fingerprint from the substring,
228 : // and append that to our own origin string.
229 48 : if (sub[0] == '[') {
230 4 : sub = sub.substr(9);
231 4 : ret = "[" + OriginString(/*normalized=*/true) + std::move(sub);
232 4 : } else {
233 44 : ret = "[" + OriginString(/*normalized=*/true) + "]" + std::move(sub);
234 : }
235 48 : return true;
236 48 : }
237 134 : bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const override
238 : {
239 134 : return m_provider->GetPrivKey(pos, arg, key);
240 : }
241 : };
242 :
243 : /** An object representing a parsed constant public key in a descriptor. */
244 : class ConstPubkeyProvider final : public PubkeyProvider
245 : {
246 : CPubKey m_pubkey;
247 :
248 : public:
249 507562 : ConstPubkeyProvider(uint32_t exp_index, const CPubKey& pubkey) : PubkeyProvider(exp_index), m_pubkey(pubkey) {}
250 133071 : bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override
251 : {
252 133071 : key = m_pubkey;
253 133071 : info.path.clear();
254 133071 : CKeyID keyid = m_pubkey.GetID();
255 133071 : std::copy(keyid.begin(), keyid.begin() + sizeof(info.fingerprint), info.fingerprint);
256 133071 : return true;
257 : }
258 17241 : bool IsRange() const override { return false; }
259 187 : size_t GetSize() const override { return m_pubkey.size(); }
260 138743 : std::string ToString() const override { return HexStr(m_pubkey); }
261 106 : bool ToPrivateString(const SigningProvider& arg, std::string& ret) const override
262 : {
263 106 : CKey key;
264 106 : if (!arg.GetKey(m_pubkey.GetID(), key)) return false;
265 68 : ret = EncodeSecret(key);
266 68 : return true;
267 106 : }
268 85 : bool ToNormalizedString(const SigningProvider& arg, std::string& ret, const DescriptorCache* cache) const override
269 : {
270 85 : ret = ToString();
271 85 : return true;
272 : }
273 9922 : bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const override
274 : {
275 9922 : return arg.GetKey(m_pubkey.GetID(), key);
276 : }
277 : };
278 :
279 : enum class DeriveType {
280 : NO,
281 : UNHARDENED,
282 : HARDENED,
283 : };
284 :
285 : /** An object representing a parsed extended public key in a descriptor. */
286 : class BIP32PubkeyProvider final : public PubkeyProvider
287 : {
288 : // Root xpub, path, and final derivation step type being used, if any
289 : CExtPubKey m_root_extkey;
290 : KeyPath m_path;
291 : DeriveType m_derive;
292 : // Whether ' or h is used in harded derivation
293 : bool m_apostrophe;
294 :
295 31038 : bool GetExtKey(const SigningProvider& arg, CExtKey& ret) const
296 : {
297 31038 : CKey key;
298 31038 : if (!arg.GetKey(m_root_extkey.pubkey.GetID(), key)) return false;
299 30241 : ret.nDepth = m_root_extkey.nDepth;
300 30241 : std::copy(m_root_extkey.vchFingerprint, m_root_extkey.vchFingerprint + sizeof(ret.vchFingerprint), ret.vchFingerprint);
301 30241 : ret.nChild = m_root_extkey.nChild;
302 30241 : ret.chaincode = m_root_extkey.chaincode;
303 30241 : ret.key = key;
304 30241 : return true;
305 31038 : }
306 :
307 : // Derives the last xprv
308 30820 : bool GetDerivedExtKey(const SigningProvider& arg, CExtKey& xprv, CExtKey& last_hardened) const
309 : {
310 30820 : if (!GetExtKey(arg, xprv)) return false;
311 102990 : for (auto entry : m_path) {
312 72937 : if (!xprv.Derive(xprv, entry)) return false;
313 72937 : if (entry >> 31) {
314 54130 : last_hardened = xprv;
315 54130 : }
316 : }
317 30053 : return true;
318 30820 : }
319 :
320 40531 : bool IsHardened() const
321 : {
322 40531 : if (m_derive == DeriveType::HARDENED) return true;
323 57847 : for (auto entry : m_path) {
324 41537 : if (entry >> 31) return true;
325 : }
326 16310 : return false;
327 40531 : }
328 :
329 : public:
330 5622 : BIP32PubkeyProvider(uint32_t exp_index, const CExtPubKey& extkey, KeyPath path, DeriveType derive, bool apostrophe) : PubkeyProvider(exp_index), m_root_extkey(extkey), m_path(std::move(path)), m_derive(derive), m_apostrophe(apostrophe) {}
331 161258 : bool IsRange() const override { return m_derive != DeriveType::NO; }
332 252 : size_t GetSize() const override { return 33; }
333 379605 : bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key_out, KeyOriginInfo& final_info_out, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override
334 : {
335 : // Info of parent of the to be derived pubkey
336 379605 : KeyOriginInfo parent_info;
337 379605 : CKeyID keyid = m_root_extkey.pubkey.GetID();
338 379605 : std::copy(keyid.begin(), keyid.begin() + sizeof(parent_info.fingerprint), parent_info.fingerprint);
339 379605 : parent_info.path = m_path;
340 :
341 : // Info of the derived key itself which is copied out upon successful completion
342 379605 : KeyOriginInfo final_info_out_tmp = parent_info;
343 379605 : if (m_derive == DeriveType::UNHARDENED) final_info_out_tmp.path.push_back((uint32_t)pos);
344 379605 : if (m_derive == DeriveType::HARDENED) final_info_out_tmp.path.push_back(((uint32_t)pos) | 0x80000000L);
345 :
346 : // Derive keys or fetch them from cache
347 379605 : CExtPubKey final_extkey = m_root_extkey;
348 379605 : CExtPubKey parent_extkey = m_root_extkey;
349 379605 : CExtPubKey last_hardened_extkey;
350 379605 : bool der = true;
351 379605 : if (read_cache) {
352 339074 : if (!read_cache->GetCachedDerivedExtPubKey(m_expr_index, pos, final_extkey)) {
353 338755 : if (m_derive == DeriveType::HARDENED) return false;
354 : // Try to get the derivation parent
355 336939 : if (!read_cache->GetCachedParentExtPubKey(m_expr_index, parent_extkey)) return false;
356 335603 : final_extkey = parent_extkey;
357 335603 : if (m_derive == DeriveType::UNHARDENED) der = parent_extkey.Derive(final_extkey, pos);
358 335603 : }
359 376453 : } else if (IsHardened()) {
360 24221 : CExtKey xprv;
361 24221 : CExtKey lh_xprv;
362 24221 : if (!GetDerivedExtKey(arg, xprv, lh_xprv)) return false;
363 24199 : parent_extkey = xprv.Neuter();
364 24199 : if (m_derive == DeriveType::UNHARDENED) der = xprv.Derive(xprv, pos);
365 24199 : if (m_derive == DeriveType::HARDENED) der = xprv.Derive(xprv, pos | 0x80000000UL);
366 24199 : final_extkey = xprv.Neuter();
367 24199 : if (lh_xprv.key.IsValid()) {
368 18197 : last_hardened_extkey = lh_xprv.Neuter();
369 18197 : }
370 24221 : } else {
371 47452 : for (auto entry : m_path) {
372 31142 : if (!parent_extkey.Derive(parent_extkey, entry)) return false;
373 : }
374 16310 : final_extkey = parent_extkey;
375 16310 : if (m_derive == DeriveType::UNHARDENED) der = parent_extkey.Derive(final_extkey, pos);
376 16310 : assert(m_derive != DeriveType::HARDENED);
377 : }
378 376431 : if (!der) return false;
379 :
380 376431 : final_info_out = final_info_out_tmp;
381 376431 : key_out = final_extkey.pubkey;
382 :
383 376431 : if (write_cache) {
384 : // Only cache parent if there is any unhardened derivation
385 3382 : if (m_derive != DeriveType::HARDENED) {
386 1594 : write_cache->CacheParentExtPubKey(m_expr_index, parent_extkey);
387 : // Cache last hardened xpub if we have it
388 1594 : if (last_hardened_extkey.pubkey.IsValid()) {
389 1291 : write_cache->CacheLastHardenedExtPubKey(m_expr_index, last_hardened_extkey);
390 1291 : }
391 3382 : } else if (final_info_out.path.size() > 0) {
392 1788 : write_cache->CacheDerivedExtPubKey(m_expr_index, pos, final_extkey);
393 1788 : }
394 3382 : }
395 :
396 376431 : return true;
397 379605 : }
398 77762 : std::string ToString(bool normalized) const
399 : {
400 77762 : const bool use_apostrophe = !normalized && m_apostrophe;
401 77762 : std::string ret = EncodeExtPubKey(m_root_extkey) + FormatHDKeypath(m_path, /*apostrophe=*/use_apostrophe);
402 77762 : if (IsRange()) {
403 77672 : ret += "/*";
404 77672 : if (m_derive == DeriveType::HARDENED) ret += use_apostrophe ? '\'' : 'h';
405 77672 : }
406 77762 : return ret;
407 77762 : }
408 77688 : std::string ToString() const override
409 : {
410 77688 : return ToString(/*normalized=*/false);
411 : }
412 218 : bool ToPrivateString(const SigningProvider& arg, std::string& out) const override
413 : {
414 218 : CExtKey key;
415 218 : if (!GetExtKey(arg, key)) return false;
416 188 : out = EncodeExtKey(key) + FormatHDKeypath(m_path, /*apostrophe=*/m_apostrophe);
417 188 : if (IsRange()) {
418 152 : out += "/*";
419 152 : if (m_derive == DeriveType::HARDENED) out += m_apostrophe ? '\'' : 'h';
420 152 : }
421 188 : return true;
422 218 : }
423 727 : bool ToNormalizedString(const SigningProvider& arg, std::string& out, const DescriptorCache* cache) const override
424 : {
425 727 : if (m_derive == DeriveType::HARDENED) {
426 4 : out = ToString(/*normalized=*/true);
427 :
428 4 : return true;
429 : }
430 : // Step backwards to find the last hardened step in the path
431 723 : int i = (int)m_path.size() - 1;
432 1420 : for (; i >= 0; --i) {
433 1350 : if (m_path.at(i) >> 31) {
434 653 : break;
435 : }
436 697 : }
437 : // Either no derivation or all unhardened derivation
438 723 : if (i == -1) {
439 70 : out = ToString(/*normalized=*/true);
440 70 : return true;
441 : }
442 : // Get the path to the last hardened stup
443 653 : KeyOriginInfo origin;
444 653 : int k = 0;
445 2634 : for (; k <= i; ++k) {
446 : // Add to the path
447 1981 : origin.path.push_back(m_path.at(k));
448 1981 : }
449 : // Build the remaining path
450 653 : KeyPath end_path;
451 1306 : for (; k < (int)m_path.size(); ++k) {
452 653 : end_path.push_back(m_path.at(k));
453 653 : }
454 : // Get the fingerprint
455 653 : CKeyID id = m_root_extkey.pubkey.GetID();
456 653 : std::copy(id.begin(), id.begin() + 4, origin.fingerprint);
457 :
458 653 : CExtPubKey xpub;
459 653 : CExtKey lh_xprv;
460 : // If we have the cache, just get the parent xpub
461 653 : if (cache != nullptr) {
462 645 : cache->GetCachedLastHardenedExtPubKey(m_expr_index, xpub);
463 645 : }
464 653 : if (!xpub.pubkey.IsValid()) {
465 : // Cache miss, or nor cache, or need privkey
466 8 : CExtKey xprv;
467 8 : if (!GetDerivedExtKey(arg, xprv, lh_xprv)) return false;
468 8 : xpub = lh_xprv.Neuter();
469 8 : }
470 653 : assert(xpub.pubkey.IsValid());
471 :
472 : // Build the string
473 653 : std::string origin_str = HexStr(origin.fingerprint) + FormatHDKeypath(origin.path);
474 653 : out = "[" + origin_str + "]" + EncodeExtPubKey(xpub) + FormatHDKeypath(end_path);
475 653 : if (IsRange()) {
476 645 : out += "/*";
477 645 : assert(m_derive == DeriveType::UNHARDENED);
478 645 : }
479 653 : return true;
480 727 : }
481 6591 : bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const override
482 : {
483 6591 : CExtKey extkey;
484 6591 : CExtKey dummy;
485 6591 : if (!GetDerivedExtKey(arg, extkey, dummy)) return false;
486 5846 : if (m_derive == DeriveType::UNHARDENED && !extkey.Derive(extkey, pos)) return false;
487 5846 : if (m_derive == DeriveType::HARDENED && !extkey.Derive(extkey, pos | 0x80000000UL)) return false;
488 5846 : key = extkey.key;
489 5846 : return true;
490 6591 : }
491 : };
492 :
493 : /** Base class for all Descriptor implementations. */
494 : class DescriptorImpl : public Descriptor
495 : {
496 : //! Public key arguments for this descriptor (size 1 for PK, PKH; any size for Multisig).
497 : const std::vector<std::unique_ptr<PubkeyProvider>> m_pubkey_args;
498 : //! The string name of the descriptor function.
499 : const std::string m_name;
500 :
501 : protected:
502 : //! The sub-descriptor arguments (empty for everything but SH and WSH).
503 : //! In doc/descriptors.m this is referred to as SCRIPT expressions sh(SCRIPT)
504 : //! and wsh(SCRIPT), and distinct from KEY expressions and ADDR expressions.
505 : //! Subdescriptors can only ever generate a single script.
506 : const std::vector<std::unique_ptr<DescriptorImpl>> m_subdescriptor_args;
507 :
508 : //! Return a serialization of anything except pubkey and script arguments, to be prepended to those.
509 251480 : virtual std::string ToStringExtra() const { return ""; }
510 :
511 : /** A helper function to construct the scripts for this descriptor.
512 : *
513 : * This function is invoked once by ExpandHelper.
514 : *
515 : * @param pubkeys The evaluations of the m_pubkey_args field.
516 : * @param scripts The evaluations of m_subdescriptor_args (one for each m_subdescriptor_args element).
517 : * @param out A FlatSigningProvider to put scripts or public keys in that are necessary to the solver.
518 : * The origin info of the provided pubkeys is automatically added.
519 : * @return A vector with scriptPubKeys for this descriptor.
520 : */
521 : virtual std::vector<CScript> MakeScripts(const std::vector<CPubKey>& pubkeys, Span<const CScript> scripts, FlatSigningProvider& out) const = 0;
522 :
523 : public:
524 292570 : DescriptorImpl(std::vector<std::unique_ptr<PubkeyProvider>> pubkeys, const std::string& name) : m_pubkey_args(std::move(pubkeys)), m_name(name), m_subdescriptor_args() {}
525 36722 : DescriptorImpl(std::vector<std::unique_ptr<PubkeyProvider>> pubkeys, std::unique_ptr<DescriptorImpl> script, const std::string& name) : m_pubkey_args(std::move(pubkeys)), m_name(name), m_subdescriptor_args(Vector(std::move(script))) {}
526 :
527 : enum class StringType
528 : {
529 : PUBLIC,
530 : PRIVATE,
531 : NORMALIZED,
532 : };
533 :
534 456 : bool IsSolvable() const override
535 : {
536 582 : for (const auto& arg : m_subdescriptor_args) {
537 126 : if (!arg->IsSolvable()) return false;
538 : }
539 456 : return true;
540 456 : }
541 :
542 103961 : bool IsRange() const final
543 : {
544 121348 : for (const auto& pubkey : m_pubkey_args) {
545 99896 : if (pubkey->IsRange()) return true;
546 : }
547 21700 : for (const auto& arg : m_subdescriptor_args) {
548 1120 : if (arg->IsRange()) return true;
549 : }
550 20580 : return false;
551 103961 : }
552 :
553 285575 : virtual bool ToStringSubScriptHelper(const SigningProvider* arg, std::string& ret, const StringType type, const DescriptorCache* cache = nullptr) const
554 : {
555 285575 : size_t pos = 0;
556 322629 : for (const auto& scriptarg : m_subdescriptor_args) {
557 37072 : if (pos++) ret += ",";
558 37072 : std::string tmp;
559 37072 : if (!scriptarg->ToStringHelper(arg, tmp, type, cache)) return false;
560 37054 : ret += tmp;
561 37072 : }
562 285557 : return true;
563 285575 : }
564 :
565 285643 : bool ToStringHelper(const SigningProvider* arg, std::string& out, const StringType type, const DescriptorCache* cache = nullptr) const
566 : {
567 285643 : std::string extra = ToStringExtra();
568 285643 : size_t pos = extra.size() > 0 ? 1 : 0;
569 285643 : std::string ret = m_name + "(" + extra;
570 503057 : for (const auto& pubkey : m_pubkey_args) {
571 217482 : if (pos++) ret += ",";
572 217482 : std::string tmp;
573 217482 : switch (type) {
574 : case StringType::NORMALIZED:
575 812 : if (!pubkey->ToNormalizedString(*arg, tmp, cache)) return false;
576 812 : break;
577 : case StringType::PRIVATE:
578 324 : if (!pubkey->ToPrivateString(*arg, tmp)) return false;
579 256 : break;
580 : case StringType::PUBLIC:
581 216346 : tmp = pubkey->ToString();
582 216346 : break;
583 : }
584 217414 : ret += tmp;
585 217482 : }
586 285575 : std::string subscript;
587 285575 : if (!ToStringSubScriptHelper(arg, subscript, type, cache)) return false;
588 285557 : if (pos && subscript.size()) ret += ',';
589 285557 : out = std::move(ret) + std::move(subscript) + ")";
590 285557 : return true;
591 285643 : }
592 :
593 247515 : std::string ToString() const final
594 : {
595 247515 : std::string ret;
596 247515 : ToStringHelper(nullptr, ret, StringType::PUBLIC);
597 247515 : return AddChecksum(ret);
598 247515 : }
599 :
600 298 : bool ToPrivateString(const SigningProvider& arg, std::string& out) const override
601 : {
602 298 : bool ret = ToStringHelper(&arg, out, StringType::PRIVATE);
603 298 : out = AddChecksum(out);
604 298 : return ret;
605 : }
606 :
607 758 : bool ToNormalizedString(const SigningProvider& arg, std::string& out, const DescriptorCache* cache) const override final
608 : {
609 758 : bool ret = ToStringHelper(&arg, out, StringType::NORMALIZED, cache);
610 758 : out = AddChecksum(out);
611 758 : return ret;
612 : }
613 :
614 439491 : bool ExpandHelper(int pos, const SigningProvider& arg, const DescriptorCache* read_cache, std::vector<CScript>& output_scripts, FlatSigningProvider& out, DescriptorCache* write_cache) const
615 : {
616 439491 : std::vector<std::pair<CPubKey, KeyOriginInfo>> entries;
617 439491 : entries.reserve(m_pubkey_args.size());
618 :
619 : // Construct temporary data in `entries`, `subscripts`, and `subprovider` to avoid producing output in case of failure.
620 948993 : for (const auto& p : m_pubkey_args) {
621 512676 : entries.emplace_back();
622 512676 : if (!p->GetPubKey(pos, arg, entries.back().first, entries.back().second, read_cache, write_cache)) return false;
623 : }
624 436317 : std::vector<CScript> subscripts;
625 436317 : FlatSigningProvider subprovider;
626 466765 : for (const auto& subarg : m_subdescriptor_args) {
627 30700 : std::vector<CScript> outscripts;
628 30700 : if (!subarg->ExpandHelper(pos, arg, read_cache, outscripts, subprovider, write_cache)) return false;
629 30448 : assert(outscripts.size() == 1);
630 30448 : subscripts.emplace_back(std::move(outscripts[0]));
631 30700 : }
632 436065 : out.Merge(std::move(subprovider));
633 :
634 436065 : std::vector<CPubKey> pubkeys;
635 436065 : pubkeys.reserve(entries.size());
636 945567 : for (auto& entry : entries) {
637 509502 : pubkeys.push_back(entry.first);
638 509502 : out.origins.emplace(entry.first.GetID(), std::make_pair<CPubKey, KeyOriginInfo>(CPubKey(entry.first), std::move(entry.second)));
639 : }
640 :
641 436065 : output_scripts = MakeScripts(pubkeys, Span{subscripts}, out);
642 436065 : return true;
643 439491 : }
644 :
645 175939 : bool Expand(int pos, const SigningProvider& provider, std::vector<CScript>& output_scripts, FlatSigningProvider& out, DescriptorCache* write_cache = nullptr) const final
646 : {
647 175939 : return ExpandHelper(pos, provider, nullptr, output_scripts, out, write_cache);
648 : }
649 :
650 232852 : bool ExpandFromCache(int pos, const DescriptorCache& read_cache, std::vector<CScript>& output_scripts, FlatSigningProvider& out) const final
651 : {
652 232852 : return ExpandHelper(pos, DUMMY_SIGNING_PROVIDER, &read_cache, output_scripts, out, nullptr);
653 : }
654 :
655 16464 : void ExpandPrivate(int pos, const SigningProvider& provider, FlatSigningProvider& out) const final
656 : {
657 32977 : for (const auto& p : m_pubkey_args) {
658 16513 : CKey key;
659 16513 : if (!p->GetPrivKey(pos, provider, key)) continue;
660 15679 : out.keys.emplace(key.GetPubKey().GetID(), key);
661 16513 : }
662 16599 : for (const auto& arg : m_subdescriptor_args) {
663 135 : arg->ExpandPrivate(pos, provider, out);
664 : }
665 16464 : }
666 10 : std::optional<OutputType> GetOutputType() const override { return std::nullopt; }
667 : };
668 :
669 : /** A parsed addr(A) descriptor. */
670 : class AddressDescriptor final : public DescriptorImpl
671 : {
672 : const CTxDestination m_destination;
673 : protected:
674 32846 : std::string ToStringExtra() const override { return EncodeDestination(m_destination); }
675 1320 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, Span<const CScript>, FlatSigningProvider&) const override { return Vector(GetScriptForDestination(m_destination)); }
676 : public:
677 67970 : AddressDescriptor(CTxDestination destination) : DescriptorImpl({}, "addr"), m_destination(std::move(destination)) {}
678 0 : bool IsSolvable() const final { return false; }
679 :
680 23 : std::optional<OutputType> GetOutputType() const override
681 : {
682 23 : switch (m_destination.index()) {
683 : case 1 /* PKHash */:
684 23 : case 2 /* ScriptHash */: return OutputType::LEGACY;
685 0 : case 0 /* CNoDestination */:
686 0 : default: return std::nullopt;
687 : }
688 23 : }
689 0 : bool IsSingleType() const final { return true; }
690 4 : bool ToPrivateString(const SigningProvider& arg, std::string& out) const final { return false; }
691 : };
692 :
693 : /** A parsed raw(H) descriptor. */
694 : class RawDescriptor final : public DescriptorImpl
695 : {
696 : const CScript m_script;
697 : protected:
698 441 : std::string ToStringExtra() const override { return HexStr(m_script); }
699 2874 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, Span<const CScript>, FlatSigningProvider&) const override { return Vector(m_script); }
700 : public:
701 6366 : RawDescriptor(CScript script) : DescriptorImpl({}, "raw"), m_script(std::move(script)) {}
702 0 : bool IsSolvable() const final { return false; }
703 :
704 2 : std::optional<OutputType> GetOutputType() const override
705 : {
706 2 : CTxDestination dest;
707 2 : ExtractDestination(m_script, dest);
708 2 : switch (dest.index()) {
709 : case 1 /* PKHash */:
710 2 : case 2 /* ScriptHash */: return OutputType::LEGACY;
711 0 : case 0 /* CNoDestination */:
712 0 : default: return std::nullopt;
713 : }
714 2 : }
715 0 : bool IsSingleType() const final { return true; }
716 0 : bool ToPrivateString(const SigningProvider& arg, std::string& out) const final { return false; }
717 : };
718 :
719 : /** A parsed pk(P) descriptor. */
720 : class PKDescriptor final : public DescriptorImpl
721 : {
722 : protected:
723 665 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider&) const override { return Vector(GetScriptForRawPubKey(keys[0])); }
724 : public:
725 74058 : PKDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), "pk") {}
726 8 : std::optional<OutputType> GetOutputType() const override { return OutputType::LEGACY; }
727 2 : bool IsSingleType() const final { return true; }
728 : };
729 :
730 : /** A parsed pkh(P) descriptor. */
731 : class PKHDescriptor final : public DescriptorImpl
732 : {
733 : protected:
734 333101 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider& out) const override
735 : {
736 333101 : CKeyID id = keys[0].GetID();
737 333101 : out.pubkeys.emplace(id, keys[0]);
738 333101 : return Vector(GetScriptForDestination(PKHash(id)));
739 0 : }
740 : public:
741 434486 : PKHDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), "pkh") {}
742 8140 : std::optional<OutputType> GetOutputType() const override { return OutputType::LEGACY; }
743 38573 : bool IsSingleType() const final { return true; }
744 : };
745 :
746 : /** A parsed multi(...) or sortedmulti(...) descriptor */
747 : class MultisigDescriptor final : public DescriptorImpl
748 : {
749 : const int m_threshold;
750 : const bool m_sorted;
751 : protected:
752 876 : std::string ToStringExtra() const override { return strprintf("%i", m_threshold); }
753 30091 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider&) const override {
754 30091 : if (m_sorted) {
755 1578 : std::vector<CPubKey> sorted_keys(keys);
756 1578 : std::sort(sorted_keys.begin(), sorted_keys.end());
757 1578 : return Vector(GetScriptForMultisig(m_threshold, sorted_keys));
758 1578 : }
759 28513 : return Vector(GetScriptForMultisig(m_threshold, keys));
760 30091 : }
761 : public:
762 950 : MultisigDescriptor(int threshold, std::vector<std::unique_ptr<PubkeyProvider>> providers, bool sorted = false) : DescriptorImpl(std::move(providers), sorted ? "sortedmulti" : "multi"), m_threshold(threshold), m_sorted(sorted) {}
763 0 : bool IsSingleType() const final { return true; }
764 : };
765 :
766 : /** A parsed sh(...) descriptor. */
767 : class SHDescriptor final : public DescriptorImpl
768 : {
769 : protected:
770 30448 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, Span<const CScript> scripts, FlatSigningProvider& out) const override
771 : {
772 30448 : auto ret = Vector(GetScriptForDestination(ScriptHash(scripts[0])));
773 30448 : if (ret.size()) out.scripts.emplace(CScriptID(scripts[0]), scripts[0]);
774 30448 : return ret;
775 30448 : }
776 : public:
777 73444 : SHDescriptor(std::unique_ptr<DescriptorImpl> desc) : DescriptorImpl({}, std::move(desc), "sh") {}
778 :
779 136 : std::optional<OutputType> GetOutputType() const override
780 : {
781 136 : assert(m_subdescriptor_args.size() == 1);
782 136 : return OutputType::LEGACY;
783 : }
784 488 : bool IsSingleType() const final { return true; }
785 : };
786 :
787 : /** A parsed combo(P) descriptor. */
788 : class ComboDescriptor final : public DescriptorImpl
789 : {
790 : protected:
791 37566 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript> scripts, FlatSigningProvider& out) const override
792 : {
793 37566 : std::vector<CScript> ret;
794 37566 : CKeyID id = keys[0].GetID();
795 37566 : out.pubkeys.emplace(id, keys[0]);
796 37566 : ret.emplace_back(GetScriptForRawPubKey(keys[0])); // P2PK
797 37566 : if (keys[0].IsCompressed()) {
798 37542 : CScript p2pkh = GetScriptForDestination(PKHash(id));
799 37542 : out.scripts.emplace(CScriptID(p2pkh), p2pkh);
800 37542 : ret.emplace_back(p2pkh);
801 37542 : ret.emplace_back(GetScriptForDestination(ScriptHash(p2pkh))); // P2SH-P2PKH
802 37542 : }
803 37566 : return ret;
804 37566 : }
805 :
806 : public:
807 1310 : ComboDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), "combo") {}
808 282 : std::optional<OutputType> GetOutputType() const override { return OutputType::LEGACY; }
809 2 : bool IsSingleType() const final { return false; }
810 : };
811 :
812 : ////////////////////////////////////////////////////////////////////////////
813 : // Parser //
814 : ////////////////////////////////////////////////////////////////////////////
815 :
816 : enum class ParseScriptContext {
817 : TOP, //!< Top-level context (script goes directly in scriptPubKey)
818 : P2SH, //!< Inside sh() (script becomes P2SH redeemScript)
819 : };
820 :
821 : /**
822 : * Parse a key path, being passed a split list of elements (the first element is ignored).
823 : *
824 : * @param[in] split BIP32 path string, using either ' or h for hardened derivation
825 : * @param[out] out the key path
826 : * @param[out] apostrophe only updated if hardened derivation is found
827 : * @param[out] error parsing error message
828 : * @returns false if parsing failed
829 : **/
830 3049 : [[nodiscard]] bool ParseKeyPath(const std::vector<Span<const char>>& split, KeyPath& out, bool& apostrophe, std::string& error)
831 : {
832 14281 : for (size_t i = 1; i < split.size(); ++i) {
833 11236 : Span<const char> elem = split[i];
834 11236 : bool hardened = false;
835 11236 : if (elem.size() > 0) {
836 11236 : const char last = elem[elem.size() - 1];
837 11236 : if (last == '\'' || last == 'h') {
838 8352 : elem = elem.first(elem.size() - 1);
839 8352 : hardened = true;
840 8352 : apostrophe = last == '\'';
841 8352 : }
842 11236 : }
843 : uint32_t p;
844 11236 : if (!ParseUInt32(std::string(elem.begin(), elem.end()), &p)) {
845 2 : error = strprintf("Key path value '%s' is not a valid uint32", std::string(elem.begin(), elem.end()));
846 2 : return false;
847 11234 : } else if (p > 0x7FFFFFFFUL) {
848 2 : error = strprintf("Key path value %u is out of range", p);
849 2 : return false;
850 : }
851 11232 : out.push_back(p | (((uint32_t)hardened) << 31));
852 11232 : }
853 3045 : return true;
854 3049 : }
855 :
856 : /** Parse a public key that excludes origin information. */
857 3716 : std::unique_ptr<PubkeyProvider> ParsePubkeyInner(uint32_t key_exp_index, const Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, bool& apostrophe, std::string& error)
858 : {
859 : using namespace spanparsing;
860 :
861 3716 : bool permit_uncompressed = ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH;
862 3716 : auto split = Split(sp, '/');
863 3716 : std::string str(split[0].begin(), split[0].end());
864 3716 : if (str.size() == 0) {
865 0 : error = "No key provided";
866 0 : return nullptr;
867 : }
868 3716 : if (split.size() == 1) {
869 921 : if (IsHex(str)) {
870 563 : std::vector<unsigned char> data = ParseHex(str);
871 563 : CPubKey pubkey(data);
872 563 : if (pubkey.IsFullyValid()) {
873 563 : if (permit_uncompressed || pubkey.IsCompressed()) {
874 563 : return std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey);
875 : } else {
876 0 : error = "Uncompressed keys are not allowed";
877 0 : return nullptr;
878 : }
879 : }
880 0 : error = strprintf("Pubkey '%s' is invalid", str);
881 0 : return nullptr;
882 563 : }
883 358 : CKey key = DecodeSecret(str);
884 358 : if (key.IsValid()) {
885 333 : if (permit_uncompressed || key.IsCompressed()) {
886 333 : CPubKey pubkey = key.GetPubKey();
887 333 : out.keys.emplace(pubkey.GetID(), key);
888 333 : return std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey);
889 : } else {
890 0 : error = "Uncompressed keys are not allowed";
891 0 : return nullptr;
892 : }
893 : }
894 358 : }
895 2820 : CExtKey extkey = DecodeExtKey(str);
896 2820 : CExtPubKey extpubkey = DecodeExtPubKey(str);
897 2820 : if (!extkey.key.IsValid() && !extpubkey.pubkey.IsValid()) {
898 5 : error = strprintf("key '%s' is not valid", str);
899 5 : return nullptr;
900 : }
901 2815 : KeyPath path;
902 2815 : DeriveType type = DeriveType::NO;
903 2815 : if (split.back() == Span{"*"}.first(1)) {
904 2636 : split.pop_back();
905 2636 : type = DeriveType::UNHARDENED;
906 2815 : } else if (split.back() == Span{"*'"}.first(2) || split.back() == Span{"*h"}.first(2)) {
907 63 : apostrophe = split.back() == Span{"*'"}.first(2);
908 63 : split.pop_back();
909 63 : type = DeriveType::HARDENED;
910 63 : }
911 2815 : if (!ParseKeyPath(split, path, apostrophe, error)) return nullptr;
912 2811 : if (extkey.key.IsValid()) {
913 258 : extpubkey = extkey.Neuter();
914 258 : out.keys.emplace(extpubkey.pubkey.GetID(), extkey.key);
915 258 : }
916 2811 : return std::make_unique<BIP32PubkeyProvider>(key_exp_index, extpubkey, std::move(path), type, apostrophe);
917 3716 : }
918 :
919 : /** Parse a public key including origin information (if enabled). */
920 3722 : std::unique_ptr<PubkeyProvider> ParsePubkey(uint32_t key_exp_index, const Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error)
921 : {
922 : using namespace spanparsing;
923 :
924 3722 : auto origin_split = Split(sp, ']');
925 3722 : if (origin_split.size() > 2) {
926 2 : error = "Multiple ']' characters found for a single pubkey";
927 2 : return nullptr;
928 : }
929 3720 : bool apostrophe = false;
930 3720 : if (origin_split.size() == 1) return ParsePubkeyInner(key_exp_index, origin_split[0], ctx, out, apostrophe, error);
931 238 : if (origin_split[0].empty() || origin_split[0][0] != '[') {
932 2 : error = strprintf("Key origin start '[ character expected but not found, got '%c' instead",
933 2 : origin_split[0].empty() ? /** empty, implies split char */ ']' : origin_split[0][0]);
934 2 : return nullptr;
935 : }
936 236 : auto slash_split = Split(origin_split[0].subspan(1), '/');
937 236 : if (slash_split[0].size() != 8) {
938 2 : error = strprintf("Fingerprint is not 4 bytes (%u characters instead of 8 characters)", slash_split[0].size());
939 2 : return nullptr;
940 : }
941 234 : std::string fpr_hex = std::string(slash_split[0].begin(), slash_split[0].end());
942 234 : if (!IsHex(fpr_hex)) {
943 0 : error = strprintf("Fingerprint '%s' is not hex", fpr_hex);
944 0 : return nullptr;
945 : }
946 234 : auto fpr_bytes = ParseHex(fpr_hex);
947 234 : KeyOriginInfo info;
948 : static_assert(sizeof(info.fingerprint) == 4, "Fingerprint must be 4 bytes");
949 234 : assert(fpr_bytes.size() == 4);
950 234 : std::copy(fpr_bytes.begin(), fpr_bytes.end(), info.fingerprint);
951 234 : if (!ParseKeyPath(slash_split, info.path, apostrophe, error)) return nullptr;
952 234 : auto provider = ParsePubkeyInner(key_exp_index, origin_split[1], ctx, out, apostrophe, error);
953 234 : if (!provider) return nullptr;
954 234 : return std::make_unique<OriginPubkeyProvider>(key_exp_index, std::move(info), std::move(provider), apostrophe);
955 3722 : }
956 :
957 : /** Parse a script in a particular context. */
958 6640 : std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error)
959 : {
960 : using namespace spanparsing;
961 :
962 6640 : auto expr = Expr(sp);
963 6640 : bool sorted_multi = false;
964 6640 : if (Func("pk", expr)) {
965 26 : auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error);
966 26 : if (!pubkey) {
967 0 : error = strprintf("pk(): %s", error);
968 0 : return nullptr;
969 : }
970 26 : ++key_exp_index;
971 26 : return std::make_unique<PKDescriptor>(std::move(pubkey));
972 26 : }
973 6614 : if (Func("pkh", expr)) {
974 2595 : auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error);
975 2595 : if (!pubkey) {
976 8 : error = strprintf("pkh(): %s", error);
977 8 : return nullptr;
978 : }
979 2587 : ++key_exp_index;
980 2587 : return std::make_unique<PKHDescriptor>(std::move(pubkey));
981 2595 : }
982 7917 : if (ctx == ParseScriptContext::TOP && Func("combo", expr)) {
983 657 : auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error);
984 657 : if (!pubkey) {
985 2 : error = strprintf("combo(): %s", error);
986 2 : return nullptr;
987 : }
988 655 : ++key_exp_index;
989 655 : return std::make_unique<ComboDescriptor>(std::move(pubkey));
990 4019 : } else if (Func("combo", expr)) {
991 2 : error = "Can only have combo() at top level";
992 2 : return nullptr;
993 : }
994 3360 : if ((sorted_multi = Func("sortedmulti", expr)) || Func("multi", expr)) {
995 145 : auto threshold = Expr(expr);
996 : uint32_t thres;
997 145 : std::vector<std::unique_ptr<PubkeyProvider>> providers;
998 145 : if (!ParseUInt32(std::string(threshold.begin(), threshold.end()), &thres)) {
999 2 : error = strprintf("Multi threshold '%s' is not valid", std::string(threshold.begin(), threshold.end()));
1000 2 : return nullptr;
1001 : }
1002 143 : size_t script_size = 0;
1003 582 : while (expr.size()) {
1004 444 : if (!Const(",", expr)) {
1005 0 : error = strprintf("Multi: expected ',', got '%c'", expr[0]);
1006 0 : return nullptr;
1007 : }
1008 444 : auto arg = Expr(expr);
1009 444 : auto pk = ParsePubkey(key_exp_index, arg, ctx, out, error);
1010 444 : if (!pk) {
1011 5 : error = strprintf("Multi: %s", error);
1012 5 : return nullptr;
1013 : }
1014 439 : script_size += pk->GetSize() + 1;
1015 439 : providers.emplace_back(std::move(pk));
1016 439 : key_exp_index++;
1017 444 : }
1018 138 : if (providers.empty() || providers.size() > MAX_PUBKEYS_PER_MULTISIG) {
1019 0 : error = strprintf("Cannot have %u keys in multisig; must have between 1 and %d keys, inclusive", providers.size(), MAX_PUBKEYS_PER_MULTISIG);
1020 0 : return nullptr;
1021 138 : } else if (thres < 1) {
1022 1 : error = strprintf("Multisig threshold cannot be %d, must be at least 1", thres);
1023 1 : return nullptr;
1024 137 : } else if (thres > providers.size()) {
1025 1 : error = strprintf("Multisig threshold cannot be larger than the number of keys; threshold is %d but only %u keys specified", thres, providers.size());
1026 1 : return nullptr;
1027 : }
1028 136 : if (ctx == ParseScriptContext::TOP) {
1029 23 : if (providers.size() > 3) {
1030 1 : error = strprintf("Cannot have %u pubkeys in bare multisig; only at most 3 pubkeys", providers.size());
1031 1 : return nullptr;
1032 : }
1033 22 : }
1034 135 : if (ctx == ParseScriptContext::P2SH) {
1035 : // This limits the maximum number of compressed pubkeys to 15.
1036 113 : if (script_size + 3 > MAX_SCRIPT_ELEMENT_SIZE) {
1037 2 : error = strprintf("P2SH script is too large, %d bytes is larger than %d bytes", script_size + 3, MAX_SCRIPT_ELEMENT_SIZE);
1038 2 : return nullptr;
1039 : }
1040 111 : }
1041 133 : return std::make_unique<MultisigDescriptor>(thres, std::move(providers), sorted_multi);
1042 145 : }
1043 6426 : if (ctx == ParseScriptContext::TOP && Func("sh", expr)) {
1044 267 : auto desc = ParseScript(key_exp_index, expr, ParseScriptContext::P2SH, out, error);
1045 267 : if (!desc || expr.size()) return nullptr;
1046 257 : return std::make_unique<SHDescriptor>(std::move(desc));
1047 3215 : } else if (Func("sh", expr)) {
1048 2 : error = "Can only have sh() at top level";
1049 2 : return nullptr;
1050 : }
1051 5890 : if (ctx == ParseScriptContext::TOP && Func("addr", expr)) {
1052 58 : CTxDestination dest = DecodeDestination(std::string(expr.begin(), expr.end()));
1053 58 : if (!IsValidDestination(dest)) {
1054 7 : error = "Address is not valid";
1055 7 : return nullptr;
1056 : }
1057 51 : return std::make_unique<AddressDescriptor>(std::move(dest));
1058 2888 : } else if (Func("addr", expr)) {
1059 0 : error = "Can only have addr() at top level";
1060 0 : return nullptr;
1061 : }
1062 5774 : if (ctx == ParseScriptContext::TOP && Func("raw", expr)) {
1063 2863 : std::string str(expr.begin(), expr.end());
1064 2863 : if (!IsHex(str)) {
1065 1 : error = "Raw script is not hex";
1066 1 : return nullptr;
1067 : }
1068 2862 : auto bytes = ParseHex(str);
1069 2862 : return std::make_unique<RawDescriptor>(CScript(bytes.begin(), bytes.end()));
1070 2888 : } else if (Func("raw", expr)) {
1071 0 : error = "Can only have raw() at top level";
1072 0 : return nullptr;
1073 : }
1074 25 : if (ctx == ParseScriptContext::P2SH) {
1075 2 : error = "A function is needed within P2SH";
1076 2 : return nullptr;
1077 : }
1078 23 : error = strprintf("'%s' is not a valid descriptor function", std::string(expr.begin(), expr.end()));
1079 23 : return nullptr;
1080 6640 : }
1081 :
1082 252885 : std::unique_ptr<PubkeyProvider> InferPubkey(const CPubKey& pubkey, ParseScriptContext, const SigningProvider& provider)
1083 : {
1084 252885 : std::unique_ptr<PubkeyProvider> key_provider = std::make_unique<ConstPubkeyProvider>(0, pubkey);
1085 252885 : KeyOriginInfo info;
1086 252885 : if (provider.GetKeyOrigin(pubkey.GetID(), info)) {
1087 252053 : return std::make_unique<OriginPubkeyProvider>(0, std::move(info), std::move(key_provider), /*apostrophe=*/false);
1088 : }
1089 832 : return key_provider;
1090 252885 : }
1091 :
1092 322721 : std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptContext ctx, const SigningProvider& provider)
1093 : {
1094 322721 : std::vector<std::vector<unsigned char>> data;
1095 322721 : TxoutType txntype = Solver(script, data);
1096 :
1097 322721 : if (txntype == TxoutType::PUBKEY) {
1098 37003 : CPubKey pubkey(data[0]);
1099 37003 : if (pubkey.IsValid()) {
1100 37003 : return std::make_unique<PKDescriptor>(InferPubkey(pubkey, ctx, provider));
1101 : }
1102 0 : }
1103 285718 : if (txntype == TxoutType::PUBKEYHASH) {
1104 235398 : uint160 hash(data[0]);
1105 235398 : CKeyID keyid(hash);
1106 235398 : CPubKey pubkey;
1107 235398 : if (provider.GetPubKey(keyid, pubkey)) {
1108 214656 : return std::make_unique<PKHDescriptor>(InferPubkey(pubkey, ctx, provider));
1109 : }
1110 20742 : }
1111 71062 : if (txntype == TxoutType::MULTISIG) {
1112 342 : std::vector<std::unique_ptr<PubkeyProvider>> providers;
1113 1568 : for (size_t i = 1; i + 1 < data.size(); ++i) {
1114 1226 : CPubKey pubkey(data[i]);
1115 1226 : providers.push_back(InferPubkey(pubkey, ctx, provider));
1116 1226 : }
1117 342 : return std::make_unique<MultisigDescriptor>((int)data[0][0], std::move(providers));
1118 342 : }
1119 70720 : if (txntype == TxoutType::SCRIPTHASH && ctx == ParseScriptContext::TOP) {
1120 49657 : uint160 hash(data[0]);
1121 49657 : CScriptID scriptid(hash);
1122 49657 : CScript subscript;
1123 49657 : if (provider.GetCScript(scriptid, subscript)) {
1124 36465 : auto sub = InferScript(subscript, ParseScriptContext::P2SH, provider);
1125 36465 : if (sub) return std::make_unique<SHDescriptor>(std::move(sub));
1126 36465 : }
1127 49657 : }
1128 :
1129 34255 : CTxDestination dest;
1130 34255 : if (ExtractDestination(script, dest)) {
1131 33934 : if (GetScriptForDestination(dest) == script) {
1132 33934 : return std::make_unique<AddressDescriptor>(std::move(dest));
1133 : }
1134 0 : }
1135 :
1136 321 : return std::make_unique<RawDescriptor>(script);
1137 322721 : }
1138 :
1139 :
1140 : } // namespace
1141 :
1142 : /** Check a descriptor checksum, and update desc to be the checksum-less part. */
1143 6488 : bool CheckChecksum(Span<const char>& sp, bool require_checksum, std::string& error, std::string* out_checksum = nullptr)
1144 : {
1145 : using namespace spanparsing;
1146 :
1147 6488 : auto check_split = Split(sp, '#');
1148 6488 : if (check_split.size() > 2) {
1149 2 : error = "Multiple '#' symbols";
1150 2 : return false;
1151 : }
1152 6486 : if (check_split.size() == 1 && require_checksum){
1153 20 : error = "Missing checksum";
1154 20 : return false;
1155 : }
1156 6466 : if (check_split.size() == 2) {
1157 4930 : if (check_split[1].size() != 8) {
1158 6 : error = strprintf("Expected 8 character checksum, not %u characters", check_split[1].size());
1159 6 : return false;
1160 : }
1161 4924 : }
1162 6460 : auto checksum = DescriptorChecksum(check_split[0]);
1163 6460 : if (checksum.empty()) {
1164 1 : error = "Invalid characters in payload";
1165 1 : return false;
1166 : }
1167 6459 : if (check_split.size() == 2) {
1168 4923 : if (!std::equal(checksum.begin(), checksum.end(), check_split[1].begin())) {
1169 14 : error = strprintf("Provided checksum '%s' does not match computed checksum '%s'", std::string(check_split[1].begin(), check_split[1].end()), checksum);
1170 14 : return false;
1171 : }
1172 4909 : }
1173 6445 : if (out_checksum) *out_checksum = std::move(checksum);
1174 6445 : sp = check_split[0];
1175 6445 : return true;
1176 6488 : }
1177 :
1178 6414 : std::unique_ptr<Descriptor> Parse(const std::string& descriptor, FlatSigningProvider& out, std::string& error, bool require_checksum)
1179 : {
1180 6414 : Span<const char> sp{descriptor};
1181 6414 : if (!CheckChecksum(sp, require_checksum, error)) return nullptr;
1182 6373 : uint32_t key_exp_index = 0;
1183 6373 : auto ret = ParseScript(key_exp_index, sp, ParseScriptContext::TOP, out, error);
1184 6373 : if (sp.size() == 0 && ret) return std::unique_ptr<Descriptor>(std::move(ret));
1185 59 : return nullptr;
1186 6414 : }
1187 :
1188 74 : std::string GetDescriptorChecksum(const std::string& descriptor)
1189 : {
1190 74 : std::string ret;
1191 74 : std::string error;
1192 74 : Span<const char> sp{descriptor};
1193 74 : if (!CheckChecksum(sp, false, error, &ret)) return "";
1194 72 : return ret;
1195 74 : }
1196 :
1197 286256 : std::unique_ptr<Descriptor> InferDescriptor(const CScript& script, const SigningProvider& provider)
1198 : {
1199 286256 : return InferScript(script, ParseScriptContext::TOP, provider);
1200 : }
1201 :
1202 2985 : uint256 DescriptorID(const Descriptor& desc)
1203 : {
1204 2985 : std::string desc_str = desc.ToString();
1205 2985 : uint256 id;
1206 2985 : CSHA256().Write((unsigned char*)desc_str.data(), desc_str.size()).Finalize(id.begin());
1207 : return id;
1208 2985 : }
1209 :
1210 5550 : void DescriptorCache::CacheParentExtPubKey(uint32_t key_exp_pos, const CExtPubKey& xpub)
1211 : {
1212 5550 : m_parent_xpubs[key_exp_pos] = xpub;
1213 5550 : }
1214 :
1215 5364 : void DescriptorCache::CacheDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index, const CExtPubKey& xpub)
1216 : {
1217 5364 : auto& xpubs = m_derived_xpubs[key_exp_pos];
1218 5364 : xpubs[der_index] = xpub;
1219 5364 : }
1220 :
1221 4840 : void DescriptorCache::CacheLastHardenedExtPubKey(uint32_t key_exp_pos, const CExtPubKey& xpub)
1222 : {
1223 4840 : m_last_hardened_xpubs[key_exp_pos] = xpub;
1224 4840 : }
1225 :
1226 338409 : bool DescriptorCache::GetCachedParentExtPubKey(uint32_t key_exp_pos, CExtPubKey& xpub) const
1227 : {
1228 338409 : const auto& it = m_parent_xpubs.find(key_exp_pos);
1229 338409 : if (it == m_parent_xpubs.end()) return false;
1230 335615 : xpub = it->second;
1231 335615 : return true;
1232 338409 : }
1233 :
1234 340862 : bool DescriptorCache::GetCachedDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index, CExtPubKey& xpub) const
1235 : {
1236 340862 : const auto& key_exp_it = m_derived_xpubs.find(key_exp_pos);
1237 340862 : if (key_exp_it == m_derived_xpubs.end()) return false;
1238 3877 : const auto& der_it = key_exp_it->second.find(der_index);
1239 3877 : if (der_it == key_exp_it->second.end()) return false;
1240 319 : xpub = der_it->second;
1241 319 : return true;
1242 340862 : }
1243 :
1244 1912 : bool DescriptorCache::GetCachedLastHardenedExtPubKey(uint32_t key_exp_pos, CExtPubKey& xpub) const
1245 : {
1246 1912 : const auto& it = m_last_hardened_xpubs.find(key_exp_pos);
1247 1912 : if (it == m_last_hardened_xpubs.end()) return false;
1248 645 : xpub = it->second;
1249 645 : return true;
1250 1912 : }
1251 :
1252 154632 : DescriptorCache DescriptorCache::MergeAndDiff(const DescriptorCache& other)
1253 : {
1254 154632 : DescriptorCache diff;
1255 156102 : for (const auto& parent_xpub_pair : other.GetCachedParentExtPubKeys()) {
1256 1470 : CExtPubKey xpub;
1257 1470 : if (GetCachedParentExtPubKey(parent_xpub_pair.first, xpub)) {
1258 12 : if (xpub != parent_xpub_pair.second) {
1259 0 : throw std::runtime_error(std::string(__func__) + ": New cached parent xpub does not match already cached parent xpub");
1260 : }
1261 12 : continue;
1262 : }
1263 1458 : CacheParentExtPubKey(parent_xpub_pair.first, parent_xpub_pair.second);
1264 1458 : diff.CacheParentExtPubKey(parent_xpub_pair.first, parent_xpub_pair.second);
1265 : }
1266 156420 : for (const auto& derived_xpub_map_pair : other.GetCachedDerivedExtPubKeys()) {
1267 3576 : for (const auto& derived_xpub_pair : derived_xpub_map_pair.second) {
1268 1788 : CExtPubKey xpub;
1269 1788 : if (GetCachedDerivedExtPubKey(derived_xpub_map_pair.first, derived_xpub_pair.first, xpub)) {
1270 0 : if (xpub != derived_xpub_pair.second) {
1271 0 : throw std::runtime_error(std::string(__func__) + ": New cached derived xpub does not match already cached derived xpub");
1272 : }
1273 0 : continue;
1274 : }
1275 1788 : CacheDerivedExtPubKey(derived_xpub_map_pair.first, derived_xpub_pair.first, derived_xpub_pair.second);
1276 1788 : diff.CacheDerivedExtPubKey(derived_xpub_map_pair.first, derived_xpub_pair.first, derived_xpub_pair.second);
1277 : }
1278 : }
1279 155899 : for (const auto& lh_xpub_pair : other.GetCachedLastHardenedExtPubKeys()) {
1280 1267 : CExtPubKey xpub;
1281 1267 : if (GetCachedLastHardenedExtPubKey(lh_xpub_pair.first, xpub)) {
1282 0 : if (xpub != lh_xpub_pair.second) {
1283 0 : throw std::runtime_error(std::string(__func__) + ": New cached last hardened xpub does not match already cached last hardened xpub");
1284 : }
1285 0 : continue;
1286 : }
1287 1267 : CacheLastHardenedExtPubKey(lh_xpub_pair.first, lh_xpub_pair.second);
1288 1267 : diff.CacheLastHardenedExtPubKey(lh_xpub_pair.first, lh_xpub_pair.second);
1289 : }
1290 154632 : return diff;
1291 154632 : }
1292 :
1293 309418 : ExtPubKeyMap DescriptorCache::GetCachedParentExtPubKeys() const
1294 : {
1295 309418 : return m_parent_xpubs;
1296 : }
1297 :
1298 309418 : std::unordered_map<uint32_t, ExtPubKeyMap> DescriptorCache::GetCachedDerivedExtPubKeys() const
1299 : {
1300 309418 : return m_derived_xpubs;
1301 : }
1302 :
1303 309934 : ExtPubKeyMap DescriptorCache::GetCachedLastHardenedExtPubKeys() const
1304 : {
1305 309934 : return m_last_hardened_xpubs;
1306 : }
|
