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 2198581 : uint64_t PolyMod(uint64_t c, int val)
85 : {
86 2198581 : uint8_t c0 = c >> 35;
87 2198581 : c = ((c & 0x7ffffffff) << 5) ^ val;
88 2198581 : if (c0 & 1) c ^= 0xf5dee51989;
89 2198581 : if (c0 & 2) c ^= 0xa9fdca3312;
90 2198581 : if (c0 & 4) c ^= 0x1bab10e32d;
91 2198581 : if (c0 & 8) c ^= 0x3706b1677a;
92 2198581 : if (c0 & 16) c ^= 0x644d626ffd;
93 2198581 : return c;
94 : }
95 :
96 12201 : 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 12224 : static std::string INPUT_CHARSET =
112 23 : "0123456789()[],'/*abcdefgh@:$%{}"
113 : "IJKLMNOPQRSTUVWXYZ&+-.;<=>?!^_|~"
114 : "ijklmnopqrstuvwxyzABCDEFGH`#\"\\ ";
115 :
116 : /** The character set for the checksum itself (same as bech32). */
117 12201 : static std::string CHECKSUM_CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l";
118 :
119 12201 : uint64_t c = 1;
120 12201 : int cls = 0;
121 12201 : int clscount = 0;
122 1581969 : for (auto ch : span) {
123 1569769 : auto pos = INPUT_CHARSET.find(ch);
124 1569769 : if (pos == std::string::npos) return "";
125 1569768 : c = PolyMod(c, pos & 31); // Emit a symbol for the position inside the group, for every character.
126 1569768 : cls = cls * 3 + (pos >> 5); // Accumulate the group numbers
127 1569768 : if (++clscount == 3) {
128 : // Emit an extra symbol representing the group numbers, for every 3 characters.
129 519169 : c = PolyMod(c, cls);
130 519169 : cls = 0;
131 519169 : clscount = 0;
132 519169 : }
133 : }
134 12200 : if (clscount > 0) c = PolyMod(c, cls);
135 109800 : for (int j = 0; j < 8; ++j) c = PolyMod(c, 0); // Shift further to determine the checksum.
136 12200 : c ^= 1; // Prevent appending zeroes from not affecting the checksum.
137 :
138 12200 : std::string ret(8, ' ');
139 109800 : for (int j = 0; j < 8; ++j) ret[j] = CHECKSUM_CHARSET[(c >> (5 * (7 - j))) & 31];
140 12200 : return ret;
141 24401 : }
142 :
143 12009 : 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 1344 : explicit PubkeyProvider(uint32_t exp_index) : m_expr_index(exp_index) {}
161 :
162 1344 : 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 71 : std::string OriginString(bool normalized=false) const
199 : {
200 71 : return HexStr(m_origin.fingerprint) + FormatHDKeypath(m_origin.path, /*apostrophe=*/!normalized && m_apostrophe);
201 0 : }
202 :
203 : public:
204 1158 : 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 816 : bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override
206 : {
207 816 : if (!m_provider->GetPubKey(pos, arg, key, info, read_cache, write_cache)) return false;
208 816 : std::copy(std::begin(m_origin.fingerprint), std::end(m_origin.fingerprint), info.fingerprint);
209 816 : info.path.insert(info.path.begin(), m_origin.path.begin(), m_origin.path.end());
210 816 : return true;
211 816 : }
212 22 : bool IsRange() const override { return m_provider->IsRange(); }
213 12 : size_t GetSize() const override { return m_provider->GetSize(); }
214 27 : std::string ToString() const override { return "[" + OriginString() + "]" + m_provider->ToString(); }
215 44 : bool ToPrivateString(const SigningProvider& arg, std::string& ret) const override
216 : {
217 44 : std::string sub;
218 44 : if (!m_provider->ToPrivateString(arg, sub)) return false;
219 22 : ret = "[" + OriginString() + "]" + std::move(sub);
220 22 : return true;
221 44 : }
222 22 : bool ToNormalizedString(const SigningProvider& arg, std::string& ret, const DescriptorCache* cache) const override
223 : {
224 22 : std::string sub;
225 22 : 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 22 : if (sub[0] == '[') {
230 4 : sub = sub.substr(9);
231 4 : ret = "[" + OriginString(/*normalized=*/true) + std::move(sub);
232 4 : } else {
233 18 : ret = "[" + OriginString(/*normalized=*/true) + "]" + std::move(sub);
234 : }
235 22 : return true;
236 22 : }
237 0 : bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const override
238 : {
239 0 : 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 1292 : ConstPubkeyProvider(uint32_t exp_index, const CPubKey& pubkey) : PubkeyProvider(exp_index), m_pubkey(pubkey) {}
250 931 : bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override
251 : {
252 931 : key = m_pubkey;
253 931 : info.path.clear();
254 931 : CKeyID keyid = m_pubkey.GetID();
255 931 : std::copy(keyid.begin(), keyid.begin() + sizeof(info.fingerprint), info.fingerprint);
256 931 : return true;
257 : }
258 465 : bool IsRange() const override { return false; }
259 53 : size_t GetSize() const override { return m_pubkey.size(); }
260 517 : std::string ToString() const override { return HexStr(m_pubkey); }
261 54 : bool ToPrivateString(const SigningProvider& arg, std::string& ret) const override
262 : {
263 54 : CKey key;
264 54 : if (!arg.GetKey(m_pubkey.GetID(), key)) return false;
265 30 : ret = EncodeSecret(key);
266 30 : return true;
267 54 : }
268 30 : bool ToNormalizedString(const SigningProvider& arg, std::string& ret, const DescriptorCache* cache) const override
269 : {
270 30 : ret = ToString();
271 30 : return true;
272 : }
273 16 : bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const override
274 : {
275 16 : 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 1198 : bool GetExtKey(const SigningProvider& arg, CExtKey& ret) const
296 : {
297 1198 : CKey key;
298 1198 : if (!arg.GetKey(m_root_extkey.pubkey.GetID(), key)) return false;
299 1170 : ret.nDepth = m_root_extkey.nDepth;
300 1170 : std::copy(m_root_extkey.vchFingerprint, m_root_extkey.vchFingerprint + sizeof(ret.vchFingerprint), ret.vchFingerprint);
301 1170 : ret.nChild = m_root_extkey.nChild;
302 1170 : ret.chaincode = m_root_extkey.chaincode;
303 1170 : ret.key = key;
304 1170 : return true;
305 1198 : }
306 :
307 : // Derives the last xprv
308 1128 : bool GetDerivedExtKey(const SigningProvider& arg, CExtKey& xprv, CExtKey& last_hardened) const
309 : {
310 1128 : if (!GetExtKey(arg, xprv)) return false;
311 3542 : for (auto entry : m_path) {
312 2414 : if (!xprv.Derive(xprv, entry)) return false;
313 2414 : if (entry >> 31) {
314 2292 : last_hardened = xprv;
315 2292 : }
316 : }
317 1128 : return true;
318 1128 : }
319 :
320 1318 : bool IsHardened() const
321 : {
322 1318 : if (m_derive == DeriveType::HARDENED) return true;
323 426 : for (auto entry : m_path) {
324 226 : if (entry >> 31) return true;
325 : }
326 200 : return false;
327 1318 : }
328 :
329 : public:
330 238 : 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 22697 : bool IsRange() const override { return m_derive != DeriveType::NO; }
332 32 : size_t GetSize() const override { return 33; }
333 85688 : 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 85688 : KeyOriginInfo parent_info;
337 85688 : CKeyID keyid = m_root_extkey.pubkey.GetID();
338 85688 : std::copy(keyid.begin(), keyid.begin() + sizeof(parent_info.fingerprint), parent_info.fingerprint);
339 85688 : parent_info.path = m_path;
340 :
341 : // Info of the derived key itself which is copied out upon successful completion
342 85688 : KeyOriginInfo final_info_out_tmp = parent_info;
343 85688 : if (m_derive == DeriveType::UNHARDENED) final_info_out_tmp.path.push_back((uint32_t)pos);
344 85688 : 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 85688 : CExtPubKey final_extkey = m_root_extkey;
348 85688 : CExtPubKey parent_extkey = m_root_extkey;
349 85688 : CExtPubKey last_hardened_extkey;
350 85688 : bool der = true;
351 85688 : if (read_cache) {
352 84370 : if (!read_cache->GetCachedDerivedExtPubKey(m_expr_index, pos, final_extkey)) {
353 84368 : if (m_derive == DeriveType::HARDENED) return false;
354 : // Try to get the derivation parent
355 83368 : if (!read_cache->GetCachedParentExtPubKey(m_expr_index, parent_extkey)) return false;
356 83300 : final_extkey = parent_extkey;
357 83300 : if (m_derive == DeriveType::UNHARDENED) der = parent_extkey.Derive(final_extkey, pos);
358 83300 : }
359 84620 : } else if (IsHardened()) {
360 1118 : CExtKey xprv;
361 1118 : CExtKey lh_xprv;
362 1118 : if (!GetDerivedExtKey(arg, xprv, lh_xprv)) return false;
363 1118 : parent_extkey = xprv.Neuter();
364 1118 : if (m_derive == DeriveType::UNHARDENED) der = xprv.Derive(xprv, pos);
365 1118 : if (m_derive == DeriveType::HARDENED) der = xprv.Derive(xprv, pos | 0x80000000UL);
366 1118 : final_extkey = xprv.Neuter();
367 1118 : if (lh_xprv.key.IsValid()) {
368 1118 : last_hardened_extkey = lh_xprv.Neuter();
369 1118 : }
370 1118 : } else {
371 308 : for (auto entry : m_path) {
372 108 : if (!parent_extkey.Derive(parent_extkey, entry)) return false;
373 : }
374 200 : final_extkey = parent_extkey;
375 200 : if (m_derive == DeriveType::UNHARDENED) der = parent_extkey.Derive(final_extkey, pos);
376 200 : assert(m_derive != DeriveType::HARDENED);
377 : }
378 84620 : if (!der) return false;
379 :
380 84620 : final_info_out = final_info_out_tmp;
381 84620 : key_out = final_extkey.pubkey;
382 :
383 84620 : if (write_cache) {
384 : // Only cache parent if there is any unhardened derivation
385 1194 : if (m_derive != DeriveType::HARDENED) {
386 194 : write_cache->CacheParentExtPubKey(m_expr_index, parent_extkey);
387 : // Cache last hardened xpub if we have it
388 194 : if (last_hardened_extkey.pubkey.IsValid()) {
389 94 : write_cache->CacheLastHardenedExtPubKey(m_expr_index, last_hardened_extkey);
390 94 : }
391 1194 : } else if (final_info_out.path.size() > 0) {
392 1000 : write_cache->CacheDerivedExtPubKey(m_expr_index, pos, final_extkey);
393 1000 : }
394 1194 : }
395 :
396 84620 : return true;
397 85688 : }
398 11408 : std::string ToString(bool normalized) const
399 : {
400 11408 : const bool use_apostrophe = !normalized && m_apostrophe;
401 11408 : std::string ret = EncodeExtPubKey(m_root_extkey) + FormatHDKeypath(m_path, /*apostrophe=*/use_apostrophe);
402 11408 : if (IsRange()) {
403 11332 : ret += "/*";
404 11332 : if (m_derive == DeriveType::HARDENED) ret += use_apostrophe ? '\'' : 'h';
405 11332 : }
406 11408 : return ret;
407 11408 : }
408 11374 : std::string ToString() const override
409 : {
410 11374 : return ToString(/*normalized=*/false);
411 : }
412 70 : bool ToPrivateString(const SigningProvider& arg, std::string& out) const override
413 : {
414 70 : CExtKey key;
415 70 : if (!GetExtKey(arg, key)) return false;
416 42 : out = EncodeExtKey(key) + FormatHDKeypath(m_path, /*apostrophe=*/m_apostrophe);
417 42 : if (IsRange()) {
418 6 : out += "/*";
419 6 : if (m_derive == DeriveType::HARDENED) out += m_apostrophe ? '\'' : 'h';
420 6 : }
421 42 : return true;
422 70 : }
423 42 : bool ToNormalizedString(const SigningProvider& arg, std::string& out, const DescriptorCache* cache) const override
424 : {
425 42 : if (m_derive == DeriveType::HARDENED) {
426 0 : out = ToString(/*normalized=*/true);
427 :
428 0 : return true;
429 : }
430 : // Step backwards to find the last hardened step in the path
431 42 : int i = (int)m_path.size() - 1;
432 68 : for (; i >= 0; --i) {
433 34 : if (m_path.at(i) >> 31) {
434 8 : break;
435 : }
436 26 : }
437 : // Either no derivation or all unhardened derivation
438 42 : if (i == -1) {
439 34 : out = ToString(/*normalized=*/true);
440 34 : return true;
441 : }
442 : // Get the path to the last hardened stup
443 8 : KeyOriginInfo origin;
444 8 : int k = 0;
445 16 : for (; k <= i; ++k) {
446 : // Add to the path
447 8 : origin.path.push_back(m_path.at(k));
448 8 : }
449 : // Build the remaining path
450 8 : KeyPath end_path;
451 16 : for (; k < (int)m_path.size(); ++k) {
452 8 : end_path.push_back(m_path.at(k));
453 8 : }
454 : // Get the fingerprint
455 8 : CKeyID id = m_root_extkey.pubkey.GetID();
456 8 : std::copy(id.begin(), id.begin() + 4, origin.fingerprint);
457 :
458 8 : CExtPubKey xpub;
459 8 : CExtKey lh_xprv;
460 : // If we have the cache, just get the parent xpub
461 8 : if (cache != nullptr) {
462 0 : cache->GetCachedLastHardenedExtPubKey(m_expr_index, xpub);
463 0 : }
464 8 : 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 8 : assert(xpub.pubkey.IsValid());
471 :
472 : // Build the string
473 8 : std::string origin_str = HexStr(origin.fingerprint) + FormatHDKeypath(origin.path);
474 8 : out = "[" + origin_str + "]" + EncodeExtPubKey(xpub) + FormatHDKeypath(end_path);
475 8 : if (IsRange()) {
476 0 : out += "/*";
477 0 : assert(m_derive == DeriveType::UNHARDENED);
478 0 : }
479 8 : return true;
480 42 : }
481 2 : bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const override
482 : {
483 2 : CExtKey extkey;
484 2 : CExtKey dummy;
485 2 : if (!GetDerivedExtKey(arg, extkey, dummy)) return false;
486 2 : if (m_derive == DeriveType::UNHARDENED && !extkey.Derive(extkey, pos)) return false;
487 2 : if (m_derive == DeriveType::HARDENED && !extkey.Derive(extkey, pos | 0x80000000UL)) return false;
488 2 : key = extkey.key;
489 2 : return true;
490 2 : }
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 11970 : 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 660 : 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 84 : 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 250 : bool IsSolvable() const override
535 : {
536 314 : for (const auto& arg : m_subdescriptor_args) {
537 64 : if (!arg->IsSolvable()) return false;
538 : }
539 250 : return true;
540 250 : }
541 :
542 11702 : bool IsRange() const final
543 : {
544 12211 : for (const auto& pubkey : m_pubkey_args) {
545 11704 : if (pubkey->IsRange()) return true;
546 : }
547 527 : for (const auto& arg : m_subdescriptor_args) {
548 20 : if (arg->IsRange()) return true;
549 : }
550 507 : return false;
551 11702 : }
552 :
553 12029 : virtual bool ToStringSubScriptHelper(const SigningProvider* arg, std::string& ret, const StringType type, const DescriptorCache* cache = nullptr) const
554 : {
555 12029 : size_t pos = 0;
556 12085 : for (const auto& scriptarg : m_subdescriptor_args) {
557 72 : if (pos++) ret += ",";
558 72 : std::string tmp;
559 72 : if (!scriptarg->ToStringHelper(arg, tmp, type, cache)) return false;
560 56 : ret += tmp;
561 72 : }
562 12013 : return true;
563 12029 : }
564 :
565 12081 : bool ToStringHelper(const SigningProvider* arg, std::string& out, const StringType type, const DescriptorCache* cache = nullptr) const
566 : {
567 12081 : std::string extra = ToStringExtra();
568 12081 : size_t pos = extra.size() > 0 ? 1 : 0;
569 12081 : std::string ret = m_name + "(" + extra;
570 24086 : for (const auto& pubkey : m_pubkey_args) {
571 12057 : if (pos++) ret += ",";
572 12057 : std::string tmp;
573 12057 : switch (type) {
574 : case StringType::NORMALIZED:
575 72 : if (!pubkey->ToNormalizedString(*arg, tmp, cache)) return false;
576 72 : break;
577 : case StringType::PRIVATE:
578 124 : if (!pubkey->ToPrivateString(*arg, tmp)) return false;
579 72 : break;
580 : case StringType::PUBLIC:
581 11861 : tmp = pubkey->ToString();
582 11861 : break;
583 : }
584 12005 : ret += tmp;
585 12057 : }
586 12029 : std::string subscript;
587 12029 : if (!ToStringSubScriptHelper(arg, subscript, type, cache)) return false;
588 12013 : if (pos && subscript.size()) ret += ',';
589 12013 : out = std::move(ret) + std::move(subscript) + ")";
590 12013 : return true;
591 12081 : }
592 :
593 11853 : std::string ToString() const final
594 : {
595 11853 : std::string ret;
596 11853 : ToStringHelper(nullptr, ret, StringType::PUBLIC);
597 11853 : return AddChecksum(ret);
598 11853 : }
599 :
600 104 : bool ToPrivateString(const SigningProvider& arg, std::string& out) const override
601 : {
602 104 : bool ret = ToStringHelper(&arg, out, StringType::PRIVATE);
603 104 : out = AddChecksum(out);
604 104 : return ret;
605 : }
606 :
607 52 : bool ToNormalizedString(const SigningProvider& arg, std::string& out, const DescriptorCache* cache) const override final
608 : {
609 52 : bool ret = ToStringHelper(&arg, out, StringType::NORMALIZED, cache);
610 52 : out = AddChecksum(out);
611 52 : return ret;
612 : }
613 :
614 86577 : bool ExpandHelper(int pos, const SigningProvider& arg, const DescriptorCache* read_cache, std::vector<CScript>& output_scripts, FlatSigningProvider& out, DescriptorCache* write_cache) const
615 : {
616 86577 : std::vector<std::pair<CPubKey, KeyOriginInfo>> entries;
617 86577 : 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 172128 : for (const auto& p : m_pubkey_args) {
621 86619 : entries.emplace_back();
622 86619 : if (!p->GetPubKey(pos, arg, entries.back().first, entries.back().second, read_cache, write_cache)) return false;
623 : }
624 85509 : std::vector<CScript> subscripts;
625 85509 : FlatSigningProvider subprovider;
626 85768 : for (const auto& subarg : m_subdescriptor_args) {
627 261 : std::vector<CScript> outscripts;
628 261 : if (!subarg->ExpandHelper(pos, arg, read_cache, outscripts, subprovider, write_cache)) return false;
629 259 : assert(outscripts.size() == 1);
630 259 : subscripts.emplace_back(std::move(outscripts[0]));
631 261 : }
632 85507 : out.Merge(std::move(subprovider));
633 :
634 85507 : std::vector<CPubKey> pubkeys;
635 85507 : pubkeys.reserve(entries.size());
636 171058 : for (auto& entry : entries) {
637 85551 : pubkeys.push_back(entry.first);
638 85551 : out.origins.emplace(entry.first.GetID(), std::make_pair<CPubKey, KeyOriginInfo>(CPubKey(entry.first), std::move(entry.second)));
639 : }
640 :
641 85507 : output_scripts = MakeScripts(pubkeys, Span{subscripts}, out);
642 85507 : return true;
643 86577 : }
644 :
645 1870 : bool Expand(int pos, const SigningProvider& provider, std::vector<CScript>& output_scripts, FlatSigningProvider& out, DescriptorCache* write_cache = nullptr) const final
646 : {
647 1870 : return ExpandHelper(pos, provider, nullptr, output_scripts, out, write_cache);
648 : }
649 :
650 84446 : bool ExpandFromCache(int pos, const DescriptorCache& read_cache, std::vector<CScript>& output_scripts, FlatSigningProvider& out) const final
651 : {
652 84446 : return ExpandHelper(pos, DUMMY_SIGNING_PROVIDER, &read_cache, output_scripts, out, nullptr);
653 : }
654 :
655 18 : void ExpandPrivate(int pos, const SigningProvider& provider, FlatSigningProvider& out) const final
656 : {
657 36 : for (const auto& p : m_pubkey_args) {
658 18 : CKey key;
659 18 : if (!p->GetPrivKey(pos, provider, key)) continue;
660 18 : out.keys.emplace(key.GetPubKey().GetID(), key);
661 18 : }
662 18 : for (const auto& arg : m_subdescriptor_args) {
663 0 : arg->ExpandPrivate(pos, provider, out);
664 : }
665 18 : }
666 8 : 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 15 : std::string ToStringExtra() const override { return EncodeDestination(m_destination); }
675 0 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, Span<const CScript>, FlatSigningProvider&) const override { return Vector(GetScriptForDestination(m_destination)); }
676 : public:
677 30 : AddressDescriptor(CTxDestination destination) : DescriptorImpl({}, "addr"), m_destination(std::move(destination)) {}
678 0 : bool IsSolvable() const final { return false; }
679 :
680 0 : std::optional<OutputType> GetOutputType() const override
681 : {
682 0 : switch (m_destination.index()) {
683 : case 1 /* PKHash */:
684 0 : case 2 /* ScriptHash */: return OutputType::LEGACY;
685 0 : case 0 /* CNoDestination */:
686 0 : default: return std::nullopt;
687 : }
688 0 : }
689 0 : bool IsSingleType() const final { return true; }
690 0 : 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 7 : std::string ToStringExtra() const override { return HexStr(m_script); }
699 0 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, Span<const CScript>, FlatSigningProvider&) const override { return Vector(m_script); }
700 : public:
701 14 : RawDescriptor(CScript script) : DescriptorImpl({}, "raw"), m_script(std::move(script)) {}
702 0 : bool IsSolvable() const final { return false; }
703 :
704 0 : std::optional<OutputType> GetOutputType() const override
705 : {
706 0 : CTxDestination dest;
707 0 : ExtractDestination(m_script, dest);
708 0 : switch (dest.index()) {
709 : case 1 /* PKHash */:
710 0 : case 2 /* ScriptHash */: return OutputType::LEGACY;
711 0 : case 0 /* CNoDestination */:
712 0 : default: return std::nullopt;
713 : }
714 0 : }
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 449 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider&) const override { return Vector(GetScriptForRawPubKey(keys[0])); }
724 : public:
725 724 : PKDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), "pk") {}
726 6 : std::optional<OutputType> GetOutputType() const override { return OutputType::LEGACY; }
727 0 : bool IsSingleType() const final { return true; }
728 : };
729 :
730 : /** A parsed pkh(P) descriptor. */
731 : class PKHDescriptor final : public DescriptorImpl
732 : {
733 : protected:
734 84390 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider& out) const override
735 : {
736 84390 : CKeyID id = keys[0].GetID();
737 84390 : out.pubkeys.emplace(id, keys[0]);
738 84390 : return Vector(GetScriptForDestination(PKHash(id)));
739 0 : }
740 : public:
741 340 : PKHDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), "pkh") {}
742 14 : std::optional<OutputType> GetOutputType() const override { return OutputType::LEGACY; }
743 11100 : 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 89 : std::string ToStringExtra() const override { return strprintf("%i", m_threshold); }
753 303 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider&) const override {
754 303 : if (m_sorted) {
755 72 : std::vector<CPubKey> sorted_keys(keys);
756 72 : std::sort(sorted_keys.begin(), sorted_keys.end());
757 72 : return Vector(GetScriptForMultisig(m_threshold, sorted_keys));
758 72 : }
759 231 : return Vector(GetScriptForMultisig(m_threshold, keys));
760 303 : }
761 : public:
762 170 : 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 259 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, Span<const CScript> scripts, FlatSigningProvider& out) const override
771 : {
772 259 : auto ret = Vector(GetScriptForDestination(ScriptHash(scripts[0])));
773 259 : if (ret.size()) out.scripts.emplace(CScriptID(scripts[0]), scripts[0]);
774 259 : return ret;
775 259 : }
776 : public:
777 168 : SHDescriptor(std::unique_ptr<DescriptorImpl> desc) : DescriptorImpl({}, std::move(desc), "sh") {}
778 :
779 16 : std::optional<OutputType> GetOutputType() const override
780 : {
781 16 : assert(m_subdescriptor_args.size() == 1);
782 16 : return OutputType::LEGACY;
783 : }
784 0 : bool IsSingleType() const final { return true; }
785 : };
786 :
787 : /** A parsed combo(P) descriptor. */
788 : class ComboDescriptor final : public DescriptorImpl
789 : {
790 : protected:
791 106 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript> scripts, FlatSigningProvider& out) const override
792 : {
793 106 : std::vector<CScript> ret;
794 106 : CKeyID id = keys[0].GetID();
795 106 : out.pubkeys.emplace(id, keys[0]);
796 106 : ret.emplace_back(GetScriptForRawPubKey(keys[0])); // P2PK
797 106 : if (keys[0].IsCompressed()) {
798 82 : CScript p2pkh = GetScriptForDestination(PKHash(id));
799 82 : out.scripts.emplace(CScriptID(p2pkh), p2pkh);
800 82 : ret.emplace_back(p2pkh);
801 82 : ret.emplace_back(GetScriptForDestination(ScriptHash(p2pkh))); // P2SH-P2PKH
802 82 : }
803 106 : return ret;
804 106 : }
805 :
806 : public:
807 42 : ComboDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), "combo") {}
808 8 : std::optional<OutputType> GetOutputType() const override { return OutputType::LEGACY; }
809 0 : 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 145 : [[nodiscard]] bool ParseKeyPath(const std::vector<Span<const char>>& split, KeyPath& out, bool& apostrophe, std::string& error)
831 : {
832 553 : for (size_t i = 1; i < split.size(); ++i) {
833 412 : Span<const char> elem = split[i];
834 412 : bool hardened = false;
835 412 : if (elem.size() > 0) {
836 412 : const char last = elem[elem.size() - 1];
837 412 : if (last == '\'' || last == 'h') {
838 282 : elem = elem.first(elem.size() - 1);
839 282 : hardened = true;
840 282 : apostrophe = last == '\'';
841 282 : }
842 412 : }
843 : uint32_t p;
844 412 : 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 410 : } else if (p > 0x7FFFFFFFUL) {
848 2 : error = strprintf("Key path value %u is out of range", p);
849 2 : return false;
850 : }
851 408 : out.push_back(p | (((uint32_t)hardened) << 31));
852 408 : }
853 141 : return true;
854 145 : }
855 :
856 : /** Parse a public key that excludes origin information. */
857 212 : 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 212 : bool permit_uncompressed = ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH;
862 212 : auto split = Split(sp, '/');
863 212 : std::string str(split[0].begin(), split[0].end());
864 212 : if (str.size() == 0) {
865 0 : error = "No key provided";
866 0 : return nullptr;
867 : }
868 212 : if (split.size() == 1) {
869 103 : if (IsHex(str)) {
870 58 : std::vector<unsigned char> data = ParseHex(str);
871 58 : CPubKey pubkey(data);
872 58 : if (pubkey.IsFullyValid()) {
873 58 : if (permit_uncompressed || pubkey.IsCompressed()) {
874 58 : 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 58 : }
883 45 : CKey key = DecodeSecret(str);
884 45 : if (key.IsValid()) {
885 26 : if (permit_uncompressed || key.IsCompressed()) {
886 26 : CPubKey pubkey = key.GetPubKey();
887 26 : out.keys.emplace(pubkey.GetID(), key);
888 26 : 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 45 : }
895 128 : CExtKey extkey = DecodeExtKey(str);
896 128 : CExtPubKey extpubkey = DecodeExtPubKey(str);
897 128 : if (!extkey.key.IsValid() && !extpubkey.pubkey.IsValid()) {
898 5 : error = strprintf("key '%s' is not valid", str);
899 5 : return nullptr;
900 : }
901 123 : KeyPath path;
902 123 : DeriveType type = DeriveType::NO;
903 123 : if (split.back() == Span{"*"}.first(1)) {
904 78 : split.pop_back();
905 78 : type = DeriveType::UNHARDENED;
906 123 : } else if (split.back() == Span{"*'"}.first(2) || split.back() == Span{"*h"}.first(2)) {
907 1 : apostrophe = split.back() == Span{"*'"}.first(2);
908 1 : split.pop_back();
909 1 : type = DeriveType::HARDENED;
910 1 : }
911 123 : if (!ParseKeyPath(split, path, apostrophe, error)) return nullptr;
912 119 : if (extkey.key.IsValid()) {
913 26 : extpubkey = extkey.Neuter();
914 26 : out.keys.emplace(extpubkey.pubkey.GetID(), extkey.key);
915 26 : }
916 119 : return std::make_unique<BIP32PubkeyProvider>(key_exp_index, extpubkey, std::move(path), type, apostrophe);
917 212 : }
918 :
919 : /** Parse a public key including origin information (if enabled). */
920 218 : 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 218 : auto origin_split = Split(sp, ']');
925 218 : if (origin_split.size() > 2) {
926 2 : error = "Multiple ']' characters found for a single pubkey";
927 2 : return nullptr;
928 : }
929 216 : bool apostrophe = false;
930 216 : if (origin_split.size() == 1) return ParsePubkeyInner(key_exp_index, origin_split[0], ctx, out, apostrophe, error);
931 26 : 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 24 : auto slash_split = Split(origin_split[0].subspan(1), '/');
937 24 : 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 22 : std::string fpr_hex = std::string(slash_split[0].begin(), slash_split[0].end());
942 22 : if (!IsHex(fpr_hex)) {
943 0 : error = strprintf("Fingerprint '%s' is not hex", fpr_hex);
944 0 : return nullptr;
945 : }
946 22 : auto fpr_bytes = ParseHex(fpr_hex);
947 22 : KeyOriginInfo info;
948 : static_assert(sizeof(info.fingerprint) == 4, "Fingerprint must be 4 bytes");
949 22 : assert(fpr_bytes.size() == 4);
950 22 : std::copy(fpr_bytes.begin(), fpr_bytes.end(), info.fingerprint);
951 22 : if (!ParseKeyPath(slash_split, info.path, apostrophe, error)) return nullptr;
952 22 : auto provider = ParsePubkeyInner(key_exp_index, origin_split[1], ctx, out, apostrophe, error);
953 22 : if (!provider) return nullptr;
954 22 : return std::make_unique<OriginPubkeyProvider>(key_exp_index, std::move(info), std::move(provider), apostrophe);
955 218 : }
956 :
957 : /** Parse a script in a particular context. */
958 201 : 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 201 : auto expr = Expr(sp);
963 201 : bool sorted_multi = false;
964 201 : if (Func("pk", expr)) {
965 8 : auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error);
966 8 : if (!pubkey) {
967 0 : error = strprintf("pk(): %s", error);
968 0 : return nullptr;
969 : }
970 8 : ++key_exp_index;
971 8 : return std::make_unique<PKDescriptor>(std::move(pubkey));
972 8 : }
973 193 : if (Func("pkh", expr)) {
974 97 : auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error);
975 97 : if (!pubkey) {
976 8 : error = strprintf("pkh(): %s", error);
977 8 : return nullptr;
978 : }
979 89 : ++key_exp_index;
980 89 : return std::make_unique<PKHDescriptor>(std::move(pubkey));
981 97 : }
982 168 : if (ctx == ParseScriptContext::TOP && Func("combo", expr)) {
983 23 : auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error);
984 23 : if (!pubkey) {
985 2 : error = strprintf("combo(): %s", error);
986 2 : return nullptr;
987 : }
988 21 : ++key_exp_index;
989 21 : return std::make_unique<ComboDescriptor>(std::move(pubkey));
990 96 : } else if (Func("combo", expr)) {
991 2 : error = "Can only have combo() at top level";
992 2 : return nullptr;
993 : }
994 71 : if ((sorted_multi = Func("sortedmulti", expr)) || Func("multi", expr)) {
995 34 : auto threshold = Expr(expr);
996 : uint32_t thres;
997 34 : std::vector<std::unique_ptr<PubkeyProvider>> providers;
998 34 : 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 32 : size_t script_size = 0;
1003 117 : while (expr.size()) {
1004 90 : if (!Const(",", expr)) {
1005 0 : error = strprintf("Multi: expected ',', got '%c'", expr[0]);
1006 0 : return nullptr;
1007 : }
1008 90 : auto arg = Expr(expr);
1009 90 : auto pk = ParsePubkey(key_exp_index, arg, ctx, out, error);
1010 90 : if (!pk) {
1011 5 : error = strprintf("Multi: %s", error);
1012 5 : return nullptr;
1013 : }
1014 85 : script_size += pk->GetSize() + 1;
1015 85 : providers.emplace_back(std::move(pk));
1016 85 : key_exp_index++;
1017 90 : }
1018 27 : 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 27 : } else if (thres < 1) {
1022 1 : error = strprintf("Multisig threshold cannot be %d, must be at least 1", thres);
1023 1 : return nullptr;
1024 26 : } 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 25 : if (ctx == ParseScriptContext::TOP) {
1029 9 : 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 8 : }
1034 24 : if (ctx == ParseScriptContext::P2SH) {
1035 : // This limits the maximum number of compressed pubkeys to 15.
1036 16 : 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 14 : }
1041 22 : return std::make_unique<MultisigDescriptor>(thres, std::move(providers), sorted_multi);
1042 34 : }
1043 70 : if (ctx == ParseScriptContext::TOP && Func("sh", expr)) {
1044 28 : auto desc = ParseScript(key_exp_index, expr, ParseScriptContext::P2SH, out, error);
1045 28 : if (!desc || expr.size()) return nullptr;
1046 18 : return std::make_unique<SHDescriptor>(std::move(desc));
1047 37 : } else if (Func("sh", expr)) {
1048 2 : error = "Can only have sh() at top level";
1049 2 : return nullptr;
1050 : }
1051 12 : if (ctx == ParseScriptContext::TOP && Func("addr", expr)) {
1052 1 : CTxDestination dest = DecodeDestination(std::string(expr.begin(), expr.end()));
1053 1 : if (!IsValidDestination(dest)) {
1054 1 : error = "Address is not valid";
1055 1 : return nullptr;
1056 : }
1057 0 : return std::make_unique<AddressDescriptor>(std::move(dest));
1058 6 : } else if (Func("addr", expr)) {
1059 0 : error = "Can only have addr() at top level";
1060 0 : return nullptr;
1061 : }
1062 10 : if (ctx == ParseScriptContext::TOP && Func("raw", expr)) {
1063 1 : std::string str(expr.begin(), expr.end());
1064 1 : if (!IsHex(str)) {
1065 1 : error = "Raw script is not hex";
1066 1 : return nullptr;
1067 : }
1068 0 : auto bytes = ParseHex(str);
1069 0 : return std::make_unique<RawDescriptor>(CScript(bytes.begin(), bytes.end()));
1070 6 : } else if (Func("raw", expr)) {
1071 0 : error = "Can only have raw() at top level";
1072 0 : return nullptr;
1073 : }
1074 5 : if (ctx == ParseScriptContext::P2SH) {
1075 2 : error = "A function is needed within P2SH";
1076 2 : return nullptr;
1077 : }
1078 3 : error = strprintf("'%s' is not a valid descriptor function", std::string(expr.begin(), expr.end()));
1079 3 : return nullptr;
1080 201 : }
1081 :
1082 562 : std::unique_ptr<PubkeyProvider> InferPubkey(const CPubKey& pubkey, ParseScriptContext, const SigningProvider& provider)
1083 : {
1084 562 : std::unique_ptr<PubkeyProvider> key_provider = std::make_unique<ConstPubkeyProvider>(0, pubkey);
1085 562 : KeyOriginInfo info;
1086 562 : if (provider.GetKeyOrigin(pubkey.GetID(), info)) {
1087 557 : return std::make_unique<OriginPubkeyProvider>(0, std::move(info), std::move(key_provider), /*apostrophe=*/false);
1088 : }
1089 5 : return key_provider;
1090 562 : }
1091 :
1092 586 : std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptContext ctx, const SigningProvider& provider)
1093 : {
1094 586 : std::vector<std::vector<unsigned char>> data;
1095 586 : TxoutType txntype = Solver(script, data);
1096 :
1097 586 : if (txntype == TxoutType::PUBKEY) {
1098 354 : CPubKey pubkey(data[0]);
1099 354 : if (pubkey.IsValid()) {
1100 354 : return std::make_unique<PKDescriptor>(InferPubkey(pubkey, ctx, provider));
1101 : }
1102 0 : }
1103 232 : if (txntype == TxoutType::PUBKEYHASH) {
1104 94 : uint160 hash(data[0]);
1105 94 : CKeyID keyid(hash);
1106 94 : CPubKey pubkey;
1107 94 : if (provider.GetPubKey(keyid, pubkey)) {
1108 81 : return std::make_unique<PKHDescriptor>(InferPubkey(pubkey, ctx, provider));
1109 : }
1110 13 : }
1111 151 : if (txntype == TxoutType::MULTISIG) {
1112 63 : std::vector<std::unique_ptr<PubkeyProvider>> providers;
1113 190 : for (size_t i = 1; i + 1 < data.size(); ++i) {
1114 127 : CPubKey pubkey(data[i]);
1115 127 : providers.push_back(InferPubkey(pubkey, ctx, provider));
1116 127 : }
1117 63 : return std::make_unique<MultisigDescriptor>((int)data[0][0], std::move(providers));
1118 63 : }
1119 88 : if (txntype == TxoutType::SCRIPTHASH && ctx == ParseScriptContext::TOP) {
1120 68 : uint160 hash(data[0]);
1121 68 : CScriptID scriptid(hash);
1122 68 : CScript subscript;
1123 68 : if (provider.GetCScript(scriptid, subscript)) {
1124 66 : auto sub = InferScript(subscript, ParseScriptContext::P2SH, provider);
1125 66 : if (sub) return std::make_unique<SHDescriptor>(std::move(sub));
1126 66 : }
1127 68 : }
1128 :
1129 22 : CTxDestination dest;
1130 22 : if (ExtractDestination(script, dest)) {
1131 15 : if (GetScriptForDestination(dest) == script) {
1132 15 : return std::make_unique<AddressDescriptor>(std::move(dest));
1133 : }
1134 0 : }
1135 :
1136 7 : return std::make_unique<RawDescriptor>(script);
1137 586 : }
1138 :
1139 :
1140 : } // namespace
1141 :
1142 : /** Check a descriptor checksum, and update desc to be the checksum-less part. */
1143 201 : bool CheckChecksum(Span<const char>& sp, bool require_checksum, std::string& error, std::string* out_checksum = nullptr)
1144 : {
1145 : using namespace spanparsing;
1146 :
1147 201 : auto check_split = Split(sp, '#');
1148 201 : if (check_split.size() > 2) {
1149 2 : error = "Multiple '#' symbols";
1150 2 : return false;
1151 : }
1152 199 : if (check_split.size() == 1 && require_checksum){
1153 1 : error = "Missing checksum";
1154 1 : return false;
1155 : }
1156 198 : if (check_split.size() == 2) {
1157 25 : 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 19 : }
1162 192 : auto checksum = DescriptorChecksum(check_split[0]);
1163 192 : if (checksum.empty()) {
1164 1 : error = "Invalid characters in payload";
1165 1 : return false;
1166 : }
1167 191 : if (check_split.size() == 2) {
1168 18 : if (!std::equal(checksum.begin(), checksum.end(), check_split[1].begin())) {
1169 6 : error = strprintf("Provided checksum '%s' does not match computed checksum '%s'", std::string(check_split[1].begin(), check_split[1].end()), checksum);
1170 6 : return false;
1171 : }
1172 12 : }
1173 185 : if (out_checksum) *out_checksum = std::move(checksum);
1174 185 : sp = check_split[0];
1175 185 : return true;
1176 201 : }
1177 :
1178 187 : std::unique_ptr<Descriptor> Parse(const std::string& descriptor, FlatSigningProvider& out, std::string& error, bool require_checksum)
1179 : {
1180 187 : Span<const char> sp{descriptor};
1181 187 : if (!CheckChecksum(sp, require_checksum, error)) return nullptr;
1182 173 : uint32_t key_exp_index = 0;
1183 173 : auto ret = ParseScript(key_exp_index, sp, ParseScriptContext::TOP, out, error);
1184 173 : if (sp.size() == 0 && ret) return std::unique_ptr<Descriptor>(std::move(ret));
1185 33 : return nullptr;
1186 187 : }
1187 :
1188 14 : std::string GetDescriptorChecksum(const std::string& descriptor)
1189 : {
1190 14 : std::string ret;
1191 14 : std::string error;
1192 14 : Span<const char> sp{descriptor};
1193 14 : if (!CheckChecksum(sp, false, error, &ret)) return "";
1194 12 : return ret;
1195 14 : }
1196 :
1197 520 : std::unique_ptr<Descriptor> InferDescriptor(const CScript& script, const SigningProvider& provider)
1198 : {
1199 520 : return InferScript(script, ParseScriptContext::TOP, provider);
1200 : }
1201 :
1202 88 : uint256 DescriptorID(const Descriptor& desc)
1203 : {
1204 88 : std::string desc_str = desc.ToString();
1205 88 : uint256 id;
1206 88 : CSHA256().Write((unsigned char*)desc_str.data(), desc_str.size()).Finalize(id.begin());
1207 : return id;
1208 88 : }
1209 :
1210 340 : void DescriptorCache::CacheParentExtPubKey(uint32_t key_exp_pos, const CExtPubKey& xpub)
1211 : {
1212 340 : m_parent_xpubs[key_exp_pos] = xpub;
1213 340 : }
1214 :
1215 3000 : void DescriptorCache::CacheDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index, const CExtPubKey& xpub)
1216 : {
1217 3000 : auto& xpubs = m_derived_xpubs[key_exp_pos];
1218 3000 : xpubs[der_index] = xpub;
1219 3000 : }
1220 :
1221 240 : void DescriptorCache::CacheLastHardenedExtPubKey(uint32_t key_exp_pos, const CExtPubKey& xpub)
1222 : {
1223 240 : m_last_hardened_xpubs[key_exp_pos] = xpub;
1224 240 : }
1225 :
1226 83438 : bool DescriptorCache::GetCachedParentExtPubKey(uint32_t key_exp_pos, CExtPubKey& xpub) const
1227 : {
1228 83438 : const auto& it = m_parent_xpubs.find(key_exp_pos);
1229 83438 : if (it == m_parent_xpubs.end()) return false;
1230 83300 : xpub = it->second;
1231 83300 : return true;
1232 83438 : }
1233 :
1234 85370 : bool DescriptorCache::GetCachedDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index, CExtPubKey& xpub) const
1235 : {
1236 85370 : const auto& key_exp_it = m_derived_xpubs.find(key_exp_pos);
1237 85370 : if (key_exp_it == m_derived_xpubs.end()) return false;
1238 2000 : const auto& der_it = key_exp_it->second.find(der_index);
1239 2000 : if (der_it == key_exp_it->second.end()) return false;
1240 2 : xpub = der_it->second;
1241 2 : return true;
1242 85370 : }
1243 :
1244 70 : bool DescriptorCache::GetCachedLastHardenedExtPubKey(uint32_t key_exp_pos, CExtPubKey& xpub) const
1245 : {
1246 70 : const auto& it = m_last_hardened_xpubs.find(key_exp_pos);
1247 70 : if (it == m_last_hardened_xpubs.end()) return false;
1248 0 : xpub = it->second;
1249 0 : return true;
1250 70 : }
1251 :
1252 72552 : DescriptorCache DescriptorCache::MergeAndDiff(const DescriptorCache& other)
1253 : {
1254 72552 : DescriptorCache diff;
1255 72622 : for (const auto& parent_xpub_pair : other.GetCachedParentExtPubKeys()) {
1256 70 : CExtPubKey xpub;
1257 70 : if (GetCachedParentExtPubKey(parent_xpub_pair.first, xpub)) {
1258 0 : 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 0 : continue;
1262 : }
1263 70 : CacheParentExtPubKey(parent_xpub_pair.first, parent_xpub_pair.second);
1264 70 : diff.CacheParentExtPubKey(parent_xpub_pair.first, parent_xpub_pair.second);
1265 : }
1266 73552 : for (const auto& derived_xpub_map_pair : other.GetCachedDerivedExtPubKeys()) {
1267 2000 : for (const auto& derived_xpub_pair : derived_xpub_map_pair.second) {
1268 1000 : CExtPubKey xpub;
1269 1000 : 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 1000 : CacheDerivedExtPubKey(derived_xpub_map_pair.first, derived_xpub_pair.first, derived_xpub_pair.second);
1276 1000 : diff.CacheDerivedExtPubKey(derived_xpub_map_pair.first, derived_xpub_pair.first, derived_xpub_pair.second);
1277 : }
1278 : }
1279 72622 : for (const auto& lh_xpub_pair : other.GetCachedLastHardenedExtPubKeys()) {
1280 70 : CExtPubKey xpub;
1281 70 : 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 70 : CacheLastHardenedExtPubKey(lh_xpub_pair.first, lh_xpub_pair.second);
1288 70 : diff.CacheLastHardenedExtPubKey(lh_xpub_pair.first, lh_xpub_pair.second);
1289 : }
1290 72552 : return diff;
1291 72552 : }
1292 :
1293 145258 : ExtPubKeyMap DescriptorCache::GetCachedParentExtPubKeys() const
1294 : {
1295 145258 : return m_parent_xpubs;
1296 : }
1297 :
1298 145258 : std::unordered_map<uint32_t, ExtPubKeyMap> DescriptorCache::GetCachedDerivedExtPubKeys() const
1299 : {
1300 145258 : return m_derived_xpubs;
1301 : }
1302 :
1303 145108 : ExtPubKeyMap DescriptorCache::GetCachedLastHardenedExtPubKeys() const
1304 : {
1305 145108 : return m_last_hardened_xpubs;
1306 : }
|
