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