LCOV - code coverage report
Current view: top level - src/script - descriptor.cpp (source / functions) Coverage Total Hit
Test: fuzz_coverage.info Lines: 94.1 % 1433 1349
Test Date: 2025-06-01 05:27:21 Functions: 87.3 % 204 178
Branches: 65.4 % 2378 1556

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

Generated by: LCOV version 2.0-1