descriptor.cpp
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 32 //////////////////////////////////////////////////////////////////////////// 33 // Checksum // 34 //////////////////////////////////////////////////////////////////////////// 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 { 104 /** A character set designed such that: 105 * - The most common 'unprotected' descriptor characters (hex, keypaths) are in the first group of 32. 106 * - Case errors cause an offset that's a multiple of 32. 107 * - As many alphabetic characters are in the same group (while following the above restrictions). 108 * 109 * If p(x) gives the position of a character c in this character set, every group of 3 characters 110 * (a,b,c) is encoded as the 4 symbols (p(a) & 31, p(b) & 31, p(c) & 31, (p(a) / 32) + 3 * (p(b) / 32) + 9 * (p(c) / 32). 111 * This means that changes that only affect the lower 5 bits of the position, or only the higher 2 bits, will just 112 * affect a single symbol. 113 * 114 * As a result, within-group-of-32 errors count as 1 symbol, as do cross-group errors that don't affect 115 * the position within the groups. 116 */ 117 static std::string INPUT_CHARSET = 118 "0123456789()[],'/*abcdefgh@:$%{}" 119 "IJKLMNOPQRSTUVWXYZ&+-.;<=>?!^_|~" 120 "ijklmnopqrstuvwxyzABCDEFGH`#\"\\ "; 121 122 /** The character set for the checksum itself (same as bech32). */ 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 151 //////////////////////////////////////////////////////////////////////////// 152 // Internal representation // 153 //////////////////////////////////////////////////////////////////////////// 154 155 typedef std::vector<uint32_t> KeyPath; 156 157 /** Interface for public key objects in descriptors. */ 158 struct PubkeyProvider 159 { 160 protected: 161 //! Index of this key expression in the descriptor 162 //! E.g. If this PubkeyProvider is key1 in multi(2, key1, key2, key3), then m_expr_index = 0 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 170 /** Compare two public keys represented by this provider. 171 * Used by the Miniscript descriptors to check for duplicate keys in the script. 172 */ 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 184 /** Derive a public key. 185 * read_cache is the cache to read keys from (if not nullptr) 186 * write_cache is the cache to write keys to (if not nullptr) 187 * Caches are not exclusive but this is not tested. Currently we use them exclusively 188 */ 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 191 /** Whether this represent multiple public keys at different positions. */ 192 virtual bool IsRange() const = 0; 193 194 /** Get the size of the generated public key(s) in bytes (33 or 65). */ 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 202 /** Get the descriptor string form. */ 203 virtual std::string ToString(StringType type=StringType::PUBLIC) const = 0; 204 205 /** Get the descriptor string form including private data (if available in arg). */ 206 virtual bool ToPrivateString(const SigningProvider& arg, std::string& out) const = 0; 207 208 /** Get the descriptor string form with the xpub at the last hardened derivation, 209 * and always use h for hardened derivation. 210 */ 211 virtual bool ToNormalizedString(const SigningProvider& arg, std::string& out, const DescriptorCache* cache = nullptr) const = 0; 212 213 /** Derive a private key, if private data is available in arg. */ 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 270 /** An object representing a parsed constant public key in a descriptor. */ 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 321 /** An object representing a parsed extended public key in a descriptor. */ 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 530 /** Base class for all Descriptor implementations. */ 531 class DescriptorImpl : public Descriptor 532 { 533 protected: 534 //! Public key arguments for this descriptor (size 1 for PK, PKH, WPKH; any size for WSH and Multisig). 535 const std::vector<std::unique_ptr<PubkeyProvider>> m_pubkey_args; 536 //! The string name of the descriptor function. 537 const std::string m_name; 538 539 //! The sub-descriptor arguments (empty for everything but SH and WSH). 540 //! In doc/descriptors.m this is referred to as SCRIPT expressions sh(SCRIPT) 541 //! and wsh(SCRIPT), and distinct from KEY expressions and ADDR expressions. 542 //! Subdescriptors can only ever generate a single script. 543 const std::vector<std::unique_ptr<DescriptorImpl>> m_subdescriptor_args; 544 545 //! Return a serialization of anything except pubkey and script arguments, to be prepended to those. 546 virtual std::string ToStringExtra() const { return ""; } 547 548 /** A helper function to construct the scripts for this descriptor. 549 * 550 * This function is invoked once by ExpandHelper. 551 * 552 * @param pubkeys The evaluations of the m_pubkey_args field. 553 * @param scripts The evaluations of m_subdescriptor_args (one for each m_subdescriptor_args element). 554 * @param out A FlatSigningProvider to put scripts or public keys in that are necessary to the solver. 555 * The origin info of the provided pubkeys is automatically added. 556 * @return A vector with scriptPubKeys for this descriptor. 557 */ 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 713 /** A helper for MaxSatisfactionWeight. 714 * 715 * @param use_max_sig Whether to assume ECDSA signatures will have a high-r. 716 * @return The maximum size of the satisfaction in raw bytes (with no witness meaning). 717 */ 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 725 /** A parsed addr(A) descriptor. */ 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 746 /** A parsed raw(H) descriptor. */ 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 769 /** A parsed pk(P) descriptor. */ 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 804 /** A parsed pkh(P) descriptor. */ 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]); 812 return Vector(GetScriptForDestination(PKHash(id))); 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 833 /** A parsed wpkh(P) descriptor. */ 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]); 841 return Vector(GetScriptForDestination(WitnessV0KeyHash(id))); 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 862 /** A parsed combo(P) descriptor. */ 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()) { 874 CScript p2wpkh = GetScriptForDestination(WitnessV0KeyHash(id)); 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 886 /** A parsed multi(...) or sortedmulti(...) descriptor */ 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 924 /** A parsed (sorted)multi_a(...) descriptor. Always uses x-only pubkeys. */ 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 960 /** A parsed sh(...) descriptor. */ 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 1005 /** A parsed wsh(...) descriptor. */ 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 { 1011 auto ret = Vector(GetScriptForDestination(WitnessV0ScriptHash(scripts[0]))); 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 1041 /** A parsed tr(...) descriptor. */ 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 1111 /** 1112 * The context for converting a Miniscript descriptor into a Script. 1113 */ 1114 class ScriptMaker { 1115 //! Keys contained in the Miniscript (the evaluation of DescriptorImpl::m_pubkey_args). 1116 const std::vector<CPubKey>& m_keys; 1117 //! The script context we're operating within (Tapscript or P2WSH). 1118 const miniscript::MiniscriptContext m_script_ctx; 1119 1120 //! Get the ripemd160(sha256()) hash of this key. 1121 //! Any key that is valid in a descriptor serializes as 32 bytes within a Tapscript context. So we 1122 //! must not hash the sign-bit byte in this case. 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 1148 /** 1149 * The context for converting a Miniscript descriptor to its textual form. 1150 */ 1151 class StringMaker { 1152 //! To convert private keys for private descriptors. 1153 const SigningProvider* m_arg; 1154 //! Keys contained in the Miniscript (a reference to DescriptorImpl::m_pubkey_args). 1155 const std::vector<std::unique_ptr<PubkeyProvider>>& m_pubkeys; 1156 //! Whether to serialize keys as private or public. 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: 1178 miniscript::NodeRef<uint32_t> m_node; 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 1224 /** A parsed rawtr(...) descriptor. */ 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 1254 //////////////////////////////////////////////////////////////////////////// 1255 // Parser // 1256 //////////////////////////////////////////////////////////////////////////// 1257 1258 enum class ParseScriptContext { 1259 TOP, //!< Top-level context (script goes directly in scriptPubKey) 1260 P2SH, //!< Inside sh() (script becomes P2SH redeemScript) 1261 P2WPKH, //!< Inside wpkh() (no script, pubkey only) 1262 P2WSH, //!< Inside wsh() (script becomes v0 witness script) 1263 P2TR, //!< Inside tr() (either internal key, or BIP342 script leaf) 1264 }; 1265 1266 /** 1267 * Parse a key path, being passed a split list of elements (the first element is ignored). 1268 * 1269 * @param[in] split BIP32 path string, using either ' or h for hardened derivation 1270 * @param[out] out the key path 1271 * @param[out] apostrophe only updated if hardened derivation is found 1272 * @param[out] error parsing error message 1273 * @returns false if parsing failed 1274 **/ 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 1301 /** Parse a public key that excludes origin information. */ 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 1375 /** Parse a public key including origin information (if enabled). */ 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() ? /** empty, implies split char */ ']' : 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 1445 /** 1446 * The context for parsing a Miniscript descriptor (either from Script or from its textual representation). 1447 */ 1448 struct KeyParser { 1449 //! The Key type is an index in DescriptorImpl::m_pubkey_args 1450 using Key = uint32_t; 1451 //! Must not be nullptr if parsing from string. 1452 FlatSigningProvider* m_out; 1453 //! Must not be nullptr if parsing from Script. 1454 const SigningProvider* m_in; 1455 //! List of keys contained in the Miniscript. 1456 mutable std::vector<std::unique_ptr<PubkeyProvider>> m_keys; 1457 //! Used to detect key parsing errors within a Miniscript. 1458 mutable std::string m_key_parsing_error; 1459 //! The script context we're operating within (Tapscript or P2WSH). 1460 const miniscript::MiniscriptContext m_script_ctx; 1461 //! The number of keys that were parsed before starting to parse this Miniscript descriptor. 1462 uint32_t m_offset; 1463 1464 KeyParser(FlatSigningProvider* out LIFETIMEBOUND, const SigningProvider* in LIFETIMEBOUND, 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 1539 /** Parse a script in a particular context. */ 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; //!< list of script subexpressions 1694 std::vector<int> depths; //!< depth in the tree of each subexpression (same length subscripts) 1695 if (expr.size()) { 1696 if (!Const(",", expr)) { 1697 error = strprintf("tr: expected ',', got '%c'", expr[0]); 1698 return nullptr; 1699 } 1700 /** The path from the top of the tree to what we're currently processing. 1701 * branches[i] == false: left branch in the i'th step from the top; true: right branch. 1702 */ 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 } 1743 assert(TaprootBuilder::ValidDepths(depths)); 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 (parser.m_key_parsing_error != "") { 1781 error = std::move(parser.m_key_parsing_error); 1782 return nullptr; 1783 } 1784 if (node) { 1785 if (ctx != ParseScriptContext::P2WSH && ctx != ParseScriptContext::P2TR) { 1786 error = "Miniscript expressions can only be used in wsh or tr."; 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; //!< list of script subexpressions 1932 std::vector<int> depths; //!< depth in the tree of each subexpression (same length subscripts) 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 1987 /** Check a descriptor checksum, and update desc to be the checksum-less part. */ 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 2047 uint256 DescriptorID(const Descriptor& desc) 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 2097 DescriptorCache DescriptorCache::MergeAndDiff(const DescriptorCache& other) 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 2138 ExtPubKeyMap DescriptorCache::GetCachedParentExtPubKeys() const 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 2148 ExtPubKeyMap DescriptorCache::GetCachedLastHardenedExtPubKeys() const 2149 { 2150 return m_last_hardened_xpubs; 2151 }