Bitcoin Core  26.99.0
P2P Digital Currency
descriptor.cpp
Go to the documentation of this file.
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 <hash.h>
8 #include <key_io.h>
9 #include <pubkey.h>
10 #include <script/miniscript.h>
11 #include <script/script.h>
12 #include <script/signingprovider.h>
13 #include <script/solver.h>
14 #include <uint256.h>
15 
16 #include <common/args.h>
17 #include <span.h>
18 #include <util/bip32.h>
19 #include <util/check.h>
20 #include <util/spanparsing.h>
21 #include <util/strencodings.h>
22 #include <util/vector.h>
23 
24 #include <memory>
25 #include <numeric>
26 #include <optional>
27 #include <string>
28 #include <vector>
29 
30 namespace {
31 
33 // Checksum //
35 
36 // This section implements a checksum algorithm for descriptors with the
37 // following properties:
38 // * Mistakes in a descriptor string are measured in "symbol errors". The higher
39 // the number of symbol errors, the harder it is to detect:
40 // * An error substituting a character from 0123456789()[],'/*abcdefgh@:$%{} for
41 // another in that set always counts as 1 symbol error.
42 // * Note that hex encoded keys are covered by these characters. Xprvs and
43 // xpubs use other characters too, but already have their own checksum
44 // mechanism.
45 // * Function names like "multi()" use other characters, but mistakes in
46 // these would generally result in an unparsable descriptor.
47 // * A case error always counts as 1 symbol error.
48 // * Any other 1 character substitution error counts as 1 or 2 symbol errors.
49 // * Any 1 symbol error is always detected.
50 // * Any 2 or 3 symbol error in a descriptor of up to 49154 characters is always detected.
51 // * Any 4 symbol error in a descriptor of up to 507 characters is always detected.
52 // * Any 5 symbol error in a descriptor of up to 77 characters is always detected.
53 // * Is optimized to minimize the chance a 5 symbol error in a descriptor up to 387 characters is undetected
54 // * Random errors have a chance of 1 in 2**40 of being undetected.
55 //
56 // These properties are achieved by expanding every group of 3 (non checksum) characters into
57 // 4 GF(32) symbols, over which a cyclic code is defined.
58 
59 /*
60  * Interprets c as 8 groups of 5 bits which are the coefficients of a degree 8 polynomial over GF(32),
61  * multiplies that polynomial by x, computes its remainder modulo a generator, and adds the constant term val.
62  *
63  * 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}.
64  * It is chosen to define an cyclic error detecting code which is selected by:
65  * - Starting from all BCH codes over GF(32) of degree 8 and below, which by construction guarantee detecting
66  * 3 errors in windows up to 19000 symbols.
67  * - Taking all those generators, and for degree 7 ones, extend them to degree 8 by adding all degree-1 factors.
68  * - Selecting just the set of generators that guarantee detecting 4 errors in a window of length 512.
69  * - Selecting one of those with best worst-case behavior for 5 errors in windows of length up to 512.
70  *
71  * The generator and the constants to implement it can be verified using this Sage code:
72  * B = GF(2) # Binary field
73  * BP.<b> = B[] # Polynomials over the binary field
74  * F_mod = b**5 + b**3 + 1
75  * F.<f> = GF(32, modulus=F_mod, repr='int') # GF(32) definition
76  * FP.<x> = F[] # Polynomials over GF(32)
77  * E_mod = x**3 + x + F.fetch_int(8)
78  * E.<e> = F.extension(E_mod) # Extension field definition
79  * alpha = e**2743 # Choice of an element in extension field
80  * for p in divisors(E.order() - 1): # Verify alpha has order 32767.
81  * assert((alpha**p == 1) == (p % 32767 == 0))
82  * G = lcm([(alpha**i).minpoly() for i in [1056,1057,1058]] + [x + 1])
83  * print(G) # Print out the generator
84  * for i in [1,2,4,8,16]: # Print out {1,2,4,8,16}*(G mod x^8), packed in hex integers.
85  * v = 0
86  * for coef in reversed((F.fetch_int(i)*(G % x**8)).coefficients(sparse=True)):
87  * v = v*32 + coef.integer_representation()
88  * print("0x%x" % v)
89  */
90 uint64_t PolyMod(uint64_t c, int val)
91 {
92  uint8_t c0 = c >> 35;
93  c = ((c & 0x7ffffffff) << 5) ^ val;
94  if (c0 & 1) c ^= 0xf5dee51989;
95  if (c0 & 2) c ^= 0xa9fdca3312;
96  if (c0 & 4) c ^= 0x1bab10e32d;
97  if (c0 & 8) c ^= 0x3706b1677a;
98  if (c0 & 16) c ^= 0x644d626ffd;
99  return c;
100 }
101 
102 std::string DescriptorChecksum(const Span<const char>& span)
103 {
117  static std::string INPUT_CHARSET =
118  "0123456789()[],'/*abcdefgh@:$%{}"
119  "IJKLMNOPQRSTUVWXYZ&+-.;<=>?!^_|~"
120  "ijklmnopqrstuvwxyzABCDEFGH`#\"\\ ";
121 
123  static std::string CHECKSUM_CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l";
124 
125  uint64_t c = 1;
126  int cls = 0;
127  int clscount = 0;
128  for (auto ch : span) {
129  auto pos = INPUT_CHARSET.find(ch);
130  if (pos == std::string::npos) return "";
131  c = PolyMod(c, pos & 31); // Emit a symbol for the position inside the group, for every character.
132  cls = cls * 3 + (pos >> 5); // Accumulate the group numbers
133  if (++clscount == 3) {
134  // Emit an extra symbol representing the group numbers, for every 3 characters.
135  c = PolyMod(c, cls);
136  cls = 0;
137  clscount = 0;
138  }
139  }
140  if (clscount > 0) c = PolyMod(c, cls);
141  for (int j = 0; j < 8; ++j) c = PolyMod(c, 0); // Shift further to determine the checksum.
142  c ^= 1; // Prevent appending zeroes from not affecting the checksum.
143 
144  std::string ret(8, ' ');
145  for (int j = 0; j < 8; ++j) ret[j] = CHECKSUM_CHARSET[(c >> (5 * (7 - j))) & 31];
146  return ret;
147 }
148 
149 std::string AddChecksum(const std::string& str) { return str + "#" + DescriptorChecksum(str); }
150 
152 // Internal representation //
154 
155 typedef std::vector<uint32_t> KeyPath;
156 
158 struct PubkeyProvider
159 {
160 protected:
163  uint32_t m_expr_index;
164 
165 public:
166  explicit PubkeyProvider(uint32_t exp_index) : m_expr_index(exp_index) {}
167 
168  virtual ~PubkeyProvider() = default;
169 
173  bool operator<(PubkeyProvider& other) const {
174  CPubKey a, b;
175  SigningProvider dummy;
176  KeyOriginInfo dummy_info;
177 
178  GetPubKey(0, dummy, a, dummy_info);
179  other.GetPubKey(0, dummy, b, dummy_info);
180 
181  return a < b;
182  }
183 
189  virtual bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const = 0;
190 
192  virtual bool IsRange() const = 0;
193 
195  virtual size_t GetSize() const = 0;
196 
197  enum class StringType {
198  PUBLIC,
199  COMPAT // string calculation that mustn't change over time to stay compatible with previous software versions
200  };
201 
203  virtual std::string ToString(StringType type=StringType::PUBLIC) const = 0;
204 
206  virtual bool ToPrivateString(const SigningProvider& arg, std::string& out) const = 0;
207 
211  virtual bool ToNormalizedString(const SigningProvider& arg, std::string& out, const DescriptorCache* cache = nullptr) const = 0;
212 
214  virtual bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const = 0;
215 };
216 
217 class OriginPubkeyProvider final : public PubkeyProvider
218 {
219  KeyOriginInfo m_origin;
220  std::unique_ptr<PubkeyProvider> m_provider;
221  bool m_apostrophe;
222 
223  std::string OriginString(StringType type, bool normalized=false) const
224  {
225  // If StringType==COMPAT, always use the apostrophe to stay compatible with previous versions
226  bool use_apostrophe = (!normalized && m_apostrophe) || type == StringType::COMPAT;
227  return HexStr(m_origin.fingerprint) + FormatHDKeypath(m_origin.path, use_apostrophe);
228  }
229 
230 public:
231  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) {}
232  bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override
233  {
234  if (!m_provider->GetPubKey(pos, arg, key, info, read_cache, write_cache)) return false;
235  std::copy(std::begin(m_origin.fingerprint), std::end(m_origin.fingerprint), info.fingerprint);
236  info.path.insert(info.path.begin(), m_origin.path.begin(), m_origin.path.end());
237  return true;
238  }
239  bool IsRange() const override { return m_provider->IsRange(); }
240  size_t GetSize() const override { return m_provider->GetSize(); }
241  std::string ToString(StringType type) const override { return "[" + OriginString(type) + "]" + m_provider->ToString(type); }
242  bool ToPrivateString(const SigningProvider& arg, std::string& ret) const override
243  {
244  std::string sub;
245  if (!m_provider->ToPrivateString(arg, sub)) return false;
246  ret = "[" + OriginString(StringType::PUBLIC) + "]" + std::move(sub);
247  return true;
248  }
249  bool ToNormalizedString(const SigningProvider& arg, std::string& ret, const DescriptorCache* cache) const override
250  {
251  std::string sub;
252  if (!m_provider->ToNormalizedString(arg, sub, cache)) return false;
253  // If m_provider is a BIP32PubkeyProvider, we may get a string formatted like a OriginPubkeyProvider
254  // In that case, we need to strip out the leading square bracket and fingerprint from the substring,
255  // and append that to our own origin string.
256  if (sub[0] == '[') {
257  sub = sub.substr(9);
258  ret = "[" + OriginString(StringType::PUBLIC, /*normalized=*/true) + std::move(sub);
259  } else {
260  ret = "[" + OriginString(StringType::PUBLIC, /*normalized=*/true) + "]" + std::move(sub);
261  }
262  return true;
263  }
264  bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const override
265  {
266  return m_provider->GetPrivKey(pos, arg, key);
267  }
268 };
269 
271 class ConstPubkeyProvider final : public PubkeyProvider
272 {
273  CPubKey m_pubkey;
274  bool m_xonly;
275 
276 public:
277  ConstPubkeyProvider(uint32_t exp_index, const CPubKey& pubkey, bool xonly) : PubkeyProvider(exp_index), m_pubkey(pubkey), m_xonly(xonly) {}
278  bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override
279  {
280  key = m_pubkey;
281  info.path.clear();
282  CKeyID keyid = m_pubkey.GetID();
283  std::copy(keyid.begin(), keyid.begin() + sizeof(info.fingerprint), info.fingerprint);
284  return true;
285  }
286  bool IsRange() const override { return false; }
287  size_t GetSize() const override { return m_pubkey.size(); }
288  std::string ToString(StringType type) const override { return m_xonly ? HexStr(m_pubkey).substr(2) : HexStr(m_pubkey); }
289  bool ToPrivateString(const SigningProvider& arg, std::string& ret) const override
290  {
291  CKey key;
292  if (m_xonly) {
293  for (const auto& keyid : XOnlyPubKey(m_pubkey).GetKeyIDs()) {
294  arg.GetKey(keyid, key);
295  if (key.IsValid()) break;
296  }
297  } else {
298  arg.GetKey(m_pubkey.GetID(), key);
299  }
300  if (!key.IsValid()) return false;
301  ret = EncodeSecret(key);
302  return true;
303  }
304  bool ToNormalizedString(const SigningProvider& arg, std::string& ret, const DescriptorCache* cache) const override
305  {
306  ret = ToString(StringType::PUBLIC);
307  return true;
308  }
309  bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const override
310  {
311  return arg.GetKey(m_pubkey.GetID(), key);
312  }
313 };
314 
315 enum class DeriveType {
316  NO,
317  UNHARDENED,
318  HARDENED,
319 };
320 
322 class BIP32PubkeyProvider final : public PubkeyProvider
323 {
324  // Root xpub, path, and final derivation step type being used, if any
325  CExtPubKey m_root_extkey;
326  KeyPath m_path;
327  DeriveType m_derive;
328  // Whether ' or h is used in harded derivation
329  bool m_apostrophe;
330 
331  bool GetExtKey(const SigningProvider& arg, CExtKey& ret) const
332  {
333  CKey key;
334  if (!arg.GetKey(m_root_extkey.pubkey.GetID(), key)) return false;
335  ret.nDepth = m_root_extkey.nDepth;
336  std::copy(m_root_extkey.vchFingerprint, m_root_extkey.vchFingerprint + sizeof(ret.vchFingerprint), ret.vchFingerprint);
337  ret.nChild = m_root_extkey.nChild;
338  ret.chaincode = m_root_extkey.chaincode;
339  ret.key = key;
340  return true;
341  }
342 
343  // Derives the last xprv
344  bool GetDerivedExtKey(const SigningProvider& arg, CExtKey& xprv, CExtKey& last_hardened) const
345  {
346  if (!GetExtKey(arg, xprv)) return false;
347  for (auto entry : m_path) {
348  if (!xprv.Derive(xprv, entry)) return false;
349  if (entry >> 31) {
350  last_hardened = xprv;
351  }
352  }
353  return true;
354  }
355 
356  bool IsHardened() const
357  {
358  if (m_derive == DeriveType::HARDENED) return true;
359  for (auto entry : m_path) {
360  if (entry >> 31) return true;
361  }
362  return false;
363  }
364 
365 public:
366  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) {}
367  bool IsRange() const override { return m_derive != DeriveType::NO; }
368  size_t GetSize() const override { return 33; }
369  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
370  {
371  // Info of parent of the to be derived pubkey
372  KeyOriginInfo parent_info;
373  CKeyID keyid = m_root_extkey.pubkey.GetID();
374  std::copy(keyid.begin(), keyid.begin() + sizeof(parent_info.fingerprint), parent_info.fingerprint);
375  parent_info.path = m_path;
376 
377  // Info of the derived key itself which is copied out upon successful completion
378  KeyOriginInfo final_info_out_tmp = parent_info;
379  if (m_derive == DeriveType::UNHARDENED) final_info_out_tmp.path.push_back((uint32_t)pos);
380  if (m_derive == DeriveType::HARDENED) final_info_out_tmp.path.push_back(((uint32_t)pos) | 0x80000000L);
381 
382  // Derive keys or fetch them from cache
383  CExtPubKey final_extkey = m_root_extkey;
384  CExtPubKey parent_extkey = m_root_extkey;
385  CExtPubKey last_hardened_extkey;
386  bool der = true;
387  if (read_cache) {
388  if (!read_cache->GetCachedDerivedExtPubKey(m_expr_index, pos, final_extkey)) {
389  if (m_derive == DeriveType::HARDENED) return false;
390  // Try to get the derivation parent
391  if (!read_cache->GetCachedParentExtPubKey(m_expr_index, parent_extkey)) return false;
392  final_extkey = parent_extkey;
393  if (m_derive == DeriveType::UNHARDENED) der = parent_extkey.Derive(final_extkey, pos);
394  }
395  } else if (IsHardened()) {
396  CExtKey xprv;
397  CExtKey lh_xprv;
398  if (!GetDerivedExtKey(arg, xprv, lh_xprv)) return false;
399  parent_extkey = xprv.Neuter();
400  if (m_derive == DeriveType::UNHARDENED) der = xprv.Derive(xprv, pos);
401  if (m_derive == DeriveType::HARDENED) der = xprv.Derive(xprv, pos | 0x80000000UL);
402  final_extkey = xprv.Neuter();
403  if (lh_xprv.key.IsValid()) {
404  last_hardened_extkey = lh_xprv.Neuter();
405  }
406  } else {
407  for (auto entry : m_path) {
408  if (!parent_extkey.Derive(parent_extkey, entry)) return false;
409  }
410  final_extkey = parent_extkey;
411  if (m_derive == DeriveType::UNHARDENED) der = parent_extkey.Derive(final_extkey, pos);
412  assert(m_derive != DeriveType::HARDENED);
413  }
414  if (!der) return false;
415 
416  final_info_out = final_info_out_tmp;
417  key_out = final_extkey.pubkey;
418 
419  if (write_cache) {
420  // Only cache parent if there is any unhardened derivation
421  if (m_derive != DeriveType::HARDENED) {
422  write_cache->CacheParentExtPubKey(m_expr_index, parent_extkey);
423  // Cache last hardened xpub if we have it
424  if (last_hardened_extkey.pubkey.IsValid()) {
425  write_cache->CacheLastHardenedExtPubKey(m_expr_index, last_hardened_extkey);
426  }
427  } else if (final_info_out.path.size() > 0) {
428  write_cache->CacheDerivedExtPubKey(m_expr_index, pos, final_extkey);
429  }
430  }
431 
432  return true;
433  }
434  std::string ToString(StringType type, bool normalized) const
435  {
436  // If StringType==COMPAT, always use the apostrophe to stay compatible with previous versions
437  const bool use_apostrophe = (!normalized && m_apostrophe) || type == StringType::COMPAT;
438  std::string ret = EncodeExtPubKey(m_root_extkey) + FormatHDKeypath(m_path, /*apostrophe=*/use_apostrophe);
439  if (IsRange()) {
440  ret += "/*";
441  if (m_derive == DeriveType::HARDENED) ret += use_apostrophe ? '\'' : 'h';
442  }
443  return ret;
444  }
445  std::string ToString(StringType type=StringType::PUBLIC) const override
446  {
447  return ToString(type, /*normalized=*/false);
448  }
449  bool ToPrivateString(const SigningProvider& arg, std::string& out) const override
450  {
451  CExtKey key;
452  if (!GetExtKey(arg, key)) return false;
453  out = EncodeExtKey(key) + FormatHDKeypath(m_path, /*apostrophe=*/m_apostrophe);
454  if (IsRange()) {
455  out += "/*";
456  if (m_derive == DeriveType::HARDENED) out += m_apostrophe ? '\'' : 'h';
457  }
458  return true;
459  }
460  bool ToNormalizedString(const SigningProvider& arg, std::string& out, const DescriptorCache* cache) const override
461  {
462  if (m_derive == DeriveType::HARDENED) {
463  out = ToString(StringType::PUBLIC, /*normalized=*/true);
464 
465  return true;
466  }
467  // Step backwards to find the last hardened step in the path
468  int i = (int)m_path.size() - 1;
469  for (; i >= 0; --i) {
470  if (m_path.at(i) >> 31) {
471  break;
472  }
473  }
474  // Either no derivation or all unhardened derivation
475  if (i == -1) {
476  out = ToString();
477  return true;
478  }
479  // Get the path to the last hardened stup
480  KeyOriginInfo origin;
481  int k = 0;
482  for (; k <= i; ++k) {
483  // Add to the path
484  origin.path.push_back(m_path.at(k));
485  }
486  // Build the remaining path
487  KeyPath end_path;
488  for (; k < (int)m_path.size(); ++k) {
489  end_path.push_back(m_path.at(k));
490  }
491  // Get the fingerprint
492  CKeyID id = m_root_extkey.pubkey.GetID();
493  std::copy(id.begin(), id.begin() + 4, origin.fingerprint);
494 
495  CExtPubKey xpub;
496  CExtKey lh_xprv;
497  // If we have the cache, just get the parent xpub
498  if (cache != nullptr) {
499  cache->GetCachedLastHardenedExtPubKey(m_expr_index, xpub);
500  }
501  if (!xpub.pubkey.IsValid()) {
502  // Cache miss, or nor cache, or need privkey
503  CExtKey xprv;
504  if (!GetDerivedExtKey(arg, xprv, lh_xprv)) return false;
505  xpub = lh_xprv.Neuter();
506  }
507  assert(xpub.pubkey.IsValid());
508 
509  // Build the string
510  std::string origin_str = HexStr(origin.fingerprint) + FormatHDKeypath(origin.path);
511  out = "[" + origin_str + "]" + EncodeExtPubKey(xpub) + FormatHDKeypath(end_path);
512  if (IsRange()) {
513  out += "/*";
514  assert(m_derive == DeriveType::UNHARDENED);
515  }
516  return true;
517  }
518  bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const override
519  {
520  CExtKey extkey;
521  CExtKey dummy;
522  if (!GetDerivedExtKey(arg, extkey, dummy)) return false;
523  if (m_derive == DeriveType::UNHARDENED && !extkey.Derive(extkey, pos)) return false;
524  if (m_derive == DeriveType::HARDENED && !extkey.Derive(extkey, pos | 0x80000000UL)) return false;
525  key = extkey.key;
526  return true;
527  }
528 };
529 
531 class DescriptorImpl : public Descriptor
532 {
533 protected:
535  const std::vector<std::unique_ptr<PubkeyProvider>> m_pubkey_args;
537  const std::string m_name;
538 
543  const std::vector<std::unique_ptr<DescriptorImpl>> m_subdescriptor_args;
544 
546  virtual std::string ToStringExtra() const { return ""; }
547 
558  virtual std::vector<CScript> MakeScripts(const std::vector<CPubKey>& pubkeys, Span<const CScript> scripts, FlatSigningProvider& out) const = 0;
559 
560 public:
561  DescriptorImpl(std::vector<std::unique_ptr<PubkeyProvider>> pubkeys, const std::string& name) : m_pubkey_args(std::move(pubkeys)), m_name(name), m_subdescriptor_args() {}
562  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))) {}
563  DescriptorImpl(std::vector<std::unique_ptr<PubkeyProvider>> pubkeys, std::vector<std::unique_ptr<DescriptorImpl>> scripts, const std::string& name) : m_pubkey_args(std::move(pubkeys)), m_name(name), m_subdescriptor_args(std::move(scripts)) {}
564 
565  enum class StringType
566  {
567  PUBLIC,
568  PRIVATE,
569  NORMALIZED,
570  COMPAT, // string calculation that mustn't change over time to stay compatible with previous software versions
571  };
572 
573  bool IsSolvable() const override
574  {
575  for (const auto& arg : m_subdescriptor_args) {
576  if (!arg->IsSolvable()) return false;
577  }
578  return true;
579  }
580 
581  bool IsRange() const final
582  {
583  for (const auto& pubkey : m_pubkey_args) {
584  if (pubkey->IsRange()) return true;
585  }
586  for (const auto& arg : m_subdescriptor_args) {
587  if (arg->IsRange()) return true;
588  }
589  return false;
590  }
591 
592  virtual bool ToStringSubScriptHelper(const SigningProvider* arg, std::string& ret, const StringType type, const DescriptorCache* cache = nullptr) const
593  {
594  size_t pos = 0;
595  for (const auto& scriptarg : m_subdescriptor_args) {
596  if (pos++) ret += ",";
597  std::string tmp;
598  if (!scriptarg->ToStringHelper(arg, tmp, type, cache)) return false;
599  ret += tmp;
600  }
601  return true;
602  }
603 
604  virtual bool ToStringHelper(const SigningProvider* arg, std::string& out, const StringType type, const DescriptorCache* cache = nullptr) const
605  {
606  std::string extra = ToStringExtra();
607  size_t pos = extra.size() > 0 ? 1 : 0;
608  std::string ret = m_name + "(" + extra;
609  for (const auto& pubkey : m_pubkey_args) {
610  if (pos++) ret += ",";
611  std::string tmp;
612  switch (type) {
613  case StringType::NORMALIZED:
614  if (!pubkey->ToNormalizedString(*arg, tmp, cache)) return false;
615  break;
616  case StringType::PRIVATE:
617  if (!pubkey->ToPrivateString(*arg, tmp)) return false;
618  break;
619  case StringType::PUBLIC:
620  tmp = pubkey->ToString();
621  break;
622  case StringType::COMPAT:
623  tmp = pubkey->ToString(PubkeyProvider::StringType::COMPAT);
624  break;
625  }
626  ret += tmp;
627  }
628  std::string subscript;
629  if (!ToStringSubScriptHelper(arg, subscript, type, cache)) return false;
630  if (pos && subscript.size()) ret += ',';
631  out = std::move(ret) + std::move(subscript) + ")";
632  return true;
633  }
634 
635  std::string ToString(bool compat_format) const final
636  {
637  std::string ret;
638  ToStringHelper(nullptr, ret, compat_format ? StringType::COMPAT : StringType::PUBLIC);
639  return AddChecksum(ret);
640  }
641 
642  bool ToPrivateString(const SigningProvider& arg, std::string& out) const override
643  {
644  bool ret = ToStringHelper(&arg, out, StringType::PRIVATE);
645  out = AddChecksum(out);
646  return ret;
647  }
648 
649  bool ToNormalizedString(const SigningProvider& arg, std::string& out, const DescriptorCache* cache) const override final
650  {
651  bool ret = ToStringHelper(&arg, out, StringType::NORMALIZED, cache);
652  out = AddChecksum(out);
653  return ret;
654  }
655 
656  bool ExpandHelper(int pos, const SigningProvider& arg, const DescriptorCache* read_cache, std::vector<CScript>& output_scripts, FlatSigningProvider& out, DescriptorCache* write_cache) const
657  {
658  std::vector<std::pair<CPubKey, KeyOriginInfo>> entries;
659  entries.reserve(m_pubkey_args.size());
660 
661  // Construct temporary data in `entries`, `subscripts`, and `subprovider` to avoid producing output in case of failure.
662  for (const auto& p : m_pubkey_args) {
663  entries.emplace_back();
664  if (!p->GetPubKey(pos, arg, entries.back().first, entries.back().second, read_cache, write_cache)) return false;
665  }
666  std::vector<CScript> subscripts;
667  FlatSigningProvider subprovider;
668  for (const auto& subarg : m_subdescriptor_args) {
669  std::vector<CScript> outscripts;
670  if (!subarg->ExpandHelper(pos, arg, read_cache, outscripts, subprovider, write_cache)) return false;
671  assert(outscripts.size() == 1);
672  subscripts.emplace_back(std::move(outscripts[0]));
673  }
674  out.Merge(std::move(subprovider));
675 
676  std::vector<CPubKey> pubkeys;
677  pubkeys.reserve(entries.size());
678  for (auto& entry : entries) {
679  pubkeys.push_back(entry.first);
680  out.origins.emplace(entry.first.GetID(), std::make_pair<CPubKey, KeyOriginInfo>(CPubKey(entry.first), std::move(entry.second)));
681  }
682 
683  output_scripts = MakeScripts(pubkeys, Span{subscripts}, out);
684  return true;
685  }
686 
687  bool Expand(int pos, const SigningProvider& provider, std::vector<CScript>& output_scripts, FlatSigningProvider& out, DescriptorCache* write_cache = nullptr) const final
688  {
689  return ExpandHelper(pos, provider, nullptr, output_scripts, out, write_cache);
690  }
691 
692  bool ExpandFromCache(int pos, const DescriptorCache& read_cache, std::vector<CScript>& output_scripts, FlatSigningProvider& out) const final
693  {
694  return ExpandHelper(pos, DUMMY_SIGNING_PROVIDER, &read_cache, output_scripts, out, nullptr);
695  }
696 
697  void ExpandPrivate(int pos, const SigningProvider& provider, FlatSigningProvider& out) const final
698  {
699  for (const auto& p : m_pubkey_args) {
700  CKey key;
701  if (!p->GetPrivKey(pos, provider, key)) continue;
702  out.keys.emplace(key.GetPubKey().GetID(), key);
703  }
704  for (const auto& arg : m_subdescriptor_args) {
705  arg->ExpandPrivate(pos, provider, out);
706  }
707  }
708 
709  std::optional<OutputType> GetOutputType() const override { return std::nullopt; }
710 
711  std::optional<int64_t> ScriptSize() const override { return {}; }
712 
718  virtual std::optional<int64_t> MaxSatSize(bool use_max_sig) const { return {}; }
719 
720  std::optional<int64_t> MaxSatisfactionWeight(bool) const override { return {}; }
721 
722  std::optional<int64_t> MaxSatisfactionElems() const override { return {}; }
723 };
724 
726 class AddressDescriptor final : public DescriptorImpl
727 {
728  const CTxDestination m_destination;
729 protected:
730  std::string ToStringExtra() const override { return EncodeDestination(m_destination); }
731  std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, Span<const CScript>, FlatSigningProvider&) const override { return Vector(GetScriptForDestination(m_destination)); }
732 public:
733  AddressDescriptor(CTxDestination destination) : DescriptorImpl({}, "addr"), m_destination(std::move(destination)) {}
734  bool IsSolvable() const final { return false; }
735 
736  std::optional<OutputType> GetOutputType() const override
737  {
738  return OutputTypeFromDestination(m_destination);
739  }
740  bool IsSingleType() const final { return true; }
741  bool ToPrivateString(const SigningProvider& arg, std::string& out) const final { return false; }
742 
743  std::optional<int64_t> ScriptSize() const override { return GetScriptForDestination(m_destination).size(); }
744 };
745 
747 class RawDescriptor final : public DescriptorImpl
748 {
749  const CScript m_script;
750 protected:
751  std::string ToStringExtra() const override { return HexStr(m_script); }
752  std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, Span<const CScript>, FlatSigningProvider&) const override { return Vector(m_script); }
753 public:
754  RawDescriptor(CScript script) : DescriptorImpl({}, "raw"), m_script(std::move(script)) {}
755  bool IsSolvable() const final { return false; }
756 
757  std::optional<OutputType> GetOutputType() const override
758  {
759  CTxDestination dest;
760  ExtractDestination(m_script, dest);
761  return OutputTypeFromDestination(dest);
762  }
763  bool IsSingleType() const final { return true; }
764  bool ToPrivateString(const SigningProvider& arg, std::string& out) const final { return false; }
765 
766  std::optional<int64_t> ScriptSize() const override { return m_script.size(); }
767 };
768 
770 class PKDescriptor final : public DescriptorImpl
771 {
772 private:
773  const bool m_xonly;
774 protected:
775  std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider&) const override
776  {
777  if (m_xonly) {
778  CScript script = CScript() << ToByteVector(XOnlyPubKey(keys[0])) << OP_CHECKSIG;
779  return Vector(std::move(script));
780  } else {
781  return Vector(GetScriptForRawPubKey(keys[0]));
782  }
783  }
784 public:
785  PKDescriptor(std::unique_ptr<PubkeyProvider> prov, bool xonly = false) : DescriptorImpl(Vector(std::move(prov)), "pk"), m_xonly(xonly) {}
786  bool IsSingleType() const final { return true; }
787 
788  std::optional<int64_t> ScriptSize() const override {
789  return 1 + (m_xonly ? 32 : m_pubkey_args[0]->GetSize()) + 1;
790  }
791 
792  std::optional<int64_t> MaxSatSize(bool use_max_sig) const override {
793  const auto ecdsa_sig_size = use_max_sig ? 72 : 71;
794  return 1 + (m_xonly ? 65 : ecdsa_sig_size);
795  }
796 
797  std::optional<int64_t> MaxSatisfactionWeight(bool use_max_sig) const override {
798  return *MaxSatSize(use_max_sig) * WITNESS_SCALE_FACTOR;
799  }
800 
801  std::optional<int64_t> MaxSatisfactionElems() const override { return 1; }
802 };
803 
805 class PKHDescriptor final : public DescriptorImpl
806 {
807 protected:
808  std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider& out) const override
809  {
810  CKeyID id = keys[0].GetID();
811  out.pubkeys.emplace(id, keys[0]);
813  }
814 public:
815  PKHDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), "pkh") {}
816  std::optional<OutputType> GetOutputType() const override { return OutputType::LEGACY; }
817  bool IsSingleType() const final { return true; }
818 
819  std::optional<int64_t> ScriptSize() const override { return 1 + 1 + 1 + 20 + 1 + 1; }
820 
821  std::optional<int64_t> MaxSatSize(bool use_max_sig) const override {
822  const auto sig_size = use_max_sig ? 72 : 71;
823  return 1 + sig_size + 1 + m_pubkey_args[0]->GetSize();
824  }
825 
826  std::optional<int64_t> MaxSatisfactionWeight(bool use_max_sig) const override {
827  return *MaxSatSize(use_max_sig) * WITNESS_SCALE_FACTOR;
828  }
829 
830  std::optional<int64_t> MaxSatisfactionElems() const override { return 2; }
831 };
832 
834 class WPKHDescriptor final : public DescriptorImpl
835 {
836 protected:
837  std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider& out) const override
838  {
839  CKeyID id = keys[0].GetID();
840  out.pubkeys.emplace(id, keys[0]);
842  }
843 public:
844  WPKHDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), "wpkh") {}
845  std::optional<OutputType> GetOutputType() const override { return OutputType::BECH32; }
846  bool IsSingleType() const final { return true; }
847 
848  std::optional<int64_t> ScriptSize() const override { return 1 + 1 + 20; }
849 
850  std::optional<int64_t> MaxSatSize(bool use_max_sig) const override {
851  const auto sig_size = use_max_sig ? 72 : 71;
852  return (1 + sig_size + 1 + 33);
853  }
854 
855  std::optional<int64_t> MaxSatisfactionWeight(bool use_max_sig) const override {
856  return MaxSatSize(use_max_sig);
857  }
858 
859  std::optional<int64_t> MaxSatisfactionElems() const override { return 2; }
860 };
861 
863 class ComboDescriptor final : public DescriptorImpl
864 {
865 protected:
866  std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider& out) const override
867  {
868  std::vector<CScript> ret;
869  CKeyID id = keys[0].GetID();
870  out.pubkeys.emplace(id, keys[0]);
871  ret.emplace_back(GetScriptForRawPubKey(keys[0])); // P2PK
872  ret.emplace_back(GetScriptForDestination(PKHash(id))); // P2PKH
873  if (keys[0].IsCompressed()) {
875  out.scripts.emplace(CScriptID(p2wpkh), p2wpkh);
876  ret.emplace_back(p2wpkh);
877  ret.emplace_back(GetScriptForDestination(ScriptHash(p2wpkh))); // P2SH-P2WPKH
878  }
879  return ret;
880  }
881 public:
882  ComboDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), "combo") {}
883  bool IsSingleType() const final { return false; }
884 };
885 
887 class MultisigDescriptor final : public DescriptorImpl
888 {
889  const int m_threshold;
890  const bool m_sorted;
891 protected:
892  std::string ToStringExtra() const override { return strprintf("%i", m_threshold); }
893  std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider&) const override {
894  if (m_sorted) {
895  std::vector<CPubKey> sorted_keys(keys);
896  std::sort(sorted_keys.begin(), sorted_keys.end());
897  return Vector(GetScriptForMultisig(m_threshold, sorted_keys));
898  }
899  return Vector(GetScriptForMultisig(m_threshold, keys));
900  }
901 public:
902  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) {}
903  bool IsSingleType() const final { return true; }
904 
905  std::optional<int64_t> ScriptSize() const override {
906  const auto n_keys = m_pubkey_args.size();
907  auto op = [](int64_t acc, const std::unique_ptr<PubkeyProvider>& pk) { return acc + 1 + pk->GetSize();};
908  const auto pubkeys_size{std::accumulate(m_pubkey_args.begin(), m_pubkey_args.end(), int64_t{0}, op)};
909  return 1 + BuildScript(n_keys).size() + BuildScript(m_threshold).size() + pubkeys_size;
910  }
911 
912  std::optional<int64_t> MaxSatSize(bool use_max_sig) const override {
913  const auto sig_size = use_max_sig ? 72 : 71;
914  return (1 + (1 + sig_size) * m_threshold);
915  }
916 
917  std::optional<int64_t> MaxSatisfactionWeight(bool use_max_sig) const override {
918  return *MaxSatSize(use_max_sig) * WITNESS_SCALE_FACTOR;
919  }
920 
921  std::optional<int64_t> MaxSatisfactionElems() const override { return 1 + m_threshold; }
922 };
923 
925 class MultiADescriptor final : public DescriptorImpl
926 {
927  const int m_threshold;
928  const bool m_sorted;
929 protected:
930  std::string ToStringExtra() const override { return strprintf("%i", m_threshold); }
931  std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider&) const override {
932  CScript ret;
933  std::vector<XOnlyPubKey> xkeys;
934  xkeys.reserve(keys.size());
935  for (const auto& key : keys) xkeys.emplace_back(key);
936  if (m_sorted) std::sort(xkeys.begin(), xkeys.end());
937  ret << ToByteVector(xkeys[0]) << OP_CHECKSIG;
938  for (size_t i = 1; i < keys.size(); ++i) {
939  ret << ToByteVector(xkeys[i]) << OP_CHECKSIGADD;
940  }
941  ret << m_threshold << OP_NUMEQUAL;
942  return Vector(std::move(ret));
943  }
944 public:
945  MultiADescriptor(int threshold, std::vector<std::unique_ptr<PubkeyProvider>> providers, bool sorted = false) : DescriptorImpl(std::move(providers), sorted ? "sortedmulti_a" : "multi_a"), m_threshold(threshold), m_sorted(sorted) {}
946  bool IsSingleType() const final { return true; }
947 
948  std::optional<int64_t> ScriptSize() const override {
949  const auto n_keys = m_pubkey_args.size();
950  return (1 + 32 + 1) * n_keys + BuildScript(m_threshold).size() + 1;
951  }
952 
953  std::optional<int64_t> MaxSatSize(bool use_max_sig) const override {
954  return (1 + 65) * m_threshold + (m_pubkey_args.size() - m_threshold);
955  }
956 
957  std::optional<int64_t> MaxSatisfactionElems() const override { return m_pubkey_args.size(); }
958 };
959 
961 class SHDescriptor final : public DescriptorImpl
962 {
963 protected:
964  std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, Span<const CScript> scripts, FlatSigningProvider& out) const override
965  {
966  auto ret = Vector(GetScriptForDestination(ScriptHash(scripts[0])));
967  if (ret.size()) out.scripts.emplace(CScriptID(scripts[0]), scripts[0]);
968  return ret;
969  }
970 
971  bool IsSegwit() const { return m_subdescriptor_args[0]->GetOutputType() == OutputType::BECH32; }
972 
973 public:
974  SHDescriptor(std::unique_ptr<DescriptorImpl> desc) : DescriptorImpl({}, std::move(desc), "sh") {}
975 
976  std::optional<OutputType> GetOutputType() const override
977  {
978  assert(m_subdescriptor_args.size() == 1);
979  if (IsSegwit()) return OutputType::P2SH_SEGWIT;
980  return OutputType::LEGACY;
981  }
982  bool IsSingleType() const final { return true; }
983 
984  std::optional<int64_t> ScriptSize() const override { return 1 + 1 + 20 + 1; }
985 
986  std::optional<int64_t> MaxSatisfactionWeight(bool use_max_sig) const override {
987  if (const auto sat_size = m_subdescriptor_args[0]->MaxSatSize(use_max_sig)) {
988  if (const auto subscript_size = m_subdescriptor_args[0]->ScriptSize()) {
989  // The subscript is never witness data.
990  const auto subscript_weight = (1 + *subscript_size) * WITNESS_SCALE_FACTOR;
991  // The weight depends on whether the inner descriptor is satisfied using the witness stack.
992  if (IsSegwit()) return subscript_weight + *sat_size;
993  return subscript_weight + *sat_size * WITNESS_SCALE_FACTOR;
994  }
995  }
996  return {};
997  }
998 
999  std::optional<int64_t> MaxSatisfactionElems() const override {
1000  if (const auto sub_elems = m_subdescriptor_args[0]->MaxSatisfactionElems()) return 1 + *sub_elems;
1001  return {};
1002  }
1003 };
1004 
1006 class WSHDescriptor final : public DescriptorImpl
1007 {
1008 protected:
1009  std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, Span<const CScript> scripts, FlatSigningProvider& out) const override
1010  {
1012  if (ret.size()) out.scripts.emplace(CScriptID(scripts[0]), scripts[0]);
1013  return ret;
1014  }
1015 public:
1016  WSHDescriptor(std::unique_ptr<DescriptorImpl> desc) : DescriptorImpl({}, std::move(desc), "wsh") {}
1017  std::optional<OutputType> GetOutputType() const override { return OutputType::BECH32; }
1018  bool IsSingleType() const final { return true; }
1019 
1020  std::optional<int64_t> ScriptSize() const override { return 1 + 1 + 32; }
1021 
1022  std::optional<int64_t> MaxSatSize(bool use_max_sig) const override {
1023  if (const auto sat_size = m_subdescriptor_args[0]->MaxSatSize(use_max_sig)) {
1024  if (const auto subscript_size = m_subdescriptor_args[0]->ScriptSize()) {
1025  return GetSizeOfCompactSize(*subscript_size) + *subscript_size + *sat_size;
1026  }
1027  }
1028  return {};
1029  }
1030 
1031  std::optional<int64_t> MaxSatisfactionWeight(bool use_max_sig) const override {
1032  return MaxSatSize(use_max_sig);
1033  }
1034 
1035  std::optional<int64_t> MaxSatisfactionElems() const override {
1036  if (const auto sub_elems = m_subdescriptor_args[0]->MaxSatisfactionElems()) return 1 + *sub_elems;
1037  return {};
1038  }
1039 };
1040 
1042 class TRDescriptor final : public DescriptorImpl
1043 {
1044  std::vector<int> m_depths;
1045 protected:
1046  std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript> scripts, FlatSigningProvider& out) const override
1047  {
1048  TaprootBuilder builder;
1049  assert(m_depths.size() == scripts.size());
1050  for (size_t pos = 0; pos < m_depths.size(); ++pos) {
1051  builder.Add(m_depths[pos], scripts[pos], TAPROOT_LEAF_TAPSCRIPT);
1052  }
1053  if (!builder.IsComplete()) return {};
1054  assert(keys.size() == 1);
1055  XOnlyPubKey xpk(keys[0]);
1056  if (!xpk.IsFullyValid()) return {};
1057  builder.Finalize(xpk);
1058  WitnessV1Taproot output = builder.GetOutput();
1059  out.tr_trees[output] = builder;
1060  out.pubkeys.emplace(keys[0].GetID(), keys[0]);
1061  return Vector(GetScriptForDestination(output));
1062  }
1063  bool ToStringSubScriptHelper(const SigningProvider* arg, std::string& ret, const StringType type, const DescriptorCache* cache = nullptr) const override
1064  {
1065  if (m_depths.empty()) return true;
1066  std::vector<bool> path;
1067  for (size_t pos = 0; pos < m_depths.size(); ++pos) {
1068  if (pos) ret += ',';
1069  while ((int)path.size() <= m_depths[pos]) {
1070  if (path.size()) ret += '{';
1071  path.push_back(false);
1072  }
1073  std::string tmp;
1074  if (!m_subdescriptor_args[pos]->ToStringHelper(arg, tmp, type, cache)) return false;
1075  ret += tmp;
1076  while (!path.empty() && path.back()) {
1077  if (path.size() > 1) ret += '}';
1078  path.pop_back();
1079  }
1080  if (!path.empty()) path.back() = true;
1081  }
1082  return true;
1083  }
1084 public:
1085  TRDescriptor(std::unique_ptr<PubkeyProvider> internal_key, std::vector<std::unique_ptr<DescriptorImpl>> descs, std::vector<int> depths) :
1086  DescriptorImpl(Vector(std::move(internal_key)), std::move(descs), "tr"), m_depths(std::move(depths))
1087  {
1088  assert(m_subdescriptor_args.size() == m_depths.size());
1089  }
1090  std::optional<OutputType> GetOutputType() const override { return OutputType::BECH32M; }
1091  bool IsSingleType() const final { return true; }
1092 
1093  std::optional<int64_t> ScriptSize() const override { return 1 + 1 + 32; }
1094 
1095  std::optional<int64_t> MaxSatisfactionWeight(bool) const override {
1096  // FIXME: We assume keypath spend, which can lead to very large underestimations.
1097  return 1 + 65;
1098  }
1099 
1100  std::optional<int64_t> MaxSatisfactionElems() const override {
1101  // FIXME: See above, we assume keypath spend.
1102  return 1;
1103  }
1104 };
1105 
1106 /* We instantiate Miniscript here with a simple integer as key type.
1107  * The value of these key integers are an index in the
1108  * DescriptorImpl::m_pubkey_args vector.
1109  */
1110 
1114 class ScriptMaker {
1116  const std::vector<CPubKey>& m_keys;
1118  const miniscript::MiniscriptContext m_script_ctx;
1119 
1123  uint160 GetHash160(uint32_t key) const {
1124  if (miniscript::IsTapscript(m_script_ctx)) {
1125  return Hash160(XOnlyPubKey{m_keys[key]});
1126  }
1127  return m_keys[key].GetID();
1128  }
1129 
1130 public:
1131  ScriptMaker(const std::vector<CPubKey>& keys LIFETIMEBOUND, const miniscript::MiniscriptContext script_ctx) : m_keys(keys), m_script_ctx{script_ctx} {}
1132 
1133  std::vector<unsigned char> ToPKBytes(uint32_t key) const {
1134  // In Tapscript keys always serialize as x-only, whether an x-only key was used in the descriptor or not.
1135  if (!miniscript::IsTapscript(m_script_ctx)) {
1136  return {m_keys[key].begin(), m_keys[key].end()};
1137  }
1138  const XOnlyPubKey xonly_pubkey{m_keys[key]};
1139  return {xonly_pubkey.begin(), xonly_pubkey.end()};
1140  }
1141 
1142  std::vector<unsigned char> ToPKHBytes(uint32_t key) const {
1143  auto id = GetHash160(key);
1144  return {id.begin(), id.end()};
1145  }
1146 };
1147 
1151 class StringMaker {
1153  const SigningProvider* m_arg;
1155  const std::vector<std::unique_ptr<PubkeyProvider>>& m_pubkeys;
1157  bool m_private;
1158 
1159 public:
1160  StringMaker(const SigningProvider* arg LIFETIMEBOUND, const std::vector<std::unique_ptr<PubkeyProvider>>& pubkeys LIFETIMEBOUND, bool priv)
1161  : m_arg(arg), m_pubkeys(pubkeys), m_private(priv) {}
1162 
1163  std::optional<std::string> ToString(uint32_t key) const
1164  {
1165  std::string ret;
1166  if (m_private) {
1167  if (!m_pubkeys[key]->ToPrivateString(*m_arg, ret)) return {};
1168  } else {
1169  ret = m_pubkeys[key]->ToString();
1170  }
1171  return ret;
1172  }
1173 };
1174 
1175 class MiniscriptDescriptor final : public DescriptorImpl
1176 {
1177 private:
1179 
1180 protected:
1181  std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript> scripts,
1182  FlatSigningProvider& provider) const override
1183  {
1184  const auto script_ctx{m_node->GetMsCtx()};
1185  for (const auto& key : keys) {
1186  if (miniscript::IsTapscript(script_ctx)) {
1187  provider.pubkeys.emplace(Hash160(XOnlyPubKey{key}), key);
1188  } else {
1189  provider.pubkeys.emplace(key.GetID(), key);
1190  }
1191  }
1192  return Vector(m_node->ToScript(ScriptMaker(keys, script_ctx)));
1193  }
1194 
1195 public:
1196  MiniscriptDescriptor(std::vector<std::unique_ptr<PubkeyProvider>> providers, miniscript::NodeRef<uint32_t> node)
1197  : DescriptorImpl(std::move(providers), "?"), m_node(std::move(node)) {}
1198 
1199  bool ToStringHelper(const SigningProvider* arg, std::string& out, const StringType type,
1200  const DescriptorCache* cache = nullptr) const override
1201  {
1202  if (const auto res = m_node->ToString(StringMaker(arg, m_pubkey_args, type == StringType::PRIVATE))) {
1203  out = *res;
1204  return true;
1205  }
1206  return false;
1207  }
1208 
1209  bool IsSolvable() const override { return true; }
1210  bool IsSingleType() const final { return true; }
1211 
1212  std::optional<int64_t> ScriptSize() const override { return m_node->ScriptSize(); }
1213 
1214  std::optional<int64_t> MaxSatSize(bool) const override {
1215  // For Miniscript we always assume high-R ECDSA signatures.
1216  return m_node->GetWitnessSize();
1217  }
1218 
1219  std::optional<int64_t> MaxSatisfactionElems() const override {
1220  return m_node->GetStackSize();
1221  }
1222 };
1223 
1225 class RawTRDescriptor final : public DescriptorImpl
1226 {
1227 protected:
1228  std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript> scripts, FlatSigningProvider& out) const override
1229  {
1230  assert(keys.size() == 1);
1231  XOnlyPubKey xpk(keys[0]);
1232  if (!xpk.IsFullyValid()) return {};
1233  WitnessV1Taproot output{xpk};
1234  return Vector(GetScriptForDestination(output));
1235  }
1236 public:
1237  RawTRDescriptor(std::unique_ptr<PubkeyProvider> output_key) : DescriptorImpl(Vector(std::move(output_key)), "rawtr") {}
1238  std::optional<OutputType> GetOutputType() const override { return OutputType::BECH32M; }
1239  bool IsSingleType() const final { return true; }
1240 
1241  std::optional<int64_t> ScriptSize() const override { return 1 + 1 + 32; }
1242 
1243  std::optional<int64_t> MaxSatisfactionWeight(bool) const override {
1244  // We can't know whether there is a script path, so assume key path spend.
1245  return 1 + 65;
1246  }
1247 
1248  std::optional<int64_t> MaxSatisfactionElems() const override {
1249  // See above, we assume keypath spend.
1250  return 1;
1251  }
1252 };
1253 
1255 // Parser //
1257 
1258 enum class ParseScriptContext {
1259  TOP,
1260  P2SH,
1261  P2WPKH,
1262  P2WSH,
1263  P2TR,
1264 };
1265 
1275 [[nodiscard]] bool ParseKeyPath(const std::vector<Span<const char>>& split, KeyPath& out, bool& apostrophe, std::string& error)
1276 {
1277  for (size_t i = 1; i < split.size(); ++i) {
1278  Span<const char> elem = split[i];
1279  bool hardened = false;
1280  if (elem.size() > 0) {
1281  const char last = elem[elem.size() - 1];
1282  if (last == '\'' || last == 'h') {
1283  elem = elem.first(elem.size() - 1);
1284  hardened = true;
1285  apostrophe = last == '\'';
1286  }
1287  }
1288  uint32_t p;
1289  if (!ParseUInt32(std::string(elem.begin(), elem.end()), &p)) {
1290  error = strprintf("Key path value '%s' is not a valid uint32", std::string(elem.begin(), elem.end()));
1291  return false;
1292  } else if (p > 0x7FFFFFFFUL) {
1293  error = strprintf("Key path value %u is out of range", p);
1294  return false;
1295  }
1296  out.push_back(p | (((uint32_t)hardened) << 31));
1297  }
1298  return true;
1299 }
1300 
1302 std::unique_ptr<PubkeyProvider> ParsePubkeyInner(uint32_t key_exp_index, const Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, bool& apostrophe, std::string& error)
1303 {
1304  using namespace spanparsing;
1305 
1306  bool permit_uncompressed = ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH;
1307  auto split = Split(sp, '/');
1308  std::string str(split[0].begin(), split[0].end());
1309  if (str.size() == 0) {
1310  error = "No key provided";
1311  return nullptr;
1312  }
1313  if (split.size() == 1) {
1314  if (IsHex(str)) {
1315  std::vector<unsigned char> data = ParseHex(str);
1316  CPubKey pubkey(data);
1317  if (pubkey.IsValid() && !pubkey.IsValidNonHybrid()) {
1318  error = "Hybrid public keys are not allowed";
1319  return nullptr;
1320  }
1321  if (pubkey.IsFullyValid()) {
1322  if (permit_uncompressed || pubkey.IsCompressed()) {
1323  return std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey, false);
1324  } else {
1325  error = "Uncompressed keys are not allowed";
1326  return nullptr;
1327  }
1328  } else if (data.size() == 32 && ctx == ParseScriptContext::P2TR) {
1329  unsigned char fullkey[33] = {0x02};
1330  std::copy(data.begin(), data.end(), fullkey + 1);
1331  pubkey.Set(std::begin(fullkey), std::end(fullkey));
1332  if (pubkey.IsFullyValid()) {
1333  return std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey, true);
1334  }
1335  }
1336  error = strprintf("Pubkey '%s' is invalid", str);
1337  return nullptr;
1338  }
1339  CKey key = DecodeSecret(str);
1340  if (key.IsValid()) {
1341  if (permit_uncompressed || key.IsCompressed()) {
1342  CPubKey pubkey = key.GetPubKey();
1343  out.keys.emplace(pubkey.GetID(), key);
1344  return std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey, ctx == ParseScriptContext::P2TR);
1345  } else {
1346  error = "Uncompressed keys are not allowed";
1347  return nullptr;
1348  }
1349  }
1350  }
1351  CExtKey extkey = DecodeExtKey(str);
1352  CExtPubKey extpubkey = DecodeExtPubKey(str);
1353  if (!extkey.key.IsValid() && !extpubkey.pubkey.IsValid()) {
1354  error = strprintf("key '%s' is not valid", str);
1355  return nullptr;
1356  }
1357  KeyPath path;
1358  DeriveType type = DeriveType::NO;
1359  if (split.back() == Span{"*"}.first(1)) {
1360  split.pop_back();
1361  type = DeriveType::UNHARDENED;
1362  } else if (split.back() == Span{"*'"}.first(2) || split.back() == Span{"*h"}.first(2)) {
1363  apostrophe = split.back() == Span{"*'"}.first(2);
1364  split.pop_back();
1365  type = DeriveType::HARDENED;
1366  }
1367  if (!ParseKeyPath(split, path, apostrophe, error)) return nullptr;
1368  if (extkey.key.IsValid()) {
1369  extpubkey = extkey.Neuter();
1370  out.keys.emplace(extpubkey.pubkey.GetID(), extkey.key);
1371  }
1372  return std::make_unique<BIP32PubkeyProvider>(key_exp_index, extpubkey, std::move(path), type, apostrophe);
1373 }
1374 
1376 std::unique_ptr<PubkeyProvider> ParsePubkey(uint32_t key_exp_index, const Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error)
1377 {
1378  using namespace spanparsing;
1379 
1380  auto origin_split = Split(sp, ']');
1381  if (origin_split.size() > 2) {
1382  error = "Multiple ']' characters found for a single pubkey";
1383  return nullptr;
1384  }
1385  // This is set if either the origin or path suffix contains a hardened derivation.
1386  bool apostrophe = false;
1387  if (origin_split.size() == 1) {
1388  return ParsePubkeyInner(key_exp_index, origin_split[0], ctx, out, apostrophe, error);
1389  }
1390  if (origin_split[0].empty() || origin_split[0][0] != '[') {
1391  error = strprintf("Key origin start '[ character expected but not found, got '%c' instead",
1392  origin_split[0].empty() ? ']' : origin_split[0][0]);
1393  return nullptr;
1394  }
1395  auto slash_split = Split(origin_split[0].subspan(1), '/');
1396  if (slash_split[0].size() != 8) {
1397  error = strprintf("Fingerprint is not 4 bytes (%u characters instead of 8 characters)", slash_split[0].size());
1398  return nullptr;
1399  }
1400  std::string fpr_hex = std::string(slash_split[0].begin(), slash_split[0].end());
1401  if (!IsHex(fpr_hex)) {
1402  error = strprintf("Fingerprint '%s' is not hex", fpr_hex);
1403  return nullptr;
1404  }
1405  auto fpr_bytes = ParseHex(fpr_hex);
1406  KeyOriginInfo info;
1407  static_assert(sizeof(info.fingerprint) == 4, "Fingerprint must be 4 bytes");
1408  assert(fpr_bytes.size() == 4);
1409  std::copy(fpr_bytes.begin(), fpr_bytes.end(), info.fingerprint);
1410  if (!ParseKeyPath(slash_split, info.path, apostrophe, error)) return nullptr;
1411  auto provider = ParsePubkeyInner(key_exp_index, origin_split[1], ctx, out, apostrophe, error);
1412  if (!provider) return nullptr;
1413  return std::make_unique<OriginPubkeyProvider>(key_exp_index, std::move(info), std::move(provider), apostrophe);
1414 }
1415 
1416 std::unique_ptr<PubkeyProvider> InferPubkey(const CPubKey& pubkey, ParseScriptContext ctx, const SigningProvider& provider)
1417 {
1418  // Key cannot be hybrid
1419  if (!pubkey.IsValidNonHybrid()) {
1420  return nullptr;
1421  }
1422  // Uncompressed is only allowed in TOP and P2SH contexts
1423  if (ctx != ParseScriptContext::TOP && ctx != ParseScriptContext::P2SH && !pubkey.IsCompressed()) {
1424  return nullptr;
1425  }
1426  std::unique_ptr<PubkeyProvider> key_provider = std::make_unique<ConstPubkeyProvider>(0, pubkey, false);
1427  KeyOriginInfo info;
1428  if (provider.GetKeyOrigin(pubkey.GetID(), info)) {
1429  return std::make_unique<OriginPubkeyProvider>(0, std::move(info), std::move(key_provider), /*apostrophe=*/false);
1430  }
1431  return key_provider;
1432 }
1433 
1434 std::unique_ptr<PubkeyProvider> InferXOnlyPubkey(const XOnlyPubKey& xkey, ParseScriptContext ctx, const SigningProvider& provider)
1435 {
1436  CPubKey pubkey{xkey.GetEvenCorrespondingCPubKey()};
1437  std::unique_ptr<PubkeyProvider> key_provider = std::make_unique<ConstPubkeyProvider>(0, pubkey, true);
1438  KeyOriginInfo info;
1439  if (provider.GetKeyOriginByXOnly(xkey, info)) {
1440  return std::make_unique<OriginPubkeyProvider>(0, std::move(info), std::move(key_provider), /*apostrophe=*/false);
1441  }
1442  return key_provider;
1443 }
1444 
1448 struct KeyParser {
1450  using Key = uint32_t;
1452  FlatSigningProvider* m_out;
1454  const SigningProvider* m_in;
1456  mutable std::vector<std::unique_ptr<PubkeyProvider>> m_keys;
1458  mutable std::string m_key_parsing_error;
1460  const miniscript::MiniscriptContext m_script_ctx;
1462  uint32_t m_offset;
1463 
1465  miniscript::MiniscriptContext ctx, uint32_t offset = 0)
1466  : m_out(out), m_in(in), m_script_ctx(ctx), m_offset(offset) {}
1467 
1468  bool KeyCompare(const Key& a, const Key& b) const {
1469  return *m_keys.at(a) < *m_keys.at(b);
1470  }
1471 
1472  ParseScriptContext ParseContext() const {
1473  switch (m_script_ctx) {
1474  case miniscript::MiniscriptContext::P2WSH: return ParseScriptContext::P2WSH;
1475  case miniscript::MiniscriptContext::TAPSCRIPT: return ParseScriptContext::P2TR;
1476  }
1477  assert(false);
1478  }
1479 
1480  template<typename I> std::optional<Key> FromString(I begin, I end) const
1481  {
1482  assert(m_out);
1483  Key key = m_keys.size();
1484  auto pk = ParsePubkey(m_offset + key, {&*begin, &*end}, ParseContext(), *m_out, m_key_parsing_error);
1485  if (!pk) return {};
1486  m_keys.push_back(std::move(pk));
1487  return key;
1488  }
1489 
1490  std::optional<std::string> ToString(const Key& key) const
1491  {
1492  return m_keys.at(key)->ToString();
1493  }
1494 
1495  template<typename I> std::optional<Key> FromPKBytes(I begin, I end) const
1496  {
1497  assert(m_in);
1498  Key key = m_keys.size();
1499  if (miniscript::IsTapscript(m_script_ctx) && end - begin == 32) {
1500  XOnlyPubKey pubkey;
1501  std::copy(begin, end, pubkey.begin());
1502  if (auto pubkey_provider = InferPubkey(pubkey.GetEvenCorrespondingCPubKey(), ParseContext(), *m_in)) {
1503  m_keys.push_back(std::move(pubkey_provider));
1504  return key;
1505  }
1506  } else if (!miniscript::IsTapscript(m_script_ctx)) {
1507  CPubKey pubkey(begin, end);
1508  if (auto pubkey_provider = InferPubkey(pubkey, ParseContext(), *m_in)) {
1509  m_keys.push_back(std::move(pubkey_provider));
1510  return key;
1511  }
1512  }
1513  return {};
1514  }
1515 
1516  template<typename I> std::optional<Key> FromPKHBytes(I begin, I end) const
1517  {
1518  assert(end - begin == 20);
1519  assert(m_in);
1520  uint160 hash;
1521  std::copy(begin, end, hash.begin());
1522  CKeyID keyid(hash);
1523  CPubKey pubkey;
1524  if (m_in->GetPubKey(keyid, pubkey)) {
1525  if (auto pubkey_provider = InferPubkey(pubkey, ParseContext(), *m_in)) {
1526  Key key = m_keys.size();
1527  m_keys.push_back(std::move(pubkey_provider));
1528  return key;
1529  }
1530  }
1531  return {};
1532  }
1533 
1534  miniscript::MiniscriptContext MsContext() const {
1535  return m_script_ctx;
1536  }
1537 };
1538 
1540 std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error)
1541 {
1542  using namespace spanparsing;
1543 
1544  auto expr = Expr(sp);
1545  if (Func("pk", expr)) {
1546  auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error);
1547  if (!pubkey) {
1548  error = strprintf("pk(): %s", error);
1549  return nullptr;
1550  }
1551  ++key_exp_index;
1552  return std::make_unique<PKDescriptor>(std::move(pubkey), ctx == ParseScriptContext::P2TR);
1553  }
1554  if ((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH) && Func("pkh", expr)) {
1555  auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error);
1556  if (!pubkey) {
1557  error = strprintf("pkh(): %s", error);
1558  return nullptr;
1559  }
1560  ++key_exp_index;
1561  return std::make_unique<PKHDescriptor>(std::move(pubkey));
1562  } else if (ctx != ParseScriptContext::P2TR && Func("pkh", expr)) {
1563  // Under Taproot, always the Miniscript parser deal with it.
1564  error = "Can only have pkh at top level, in sh(), wsh(), or in tr()";
1565  return nullptr;
1566  }
1567  if (ctx == ParseScriptContext::TOP && Func("combo", expr)) {
1568  auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error);
1569  if (!pubkey) {
1570  error = strprintf("combo(): %s", error);
1571  return nullptr;
1572  }
1573  ++key_exp_index;
1574  return std::make_unique<ComboDescriptor>(std::move(pubkey));
1575  } else if (Func("combo", expr)) {
1576  error = "Can only have combo() at top level";
1577  return nullptr;
1578  }
1579  const bool multi = Func("multi", expr);
1580  const bool sortedmulti = !multi && Func("sortedmulti", expr);
1581  const bool multi_a = !(multi || sortedmulti) && Func("multi_a", expr);
1582  const bool sortedmulti_a = !(multi || sortedmulti || multi_a) && Func("sortedmulti_a", expr);
1583  if (((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH) && (multi || sortedmulti)) ||
1584  (ctx == ParseScriptContext::P2TR && (multi_a || sortedmulti_a))) {
1585  auto threshold = Expr(expr);
1586  uint32_t thres;
1587  std::vector<std::unique_ptr<PubkeyProvider>> providers;
1588  if (!ParseUInt32(std::string(threshold.begin(), threshold.end()), &thres)) {
1589  error = strprintf("Multi threshold '%s' is not valid", std::string(threshold.begin(), threshold.end()));
1590  return nullptr;
1591  }
1592  size_t script_size = 0;
1593  while (expr.size()) {
1594  if (!Const(",", expr)) {
1595  error = strprintf("Multi: expected ',', got '%c'", expr[0]);
1596  return nullptr;
1597  }
1598  auto arg = Expr(expr);
1599  auto pk = ParsePubkey(key_exp_index, arg, ctx, out, error);
1600  if (!pk) {
1601  error = strprintf("Multi: %s", error);
1602  return nullptr;
1603  }
1604  script_size += pk->GetSize() + 1;
1605  providers.emplace_back(std::move(pk));
1606  key_exp_index++;
1607  }
1608  if ((multi || sortedmulti) && (providers.empty() || providers.size() > MAX_PUBKEYS_PER_MULTISIG)) {
1609  error = strprintf("Cannot have %u keys in multisig; must have between 1 and %d keys, inclusive", providers.size(), MAX_PUBKEYS_PER_MULTISIG);
1610  return nullptr;
1611  } else if ((multi_a || sortedmulti_a) && (providers.empty() || providers.size() > MAX_PUBKEYS_PER_MULTI_A)) {
1612  error = strprintf("Cannot have %u keys in multi_a; must have between 1 and %d keys, inclusive", providers.size(), MAX_PUBKEYS_PER_MULTI_A);
1613  return nullptr;
1614  } else if (thres < 1) {
1615  error = strprintf("Multisig threshold cannot be %d, must be at least 1", thres);
1616  return nullptr;
1617  } else if (thres > providers.size()) {
1618  error = strprintf("Multisig threshold cannot be larger than the number of keys; threshold is %d but only %u keys specified", thres, providers.size());
1619  return nullptr;
1620  }
1621  if (ctx == ParseScriptContext::TOP) {
1622  if (providers.size() > 3) {
1623  error = strprintf("Cannot have %u pubkeys in bare multisig; only at most 3 pubkeys", providers.size());
1624  return nullptr;
1625  }
1626  }
1627  if (ctx == ParseScriptContext::P2SH) {
1628  // This limits the maximum number of compressed pubkeys to 15.
1629  if (script_size + 3 > MAX_SCRIPT_ELEMENT_SIZE) {
1630  error = strprintf("P2SH script is too large, %d bytes is larger than %d bytes", script_size + 3, MAX_SCRIPT_ELEMENT_SIZE);
1631  return nullptr;
1632  }
1633  }
1634  if (multi || sortedmulti) {
1635  return std::make_unique<MultisigDescriptor>(thres, std::move(providers), sortedmulti);
1636  } else {
1637  return std::make_unique<MultiADescriptor>(thres, std::move(providers), sortedmulti_a);
1638  }
1639  } else if (multi || sortedmulti) {
1640  error = "Can only have multi/sortedmulti at top level, in sh(), or in wsh()";
1641  return nullptr;
1642  } else if (multi_a || sortedmulti_a) {
1643  error = "Can only have multi_a/sortedmulti_a inside tr()";
1644  return nullptr;
1645  }
1646  if ((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH) && Func("wpkh", expr)) {
1647  auto pubkey = ParsePubkey(key_exp_index, expr, ParseScriptContext::P2WPKH, out, error);
1648  if (!pubkey) {
1649  error = strprintf("wpkh(): %s", error);
1650  return nullptr;
1651  }
1652  key_exp_index++;
1653  return std::make_unique<WPKHDescriptor>(std::move(pubkey));
1654  } else if (Func("wpkh", expr)) {
1655  error = "Can only have wpkh() at top level or inside sh()";
1656  return nullptr;
1657  }
1658  if (ctx == ParseScriptContext::TOP && Func("sh", expr)) {
1659  auto desc = ParseScript(key_exp_index, expr, ParseScriptContext::P2SH, out, error);
1660  if (!desc || expr.size()) return nullptr;
1661  return std::make_unique<SHDescriptor>(std::move(desc));
1662  } else if (Func("sh", expr)) {
1663  error = "Can only have sh() at top level";
1664  return nullptr;
1665  }
1666  if ((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH) && Func("wsh", expr)) {
1667  auto desc = ParseScript(key_exp_index, expr, ParseScriptContext::P2WSH, out, error);
1668  if (!desc || expr.size()) return nullptr;
1669  return std::make_unique<WSHDescriptor>(std::move(desc));
1670  } else if (Func("wsh", expr)) {
1671  error = "Can only have wsh() at top level or inside sh()";
1672  return nullptr;
1673  }
1674  if (ctx == ParseScriptContext::TOP && Func("addr", expr)) {
1675  CTxDestination dest = DecodeDestination(std::string(expr.begin(), expr.end()));
1676  if (!IsValidDestination(dest)) {
1677  error = "Address is not valid";
1678  return nullptr;
1679  }
1680  return std::make_unique<AddressDescriptor>(std::move(dest));
1681  } else if (Func("addr", expr)) {
1682  error = "Can only have addr() at top level";
1683  return nullptr;
1684  }
1685  if (ctx == ParseScriptContext::TOP && Func("tr", expr)) {
1686  auto arg = Expr(expr);
1687  auto internal_key = ParsePubkey(key_exp_index, arg, ParseScriptContext::P2TR, out, error);
1688  if (!internal_key) {
1689  error = strprintf("tr(): %s", error);
1690  return nullptr;
1691  }
1692  ++key_exp_index;
1693  std::vector<std::unique_ptr<DescriptorImpl>> subscripts;
1694  std::vector<int> depths;
1695  if (expr.size()) {
1696  if (!Const(",", expr)) {
1697  error = strprintf("tr: expected ',', got '%c'", expr[0]);
1698  return nullptr;
1699  }
1703  std::vector<bool> branches;
1704  // Loop over all provided scripts. In every iteration exactly one script will be processed.
1705  // Use a do-loop because inside this if-branch we expect at least one script.
1706  do {
1707  // First process all open braces.
1708  while (Const("{", expr)) {
1709  branches.push_back(false); // new left branch
1710  if (branches.size() > TAPROOT_CONTROL_MAX_NODE_COUNT) {
1711  error = strprintf("tr() supports at most %i nesting levels", TAPROOT_CONTROL_MAX_NODE_COUNT);
1712  return nullptr;
1713  }
1714  }
1715  // Process the actual script expression.
1716  auto sarg = Expr(expr);
1717  subscripts.emplace_back(ParseScript(key_exp_index, sarg, ParseScriptContext::P2TR, out, error));
1718  if (!subscripts.back()) return nullptr;
1719  depths.push_back(branches.size());
1720  // Process closing braces; one is expected for every right branch we were in.
1721  while (branches.size() && branches.back()) {
1722  if (!Const("}", expr)) {
1723  error = strprintf("tr(): expected '}' after script expression");
1724  return nullptr;
1725  }
1726  branches.pop_back(); // move up one level after encountering '}'
1727  }
1728  // If after that, we're at the end of a left branch, expect a comma.
1729  if (branches.size() && !branches.back()) {
1730  if (!Const(",", expr)) {
1731  error = strprintf("tr(): expected ',' after script expression");
1732  return nullptr;
1733  }
1734  branches.back() = true; // And now we're in a right branch.
1735  }
1736  } while (branches.size());
1737  // After we've explored a whole tree, we must be at the end of the expression.
1738  if (expr.size()) {
1739  error = strprintf("tr(): expected ')' after script expression");
1740  return nullptr;
1741  }
1742  }
1744  return std::make_unique<TRDescriptor>(std::move(internal_key), std::move(subscripts), std::move(depths));
1745  } else if (Func("tr", expr)) {
1746  error = "Can only have tr at top level";
1747  return nullptr;
1748  }
1749  if (ctx == ParseScriptContext::TOP && Func("rawtr", expr)) {
1750  auto arg = Expr(expr);
1751  if (expr.size()) {
1752  error = strprintf("rawtr(): only one key expected.");
1753  return nullptr;
1754  }
1755  auto output_key = ParsePubkey(key_exp_index, arg, ParseScriptContext::P2TR, out, error);
1756  if (!output_key) return nullptr;
1757  ++key_exp_index;
1758  return std::make_unique<RawTRDescriptor>(std::move(output_key));
1759  } else if (Func("rawtr", expr)) {
1760  error = "Can only have rawtr at top level";
1761  return nullptr;
1762  }
1763  if (ctx == ParseScriptContext::TOP && Func("raw", expr)) {
1764  std::string str(expr.begin(), expr.end());
1765  if (!IsHex(str)) {
1766  error = "Raw script is not hex";
1767  return nullptr;
1768  }
1769  auto bytes = ParseHex(str);
1770  return std::make_unique<RawDescriptor>(CScript(bytes.begin(), bytes.end()));
1771  } else if (Func("raw", expr)) {
1772  error = "Can only have raw() at top level";
1773  return nullptr;
1774  }
1775  // Process miniscript expressions.
1776  {
1777  const auto script_ctx{ctx == ParseScriptContext::P2WSH ? miniscript::MiniscriptContext::P2WSH : miniscript::MiniscriptContext::TAPSCRIPT};
1778  KeyParser parser(/*out = */&out, /* in = */nullptr, /* ctx = */script_ctx, key_exp_index);
1779  auto node = miniscript::FromString(std::string(expr.begin(), expr.end()), parser);
1780  if (node) {
1781  if (ctx != ParseScriptContext::P2WSH && ctx != ParseScriptContext::P2TR) {
1782  error = "Miniscript expressions can only be used in wsh or tr.";
1783  return nullptr;
1784  }
1785  if (parser.m_key_parsing_error != "") {
1786  error = std::move(parser.m_key_parsing_error);
1787  return nullptr;
1788  }
1789  if (!node->IsSane() || node->IsNotSatisfiable()) {
1790  // Try to find the first insane sub for better error reporting.
1791  auto insane_node = node.get();
1792  if (const auto sub = node->FindInsaneSub()) insane_node = sub;
1793  if (const auto str = insane_node->ToString(parser)) error = *str;
1794  if (!insane_node->IsValid()) {
1795  error += " is invalid";
1796  } else if (!node->IsSane()) {
1797  error += " is not sane";
1798  if (!insane_node->IsNonMalleable()) {
1799  error += ": malleable witnesses exist";
1800  } else if (insane_node == node.get() && !insane_node->NeedsSignature()) {
1801  error += ": witnesses without signature exist";
1802  } else if (!insane_node->CheckTimeLocksMix()) {
1803  error += ": contains mixes of timelocks expressed in blocks and seconds";
1804  } else if (!insane_node->CheckDuplicateKey()) {
1805  error += ": contains duplicate public keys";
1806  } else if (!insane_node->ValidSatisfactions()) {
1807  error += ": needs witnesses that may exceed resource limits";
1808  }
1809  } else {
1810  error += " is not satisfiable";
1811  }
1812  return nullptr;
1813  }
1814  // A signature check is required for a miniscript to be sane. Therefore no sane miniscript
1815  // may have an empty list of public keys.
1816  CHECK_NONFATAL(!parser.m_keys.empty());
1817  key_exp_index += parser.m_keys.size();
1818  return std::make_unique<MiniscriptDescriptor>(std::move(parser.m_keys), std::move(node));
1819  }
1820  }
1821  if (ctx == ParseScriptContext::P2SH) {
1822  error = "A function is needed within P2SH";
1823  return nullptr;
1824  } else if (ctx == ParseScriptContext::P2WSH) {
1825  error = "A function is needed within P2WSH";
1826  return nullptr;
1827  }
1828  error = strprintf("'%s' is not a valid descriptor function", std::string(expr.begin(), expr.end()));
1829  return nullptr;
1830 }
1831 
1832 std::unique_ptr<DescriptorImpl> InferMultiA(const CScript& script, ParseScriptContext ctx, const SigningProvider& provider)
1833 {
1834  auto match = MatchMultiA(script);
1835  if (!match) return {};
1836  std::vector<std::unique_ptr<PubkeyProvider>> keys;
1837  keys.reserve(match->second.size());
1838  for (const auto keyspan : match->second) {
1839  if (keyspan.size() != 32) return {};
1840  auto key = InferXOnlyPubkey(XOnlyPubKey{keyspan}, ctx, provider);
1841  if (!key) return {};
1842  keys.push_back(std::move(key));
1843  }
1844  return std::make_unique<MultiADescriptor>(match->first, std::move(keys));
1845 }
1846 
1847 std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptContext ctx, const SigningProvider& provider)
1848 {
1849  if (ctx == ParseScriptContext::P2TR && script.size() == 34 && script[0] == 32 && script[33] == OP_CHECKSIG) {
1850  XOnlyPubKey key{Span{script}.subspan(1, 32)};
1851  return std::make_unique<PKDescriptor>(InferXOnlyPubkey(key, ctx, provider), true);
1852  }
1853 
1854  if (ctx == ParseScriptContext::P2TR) {
1855  auto ret = InferMultiA(script, ctx, provider);
1856  if (ret) return ret;
1857  }
1858 
1859  std::vector<std::vector<unsigned char>> data;
1860  TxoutType txntype = Solver(script, data);
1861 
1862  if (txntype == TxoutType::PUBKEY && (ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH)) {
1863  CPubKey pubkey(data[0]);
1864  if (auto pubkey_provider = InferPubkey(pubkey, ctx, provider)) {
1865  return std::make_unique<PKDescriptor>(std::move(pubkey_provider));
1866  }
1867  }
1868  if (txntype == TxoutType::PUBKEYHASH && (ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH)) {
1869  uint160 hash(data[0]);
1870  CKeyID keyid(hash);
1871  CPubKey pubkey;
1872  if (provider.GetPubKey(keyid, pubkey)) {
1873  if (auto pubkey_provider = InferPubkey(pubkey, ctx, provider)) {
1874  return std::make_unique<PKHDescriptor>(std::move(pubkey_provider));
1875  }
1876  }
1877  }
1878  if (txntype == TxoutType::WITNESS_V0_KEYHASH && (ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH)) {
1879  uint160 hash(data[0]);
1880  CKeyID keyid(hash);
1881  CPubKey pubkey;
1882  if (provider.GetPubKey(keyid, pubkey)) {
1883  if (auto pubkey_provider = InferPubkey(pubkey, ParseScriptContext::P2WPKH, provider)) {
1884  return std::make_unique<WPKHDescriptor>(std::move(pubkey_provider));
1885  }
1886  }
1887  }
1888  if (txntype == TxoutType::MULTISIG && (ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH)) {
1889  bool ok = true;
1890  std::vector<std::unique_ptr<PubkeyProvider>> providers;
1891  for (size_t i = 1; i + 1 < data.size(); ++i) {
1892  CPubKey pubkey(data[i]);
1893  if (auto pubkey_provider = InferPubkey(pubkey, ctx, provider)) {
1894  providers.push_back(std::move(pubkey_provider));
1895  } else {
1896  ok = false;
1897  break;
1898  }
1899  }
1900  if (ok) return std::make_unique<MultisigDescriptor>((int)data[0][0], std::move(providers));
1901  }
1902  if (txntype == TxoutType::SCRIPTHASH && ctx == ParseScriptContext::TOP) {
1903  uint160 hash(data[0]);
1904  CScriptID scriptid(hash);
1905  CScript subscript;
1906  if (provider.GetCScript(scriptid, subscript)) {
1907  auto sub = InferScript(subscript, ParseScriptContext::P2SH, provider);
1908  if (sub) return std::make_unique<SHDescriptor>(std::move(sub));
1909  }
1910  }
1911  if (txntype == TxoutType::WITNESS_V0_SCRIPTHASH && (ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH)) {
1912  CScriptID scriptid{RIPEMD160(data[0])};
1913  CScript subscript;
1914  if (provider.GetCScript(scriptid, subscript)) {
1915  auto sub = InferScript(subscript, ParseScriptContext::P2WSH, provider);
1916  if (sub) return std::make_unique<WSHDescriptor>(std::move(sub));
1917  }
1918  }
1919  if (txntype == TxoutType::WITNESS_V1_TAPROOT && ctx == ParseScriptContext::TOP) {
1920  // Extract x-only pubkey from output.
1921  XOnlyPubKey pubkey;
1922  std::copy(data[0].begin(), data[0].end(), pubkey.begin());
1923  // Request spending data.
1924  TaprootSpendData tap;
1925  if (provider.GetTaprootSpendData(pubkey, tap)) {
1926  // If found, convert it back to tree form.
1927  auto tree = InferTaprootTree(tap, pubkey);
1928  if (tree) {
1929  // If that works, try to infer subdescriptors for all leaves.
1930  bool ok = true;
1931  std::vector<std::unique_ptr<DescriptorImpl>> subscripts;
1932  std::vector<int> depths;
1933  for (const auto& [depth, script, leaf_ver] : *tree) {
1934  std::unique_ptr<DescriptorImpl> subdesc;
1935  if (leaf_ver == TAPROOT_LEAF_TAPSCRIPT) {
1936  subdesc = InferScript(CScript(script.begin(), script.end()), ParseScriptContext::P2TR, provider);
1937  }
1938  if (!subdesc) {
1939  ok = false;
1940  break;
1941  } else {
1942  subscripts.push_back(std::move(subdesc));
1943  depths.push_back(depth);
1944  }
1945  }
1946  if (ok) {
1947  auto key = InferXOnlyPubkey(tap.internal_key, ParseScriptContext::P2TR, provider);
1948  return std::make_unique<TRDescriptor>(std::move(key), std::move(subscripts), std::move(depths));
1949  }
1950  }
1951  }
1952  // If the above doesn't work, construct a rawtr() descriptor with just the encoded x-only pubkey.
1953  if (pubkey.IsFullyValid()) {
1954  auto key = InferXOnlyPubkey(pubkey, ParseScriptContext::P2TR, provider);
1955  if (key) {
1956  return std::make_unique<RawTRDescriptor>(std::move(key));
1957  }
1958  }
1959  }
1960 
1961  if (ctx == ParseScriptContext::P2WSH || ctx == ParseScriptContext::P2TR) {
1962  const auto script_ctx{ctx == ParseScriptContext::P2WSH ? miniscript::MiniscriptContext::P2WSH : miniscript::MiniscriptContext::TAPSCRIPT};
1963  KeyParser parser(/* out = */nullptr, /* in = */&provider, /* ctx = */script_ctx);
1964  auto node = miniscript::FromScript(script, parser);
1965  if (node && node->IsSane()) {
1966  return std::make_unique<MiniscriptDescriptor>(std::move(parser.m_keys), std::move(node));
1967  }
1968  }
1969 
1970  // The following descriptors are all top-level only descriptors.
1971  // So if we are not at the top level, return early.
1972  if (ctx != ParseScriptContext::TOP) return nullptr;
1973 
1974  CTxDestination dest;
1975  if (ExtractDestination(script, dest)) {
1976  if (GetScriptForDestination(dest) == script) {
1977  return std::make_unique<AddressDescriptor>(std::move(dest));
1978  }
1979  }
1980 
1981  return std::make_unique<RawDescriptor>(script);
1982 }
1983 
1984 
1985 } // namespace
1986 
1988 bool CheckChecksum(Span<const char>& sp, bool require_checksum, std::string& error, std::string* out_checksum = nullptr)
1989 {
1990  using namespace spanparsing;
1991 
1992  auto check_split = Split(sp, '#');
1993  if (check_split.size() > 2) {
1994  error = "Multiple '#' symbols";
1995  return false;
1996  }
1997  if (check_split.size() == 1 && require_checksum){
1998  error = "Missing checksum";
1999  return false;
2000  }
2001  if (check_split.size() == 2) {
2002  if (check_split[1].size() != 8) {
2003  error = strprintf("Expected 8 character checksum, not %u characters", check_split[1].size());
2004  return false;
2005  }
2006  }
2007  auto checksum = DescriptorChecksum(check_split[0]);
2008  if (checksum.empty()) {
2009  error = "Invalid characters in payload";
2010  return false;
2011  }
2012  if (check_split.size() == 2) {
2013  if (!std::equal(checksum.begin(), checksum.end(), check_split[1].begin())) {
2014  error = strprintf("Provided checksum '%s' does not match computed checksum '%s'", std::string(check_split[1].begin(), check_split[1].end()), checksum);
2015  return false;
2016  }
2017  }
2018  if (out_checksum) *out_checksum = std::move(checksum);
2019  sp = check_split[0];
2020  return true;
2021 }
2022 
2023 std::unique_ptr<Descriptor> Parse(const std::string& descriptor, FlatSigningProvider& out, std::string& error, bool require_checksum)
2024 {
2025  Span<const char> sp{descriptor};
2026  if (!CheckChecksum(sp, require_checksum, error)) return nullptr;
2027  uint32_t key_exp_index = 0;
2028  auto ret = ParseScript(key_exp_index, sp, ParseScriptContext::TOP, out, error);
2029  if (sp.size() == 0 && ret) return std::unique_ptr<Descriptor>(std::move(ret));
2030  return nullptr;
2031 }
2032 
2033 std::string GetDescriptorChecksum(const std::string& descriptor)
2034 {
2035  std::string ret;
2036  std::string error;
2037  Span<const char> sp{descriptor};
2038  if (!CheckChecksum(sp, false, error, &ret)) return "";
2039  return ret;
2040 }
2041 
2042 std::unique_ptr<Descriptor> InferDescriptor(const CScript& script, const SigningProvider& provider)
2043 {
2044  return InferScript(script, ParseScriptContext::TOP, provider);
2045 }
2046 
2048 {
2049  std::string desc_str = desc.ToString(/*compat_format=*/true);
2050  uint256 id;
2051  CSHA256().Write((unsigned char*)desc_str.data(), desc_str.size()).Finalize(id.begin());
2052  return id;
2053 }
2054 
2055 void DescriptorCache::CacheParentExtPubKey(uint32_t key_exp_pos, const CExtPubKey& xpub)
2056 {
2057  m_parent_xpubs[key_exp_pos] = xpub;
2058 }
2059 
2060 void DescriptorCache::CacheDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index, const CExtPubKey& xpub)
2061 {
2062  auto& xpubs = m_derived_xpubs[key_exp_pos];
2063  xpubs[der_index] = xpub;
2064 }
2065 
2066 void DescriptorCache::CacheLastHardenedExtPubKey(uint32_t key_exp_pos, const CExtPubKey& xpub)
2067 {
2068  m_last_hardened_xpubs[key_exp_pos] = xpub;
2069 }
2070 
2071 bool DescriptorCache::GetCachedParentExtPubKey(uint32_t key_exp_pos, CExtPubKey& xpub) const
2072 {
2073  const auto& it = m_parent_xpubs.find(key_exp_pos);
2074  if (it == m_parent_xpubs.end()) return false;
2075  xpub = it->second;
2076  return true;
2077 }
2078 
2079 bool DescriptorCache::GetCachedDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index, CExtPubKey& xpub) const
2080 {
2081  const auto& key_exp_it = m_derived_xpubs.find(key_exp_pos);
2082  if (key_exp_it == m_derived_xpubs.end()) return false;
2083  const auto& der_it = key_exp_it->second.find(der_index);
2084  if (der_it == key_exp_it->second.end()) return false;
2085  xpub = der_it->second;
2086  return true;
2087 }
2088 
2089 bool DescriptorCache::GetCachedLastHardenedExtPubKey(uint32_t key_exp_pos, CExtPubKey& xpub) const
2090 {
2091  const auto& it = m_last_hardened_xpubs.find(key_exp_pos);
2092  if (it == m_last_hardened_xpubs.end()) return false;
2093  xpub = it->second;
2094  return true;
2095 }
2096 
2098 {
2099  DescriptorCache diff;
2100  for (const auto& parent_xpub_pair : other.GetCachedParentExtPubKeys()) {
2101  CExtPubKey xpub;
2102  if (GetCachedParentExtPubKey(parent_xpub_pair.first, xpub)) {
2103  if (xpub != parent_xpub_pair.second) {
2104  throw std::runtime_error(std::string(__func__) + ": New cached parent xpub does not match already cached parent xpub");
2105  }
2106  continue;
2107  }
2108  CacheParentExtPubKey(parent_xpub_pair.first, parent_xpub_pair.second);
2109  diff.CacheParentExtPubKey(parent_xpub_pair.first, parent_xpub_pair.second);
2110  }
2111  for (const auto& derived_xpub_map_pair : other.GetCachedDerivedExtPubKeys()) {
2112  for (const auto& derived_xpub_pair : derived_xpub_map_pair.second) {
2113  CExtPubKey xpub;
2114  if (GetCachedDerivedExtPubKey(derived_xpub_map_pair.first, derived_xpub_pair.first, xpub)) {
2115  if (xpub != derived_xpub_pair.second) {
2116  throw std::runtime_error(std::string(__func__) + ": New cached derived xpub does not match already cached derived xpub");
2117  }
2118  continue;
2119  }
2120  CacheDerivedExtPubKey(derived_xpub_map_pair.first, derived_xpub_pair.first, derived_xpub_pair.second);
2121  diff.CacheDerivedExtPubKey(derived_xpub_map_pair.first, derived_xpub_pair.first, derived_xpub_pair.second);
2122  }
2123  }
2124  for (const auto& lh_xpub_pair : other.GetCachedLastHardenedExtPubKeys()) {
2125  CExtPubKey xpub;
2126  if (GetCachedLastHardenedExtPubKey(lh_xpub_pair.first, xpub)) {
2127  if (xpub != lh_xpub_pair.second) {
2128  throw std::runtime_error(std::string(__func__) + ": New cached last hardened xpub does not match already cached last hardened xpub");
2129  }
2130  continue;
2131  }
2132  CacheLastHardenedExtPubKey(lh_xpub_pair.first, lh_xpub_pair.second);
2133  diff.CacheLastHardenedExtPubKey(lh_xpub_pair.first, lh_xpub_pair.second);
2134  }
2135  return diff;
2136 }
2137 
2139 {
2140  return m_parent_xpubs;
2141 }
2142 
2143 std::unordered_map<uint32_t, ExtPubKeyMap> DescriptorCache::GetCachedDerivedExtPubKeys() const
2144 {
2145  return m_derived_xpubs;
2146 }
2147 
2149 {
2150  return m_last_hardened_xpubs;
2151 }
bool ExtractDestination(const CScript &scriptPubKey, CTxDestination &addressRet)
Parse a scriptPubKey for the destination.
Definition: addresstype.cpp:49
bool IsValidDestination(const CTxDestination &dest)
Check whether a CTxDestination corresponds to one with an address.
CScript GetScriptForDestination(const CTxDestination &dest)
Generate a Bitcoin scriptPubKey for the given CTxDestination.
std::variant< CNoDestination, PubKeyDestination, PKHash, ScriptHash, WitnessV0ScriptHash, WitnessV0KeyHash, WitnessV1Taproot, WitnessUnknown > CTxDestination
A txout script categorized into standard templates.
Definition: addresstype.h:131
#define LIFETIMEBOUND
Definition: attributes.h:16
std::string FormatHDKeypath(const std::vector< uint32_t > &path, bool apostrophe)
Definition: bip32.cpp:54
int ret
node::NodeContext m_node
Definition: bitcoin-gui.cpp:37
#define CHECK_NONFATAL(condition)
Identity function.
Definition: check.h:72
An encapsulated private key.
Definition: key.h:33
unsigned int size() const
Simple read-only vector-like interface.
Definition: key.h:113
bool IsValid() const
Check whether this private key is valid.
Definition: key.h:119
bool IsCompressed() const
Check whether the public key corresponding to this private key is (to be) compressed.
Definition: key.h:122
CPubKey GetPubKey() const
Compute the public key from a private key.
Definition: key.cpp:188
A reference to a CKey: the Hash160 of its serialized public key.
Definition: pubkey.h:24
An encapsulated public key.
Definition: pubkey.h:34
bool IsCompressed() const
Check whether this is a compressed public key.
Definition: pubkey.h:204
CKeyID GetID() const
Get the KeyID of this public key (hash of its serialization)
Definition: pubkey.h:164
bool IsValid() const
Definition: pubkey.h:189
bool IsValidNonHybrid() const noexcept
Check if a public key is a syntactically valid compressed or uncompressed key.
Definition: pubkey.h:195
A hasher class for SHA-256.
Definition: sha256.h:14
void Finalize(unsigned char hash[OUTPUT_SIZE])
Definition: sha256.cpp:720
CSHA256 & Write(const unsigned char *data, size_t len)
Definition: sha256.cpp:694
Serialized script, used inside transaction inputs and outputs.
Definition: script.h:414
A reference to a CScript: the Hash160 of its serialization.
Definition: script.h:583
Cache for single descriptor's derived extended pubkeys.
Definition: descriptor.h:19
bool GetCachedParentExtPubKey(uint32_t key_exp_pos, CExtPubKey &xpub) const
Retrieve a cached parent xpub.
std::unordered_map< uint32_t, ExtPubKeyMap > GetCachedDerivedExtPubKeys() const
Retrieve all cached derived xpubs.
ExtPubKeyMap m_last_hardened_xpubs
Map key expression index -> last hardened xpub.
Definition: descriptor.h:26
void CacheDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index, const CExtPubKey &xpub)
Cache an xpub derived at an index.
DescriptorCache MergeAndDiff(const DescriptorCache &other)
Combine another DescriptorCache into this one.
ExtPubKeyMap GetCachedParentExtPubKeys() const
Retrieve all cached parent xpubs.
ExtPubKeyMap GetCachedLastHardenedExtPubKeys() const
Retrieve all cached last hardened xpubs.
void CacheParentExtPubKey(uint32_t key_exp_pos, const CExtPubKey &xpub)
Cache a parent xpub.
void CacheLastHardenedExtPubKey(uint32_t key_exp_pos, const CExtPubKey &xpub)
Cache a last hardened xpub.
bool GetCachedDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index, CExtPubKey &xpub) const
Retrieve a cached xpub derived at an index.
std::unordered_map< uint32_t, ExtPubKeyMap > m_derived_xpubs
Map key expression index -> map of (key derivation index -> xpub)
Definition: descriptor.h:22
bool GetCachedLastHardenedExtPubKey(uint32_t key_exp_pos, CExtPubKey &xpub) const
Retrieve a cached last hardened xpub.
ExtPubKeyMap m_parent_xpubs
Map key expression index -> parent xpub.
Definition: descriptor.h:24
An interface to be implemented by keystores that support signing.
virtual bool GetCScript(const CScriptID &scriptid, CScript &script) const
virtual bool GetTaprootSpendData(const XOnlyPubKey &output_key, TaprootSpendData &spenddata) const
virtual bool GetPubKey(const CKeyID &address, CPubKey &pubkey) const
bool GetKeyOriginByXOnly(const XOnlyPubKey &pubkey, KeyOriginInfo &info) const
virtual bool GetKey(const CKeyID &address, CKey &key) const
virtual bool GetKeyOrigin(const CKeyID &keyid, KeyOriginInfo &info) const
A Span is an object that can refer to a contiguous sequence of objects.
Definition: span.h:97
constexpr std::size_t size() const noexcept
Definition: span.h:186
constexpr C * end() const noexcept
Definition: span.h:175
constexpr C * begin() const noexcept
Definition: span.h:174
CONSTEXPR_IF_NOT_DEBUG Span< C > first(std::size_t count) const noexcept
Definition: span.h:204
Utility class to construct Taproot outputs from internal key and script tree.
WitnessV1Taproot GetOutput()
Compute scriptPubKey (after Finalize()).
bool IsComplete() const
Return whether there were either no leaves, or the leaves form a Huffman tree.
static bool ValidDepths(const std::vector< int > &depths)
Check if a list of depths is legal (will lead to IsComplete()).
TaprootBuilder & Add(int depth, Span< const unsigned char > script, int leaf_version, bool track=true)
Add a new script at a certain depth in the tree.
TaprootBuilder & Finalize(const XOnlyPubKey &internal_key)
Finalize the construction.
const unsigned char * begin() const
Definition: pubkey.h:290
static constexpr size_t size()
Definition: pubkey.h:289
CPubKey GetEvenCorrespondingCPubKey() const
Definition: pubkey.cpp:207
bool IsFullyValid() const
Determine if this pubkey is fully valid.
Definition: pubkey.cpp:214
constexpr unsigned char * begin()
Definition: uint256.h:68
size_type size() const
Definition: prevector.h:291
iterator begin()
Definition: prevector.h:299
iterator end()
Definition: prevector.h:301
160-bit opaque blob.
Definition: uint256.h:95
256-bit opaque blob.
Definition: uint256.h:106
static const int WITNESS_SCALE_FACTOR
Definition: consensus.h:21
CScript ParseScript(const std::string &s)
Definition: core_read.cpp:61
bool CheckChecksum(Span< const char > &sp, bool require_checksum, std::string &error, std::string *out_checksum=nullptr)
Check a descriptor checksum, and update desc to be the checksum-less part.
uint256 DescriptorID(const Descriptor &desc)
Unique identifier that may not change over time, unless explicitly marked as not backwards compatible...
std::string GetDescriptorChecksum(const std::string &descriptor)
Get the checksum for a descriptor.
std::unique_ptr< Descriptor > Parse(const std::string &descriptor, FlatSigningProvider &out, std::string &error, bool require_checksum)
Parse a descriptor string.
std::unique_ptr< Descriptor > InferDescriptor(const CScript &script, const SigningProvider &provider)
Find a descriptor for the specified script, using information from provider where possible.
std::unordered_map< uint32_t, CExtPubKey > ExtPubKeyMap
Definition: descriptor.h:16
uint160 Hash160(const T1 &in1)
Compute the 160-bit hash an object.
Definition: hash.h:92
uint160 RIPEMD160(Span< const unsigned char > data)
Compute the 160-bit RIPEMD-160 hash of an array.
Definition: hash.h:222
static constexpr uint8_t TAPROOT_LEAF_TAPSCRIPT
Definition: interpreter.h:230
static constexpr size_t TAPROOT_CONTROL_MAX_NODE_COUNT
Definition: interpreter.h:233
std::string EncodeExtKey(const CExtKey &key)
Definition: key_io.cpp:276
CExtPubKey DecodeExtPubKey(const std::string &str)
Definition: key_io.cpp:240
CTxDestination DecodeDestination(const std::string &str, std::string &error_msg, std::vector< int > *error_locations)
Definition: key_io.cpp:292
std::string EncodeSecret(const CKey &key)
Definition: key_io.cpp:227
std::string EncodeDestination(const CTxDestination &dest)
Definition: key_io.cpp:287
CKey DecodeSecret(const std::string &str)
Definition: key_io.cpp:209
std::string EncodeExtPubKey(const CExtPubKey &key)
Definition: key_io.cpp:253
CExtKey DecodeExtKey(const std::string &str)
Definition: key_io.cpp:263
bool error(const char *fmt, const Args &... args)
Definition: logging.h:262
std::shared_ptr< const Node< Key > > NodeRef
Definition: miniscript.h:187
constexpr bool IsTapscript(MiniscriptContext ms_ctx)
Whether the context Tapscript, ensuring the only other possibility is P2WSH.
Definition: miniscript.h:240
NodeRef< typename Ctx::Key > FromScript(const CScript &script, const Ctx &ctx)
Definition: miniscript.h:2616
NodeRef< typename Ctx::Key > FromString(const std::string &str, const Ctx &ctx)
Definition: miniscript.h:2611
Definition: init.h:25
Span< const char > Expr(Span< const char > &sp)
Extract the expression that sp begins with.
Definition: spanparsing.cpp:33
bool Const(const std::string &str, Span< const char > &sp)
Parse a constant.
Definition: spanparsing.cpp:15
bool Func(const std::string &str, Span< const char > &sp)
Parse a function call.
Definition: spanparsing.cpp:24
std::vector< T > Split(const Span< const char > &sp, std::string_view separators)
Split a string on any char found in separators, returning a vector.
Definition: spanparsing.h:48
static OutputType GetOutputType(TxoutType type, bool is_from_p2sh)
Definition: spend.cpp:238
static bool IsSegwit(const Descriptor &desc)
Whether the descriptor represents, directly or not, a witness program.
Definition: spend.cpp:38
bool operator<(const CNetAddr &a, const CNetAddr &b)
Definition: netaddress.cpp:609
std::optional< OutputType > OutputTypeFromDestination(const CTxDestination &dest)
Get the OutputType for a CTxDestination.
Definition: outputtype.cpp:110
const char * name
Definition: rest.cpp:45
static const unsigned int MAX_SCRIPT_ELEMENT_SIZE
Definition: script.h:27
std::vector< unsigned char > ToByteVector(const T &in)
Definition: script.h:66
@ OP_CHECKSIG
Definition: script.h:189
@ OP_NUMEQUAL
Definition: script.h:170
@ OP_CHECKSIGADD
Definition: script.h:209
static constexpr unsigned int MAX_PUBKEYS_PER_MULTI_A
The limit of keys in OP_CHECKSIGADD-based scripts.
Definition: script.h:36
CScript BuildScript(Ts &&... inputs)
Build a script by concatenating other scripts, or any argument accepted by CScript::operator<<.
Definition: script.h:597
static const int MAX_PUBKEYS_PER_MULTISIG
Definition: script.h:33
constexpr unsigned int GetSizeOfCompactSize(uint64_t nSize)
Compact Size size < 253 – 1 byte size <= USHRT_MAX – 3 bytes (253 + 2 bytes) size <= UINT_MAX – 5 byt...
Definition: serialize.h:319
static bool GetPubKey(const SigningProvider &provider, const SignatureData &sigdata, const CKeyID &address, CPubKey &pubkey)
Definition: sign.cpp:109
const SigningProvider & DUMMY_SIGNING_PROVIDER
std::optional< std::vector< std::tuple< int, std::vector< unsigned char >, int > > > InferTaprootTree(const TaprootSpendData &spenddata, const XOnlyPubKey &output)
Given a TaprootSpendData and the output key, reconstruct its script tree.
void PolyMod(const std::vector< typename F::Elem > &mod, std::vector< typename F::Elem > &val, const F &field)
Compute the remainder of a polynomial division of val by mod, putting the result in mod.
Definition: sketch_impl.h:18
TxoutType Solver(const CScript &scriptPubKey, std::vector< std::vector< unsigned char >> &vSolutionsRet)
Parse a scriptPubKey and identify script type for standard scripts.
Definition: solver.cpp:140
std::optional< std::pair< int, std::vector< Span< const unsigned char > > > > MatchMultiA(const CScript &script)
Definition: solver.cpp:106
CScript GetScriptForMultisig(int nRequired, const std::vector< CPubKey > &keys)
Generate a multisig script.
Definition: solver.cpp:214
CScript GetScriptForRawPubKey(const CPubKey &pubKey)
Generate a P2PK script for the given pubkey.
Definition: solver.cpp:209
TxoutType
Definition: solver.h:22
@ WITNESS_V1_TAPROOT
@ WITNESS_V0_SCRIPTHASH
@ WITNESS_V0_KEYHASH
std::vector< Byte > ParseHex(std::string_view hex_str)
Like TryParseHex, but returns an empty vector on invalid input.
Definition: strencodings.h:65
std::string ToString(const T &t)
Locale-independent version of std::to_string.
Definition: string.h:109
Definition: key.h:208
CExtPubKey Neuter() const
Definition: key.cpp:393
bool Derive(CExtKey &out, unsigned int nChild) const
Definition: key.cpp:372
CKey key
Definition: key.h:213
bool Derive(CExtPubKey &out, unsigned int nChild) const
Definition: pubkey.cpp:396
CPubKey pubkey
Definition: pubkey.h:342
Interface for parsed descriptor objects.
Definition: descriptor.h:98
virtual std::optional< int64_t > MaxSatisfactionElems() const =0
Get the maximum size number of stack elements for satisfying this descriptor.
virtual std::optional< OutputType > GetOutputType() const =0
virtual bool ToNormalizedString(const SigningProvider &provider, std::string &out, const DescriptorCache *cache=nullptr) const =0
Convert the descriptor to a normalized string.
virtual std::optional< int64_t > ScriptSize() const =0
Get the size of the scriptPubKey for this descriptor.
virtual std::optional< int64_t > MaxSatisfactionWeight(bool use_max_sig) const =0
Get the maximum size of a satisfaction for this descriptor, in weight units.
virtual std::string ToString(bool compat_format=false) const =0
Convert the descriptor back to a string, undoing parsing.
virtual bool Expand(int pos, const SigningProvider &provider, std::vector< CScript > &output_scripts, FlatSigningProvider &out, DescriptorCache *write_cache=nullptr) const =0
Expand a descriptor at a specified position.
virtual bool IsRange() const =0
Whether the expansion of this descriptor depends on the position.
virtual bool IsSolvable() const =0
Whether this descriptor has all information about signing ignoring lack of private keys.
virtual void ExpandPrivate(int pos, const SigningProvider &provider, FlatSigningProvider &out) const =0
Expand the private key for a descriptor at a specified position, if possible.
virtual bool ToPrivateString(const SigningProvider &provider, std::string &out) const =0
Convert the descriptor to a private string.
virtual bool ExpandFromCache(int pos, const DescriptorCache &read_cache, std::vector< CScript > &output_scripts, FlatSigningProvider &out) const =0
Expand a descriptor at a specified position using cached expansion data.
std::map< CKeyID, CPubKey > pubkeys
unsigned char fingerprint[4]
First 32 bits of the Hash160 of the public key at the root of the path.
Definition: keyorigin.h:13
std::vector< uint32_t > path
Definition: keyorigin.h:14
XOnlyPubKey internal_key
The BIP341 internal key.
#define strprintf
Format arguments and return the string or write to given std::ostream (see tinyformat::format doc for...
Definition: tinyformat.h:1162
std::string HexStr(const Span< const uint8_t > s)
Convert a span of bytes to a lower-case hexadecimal string.
bool IsHex(std::string_view str)
bool ParseUInt32(std::string_view str, uint32_t *out)
Convert decimal string to unsigned 32-bit integer with strict parse error feedback.
assert(!tx.IsCoinBase())
std::vector< typename std::common_type< Args... >::type > Vector(Args &&... args)
Construct a vector with the specified elements.
Definition: vector.h:23