descriptor.cpp
1 // Copyright (c) 2018-present 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/parsing.h> 12 #include <script/script.h> 13 #include <script/signingprovider.h> 14 #include <script/solver.h> 15 #include <uint256.h> 16 17 #include <common/args.h> 18 #include <span.h> 19 #include <util/bip32.h> 20 #include <util/check.h> 21 #include <util/strencodings.h> 22 #include <util/vector.h> 23 24 #include <algorithm> 25 #include <memory> 26 #include <numeric> 27 #include <optional> 28 #include <string> 29 #include <vector> 30 31 using util::Split; 32 33 namespace { 34 35 //////////////////////////////////////////////////////////////////////////// 36 // Checksum // 37 //////////////////////////////////////////////////////////////////////////// 38 39 // This section implements a checksum algorithm for descriptors with the 40 // following properties: 41 // * Mistakes in a descriptor string are measured in "symbol errors". The higher 42 // the number of symbol errors, the harder it is to detect: 43 // * An error substituting a character from 0123456789()[],'/*abcdefgh@:$%{} for 44 // another in that set always counts as 1 symbol error. 45 // * Note that hex encoded keys are covered by these characters. Xprvs and 46 // xpubs use other characters too, but already have their own checksum 47 // mechanism. 48 // * Function names like "multi()" use other characters, but mistakes in 49 // these would generally result in an unparsable descriptor. 50 // * A case error always counts as 1 symbol error. 51 // * Any other 1 character substitution error counts as 1 or 2 symbol errors. 52 // * Any 1 symbol error is always detected. 53 // * Any 2 or 3 symbol error in a descriptor of up to 49154 characters is always detected. 54 // * Any 4 symbol error in a descriptor of up to 507 characters is always detected. 55 // * Any 5 symbol error in a descriptor of up to 77 characters is always detected. 56 // * Is optimized to minimize the chance a 5 symbol error in a descriptor up to 387 characters is undetected 57 // * Random errors have a chance of 1 in 2**40 of being undetected. 58 // 59 // These properties are achieved by expanding every group of 3 (non checksum) characters into 60 // 4 GF(32) symbols, over which a cyclic code is defined. 61 62 /* 63 * Interprets c as 8 groups of 5 bits which are the coefficients of a degree 8 polynomial over GF(32), 64 * multiplies that polynomial by x, computes its remainder modulo a generator, and adds the constant term val. 65 * 66 * 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}. 67 * It is chosen to define an cyclic error detecting code which is selected by: 68 * - Starting from all BCH codes over GF(32) of degree 8 and below, which by construction guarantee detecting 69 * 3 errors in windows up to 19000 symbols. 70 * - Taking all those generators, and for degree 7 ones, extend them to degree 8 by adding all degree-1 factors. 71 * - Selecting just the set of generators that guarantee detecting 4 errors in a window of length 512. 72 * - Selecting one of those with best worst-case behavior for 5 errors in windows of length up to 512. 73 * 74 * The generator and the constants to implement it can be verified using this Sage code: 75 * B = GF(2) # Binary field 76 * BP.<b> = B[] # Polynomials over the binary field 77 * F_mod = b**5 + b**3 + 1 78 * F.<f> = GF(32, modulus=F_mod, repr='int') # GF(32) definition 79 * FP.<x> = F[] # Polynomials over GF(32) 80 * E_mod = x**3 + x + F.fetch_int(8) 81 * E.<e> = F.extension(E_mod) # Extension field definition 82 * alpha = e**2743 # Choice of an element in extension field 83 * for p in divisors(E.order() - 1): # Verify alpha has order 32767. 84 * assert((alpha**p == 1) == (p % 32767 == 0)) 85 * G = lcm([(alpha**i).minpoly() for i in [1056,1057,1058]] + [x + 1]) 86 * print(G) # Print out the generator 87 * for i in [1,2,4,8,16]: # Print out {1,2,4,8,16}*(G mod x^8), packed in hex integers. 88 * v = 0 89 * for coef in reversed((F.fetch_int(i)*(G % x**8)).coefficients(sparse=True)): 90 * v = v*32 + coef.integer_representation() 91 * print("0x%x" % v) 92 */ 93 uint64_t PolyMod(uint64_t c, int val) 94 { 95 uint8_t c0 = c >> 35; 96 c = ((c & 0x7ffffffff) << 5) ^ val; 97 if (c0 & 1) c ^= 0xf5dee51989; 98 if (c0 & 2) c ^= 0xa9fdca3312; 99 if (c0 & 4) c ^= 0x1bab10e32d; 100 if (c0 & 8) c ^= 0x3706b1677a; 101 if (c0 & 16) c ^= 0x644d626ffd; 102 return c; 103 } 104 105 std::string DescriptorChecksum(const std::span<const char>& span) 106 { 107 /** A character set designed such that: 108 * - The most common 'unprotected' descriptor characters (hex, keypaths) are in the first group of 32. 109 * - Case errors cause an offset that's a multiple of 32. 110 * - As many alphabetic characters are in the same group (while following the above restrictions). 111 * 112 * If p(x) gives the position of a character c in this character set, every group of 3 characters 113 * (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). 114 * This means that changes that only affect the lower 5 bits of the position, or only the higher 2 bits, will just 115 * affect a single symbol. 116 * 117 * As a result, within-group-of-32 errors count as 1 symbol, as do cross-group errors that don't affect 118 * the position within the groups. 119 */ 120 static const std::string INPUT_CHARSET = 121 "0123456789()[],'/*abcdefgh@:$%{}" 122 "IJKLMNOPQRSTUVWXYZ&+-.;<=>?!^_|~" 123 "ijklmnopqrstuvwxyzABCDEFGH`#\"\\ "; 124 125 /** The character set for the checksum itself (same as bech32). */ 126 static const std::string CHECKSUM_CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l"; 127 128 uint64_t c = 1; 129 int cls = 0; 130 int clscount = 0; 131 for (auto ch : span) { 132 auto pos = INPUT_CHARSET.find(ch); 133 if (pos == std::string::npos) return ""; 134 c = PolyMod(c, pos & 31); // Emit a symbol for the position inside the group, for every character. 135 cls = cls * 3 + (pos >> 5); // Accumulate the group numbers 136 if (++clscount == 3) { 137 // Emit an extra symbol representing the group numbers, for every 3 characters. 138 c = PolyMod(c, cls); 139 cls = 0; 140 clscount = 0; 141 } 142 } 143 if (clscount > 0) c = PolyMod(c, cls); 144 for (int j = 0; j < 8; ++j) c = PolyMod(c, 0); // Shift further to determine the checksum. 145 c ^= 1; // Prevent appending zeroes from not affecting the checksum. 146 147 std::string ret(8, ' '); 148 for (int j = 0; j < 8; ++j) ret[j] = CHECKSUM_CHARSET[(c >> (5 * (7 - j))) & 31]; 149 return ret; 150 } 151 152 std::string AddChecksum(const std::string& str) { return str + "#" + DescriptorChecksum(str); } 153 154 //////////////////////////////////////////////////////////////////////////// 155 // Internal representation // 156 //////////////////////////////////////////////////////////////////////////// 157 158 typedef std::vector<uint32_t> KeyPath; 159 160 /** Interface for public key objects in descriptors. */ 161 struct PubkeyProvider 162 { 163 protected: 164 //! Index of this key expression in the descriptor 165 //! E.g. If this PubkeyProvider is key1 in multi(2, key1, key2, key3), then m_expr_index = 0 166 uint32_t m_expr_index; 167 168 public: 169 explicit PubkeyProvider(uint32_t exp_index) : m_expr_index(exp_index) {} 170 171 virtual ~PubkeyProvider() = default; 172 173 /** Compare two public keys represented by this provider. 174 * Used by the Miniscript descriptors to check for duplicate keys in the script. 175 */ 176 bool operator<(PubkeyProvider& other) const { 177 FlatSigningProvider dummy; 178 179 std::optional<CPubKey> a = GetPubKey(0, dummy, dummy); 180 std::optional<CPubKey> b = other.GetPubKey(0, dummy, dummy); 181 182 return a < b; 183 } 184 185 /** Derive a public key and put it into out. 186 * read_cache is the cache to read keys from (if not nullptr) 187 * write_cache is the cache to write keys to (if not nullptr) 188 * Caches are not exclusive but this is not tested. Currently we use them exclusively 189 */ 190 virtual std::optional<CPubKey> GetPubKey(int pos, const SigningProvider& arg, FlatSigningProvider& out, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const = 0; 191 192 /** Whether this represent multiple public keys at different positions. */ 193 virtual bool IsRange() const = 0; 194 195 /** Get the size of the generated public key(s) in bytes (33 or 65). */ 196 virtual size_t GetSize() const = 0; 197 198 enum class StringType { 199 PUBLIC, 200 COMPAT // string calculation that mustn't change over time to stay compatible with previous software versions 201 }; 202 203 /** Get the descriptor string form. */ 204 virtual std::string ToString(StringType type=StringType::PUBLIC) const = 0; 205 206 /** Get the descriptor string form including private data (if available in arg). */ 207 virtual bool ToPrivateString(const SigningProvider& arg, std::string& out) const = 0; 208 209 /** Get the descriptor string form with the xpub at the last hardened derivation, 210 * and always use h for hardened derivation. 211 */ 212 virtual bool ToNormalizedString(const SigningProvider& arg, std::string& out, const DescriptorCache* cache = nullptr) const = 0; 213 214 /** Derive a private key, if private data is available in arg and put it into out. */ 215 virtual void GetPrivKey(int pos, const SigningProvider& arg, FlatSigningProvider& out) const = 0; 216 217 /** Return the non-extended public key for this PubkeyProvider, if it has one. */ 218 virtual std::optional<CPubKey> GetRootPubKey() const = 0; 219 /** Return the extended public key for this PubkeyProvider, if it has one. */ 220 virtual std::optional<CExtPubKey> GetRootExtPubKey() const = 0; 221 222 /** Make a deep copy of this PubkeyProvider */ 223 virtual std::unique_ptr<PubkeyProvider> Clone() const = 0; 224 }; 225 226 class OriginPubkeyProvider final : public PubkeyProvider 227 { 228 KeyOriginInfo m_origin; 229 std::unique_ptr<PubkeyProvider> m_provider; 230 bool m_apostrophe; 231 232 std::string OriginString(StringType type, bool normalized=false) const 233 { 234 // If StringType==COMPAT, always use the apostrophe to stay compatible with previous versions 235 bool use_apostrophe = (!normalized && m_apostrophe) || type == StringType::COMPAT; 236 return HexStr(m_origin.fingerprint) + FormatHDKeypath(m_origin.path, use_apostrophe); 237 } 238 239 public: 240 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) {} 241 std::optional<CPubKey> GetPubKey(int pos, const SigningProvider& arg, FlatSigningProvider& out, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override 242 { 243 std::optional<CPubKey> pub = m_provider->GetPubKey(pos, arg, out, read_cache, write_cache); 244 if (!pub) return std::nullopt; 245 Assert(out.pubkeys.contains(pub->GetID())); 246 auto& [pubkey, suborigin] = out.origins[pub->GetID()]; 247 Assert(pubkey == *pub); // m_provider must have a valid origin by this point. 248 std::copy(std::begin(m_origin.fingerprint), std::end(m_origin.fingerprint), suborigin.fingerprint); 249 suborigin.path.insert(suborigin.path.begin(), m_origin.path.begin(), m_origin.path.end()); 250 return pub; 251 } 252 bool IsRange() const override { return m_provider->IsRange(); } 253 size_t GetSize() const override { return m_provider->GetSize(); } 254 std::string ToString(StringType type) const override { return "[" + OriginString(type) + "]" + m_provider->ToString(type); } 255 bool ToPrivateString(const SigningProvider& arg, std::string& ret) const override 256 { 257 std::string sub; 258 if (!m_provider->ToPrivateString(arg, sub)) return false; 259 ret = "[" + OriginString(StringType::PUBLIC) + "]" + std::move(sub); 260 return true; 261 } 262 bool ToNormalizedString(const SigningProvider& arg, std::string& ret, const DescriptorCache* cache) const override 263 { 264 std::string sub; 265 if (!m_provider->ToNormalizedString(arg, sub, cache)) return false; 266 // If m_provider is a BIP32PubkeyProvider, we may get a string formatted like a OriginPubkeyProvider 267 // In that case, we need to strip out the leading square bracket and fingerprint from the substring, 268 // and append that to our own origin string. 269 if (sub[0] == '[') { 270 sub = sub.substr(9); 271 ret = "[" + OriginString(StringType::PUBLIC, /*normalized=*/true) + std::move(sub); 272 } else { 273 ret = "[" + OriginString(StringType::PUBLIC, /*normalized=*/true) + "]" + std::move(sub); 274 } 275 return true; 276 } 277 void GetPrivKey(int pos, const SigningProvider& arg, FlatSigningProvider& out) const override 278 { 279 m_provider->GetPrivKey(pos, arg, out); 280 } 281 std::optional<CPubKey> GetRootPubKey() const override 282 { 283 return m_provider->GetRootPubKey(); 284 } 285 std::optional<CExtPubKey> GetRootExtPubKey() const override 286 { 287 return m_provider->GetRootExtPubKey(); 288 } 289 std::unique_ptr<PubkeyProvider> Clone() const override 290 { 291 return std::make_unique<OriginPubkeyProvider>(m_expr_index, m_origin, m_provider->Clone(), m_apostrophe); 292 } 293 }; 294 295 /** An object representing a parsed constant public key in a descriptor. */ 296 class ConstPubkeyProvider final : public PubkeyProvider 297 { 298 CPubKey m_pubkey; 299 bool m_xonly; 300 301 std::optional<CKey> GetPrivKey(const SigningProvider& arg) const 302 { 303 CKey key; 304 if (!(m_xonly ? arg.GetKeyByXOnly(XOnlyPubKey(m_pubkey), key) : 305 arg.GetKey(m_pubkey.GetID(), key))) return std::nullopt; 306 return key; 307 } 308 309 public: 310 ConstPubkeyProvider(uint32_t exp_index, const CPubKey& pubkey, bool xonly) : PubkeyProvider(exp_index), m_pubkey(pubkey), m_xonly(xonly) {} 311 std::optional<CPubKey> GetPubKey(int pos, const SigningProvider&, FlatSigningProvider& out, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override 312 { 313 KeyOriginInfo info; 314 CKeyID keyid = m_pubkey.GetID(); 315 std::copy(keyid.begin(), keyid.begin() + sizeof(info.fingerprint), info.fingerprint); 316 out.origins.emplace(keyid, std::make_pair(m_pubkey, info)); 317 out.pubkeys.emplace(keyid, m_pubkey); 318 return m_pubkey; 319 } 320 bool IsRange() const override { return false; } 321 size_t GetSize() const override { return m_pubkey.size(); } 322 std::string ToString(StringType type) const override { return m_xonly ? HexStr(m_pubkey).substr(2) : HexStr(m_pubkey); } 323 bool ToPrivateString(const SigningProvider& arg, std::string& ret) const override 324 { 325 std::optional<CKey> key = GetPrivKey(arg); 326 if (!key) return false; 327 ret = EncodeSecret(*key); 328 return true; 329 } 330 bool ToNormalizedString(const SigningProvider& arg, std::string& ret, const DescriptorCache* cache) const override 331 { 332 ret = ToString(StringType::PUBLIC); 333 return true; 334 } 335 void GetPrivKey(int pos, const SigningProvider& arg, FlatSigningProvider& out) const override 336 { 337 std::optional<CKey> key = GetPrivKey(arg); 338 if (!key) return; 339 out.keys.emplace(key->GetPubKey().GetID(), *key); 340 } 341 std::optional<CPubKey> GetRootPubKey() const override 342 { 343 return m_pubkey; 344 } 345 std::optional<CExtPubKey> GetRootExtPubKey() const override 346 { 347 return std::nullopt; 348 } 349 std::unique_ptr<PubkeyProvider> Clone() const override 350 { 351 return std::make_unique<ConstPubkeyProvider>(m_expr_index, m_pubkey, m_xonly); 352 } 353 }; 354 355 enum class DeriveType { 356 NO, 357 UNHARDENED, 358 HARDENED, 359 }; 360 361 /** An object representing a parsed extended public key in a descriptor. */ 362 class BIP32PubkeyProvider final : public PubkeyProvider 363 { 364 // Root xpub, path, and final derivation step type being used, if any 365 CExtPubKey m_root_extkey; 366 KeyPath m_path; 367 DeriveType m_derive; 368 // Whether ' or h is used in harded derivation 369 bool m_apostrophe; 370 371 bool GetExtKey(const SigningProvider& arg, CExtKey& ret) const 372 { 373 CKey key; 374 if (!arg.GetKey(m_root_extkey.pubkey.GetID(), key)) return false; 375 ret.nDepth = m_root_extkey.nDepth; 376 std::copy(m_root_extkey.vchFingerprint, m_root_extkey.vchFingerprint + sizeof(ret.vchFingerprint), ret.vchFingerprint); 377 ret.nChild = m_root_extkey.nChild; 378 ret.chaincode = m_root_extkey.chaincode; 379 ret.key = key; 380 return true; 381 } 382 383 // Derives the last xprv 384 bool GetDerivedExtKey(const SigningProvider& arg, CExtKey& xprv, CExtKey& last_hardened) const 385 { 386 if (!GetExtKey(arg, xprv)) return false; 387 for (auto entry : m_path) { 388 if (!xprv.Derive(xprv, entry)) return false; 389 if (entry >> 31) { 390 last_hardened = xprv; 391 } 392 } 393 return true; 394 } 395 396 bool IsHardened() const 397 { 398 if (m_derive == DeriveType::HARDENED) return true; 399 for (auto entry : m_path) { 400 if (entry >> 31) return true; 401 } 402 return false; 403 } 404 405 public: 406 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) {} 407 bool IsRange() const override { return m_derive != DeriveType::NO; } 408 size_t GetSize() const override { return 33; } 409 std::optional<CPubKey> GetPubKey(int pos, const SigningProvider& arg, FlatSigningProvider& out, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override 410 { 411 KeyOriginInfo info; 412 CKeyID keyid = m_root_extkey.pubkey.GetID(); 413 std::copy(keyid.begin(), keyid.begin() + sizeof(info.fingerprint), info.fingerprint); 414 info.path = m_path; 415 if (m_derive == DeriveType::UNHARDENED) info.path.push_back((uint32_t)pos); 416 if (m_derive == DeriveType::HARDENED) info.path.push_back(((uint32_t)pos) | 0x80000000L); 417 418 // Derive keys or fetch them from cache 419 CExtPubKey final_extkey = m_root_extkey; 420 CExtPubKey parent_extkey = m_root_extkey; 421 CExtPubKey last_hardened_extkey; 422 bool der = true; 423 if (read_cache) { 424 if (!read_cache->GetCachedDerivedExtPubKey(m_expr_index, pos, final_extkey)) { 425 if (m_derive == DeriveType::HARDENED) return std::nullopt; 426 // Try to get the derivation parent 427 if (!read_cache->GetCachedParentExtPubKey(m_expr_index, parent_extkey)) return std::nullopt; 428 final_extkey = parent_extkey; 429 if (m_derive == DeriveType::UNHARDENED) der = parent_extkey.Derive(final_extkey, pos); 430 } 431 } else if (IsHardened()) { 432 CExtKey xprv; 433 CExtKey lh_xprv; 434 if (!GetDerivedExtKey(arg, xprv, lh_xprv)) return std::nullopt; 435 parent_extkey = xprv.Neuter(); 436 if (m_derive == DeriveType::UNHARDENED) der = xprv.Derive(xprv, pos); 437 if (m_derive == DeriveType::HARDENED) der = xprv.Derive(xprv, pos | 0x80000000UL); 438 final_extkey = xprv.Neuter(); 439 if (lh_xprv.key.IsValid()) { 440 last_hardened_extkey = lh_xprv.Neuter(); 441 } 442 } else { 443 for (auto entry : m_path) { 444 if (!parent_extkey.Derive(parent_extkey, entry)) return std::nullopt; 445 } 446 final_extkey = parent_extkey; 447 if (m_derive == DeriveType::UNHARDENED) der = parent_extkey.Derive(final_extkey, pos); 448 assert(m_derive != DeriveType::HARDENED); 449 } 450 if (!der) return std::nullopt; 451 452 out.origins.emplace(final_extkey.pubkey.GetID(), std::make_pair(final_extkey.pubkey, info)); 453 out.pubkeys.emplace(final_extkey.pubkey.GetID(), final_extkey.pubkey); 454 455 if (write_cache) { 456 // Only cache parent if there is any unhardened derivation 457 if (m_derive != DeriveType::HARDENED) { 458 write_cache->CacheParentExtPubKey(m_expr_index, parent_extkey); 459 // Cache last hardened xpub if we have it 460 if (last_hardened_extkey.pubkey.IsValid()) { 461 write_cache->CacheLastHardenedExtPubKey(m_expr_index, last_hardened_extkey); 462 } 463 } else if (info.path.size() > 0) { 464 write_cache->CacheDerivedExtPubKey(m_expr_index, pos, final_extkey); 465 } 466 } 467 468 return final_extkey.pubkey; 469 } 470 std::string ToString(StringType type, bool normalized) const 471 { 472 // If StringType==COMPAT, always use the apostrophe to stay compatible with previous versions 473 const bool use_apostrophe = (!normalized && m_apostrophe) || type == StringType::COMPAT; 474 std::string ret = EncodeExtPubKey(m_root_extkey) + FormatHDKeypath(m_path, /*apostrophe=*/use_apostrophe); 475 if (IsRange()) { 476 ret += "/*"; 477 if (m_derive == DeriveType::HARDENED) ret += use_apostrophe ? '\'' : 'h'; 478 } 479 return ret; 480 } 481 std::string ToString(StringType type=StringType::PUBLIC) const override 482 { 483 return ToString(type, /*normalized=*/false); 484 } 485 bool ToPrivateString(const SigningProvider& arg, std::string& out) const override 486 { 487 CExtKey key; 488 if (!GetExtKey(arg, key)) return false; 489 out = EncodeExtKey(key) + FormatHDKeypath(m_path, /*apostrophe=*/m_apostrophe); 490 if (IsRange()) { 491 out += "/*"; 492 if (m_derive == DeriveType::HARDENED) out += m_apostrophe ? '\'' : 'h'; 493 } 494 return true; 495 } 496 bool ToNormalizedString(const SigningProvider& arg, std::string& out, const DescriptorCache* cache) const override 497 { 498 if (m_derive == DeriveType::HARDENED) { 499 out = ToString(StringType::PUBLIC, /*normalized=*/true); 500 501 return true; 502 } 503 // Step backwards to find the last hardened step in the path 504 int i = (int)m_path.size() - 1; 505 for (; i >= 0; --i) { 506 if (m_path.at(i) >> 31) { 507 break; 508 } 509 } 510 // Either no derivation or all unhardened derivation 511 if (i == -1) { 512 out = ToString(); 513 return true; 514 } 515 // Get the path to the last hardened stup 516 KeyOriginInfo origin; 517 int k = 0; 518 for (; k <= i; ++k) { 519 // Add to the path 520 origin.path.push_back(m_path.at(k)); 521 } 522 // Build the remaining path 523 KeyPath end_path; 524 for (; k < (int)m_path.size(); ++k) { 525 end_path.push_back(m_path.at(k)); 526 } 527 // Get the fingerprint 528 CKeyID id = m_root_extkey.pubkey.GetID(); 529 std::copy(id.begin(), id.begin() + 4, origin.fingerprint); 530 531 CExtPubKey xpub; 532 CExtKey lh_xprv; 533 // If we have the cache, just get the parent xpub 534 if (cache != nullptr) { 535 cache->GetCachedLastHardenedExtPubKey(m_expr_index, xpub); 536 } 537 if (!xpub.pubkey.IsValid()) { 538 // Cache miss, or nor cache, or need privkey 539 CExtKey xprv; 540 if (!GetDerivedExtKey(arg, xprv, lh_xprv)) return false; 541 xpub = lh_xprv.Neuter(); 542 } 543 assert(xpub.pubkey.IsValid()); 544 545 // Build the string 546 std::string origin_str = HexStr(origin.fingerprint) + FormatHDKeypath(origin.path); 547 out = "[" + origin_str + "]" + EncodeExtPubKey(xpub) + FormatHDKeypath(end_path); 548 if (IsRange()) { 549 out += "/*"; 550 assert(m_derive == DeriveType::UNHARDENED); 551 } 552 return true; 553 } 554 void GetPrivKey(int pos, const SigningProvider& arg, FlatSigningProvider& out) const override 555 { 556 CExtKey extkey; 557 CExtKey dummy; 558 if (!GetDerivedExtKey(arg, extkey, dummy)) return; 559 if (m_derive == DeriveType::UNHARDENED && !extkey.Derive(extkey, pos)) return; 560 if (m_derive == DeriveType::HARDENED && !extkey.Derive(extkey, pos | 0x80000000UL)) return; 561 out.keys.emplace(extkey.key.GetPubKey().GetID(), extkey.key); 562 } 563 std::optional<CPubKey> GetRootPubKey() const override 564 { 565 return std::nullopt; 566 } 567 std::optional<CExtPubKey> GetRootExtPubKey() const override 568 { 569 return m_root_extkey; 570 } 571 std::unique_ptr<PubkeyProvider> Clone() const override 572 { 573 return std::make_unique<BIP32PubkeyProvider>(m_expr_index, m_root_extkey, m_path, m_derive, m_apostrophe); 574 } 575 }; 576 577 /** Base class for all Descriptor implementations. */ 578 class DescriptorImpl : public Descriptor 579 { 580 protected: 581 //! Public key arguments for this descriptor (size 1 for PK, PKH, WPKH; any size for WSH and Multisig). 582 const std::vector<std::unique_ptr<PubkeyProvider>> m_pubkey_args; 583 //! The string name of the descriptor function. 584 const std::string m_name; 585 586 //! The sub-descriptor arguments (empty for everything but SH and WSH). 587 //! In doc/descriptors.m this is referred to as SCRIPT expressions sh(SCRIPT) 588 //! and wsh(SCRIPT), and distinct from KEY expressions and ADDR expressions. 589 //! Subdescriptors can only ever generate a single script. 590 const std::vector<std::unique_ptr<DescriptorImpl>> m_subdescriptor_args; 591 592 //! Return a serialization of anything except pubkey and script arguments, to be prepended to those. 593 virtual std::string ToStringExtra() const { return ""; } 594 595 /** A helper function to construct the scripts for this descriptor. 596 * 597 * This function is invoked once by ExpandHelper. 598 * 599 * @param pubkeys The evaluations of the m_pubkey_args field. 600 * @param scripts The evaluations of m_subdescriptor_args (one for each m_subdescriptor_args element). 601 * @param out A FlatSigningProvider to put scripts or public keys in that are necessary to the solver. 602 * The origin info of the provided pubkeys is automatically added. 603 * @return A vector with scriptPubKeys for this descriptor. 604 */ 605 virtual std::vector<CScript> MakeScripts(const std::vector<CPubKey>& pubkeys, std::span<const CScript> scripts, FlatSigningProvider& out) const = 0; 606 607 public: 608 DescriptorImpl(std::vector<std::unique_ptr<PubkeyProvider>> pubkeys, const std::string& name) : m_pubkey_args(std::move(pubkeys)), m_name(name), m_subdescriptor_args() {} 609 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))) {} 610 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)) {} 611 612 enum class StringType 613 { 614 PUBLIC, 615 PRIVATE, 616 NORMALIZED, 617 COMPAT, // string calculation that mustn't change over time to stay compatible with previous software versions 618 }; 619 620 // NOLINTNEXTLINE(misc-no-recursion) 621 bool IsSolvable() const override 622 { 623 for (const auto& arg : m_subdescriptor_args) { 624 if (!arg->IsSolvable()) return false; 625 } 626 return true; 627 } 628 629 // NOLINTNEXTLINE(misc-no-recursion) 630 bool IsRange() const final 631 { 632 for (const auto& pubkey : m_pubkey_args) { 633 if (pubkey->IsRange()) return true; 634 } 635 for (const auto& arg : m_subdescriptor_args) { 636 if (arg->IsRange()) return true; 637 } 638 return false; 639 } 640 641 // NOLINTNEXTLINE(misc-no-recursion) 642 virtual bool ToStringSubScriptHelper(const SigningProvider* arg, std::string& ret, const StringType type, const DescriptorCache* cache = nullptr) const 643 { 644 size_t pos = 0; 645 for (const auto& scriptarg : m_subdescriptor_args) { 646 if (pos++) ret += ","; 647 std::string tmp; 648 if (!scriptarg->ToStringHelper(arg, tmp, type, cache)) return false; 649 ret += tmp; 650 } 651 return true; 652 } 653 654 // NOLINTNEXTLINE(misc-no-recursion) 655 virtual bool ToStringHelper(const SigningProvider* arg, std::string& out, const StringType type, const DescriptorCache* cache = nullptr) const 656 { 657 std::string extra = ToStringExtra(); 658 size_t pos = extra.size() > 0 ? 1 : 0; 659 std::string ret = m_name + "(" + extra; 660 for (const auto& pubkey : m_pubkey_args) { 661 if (pos++) ret += ","; 662 std::string tmp; 663 switch (type) { 664 case StringType::NORMALIZED: 665 if (!pubkey->ToNormalizedString(*arg, tmp, cache)) return false; 666 break; 667 case StringType::PRIVATE: 668 if (!pubkey->ToPrivateString(*arg, tmp)) return false; 669 break; 670 case StringType::PUBLIC: 671 tmp = pubkey->ToString(); 672 break; 673 case StringType::COMPAT: 674 tmp = pubkey->ToString(PubkeyProvider::StringType::COMPAT); 675 break; 676 } 677 ret += tmp; 678 } 679 std::string subscript; 680 if (!ToStringSubScriptHelper(arg, subscript, type, cache)) return false; 681 if (pos && subscript.size()) ret += ','; 682 out = std::move(ret) + std::move(subscript) + ")"; 683 return true; 684 } 685 686 std::string ToString(bool compat_format) const final 687 { 688 std::string ret; 689 ToStringHelper(nullptr, ret, compat_format ? StringType::COMPAT : StringType::PUBLIC); 690 return AddChecksum(ret); 691 } 692 693 bool ToPrivateString(const SigningProvider& arg, std::string& out) const override 694 { 695 bool ret = ToStringHelper(&arg, out, StringType::PRIVATE); 696 out = AddChecksum(out); 697 return ret; 698 } 699 700 bool ToNormalizedString(const SigningProvider& arg, std::string& out, const DescriptorCache* cache) const override final 701 { 702 bool ret = ToStringHelper(&arg, out, StringType::NORMALIZED, cache); 703 out = AddChecksum(out); 704 return ret; 705 } 706 707 // NOLINTNEXTLINE(misc-no-recursion) 708 bool ExpandHelper(int pos, const SigningProvider& arg, const DescriptorCache* read_cache, std::vector<CScript>& output_scripts, FlatSigningProvider& out, DescriptorCache* write_cache) const 709 { 710 FlatSigningProvider subprovider; 711 std::vector<CPubKey> pubkeys; 712 pubkeys.reserve(m_pubkey_args.size()); 713 714 // Construct temporary data in `pubkeys`, `subscripts`, and `subprovider` to avoid producing output in case of failure. 715 for (const auto& p : m_pubkey_args) { 716 std::optional<CPubKey> pubkey = p->GetPubKey(pos, arg, subprovider, read_cache, write_cache); 717 if (!pubkey) return false; 718 pubkeys.push_back(pubkey.value()); 719 } 720 std::vector<CScript> subscripts; 721 for (const auto& subarg : m_subdescriptor_args) { 722 std::vector<CScript> outscripts; 723 if (!subarg->ExpandHelper(pos, arg, read_cache, outscripts, subprovider, write_cache)) return false; 724 assert(outscripts.size() == 1); 725 subscripts.emplace_back(std::move(outscripts[0])); 726 } 727 out.Merge(std::move(subprovider)); 728 729 output_scripts = MakeScripts(pubkeys, std::span{subscripts}, out); 730 return true; 731 } 732 733 bool Expand(int pos, const SigningProvider& provider, std::vector<CScript>& output_scripts, FlatSigningProvider& out, DescriptorCache* write_cache = nullptr) const final 734 { 735 return ExpandHelper(pos, provider, nullptr, output_scripts, out, write_cache); 736 } 737 738 bool ExpandFromCache(int pos, const DescriptorCache& read_cache, std::vector<CScript>& output_scripts, FlatSigningProvider& out) const final 739 { 740 return ExpandHelper(pos, DUMMY_SIGNING_PROVIDER, &read_cache, output_scripts, out, nullptr); 741 } 742 743 // NOLINTNEXTLINE(misc-no-recursion) 744 void ExpandPrivate(int pos, const SigningProvider& provider, FlatSigningProvider& out) const final 745 { 746 for (const auto& p : m_pubkey_args) { 747 p->GetPrivKey(pos, provider, out); 748 } 749 for (const auto& arg : m_subdescriptor_args) { 750 arg->ExpandPrivate(pos, provider, out); 751 } 752 } 753 754 std::optional<OutputType> GetOutputType() const override { return std::nullopt; } 755 756 std::optional<int64_t> ScriptSize() const override { return {}; } 757 758 /** A helper for MaxSatisfactionWeight. 759 * 760 * @param use_max_sig Whether to assume ECDSA signatures will have a high-r. 761 * @return The maximum size of the satisfaction in raw bytes (with no witness meaning). 762 */ 763 virtual std::optional<int64_t> MaxSatSize(bool use_max_sig) const { return {}; } 764 765 std::optional<int64_t> MaxSatisfactionWeight(bool) const override { return {}; } 766 767 std::optional<int64_t> MaxSatisfactionElems() const override { return {}; } 768 769 // NOLINTNEXTLINE(misc-no-recursion) 770 void GetPubKeys(std::set<CPubKey>& pubkeys, std::set<CExtPubKey>& ext_pubs) const override 771 { 772 for (const auto& p : m_pubkey_args) { 773 std::optional<CPubKey> pub = p->GetRootPubKey(); 774 if (pub) pubkeys.insert(*pub); 775 std::optional<CExtPubKey> ext_pub = p->GetRootExtPubKey(); 776 if (ext_pub) ext_pubs.insert(*ext_pub); 777 } 778 for (const auto& arg : m_subdescriptor_args) { 779 arg->GetPubKeys(pubkeys, ext_pubs); 780 } 781 } 782 783 virtual std::unique_ptr<DescriptorImpl> Clone() const = 0; 784 }; 785 786 /** A parsed addr(A) descriptor. */ 787 class AddressDescriptor final : public DescriptorImpl 788 { 789 const CTxDestination m_destination; 790 protected: 791 std::string ToStringExtra() const override { return EncodeDestination(m_destination); } 792 std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, std::span<const CScript>, FlatSigningProvider&) const override { return Vector(GetScriptForDestination(m_destination)); } 793 public: 794 AddressDescriptor(CTxDestination destination) : DescriptorImpl({}, "addr"), m_destination(std::move(destination)) {} 795 bool IsSolvable() const final { return false; } 796 797 std::optional<OutputType> GetOutputType() const override 798 { 799 return OutputTypeFromDestination(m_destination); 800 } 801 bool IsSingleType() const final { return true; } 802 bool IsSingleKey() const final { return false; } 803 bool ToPrivateString(const SigningProvider& arg, std::string& out) const final { return false; } 804 805 std::optional<int64_t> ScriptSize() const override { return GetScriptForDestination(m_destination).size(); } 806 std::unique_ptr<DescriptorImpl> Clone() const override 807 { 808 return std::make_unique<AddressDescriptor>(m_destination); 809 } 810 }; 811 812 /** A parsed raw(H) descriptor. */ 813 class RawDescriptor final : public DescriptorImpl 814 { 815 const CScript m_script; 816 protected: 817 std::string ToStringExtra() const override { return HexStr(m_script); } 818 std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, std::span<const CScript>, FlatSigningProvider&) const override { return Vector(m_script); } 819 public: 820 RawDescriptor(CScript script) : DescriptorImpl({}, "raw"), m_script(std::move(script)) {} 821 bool IsSolvable() const final { return false; } 822 823 std::optional<OutputType> GetOutputType() const override 824 { 825 CTxDestination dest; 826 ExtractDestination(m_script, dest); 827 return OutputTypeFromDestination(dest); 828 } 829 bool IsSingleType() const final { return true; } 830 bool IsSingleKey() const final { return false; } 831 bool ToPrivateString(const SigningProvider& arg, std::string& out) const final { return false; } 832 833 std::optional<int64_t> ScriptSize() const override { return m_script.size(); } 834 835 std::unique_ptr<DescriptorImpl> Clone() const override 836 { 837 return std::make_unique<RawDescriptor>(m_script); 838 } 839 }; 840 841 /** A parsed pk(P) descriptor. */ 842 class PKDescriptor final : public DescriptorImpl 843 { 844 private: 845 const bool m_xonly; 846 protected: 847 std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, std::span<const CScript>, FlatSigningProvider&) const override 848 { 849 if (m_xonly) { 850 CScript script = CScript() << ToByteVector(XOnlyPubKey(keys[0])) << OP_CHECKSIG; 851 return Vector(std::move(script)); 852 } else { 853 return Vector(GetScriptForRawPubKey(keys[0])); 854 } 855 } 856 public: 857 PKDescriptor(std::unique_ptr<PubkeyProvider> prov, bool xonly = false) : DescriptorImpl(Vector(std::move(prov)), "pk"), m_xonly(xonly) {} 858 bool IsSingleType() const final { return true; } 859 bool IsSingleKey() const final { return true; } 860 861 std::optional<int64_t> ScriptSize() const override { 862 return 1 + (m_xonly ? 32 : m_pubkey_args[0]->GetSize()) + 1; 863 } 864 865 std::optional<int64_t> MaxSatSize(bool use_max_sig) const override { 866 const auto ecdsa_sig_size = use_max_sig ? 72 : 71; 867 return 1 + (m_xonly ? 65 : ecdsa_sig_size); 868 } 869 870 std::optional<int64_t> MaxSatisfactionWeight(bool use_max_sig) const override { 871 return *MaxSatSize(use_max_sig) * WITNESS_SCALE_FACTOR; 872 } 873 874 std::optional<int64_t> MaxSatisfactionElems() const override { return 1; } 875 876 std::unique_ptr<DescriptorImpl> Clone() const override 877 { 878 return std::make_unique<PKDescriptor>(m_pubkey_args.at(0)->Clone(), m_xonly); 879 } 880 }; 881 882 /** A parsed pkh(P) descriptor. */ 883 class PKHDescriptor final : public DescriptorImpl 884 { 885 protected: 886 std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, std::span<const CScript>, FlatSigningProvider&) const override 887 { 888 CKeyID id = keys[0].GetID(); 889 return Vector(GetScriptForDestination(PKHash(id))); 890 } 891 public: 892 PKHDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), "pkh") {} 893 std::optional<OutputType> GetOutputType() const override { return OutputType::LEGACY; } 894 bool IsSingleType() const final { return true; } 895 bool IsSingleKey() const final { return true; } 896 897 std::optional<int64_t> ScriptSize() const override { return 1 + 1 + 1 + 20 + 1 + 1; } 898 899 std::optional<int64_t> MaxSatSize(bool use_max_sig) const override { 900 const auto sig_size = use_max_sig ? 72 : 71; 901 return 1 + sig_size + 1 + m_pubkey_args[0]->GetSize(); 902 } 903 904 std::optional<int64_t> MaxSatisfactionWeight(bool use_max_sig) const override { 905 return *MaxSatSize(use_max_sig) * WITNESS_SCALE_FACTOR; 906 } 907 908 std::optional<int64_t> MaxSatisfactionElems() const override { return 2; } 909 910 std::unique_ptr<DescriptorImpl> Clone() const override 911 { 912 return std::make_unique<PKHDescriptor>(m_pubkey_args.at(0)->Clone()); 913 } 914 }; 915 916 /** A parsed wpkh(P) descriptor. */ 917 class WPKHDescriptor final : public DescriptorImpl 918 { 919 protected: 920 std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, std::span<const CScript>, FlatSigningProvider&) const override 921 { 922 CKeyID id = keys[0].GetID(); 923 return Vector(GetScriptForDestination(WitnessV0KeyHash(id))); 924 } 925 public: 926 WPKHDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), "wpkh") {} 927 std::optional<OutputType> GetOutputType() const override { return OutputType::BECH32; } 928 bool IsSingleType() const final { return true; } 929 bool IsSingleKey() const final { return true; } 930 931 std::optional<int64_t> ScriptSize() const override { return 1 + 1 + 20; } 932 933 std::optional<int64_t> MaxSatSize(bool use_max_sig) const override { 934 const auto sig_size = use_max_sig ? 72 : 71; 935 return (1 + sig_size + 1 + 33); 936 } 937 938 std::optional<int64_t> MaxSatisfactionWeight(bool use_max_sig) const override { 939 return MaxSatSize(use_max_sig); 940 } 941 942 std::optional<int64_t> MaxSatisfactionElems() const override { return 2; } 943 944 std::unique_ptr<DescriptorImpl> Clone() const override 945 { 946 return std::make_unique<WPKHDescriptor>(m_pubkey_args.at(0)->Clone()); 947 } 948 }; 949 950 /** A parsed combo(P) descriptor. */ 951 class ComboDescriptor final : public DescriptorImpl 952 { 953 protected: 954 std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, std::span<const CScript>, FlatSigningProvider& out) const override 955 { 956 std::vector<CScript> ret; 957 CKeyID id = keys[0].GetID(); 958 ret.emplace_back(GetScriptForRawPubKey(keys[0])); // P2PK 959 ret.emplace_back(GetScriptForDestination(PKHash(id))); // P2PKH 960 if (keys[0].IsCompressed()) { 961 CScript p2wpkh = GetScriptForDestination(WitnessV0KeyHash(id)); 962 out.scripts.emplace(CScriptID(p2wpkh), p2wpkh); 963 ret.emplace_back(p2wpkh); 964 ret.emplace_back(GetScriptForDestination(ScriptHash(p2wpkh))); // P2SH-P2WPKH 965 } 966 return ret; 967 } 968 public: 969 ComboDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), "combo") {} 970 bool IsSingleType() const final { return false; } 971 bool IsSingleKey() const final { return true; } 972 std::unique_ptr<DescriptorImpl> Clone() const override 973 { 974 return std::make_unique<ComboDescriptor>(m_pubkey_args.at(0)->Clone()); 975 } 976 }; 977 978 /** A parsed multi(...) or sortedmulti(...) descriptor */ 979 class MultisigDescriptor final : public DescriptorImpl 980 { 981 const int m_threshold; 982 const bool m_sorted; 983 protected: 984 std::string ToStringExtra() const override { return strprintf("%i", m_threshold); } 985 std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, std::span<const CScript>, FlatSigningProvider&) const override { 986 if (m_sorted) { 987 std::vector<CPubKey> sorted_keys(keys); 988 std::sort(sorted_keys.begin(), sorted_keys.end()); 989 return Vector(GetScriptForMultisig(m_threshold, sorted_keys)); 990 } 991 return Vector(GetScriptForMultisig(m_threshold, keys)); 992 } 993 public: 994 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) {} 995 bool IsSingleType() const final { return true; } 996 bool IsSingleKey() const final { return false; } 997 998 std::optional<int64_t> ScriptSize() const override { 999 const auto n_keys = m_pubkey_args.size(); 1000 auto op = [](int64_t acc, const std::unique_ptr<PubkeyProvider>& pk) { return acc + 1 + pk->GetSize();}; 1001 const auto pubkeys_size{std::accumulate(m_pubkey_args.begin(), m_pubkey_args.end(), int64_t{0}, op)}; 1002 return 1 + BuildScript(n_keys).size() + BuildScript(m_threshold).size() + pubkeys_size; 1003 } 1004 1005 std::optional<int64_t> MaxSatSize(bool use_max_sig) const override { 1006 const auto sig_size = use_max_sig ? 72 : 71; 1007 return (1 + (1 + sig_size) * m_threshold); 1008 } 1009 1010 std::optional<int64_t> MaxSatisfactionWeight(bool use_max_sig) const override { 1011 return *MaxSatSize(use_max_sig) * WITNESS_SCALE_FACTOR; 1012 } 1013 1014 std::optional<int64_t> MaxSatisfactionElems() const override { return 1 + m_threshold; } 1015 1016 std::unique_ptr<DescriptorImpl> Clone() const override 1017 { 1018 std::vector<std::unique_ptr<PubkeyProvider>> providers; 1019 providers.reserve(m_pubkey_args.size()); 1020 std::transform(m_pubkey_args.begin(), m_pubkey_args.end(), providers.begin(), [](const std::unique_ptr<PubkeyProvider>& p) { return p->Clone(); }); 1021 return std::make_unique<MultisigDescriptor>(m_threshold, std::move(providers), m_sorted); 1022 } 1023 }; 1024 1025 /** A parsed (sorted)multi_a(...) descriptor. Always uses x-only pubkeys. */ 1026 class MultiADescriptor final : public DescriptorImpl 1027 { 1028 const int m_threshold; 1029 const bool m_sorted; 1030 protected: 1031 std::string ToStringExtra() const override { return strprintf("%i", m_threshold); } 1032 std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, std::span<const CScript>, FlatSigningProvider&) const override { 1033 CScript ret; 1034 std::vector<XOnlyPubKey> xkeys; 1035 xkeys.reserve(keys.size()); 1036 for (const auto& key : keys) xkeys.emplace_back(key); 1037 if (m_sorted) std::sort(xkeys.begin(), xkeys.end()); 1038 ret << ToByteVector(xkeys[0]) << OP_CHECKSIG; 1039 for (size_t i = 1; i < keys.size(); ++i) { 1040 ret << ToByteVector(xkeys[i]) << OP_CHECKSIGADD; 1041 } 1042 ret << m_threshold << OP_NUMEQUAL; 1043 return Vector(std::move(ret)); 1044 } 1045 public: 1046 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) {} 1047 bool IsSingleType() const final { return true; } 1048 bool IsSingleKey() const final { return false; } 1049 1050 std::optional<int64_t> ScriptSize() const override { 1051 const auto n_keys = m_pubkey_args.size(); 1052 return (1 + 32 + 1) * n_keys + BuildScript(m_threshold).size() + 1; 1053 } 1054 1055 std::optional<int64_t> MaxSatSize(bool use_max_sig) const override { 1056 return (1 + 65) * m_threshold + (m_pubkey_args.size() - m_threshold); 1057 } 1058 1059 std::optional<int64_t> MaxSatisfactionElems() const override { return m_pubkey_args.size(); } 1060 1061 std::unique_ptr<DescriptorImpl> Clone() const override 1062 { 1063 std::vector<std::unique_ptr<PubkeyProvider>> providers; 1064 providers.reserve(m_pubkey_args.size()); 1065 for (const auto& arg : m_pubkey_args) { 1066 providers.push_back(arg->Clone()); 1067 } 1068 return std::make_unique<MultiADescriptor>(m_threshold, std::move(providers), m_sorted); 1069 } 1070 }; 1071 1072 /** A parsed sh(...) descriptor. */ 1073 class SHDescriptor final : public DescriptorImpl 1074 { 1075 protected: 1076 std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, std::span<const CScript> scripts, FlatSigningProvider& out) const override 1077 { 1078 auto ret = Vector(GetScriptForDestination(ScriptHash(scripts[0]))); 1079 if (ret.size()) out.scripts.emplace(CScriptID(scripts[0]), scripts[0]); 1080 return ret; 1081 } 1082 1083 bool IsSegwit() const { return m_subdescriptor_args[0]->GetOutputType() == OutputType::BECH32; } 1084 1085 public: 1086 SHDescriptor(std::unique_ptr<DescriptorImpl> desc) : DescriptorImpl({}, std::move(desc), "sh") {} 1087 1088 std::optional<OutputType> GetOutputType() const override 1089 { 1090 assert(m_subdescriptor_args.size() == 1); 1091 if (IsSegwit()) return OutputType::P2SH_SEGWIT; 1092 return OutputType::LEGACY; 1093 } 1094 bool IsSingleType() const final { return true; } 1095 bool IsSingleKey() const final { return m_subdescriptor_args[0]->IsSingleKey(); } 1096 1097 std::optional<int64_t> ScriptSize() const override { return 1 + 1 + 20 + 1; } 1098 1099 std::optional<int64_t> MaxSatisfactionWeight(bool use_max_sig) const override { 1100 if (const auto sat_size = m_subdescriptor_args[0]->MaxSatSize(use_max_sig)) { 1101 if (const auto subscript_size = m_subdescriptor_args[0]->ScriptSize()) { 1102 // The subscript is never witness data. 1103 const auto subscript_weight = (1 + *subscript_size) * WITNESS_SCALE_FACTOR; 1104 // The weight depends on whether the inner descriptor is satisfied using the witness stack. 1105 if (IsSegwit()) return subscript_weight + *sat_size; 1106 return subscript_weight + *sat_size * WITNESS_SCALE_FACTOR; 1107 } 1108 } 1109 return {}; 1110 } 1111 1112 std::optional<int64_t> MaxSatisfactionElems() const override { 1113 if (const auto sub_elems = m_subdescriptor_args[0]->MaxSatisfactionElems()) return 1 + *sub_elems; 1114 return {}; 1115 } 1116 1117 std::unique_ptr<DescriptorImpl> Clone() const override 1118 { 1119 return std::make_unique<SHDescriptor>(m_subdescriptor_args.at(0)->Clone()); 1120 } 1121 }; 1122 1123 /** A parsed wsh(...) descriptor. */ 1124 class WSHDescriptor final : public DescriptorImpl 1125 { 1126 protected: 1127 std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, std::span<const CScript> scripts, FlatSigningProvider& out) const override 1128 { 1129 auto ret = Vector(GetScriptForDestination(WitnessV0ScriptHash(scripts[0]))); 1130 if (ret.size()) out.scripts.emplace(CScriptID(scripts[0]), scripts[0]); 1131 return ret; 1132 } 1133 public: 1134 WSHDescriptor(std::unique_ptr<DescriptorImpl> desc) : DescriptorImpl({}, std::move(desc), "wsh") {} 1135 std::optional<OutputType> GetOutputType() const override { return OutputType::BECH32; } 1136 bool IsSingleType() const final { return true; } 1137 bool IsSingleKey() const final { return m_subdescriptor_args[0]->IsSingleKey(); } 1138 1139 std::optional<int64_t> ScriptSize() const override { return 1 + 1 + 32; } 1140 1141 std::optional<int64_t> MaxSatSize(bool use_max_sig) const override { 1142 if (const auto sat_size = m_subdescriptor_args[0]->MaxSatSize(use_max_sig)) { 1143 if (const auto subscript_size = m_subdescriptor_args[0]->ScriptSize()) { 1144 return GetSizeOfCompactSize(*subscript_size) + *subscript_size + *sat_size; 1145 } 1146 } 1147 return {}; 1148 } 1149 1150 std::optional<int64_t> MaxSatisfactionWeight(bool use_max_sig) const override { 1151 return MaxSatSize(use_max_sig); 1152 } 1153 1154 std::optional<int64_t> MaxSatisfactionElems() const override { 1155 if (const auto sub_elems = m_subdescriptor_args[0]->MaxSatisfactionElems()) return 1 + *sub_elems; 1156 return {}; 1157 } 1158 1159 std::unique_ptr<DescriptorImpl> Clone() const override 1160 { 1161 return std::make_unique<WSHDescriptor>(m_subdescriptor_args.at(0)->Clone()); 1162 } 1163 }; 1164 1165 /** A parsed tr(...) descriptor. */ 1166 class TRDescriptor final : public DescriptorImpl 1167 { 1168 std::vector<int> m_depths; 1169 protected: 1170 std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, std::span<const CScript> scripts, FlatSigningProvider& out) const override 1171 { 1172 TaprootBuilder builder; 1173 assert(m_depths.size() == scripts.size()); 1174 for (size_t pos = 0; pos < m_depths.size(); ++pos) { 1175 builder.Add(m_depths[pos], scripts[pos], TAPROOT_LEAF_TAPSCRIPT); 1176 } 1177 if (!builder.IsComplete()) return {}; 1178 assert(keys.size() == 1); 1179 XOnlyPubKey xpk(keys[0]); 1180 if (!xpk.IsFullyValid()) return {}; 1181 builder.Finalize(xpk); 1182 WitnessV1Taproot output = builder.GetOutput(); 1183 out.tr_trees[output] = builder; 1184 return Vector(GetScriptForDestination(output)); 1185 } 1186 bool ToStringSubScriptHelper(const SigningProvider* arg, std::string& ret, const StringType type, const DescriptorCache* cache = nullptr) const override 1187 { 1188 if (m_depths.empty()) return true; 1189 std::vector<bool> path; 1190 for (size_t pos = 0; pos < m_depths.size(); ++pos) { 1191 if (pos) ret += ','; 1192 while ((int)path.size() <= m_depths[pos]) { 1193 if (path.size()) ret += '{'; 1194 path.push_back(false); 1195 } 1196 std::string tmp; 1197 if (!m_subdescriptor_args[pos]->ToStringHelper(arg, tmp, type, cache)) return false; 1198 ret += tmp; 1199 while (!path.empty() && path.back()) { 1200 if (path.size() > 1) ret += '}'; 1201 path.pop_back(); 1202 } 1203 if (!path.empty()) path.back() = true; 1204 } 1205 return true; 1206 } 1207 public: 1208 TRDescriptor(std::unique_ptr<PubkeyProvider> internal_key, std::vector<std::unique_ptr<DescriptorImpl>> descs, std::vector<int> depths) : 1209 DescriptorImpl(Vector(std::move(internal_key)), std::move(descs), "tr"), m_depths(std::move(depths)) 1210 { 1211 assert(m_subdescriptor_args.size() == m_depths.size()); 1212 } 1213 std::optional<OutputType> GetOutputType() const override { return OutputType::BECH32M; } 1214 bool IsSingleType() const final { return true; } 1215 bool IsSingleKey() const final { return false; } 1216 1217 std::optional<int64_t> ScriptSize() const override { return 1 + 1 + 32; } 1218 1219 std::optional<int64_t> MaxSatisfactionWeight(bool) const override { 1220 // FIXME: We assume keypath spend, which can lead to very large underestimations. 1221 return 1 + 65; 1222 } 1223 1224 std::optional<int64_t> MaxSatisfactionElems() const override { 1225 // FIXME: See above, we assume keypath spend. 1226 return 1; 1227 } 1228 1229 std::unique_ptr<DescriptorImpl> Clone() const override 1230 { 1231 std::vector<std::unique_ptr<DescriptorImpl>> subdescs; 1232 subdescs.reserve(m_subdescriptor_args.size()); 1233 std::transform(m_subdescriptor_args.begin(), m_subdescriptor_args.end(), subdescs.begin(), [](const std::unique_ptr<DescriptorImpl>& d) { return d->Clone(); }); 1234 return std::make_unique<TRDescriptor>(m_pubkey_args.at(0)->Clone(), std::move(subdescs), m_depths); 1235 } 1236 }; 1237 1238 /* We instantiate Miniscript here with a simple integer as key type. 1239 * The value of these key integers are an index in the 1240 * DescriptorImpl::m_pubkey_args vector. 1241 */ 1242 1243 /** 1244 * The context for converting a Miniscript descriptor into a Script. 1245 */ 1246 class ScriptMaker { 1247 //! Keys contained in the Miniscript (the evaluation of DescriptorImpl::m_pubkey_args). 1248 const std::vector<CPubKey>& m_keys; 1249 //! The script context we're operating within (Tapscript or P2WSH). 1250 const miniscript::MiniscriptContext m_script_ctx; 1251 1252 //! Get the ripemd160(sha256()) hash of this key. 1253 //! Any key that is valid in a descriptor serializes as 32 bytes within a Tapscript context. So we 1254 //! must not hash the sign-bit byte in this case. 1255 uint160 GetHash160(uint32_t key) const { 1256 if (miniscript::IsTapscript(m_script_ctx)) { 1257 return Hash160(XOnlyPubKey{m_keys[key]}); 1258 } 1259 return m_keys[key].GetID(); 1260 } 1261 1262 public: 1263 ScriptMaker(const std::vector<CPubKey>& keys LIFETIMEBOUND, const miniscript::MiniscriptContext script_ctx) : m_keys(keys), m_script_ctx{script_ctx} {} 1264 1265 std::vector<unsigned char> ToPKBytes(uint32_t key) const { 1266 // In Tapscript keys always serialize as x-only, whether an x-only key was used in the descriptor or not. 1267 if (!miniscript::IsTapscript(m_script_ctx)) { 1268 return {m_keys[key].begin(), m_keys[key].end()}; 1269 } 1270 const XOnlyPubKey xonly_pubkey{m_keys[key]}; 1271 return {xonly_pubkey.begin(), xonly_pubkey.end()}; 1272 } 1273 1274 std::vector<unsigned char> ToPKHBytes(uint32_t key) const { 1275 auto id = GetHash160(key); 1276 return {id.begin(), id.end()}; 1277 } 1278 }; 1279 1280 /** 1281 * The context for converting a Miniscript descriptor to its textual form. 1282 */ 1283 class StringMaker { 1284 //! To convert private keys for private descriptors. 1285 const SigningProvider* m_arg; 1286 //! Keys contained in the Miniscript (a reference to DescriptorImpl::m_pubkey_args). 1287 const std::vector<std::unique_ptr<PubkeyProvider>>& m_pubkeys; 1288 //! Whether to serialize keys as private or public. 1289 bool m_private; 1290 1291 public: 1292 StringMaker(const SigningProvider* arg LIFETIMEBOUND, const std::vector<std::unique_ptr<PubkeyProvider>>& pubkeys LIFETIMEBOUND, bool priv) 1293 : m_arg(arg), m_pubkeys(pubkeys), m_private(priv) {} 1294 1295 std::optional<std::string> ToString(uint32_t key) const 1296 { 1297 std::string ret; 1298 if (m_private) { 1299 if (!m_pubkeys[key]->ToPrivateString(*m_arg, ret)) return {}; 1300 } else { 1301 ret = m_pubkeys[key]->ToString(); 1302 } 1303 return ret; 1304 } 1305 }; 1306 1307 class MiniscriptDescriptor final : public DescriptorImpl 1308 { 1309 private: 1310 miniscript::NodeRef<uint32_t> m_node; 1311 1312 protected: 1313 std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, std::span<const CScript> scripts, 1314 FlatSigningProvider& provider) const override 1315 { 1316 const auto script_ctx{m_node->GetMsCtx()}; 1317 for (const auto& key : keys) { 1318 if (miniscript::IsTapscript(script_ctx)) { 1319 provider.pubkeys.emplace(Hash160(XOnlyPubKey{key}), key); 1320 } else { 1321 provider.pubkeys.emplace(key.GetID(), key); 1322 } 1323 } 1324 return Vector(m_node->ToScript(ScriptMaker(keys, script_ctx))); 1325 } 1326 1327 public: 1328 MiniscriptDescriptor(std::vector<std::unique_ptr<PubkeyProvider>> providers, miniscript::NodeRef<uint32_t> node) 1329 : DescriptorImpl(std::move(providers), "?"), m_node(std::move(node)) {} 1330 1331 bool ToStringHelper(const SigningProvider* arg, std::string& out, const StringType type, 1332 const DescriptorCache* cache = nullptr) const override 1333 { 1334 if (const auto res = m_node->ToString(StringMaker(arg, m_pubkey_args, type == StringType::PRIVATE))) { 1335 out = *res; 1336 return true; 1337 } 1338 return false; 1339 } 1340 1341 bool IsSolvable() const override { return true; } 1342 bool IsSingleType() const final { return true; } 1343 bool IsSingleKey() const final { return false; } 1344 1345 std::optional<int64_t> ScriptSize() const override { return m_node->ScriptSize(); } 1346 1347 std::optional<int64_t> MaxSatSize(bool) const override { 1348 // For Miniscript we always assume high-R ECDSA signatures. 1349 return m_node->GetWitnessSize(); 1350 } 1351 1352 std::optional<int64_t> MaxSatisfactionElems() const override { 1353 return m_node->GetStackSize(); 1354 } 1355 1356 std::unique_ptr<DescriptorImpl> Clone() const override 1357 { 1358 std::vector<std::unique_ptr<PubkeyProvider>> providers; 1359 providers.reserve(m_pubkey_args.size()); 1360 for (const auto& arg : m_pubkey_args) { 1361 providers.push_back(arg->Clone()); 1362 } 1363 return std::make_unique<MiniscriptDescriptor>(std::move(providers), m_node->Clone()); 1364 } 1365 }; 1366 1367 /** A parsed rawtr(...) descriptor. */ 1368 class RawTRDescriptor final : public DescriptorImpl 1369 { 1370 protected: 1371 std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, std::span<const CScript> scripts, FlatSigningProvider& out) const override 1372 { 1373 assert(keys.size() == 1); 1374 XOnlyPubKey xpk(keys[0]); 1375 if (!xpk.IsFullyValid()) return {}; 1376 WitnessV1Taproot output{xpk}; 1377 return Vector(GetScriptForDestination(output)); 1378 } 1379 public: 1380 RawTRDescriptor(std::unique_ptr<PubkeyProvider> output_key) : DescriptorImpl(Vector(std::move(output_key)), "rawtr") {} 1381 std::optional<OutputType> GetOutputType() const override { return OutputType::BECH32M; } 1382 bool IsSingleType() const final { return true; } 1383 bool IsSingleKey() const final { return false; } 1384 1385 std::optional<int64_t> ScriptSize() const override { return 1 + 1 + 32; } 1386 1387 std::optional<int64_t> MaxSatisfactionWeight(bool) const override { 1388 // We can't know whether there is a script path, so assume key path spend. 1389 return 1 + 65; 1390 } 1391 1392 std::optional<int64_t> MaxSatisfactionElems() const override { 1393 // See above, we assume keypath spend. 1394 return 1; 1395 } 1396 1397 std::unique_ptr<DescriptorImpl> Clone() const override 1398 { 1399 return std::make_unique<RawTRDescriptor>(m_pubkey_args.at(0)->Clone()); 1400 } 1401 }; 1402 1403 //////////////////////////////////////////////////////////////////////////// 1404 // Parser // 1405 //////////////////////////////////////////////////////////////////////////// 1406 1407 enum class ParseScriptContext { 1408 TOP, //!< Top-level context (script goes directly in scriptPubKey) 1409 P2SH, //!< Inside sh() (script becomes P2SH redeemScript) 1410 P2WPKH, //!< Inside wpkh() (no script, pubkey only) 1411 P2WSH, //!< Inside wsh() (script becomes v0 witness script) 1412 P2TR, //!< Inside tr() (either internal key, or BIP342 script leaf) 1413 }; 1414 1415 std::optional<uint32_t> ParseKeyPathNum(std::span<const char> elem, bool& apostrophe, std::string& error) 1416 { 1417 bool hardened = false; 1418 if (elem.size() > 0) { 1419 const char last = elem[elem.size() - 1]; 1420 if (last == '\'' || last == 'h') { 1421 elem = elem.first(elem.size() - 1); 1422 hardened = true; 1423 apostrophe = last == '\''; 1424 } 1425 } 1426 const auto p{ToIntegral<uint32_t>(std::string_view{elem.begin(), elem.end()})}; 1427 if (!p) { 1428 error = strprintf("Key path value '%s' is not a valid uint32", std::string_view{elem.begin(), elem.end()}); 1429 return std::nullopt; 1430 } else if (*p > 0x7FFFFFFFUL) { 1431 error = strprintf("Key path value %u is out of range", *p); 1432 return std::nullopt; 1433 } 1434 1435 return std::make_optional<uint32_t>(*p | (((uint32_t)hardened) << 31)); 1436 } 1437 1438 /** 1439 * Parse a key path, being passed a split list of elements (the first element is ignored because it is always the key). 1440 * 1441 * @param[in] split BIP32 path string, using either ' or h for hardened derivation 1442 * @param[out] out Vector of parsed key paths 1443 * @param[out] apostrophe only updated if hardened derivation is found 1444 * @param[out] error parsing error message 1445 * @param[in] allow_multipath Allows the parsed path to use the multipath specifier 1446 * @returns false if parsing failed 1447 **/ 1448 [[nodiscard]] bool ParseKeyPath(const std::vector<std::span<const char>>& split, std::vector<KeyPath>& out, bool& apostrophe, std::string& error, bool allow_multipath) 1449 { 1450 KeyPath path; 1451 struct MultipathSubstitutes { 1452 size_t placeholder_index; 1453 std::vector<uint32_t> values; 1454 }; 1455 std::optional<MultipathSubstitutes> substitutes; 1456 1457 for (size_t i = 1; i < split.size(); ++i) { 1458 const std::span<const char>& elem = split[i]; 1459 1460 // Check if element contains multipath specifier 1461 if (!elem.empty() && elem.front() == '<' && elem.back() == '>') { 1462 if (!allow_multipath) { 1463 error = strprintf("Key path value '%s' specifies multipath in a section where multipath is not allowed", std::string(elem.begin(), elem.end())); 1464 return false; 1465 } 1466 if (substitutes) { 1467 error = "Multiple multipath key path specifiers found"; 1468 return false; 1469 } 1470 1471 // Parse each possible value 1472 std::vector<std::span<const char>> nums = Split(std::span(elem.begin()+1, elem.end()-1), ";"); 1473 if (nums.size() < 2) { 1474 error = "Multipath key path specifiers must have at least two items"; 1475 return false; 1476 } 1477 1478 substitutes.emplace(); 1479 std::unordered_set<uint32_t> seen_substitutes; 1480 for (const auto& num : nums) { 1481 const auto& op_num = ParseKeyPathNum(num, apostrophe, error); 1482 if (!op_num) return false; 1483 auto [_, inserted] = seen_substitutes.insert(*op_num); 1484 if (!inserted) { 1485 error = strprintf("Duplicated key path value %u in multipath specifier", *op_num); 1486 return false; 1487 } 1488 substitutes->values.emplace_back(*op_num); 1489 } 1490 1491 path.emplace_back(); // Placeholder for multipath segment 1492 substitutes->placeholder_index = path.size() - 1; 1493 } else { 1494 const auto& op_num = ParseKeyPathNum(elem, apostrophe, error); 1495 if (!op_num) return false; 1496 path.emplace_back(*op_num); 1497 } 1498 } 1499 1500 if (!substitutes) { 1501 out.emplace_back(std::move(path)); 1502 } else { 1503 // Replace the multipath placeholder with each value while generating paths 1504 for (uint32_t substitute : substitutes->values) { 1505 KeyPath branch_path = path; 1506 branch_path[substitutes->placeholder_index] = substitute; 1507 out.emplace_back(std::move(branch_path)); 1508 } 1509 } 1510 return true; 1511 } 1512 1513 /** Parse a public key that excludes origin information. */ 1514 std::vector<std::unique_ptr<PubkeyProvider>> ParsePubkeyInner(uint32_t key_exp_index, const std::span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, bool& apostrophe, std::string& error) 1515 { 1516 std::vector<std::unique_ptr<PubkeyProvider>> ret; 1517 bool permit_uncompressed = ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH; 1518 auto split = Split(sp, '/'); 1519 std::string str(split[0].begin(), split[0].end()); 1520 if (str.size() == 0) { 1521 error = "No key provided"; 1522 return {}; 1523 } 1524 if (IsSpace(str.front()) || IsSpace(str.back())) { 1525 error = strprintf("Key '%s' is invalid due to whitespace", str); 1526 return {}; 1527 } 1528 if (split.size() == 1) { 1529 if (IsHex(str)) { 1530 std::vector<unsigned char> data = ParseHex(str); 1531 CPubKey pubkey(data); 1532 if (pubkey.IsValid() && !pubkey.IsValidNonHybrid()) { 1533 error = "Hybrid public keys are not allowed"; 1534 return {}; 1535 } 1536 if (pubkey.IsFullyValid()) { 1537 if (permit_uncompressed || pubkey.IsCompressed()) { 1538 ret.emplace_back(std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey, false)); 1539 return ret; 1540 } else { 1541 error = "Uncompressed keys are not allowed"; 1542 return {}; 1543 } 1544 } else if (data.size() == 32 && ctx == ParseScriptContext::P2TR) { 1545 unsigned char fullkey[33] = {0x02}; 1546 std::copy(data.begin(), data.end(), fullkey + 1); 1547 pubkey.Set(std::begin(fullkey), std::end(fullkey)); 1548 if (pubkey.IsFullyValid()) { 1549 ret.emplace_back(std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey, true)); 1550 return ret; 1551 } 1552 } 1553 error = strprintf("Pubkey '%s' is invalid", str); 1554 return {}; 1555 } 1556 CKey key = DecodeSecret(str); 1557 if (key.IsValid()) { 1558 if (permit_uncompressed || key.IsCompressed()) { 1559 CPubKey pubkey = key.GetPubKey(); 1560 out.keys.emplace(pubkey.GetID(), key); 1561 ret.emplace_back(std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey, ctx == ParseScriptContext::P2TR)); 1562 return ret; 1563 } else { 1564 error = "Uncompressed keys are not allowed"; 1565 return {}; 1566 } 1567 } 1568 } 1569 CExtKey extkey = DecodeExtKey(str); 1570 CExtPubKey extpubkey = DecodeExtPubKey(str); 1571 if (!extkey.key.IsValid() && !extpubkey.pubkey.IsValid()) { 1572 error = strprintf("key '%s' is not valid", str); 1573 return {}; 1574 } 1575 std::vector<KeyPath> paths; 1576 DeriveType type = DeriveType::NO; 1577 if (std::ranges::equal(split.back(), std::span{"*"}.first(1))) { 1578 split.pop_back(); 1579 type = DeriveType::UNHARDENED; 1580 } else if (std::ranges::equal(split.back(), std::span{"*'"}.first(2)) || std::ranges::equal(split.back(), std::span{"*h"}.first(2))) { 1581 apostrophe = std::ranges::equal(split.back(), std::span{"*'"}.first(2)); 1582 split.pop_back(); 1583 type = DeriveType::HARDENED; 1584 } 1585 if (!ParseKeyPath(split, paths, apostrophe, error, /*allow_multipath=*/true)) return {}; 1586 if (extkey.key.IsValid()) { 1587 extpubkey = extkey.Neuter(); 1588 out.keys.emplace(extpubkey.pubkey.GetID(), extkey.key); 1589 } 1590 for (auto& path : paths) { 1591 ret.emplace_back(std::make_unique<BIP32PubkeyProvider>(key_exp_index, extpubkey, std::move(path), type, apostrophe)); 1592 } 1593 return ret; 1594 } 1595 1596 /** Parse a public key including origin information (if enabled). */ 1597 std::vector<std::unique_ptr<PubkeyProvider>> ParsePubkey(uint32_t key_exp_index, const std::span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error) 1598 { 1599 std::vector<std::unique_ptr<PubkeyProvider>> ret; 1600 auto origin_split = Split(sp, ']'); 1601 if (origin_split.size() > 2) { 1602 error = "Multiple ']' characters found for a single pubkey"; 1603 return {}; 1604 } 1605 // This is set if either the origin or path suffix contains a hardened derivation. 1606 bool apostrophe = false; 1607 if (origin_split.size() == 1) { 1608 return ParsePubkeyInner(key_exp_index, origin_split[0], ctx, out, apostrophe, error); 1609 } 1610 if (origin_split[0].empty() || origin_split[0][0] != '[') { 1611 error = strprintf("Key origin start '[ character expected but not found, got '%c' instead", 1612 origin_split[0].empty() ? /** empty, implies split char */ ']' : origin_split[0][0]); 1613 return {}; 1614 } 1615 auto slash_split = Split(origin_split[0].subspan(1), '/'); 1616 if (slash_split[0].size() != 8) { 1617 error = strprintf("Fingerprint is not 4 bytes (%u characters instead of 8 characters)", slash_split[0].size()); 1618 return {}; 1619 } 1620 std::string fpr_hex = std::string(slash_split[0].begin(), slash_split[0].end()); 1621 if (!IsHex(fpr_hex)) { 1622 error = strprintf("Fingerprint '%s' is not hex", fpr_hex); 1623 return {}; 1624 } 1625 auto fpr_bytes = ParseHex(fpr_hex); 1626 KeyOriginInfo info; 1627 static_assert(sizeof(info.fingerprint) == 4, "Fingerprint must be 4 bytes"); 1628 assert(fpr_bytes.size() == 4); 1629 std::copy(fpr_bytes.begin(), fpr_bytes.end(), info.fingerprint); 1630 std::vector<KeyPath> path; 1631 if (!ParseKeyPath(slash_split, path, apostrophe, error, /*allow_multipath=*/false)) return {}; 1632 info.path = path.at(0); 1633 auto providers = ParsePubkeyInner(key_exp_index, origin_split[1], ctx, out, apostrophe, error); 1634 if (providers.empty()) return {}; 1635 ret.reserve(providers.size()); 1636 for (auto& prov : providers) { 1637 ret.emplace_back(std::make_unique<OriginPubkeyProvider>(key_exp_index, info, std::move(prov), apostrophe)); 1638 } 1639 return ret; 1640 } 1641 1642 std::unique_ptr<PubkeyProvider> InferPubkey(const CPubKey& pubkey, ParseScriptContext ctx, const SigningProvider& provider) 1643 { 1644 // Key cannot be hybrid 1645 if (!pubkey.IsValidNonHybrid()) { 1646 return nullptr; 1647 } 1648 // Uncompressed is only allowed in TOP and P2SH contexts 1649 if (ctx != ParseScriptContext::TOP && ctx != ParseScriptContext::P2SH && !pubkey.IsCompressed()) { 1650 return nullptr; 1651 } 1652 std::unique_ptr<PubkeyProvider> key_provider = std::make_unique<ConstPubkeyProvider>(0, pubkey, false); 1653 KeyOriginInfo info; 1654 if (provider.GetKeyOrigin(pubkey.GetID(), info)) { 1655 return std::make_unique<OriginPubkeyProvider>(0, std::move(info), std::move(key_provider), /*apostrophe=*/false); 1656 } 1657 return key_provider; 1658 } 1659 1660 std::unique_ptr<PubkeyProvider> InferXOnlyPubkey(const XOnlyPubKey& xkey, ParseScriptContext ctx, const SigningProvider& provider) 1661 { 1662 CPubKey pubkey{xkey.GetEvenCorrespondingCPubKey()}; 1663 std::unique_ptr<PubkeyProvider> key_provider = std::make_unique<ConstPubkeyProvider>(0, pubkey, true); 1664 KeyOriginInfo info; 1665 if (provider.GetKeyOriginByXOnly(xkey, info)) { 1666 return std::make_unique<OriginPubkeyProvider>(0, std::move(info), std::move(key_provider), /*apostrophe=*/false); 1667 } 1668 return key_provider; 1669 } 1670 1671 /** 1672 * The context for parsing a Miniscript descriptor (either from Script or from its textual representation). 1673 */ 1674 struct KeyParser { 1675 //! The Key type is an index in DescriptorImpl::m_pubkey_args 1676 using Key = uint32_t; 1677 //! Must not be nullptr if parsing from string. 1678 FlatSigningProvider* m_out; 1679 //! Must not be nullptr if parsing from Script. 1680 const SigningProvider* m_in; 1681 //! List of multipath expanded keys contained in the Miniscript. 1682 mutable std::vector<std::vector<std::unique_ptr<PubkeyProvider>>> m_keys; 1683 //! Used to detect key parsing errors within a Miniscript. 1684 mutable std::string m_key_parsing_error; 1685 //! The script context we're operating within (Tapscript or P2WSH). 1686 const miniscript::MiniscriptContext m_script_ctx; 1687 //! The number of keys that were parsed before starting to parse this Miniscript descriptor. 1688 uint32_t m_offset; 1689 1690 KeyParser(FlatSigningProvider* out LIFETIMEBOUND, const SigningProvider* in LIFETIMEBOUND, 1691 miniscript::MiniscriptContext ctx, uint32_t offset = 0) 1692 : m_out(out), m_in(in), m_script_ctx(ctx), m_offset(offset) {} 1693 1694 bool KeyCompare(const Key& a, const Key& b) const { 1695 return *m_keys.at(a).at(0) < *m_keys.at(b).at(0); 1696 } 1697 1698 ParseScriptContext ParseContext() const { 1699 switch (m_script_ctx) { 1700 case miniscript::MiniscriptContext::P2WSH: return ParseScriptContext::P2WSH; 1701 case miniscript::MiniscriptContext::TAPSCRIPT: return ParseScriptContext::P2TR; 1702 } 1703 assert(false); 1704 } 1705 1706 template<typename I> std::optional<Key> FromString(I begin, I end) const 1707 { 1708 assert(m_out); 1709 Key key = m_keys.size(); 1710 auto pk = ParsePubkey(m_offset + key, {&*begin, &*end}, ParseContext(), *m_out, m_key_parsing_error); 1711 if (pk.empty()) return {}; 1712 m_keys.emplace_back(std::move(pk)); 1713 return key; 1714 } 1715 1716 std::optional<std::string> ToString(const Key& key) const 1717 { 1718 return m_keys.at(key).at(0)->ToString(); 1719 } 1720 1721 template<typename I> std::optional<Key> FromPKBytes(I begin, I end) const 1722 { 1723 assert(m_in); 1724 Key key = m_keys.size(); 1725 if (miniscript::IsTapscript(m_script_ctx) && end - begin == 32) { 1726 XOnlyPubKey pubkey; 1727 std::copy(begin, end, pubkey.begin()); 1728 if (auto pubkey_provider = InferXOnlyPubkey(pubkey, ParseContext(), *m_in)) { 1729 m_keys.emplace_back(); 1730 m_keys.back().push_back(std::move(pubkey_provider)); 1731 return key; 1732 } 1733 } else if (!miniscript::IsTapscript(m_script_ctx)) { 1734 CPubKey pubkey(begin, end); 1735 if (auto pubkey_provider = InferPubkey(pubkey, ParseContext(), *m_in)) { 1736 m_keys.emplace_back(); 1737 m_keys.back().push_back(std::move(pubkey_provider)); 1738 return key; 1739 } 1740 } 1741 return {}; 1742 } 1743 1744 template<typename I> std::optional<Key> FromPKHBytes(I begin, I end) const 1745 { 1746 assert(end - begin == 20); 1747 assert(m_in); 1748 uint160 hash; 1749 std::copy(begin, end, hash.begin()); 1750 CKeyID keyid(hash); 1751 CPubKey pubkey; 1752 if (m_in->GetPubKey(keyid, pubkey)) { 1753 if (auto pubkey_provider = InferPubkey(pubkey, ParseContext(), *m_in)) { 1754 Key key = m_keys.size(); 1755 m_keys.emplace_back(); 1756 m_keys.back().push_back(std::move(pubkey_provider)); 1757 return key; 1758 } 1759 } 1760 return {}; 1761 } 1762 1763 miniscript::MiniscriptContext MsContext() const { 1764 return m_script_ctx; 1765 } 1766 }; 1767 1768 /** Parse a script in a particular context. */ 1769 // NOLINTNEXTLINE(misc-no-recursion) 1770 std::vector<std::unique_ptr<DescriptorImpl>> ParseScript(uint32_t& key_exp_index, std::span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error) 1771 { 1772 using namespace script; 1773 Assume(ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH || ctx == ParseScriptContext::P2TR); 1774 std::vector<std::unique_ptr<DescriptorImpl>> ret; 1775 auto expr = Expr(sp); 1776 if (Func("pk", expr)) { 1777 auto pubkeys = ParsePubkey(key_exp_index, expr, ctx, out, error); 1778 if (pubkeys.empty()) { 1779 error = strprintf("pk(): %s", error); 1780 return {}; 1781 } 1782 ++key_exp_index; 1783 for (auto& pubkey : pubkeys) { 1784 ret.emplace_back(std::make_unique<PKDescriptor>(std::move(pubkey), ctx == ParseScriptContext::P2TR)); 1785 } 1786 return ret; 1787 } 1788 if ((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH) && Func("pkh", expr)) { 1789 auto pubkeys = ParsePubkey(key_exp_index, expr, ctx, out, error); 1790 if (pubkeys.empty()) { 1791 error = strprintf("pkh(): %s", error); 1792 return {}; 1793 } 1794 ++key_exp_index; 1795 for (auto& pubkey : pubkeys) { 1796 ret.emplace_back(std::make_unique<PKHDescriptor>(std::move(pubkey))); 1797 } 1798 return ret; 1799 } 1800 if (ctx == ParseScriptContext::TOP && Func("combo", expr)) { 1801 auto pubkeys = ParsePubkey(key_exp_index, expr, ctx, out, error); 1802 if (pubkeys.empty()) { 1803 error = strprintf("combo(): %s", error); 1804 return {}; 1805 } 1806 ++key_exp_index; 1807 for (auto& pubkey : pubkeys) { 1808 ret.emplace_back(std::make_unique<ComboDescriptor>(std::move(pubkey))); 1809 } 1810 return ret; 1811 } else if (Func("combo", expr)) { 1812 error = "Can only have combo() at top level"; 1813 return {}; 1814 } 1815 const bool multi = Func("multi", expr); 1816 const bool sortedmulti = !multi && Func("sortedmulti", expr); 1817 const bool multi_a = !(multi || sortedmulti) && Func("multi_a", expr); 1818 const bool sortedmulti_a = !(multi || sortedmulti || multi_a) && Func("sortedmulti_a", expr); 1819 if (((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH) && (multi || sortedmulti)) || 1820 (ctx == ParseScriptContext::P2TR && (multi_a || sortedmulti_a))) { 1821 auto threshold = Expr(expr); 1822 uint32_t thres; 1823 std::vector<std::vector<std::unique_ptr<PubkeyProvider>>> providers; // List of multipath expanded pubkeys 1824 if (const auto maybe_thres{ToIntegral<uint32_t>(std::string_view{threshold.begin(), threshold.end()})}) { 1825 thres = *maybe_thres; 1826 } else { 1827 error = strprintf("Multi threshold '%s' is not valid", std::string(threshold.begin(), threshold.end())); 1828 return {}; 1829 } 1830 size_t script_size = 0; 1831 size_t max_providers_len = 0; 1832 while (expr.size()) { 1833 if (!Const(",", expr)) { 1834 error = strprintf("Multi: expected ',', got '%c'", expr[0]); 1835 return {}; 1836 } 1837 auto arg = Expr(expr); 1838 auto pks = ParsePubkey(key_exp_index, arg, ctx, out, error); 1839 if (pks.empty()) { 1840 error = strprintf("Multi: %s", error); 1841 return {}; 1842 } 1843 script_size += pks.at(0)->GetSize() + 1; 1844 max_providers_len = std::max(max_providers_len, pks.size()); 1845 providers.emplace_back(std::move(pks)); 1846 key_exp_index++; 1847 } 1848 if ((multi || sortedmulti) && (providers.empty() || providers.size() > MAX_PUBKEYS_PER_MULTISIG)) { 1849 error = strprintf("Cannot have %u keys in multisig; must have between 1 and %d keys, inclusive", providers.size(), MAX_PUBKEYS_PER_MULTISIG); 1850 return {}; 1851 } else if ((multi_a || sortedmulti_a) && (providers.empty() || providers.size() > MAX_PUBKEYS_PER_MULTI_A)) { 1852 error = strprintf("Cannot have %u keys in multi_a; must have between 1 and %d keys, inclusive", providers.size(), MAX_PUBKEYS_PER_MULTI_A); 1853 return {}; 1854 } else if (thres < 1) { 1855 error = strprintf("Multisig threshold cannot be %d, must be at least 1", thres); 1856 return {}; 1857 } else if (thres > providers.size()) { 1858 error = strprintf("Multisig threshold cannot be larger than the number of keys; threshold is %d but only %u keys specified", thres, providers.size()); 1859 return {}; 1860 } 1861 if (ctx == ParseScriptContext::TOP) { 1862 if (providers.size() > 3) { 1863 error = strprintf("Cannot have %u pubkeys in bare multisig; only at most 3 pubkeys", providers.size()); 1864 return {}; 1865 } 1866 } 1867 if (ctx == ParseScriptContext::P2SH) { 1868 // This limits the maximum number of compressed pubkeys to 15. 1869 if (script_size + 3 > MAX_SCRIPT_ELEMENT_SIZE) { 1870 error = strprintf("P2SH script is too large, %d bytes is larger than %d bytes", script_size + 3, MAX_SCRIPT_ELEMENT_SIZE); 1871 return {}; 1872 } 1873 } 1874 1875 // Make sure all vecs are of the same length, or exactly length 1 1876 // For length 1 vectors, clone key providers until vector is the same length 1877 for (auto& vec : providers) { 1878 if (vec.size() == 1) { 1879 for (size_t i = 1; i < max_providers_len; ++i) { 1880 vec.emplace_back(vec.at(0)->Clone()); 1881 } 1882 } else if (vec.size() != max_providers_len) { 1883 error = strprintf("multi(): Multipath derivation paths have mismatched lengths"); 1884 return {}; 1885 } 1886 } 1887 1888 // Build the final descriptors vector 1889 for (size_t i = 0; i < max_providers_len; ++i) { 1890 // Build final pubkeys vectors by retrieving the i'th subscript for each vector in subscripts 1891 std::vector<std::unique_ptr<PubkeyProvider>> pubs; 1892 pubs.reserve(providers.size()); 1893 for (auto& pub : providers) { 1894 pubs.emplace_back(std::move(pub.at(i))); 1895 } 1896 if (multi || sortedmulti) { 1897 ret.emplace_back(std::make_unique<MultisigDescriptor>(thres, std::move(pubs), sortedmulti)); 1898 } else { 1899 ret.emplace_back(std::make_unique<MultiADescriptor>(thres, std::move(pubs), sortedmulti_a)); 1900 } 1901 } 1902 return ret; 1903 } else if (multi || sortedmulti) { 1904 error = "Can only have multi/sortedmulti at top level, in sh(), or in wsh()"; 1905 return {}; 1906 } else if (multi_a || sortedmulti_a) { 1907 error = "Can only have multi_a/sortedmulti_a inside tr()"; 1908 return {}; 1909 } 1910 if ((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH) && Func("wpkh", expr)) { 1911 auto pubkeys = ParsePubkey(key_exp_index, expr, ParseScriptContext::P2WPKH, out, error); 1912 if (pubkeys.empty()) { 1913 error = strprintf("wpkh(): %s", error); 1914 return {}; 1915 } 1916 key_exp_index++; 1917 for (auto& pubkey : pubkeys) { 1918 ret.emplace_back(std::make_unique<WPKHDescriptor>(std::move(pubkey))); 1919 } 1920 return ret; 1921 } else if (Func("wpkh", expr)) { 1922 error = "Can only have wpkh() at top level or inside sh()"; 1923 return {}; 1924 } 1925 if (ctx == ParseScriptContext::TOP && Func("sh", expr)) { 1926 auto descs = ParseScript(key_exp_index, expr, ParseScriptContext::P2SH, out, error); 1927 if (descs.empty() || expr.size()) return {}; 1928 std::vector<std::unique_ptr<DescriptorImpl>> ret; 1929 ret.reserve(descs.size()); 1930 for (auto& desc : descs) { 1931 ret.push_back(std::make_unique<SHDescriptor>(std::move(desc))); 1932 } 1933 return ret; 1934 } else if (Func("sh", expr)) { 1935 error = "Can only have sh() at top level"; 1936 return {}; 1937 } 1938 if ((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH) && Func("wsh", expr)) { 1939 auto descs = ParseScript(key_exp_index, expr, ParseScriptContext::P2WSH, out, error); 1940 if (descs.empty() || expr.size()) return {}; 1941 for (auto& desc : descs) { 1942 ret.emplace_back(std::make_unique<WSHDescriptor>(std::move(desc))); 1943 } 1944 return ret; 1945 } else if (Func("wsh", expr)) { 1946 error = "Can only have wsh() at top level or inside sh()"; 1947 return {}; 1948 } 1949 if (ctx == ParseScriptContext::TOP && Func("addr", expr)) { 1950 CTxDestination dest = DecodeDestination(std::string(expr.begin(), expr.end())); 1951 if (!IsValidDestination(dest)) { 1952 error = "Address is not valid"; 1953 return {}; 1954 } 1955 ret.emplace_back(std::make_unique<AddressDescriptor>(std::move(dest))); 1956 return ret; 1957 } else if (Func("addr", expr)) { 1958 error = "Can only have addr() at top level"; 1959 return {}; 1960 } 1961 if (ctx == ParseScriptContext::TOP && Func("tr", expr)) { 1962 auto arg = Expr(expr); 1963 auto internal_keys = ParsePubkey(key_exp_index, arg, ParseScriptContext::P2TR, out, error); 1964 if (internal_keys.empty()) { 1965 error = strprintf("tr(): %s", error); 1966 return {}; 1967 } 1968 size_t max_providers_len = internal_keys.size(); 1969 ++key_exp_index; 1970 std::vector<std::vector<std::unique_ptr<DescriptorImpl>>> subscripts; //!< list of multipath expanded script subexpressions 1971 std::vector<int> depths; //!< depth in the tree of each subexpression (same length subscripts) 1972 if (expr.size()) { 1973 if (!Const(",", expr)) { 1974 error = strprintf("tr: expected ',', got '%c'", expr[0]); 1975 return {}; 1976 } 1977 /** The path from the top of the tree to what we're currently processing. 1978 * branches[i] == false: left branch in the i'th step from the top; true: right branch. 1979 */ 1980 std::vector<bool> branches; 1981 // Loop over all provided scripts. In every iteration exactly one script will be processed. 1982 // Use a do-loop because inside this if-branch we expect at least one script. 1983 do { 1984 // First process all open braces. 1985 while (Const("{", expr)) { 1986 branches.push_back(false); // new left branch 1987 if (branches.size() > TAPROOT_CONTROL_MAX_NODE_COUNT) { 1988 error = strprintf("tr() supports at most %i nesting levels", TAPROOT_CONTROL_MAX_NODE_COUNT); 1989 return {}; 1990 } 1991 } 1992 // Process the actual script expression. 1993 auto sarg = Expr(expr); 1994 subscripts.emplace_back(ParseScript(key_exp_index, sarg, ParseScriptContext::P2TR, out, error)); 1995 if (subscripts.back().empty()) return {}; 1996 max_providers_len = std::max(max_providers_len, subscripts.back().size()); 1997 depths.push_back(branches.size()); 1998 // Process closing braces; one is expected for every right branch we were in. 1999 while (branches.size() && branches.back()) { 2000 if (!Const("}", expr)) { 2001 error = strprintf("tr(): expected '}' after script expression"); 2002 return {}; 2003 } 2004 branches.pop_back(); // move up one level after encountering '}' 2005 } 2006 // If after that, we're at the end of a left branch, expect a comma. 2007 if (branches.size() && !branches.back()) { 2008 if (!Const(",", expr)) { 2009 error = strprintf("tr(): expected ',' after script expression"); 2010 return {}; 2011 } 2012 branches.back() = true; // And now we're in a right branch. 2013 } 2014 } while (branches.size()); 2015 // After we've explored a whole tree, we must be at the end of the expression. 2016 if (expr.size()) { 2017 error = strprintf("tr(): expected ')' after script expression"); 2018 return {}; 2019 } 2020 } 2021 assert(TaprootBuilder::ValidDepths(depths)); 2022 2023 // Make sure all vecs are of the same length, or exactly length 1 2024 // For length 1 vectors, clone subdescs until vector is the same length 2025 for (auto& vec : subscripts) { 2026 if (vec.size() == 1) { 2027 for (size_t i = 1; i < max_providers_len; ++i) { 2028 vec.emplace_back(vec.at(0)->Clone()); 2029 } 2030 } else if (vec.size() != max_providers_len) { 2031 error = strprintf("tr(): Multipath subscripts have mismatched lengths"); 2032 return {}; 2033 } 2034 } 2035 2036 if (internal_keys.size() > 1 && internal_keys.size() != max_providers_len) { 2037 error = strprintf("tr(): Multipath internal key mismatches multipath subscripts lengths"); 2038 return {}; 2039 } 2040 2041 while (internal_keys.size() < max_providers_len) { 2042 internal_keys.emplace_back(internal_keys.at(0)->Clone()); 2043 } 2044 2045 // Build the final descriptors vector 2046 for (size_t i = 0; i < max_providers_len; ++i) { 2047 // Build final subscripts vectors by retrieving the i'th subscript for each vector in subscripts 2048 std::vector<std::unique_ptr<DescriptorImpl>> this_subs; 2049 this_subs.reserve(subscripts.size()); 2050 for (auto& subs : subscripts) { 2051 this_subs.emplace_back(std::move(subs.at(i))); 2052 } 2053 ret.emplace_back(std::make_unique<TRDescriptor>(std::move(internal_keys.at(i)), std::move(this_subs), depths)); 2054 } 2055 return ret; 2056 2057 2058 } else if (Func("tr", expr)) { 2059 error = "Can only have tr at top level"; 2060 return {}; 2061 } 2062 if (ctx == ParseScriptContext::TOP && Func("rawtr", expr)) { 2063 auto arg = Expr(expr); 2064 if (expr.size()) { 2065 error = strprintf("rawtr(): only one key expected."); 2066 return {}; 2067 } 2068 auto output_keys = ParsePubkey(key_exp_index, arg, ParseScriptContext::P2TR, out, error); 2069 if (output_keys.empty()) { 2070 error = strprintf("rawtr(): %s", error); 2071 return {}; 2072 } 2073 ++key_exp_index; 2074 for (auto& pubkey : output_keys) { 2075 ret.emplace_back(std::make_unique<RawTRDescriptor>(std::move(pubkey))); 2076 } 2077 return ret; 2078 } else if (Func("rawtr", expr)) { 2079 error = "Can only have rawtr at top level"; 2080 return {}; 2081 } 2082 if (ctx == ParseScriptContext::TOP && Func("raw", expr)) { 2083 std::string str(expr.begin(), expr.end()); 2084 if (!IsHex(str)) { 2085 error = "Raw script is not hex"; 2086 return {}; 2087 } 2088 auto bytes = ParseHex(str); 2089 ret.emplace_back(std::make_unique<RawDescriptor>(CScript(bytes.begin(), bytes.end()))); 2090 return ret; 2091 } else if (Func("raw", expr)) { 2092 error = "Can only have raw() at top level"; 2093 return {}; 2094 } 2095 // Process miniscript expressions. 2096 { 2097 const auto script_ctx{ctx == ParseScriptContext::P2WSH ? miniscript::MiniscriptContext::P2WSH : miniscript::MiniscriptContext::TAPSCRIPT}; 2098 KeyParser parser(/*out = */&out, /* in = */nullptr, /* ctx = */script_ctx, key_exp_index); 2099 auto node = miniscript::FromString(std::string(expr.begin(), expr.end()), parser); 2100 if (parser.m_key_parsing_error != "") { 2101 error = std::move(parser.m_key_parsing_error); 2102 return {}; 2103 } 2104 if (node) { 2105 if (ctx != ParseScriptContext::P2WSH && ctx != ParseScriptContext::P2TR) { 2106 error = "Miniscript expressions can only be used in wsh or tr."; 2107 return {}; 2108 } 2109 if (!node->IsSane() || node->IsNotSatisfiable()) { 2110 // Try to find the first insane sub for better error reporting. 2111 auto insane_node = node.get(); 2112 if (const auto sub = node->FindInsaneSub()) insane_node = sub; 2113 if (const auto str = insane_node->ToString(parser)) error = *str; 2114 if (!insane_node->IsValid()) { 2115 error += " is invalid"; 2116 } else if (!node->IsSane()) { 2117 error += " is not sane"; 2118 if (!insane_node->IsNonMalleable()) { 2119 error += ": malleable witnesses exist"; 2120 } else if (insane_node == node.get() && !insane_node->NeedsSignature()) { 2121 error += ": witnesses without signature exist"; 2122 } else if (!insane_node->CheckTimeLocksMix()) { 2123 error += ": contains mixes of timelocks expressed in blocks and seconds"; 2124 } else if (!insane_node->CheckDuplicateKey()) { 2125 error += ": contains duplicate public keys"; 2126 } else if (!insane_node->ValidSatisfactions()) { 2127 error += ": needs witnesses that may exceed resource limits"; 2128 } 2129 } else { 2130 error += " is not satisfiable"; 2131 } 2132 return {}; 2133 } 2134 // A signature check is required for a miniscript to be sane. Therefore no sane miniscript 2135 // may have an empty list of public keys. 2136 CHECK_NONFATAL(!parser.m_keys.empty()); 2137 key_exp_index += parser.m_keys.size(); 2138 // Make sure all vecs are of the same length, or exactly length 1 2139 // For length 1 vectors, clone subdescs until vector is the same length 2140 size_t num_multipath = std::max_element(parser.m_keys.begin(), parser.m_keys.end(), 2141 [](const std::vector<std::unique_ptr<PubkeyProvider>>& a, const std::vector<std::unique_ptr<PubkeyProvider>>& b) { 2142 return a.size() < b.size(); 2143 })->size(); 2144 2145 for (auto& vec : parser.m_keys) { 2146 if (vec.size() == 1) { 2147 for (size_t i = 1; i < num_multipath; ++i) { 2148 vec.emplace_back(vec.at(0)->Clone()); 2149 } 2150 } else if (vec.size() != num_multipath) { 2151 error = strprintf("Miniscript: Multipath derivation paths have mismatched lengths"); 2152 return {}; 2153 } 2154 } 2155 2156 // Build the final descriptors vector 2157 for (size_t i = 0; i < num_multipath; ++i) { 2158 // Build final pubkeys vectors by retrieving the i'th subscript for each vector in subscripts 2159 std::vector<std::unique_ptr<PubkeyProvider>> pubs; 2160 pubs.reserve(parser.m_keys.size()); 2161 for (auto& pub : parser.m_keys) { 2162 pubs.emplace_back(std::move(pub.at(i))); 2163 } 2164 ret.emplace_back(std::make_unique<MiniscriptDescriptor>(std::move(pubs), node->Clone())); 2165 } 2166 return ret; 2167 } 2168 } 2169 if (ctx == ParseScriptContext::P2SH) { 2170 error = "A function is needed within P2SH"; 2171 return {}; 2172 } else if (ctx == ParseScriptContext::P2WSH) { 2173 error = "A function is needed within P2WSH"; 2174 return {}; 2175 } 2176 error = strprintf("'%s' is not a valid descriptor function", std::string(expr.begin(), expr.end())); 2177 return {}; 2178 } 2179 2180 std::unique_ptr<DescriptorImpl> InferMultiA(const CScript& script, ParseScriptContext ctx, const SigningProvider& provider) 2181 { 2182 auto match = MatchMultiA(script); 2183 if (!match) return {}; 2184 std::vector<std::unique_ptr<PubkeyProvider>> keys; 2185 keys.reserve(match->second.size()); 2186 for (const auto keyspan : match->second) { 2187 if (keyspan.size() != 32) return {}; 2188 auto key = InferXOnlyPubkey(XOnlyPubKey{keyspan}, ctx, provider); 2189 if (!key) return {}; 2190 keys.push_back(std::move(key)); 2191 } 2192 return std::make_unique<MultiADescriptor>(match->first, std::move(keys)); 2193 } 2194 2195 // NOLINTNEXTLINE(misc-no-recursion) 2196 std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptContext ctx, const SigningProvider& provider) 2197 { 2198 if (ctx == ParseScriptContext::P2TR && script.size() == 34 && script[0] == 32 && script[33] == OP_CHECKSIG) { 2199 XOnlyPubKey key{std::span{script}.subspan(1, 32)}; 2200 return std::make_unique<PKDescriptor>(InferXOnlyPubkey(key, ctx, provider), true); 2201 } 2202 2203 if (ctx == ParseScriptContext::P2TR) { 2204 auto ret = InferMultiA(script, ctx, provider); 2205 if (ret) return ret; 2206 } 2207 2208 std::vector<std::vector<unsigned char>> data; 2209 TxoutType txntype = Solver(script, data); 2210 2211 if (txntype == TxoutType::PUBKEY && (ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH)) { 2212 CPubKey pubkey(data[0]); 2213 if (auto pubkey_provider = InferPubkey(pubkey, ctx, provider)) { 2214 return std::make_unique<PKDescriptor>(std::move(pubkey_provider)); 2215 } 2216 } 2217 if (txntype == TxoutType::PUBKEYHASH && (ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH)) { 2218 uint160 hash(data[0]); 2219 CKeyID keyid(hash); 2220 CPubKey pubkey; 2221 if (provider.GetPubKey(keyid, pubkey)) { 2222 if (auto pubkey_provider = InferPubkey(pubkey, ctx, provider)) { 2223 return std::make_unique<PKHDescriptor>(std::move(pubkey_provider)); 2224 } 2225 } 2226 } 2227 if (txntype == TxoutType::WITNESS_V0_KEYHASH && (ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH)) { 2228 uint160 hash(data[0]); 2229 CKeyID keyid(hash); 2230 CPubKey pubkey; 2231 if (provider.GetPubKey(keyid, pubkey)) { 2232 if (auto pubkey_provider = InferPubkey(pubkey, ParseScriptContext::P2WPKH, provider)) { 2233 return std::make_unique<WPKHDescriptor>(std::move(pubkey_provider)); 2234 } 2235 } 2236 } 2237 if (txntype == TxoutType::MULTISIG && (ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH)) { 2238 bool ok = true; 2239 std::vector<std::unique_ptr<PubkeyProvider>> providers; 2240 for (size_t i = 1; i + 1 < data.size(); ++i) { 2241 CPubKey pubkey(data[i]); 2242 if (auto pubkey_provider = InferPubkey(pubkey, ctx, provider)) { 2243 providers.push_back(std::move(pubkey_provider)); 2244 } else { 2245 ok = false; 2246 break; 2247 } 2248 } 2249 if (ok) return std::make_unique<MultisigDescriptor>((int)data[0][0], std::move(providers)); 2250 } 2251 if (txntype == TxoutType::SCRIPTHASH && ctx == ParseScriptContext::TOP) { 2252 uint160 hash(data[0]); 2253 CScriptID scriptid(hash); 2254 CScript subscript; 2255 if (provider.GetCScript(scriptid, subscript)) { 2256 auto sub = InferScript(subscript, ParseScriptContext::P2SH, provider); 2257 if (sub) return std::make_unique<SHDescriptor>(std::move(sub)); 2258 } 2259 } 2260 if (txntype == TxoutType::WITNESS_V0_SCRIPTHASH && (ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH)) { 2261 CScriptID scriptid{RIPEMD160(data[0])}; 2262 CScript subscript; 2263 if (provider.GetCScript(scriptid, subscript)) { 2264 auto sub = InferScript(subscript, ParseScriptContext::P2WSH, provider); 2265 if (sub) return std::make_unique<WSHDescriptor>(std::move(sub)); 2266 } 2267 } 2268 if (txntype == TxoutType::WITNESS_V1_TAPROOT && ctx == ParseScriptContext::TOP) { 2269 // Extract x-only pubkey from output. 2270 XOnlyPubKey pubkey; 2271 std::copy(data[0].begin(), data[0].end(), pubkey.begin()); 2272 // Request spending data. 2273 TaprootSpendData tap; 2274 if (provider.GetTaprootSpendData(pubkey, tap)) { 2275 // If found, convert it back to tree form. 2276 auto tree = InferTaprootTree(tap, pubkey); 2277 if (tree) { 2278 // If that works, try to infer subdescriptors for all leaves. 2279 bool ok = true; 2280 std::vector<std::unique_ptr<DescriptorImpl>> subscripts; //!< list of script subexpressions 2281 std::vector<int> depths; //!< depth in the tree of each subexpression (same length subscripts) 2282 for (const auto& [depth, script, leaf_ver] : *tree) { 2283 std::unique_ptr<DescriptorImpl> subdesc; 2284 if (leaf_ver == TAPROOT_LEAF_TAPSCRIPT) { 2285 subdesc = InferScript(CScript(script.begin(), script.end()), ParseScriptContext::P2TR, provider); 2286 } 2287 if (!subdesc) { 2288 ok = false; 2289 break; 2290 } else { 2291 subscripts.push_back(std::move(subdesc)); 2292 depths.push_back(depth); 2293 } 2294 } 2295 if (ok) { 2296 auto key = InferXOnlyPubkey(tap.internal_key, ParseScriptContext::P2TR, provider); 2297 return std::make_unique<TRDescriptor>(std::move(key), std::move(subscripts), std::move(depths)); 2298 } 2299 } 2300 } 2301 // If the above doesn't work, construct a rawtr() descriptor with just the encoded x-only pubkey. 2302 if (pubkey.IsFullyValid()) { 2303 auto key = InferXOnlyPubkey(pubkey, ParseScriptContext::P2TR, provider); 2304 if (key) { 2305 return std::make_unique<RawTRDescriptor>(std::move(key)); 2306 } 2307 } 2308 } 2309 2310 if (ctx == ParseScriptContext::P2WSH || ctx == ParseScriptContext::P2TR) { 2311 const auto script_ctx{ctx == ParseScriptContext::P2WSH ? miniscript::MiniscriptContext::P2WSH : miniscript::MiniscriptContext::TAPSCRIPT}; 2312 KeyParser parser(/* out = */nullptr, /* in = */&provider, /* ctx = */script_ctx); 2313 auto node = miniscript::FromScript(script, parser); 2314 if (node && node->IsSane()) { 2315 std::vector<std::unique_ptr<PubkeyProvider>> keys; 2316 keys.reserve(parser.m_keys.size()); 2317 for (auto& key : parser.m_keys) { 2318 keys.emplace_back(std::move(key.at(0))); 2319 } 2320 return std::make_unique<MiniscriptDescriptor>(std::move(keys), std::move(node)); 2321 } 2322 } 2323 2324 // The following descriptors are all top-level only descriptors. 2325 // So if we are not at the top level, return early. 2326 if (ctx != ParseScriptContext::TOP) return nullptr; 2327 2328 CTxDestination dest; 2329 if (ExtractDestination(script, dest)) { 2330 if (GetScriptForDestination(dest) == script) { 2331 return std::make_unique<AddressDescriptor>(std::move(dest)); 2332 } 2333 } 2334 2335 return std::make_unique<RawDescriptor>(script); 2336 } 2337 2338 2339 } // namespace 2340 2341 /** Check a descriptor checksum, and update desc to be the checksum-less part. */ 2342 bool CheckChecksum(std::span<const char>& sp, bool require_checksum, std::string& error, std::string* out_checksum = nullptr) 2343 { 2344 auto check_split = Split(sp, '#'); 2345 if (check_split.size() > 2) { 2346 error = "Multiple '#' symbols"; 2347 return false; 2348 } 2349 if (check_split.size() == 1 && require_checksum){ 2350 error = "Missing checksum"; 2351 return false; 2352 } 2353 if (check_split.size() == 2) { 2354 if (check_split[1].size() != 8) { 2355 error = strprintf("Expected 8 character checksum, not %u characters", check_split[1].size()); 2356 return false; 2357 } 2358 } 2359 auto checksum = DescriptorChecksum(check_split[0]); 2360 if (checksum.empty()) { 2361 error = "Invalid characters in payload"; 2362 return false; 2363 } 2364 if (check_split.size() == 2) { 2365 if (!std::equal(checksum.begin(), checksum.end(), check_split[1].begin())) { 2366 error = strprintf("Provided checksum '%s' does not match computed checksum '%s'", std::string(check_split[1].begin(), check_split[1].end()), checksum); 2367 return false; 2368 } 2369 } 2370 if (out_checksum) *out_checksum = std::move(checksum); 2371 sp = check_split[0]; 2372 return true; 2373 } 2374 2375 std::vector<std::unique_ptr<Descriptor>> Parse(const std::string& descriptor, FlatSigningProvider& out, std::string& error, bool require_checksum) 2376 { 2377 std::span<const char> sp{descriptor}; 2378 if (!CheckChecksum(sp, require_checksum, error)) return {}; 2379 uint32_t key_exp_index = 0; 2380 auto ret = ParseScript(key_exp_index, sp, ParseScriptContext::TOP, out, error); 2381 if (sp.size() == 0 && !ret.empty()) { 2382 std::vector<std::unique_ptr<Descriptor>> descs; 2383 descs.reserve(ret.size()); 2384 for (auto& r : ret) { 2385 descs.emplace_back(std::unique_ptr<Descriptor>(std::move(r))); 2386 } 2387 return descs; 2388 } 2389 return {}; 2390 } 2391 2392 std::string GetDescriptorChecksum(const std::string& descriptor) 2393 { 2394 std::string ret; 2395 std::string error; 2396 std::span<const char> sp{descriptor}; 2397 if (!CheckChecksum(sp, false, error, &ret)) return ""; 2398 return ret; 2399 } 2400 2401 std::unique_ptr<Descriptor> InferDescriptor(const CScript& script, const SigningProvider& provider) 2402 { 2403 return InferScript(script, ParseScriptContext::TOP, provider); 2404 } 2405 2406 uint256 DescriptorID(const Descriptor& desc) 2407 { 2408 std::string desc_str = desc.ToString(/*compat_format=*/true); 2409 uint256 id; 2410 CSHA256().Write((unsigned char*)desc_str.data(), desc_str.size()).Finalize(id.begin()); 2411 return id; 2412 } 2413 2414 void DescriptorCache::CacheParentExtPubKey(uint32_t key_exp_pos, const CExtPubKey& xpub) 2415 { 2416 m_parent_xpubs[key_exp_pos] = xpub; 2417 } 2418 2419 void DescriptorCache::CacheDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index, const CExtPubKey& xpub) 2420 { 2421 auto& xpubs = m_derived_xpubs[key_exp_pos]; 2422 xpubs[der_index] = xpub; 2423 } 2424 2425 void DescriptorCache::CacheLastHardenedExtPubKey(uint32_t key_exp_pos, const CExtPubKey& xpub) 2426 { 2427 m_last_hardened_xpubs[key_exp_pos] = xpub; 2428 } 2429 2430 bool DescriptorCache::GetCachedParentExtPubKey(uint32_t key_exp_pos, CExtPubKey& xpub) const 2431 { 2432 const auto& it = m_parent_xpubs.find(key_exp_pos); 2433 if (it == m_parent_xpubs.end()) return false; 2434 xpub = it->second; 2435 return true; 2436 } 2437 2438 bool DescriptorCache::GetCachedDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index, CExtPubKey& xpub) const 2439 { 2440 const auto& key_exp_it = m_derived_xpubs.find(key_exp_pos); 2441 if (key_exp_it == m_derived_xpubs.end()) return false; 2442 const auto& der_it = key_exp_it->second.find(der_index); 2443 if (der_it == key_exp_it->second.end()) return false; 2444 xpub = der_it->second; 2445 return true; 2446 } 2447 2448 bool DescriptorCache::GetCachedLastHardenedExtPubKey(uint32_t key_exp_pos, CExtPubKey& xpub) const 2449 { 2450 const auto& it = m_last_hardened_xpubs.find(key_exp_pos); 2451 if (it == m_last_hardened_xpubs.end()) return false; 2452 xpub = it->second; 2453 return true; 2454 } 2455 2456 DescriptorCache DescriptorCache::MergeAndDiff(const DescriptorCache& other) 2457 { 2458 DescriptorCache diff; 2459 for (const auto& parent_xpub_pair : other.GetCachedParentExtPubKeys()) { 2460 CExtPubKey xpub; 2461 if (GetCachedParentExtPubKey(parent_xpub_pair.first, xpub)) { 2462 if (xpub != parent_xpub_pair.second) { 2463 throw std::runtime_error(std::string(__func__) + ": New cached parent xpub does not match already cached parent xpub"); 2464 } 2465 continue; 2466 } 2467 CacheParentExtPubKey(parent_xpub_pair.first, parent_xpub_pair.second); 2468 diff.CacheParentExtPubKey(parent_xpub_pair.first, parent_xpub_pair.second); 2469 } 2470 for (const auto& derived_xpub_map_pair : other.GetCachedDerivedExtPubKeys()) { 2471 for (const auto& derived_xpub_pair : derived_xpub_map_pair.second) { 2472 CExtPubKey xpub; 2473 if (GetCachedDerivedExtPubKey(derived_xpub_map_pair.first, derived_xpub_pair.first, xpub)) { 2474 if (xpub != derived_xpub_pair.second) { 2475 throw std::runtime_error(std::string(__func__) + ": New cached derived xpub does not match already cached derived xpub"); 2476 } 2477 continue; 2478 } 2479 CacheDerivedExtPubKey(derived_xpub_map_pair.first, derived_xpub_pair.first, derived_xpub_pair.second); 2480 diff.CacheDerivedExtPubKey(derived_xpub_map_pair.first, derived_xpub_pair.first, derived_xpub_pair.second); 2481 } 2482 } 2483 for (const auto& lh_xpub_pair : other.GetCachedLastHardenedExtPubKeys()) { 2484 CExtPubKey xpub; 2485 if (GetCachedLastHardenedExtPubKey(lh_xpub_pair.first, xpub)) { 2486 if (xpub != lh_xpub_pair.second) { 2487 throw std::runtime_error(std::string(__func__) + ": New cached last hardened xpub does not match already cached last hardened xpub"); 2488 } 2489 continue; 2490 } 2491 CacheLastHardenedExtPubKey(lh_xpub_pair.first, lh_xpub_pair.second); 2492 diff.CacheLastHardenedExtPubKey(lh_xpub_pair.first, lh_xpub_pair.second); 2493 } 2494 return diff; 2495 } 2496 2497 ExtPubKeyMap DescriptorCache::GetCachedParentExtPubKeys() const 2498 { 2499 return m_parent_xpubs; 2500 } 2501 2502 std::unordered_map<uint32_t, ExtPubKeyMap> DescriptorCache::GetCachedDerivedExtPubKeys() const 2503 { 2504 return m_derived_xpubs; 2505 } 2506 2507 ExtPubKeyMap DescriptorCache::GetCachedLastHardenedExtPubKeys() const 2508 { 2509 return m_last_hardened_xpubs; 2510 }