LCOV - code coverage report
Current view: top level - src/script - descriptor.cpp (source / functions) Hit Total Coverage
Test: fuzz_coverage.info Lines: 1136 1323 85.9 %
Date: 2024-01-03 14:57:27 Functions: 202 230 87.8 %
Branches: 1275 2173 58.7 %

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

Generated by: LCOV version 1.14