Line data Source code
1 : // Copyright (c) 2018-2020 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/system.h>
16 : #include <util/strencodings.h>
17 : #include <util/vector.h>
18 :
19 : #include <memory>
20 : #include <string>
21 : #include <vector>
22 :
23 : namespace {
24 :
25 : ////////////////////////////////////////////////////////////////////////////
26 : // Checksum //
27 : ////////////////////////////////////////////////////////////////////////////
28 :
29 : // This section implements a checksum algorithm for descriptors with the
30 : // following properties:
31 : // * Mistakes in a descriptor string are measured in "symbol errors". The higher
32 : // the number of symbol errors, the harder it is to detect:
33 : // * An error substituting a character from 0123456789()[],'/*abcdefgh@:$%{} for
34 : // another in that set always counts as 1 symbol error.
35 : // * Note that hex encoded keys are covered by these characters. Xprvs and
36 : // xpubs use other characters too, but already have their own checksum
37 : // mechanism.
38 : // * Function names like "multi()" use other characters, but mistakes in
39 : // these would generally result in an unparsable descriptor.
40 : // * A case error always counts as 1 symbol error.
41 : // * Any other 1 character substitution error counts as 1 or 2 symbol errors.
42 : // * Any 1 symbol error is always detected.
43 : // * Any 2 or 3 symbol error in a descriptor of up to 49154 characters is always detected.
44 : // * Any 4 symbol error in a descriptor of up to 507 characters is always detected.
45 : // * Any 5 symbol error in a descriptor of up to 77 characters is always detected.
46 : // * Is optimized to minimize the chance a 5 symbol error in a descriptor up to 387 characters is undetected
47 : // * Random errors have a chance of 1 in 2**40 of being undetected.
48 : //
49 : // These properties are achieved by expanding every group of 3 (non checksum) characters into
50 : // 4 GF(32) symbols, over which a cyclic code is defined.
51 :
52 : /*
53 : * Interprets c as 8 groups of 5 bits which are the coefficients of a degree 8 polynomial over GF(32),
54 : * multiplies that polynomial by x, computes its remainder modulo a generator, and adds the constant term val.
55 : *
56 : * 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}.
57 : * It is chosen to define an cyclic error detecting code which is selected by:
58 : * - Starting from all BCH codes over GF(32) of degree 8 and below, which by construction guarantee detecting
59 : * 3 errors in windows up to 19000 symbols.
60 : * - Taking all those generators, and for degree 7 ones, extend them to degree 8 by adding all degree-1 factors.
61 : * - Selecting just the set of generators that guarantee detecting 4 errors in a window of length 512.
62 : * - Selecting one of those with best worst-case behavior for 5 errors in windows of length up to 512.
63 : *
64 : * The generator and the constants to implement it can be verified using this Sage code:
65 : * B = GF(2) # Binary field
66 : * BP.<b> = B[] # Polynomials over the binary field
67 : * F_mod = b**5 + b**3 + 1
68 : * F.<f> = GF(32, modulus=F_mod, repr='int') # GF(32) definition
69 : * FP.<x> = F[] # Polynomials over GF(32)
70 : * E_mod = x**3 + x + F.fetch_int(8)
71 : * E.<e> = F.extension(E_mod) # Extension field definition
72 : * alpha = e**2743 # Choice of an element in extension field
73 : * for p in divisors(E.order() - 1): # Verify alpha has order 32767.
74 : * assert((alpha**p == 1) == (p % 32767 == 0))
75 : * G = lcm([(alpha**i).minpoly() for i in [1056,1057,1058]] + [x + 1])
76 : * print(G) # Print out the generator
77 : * for i in [1,2,4,8,16]: # Print out {1,2,4,8,16}*(G mod x^8), packed in hex integers.
78 : * v = 0
79 : * for coef in reversed((F.fetch_int(i)*(G % x**8)).coefficients(sparse=True)):
80 : * v = v*32 + coef.integer_representation()
81 : * print("0x%x" % v)
82 : */
83 18025501 : uint64_t PolyMod(uint64_t c, int val)
84 : {
85 18025501 : uint8_t c0 = c >> 35;
86 18025501 : c = ((c & 0x7ffffffff) << 5) ^ val;
87 18025501 : if (c0 & 1) c ^= 0xf5dee51989;
88 18025501 : if (c0 & 2) c ^= 0xa9fdca3312;
89 18025501 : if (c0 & 4) c ^= 0x1bab10e32d;
90 18025501 : if (c0 & 8) c ^= 0x3706b1677a;
91 18025501 : if (c0 & 16) c ^= 0x644d626ffd;
92 18025501 : return c;
93 : }
94 :
95 129143 : std::string DescriptorChecksum(const Span<const char>& span)
96 : {
97 : /** A character set designed such that:
98 : * - The most common 'unprotected' descriptor characters (hex, keypaths) are in the first group of 32.
99 : * - Case errors cause an offset that's a multiple of 32.
100 : * - As many alphabetic characters are in the same group (while following the above restrictions).
101 : *
102 : * If p(x) gives the position of a character c in this character set, every group of 3 characters
103 : * (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).
104 : * This means that changes that only affect the lower 5 bits of the position, or only the higher 2 bits, will just
105 : * affect a single symbol.
106 : *
107 : * As a result, within-group-of-32 errors count as 1 symbol, as do cross-group errors that don't affect
108 : * the position within the groups.
109 : */
110 129282 : static std::string INPUT_CHARSET =
111 139 : "0123456789()[],'/*abcdefgh@:$%{}"
112 : "IJKLMNOPQRSTUVWXYZ&+-.;<=>?!^_|~"
113 : "ijklmnopqrstuvwxyzABCDEFGH`#\"\\ ";
114 :
115 : /** The character set for the checksum itself (same as bech32). */
116 129143 : static std::string CHECKSUM_CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l";
117 :
118 12972052 : uint64_t c = 1;
119 12972052 : int cls = 0;
120 12972052 : int clscount = 0;
121 12842909 : for (auto ch : span) {
122 12713767 : auto pos = INPUT_CHARSET.find(ch);
123 12713767 : if (pos == std::string::npos) return "";
124 12713766 : c = PolyMod(c, pos & 31); // Emit a symbol for the position inside the group, for every character.
125 12713766 : cls = cls * 3 + (pos >> 5); // Accumulate the group numbers
126 12713766 : if (++clscount == 3) {
127 : // Emit an extra symbol representing the group numbers, for every 3 characters.
128 4195656 : c = PolyMod(c, cls);
129 : cls = 0;
130 : clscount = 0;
131 4195656 : }
132 25427532 : }
133 129142 : if (clscount > 0) c = PolyMod(c, cls);
134 1162278 : for (int j = 0; j < 8; ++j) c = PolyMod(c, 0); // Shift further to determine the checksum.
135 129142 : c ^= 1; // Prevent appending zeroes from not affecting the checksum.
136 :
137 129142 : std::string ret(8, ' ');
138 1162278 : for (int j = 0; j < 8; ++j) ret[j] = CHECKSUM_CHARSET[(c >> (5 * (7 - j))) & 31];
139 129142 : return ret;
140 129143 : }
141 :
142 127691 : std::string AddChecksum(const std::string& str) { return str + "#" + DescriptorChecksum(str); }
143 :
144 : ////////////////////////////////////////////////////////////////////////////
145 : // Internal representation //
146 : ////////////////////////////////////////////////////////////////////////////
147 :
148 : typedef std::vector<uint32_t> KeyPath;
149 :
150 : /** Interface for public key objects in descriptors. */
151 : struct PubkeyProvider
152 : {
153 : protected:
154 : //! Index of this key expression in the descriptor
155 : //! E.g. If this PubkeyProvider is key1 in multi(2, key1, key2, key3), then m_expr_index = 0
156 : uint32_t m_expr_index;
157 :
158 : public:
159 374262 : PubkeyProvider(uint32_t exp_index) : m_expr_index(exp_index) {}
160 :
161 374262 : virtual ~PubkeyProvider() = default;
162 :
163 : /** Derive a public key.
164 : * read_cache is the cache to read keys from (if not nullptr)
165 : * write_cache is the cache to write keys to (if not nullptr)
166 : * Caches are not exclusive but this is not tested. Currently we use them exclusively
167 : */
168 : virtual bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) = 0;
169 :
170 : /** Whether this represent multiple public keys at different positions. */
171 : virtual bool IsRange() const = 0;
172 :
173 : /** Get the size of the generated public key(s) in bytes (33 or 65). */
174 : virtual size_t GetSize() const = 0;
175 :
176 : /** Get the descriptor string form. */
177 : virtual std::string ToString() const = 0;
178 :
179 : /** Get the descriptor string form including private data (if available in arg). */
180 : virtual bool ToPrivateString(const SigningProvider& arg, std::string& out) const = 0;
181 :
182 : /** Derive a private key, if private data is available in arg. */
183 : virtual bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const = 0;
184 : };
185 :
186 559167 : class OriginPubkeyProvider final : public PubkeyProvider
187 : {
188 : KeyOriginInfo m_origin;
189 : std::unique_ptr<PubkeyProvider> m_provider;
190 :
191 104153 : std::string OriginString() const
192 : {
193 104153 : return HexStr(m_origin.fingerprint) + FormatHDKeypath(m_origin.path);
194 0 : }
195 :
196 : public:
197 372778 : OriginPubkeyProvider(uint32_t exp_index, KeyOriginInfo info, std::unique_ptr<PubkeyProvider> provider) : PubkeyProvider(exp_index), m_origin(std::move(info)), m_provider(std::move(provider)) {}
198 103567 : bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) override
199 : {
200 103567 : if (!m_provider->GetPubKey(pos, arg, key, info, read_cache, write_cache)) return false;
201 103560 : std::copy(std::begin(m_origin.fingerprint), std::end(m_origin.fingerprint), info.fingerprint);
202 103560 : info.path.insert(info.path.begin(), m_origin.path.begin(), m_origin.path.end());
203 103560 : return true;
204 103567 : }
205 606 : bool IsRange() const override { return m_provider->IsRange(); }
206 300 : size_t GetSize() const override { return m_provider->GetSize(); }
207 104111 : std::string ToString() const override { return "[" + OriginString() + "]" + m_provider->ToString(); }
208 84 : bool ToPrivateString(const SigningProvider& arg, std::string& ret) const override
209 : {
210 84 : std::string sub;
211 84 : if (!m_provider->ToPrivateString(arg, sub)) return false;
212 42 : ret = "[" + OriginString() + "]" + std::move(sub);
213 42 : return true;
214 84 : }
215 69 : bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const override
216 : {
217 69 : return m_provider->GetPrivKey(pos, arg, key);
218 : }
219 : };
220 :
221 : /** An object representing a parsed constant public key in a descriptor. */
222 561912 : class ConstPubkeyProvider final : public PubkeyProvider
223 : {
224 : CPubKey m_pubkey;
225 :
226 : public:
227 374608 : ConstPubkeyProvider(uint32_t exp_index, const CPubKey& pubkey) : PubkeyProvider(exp_index), m_pubkey(pubkey) {}
228 104758 : bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) override
229 : {
230 104758 : key = m_pubkey;
231 104758 : info.path.clear();
232 104758 : CKeyID keyid = m_pubkey.GetID();
233 104758 : std::copy(keyid.begin(), keyid.begin() + sizeof(info.fingerprint), info.fingerprint);
234 104758 : return true;
235 104758 : }
236 3361 : bool IsRange() const override { return false; }
237 795 : size_t GetSize() const override { return m_pubkey.size(); }
238 113400 : std::string ToString() const override { return HexStr(m_pubkey); }
239 120 : bool ToPrivateString(const SigningProvider& arg, std::string& ret) const override
240 : {
241 120 : CKey key;
242 120 : if (!arg.GetKey(m_pubkey.GetID(), key)) return false;
243 78 : ret = EncodeSecret(key);
244 78 : return true;
245 120 : }
246 622 : bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const override
247 : {
248 622 : return arg.GetKey(m_pubkey.GetID(), key);
249 : }
250 : };
251 :
252 : enum class DeriveType {
253 : NO,
254 : UNHARDENED,
255 : HARDENED,
256 : };
257 :
258 : /** An object representing a parsed extended public key in a descriptor. */
259 1707 : class BIP32PubkeyProvider final : public PubkeyProvider
260 : {
261 : // Root xpub, path, and final derivation step type being used, if any
262 : CExtPubKey m_root_extkey;
263 : KeyPath m_path;
264 : DeriveType m_derive;
265 : // Cache of the parent of the final derived pubkeys.
266 : // Primarily useful for situations when no read_cache is provided
267 : CExtPubKey m_cached_xpub;
268 :
269 7820 : bool GetExtKey(const SigningProvider& arg, CExtKey& ret) const
270 : {
271 7820 : CKey key;
272 7820 : if (!arg.GetKey(m_root_extkey.pubkey.GetID(), key)) return false;
273 7493 : ret.nDepth = m_root_extkey.nDepth;
274 7493 : std::copy(m_root_extkey.vchFingerprint, m_root_extkey.vchFingerprint + sizeof(ret.vchFingerprint), ret.vchFingerprint);
275 7493 : ret.nChild = m_root_extkey.nChild;
276 7493 : ret.chaincode = m_root_extkey.chaincode;
277 7493 : ret.key = key;
278 7493 : return true;
279 7820 : }
280 :
281 : // Derives the last xprv
282 7650 : bool GetDerivedExtKey(const SigningProvider& arg, CExtKey& xprv) const
283 : {
284 7650 : if (!GetExtKey(arg, xprv)) return false;
285 22652 : for (auto entry : m_path) {
286 15265 : xprv.Derive(xprv, entry);
287 : }
288 7387 : return true;
289 7650 : }
290 :
291 7354 : bool IsHardened() const
292 : {
293 7354 : if (m_derive == DeriveType::HARDENED) return true;
294 764 : for (auto entry : m_path) {
295 392 : if (entry >> 31) return true;
296 147 : }
297 127 : return false;
298 7354 : }
299 :
300 : public:
301 1138 : BIP32PubkeyProvider(uint32_t exp_index, const CExtPubKey& extkey, KeyPath path, DeriveType derive) : PubkeyProvider(exp_index), m_root_extkey(extkey), m_path(std::move(path)), m_derive(derive) {}
302 25892 : bool IsRange() const override { return m_derive != DeriveType::NO; }
303 114 : size_t GetSize() const override { return 33; }
304 68002 : bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key_out, KeyOriginInfo& final_info_out, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) override
305 : {
306 : // Info of parent of the to be derived pubkey
307 68002 : KeyOriginInfo parent_info;
308 68002 : CKeyID keyid = m_root_extkey.pubkey.GetID();
309 68002 : std::copy(keyid.begin(), keyid.begin() + sizeof(parent_info.fingerprint), parent_info.fingerprint);
310 68002 : parent_info.path = m_path;
311 :
312 : // Info of the derived key itself which is copied out upon successful completion
313 68002 : KeyOriginInfo final_info_out_tmp = parent_info;
314 68002 : if (m_derive == DeriveType::UNHARDENED) final_info_out_tmp.path.push_back((uint32_t)pos);
315 68002 : if (m_derive == DeriveType::HARDENED) final_info_out_tmp.path.push_back(((uint32_t)pos) | 0x80000000L);
316 :
317 : // Derive keys or fetch them from cache
318 68002 : CExtPubKey final_extkey = m_root_extkey;
319 68002 : CExtPubKey parent_extkey = m_root_extkey;
320 : bool der = true;
321 68002 : if (read_cache) {
322 48194 : if (!read_cache->GetCachedDerivedExtPubKey(m_expr_index, pos, final_extkey)) {
323 48018 : if (m_derive == DeriveType::HARDENED) return false;
324 : // Try to get the derivation parent
325 47090 : if (!read_cache->GetCachedParentExtPubKey(m_expr_index, parent_extkey)) return false;
326 46873 : final_extkey = parent_extkey;
327 46873 : if (m_derive == DeriveType::UNHARDENED) der = parent_extkey.Derive(final_extkey, pos);
328 : }
329 19808 : } else if (m_cached_xpub.pubkey.IsValid() && m_derive != DeriveType::HARDENED) {
330 12454 : parent_extkey = final_extkey = m_cached_xpub;
331 12454 : if (m_derive == DeriveType::UNHARDENED) der = parent_extkey.Derive(final_extkey, pos);
332 7354 : } else if (IsHardened()) {
333 7227 : CExtKey xprv;
334 7227 : if (!GetDerivedExtKey(arg, xprv)) return false;
335 7016 : parent_extkey = xprv.Neuter();
336 7016 : if (m_derive == DeriveType::UNHARDENED) der = xprv.Derive(xprv, pos);
337 7016 : if (m_derive == DeriveType::HARDENED) der = xprv.Derive(xprv, pos | 0x80000000UL);
338 7016 : final_extkey = xprv.Neuter();
339 7227 : } else {
340 268 : for (auto entry : m_path) {
341 141 : der = parent_extkey.Derive(parent_extkey, entry);
342 141 : assert(der);
343 : }
344 127 : final_extkey = parent_extkey;
345 127 : if (m_derive == DeriveType::UNHARDENED) der = parent_extkey.Derive(final_extkey, pos);
346 127 : assert(m_derive != DeriveType::HARDENED);
347 : }
348 66646 : assert(der);
349 :
350 66646 : final_info_out = final_info_out_tmp;
351 66646 : key_out = final_extkey.pubkey;
352 :
353 : // We rely on the consumer to check that m_derive isn't HARDENED as above
354 : // But we can't have already cached something in case we read something from the cache
355 : // and parent_extkey isn't actually the parent.
356 66646 : if (!m_cached_xpub.pubkey.IsValid()) m_cached_xpub = parent_extkey;
357 :
358 66646 : if (write_cache) {
359 : // Only cache parent if there is any unhardened derivation
360 1264 : if (m_derive != DeriveType::HARDENED) {
361 501 : write_cache->CacheParentExtPubKey(m_expr_index, parent_extkey);
362 763 : } else if (final_info_out.path.size() > 0) {
363 763 : write_cache->CacheDerivedExtPubKey(m_expr_index, pos, final_extkey);
364 : }
365 : }
366 :
367 66646 : return true;
368 68002 : }
369 18402 : std::string ToString() const override
370 : {
371 18402 : std::string ret = EncodeExtPubKey(m_root_extkey) + FormatHDKeypath(m_path);
372 18402 : if (IsRange()) {
373 18330 : ret += "/*";
374 18330 : if (m_derive == DeriveType::HARDENED) ret += '\'';
375 : }
376 : return ret;
377 18402 : }
378 170 : bool ToPrivateString(const SigningProvider& arg, std::string& out) const override
379 : {
380 170 : CExtKey key;
381 170 : if (!GetExtKey(arg, key)) return false;
382 106 : out = EncodeExtKey(key) + FormatHDKeypath(m_path);
383 106 : if (IsRange()) {
384 38 : out += "/*";
385 38 : if (m_derive == DeriveType::HARDENED) out += '\'';
386 : }
387 106 : return true;
388 170 : }
389 423 : bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const override
390 : {
391 423 : CExtKey extkey;
392 423 : if (!GetDerivedExtKey(arg, extkey)) return false;
393 371 : if (m_derive == DeriveType::UNHARDENED) extkey.Derive(extkey, pos);
394 371 : if (m_derive == DeriveType::HARDENED) extkey.Derive(extkey, pos | 0x80000000UL);
395 371 : key = extkey.key;
396 371 : return true;
397 423 : }
398 : };
399 :
400 : /** Base class for all Descriptor implementations. */
401 315668 : class DescriptorImpl : public Descriptor
402 : {
403 : //! Public key arguments for this descriptor (size 1 for PK, PKH, WPKH; any size for Multisig).
404 : const std::vector<std::unique_ptr<PubkeyProvider>> m_pubkey_args;
405 : //! The string name of the descriptor function.
406 : const std::string m_name;
407 :
408 : protected:
409 : //! The sub-descriptor argument (nullptr for everything but SH and WSH).
410 : //! In doc/descriptors.m this is referred to as SCRIPT expressions sh(SCRIPT)
411 : //! and wsh(SCRIPT), and distinct from KEY expressions and ADDR expressions.
412 : const std::unique_ptr<DescriptorImpl> m_subdescriptor_arg;
413 :
414 : //! Return a serialization of anything except pubkey and script arguments, to be prepended to those.
415 149533 : virtual std::string ToStringExtra() const { return ""; }
416 :
417 : /** A helper function to construct the scripts for this descriptor.
418 : *
419 : * This function is invoked once for every CScript produced by evaluating
420 : * m_subdescriptor_arg, or just once in case m_subdescriptor_arg is nullptr.
421 :
422 : * @param pubkeys The evaluations of the m_pubkey_args field.
423 : * @param script The evaluation of m_subdescriptor_arg (or nullptr when m_subdescriptor_arg is nullptr).
424 : * @param out A FlatSigningProvider to put scripts or public keys in that are necessary to the solver.
425 : * The script arguments to this function are automatically added, as is the origin info of the provided pubkeys.
426 : * @return A vector with scriptPubKeys for this descriptor.
427 : */
428 : virtual std::vector<CScript> MakeScripts(const std::vector<CPubKey>& pubkeys, const CScript* script, FlatSigningProvider& out) const = 0;
429 :
430 : public:
431 315668 : 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_arg(std::move(script)) {}
432 :
433 1173 : bool IsSolvable() const override
434 : {
435 1173 : if (m_subdescriptor_arg) {
436 480 : if (!m_subdescriptor_arg->IsSolvable()) return false;
437 : }
438 1173 : return true;
439 1173 : }
440 :
441 11290 : bool IsRange() const final
442 : {
443 22035 : for (const auto& pubkey : m_pubkey_args) {
444 10745 : if (pubkey->IsRange()) return true;
445 3476 : }
446 4021 : if (m_subdescriptor_arg) {
447 1369 : if (m_subdescriptor_arg->IsRange()) return true;
448 : }
449 3295 : return false;
450 11290 : }
451 :
452 152188 : bool ToStringHelper(const SigningProvider* arg, std::string& out, bool priv) const
453 : {
454 152188 : std::string extra = ToStringExtra();
455 152188 : size_t pos = extra.size() > 0 ? 1 : 0;
456 152188 : std::string ret = m_name + "(" + extra;
457 284280 : for (const auto& pubkey : m_pubkey_args) {
458 132092 : if (pos++) ret += ",";
459 132092 : std::string tmp;
460 132092 : if (priv) {
461 290 : if (!pubkey->ToPrivateString(*arg, tmp)) return false;
462 : } else {
463 131802 : tmp = pubkey->ToString();
464 : }
465 131986 : ret += std::move(tmp);
466 132092 : }
467 152082 : if (m_subdescriptor_arg) {
468 24497 : if (pos++) ret += ",";
469 24497 : std::string tmp;
470 24497 : if (!m_subdescriptor_arg->ToStringHelper(arg, tmp, priv)) return false;
471 24435 : ret += std::move(tmp);
472 24497 : }
473 152020 : out = std::move(ret) + ")";
474 152020 : return true;
475 152188 : }
476 :
477 127479 : std::string ToString() const final
478 : {
479 127479 : std::string ret;
480 127479 : ToStringHelper(nullptr, ret, false);
481 127479 : return AddChecksum(ret);
482 127479 : }
483 :
484 212 : bool ToPrivateString(const SigningProvider& arg, std::string& out) const final
485 : {
486 212 : bool ret = ToStringHelper(&arg, out, true);
487 212 : out = AddChecksum(out);
488 212 : return ret;
489 : }
490 :
491 274161 : bool ExpandHelper(int pos, const SigningProvider& arg, const DescriptorCache* read_cache, std::vector<CScript>& output_scripts, FlatSigningProvider& out, DescriptorCache* write_cache) const
492 : {
493 274161 : std::vector<std::pair<CPubKey, KeyOriginInfo>> entries;
494 274161 : entries.reserve(m_pubkey_args.size());
495 :
496 : // Construct temporary data in `entries` and `subscripts`, to avoid producing output in case of failure.
497 446921 : for (const auto& p : m_pubkey_args) {
498 172760 : entries.emplace_back();
499 172760 : if (!p->GetPubKey(pos, arg, entries.back().first, entries.back().second, read_cache, write_cache)) return false;
500 171404 : }
501 272805 : std::vector<CScript> subscripts;
502 272805 : if (m_subdescriptor_arg) {
503 18052 : FlatSigningProvider subprovider;
504 18052 : if (!m_subdescriptor_arg->ExpandHelper(pos, arg, read_cache, subscripts, subprovider, write_cache)) return false;
505 17774 : out = Merge(out, subprovider);
506 18052 : }
507 :
508 272527 : std::vector<CPubKey> pubkeys;
509 272527 : pubkeys.reserve(entries.size());
510 443931 : for (auto& entry : entries) {
511 171404 : pubkeys.push_back(entry.first);
512 171404 : out.origins.emplace(entry.first.GetID(), std::make_pair<CPubKey, KeyOriginInfo>(CPubKey(entry.first), std::move(entry.second)));
513 : }
514 272527 : if (m_subdescriptor_arg) {
515 35548 : for (const auto& subscript : subscripts) {
516 17774 : out.scripts.emplace(CScriptID(subscript), subscript);
517 17774 : std::vector<CScript> addscripts = MakeScripts(pubkeys, &subscript, out);
518 35548 : for (auto& addscript : addscripts) {
519 17774 : output_scripts.push_back(std::move(addscript));
520 : }
521 17774 : }
522 17774 : } else {
523 254753 : output_scripts = MakeScripts(pubkeys, nullptr, out);
524 : }
525 : return true;
526 274161 : }
527 :
528 207426 : bool Expand(int pos, const SigningProvider& provider, std::vector<CScript>& output_scripts, FlatSigningProvider& out, DescriptorCache* write_cache = nullptr) const final
529 : {
530 207426 : return ExpandHelper(pos, provider, nullptr, output_scripts, out, write_cache);
531 : }
532 :
533 48683 : bool ExpandFromCache(int pos, const DescriptorCache& read_cache, std::vector<CScript>& output_scripts, FlatSigningProvider& out) const final
534 : {
535 48683 : return ExpandHelper(pos, DUMMY_SIGNING_PROVIDER, &read_cache, output_scripts, out, nullptr);
536 : }
537 :
538 1006 : void ExpandPrivate(int pos, const SigningProvider& provider, FlatSigningProvider& out) const final
539 : {
540 2051 : for (const auto& p : m_pubkey_args) {
541 1045 : CKey key;
542 1045 : if (!p->GetPrivKey(pos, provider, key)) continue;
543 852 : out.keys.emplace(key.GetPubKey().GetID(), key);
544 1045 : }
545 1006 : if (m_subdescriptor_arg) {
546 66 : FlatSigningProvider subprovider;
547 66 : m_subdescriptor_arg->ExpandPrivate(pos, provider, subprovider);
548 66 : out = Merge(out, subprovider);
549 66 : }
550 1006 : }
551 :
552 49 : Optional<OutputType> GetOutputType() const override { return nullopt; }
553 : };
554 :
555 : /** A parsed addr(A) descriptor. */
556 76245 : class AddressDescriptor final : public DescriptorImpl
557 : {
558 : const CTxDestination m_destination;
559 : protected:
560 5 : std::string ToStringExtra() const override { return EncodeDestination(m_destination); }
561 25410 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, const CScript*, FlatSigningProvider&) const override { return Vector(GetScriptForDestination(m_destination)); }
562 : public:
563 50830 : AddressDescriptor(CTxDestination destination) : DescriptorImpl({}, {}, "addr"), m_destination(std::move(destination)) {}
564 0 : bool IsSolvable() const final { return false; }
565 :
566 0 : Optional<OutputType> GetOutputType() const override
567 : {
568 0 : switch (m_destination.which()) {
569 : case 1 /* PKHash */:
570 0 : case 2 /* ScriptHash */: return OutputType::LEGACY;
571 : case 3 /* WitnessV0ScriptHash */:
572 : case 4 /* WitnessV0KeyHash */:
573 0 : case 5 /* WitnessUnknown */: return OutputType::BECH32;
574 : case 0 /* CNoDestination */:
575 0 : default: return nullopt;
576 : }
577 0 : }
578 0 : bool IsSingleType() const final { return true; }
579 : };
580 :
581 : /** A parsed raw(H) descriptor. */
582 242082 : class RawDescriptor final : public DescriptorImpl
583 : {
584 : const CScript m_script;
585 : protected:
586 0 : std::string ToStringExtra() const override { return HexStr(m_script); }
587 80694 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, const CScript*, FlatSigningProvider&) const override { return Vector(m_script); }
588 : public:
589 161388 : RawDescriptor(CScript script) : DescriptorImpl({}, {}, "raw"), m_script(std::move(script)) {}
590 0 : bool IsSolvable() const final { return false; }
591 :
592 0 : Optional<OutputType> GetOutputType() const override
593 : {
594 0 : CTxDestination dest;
595 0 : ExtractDestination(m_script, dest);
596 0 : switch (dest.which()) {
597 : case 1 /* PKHash */:
598 0 : case 2 /* ScriptHash */: return OutputType::LEGACY;
599 : case 3 /* WitnessV0ScriptHash */:
600 : case 4 /* WitnessV0KeyHash */:
601 0 : case 5 /* WitnessUnknown */: return OutputType::BECH32;
602 : case 0 /* CNoDestination */:
603 0 : default: return nullopt;
604 : }
605 0 : }
606 0 : bool IsSingleType() const final { return true; }
607 : };
608 :
609 : /** A parsed pk(P) descriptor. */
610 58281 : class PKDescriptor final : public DescriptorImpl
611 : {
612 : protected:
613 1071 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, const CScript*, FlatSigningProvider&) const override { return Vector(GetScriptForRawPubKey(keys[0])); }
614 : public:
615 38854 : PKDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), {}, "pk") {}
616 1 : bool IsSingleType() const final { return true; }
617 : };
618 :
619 : /** A parsed pkh(P) descriptor. */
620 232479 : class PKHDescriptor final : public DescriptorImpl
621 : {
622 : protected:
623 43058 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, const CScript*, FlatSigningProvider& out) const override
624 : {
625 43058 : CKeyID id = keys[0].GetID();
626 43058 : out.pubkeys.emplace(id, keys[0]);
627 43058 : return Vector(GetScriptForDestination(PKHash(id)));
628 43058 : }
629 : public:
630 154986 : PKHDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), {}, "pkh") {}
631 276 : Optional<OutputType> GetOutputType() const override { return OutputType::LEGACY; }
632 1385 : bool IsSingleType() const final { return true; }
633 : };
634 :
635 : /** A parsed wpkh(P) descriptor. */
636 253389 : class WPKHDescriptor final : public DescriptorImpl
637 : {
638 : protected:
639 53770 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, const CScript*, FlatSigningProvider& out) const override
640 : {
641 53770 : CKeyID id = keys[0].GetID();
642 53770 : out.pubkeys.emplace(id, keys[0]);
643 53770 : return Vector(GetScriptForDestination(WitnessV0KeyHash(id)));
644 53770 : }
645 : public:
646 168926 : WPKHDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), {}, "wpkh") {}
647 2685 : Optional<OutputType> GetOutputType() const override { return OutputType::BECH32; }
648 2414 : bool IsSingleType() const final { return true; }
649 : };
650 :
651 : /** A parsed combo(P) descriptor. */
652 318 : class ComboDescriptor final : public DescriptorImpl
653 : {
654 : protected:
655 38429 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, const CScript*, FlatSigningProvider& out) const override
656 : {
657 38429 : std::vector<CScript> ret;
658 38429 : CKeyID id = keys[0].GetID();
659 38429 : out.pubkeys.emplace(id, keys[0]);
660 38429 : ret.emplace_back(GetScriptForRawPubKey(keys[0])); // P2PK
661 38429 : ret.emplace_back(GetScriptForDestination(PKHash(id))); // P2PKH
662 38429 : if (keys[0].IsCompressed()) {
663 38404 : CScript p2wpkh = GetScriptForDestination(WitnessV0KeyHash(id));
664 38404 : out.scripts.emplace(CScriptID(p2wpkh), p2wpkh);
665 38404 : ret.emplace_back(p2wpkh);
666 38404 : ret.emplace_back(GetScriptForDestination(ScriptHash(p2wpkh))); // P2SH-P2WPKH
667 38404 : }
668 : return ret;
669 38429 : }
670 : public:
671 212 : ComboDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), {}, "combo") {}
672 1 : bool IsSingleType() const final { return false; }
673 : };
674 :
675 : /** A parsed multi(...) or sortedmulti(...) descriptor */
676 9402 : class MultisigDescriptor final : public DescriptorImpl
677 : {
678 : const int m_threshold;
679 : const bool m_sorted;
680 : protected:
681 2650 : std::string ToStringExtra() const override { return strprintf("%i", m_threshold); }
682 12321 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, const CScript*, FlatSigningProvider&) const override {
683 12321 : if (m_sorted) {
684 80 : std::vector<CPubKey> sorted_keys(keys);
685 80 : std::sort(sorted_keys.begin(), sorted_keys.end());
686 80 : return Vector(GetScriptForMultisig(m_threshold, sorted_keys));
687 80 : }
688 12241 : return Vector(GetScriptForMultisig(m_threshold, keys));
689 12321 : }
690 : public:
691 6268 : 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) {}
692 0 : bool IsSingleType() const final { return true; }
693 : };
694 :
695 : /** A parsed sh(...) descriptor. */
696 66147 : class SHDescriptor final : public DescriptorImpl
697 : {
698 : protected:
699 5719 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, const CScript* script, FlatSigningProvider&) const override { return Vector(GetScriptForDestination(ScriptHash(*script))); }
700 : public:
701 44098 : SHDescriptor(std::unique_ptr<DescriptorImpl> desc) : DescriptorImpl({}, std::move(desc), "sh") {}
702 :
703 296 : Optional<OutputType> GetOutputType() const override
704 : {
705 296 : assert(m_subdescriptor_arg);
706 296 : if (m_subdescriptor_arg->GetOutputType() == OutputType::BECH32) return OutputType::P2SH_SEGWIT;
707 28 : return OutputType::LEGACY;
708 296 : }
709 249 : bool IsSingleType() const final { return true; }
710 : };
711 :
712 : /** A parsed wsh(...) descriptor. */
713 8661 : class WSHDescriptor final : public DescriptorImpl
714 : {
715 : protected:
716 12055 : std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, const CScript* script, FlatSigningProvider&) const override { return Vector(GetScriptForDestination(WitnessV0ScriptHash(*script))); }
717 : public:
718 5774 : WSHDescriptor(std::unique_ptr<DescriptorImpl> desc) : DescriptorImpl({}, std::move(desc), "wsh") {}
719 46 : Optional<OutputType> GetOutputType() const override { return OutputType::BECH32; }
720 24 : bool IsSingleType() const final { return true; }
721 : };
722 :
723 : ////////////////////////////////////////////////////////////////////////////
724 : // Parser //
725 : ////////////////////////////////////////////////////////////////////////////
726 :
727 : enum class ParseScriptContext {
728 : TOP,
729 : P2SH,
730 : P2WSH,
731 : };
732 :
733 : /** Parse a key path, being passed a split list of elements (the first element is ignored). */
734 1058 : NODISCARD bool ParseKeyPath(const std::vector<Span<const char>>& split, KeyPath& out, std::string& error)
735 : {
736 4192 : for (size_t i = 1; i < split.size(); ++i) {
737 3138 : Span<const char> elem = split[i];
738 : bool hardened = false;
739 3138 : if (elem.size() > 0 && (elem[elem.size() - 1] == '\'' || elem[elem.size() - 1] == 'h')) {
740 2484 : elem = elem.first(elem.size() - 1);
741 : hardened = true;
742 2484 : }
743 3138 : uint32_t p;
744 3138 : if (!ParseUInt32(std::string(elem.begin(), elem.end()), &p)) {
745 2 : error = strprintf("Key path value '%s' is not a valid uint32", std::string(elem.begin(), elem.end()));
746 2 : return false;
747 3136 : } else if (p > 0x7FFFFFFFUL) {
748 2 : error = strprintf("Key path value %u is out of range", p);
749 2 : return false;
750 : }
751 3134 : out.push_back(p | (((uint32_t)hardened) << 31));
752 3138 : }
753 1054 : return true;
754 1058 : }
755 :
756 : /** Parse a public key that excludes origin information. */
757 1663 : std::unique_ptr<PubkeyProvider> ParsePubkeyInner(uint32_t key_exp_index, const Span<const char>& sp, bool permit_uncompressed, FlatSigningProvider& out, std::string& error)
758 : {
759 : using namespace spanparsing;
760 :
761 1663 : auto split = Split(sp, '/');
762 1663 : std::string str(split[0].begin(), split[0].end());
763 1663 : if (str.size() == 0) {
764 2 : error = "No key provided";
765 2 : return nullptr;
766 : }
767 1661 : if (split.size() == 1) {
768 1116 : if (IsHex(str)) {
769 968 : std::vector<unsigned char> data = ParseHex(str);
770 968 : CPubKey pubkey(data);
771 968 : if (pubkey.IsFullyValid()) {
772 967 : if (permit_uncompressed || pubkey.IsCompressed()) {
773 964 : return MakeUnique<ConstPubkeyProvider>(key_exp_index, pubkey);
774 : } else {
775 3 : error = "Uncompressed keys are not allowed";
776 3 : return nullptr;
777 : }
778 : }
779 1 : error = strprintf("Pubkey '%s' is invalid", str);
780 1 : return nullptr;
781 968 : }
782 148 : CKey key = DecodeSecret(str);
783 148 : if (key.IsValid()) {
784 119 : if (permit_uncompressed || key.IsCompressed()) {
785 116 : CPubKey pubkey = key.GetPubKey();
786 116 : out.keys.emplace(pubkey.GetID(), key);
787 116 : return MakeUnique<ConstPubkeyProvider>(key_exp_index, pubkey);
788 116 : } else {
789 3 : error = "Uncompressed keys are not allowed";
790 3 : return nullptr;
791 : }
792 : }
793 148 : }
794 574 : CExtKey extkey = DecodeExtKey(str);
795 574 : CExtPubKey extpubkey = DecodeExtPubKey(str);
796 574 : if (!extkey.key.IsValid() && !extpubkey.pubkey.IsValid()) {
797 1 : error = strprintf("key '%s' is not valid", str);
798 1 : return nullptr;
799 : }
800 573 : KeyPath path;
801 573 : DeriveType type = DeriveType::NO;
802 573 : if (split.back() == MakeSpan("*").first(1)) {
803 426 : split.pop_back();
804 426 : type = DeriveType::UNHARDENED;
805 573 : } else if (split.back() == MakeSpan("*'").first(2) || split.back() == MakeSpan("*h").first(2)) {
806 40 : split.pop_back();
807 40 : type = DeriveType::HARDENED;
808 40 : }
809 573 : if (!ParseKeyPath(split, path, error)) return nullptr;
810 569 : if (extkey.key.IsValid()) {
811 121 : extpubkey = extkey.Neuter();
812 121 : out.keys.emplace(extpubkey.pubkey.GetID(), extkey.key);
813 121 : }
814 569 : return MakeUnique<BIP32PubkeyProvider>(key_exp_index, extpubkey, std::move(path), type);
815 1663 : }
816 :
817 : /** Parse a public key including origin information (if enabled). */
818 1677 : std::unique_ptr<PubkeyProvider> ParsePubkey(uint32_t key_exp_index, const Span<const char>& sp, bool permit_uncompressed, FlatSigningProvider& out, std::string& error)
819 : {
820 : using namespace spanparsing;
821 :
822 1677 : auto origin_split = Split(sp, ']');
823 1677 : if (origin_split.size() > 2) {
824 4 : error = "Multiple ']' characters found for a single pubkey";
825 4 : return nullptr;
826 : }
827 1673 : if (origin_split.size() == 1) return ParsePubkeyInner(key_exp_index, origin_split[0], permit_uncompressed, out, error);
828 495 : if (origin_split[0].empty() || origin_split[0][0] != '[') {
829 4 : error = strprintf("Key origin start '[ character expected but not found, got '%c' instead",
830 2 : origin_split[0].empty() ? /** empty, implies split char */ ']' : origin_split[0][0]);
831 2 : return nullptr;
832 : }
833 493 : auto slash_split = Split(origin_split[0].subspan(1), '/');
834 493 : if (slash_split[0].size() != 8) {
835 6 : error = strprintf("Fingerprint is not 4 bytes (%u characters instead of 8 characters)", slash_split[0].size());
836 6 : return nullptr;
837 : }
838 487 : std::string fpr_hex = std::string(slash_split[0].begin(), slash_split[0].end());
839 487 : if (!IsHex(fpr_hex)) {
840 2 : error = strprintf("Fingerprint '%s' is not hex", fpr_hex);
841 2 : return nullptr;
842 : }
843 485 : auto fpr_bytes = ParseHex(fpr_hex);
844 485 : KeyOriginInfo info;
845 : static_assert(sizeof(info.fingerprint) == 4, "Fingerprint must be 4 bytes");
846 485 : assert(fpr_bytes.size() == 4);
847 485 : std::copy(fpr_bytes.begin(), fpr_bytes.end(), info.fingerprint);
848 485 : if (!ParseKeyPath(slash_split, info.path, error)) return nullptr;
849 485 : auto provider = ParsePubkeyInner(key_exp_index, origin_split[1], permit_uncompressed, out, error);
850 485 : if (!provider) return nullptr;
851 483 : return MakeUnique<OriginPubkeyProvider>(key_exp_index, std::move(info), std::move(provider));
852 1677 : }
853 :
854 : /** Parse a script in a particular context. */
855 1785 : std::unique_ptr<DescriptorImpl> ParseScript(uint32_t key_exp_index, Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error)
856 : {
857 : using namespace spanparsing;
858 :
859 1785 : auto expr = Expr(sp);
860 1785 : bool sorted_multi = false;
861 1785 : if (Func("pk", expr)) {
862 19 : auto pubkey = ParsePubkey(key_exp_index, expr, ctx != ParseScriptContext::P2WSH, out, error);
863 19 : if (!pubkey) return nullptr;
864 17 : return MakeUnique<PKDescriptor>(std::move(pubkey));
865 19 : }
866 1766 : if (Func("pkh", expr)) {
867 199 : auto pubkey = ParsePubkey(key_exp_index, expr, ctx != ParseScriptContext::P2WSH, out, error);
868 199 : if (!pubkey) return nullptr;
869 191 : return MakeUnique<PKHDescriptor>(std::move(pubkey));
870 199 : }
871 1567 : if (ctx == ParseScriptContext::TOP && Func("combo", expr)) {
872 108 : auto pubkey = ParsePubkey(key_exp_index, expr, true, out, error);
873 108 : if (!pubkey) return nullptr;
874 106 : return MakeUnique<ComboDescriptor>(std::move(pubkey));
875 1567 : } else if (ctx != ParseScriptContext::TOP && Func("combo", expr)) {
876 2 : error = "Cannot have combo in non-top level";
877 2 : return nullptr;
878 : }
879 1457 : if ((sorted_multi = Func("sortedmulti", expr)) || Func("multi", expr)) {
880 332 : auto threshold = Expr(expr);
881 332 : uint32_t thres;
882 332 : std::vector<std::unique_ptr<PubkeyProvider>> providers;
883 332 : if (!ParseUInt32(std::string(threshold.begin(), threshold.end()), &thres)) {
884 2 : error = strprintf("Multi threshold '%s' is not valid", std::string(threshold.begin(), threshold.end()));
885 2 : return nullptr;
886 : }
887 : size_t script_size = 0;
888 1239 : while (expr.size()) {
889 919 : if (!Const(",", expr)) {
890 0 : error = strprintf("Multi: expected ',', got '%c'", expr[0]);
891 0 : return nullptr;
892 : }
893 919 : auto arg = Expr(expr);
894 919 : auto pk = ParsePubkey(key_exp_index, arg, ctx != ParseScriptContext::P2WSH, out, error);
895 919 : if (!pk) return nullptr;
896 909 : script_size += pk->GetSize() + 1;
897 909 : providers.emplace_back(std::move(pk));
898 909 : key_exp_index++;
899 919 : }
900 320 : if (providers.empty() || providers.size() > 16) {
901 2 : error = strprintf("Cannot have %u keys in multisig; must have between 1 and 16 keys, inclusive", providers.size());
902 2 : return nullptr;
903 318 : } else if (thres < 1) {
904 2 : error = strprintf("Multisig threshold cannot be %d, must be at least 1", thres);
905 2 : return nullptr;
906 316 : } else if (thres > providers.size()) {
907 2 : error = strprintf("Multisig threshold cannot be larger than the number of keys; threshold is %d but only %u keys specified", thres, providers.size());
908 2 : return nullptr;
909 : }
910 314 : if (ctx == ParseScriptContext::TOP) {
911 16 : if (providers.size() > 3) {
912 2 : error = strprintf("Cannot have %u pubkeys in bare multisig; only at most 3 pubkeys", providers.size());
913 2 : return nullptr;
914 : }
915 : }
916 312 : if (ctx == ParseScriptContext::P2SH) {
917 117 : if (script_size + 3 > MAX_SCRIPT_ELEMENT_SIZE) {
918 2 : error = strprintf("P2SH script is too large, %d bytes is larger than %d bytes", script_size + 3, MAX_SCRIPT_ELEMENT_SIZE);
919 2 : return nullptr;
920 : }
921 : }
922 310 : return MakeUnique<MultisigDescriptor>(thres, std::move(providers), sorted_multi);
923 332 : }
924 1125 : if (ctx != ParseScriptContext::P2WSH && Func("wpkh", expr)) {
925 432 : auto pubkey = ParsePubkey(key_exp_index, expr, false, out, error);
926 432 : if (!pubkey) return nullptr;
927 426 : return MakeUnique<WPKHDescriptor>(std::move(pubkey));
928 1125 : } else if (ctx == ParseScriptContext::P2WSH && Func("wpkh", expr)) {
929 2 : error = "Cannot have wpkh within wsh";
930 2 : return nullptr;
931 : }
932 691 : if (ctx == ParseScriptContext::TOP && Func("sh", expr)) {
933 449 : auto desc = ParseScript(key_exp_index, expr, ParseScriptContext::P2SH, out, error);
934 449 : if (!desc || expr.size()) return nullptr;
935 435 : return MakeUnique<SHDescriptor>(std::move(desc));
936 691 : } else if (ctx != ParseScriptContext::TOP && Func("sh", expr)) {
937 4 : error = "Cannot have sh in non-top level";
938 4 : return nullptr;
939 : }
940 238 : if (ctx != ParseScriptContext::P2WSH && Func("wsh", expr)) {
941 211 : auto desc = ParseScript(key_exp_index, expr, ParseScriptContext::P2WSH, out, error);
942 211 : if (!desc || expr.size()) return nullptr;
943 191 : return MakeUnique<WSHDescriptor>(std::move(desc));
944 238 : } else if (ctx == ParseScriptContext::P2WSH && Func("wsh", expr)) {
945 2 : error = "Cannot have wsh within wsh";
946 2 : return nullptr;
947 : }
948 25 : if (ctx == ParseScriptContext::TOP && Func("addr", expr)) {
949 9 : CTxDestination dest = DecodeDestination(std::string(expr.begin(), expr.end()));
950 9 : if (!IsValidDestination(dest)) {
951 1 : error = "Address is not valid";
952 1 : return nullptr;
953 : }
954 8 : return MakeUnique<AddressDescriptor>(std::move(dest));
955 9 : }
956 16 : if (ctx == ParseScriptContext::TOP && Func("raw", expr)) {
957 1 : std::string str(expr.begin(), expr.end());
958 1 : if (!IsHex(str)) {
959 1 : error = "Raw script is not hex";
960 1 : return nullptr;
961 : }
962 0 : auto bytes = ParseHex(str);
963 0 : return MakeUnique<RawDescriptor>(CScript(bytes.begin(), bytes.end()));
964 1 : }
965 15 : if (ctx == ParseScriptContext::P2SH) {
966 2 : error = "A function is needed within P2SH";
967 2 : return nullptr;
968 13 : } else if (ctx == ParseScriptContext::P2WSH) {
969 2 : error = "A function is needed within P2WSH";
970 2 : return nullptr;
971 : }
972 11 : error = strprintf("%s is not a valid descriptor function", std::string(expr.begin(), expr.end()));
973 11 : return nullptr;
974 1785 : }
975 :
976 186224 : std::unique_ptr<PubkeyProvider> InferPubkey(const CPubKey& pubkey, ParseScriptContext, const SigningProvider& provider)
977 : {
978 186224 : std::unique_ptr<PubkeyProvider> key_provider = MakeUnique<ConstPubkeyProvider>(0, pubkey);
979 186224 : KeyOriginInfo info;
980 186224 : if (provider.GetKeyOrigin(pubkey.GetID(), info)) {
981 185906 : return MakeUnique<OriginPubkeyProvider>(0, std::move(info), std::move(key_provider));
982 : }
983 318 : return key_provider;
984 186224 : }
985 :
986 313984 : std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptContext ctx, const SigningProvider& provider)
987 : {
988 313984 : std::vector<std::vector<unsigned char>> data;
989 313984 : TxoutType txntype = Solver(script, data);
990 :
991 313984 : if (txntype == TxoutType::PUBKEY) {
992 19410 : CPubKey pubkey(data[0].begin(), data[0].end());
993 19410 : if (pubkey.IsValid()) {
994 19410 : return MakeUnique<PKDescriptor>(InferPubkey(pubkey, ctx, provider));
995 : }
996 19410 : }
997 294574 : if (txntype == TxoutType::PUBKEYHASH) {
998 77757 : uint160 hash(data[0]);
999 77757 : CKeyID keyid(hash);
1000 77757 : CPubKey pubkey;
1001 77757 : if (provider.GetPubKey(keyid, pubkey)) {
1002 77302 : return MakeUnique<PKHDescriptor>(InferPubkey(pubkey, ctx, provider));
1003 : }
1004 77757 : }
1005 217272 : if (txntype == TxoutType::WITNESS_V0_KEYHASH && ctx != ParseScriptContext::P2WSH) {
1006 107037 : uint160 hash(data[0]);
1007 107037 : CKeyID keyid(hash);
1008 107037 : CPubKey pubkey;
1009 107037 : if (provider.GetPubKey(keyid, pubkey)) {
1010 84037 : return MakeUnique<WPKHDescriptor>(InferPubkey(pubkey, ctx, provider));
1011 : }
1012 107037 : }
1013 133235 : if (txntype == TxoutType::MULTISIG) {
1014 2824 : std::vector<std::unique_ptr<PubkeyProvider>> providers;
1015 8299 : for (size_t i = 1; i + 1 < data.size(); ++i) {
1016 5475 : CPubKey pubkey(data[i].begin(), data[i].end());
1017 5475 : providers.push_back(InferPubkey(pubkey, ctx, provider));
1018 5475 : }
1019 2824 : return MakeUnique<MultisigDescriptor>((int)data[0][0], std::move(providers));
1020 2824 : }
1021 130411 : if (txntype == TxoutType::SCRIPTHASH && ctx == ParseScriptContext::TOP) {
1022 22737 : uint160 hash(data[0]);
1023 22737 : CScriptID scriptid(hash);
1024 22737 : CScript subscript;
1025 22737 : if (provider.GetCScript(scriptid, subscript)) {
1026 21614 : auto sub = InferScript(subscript, ParseScriptContext::P2SH, provider);
1027 21614 : if (sub) return MakeUnique<SHDescriptor>(std::move(sub));
1028 21614 : }
1029 22737 : }
1030 108797 : if (txntype == TxoutType::WITNESS_V0_SCRIPTHASH && ctx != ParseScriptContext::P2WSH) {
1031 3519 : CScriptID scriptid;
1032 3519 : CRIPEMD160().Write(data[0].data(), data[0].size()).Finalize(scriptid.begin());
1033 3519 : CScript subscript;
1034 3519 : if (provider.GetCScript(scriptid, subscript)) {
1035 2696 : auto sub = InferScript(subscript, ParseScriptContext::P2WSH, provider);
1036 2696 : if (sub) return MakeUnique<WSHDescriptor>(std::move(sub));
1037 2696 : }
1038 3519 : }
1039 :
1040 106101 : CTxDestination dest;
1041 106101 : if (ExtractDestination(script, dest)) {
1042 25407 : if (GetScriptForDestination(dest) == script) {
1043 25407 : return MakeUnique<AddressDescriptor>(std::move(dest));
1044 : }
1045 : }
1046 :
1047 80694 : return MakeUnique<RawDescriptor>(script);
1048 313984 : }
1049 :
1050 :
1051 : } // namespace
1052 :
1053 : /** Check a descriptor checksum, and update desc to be the checksum-less part. */
1054 1467 : bool CheckChecksum(Span<const char>& sp, bool require_checksum, std::string& error, std::string* out_checksum = nullptr)
1055 : {
1056 : using namespace spanparsing;
1057 :
1058 1467 : auto check_split = Split(sp, '#');
1059 1467 : if (check_split.size() > 2) {
1060 2 : error = "Multiple '#' symbols";
1061 2 : return false;
1062 : }
1063 1465 : if (check_split.size() == 1 && require_checksum){
1064 7 : error = "Missing checksum";
1065 7 : return false;
1066 : }
1067 1458 : if (check_split.size() == 2) {
1068 721 : if (check_split[1].size() != 8) {
1069 6 : error = strprintf("Expected 8 character checksum, not %u characters", check_split[1].size());
1070 6 : return false;
1071 : }
1072 : }
1073 1452 : auto checksum = DescriptorChecksum(check_split[0]);
1074 1452 : if (checksum.empty()) {
1075 1 : error = "Invalid characters in payload";
1076 1 : return false;
1077 : }
1078 1451 : if (check_split.size() == 2) {
1079 714 : if (!std::equal(checksum.begin(), checksum.end(), check_split[1].begin())) {
1080 8 : error = strprintf("Provided checksum '%s' does not match computed checksum '%s'", std::string(check_split[1].begin(), check_split[1].end()), checksum);
1081 8 : return false;
1082 : }
1083 : }
1084 1443 : if (out_checksum) *out_checksum = std::move(checksum);
1085 1443 : sp = check_split[0];
1086 1443 : return true;
1087 1467 : }
1088 :
1089 1145 : std::unique_ptr<Descriptor> Parse(const std::string& descriptor, FlatSigningProvider& out, std::string& error, bool require_checksum)
1090 : {
1091 1145 : Span<const char> sp{descriptor};
1092 1145 : if (!CheckChecksum(sp, require_checksum, error)) return nullptr;
1093 1125 : auto ret = ParseScript(0, sp, ParseScriptContext::TOP, out, error);
1094 1125 : if (sp.size() == 0 && ret) return std::unique_ptr<Descriptor>(std::move(ret));
1095 67 : return nullptr;
1096 1145 : }
1097 :
1098 322 : std::string GetDescriptorChecksum(const std::string& descriptor)
1099 : {
1100 322 : std::string ret;
1101 322 : std::string error;
1102 322 : Span<const char> sp{descriptor};
1103 322 : if (!CheckChecksum(sp, false, error, &ret)) return "";
1104 318 : return ret;
1105 322 : }
1106 :
1107 289674 : std::unique_ptr<Descriptor> InferDescriptor(const CScript& script, const SigningProvider& provider)
1108 : {
1109 289674 : return InferScript(script, ParseScriptContext::TOP, provider);
1110 : }
1111 :
1112 872 : void DescriptorCache::CacheParentExtPubKey(uint32_t key_exp_pos, const CExtPubKey& xpub)
1113 : {
1114 872 : m_parent_xpubs[key_exp_pos] = xpub;
1115 872 : }
1116 :
1117 1478 : void DescriptorCache::CacheDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index, const CExtPubKey& xpub)
1118 : {
1119 1478 : auto& xpubs = m_derived_xpubs[key_exp_pos];
1120 1478 : xpubs[der_index] = xpub;
1121 1478 : }
1122 :
1123 47323 : bool DescriptorCache::GetCachedParentExtPubKey(uint32_t key_exp_pos, CExtPubKey& xpub) const
1124 : {
1125 47323 : const auto& it = m_parent_xpubs.find(key_exp_pos);
1126 47323 : if (it == m_parent_xpubs.end()) return false;
1127 46873 : xpub = it->second;
1128 46873 : return true;
1129 47323 : }
1130 :
1131 48909 : bool DescriptorCache::GetCachedDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index, CExtPubKey& xpub) const
1132 : {
1133 48909 : const auto& key_exp_it = m_derived_xpubs.find(key_exp_pos);
1134 48909 : if (key_exp_it == m_derived_xpubs.end()) return false;
1135 1805 : const auto& der_it = key_exp_it->second.find(der_index);
1136 1805 : if (der_it == key_exp_it->second.end()) return false;
1137 176 : xpub = der_it->second;
1138 176 : return true;
1139 48909 : }
1140 :
1141 14936 : const ExtPubKeyMap DescriptorCache::GetCachedParentExtPubKeys() const
1142 : {
1143 14936 : return m_parent_xpubs;
1144 : }
1145 :
1146 14936 : const std::unordered_map<uint32_t, ExtPubKeyMap> DescriptorCache::GetCachedDerivedExtPubKeys() const
1147 : {
1148 14936 : return m_derived_xpubs;
1149 : }
|
