diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp
index cb3b197e6..367263e57 100644
--- a/src/script/descriptor.cpp
+++ b/src/script/descriptor.cpp
@@ -1,1255 +1,1276 @@
 // Copyright (c) 2018 The Bitcoin Core developers
 // Distributed under the MIT software license, see the accompanying
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
 #include <script/descriptor.h>
 
 #include <chainparams.h> // For Params()
 #include <config.h>
 #include <key_io.h>
 #include <pubkey.h>
 #include <script/standard.h>
 #include <span.h>
 #include <util/bip32.h>
 #include <util/spanparsing.h>
 #include <util/strencodings.h>
 #include <util/system.h>
 #include <util/vector.h>
 
 #include <memory>
 #include <string>
 
 namespace {
 
 ////////////////////////////////////////////////////////////////////////////
 // Checksum                                                               //
 ////////////////////////////////////////////////////////////////////////////
 
 // This section implements a checksum algorithm for descriptors with the
 // following properties:
 // * Mistakes in a descriptor string are measured in "symbol errors". The higher
 //   the number of symbol errors, the harder it is to detect:
 //   * An error substituting a character from 0123456789()[],'/*abcdefgh@:$%{}
 //   for
 //     another in that set always counts as 1 symbol error.
 //     * Note that hex encoded keys are covered by these characters. Xprvs and
 //       xpubs use other characters too, but already have their own checksum
 //       mechanism.
 //     * Function names like "multi()" use other characters, but mistakes in
 //       these would generally result in an unparsable descriptor.
 //   * A case error always counts as 1 symbol error.
 //   * Any other 1 character substitution error counts as 1 or 2 symbol errors.
 // * Any 1 symbol error is always detected.
 // * Any 2 or 3 symbol error in a descriptor of up to 49154 characters is always
 // detected.
 // * Any 4 symbol error in a descriptor of up to 507 characters is always
 // detected.
 // * Any 5 symbol error in a descriptor of up to 77 characters is always
 // detected.
 // * Is optimized to minimize the chance a 5 symbol error in a descriptor up to
 // 387 characters is undetected
 // * Random errors have a chance of 1 in 2**40 of being undetected.
 //
 // These properties are achieved by expanding every group of 3 (non checksum)
 // characters into 4 GF(32) symbols, over which a cyclic code is defined.
 
 /*
  * Interprets c as 8 groups of 5 bits which are the coefficients of a degree 8
  * polynomial over GF(32), multiplies that polynomial by x, computes its
  * remainder modulo a generator, and adds the constant term val.
  *
  * 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}. It is chosen to define an cyclic error
  * detecting code which is selected by:
  * - Starting from all BCH codes over GF(32) of degree 8 and below, which by
  * construction guarantee detecting 3 errors in windows up to 19000 symbols.
  * - Taking all those generators, and for degree 7 ones, extend them to degree 8
  * by adding all degree-1 factors.
  * - Selecting just the set of generators that guarantee detecting 4 errors in a
  * window of length 512.
  * - Selecting one of those with best worst-case behavior for 5 errors in
  * windows of length up to 512.
  *
  * The generator and the constants to implement it can be verified using this
  * Sage code: B = GF(2) # Binary field BP.<b> = B[] # Polynomials over the
  * binary field F_mod = b**5 + b**3 + 1 F.<f> = GF(32, modulus=F_mod,
  * repr='int') # GF(32) definition FP.<x> = F[] # Polynomials over GF(32) E_mod
  * = x**3 + x + F.fetch_int(8) E.<e> = F.extension(E_mod) # Extension field
  * definition alpha = e**2743 # Choice of an element in extension field for p in
  * divisors(E.order() - 1): # Verify alpha has order 32767. assert((alpha**p ==
  * 1) == (p % 32767 == 0)) G = lcm([(alpha**i).minpoly() for i in
  * [1056,1057,1058]] + [x + 1]) print(G) # Print out the generator for i in
  * [1,2,4,8,16]: # Print out {1,2,4,8,16}*(G mod x^8), packed in hex integers.
  *       v = 0
  *       for coef in reversed((F.fetch_int(i)*(G %
  * x**8)).coefficients(sparse=True)): v = v*32 + coef.integer_representation()
  *       print("0x%x" % v)
  */
 uint64_t PolyMod(uint64_t c, int val) {
     uint8_t c0 = c >> 35;
     c = ((c & 0x7ffffffff) << 5) ^ val;
     if (c0 & 1) {
         c ^= 0xf5dee51989;
     }
     if (c0 & 2) {
         c ^= 0xa9fdca3312;
     }
     if (c0 & 4) {
         c ^= 0x1bab10e32d;
     }
     if (c0 & 8) {
         c ^= 0x3706b1677a;
     }
     if (c0 & 16) {
         c ^= 0x644d626ffd;
     }
     return c;
 }
 
 std::string DescriptorChecksum(const Span<const char> &span) {
     /** A character set designed such that:
      *  - The most common 'unprotected' descriptor characters (hex, keypaths)
      * are in the first group of 32.
      *  - Case errors cause an offset that's a multiple of 32.
      *  - As many alphabetic characters are in the same group (while following
      * the above restrictions).
      *
      * If p(x) gives the position of a character c in this character set, every
      * group of 3 characters (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).
      * This means that changes that only affect the lower 5 bits of the
      * position, or only the higher 2 bits, will just affect a single symbol.
      *
      * As a result, within-group-of-32 errors count as 1 symbol, as do
      * cross-group errors that don't affect the position within the groups.
      */
     static std::string INPUT_CHARSET = "0123456789()[],'/*abcdefgh@:$%{}"
                                        "IJKLMNOPQRSTUVWXYZ&+-.;<=>?!^_|~"
                                        "ijklmnopqrstuvwxyzABCDEFGH`#\"\\ ";
 
     /** The character set for the checksum itself (same as bech32). */
     static std::string CHECKSUM_CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l";
 
     uint64_t c = 1;
     int cls = 0;
     int clscount = 0;
     for (auto ch : span) {
         auto pos = INPUT_CHARSET.find(ch);
         if (pos == std::string::npos) {
             return "";
         }
         // Emit a symbol for the position inside the group, for every character.
         c = PolyMod(c, pos & 31);
         // Accumulate the group numbers
         cls = cls * 3 + (pos >> 5);
         if (++clscount == 3) {
             // Emit an extra symbol representing the group numbers, for every 3
             // characters.
             c = PolyMod(c, cls);
             cls = 0;
             clscount = 0;
         }
     }
     if (clscount > 0) {
         c = PolyMod(c, cls);
     }
     for (int j = 0; j < 8; ++j) {
         // Shift further to determine the checksum.
         c = PolyMod(c, 0);
     }
     // Prevent appending zeroes from not affecting the checksum.
     c ^= 1;
 
     std::string ret(8, ' ');
     for (int j = 0; j < 8; ++j) {
         ret[j] = CHECKSUM_CHARSET[(c >> (5 * (7 - j))) & 31];
     }
     return ret;
 }
 
 std::string AddChecksum(const std::string &str) {
     return str + "#" + DescriptorChecksum(MakeSpan(str));
 }
 
 ////////////////////////////////////////////////////////////////////////////
 // Internal representation                                                //
 ////////////////////////////////////////////////////////////////////////////
 
 typedef std::vector<uint32_t> KeyPath;
 
 /** Interface for public key objects in descriptors. */
 struct PubkeyProvider {
 protected:
     //! Index of this key expression in the descriptor
     //! E.g. If this PubkeyProvider is key1 in multi(2, key1, key2, key3), then
     //! m_expr_index = 0
     uint32_t m_expr_index;
 
 public:
     PubkeyProvider(uint32_t exp_index) : m_expr_index(exp_index) {}
 
     virtual ~PubkeyProvider() = default;
 
-    /** Derive a public key. If key==nullptr, only info is desired. */
-    virtual bool GetPubKey(int pos, const SigningProvider &arg, CPubKey *key,
-                           KeyOriginInfo &info) const = 0;
+    /**
+     * Derive a public key.
+     * read_cache is the cache to read keys from (if not nullptr)
+     * write_cache is the cache to write keys to (if not nullptr)
+     * Caches are not exclusive but this is not tested. Currently we use them
+     * exclusively
+     */
+    virtual bool GetPubKey(int pos, const SigningProvider &arg, CPubKey &key,
+                           KeyOriginInfo &info,
+                           const DescriptorCache *read_cache = nullptr,
+                           DescriptorCache *write_cache = nullptr) const = 0;
 
     /** Whether this represent multiple public keys at different positions. */
     virtual bool IsRange() const = 0;
 
     /** Get the size of the generated public key(s) in bytes (33 or 65). */
     virtual size_t GetSize() const = 0;
 
     /** Get the descriptor string form. */
     virtual std::string ToString() const = 0;
 
     /**
      * Get the descriptor string form including private data (if available in
      * arg).
      */
     virtual bool ToPrivateString(const SigningProvider &arg,
                                  std::string &out) const = 0;
 
     /** Derive a private key, if private data is available in arg. */
     virtual bool GetPrivKey(int pos, const SigningProvider &arg,
                             CKey &key) const = 0;
 };
 
 class OriginPubkeyProvider final : public PubkeyProvider {
     KeyOriginInfo m_origin;
     std::unique_ptr<PubkeyProvider> m_provider;
 
     std::string OriginString() const {
         return HexStr(std::begin(m_origin.fingerprint),
                       std::end(m_origin.fingerprint)) +
                FormatHDKeypath(m_origin.path);
     }
 
 public:
     OriginPubkeyProvider(uint32_t exp_index, KeyOriginInfo info,
                          std::unique_ptr<PubkeyProvider> provider)
         : PubkeyProvider(exp_index), m_origin(std::move(info)),
           m_provider(std::move(provider)) {}
-    bool GetPubKey(int pos, const SigningProvider &arg, CPubKey *key,
-                   KeyOriginInfo &info) const override {
-        if (!m_provider->GetPubKey(pos, arg, key, info)) {
+    bool GetPubKey(int pos, const SigningProvider &arg, CPubKey &key,
+                   KeyOriginInfo &info,
+                   const DescriptorCache *read_cache = nullptr,
+                   DescriptorCache *write_cache = nullptr) const override {
+        if (!m_provider->GetPubKey(pos, arg, key, info, read_cache,
+                                   write_cache)) {
             return false;
         }
         std::copy(std::begin(m_origin.fingerprint),
                   std::end(m_origin.fingerprint), info.fingerprint);
         info.path.insert(info.path.begin(), m_origin.path.begin(),
                          m_origin.path.end());
         return true;
     }
     bool IsRange() const override { return m_provider->IsRange(); }
     size_t GetSize() const override { return m_provider->GetSize(); }
     std::string ToString() const override {
         return "[" + OriginString() + "]" + m_provider->ToString();
     }
     bool ToPrivateString(const SigningProvider &arg,
                          std::string &ret) const override {
         std::string sub;
         if (!m_provider->ToPrivateString(arg, sub)) {
             return false;
         }
         ret = "[" + OriginString() + "]" + std::move(sub);
         return true;
     }
     bool GetPrivKey(int pos, const SigningProvider &arg,
                     CKey &key) const override {
         return m_provider->GetPrivKey(pos, arg, key);
     }
 };
 
 /** An object representing a parsed constant public key in a descriptor. */
 class ConstPubkeyProvider final : public PubkeyProvider {
     CPubKey m_pubkey;
 
 public:
     ConstPubkeyProvider(uint32_t exp_index, const CPubKey &pubkey)
         : PubkeyProvider(exp_index), m_pubkey(pubkey) {}
-    bool GetPubKey(int pos, const SigningProvider &arg, CPubKey *key,
-                   KeyOriginInfo &info) const override {
-        if (key) {
-            *key = m_pubkey;
-        }
+    bool GetPubKey(int pos, const SigningProvider &arg, CPubKey &key,
+                   KeyOriginInfo &info,
+                   const DescriptorCache *read_cache = nullptr,
+                   DescriptorCache *write_cache = nullptr) const override {
+        key = m_pubkey;
         info.path.clear();
         CKeyID keyid = m_pubkey.GetID();
         std::copy(keyid.begin(), keyid.begin() + sizeof(info.fingerprint),
                   info.fingerprint);
         return true;
     }
     bool IsRange() const override { return false; }
     size_t GetSize() const override { return m_pubkey.size(); }
     std::string ToString() const override {
         return HexStr(m_pubkey.begin(), m_pubkey.end());
     }
     bool ToPrivateString(const SigningProvider &arg,
                          std::string &ret) const override {
         CKey key;
         if (!arg.GetKey(m_pubkey.GetID(), key)) {
             return false;
         }
         ret = EncodeSecret(key);
         return true;
     }
     bool GetPrivKey(int pos, const SigningProvider &arg,
                     CKey &key) const override {
         return arg.GetKey(m_pubkey.GetID(), key);
     }
 };
 
 enum class DeriveType {
     NO,
     UNHARDENED,
     HARDENED,
 };
 
 /** An object representing a parsed extended public key in a descriptor. */
 class BIP32PubkeyProvider final : public PubkeyProvider {
     // Root xpub, path, and final derivation step type being used, if any
     CExtPubKey m_root_extkey;
     KeyPath m_path;
     DeriveType m_derive;
 
     bool GetExtKey(const SigningProvider &arg, CExtKey &ret) const {
         CKey key;
         if (!arg.GetKey(m_root_extkey.pubkey.GetID(), key)) {
             return false;
         }
         ret.nDepth = m_root_extkey.nDepth;
         std::copy(m_root_extkey.vchFingerprint,
                   m_root_extkey.vchFingerprint + sizeof(ret.vchFingerprint),
                   ret.vchFingerprint);
         ret.nChild = m_root_extkey.nChild;
         ret.chaincode = m_root_extkey.chaincode;
         ret.key = key;
         return true;
     }
 
+    // Derives the last xprv
+    bool GetDerivedExtKey(const SigningProvider &arg, CExtKey &xprv) const {
+        if (!GetExtKey(arg, xprv)) {
+            return false;
+        }
+        for (auto entry : m_path) {
+            xprv.Derive(xprv, entry);
+        }
+        return true;
+    }
+
     bool IsHardened() const {
         if (m_derive == DeriveType::HARDENED) {
             return true;
         }
         for (auto entry : m_path) {
             if (entry >> 31) {
                 return true;
             }
         }
         return false;
     }
 
 public:
     BIP32PubkeyProvider(uint32_t exp_index, const CExtPubKey &extkey,
                         KeyPath path, DeriveType derive)
         : PubkeyProvider(exp_index), m_root_extkey(extkey),
           m_path(std::move(path)), m_derive(derive) {}
     bool IsRange() const override { return m_derive != DeriveType::NO; }
     size_t GetSize() const override { return 33; }
-    bool GetPubKey(int pos, const SigningProvider &arg, CPubKey *key,
-                   KeyOriginInfo &info) const override {
-        if (key) {
-            if (IsHardened()) {
-                CKey priv_key;
-                if (!GetPrivKey(pos, arg, priv_key)) {
-                    return false;
-                }
-                *key = priv_key.GetPubKey();
-            } else {
-                // TODO: optimize by caching
-                CExtPubKey extkey = m_root_extkey;
-                for (auto entry : m_path) {
-                    extkey.Derive(extkey, entry);
-                }
-                if (m_derive == DeriveType::UNHARDENED) {
-                    extkey.Derive(extkey, pos);
-                }
-                assert(m_derive != DeriveType::HARDENED);
-                *key = extkey.pubkey;
-            }
-        }
+    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 {
+        // Info of parent of the to be derived pubkey
+        KeyOriginInfo parent_info;
         CKeyID keyid = m_root_extkey.pubkey.GetID();
-        std::copy(keyid.begin(), keyid.begin() + sizeof(info.fingerprint),
-                  info.fingerprint);
-        info.path = m_path;
+        std::copy(keyid.begin(),
+                  keyid.begin() + sizeof(parent_info.fingerprint),
+                  parent_info.fingerprint);
+        parent_info.path = m_path;
+
+        // Info of the derived key itself which is copied out upon successful
+        // completion
+        KeyOriginInfo final_info_out_tmp = parent_info;
         if (m_derive == DeriveType::UNHARDENED) {
-            info.path.push_back(uint32_t(pos));
+            final_info_out_tmp.path.push_back((uint32_t)pos);
         }
         if (m_derive == DeriveType::HARDENED) {
-            info.path.push_back(uint32_t(pos) | 0x80000000L);
+            final_info_out_tmp.path.push_back(((uint32_t)pos) | 0x80000000L);
         }
+
+        // Derive keys or fetch them from cache
+        CExtPubKey final_extkey = m_root_extkey;
+        bool der = true;
+        if (read_cache) {
+            if (!read_cache->GetCachedDerivedExtPubKey(m_expr_index, pos,
+                                                       final_extkey)) {
+                return false;
+            }
+        } else if (IsHardened()) {
+            CExtKey xprv;
+            if (!GetDerivedExtKey(arg, xprv)) {
+                return false;
+            }
+            if (m_derive == DeriveType::UNHARDENED) {
+                der = xprv.Derive(xprv, pos);
+            }
+            if (m_derive == DeriveType::HARDENED) {
+                der = xprv.Derive(xprv, pos | 0x80000000UL);
+            }
+            final_extkey = xprv.Neuter();
+        } else {
+            for (auto entry : m_path) {
+                der = final_extkey.Derive(final_extkey, entry);
+                assert(der);
+            }
+            if (m_derive == DeriveType::UNHARDENED) {
+                der = final_extkey.Derive(final_extkey, pos);
+            }
+            assert(m_derive != DeriveType::HARDENED);
+        }
+        assert(der);
+
+        final_info_out = final_info_out_tmp;
+        key_out = final_extkey.pubkey;
+
+        if (write_cache) {
+            write_cache->CacheDerivedExtPubKey(m_expr_index, pos, final_extkey);
+        }
+
         return true;
     }
     std::string ToString() const override {
         std::string ret =
             EncodeExtPubKey(m_root_extkey) + FormatHDKeypath(m_path);
         if (IsRange()) {
             ret += "/*";
             if (m_derive == DeriveType::HARDENED) {
                 ret += '\'';
             }
         }
         return ret;
     }
     bool ToPrivateString(const SigningProvider &arg,
                          std::string &out) const override {
         CExtKey key;
         if (!GetExtKey(arg, key)) {
             return false;
         }
         out = EncodeExtKey(key) + FormatHDKeypath(m_path);
         if (IsRange()) {
             out += "/*";
             if (m_derive == DeriveType::HARDENED) {
                 out += '\'';
             }
         }
         return true;
     }
     bool GetPrivKey(int pos, const SigningProvider &arg,
                     CKey &key) const override {
         CExtKey extkey;
-        if (!GetExtKey(arg, extkey)) {
+        if (!GetDerivedExtKey(arg, extkey)) {
             return false;
         }
-        for (auto entry : m_path) {
-            extkey.Derive(extkey, entry);
-        }
         if (m_derive == DeriveType::UNHARDENED) {
             extkey.Derive(extkey, pos);
         }
         if (m_derive == DeriveType::HARDENED) {
             extkey.Derive(extkey, pos | 0x80000000UL);
         }
         key = extkey.key;
         return true;
     }
 };
 
 /** Base class for all Descriptor implementations. */
 class DescriptorImpl : public Descriptor {
     //! Public key arguments for this descriptor (size 1 for PK, PKH; any size
     //! for Multisig).
     const std::vector<std::unique_ptr<PubkeyProvider>> m_pubkey_args;
     //! The sub-descriptor argument (nullptr for everything but SH).
     //! In doc/descriptors.m this is referred to as SCRIPT expressions
     //! sh(SCRIPT), and distinct from KEY expressions and ADDR expressions.
     const std::unique_ptr<DescriptorImpl> m_subdescriptor_arg;
     //! The string name of the descriptor function.
     const std::string m_name;
 
 protected:
     //! Return a serialization of anything except pubkey and script arguments,
     //! to be prepended to those.
     virtual std::string ToStringExtra() const { return ""; }
 
     /**
      * A helper function to construct the scripts for this descriptor.
      *
      *  This function is invoked once for every CScript produced by evaluating
      *  m_subdescriptor_arg, or just once in case m_subdescriptor_arg is
      nullptr.
 
      *  @param pubkeys The evaluations of the m_pubkey_args field.
      *  @param script The evaluation of m_subdescriptor_arg (or nullptr when
      m_subdescriptor_arg is nullptr).
      *  @param out A FlatSigningProvider to put scripts or public keys in that
      are necessary to the solver.
      *             The script arguments to this function are automatically
      added, as is the origin info of the provided pubkeys.
      *  @return A vector with scriptPubKeys for this descriptor.
      */
     virtual std::vector<CScript>
     MakeScripts(const std::vector<CPubKey> &pubkeys, const CScript *script,
                 FlatSigningProvider &out) const = 0;
 
 public:
     DescriptorImpl(std::vector<std::unique_ptr<PubkeyProvider>> pubkeys,
                    std::unique_ptr<DescriptorImpl> script,
                    const std::string &name)
         : m_pubkey_args(std::move(pubkeys)),
           m_subdescriptor_arg(std::move(script)), m_name(name) {}
 
     bool IsSolvable() const override {
         if (m_subdescriptor_arg) {
             if (!m_subdescriptor_arg->IsSolvable()) {
                 return false;
             }
         }
         return true;
     }
 
     bool IsRange() const final {
         for (const auto &pubkey : m_pubkey_args) {
             if (pubkey->IsRange()) {
                 return true;
             }
         }
         if (m_subdescriptor_arg) {
             if (m_subdescriptor_arg->IsRange()) {
                 return true;
             }
         }
         return false;
     }
 
     bool ToStringHelper(const SigningProvider *arg, std::string &out,
                         bool priv) const {
         std::string extra = ToStringExtra();
         size_t pos = extra.size() > 0 ? 1 : 0;
         std::string ret = m_name + "(" + extra;
         for (const auto &pubkey : m_pubkey_args) {
             if (pos++) {
                 ret += ",";
             }
             std::string tmp;
             if (priv) {
                 if (!pubkey->ToPrivateString(*arg, tmp)) {
                     return false;
                 }
             } else {
                 tmp = pubkey->ToString();
             }
             ret += std::move(tmp);
         }
         if (m_subdescriptor_arg) {
             if (pos++) {
                 ret += ",";
             }
             std::string tmp;
             if (!m_subdescriptor_arg->ToStringHelper(arg, tmp, priv)) {
                 return false;
             }
             ret += std::move(tmp);
         }
         out = std::move(ret) + ")";
         return true;
     }
 
     std::string ToString() const final {
         std::string ret;
         ToStringHelper(nullptr, ret, false);
         return AddChecksum(ret);
     }
 
     bool ToPrivateString(const SigningProvider &arg,
                          std::string &out) const override final {
         bool ret = ToStringHelper(&arg, out, true);
         out = AddChecksum(out);
         return ret;
     }
 
     bool ExpandHelper(int pos, const SigningProvider &arg,
-                      Span<const uint8_t> *cache_read,
+                      const DescriptorCache *read_cache,
                       std::vector<CScript> &output_scripts,
                       FlatSigningProvider &out,
-                      std::vector<uint8_t> *cache_write) const {
+                      DescriptorCache *write_cache) const {
         std::vector<std::pair<CPubKey, KeyOriginInfo>> entries;
         entries.reserve(m_pubkey_args.size());
 
         // Construct temporary data in `entries` and `subscripts`, to avoid
         // producing output in case of failure.
         for (const auto &p : m_pubkey_args) {
             entries.emplace_back();
-            // If we have a cache, we don't need GetPubKey to compute the public
-            // key. Pass in nullptr to signify only origin info is desired.
-            if (!p->GetPubKey(pos, arg,
-                              cache_read ? nullptr : &entries.back().first,
-                              entries.back().second)) {
+            if (!p->GetPubKey(pos, arg, entries.back().first,
+                              entries.back().second, read_cache, write_cache)) {
                 return false;
             }
-            if (cache_read) {
-                // Cached expanded public key exists, use it.
-                if (cache_read->size() == 0) {
-                    return false;
-                }
-                bool compressed =
-                    ((*cache_read)[0] == 0x02 || (*cache_read)[0] == 0x03) &&
-                    cache_read->size() >= 33;
-                bool uncompressed =
-                    ((*cache_read)[0] == 0x04) && cache_read->size() >= 65;
-                if (!(compressed || uncompressed)) {
-                    return false;
-                }
-                CPubKey pubkey(cache_read->begin(),
-                               cache_read->begin() + (compressed ? 33 : 65));
-                entries.back().first = pubkey;
-                *cache_read = cache_read->subspan(compressed ? 33 : 65);
-            }
-            if (cache_write) {
-                cache_write->insert(cache_write->end(),
-                                    entries.back().first.begin(),
-                                    entries.back().first.end());
-            }
         }
         std::vector<CScript> subscripts;
         if (m_subdescriptor_arg) {
             FlatSigningProvider subprovider;
-            if (!m_subdescriptor_arg->ExpandHelper(pos, arg, cache_read,
+            if (!m_subdescriptor_arg->ExpandHelper(pos, arg, read_cache,
                                                    subscripts, subprovider,
-                                                   cache_write)) {
+                                                   write_cache)) {
                 return false;
             }
             out = Merge(out, subprovider);
         }
 
         std::vector<CPubKey> pubkeys;
         pubkeys.reserve(entries.size());
         for (auto &entry : entries) {
             pubkeys.push_back(entry.first);
             out.origins.emplace(
                 entry.first.GetID(),
                 std::make_pair<CPubKey, KeyOriginInfo>(
                     CPubKey(entry.first), std::move(entry.second)));
         }
         if (m_subdescriptor_arg) {
             for (const auto &subscript : subscripts) {
                 out.scripts.emplace(CScriptID(subscript), subscript);
                 std::vector<CScript> addscripts =
                     MakeScripts(pubkeys, &subscript, out);
                 for (auto &addscript : addscripts) {
                     output_scripts.push_back(std::move(addscript));
                 }
             }
         } else {
             output_scripts = MakeScripts(pubkeys, nullptr, out);
         }
         return true;
     }
 
     bool Expand(int pos, const SigningProvider &provider,
                 std::vector<CScript> &output_scripts, FlatSigningProvider &out,
-                std::vector<uint8_t> *cache = nullptr) const final {
-        return ExpandHelper(pos, provider, nullptr, output_scripts, out, cache);
+                DescriptorCache *write_cache = nullptr) const final {
+        return ExpandHelper(pos, provider, nullptr, output_scripts, out,
+                            write_cache);
     }
 
-    bool ExpandFromCache(int pos, const std::vector<uint8_t> &cache,
+    bool ExpandFromCache(int pos, const DescriptorCache &read_cache,
                          std::vector<CScript> &output_scripts,
                          FlatSigningProvider &out) const final {
-        Span<const uint8_t> span = MakeSpan(cache);
-        return ExpandHelper(pos, DUMMY_SIGNING_PROVIDER, &span, output_scripts,
-                            out, nullptr) &&
-               span.size() == 0;
+        return ExpandHelper(pos, DUMMY_SIGNING_PROVIDER, &read_cache,
+                            output_scripts, out, nullptr);
     }
 
     void ExpandPrivate(int pos, const SigningProvider &provider,
                        FlatSigningProvider &out) const final {
         for (const auto &p : m_pubkey_args) {
             CKey key;
             if (!p->GetPrivKey(pos, provider, key)) {
                 continue;
             }
             out.keys.emplace(key.GetPubKey().GetID(), key);
         }
         if (m_subdescriptor_arg) {
             FlatSigningProvider subprovider;
             m_subdescriptor_arg->ExpandPrivate(pos, provider, subprovider);
             out = Merge(out, subprovider);
         }
     }
 };
 
 /** A parsed addr(A) descriptor. */
 class AddressDescriptor final : public DescriptorImpl {
     const CTxDestination m_destination;
 
 protected:
     std::string ToStringExtra() const override {
         return EncodeDestination(m_destination, GetConfig());
     }
     std::vector<CScript> MakeScripts(const std::vector<CPubKey> &,
                                      const CScript *,
                                      FlatSigningProvider &) const override {
         return Vector(GetScriptForDestination(m_destination));
     }
 
 public:
     AddressDescriptor(CTxDestination destination)
         : DescriptorImpl({}, {}, "addr"),
           m_destination(std::move(destination)) {}
     bool IsSolvable() const final { return false; }
 };
 
 /** A parsed raw(H) descriptor. */
 class RawDescriptor final : public DescriptorImpl {
     const CScript m_script;
 
 protected:
     std::string ToStringExtra() const override {
         return HexStr(m_script.begin(), m_script.end());
     }
     std::vector<CScript> MakeScripts(const std::vector<CPubKey> &,
                                      const CScript *,
                                      FlatSigningProvider &) const override {
         return Vector(m_script);
     }
 
 public:
     RawDescriptor(CScript script)
         : DescriptorImpl({}, {}, "raw"), m_script(std::move(script)) {}
     bool IsSolvable() const final { return false; }
 };
 
 /** A parsed pk(P) descriptor. */
 class PKDescriptor final : public DescriptorImpl {
 protected:
     std::vector<CScript> MakeScripts(const std::vector<CPubKey> &keys,
                                      const CScript *,
                                      FlatSigningProvider &) const override {
         return Vector(GetScriptForRawPubKey(keys[0]));
     }
 
 public:
     PKDescriptor(std::unique_ptr<PubkeyProvider> prov)
         : DescriptorImpl(Vector(std::move(prov)), {}, "pk") {}
 };
 
 /** A parsed pkh(P) descriptor. */
 class PKHDescriptor final : public DescriptorImpl {
 protected:
     std::vector<CScript> MakeScripts(const std::vector<CPubKey> &keys,
                                      const CScript *,
                                      FlatSigningProvider &out) const override {
         CKeyID id = keys[0].GetID();
         out.pubkeys.emplace(id, keys[0]);
         return Vector(GetScriptForDestination(PKHash(id)));
     }
 
 public:
     PKHDescriptor(std::unique_ptr<PubkeyProvider> prov)
         : DescriptorImpl(Vector(std::move(prov)), {}, "pkh") {}
 };
 
 /** A parsed combo(P) descriptor. */
 class ComboDescriptor final : public DescriptorImpl {
 protected:
     std::vector<CScript> MakeScripts(const std::vector<CPubKey> &keys,
                                      const CScript *,
                                      FlatSigningProvider &out) const override {
         std::vector<CScript> ret;
         CKeyID id = keys[0].GetID();
         out.pubkeys.emplace(id, keys[0]);
         // P2PK
         ret.emplace_back(GetScriptForRawPubKey(keys[0]));
         // P2PKH
         ret.emplace_back(GetScriptForDestination(PKHash(id)));
         return ret;
     }
 
 public:
     ComboDescriptor(std::unique_ptr<PubkeyProvider> prov)
         : DescriptorImpl(Vector(std::move(prov)), {}, "combo") {}
 };
 
 /** A parsed multi(...) descriptor. */
 class MultisigDescriptor final : public DescriptorImpl {
     const int m_threshold;
     const bool m_sorted;
 
 protected:
     std::string ToStringExtra() const override {
         return strprintf("%i", m_threshold);
     }
     std::vector<CScript> MakeScripts(const std::vector<CPubKey> &keys,
                                      const CScript *,
                                      FlatSigningProvider &) const override {
         if (m_sorted) {
             std::vector<CPubKey> sorted_keys(keys);
             std::sort(sorted_keys.begin(), sorted_keys.end());
             return Vector(GetScriptForMultisig(m_threshold, sorted_keys));
         }
         return Vector(GetScriptForMultisig(m_threshold, keys));
     }
 
 public:
     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) {}
 };
 
 /** A parsed sh(...) descriptor. */
 class SHDescriptor final : public DescriptorImpl {
 protected:
     std::vector<CScript> MakeScripts(const std::vector<CPubKey> &,
                                      const CScript *script,
                                      FlatSigningProvider &) const override {
         return Vector(GetScriptForDestination(ScriptHash(*script)));
     }
 
 public:
     SHDescriptor(std::unique_ptr<DescriptorImpl> desc)
         : DescriptorImpl({}, std::move(desc), "sh") {}
 };
 
 ////////////////////////////////////////////////////////////////////////////
 // Parser                                                                 //
 ////////////////////////////////////////////////////////////////////////////
 
 enum class ParseScriptContext {
     TOP,
     P2SH,
 };
 
 /**
  * Parse a key path, being passed a split list of elements (the first element is
  * ignored).
  */
 NODISCARD bool ParseKeyPath(const std::vector<Span<const char>> &split,
                             KeyPath &out, std::string &error) {
     for (size_t i = 1; i < split.size(); ++i) {
         Span<const char> elem = split[i];
         bool hardened = false;
         if (elem.size() > 0 &&
             (elem[elem.size() - 1] == '\'' || elem[elem.size() - 1] == 'h')) {
             elem = elem.first(elem.size() - 1);
             hardened = true;
         }
         uint32_t p;
         if (!ParseUInt32(std::string(elem.begin(), elem.end()), &p)) {
             error = strprintf("Key path value '%s' is not a valid uint32",
                               std::string(elem.begin(), elem.end()).c_str());
             return false;
         } else if (p > 0x7FFFFFFFUL) {
             error = strprintf("Key path value %u is out of range", p);
             return false;
         }
         out.push_back(p | (uint32_t(hardened) << 31));
     }
     return true;
 }
 
 /** Parse a public key that excludes origin information. */
 std::unique_ptr<PubkeyProvider> ParsePubkeyInner(uint32_t key_exp_index,
                                                  const Span<const char> &sp,
                                                  FlatSigningProvider &out,
                                                  std::string &error) {
     using namespace spanparsing;
 
     auto split = Split(sp, '/');
     std::string str(split[0].begin(), split[0].end());
     if (str.size() == 0) {
         error = "No key provided";
         return nullptr;
     }
     if (split.size() == 1) {
         if (IsHex(str)) {
             std::vector<uint8_t> data = ParseHex(str);
             CPubKey pubkey(data);
             if (pubkey.IsFullyValid()) {
                 return std::make_unique<ConstPubkeyProvider>(key_exp_index,
                                                              pubkey);
             }
             error = strprintf("Pubkey '%s' is invalid", str);
             return nullptr;
         }
         CKey key = DecodeSecret(str);
         if (key.IsValid()) {
             CPubKey pubkey = key.GetPubKey();
             out.keys.emplace(pubkey.GetID(), key);
             return std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey);
         }
     }
     CExtKey extkey = DecodeExtKey(str);
     CExtPubKey extpubkey = DecodeExtPubKey(str);
     if (!extkey.key.IsValid() && !extpubkey.pubkey.IsValid()) {
         error = strprintf("key '%s' is not valid", str);
         return nullptr;
     }
     KeyPath path;
     DeriveType type = DeriveType::NO;
     if (split.back() == MakeSpan("*").first(1)) {
         split.pop_back();
         type = DeriveType::UNHARDENED;
     } else if (split.back() == MakeSpan("*'").first(2) ||
                split.back() == MakeSpan("*h").first(2)) {
         split.pop_back();
         type = DeriveType::HARDENED;
     }
     if (!ParseKeyPath(split, path, error)) {
         return nullptr;
     }
     if (extkey.key.IsValid()) {
         extpubkey = extkey.Neuter();
         out.keys.emplace(extpubkey.pubkey.GetID(), extkey.key);
     }
     return std::make_unique<BIP32PubkeyProvider>(key_exp_index, extpubkey,
                                                  std::move(path), type);
 }
 
 /** Parse a public key including origin information (if enabled). */
 std::unique_ptr<PubkeyProvider> ParsePubkey(uint32_t key_exp_index,
                                             const Span<const char> &sp,
                                             FlatSigningProvider &out,
                                             std::string &error) {
     using namespace spanparsing;
 
     auto origin_split = Split(sp, ']');
     if (origin_split.size() > 2) {
         error = "Multiple ']' characters found for a single pubkey";
         return nullptr;
     }
     if (origin_split.size() == 1) {
         return ParsePubkeyInner(key_exp_index, origin_split[0], out, error);
     }
     if (origin_split[0].size() < 1 || origin_split[0][0] != '[') {
         error = strprintf("Key origin start '[ character expected but not "
                           "found, got '%c' instead",
                           origin_split[0][0]);
         return nullptr;
     }
     auto slash_split = Split(origin_split[0].subspan(1), '/');
     if (slash_split[0].size() != 8) {
         error = strprintf("Fingerprint is not 4 bytes (%u characters instead "
                           "of 8 characters)",
                           slash_split[0].size());
         return nullptr;
     }
     std::string fpr_hex =
         std::string(slash_split[0].begin(), slash_split[0].end());
     if (!IsHex(fpr_hex)) {
         error = strprintf("Fingerprint '%s' is not hex", fpr_hex);
         return nullptr;
     }
     auto fpr_bytes = ParseHex(fpr_hex);
     KeyOriginInfo info;
     static_assert(sizeof(info.fingerprint) == 4, "Fingerprint must be 4 bytes");
     assert(fpr_bytes.size() == 4);
     std::copy(fpr_bytes.begin(), fpr_bytes.end(), info.fingerprint);
     if (!ParseKeyPath(slash_split, info.path, error)) {
         return nullptr;
     }
     auto provider =
         ParsePubkeyInner(key_exp_index, origin_split[1], out, error);
     if (!provider) {
         return nullptr;
     }
     return std::make_unique<OriginPubkeyProvider>(
         key_exp_index, std::move(info), std::move(provider));
 }
 
 /** Parse a script in a particular context. */
 std::unique_ptr<DescriptorImpl> ParseScript(uint32_t key_exp_index,
                                             Span<const char> &sp,
                                             ParseScriptContext ctx,
                                             FlatSigningProvider &out,
                                             std::string &error) {
     using namespace spanparsing;
 
     auto expr = Expr(sp);
     bool sorted_multi = false;
     if (Func("pk", expr)) {
         auto pubkey = ParsePubkey(key_exp_index, expr, out, error);
         if (!pubkey) {
             return nullptr;
         }
         return std::make_unique<PKDescriptor>(std::move(pubkey));
     }
     if (Func("pkh", expr)) {
         auto pubkey = ParsePubkey(key_exp_index, expr, out, error);
         if (!pubkey) {
             return nullptr;
         }
         return std::make_unique<PKHDescriptor>(std::move(pubkey));
     }
     if (ctx == ParseScriptContext::TOP && Func("combo", expr)) {
         auto pubkey = ParsePubkey(key_exp_index, expr, out, error);
         if (!pubkey) {
             return nullptr;
         }
         return std::make_unique<ComboDescriptor>(std::move(pubkey));
     } else if (ctx != ParseScriptContext::TOP && Func("combo", expr)) {
         error = "Cannot have combo in non-top level";
         return nullptr;
     }
     if ((sorted_multi = Func("sortedmulti", expr)) || Func("multi", expr)) {
         auto threshold = Expr(expr);
         uint32_t thres;
         std::vector<std::unique_ptr<PubkeyProvider>> providers;
         if (!ParseUInt32(std::string(threshold.begin(), threshold.end()),
                          &thres)) {
             error = strprintf(
                 "Multi threshold '%s' is not valid",
                 std::string(threshold.begin(), threshold.end()).c_str());
             return nullptr;
         }
         size_t script_size = 0;
         while (expr.size()) {
             if (!Const(",", expr)) {
                 error = strprintf("Multi: expected ',', got '%c'", expr[0]);
                 return nullptr;
             }
             auto arg = Expr(expr);
             auto pk = ParsePubkey(key_exp_index, arg, out, error);
             if (!pk) {
                 return nullptr;
             }
             script_size += pk->GetSize() + 1;
             providers.emplace_back(std::move(pk));
             key_exp_index++;
         }
         if (providers.size() < 1 || providers.size() > 16) {
             error = strprintf("Cannot have %u keys in multisig; must have "
                               "between 1 and 16 keys, inclusive",
                               providers.size());
             return nullptr;
         } else if (thres < 1) {
             error = strprintf(
                 "Multisig threshold cannot be %d, must be at least 1", thres);
             return nullptr;
         } else if (thres > providers.size()) {
             error =
                 strprintf("Multisig threshold cannot be larger than the number "
                           "of keys; threshold is %d but only %u keys specified",
                           thres, providers.size());
             return nullptr;
         }
         if (ctx == ParseScriptContext::TOP) {
             if (providers.size() > 3) {
                 error = strprintf("Cannot have %u pubkeys in bare multisig; "
                                   "only at most 3 pubkeys",
                                   providers.size());
                 return nullptr;
             }
         }
         if (ctx == ParseScriptContext::P2SH) {
             if (script_size + 3 > MAX_SCRIPT_ELEMENT_SIZE) {
                 error = strprintf("P2SH script is too large, %d bytes is "
                                   "larger than %d bytes",
                                   script_size + 3, MAX_SCRIPT_ELEMENT_SIZE);
                 return nullptr;
             }
         }
         return std::make_unique<MultisigDescriptor>(thres, std::move(providers),
                                                     sorted_multi);
     }
     if (ctx == ParseScriptContext::TOP && Func("sh", expr)) {
         auto desc = ParseScript(key_exp_index, expr, ParseScriptContext::P2SH,
                                 out, error);
         if (!desc || expr.size()) {
             return nullptr;
         }
         return std::make_unique<SHDescriptor>(std::move(desc));
     } else if (ctx != ParseScriptContext::TOP && Func("sh", expr)) {
         error = "Cannot have sh in non-top level";
         return nullptr;
     }
     if (ctx == ParseScriptContext::TOP && Func("addr", expr)) {
         CTxDestination dest =
             DecodeDestination(std::string(expr.begin(), expr.end()), Params());
         if (!IsValidDestination(dest)) {
             error = "Address is not valid";
             return nullptr;
         }
         return std::make_unique<AddressDescriptor>(std::move(dest));
     }
     if (ctx == ParseScriptContext::TOP && Func("raw", expr)) {
         std::string str(expr.begin(), expr.end());
         if (!IsHex(str)) {
             error = "Raw script is not hex";
             return nullptr;
         }
         auto bytes = ParseHex(str);
         return std::make_unique<RawDescriptor>(
             CScript(bytes.begin(), bytes.end()));
     }
     if (ctx == ParseScriptContext::P2SH) {
         error = "A function is needed within P2SH";
         return nullptr;
     }
     error = strprintf("%s is not a valid descriptor function",
                       std::string(expr.begin(), expr.end()));
     return nullptr;
 }
 
 std::unique_ptr<PubkeyProvider> InferPubkey(const CPubKey &pubkey,
                                             ParseScriptContext,
                                             const SigningProvider &provider) {
     std::unique_ptr<PubkeyProvider> key_provider =
         std::make_unique<ConstPubkeyProvider>(0, pubkey);
     KeyOriginInfo info;
     if (provider.GetKeyOrigin(pubkey.GetID(), info)) {
         return std::make_unique<OriginPubkeyProvider>(0, std::move(info),
                                                       std::move(key_provider));
     }
     return key_provider;
 }
 
 std::unique_ptr<DescriptorImpl> InferScript(const CScript &script,
                                             ParseScriptContext ctx,
                                             const SigningProvider &provider) {
     std::vector<std::vector<uint8_t>> data;
     txnouttype txntype = Solver(script, data);
 
     if (txntype == TX_PUBKEY) {
         CPubKey pubkey(data[0].begin(), data[0].end());
         if (pubkey.IsValid()) {
             return std::make_unique<PKDescriptor>(
                 InferPubkey(pubkey, ctx, provider));
         }
     }
     if (txntype == TX_PUBKEYHASH) {
         uint160 hash(data[0]);
         CKeyID keyid(hash);
         CPubKey pubkey;
         if (provider.GetPubKey(keyid, pubkey)) {
             return std::make_unique<PKHDescriptor>(
                 InferPubkey(pubkey, ctx, provider));
         }
     }
     if (txntype == TX_MULTISIG) {
         std::vector<std::unique_ptr<PubkeyProvider>> providers;
         for (size_t i = 1; i + 1 < data.size(); ++i) {
             CPubKey pubkey(data[i].begin(), data[i].end());
             providers.push_back(InferPubkey(pubkey, ctx, provider));
         }
         return std::make_unique<MultisigDescriptor>((int)data[0][0],
                                                     std::move(providers));
     }
     if (txntype == TX_SCRIPTHASH && ctx == ParseScriptContext::TOP) {
         uint160 hash(data[0]);
         CScriptID scriptid(hash);
         CScript subscript;
         if (provider.GetCScript(scriptid, subscript)) {
             auto sub =
                 InferScript(subscript, ParseScriptContext::P2SH, provider);
             if (sub) {
                 return std::make_unique<SHDescriptor>(std::move(sub));
             }
         }
     }
 
     CTxDestination dest;
     if (ExtractDestination(script, dest)) {
         if (GetScriptForDestination(dest) == script) {
             return std::make_unique<AddressDescriptor>(std::move(dest));
         }
     }
 
     return std::make_unique<RawDescriptor>(script);
 }
 
 } // namespace
 
 /**
  * Check a descriptor checksum, and update desc to be the checksum-less part.
  */
 bool CheckChecksum(Span<const char> &sp, bool require_checksum,
                    std::string &error, std::string *out_checksum = nullptr) {
     using namespace spanparsing;
 
     auto check_split = Split(sp, '#');
     if (check_split.size() > 2) {
         error = "Multiple '#' symbols";
         return false;
     }
     if (check_split.size() == 1 && require_checksum) {
         error = "Missing checksum";
         return false;
     }
     if (check_split.size() == 2) {
         if (check_split[1].size() != 8) {
             error =
                 strprintf("Expected 8 character checksum, not %u characters",
                           check_split[1].size());
             return false;
         }
     }
     auto checksum = DescriptorChecksum(check_split[0]);
     if (checksum.empty()) {
         error = "Invalid characters in payload";
         return false;
     }
     if (check_split.size() == 2) {
         if (!std::equal(checksum.begin(), checksum.end(),
                         check_split[1].begin())) {
             error = strprintf(
                 "Provided checksum '%s' does not match computed checksum '%s'",
                 std::string(check_split[1].begin(), check_split[1].end()),
                 checksum);
             return false;
         }
     }
     if (out_checksum) {
         *out_checksum = std::move(checksum);
     }
     sp = check_split[0];
     return true;
 }
 
 std::unique_ptr<Descriptor> Parse(const std::string &descriptor,
                                   FlatSigningProvider &out, std::string &error,
                                   bool require_checksum) {
     Span<const char> sp(descriptor.data(), descriptor.size());
     if (!CheckChecksum(sp, require_checksum, error)) {
         return nullptr;
     }
     auto ret = ParseScript(0, sp, ParseScriptContext::TOP, out, error);
     if (sp.size() == 0 && ret) {
         return std::unique_ptr<Descriptor>(std::move(ret));
     }
     return nullptr;
 }
 
 std::string GetDescriptorChecksum(const std::string &descriptor) {
     std::string ret;
     std::string error;
     Span<const char> sp(descriptor.data(), descriptor.size());
     if (!CheckChecksum(sp, false, error, &ret)) {
         return "";
     }
     return ret;
 }
 
 std::unique_ptr<Descriptor> InferDescriptor(const CScript &script,
                                             const SigningProvider &provider) {
     return InferScript(script, ParseScriptContext::TOP, provider);
 }
 
 void DescriptorCache::CacheParentExtPubKey(uint32_t key_exp_pos,
                                            const CExtPubKey &xpub) {
     m_parent_xpubs[key_exp_pos] = xpub;
 }
 
 void DescriptorCache::CacheDerivedExtPubKey(uint32_t key_exp_pos,
                                             uint32_t der_index,
                                             const CExtPubKey &xpub) {
     auto &xpubs = m_derived_xpubs[key_exp_pos];
     xpubs[der_index] = xpub;
 }
 
 bool DescriptorCache::GetCachedParentExtPubKey(uint32_t key_exp_pos,
                                                CExtPubKey &xpub) const {
     const auto &it = m_parent_xpubs.find(key_exp_pos);
     if (it == m_parent_xpubs.end()) {
         return false;
     }
     xpub = it->second;
     return true;
 }
 
 bool DescriptorCache::GetCachedDerivedExtPubKey(uint32_t key_exp_pos,
                                                 uint32_t der_index,
                                                 CExtPubKey &xpub) const {
     const auto &key_exp_it = m_derived_xpubs.find(key_exp_pos);
     if (key_exp_it == m_derived_xpubs.end()) {
         return false;
     }
     const auto &der_it = key_exp_it->second.find(der_index);
     if (der_it == key_exp_it->second.end()) {
         return false;
     }
     xpub = der_it->second;
     return true;
 }
 
 const ExtPubKeyMap DescriptorCache::GetCachedParentExtPubKeys() const {
     return m_parent_xpubs;
 }
 
 const std::unordered_map<uint32_t, ExtPubKeyMap>
 DescriptorCache::GetCachedDerivedExtPubKeys() const {
     return m_derived_xpubs;
 }
diff --git a/src/script/descriptor.h b/src/script/descriptor.h
index e35ffcb29..a16a0d80b 100644
--- a/src/script/descriptor.h
+++ b/src/script/descriptor.h
@@ -1,198 +1,198 @@
 // Copyright (c) 2018 The Bitcoin Core developers
 // Distributed under the MIT software license, see the accompanying
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
 #ifndef BITCOIN_SCRIPT_DESCRIPTOR_H
 #define BITCOIN_SCRIPT_DESCRIPTOR_H
 
 #include <script/script.h>
 #include <script/sign.h>
 #include <script/signingprovider.h>
 
 #include <vector>
 
 using ExtPubKeyMap = std::unordered_map<uint32_t, CExtPubKey>;
 
 /** Cache for single descriptor's derived extended pubkeys */
 class DescriptorCache {
 private:
     /** Map key expression index -> map of (key derivation index -> xpub) */
     std::unordered_map<uint32_t, ExtPubKeyMap> m_derived_xpubs;
     /** Map key expression index -> parent xpub */
     ExtPubKeyMap m_parent_xpubs;
 
 public:
     /**
      * Cache a parent xpub
      *
      * @param[in] key_exp_pos Position of the key expression within the
      *                        descriptor
      * @param[in] xpub The CExtPubKey to cache
      */
     void CacheParentExtPubKey(uint32_t key_exp_pos, const CExtPubKey &xpub);
     /**
      * Retrieve a cached parent xpub
      *
      * @param[in] key_exp_pos Position of the key expression within the
      *                        descriptor
      * @param[in] xpub The CExtPubKey to get from cache
      */
     bool GetCachedParentExtPubKey(uint32_t key_exp_pos, CExtPubKey &xpub) const;
     /**
      * Cache an xpub derived at an index
      *
      * @param[in] key_exp_pos Position of the key expression within the
      *                        descriptor
      * @param[in] der_index Derivation index of the xpub
      * @param[in] xpub The CExtPubKey to cache
      */
     void CacheDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index,
                                const CExtPubKey &xpub);
     /**
      * Retrieve a cached xpub derived at an index
      *
      * @param[in] key_exp_pos Position of the key expression within the
      *                        descriptor
      * @param[in] der_index Derivation index of the xpub
      * @param[in] xpub The CExtPubKey to get from cache
      */
     bool GetCachedDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index,
                                    CExtPubKey &xpub) const;
 
     /** Retrieve all cached parent xpubs */
     const ExtPubKeyMap GetCachedParentExtPubKeys() const;
     /** Retrieve all cached derived xpubs */
     const std::unordered_map<uint32_t, ExtPubKeyMap>
     GetCachedDerivedExtPubKeys() const;
 };
 
 /**
  *  \brief Interface for parsed descriptor objects.
  *
  * Descriptors are strings that describe a set of scriptPubKeys, together with
  * all information necessary to solve them. By combining all information into
  * one, they avoid the need to separately import keys and scripts.
  *
  * Descriptors may be ranged, which occurs when the public keys inside are
  * specified in the form of HD chains (xpubs).
  *
  * Descriptors always represent public information - public keys and scripts -
  * but in cases where private keys need to be conveyed along with a descriptor,
  * they can be included inside by changing public keys to private keys (WIF
  * format), and changing xpubs by xprvs.
  *
  * Reference documentation about the descriptor language can be found in
  * doc/descriptors.md.
  */
 struct Descriptor {
     virtual ~Descriptor() = default;
 
     /** Whether the expansion of this descriptor depends on the position. */
     virtual bool IsRange() const = 0;
 
     /**
      * Whether this descriptor has all information about signing ignoring lack
      * of private keys. This is true for all descriptors except ones that use
      * `raw` or `addr` constructions.
      */
     virtual bool IsSolvable() const = 0;
 
     /** Convert the descriptor back to a string, undoing parsing. */
     virtual std::string ToString() const = 0;
 
     /**
      * Convert the descriptor to a private string. This fails if the provided
      * provider does not have the relevant private keys.
      */
     virtual bool ToPrivateString(const SigningProvider &provider,
                                  std::string &out) const = 0;
 
     /**
      * Expand a descriptor at a specified position.
      *
      * @param[in] pos: The position at which to expand the descriptor. If
      *                 IsRange() is false, this is ignored.
      * @param[in] provider: The provider to query for private keys in case of
      *                      hardened derivation.
      * @param[out] output_scripts: The expanded scriptPubKeys.
      * @param[out] out: Scripts and public keys necessary for solving the
      *                  expanded scriptPubKeys (may be equal to `provider`).
-     * @param[out] cache: Cache data necessary to evaluate the descriptor at
-     *                    this point without access to private keys.
+     * @param[out] write_cache: Cache data necessary to evaluate the descriptor
+     *                          at this point without access to private keys.
      */
     virtual bool Expand(int pos, const SigningProvider &provider,
                         std::vector<CScript> &output_scripts,
                         FlatSigningProvider &out,
-                        std::vector<uint8_t> *cache = nullptr) const = 0;
+                        DescriptorCache *write_cache = nullptr) const = 0;
 
     /**
      * Expand a descriptor at a specified position using cached expansion data.
      *
      * @param[in] pos: The position at which to expand the descriptor. If
      *                 IsRange() is false, this is ignored.
-     * @param[in] cache: Cached expansion data.
+     * @param[in] read_cache: Cached expansion data.
      * @param[out] output_scripts: The expanded scriptPubKeys.
      * @param[out] out: Scripts and public keys necessary for solving the
      *                  expanded scriptPubKeys (may be equal to `provider`).
      */
-    virtual bool ExpandFromCache(int pos, const std::vector<uint8_t> &cache,
+    virtual bool ExpandFromCache(int pos, const DescriptorCache &read_cache,
                                  std::vector<CScript> &output_scripts,
                                  FlatSigningProvider &out) const = 0;
 
     /**
      * Expand the private key for a descriptor at a specified position, if
      * possible.
      *
      * @param[in] pos: The position at which to expand the descriptor. If
      *                 IsRange() is false, this is ignored.
      * @param[in] provider: The provider to query for the private keys.
      * @param[out] out: Any private keys available for the specified `pos`.
      */
     virtual void ExpandPrivate(int pos, const SigningProvider &provider,
                                FlatSigningProvider &out) const = 0;
 };
 
 /**
  * Parse a `descriptor` string. Included private keys are put in `out`.
  *
  * If the descriptor has a checksum, it must be valid. If `require_checksum`
  * is set, the checksum is mandatory - otherwise it is optional.
  *
  * If a parse error occurs, or the checksum is missing/invalid, or anything
  * else is wrong, `nullptr` is returned.
  */
 std::unique_ptr<Descriptor> Parse(const std::string &descriptor,
                                   FlatSigningProvider &out, std::string &error,
                                   bool require_checksum = false);
 
 /**
  * Get the checksum for a `descriptor`.
  *
  * - If it already has one, and it is correct, return the checksum in the input.
  * - If it already has one that is wrong, return "".
  * - If it does not already have one, return the checksum that would need to be
  * added.
  */
 std::string GetDescriptorChecksum(const std::string &descriptor);
 
 /**
  * Find a descriptor for the specified `script`, using information from
  * `provider` where possible.
  *
  * A non-ranged descriptor which only generates the specified script will be
  * returned in all circumstances.
  *
  * For public keys with key origin information, this information will be
  * preserved in the returned descriptor.
  *
  * - If all information for solving `script` is present in `provider`, a
  * descriptor will be returned which is IsSolvable() and encapsulates said
  * information.
  * - Failing that, if `script` corresponds to a known address type, an "addr()"
  * descriptor will be returned (which is not IsSolvable()).
  * - Failing that, a "raw()" descriptor is returned.
  */
 std::unique_ptr<Descriptor> InferDescriptor(const CScript &script,
                                             const SigningProvider &provider);
 
 #endif // BITCOIN_SCRIPT_DESCRIPTOR_H
diff --git a/src/test/descriptor_tests.cpp b/src/test/descriptor_tests.cpp
index ae041c809..82eed604d 100644
--- a/src/test/descriptor_tests.cpp
+++ b/src/test/descriptor_tests.cpp
@@ -1,818 +1,818 @@
 // Copyright (c) 2018-2019 The Bitcoin Core developers
 // Distributed under the MIT software license, see the accompanying
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
 #include <script/descriptor.h>
 #include <script/sign.h>
 #include <script/standard.h>
 #include <util/strencodings.h>
 
 #include <test/util/setup_common.h>
 
 #include <boost/test/unit_test.hpp>
 
 #include <string>
 #include <vector>
 
 namespace {
 
 void CheckUnparsable(const std::string &prv, const std::string &pub,
                      const std::string &expected_error) {
     FlatSigningProvider keys_priv, keys_pub;
     std::string error;
     auto parse_priv = Parse(prv, keys_priv, error);
     auto parse_pub = Parse(pub, keys_pub, error);
     BOOST_CHECK_MESSAGE(!parse_priv, prv);
     BOOST_CHECK_MESSAGE(!parse_pub, pub);
     BOOST_CHECK(error == expected_error);
 }
 
 constexpr int DEFAULT = 0;
 // Expected to be ranged descriptor
 constexpr int RANGE = 1;
 // Derivation needs access to private keys
 constexpr int HARDENED = 2;
 // This descriptor is not expected to be solvable
 constexpr int UNSOLVABLE = 4;
 // We can sign with this descriptor (this is not true when actual BIP32
 // derivation is used, as that's not integrated in our signing code)
 constexpr int SIGNABLE = 8;
 
 /**
  * Compare two descriptors. If only one of them has a checksum, the checksum is
  * ignored.
  */
 bool EqualDescriptor(std::string a, std::string b) {
     bool a_check = (a.size() > 9 && a[a.size() - 9] == '#');
     bool b_check = (b.size() > 9 && b[b.size() - 9] == '#');
     if (a_check != b_check) {
         if (a_check) {
             a = a.substr(0, a.size() - 9);
         }
         if (b_check) {
             b = b.substr(0, b.size() - 9);
         }
     }
     return a == b;
 }
 
 std::string UseHInsteadOfApostrophe(const std::string &desc) {
     std::string ret = desc;
     while (true) {
         auto it = ret.find('\'');
         if (it == std::string::npos) {
             break;
         }
         ret[it] = 'h';
     }
 
     // GetDescriptorChecksum returns "" if the checksum exists but is bad.
     // Switching apostrophes with 'h' breaks the checksum if it exists -
     // recalculate it and replace the broken one.
     if (GetDescriptorChecksum(ret) == "") {
         ret = ret.substr(0, desc.size() - 9);
         ret += std::string("#") + GetDescriptorChecksum(ret);
     }
     return ret;
 }
 
 const std::set<std::vector<uint32_t>> ONLY_EMPTY{{}};
 
 void DoCheck(const std::string &prv, const std::string &pub, int flags,
              const std::vector<std::vector<std::string>> &scripts,
              const std::set<std::vector<uint32_t>> &paths = ONLY_EMPTY,
              bool replace_apostrophe_with_h_in_prv = false,
              bool replace_apostrophe_with_h_in_pub = false) {
     FlatSigningProvider keys_priv, keys_pub;
     std::set<std::vector<uint32_t>> left_paths = paths;
     std::string error_priv;
     std::string error_pub;
 
     std::unique_ptr<Descriptor> parse_priv;
     std::unique_ptr<Descriptor> parse_pub;
     // Check that parsing succeeds.
     if (replace_apostrophe_with_h_in_prv) {
         parse_priv = Parse(UseHInsteadOfApostrophe(prv), keys_priv, error_priv);
     } else {
         parse_priv = Parse(prv, keys_priv, error_priv);
     }
     if (replace_apostrophe_with_h_in_pub) {
         parse_pub = Parse(UseHInsteadOfApostrophe(pub), keys_pub, error_pub);
     } else {
         parse_pub = Parse(pub, keys_pub, error_pub);
     }
 
     BOOST_CHECK_MESSAGE(parse_priv, error_priv);
     BOOST_CHECK_MESSAGE(parse_pub, error_pub);
 
     // Check private keys are extracted from the private version but not the
     // public one.
     BOOST_CHECK(keys_priv.keys.size());
     BOOST_CHECK(!keys_pub.keys.size());
 
     // Check that both versions serialize back to the public version.
     std::string pub1 = parse_priv->ToString();
     std::string pub2 = parse_pub->ToString();
     BOOST_CHECK(EqualDescriptor(pub, pub1));
     BOOST_CHECK(EqualDescriptor(pub, pub2));
 
     // Check that both can be serialized with private key back to the private
     // version, but not without private key.
     std::string prv1, prv2;
     BOOST_CHECK(parse_priv->ToPrivateString(keys_priv, prv1));
     BOOST_CHECK(EqualDescriptor(prv, prv1));
     BOOST_CHECK(!parse_priv->ToPrivateString(keys_pub, prv1));
     BOOST_CHECK(parse_pub->ToPrivateString(keys_priv, prv1));
     BOOST_CHECK(EqualDescriptor(prv, prv1));
     BOOST_CHECK(!parse_pub->ToPrivateString(keys_pub, prv1));
 
     // Check whether IsRange on both returns the expected result
     BOOST_CHECK_EQUAL(parse_pub->IsRange(), (flags & RANGE) != 0);
     BOOST_CHECK_EQUAL(parse_priv->IsRange(), (flags & RANGE) != 0);
 
     // * For ranged descriptors,  the `scripts` parameter is a list of expected
     // result outputs, for subsequent
     //   positions to evaluate the descriptors on (so the first element of
     //   `scripts` is for evaluating the descriptor at 0; the second at 1; and
     //   so on). To verify this, we evaluate the descriptors once for each
     //   element in `scripts`.
     // * For non-ranged descriptors, we evaluate the descriptors at positions 0,
     // 1, and 2, but expect the
     //   same result in each case, namely the first element of `scripts`.
     //   Because of that, the size of `scripts` must be one in that case.
     if (!(flags & RANGE)) {
         assert(scripts.size() == 1);
     }
     size_t max = (flags & RANGE) ? scripts.size() : 3;
 
     // Iterate over the position we'll evaluate the descriptors in.
     for (size_t i = 0; i < max; ++i) {
         // Call the expected result scripts `ref`.
         const auto &ref = scripts[(flags & RANGE) ? i : 0];
         // When t=0, evaluate the `prv` descriptor; when t=1, evaluate the `pub`
         // descriptor.
         for (int t = 0; t < 2; ++t) {
             // When the descriptor is hardened, evaluate with access to the
             // private keys inside.
             const FlatSigningProvider &key_provider =
                 (flags & HARDENED) ? keys_priv : keys_pub;
 
             // Evaluate the descriptor selected by `t` in position `i`.
             FlatSigningProvider script_provider, script_provider_cached;
             std::vector<CScript> spks, spks_cached;
-            std::vector<uint8_t> cache;
-            BOOST_CHECK(
-                (t ? parse_priv : parse_pub)
-                    ->Expand(i, key_provider, spks, script_provider, &cache));
+            DescriptorCache desc_cache;
+            BOOST_CHECK((t ? parse_priv : parse_pub)
+                            ->Expand(i, key_provider, spks, script_provider,
+                                     &desc_cache));
 
             // Compare the output with the expected result.
             BOOST_CHECK_EQUAL(spks.size(), ref.size());
 
             // Try to expand again using cached data, and compare.
-            BOOST_CHECK(parse_pub->ExpandFromCache(i, cache, spks_cached,
+            BOOST_CHECK(parse_pub->ExpandFromCache(i, desc_cache, spks_cached,
                                                    script_provider_cached));
             BOOST_CHECK(spks == spks_cached);
             BOOST_CHECK(script_provider.pubkeys ==
                         script_provider_cached.pubkeys);
             BOOST_CHECK(script_provider.scripts ==
                         script_provider_cached.scripts);
             BOOST_CHECK(script_provider.origins ==
                         script_provider_cached.origins);
 
             // For each of the produced scripts, verify solvability, and when
             // possible, try to sign a transaction spending it.
             for (size_t n = 0; n < spks.size(); ++n) {
                 BOOST_CHECK_EQUAL(ref[n],
                                   HexStr(spks[n].begin(), spks[n].end()));
                 BOOST_CHECK_EQUAL(
                     IsSolvable(Merge(key_provider, script_provider), spks[n]),
                     (flags & UNSOLVABLE) == 0);
 
                 if (flags & SIGNABLE) {
                     CMutableTransaction spend;
                     spend.vin.resize(1);
                     spend.vout.resize(1);
                     BOOST_CHECK_MESSAGE(
                         SignSignature(Merge(keys_priv, script_provider),
                                       spks[n], spend, 0, 1 * COIN,
                                       SigHashType().withForkId()),
                         prv);
                 }
 
                 // Infer a descriptor from the generated script, and verify its
                 // solvability and that it roundtrips.
                 auto inferred = InferDescriptor(spks[n], script_provider);
                 BOOST_CHECK_EQUAL(inferred->IsSolvable(),
                                   !(flags & UNSOLVABLE));
                 std::vector<CScript> spks_inferred;
                 FlatSigningProvider provider_inferred;
                 BOOST_CHECK(inferred->Expand(0, provider_inferred,
                                              spks_inferred, provider_inferred));
                 BOOST_CHECK_EQUAL(spks_inferred.size(), 1);
                 BOOST_CHECK(spks_inferred[0] == spks[n]);
                 BOOST_CHECK_EQUAL(
                     IsSolvable(provider_inferred, spks_inferred[0]),
                     !(flags & UNSOLVABLE));
                 BOOST_CHECK(provider_inferred.origins ==
                             script_provider.origins);
             }
 
             // Test whether the observed key path is present in the 'paths'
             // variable (which contains expected, unobserved paths), and then
             // remove it from that set.
             for (const auto &origin : script_provider.origins) {
                 BOOST_CHECK_MESSAGE(paths.count(origin.second.second.path),
                                     "Unexpected key path: " + prv);
                 left_paths.erase(origin.second.second.path);
             }
         }
     }
 
     // Verify no expected paths remain that were not observed.
     BOOST_CHECK_MESSAGE(left_paths.empty(),
                         "Not all expected key paths found: " + prv);
 }
 
 void Check(const std::string &prv, const std::string &pub, int flags,
            const std::vector<std::vector<std::string>> &scripts,
            const std::set<std::vector<uint32_t>> &paths = ONLY_EMPTY) {
     bool found_apostrophes_in_prv = false;
     bool found_apostrophes_in_pub = false;
 
     // Do not replace apostrophes with 'h' in prv and pub
     DoCheck(prv, pub, flags, scripts, paths);
 
     // Replace apostrophes with 'h' in prv but not in pub, if apostrophes are
     // found in prv
     if (prv.find('\'') != std::string::npos) {
         found_apostrophes_in_prv = true;
         DoCheck(prv, pub, flags, scripts, paths,
                 /* replace_apostrophe_with_h_in_prv = */ true,
                 /*replace_apostrophe_with_h_in_pub = */ false);
     }
 
     // Replace apostrophes with 'h' in pub but not in prv, if apostrophes are
     // found in pub
     if (pub.find('\'') != std::string::npos) {
         found_apostrophes_in_pub = true;
         DoCheck(prv, pub, flags, scripts, paths,
                 /* replace_apostrophe_with_h_in_prv = */ false,
                 /*replace_apostrophe_with_h_in_pub = */ true);
     }
 
     // Replace apostrophes with 'h' both in prv and in pub, if apostrophes are
     // found in both
     if (found_apostrophes_in_prv && found_apostrophes_in_pub) {
         DoCheck(prv, pub, flags, scripts, paths,
                 /* replace_apostrophe_with_h_in_prv = */ true,
                 /*replace_apostrophe_with_h_in_pub = */ true);
     }
 }
 
 } // namespace
 
 BOOST_FIXTURE_TEST_SUITE(descriptor_tests, BasicTestingSetup)
 
 BOOST_AUTO_TEST_CASE(descriptor_test) {
     // Basic single-key compressed
     Check("combo(L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1)",
           "combo("
           "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd)",
           SIGNABLE,
           {{"2103a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5"
             "bdac",
             "76a9149a1c78a507689f6f54b847ad1cef1e614ee23f1e88ac"}});
     Check("pk(L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1)",
           "pk("
           "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd)",
           SIGNABLE,
           {{"2103a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5"
             "bdac"}});
     Check("pkh([deadbeef/1/2'/3/4']"
           "L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1)",
           "pkh([deadbeef/1/2'/3/4']"
           "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd)",
           SIGNABLE, {{"76a9149a1c78a507689f6f54b847ad1cef1e614ee23f1e88ac"}},
           {{1, 0x80000002UL, 3, 0x80000004UL}});
     // Missing start bracket in key origin
     CheckUnparsable(
         "pkh(deadbeef/1/2'/3/"
         "4']L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1)",
         "pkh(deadbeef/1/2'/3/"
         "4']"
         "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd)",
         "Key origin start '[ character expected but not found, got 'd' "
         "instead");
     // Multiple end brackets in key origin
     CheckUnparsable(
         "pkh([deadbeef]/1/2'/3/"
         "4']L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1)",
         "pkh([deadbeef]/1/2'/3/"
         "4']"
         "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd)",
         "Multiple ']' characters found for a single pubkey");
 
     // Basic single-key uncompressed
     Check(
         "combo(5KYZdUEo39z3FPrtuX2QbbwGnNP5zTd7yyr2SC1j299sBCnWjss)",
         "combo("
         "04a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd5b8d"
         "ec5235a0fa8722476c7709c02559e3aa73aa03918ba2d492eea75abea235)",
         SIGNABLE,
         {{"4104a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd"
           "5b8dec5235a0fa8722476c7709c02559e3aa73aa03918ba2d492eea75abea235ac",
           "76a914b5bd079c4d57cc7fc28ecf8213a6b791625b818388ac"}});
     Check("pk(5KYZdUEo39z3FPrtuX2QbbwGnNP5zTd7yyr2SC1j299sBCnWjss)",
           "pk("
           "04a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd5b"
           "8dec5235a0fa8722476c7709c02559e3aa73aa03918ba2d492eea75abea235)",
           SIGNABLE,
           {{"4104a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5"
             "bd5b8dec5235a0fa8722476c7709c02559e3aa73aa03918ba2d492eea75abea235"
             "ac"}});
     Check("pkh(5KYZdUEo39z3FPrtuX2QbbwGnNP5zTd7yyr2SC1j299sBCnWjss)",
           "pkh("
           "04a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd5b"
           "8dec5235a0fa8722476c7709c02559e3aa73aa03918ba2d492eea75abea235)",
           SIGNABLE, {{"76a914b5bd079c4d57cc7fc28ecf8213a6b791625b818388ac"}});
 
     // Some unconventional single-key constructions
     Check(
         "sh(pk(L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1))",
         "sh(pk("
         "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd))",
         SIGNABLE, {{"a9141857af51a5e516552b3086430fd8ce55f7c1a52487"}});
     Check(
         "sh(pkh(L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1))",
         "sh(pkh("
         "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd))",
         SIGNABLE, {{"a9141a31ad23bf49c247dd531a623c2ef57da3c400c587"}});
 
     // Versions with BIP32 derivations
     Check("combo([01234567]"
           "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39"
           "njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc)",
           "combo([01234567]"
           "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4"
           "koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL)",
           SIGNABLE,
           {{"2102d2b36900396c9282fa14628566582f206a5dd0bcc8d5e892611806cafb0301"
             "f0ac",
             "76a91431a507b815593dfc51ffc7245ae7e5aee304246e88ac"}});
     Check("pk("
           "xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7"
           "AANYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0)",
           "pk("
           "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHB"
           "aohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0)",
           DEFAULT,
           {{"210379e45b3cf75f9c5f9befd8e9506fb962f6a9d185ac87001ec44a8d3df8d4a9"
             "e3ac"}},
           {{0}});
     Check("pkh("
           "xprv9s21ZrQH143K31xYSDQpPDxsXRTUcvj2iNHm5NUtrGiGG5e2DtALGdso3pGz6ssr"
           "dK4PFmM8NSpSBHNqPqm55Qn3LqFtT2emdEXVYsCzC2U/2147483647'/0)",
           "pkh("
           "xpub661MyMwAqRbcFW31YEwpkMuc5THy2PSt5bDMsktWQcFF8syAmRUapSCGu8ED9W6o"
           "DMSgv6Zz8idoc4a6mr8BDzTJY47LJhkJ8UB7WEGuduB/2147483647'/0)",
           HARDENED, {{"76a914ebdc90806a9c4356c1c88e42216611e1cb4c1c1788ac"}},
           {{0xFFFFFFFFUL, 0}});
     Check("pkh([ffffffff/13']"
           "xprv9vHkqa6EV4sPZHYqZznhT2NPtPCjKuDKGY38FBWLvgaDx45zo9WQRUT3dKYnjwih"
           "2yJD9mkrocEZXo1ex8G81dwSM1fwqWpWkeS3v86pgKt/1/2/*)",
           "pkh([ffffffff/13']"
           "xpub69H7F5d8KSRgmmdJg2KhpAK8SR3DjMwAdkxj3ZuxV27CprR9LgpeyGmXUbC6wb7E"
           "RfvrnKZjXoUmmDznezpbZb7ap6r1D3tgFxHmwMkQTPH/1/2/*)",
           RANGE,
           {{"76a914326b2249e3a25d5dc60935f044ee835d090ba85988ac"},
            {"76a914af0bd98abc2f2cae66e36896a39ffe2d32984fb788ac"},
            {"76a9141fa798efd1cbf95cebf912c031b8a4a6e9fb9f2788ac"}},
           {{0x8000000DUL, 1, 2, 0},
            {0x8000000DUL, 1, 2, 1},
            {0x8000000DUL, 1, 2, 2}});
     Check("sh(pkh("
           "xprv9s21ZrQH143K3QTDL4LXw2F7HEK3wJUD2nW2nRk4stbPy6cq3jPPqjiChkVvvNKm"
           "PGJxWUtg6LnF5kejMRNNU3TGtRBeJgk33yuGBxrMPHi/10/20/30/40/*'))",
           "sh(pkh("
           "xpub661MyMwAqRbcFtXgS5sYJABqqG9YLmC4Q1Rdap9gSE8NqtwybGhePY2gZ29ESFjq"
           "JoCu1Rupje8YtGqsefD265TMg7usUDFdp6W1EGMcet8/10/20/30/40/*'))",
           RANGE | HARDENED,
           {{"a9149976cc014a7c012bbc43954a38cdee554865bd1987"},
            {"a914ad29a49cb0420b53d9d6bb8944bcd819c5ff716e87"},
            {"a914b2d9d290b193fd23b720e738184e3eedadc7d87d87"}},
           {{10, 20, 30, 40, 0x80000000UL},
            {10, 20, 30, 40, 0x80000001UL},
            {10, 20, 30, 40, 0x80000002UL}});
     Check("combo("
           "xprvA2JDeKCSNNZky6uBCviVfJSKyQ1mDYahRjijr5idH2WwLsEd4Hsb2Tyh8RfQMuPh"
           "7f7RtyzTtdrbdqqsunu5Mm3wDvUAKRHSC34sJ7in334/*)",
           "combo("
           "xpub6FHa3pjLCk84BayeJxFW2SP4XRrFd1JYnxeLeU8EqN3vDfZmbqBqaGJAyiLjTAwm"
           "6ZLRQUMv1ZACTj37sR62cfN7fe5JnJ7dh8zL4fiyLHV/*)",
           RANGE,
           {{"2102df12b7035bdac8e3bab862a3a83d06ea6b17b6753d52edecba9be46f5d09e0"
             "76ac",
             "76a914f90e3178ca25f2c808dc76624032d352fdbdfaf288ac"},
            {"21032869a233c9adff9a994e4966e5b821fd5bac066da6c3112488dc52383b4a98"
             "ecac",
             "76a914a8409d1b6dfb1ed2a3e8aa5e0ef2ff26b15b75b788ac"}},
           {{0}, {1}});
 
     // Too long key fingerprint
     CheckUnparsable("combo([012345678]"
                     "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3x"
                     "z7iAxn8L39njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc)",
                     "combo([012345678]"
                     "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbm"
                     "JbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL)",
                     "Fingerprint is not 4 bytes (9 characters instead of 8 "
                     "characters)");
     // BIP 32 path element overflow
     CheckUnparsable(
         "pkh("
         "xprv9s21ZrQH143K31xYSDQpPDxsXRTUcvj2iNHm5NUtrGiGG5e2DtALGdso3pGz6ssrdK"
         "4PFmM8NSpSBHNqPqm55Qn3LqFtT2emdEXVYsCzC2U/2147483648)",
         "pkh("
         "xpub661MyMwAqRbcFW31YEwpkMuc5THy2PSt5bDMsktWQcFF8syAmRUapSCGu8ED9W6oDM"
         "Sgv6Zz8idoc4a6mr8BDzTJY47LJhkJ8UB7WEGuduB/2147483648)",
         "Key path value 2147483648 is out of range");
     // Path is not valid uint
     CheckUnparsable(
         "pkh("
         "xprv9s21ZrQH143K31xYSDQpPDxsXRTUcvj2iNHm5NUtrGiGG5e2DtALGdso3pGz6ssrdK"
         "4PFmM8NSpSBHNqPqm55Qn3LqFtT2emdEXVYsCzC2U/1aa)",
         "pkh("
         "xpub661MyMwAqRbcFW31YEwpkMuc5THy2PSt5bDMsktWQcFF8syAmRUapSCGu8ED9W6oDM"
         "Sgv6Zz8idoc4a6mr8BDzTJY47LJhkJ8UB7WEGuduB/1aa)",
         "Key path value '1aa' is not a valid uint32");
 
     // Multisig constructions
     Check("multi(1,L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1,"
           "5KYZdUEo39z3FPrtuX2QbbwGnNP5zTd7yyr2SC1j299sBCnWjss)",
           "multi(1,"
           "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd,"
           "04a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd5b"
           "8dec5235a0fa8722476c7709c02559e3aa73aa03918ba2d492eea75abea235)",
           SIGNABLE,
           {{"512103a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540"
             "c5bd4104a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c5"
             "40c5bd5b8dec5235a0fa8722476c7709c02559e3aa73aa03918ba2d492eea75abe"
             "a23552ae"}});
     Check("sortedmulti(1,L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1,"
           "5KYZdUEo39z3FPrtuX2QbbwGnNP5zTd7yyr2SC1j299sBCnWjss)",
           "sortedmulti(1,"
           "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd,"
           "04a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd5b"
           "8dec5235a0fa8722476c7709c02559e3aa73aa03918ba2d492eea75abea235)",
           SIGNABLE,
           {{"512103a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540"
             "c5bd4104a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c5"
             "40c5bd5b8dec5235a0fa8722476c7709c02559e3aa73aa03918ba2d492eea75abe"
             "a23552ae"}});
     Check("sortedmulti(1,5KYZdUEo39z3FPrtuX2QbbwGnNP5zTd7yyr2SC1j299sBCnWjss,"
           "L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1)",
           "sortedmulti(1,"
           "04a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd5b"
           "8dec5235a0fa8722476c7709c02559e3aa73aa03918ba2d492eea75abea235,"
           "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd)",
           SIGNABLE,
           {{"512103a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540"
             "c5bd4104a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c5"
             "40c5bd5b8dec5235a0fa8722476c7709c02559e3aa73aa03918ba2d492eea75abe"
             "a23552ae"}});
     Check("sh(multi(2,[00000000/111'/222]"
           "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39"
           "njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc,"
           "xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7"
           "AANYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))",
           "sh(multi(2,[00000000/111'/222]"
           "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4"
           "koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL,"
           "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHB"
           "aohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))",
           DEFAULT, {{"a91445a9a622a8b0a1269944be477640eedc447bbd8487"}},
           {{0x8000006FUL, 222}, {0}});
     Check("sortedmulti(2,"
           "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39"
           "njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc/"
           "*,"
           "xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7"
           "AANYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0/0/*)",
           "sortedmulti(2,"
           "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4"
           "koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL/"
           "*,"
           "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHB"
           "aohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0/0/*)",
           RANGE,
           {{"5221025d5fc65ebb8d44a5274b53bac21ff8307fec2334a32df05553459f8b1f7f"
             "e1b62102fbd47cc8034098f0e6a94c6aeee8528abf0a2153a5d8e46d325b7284c0"
             "46784652ae"},
            {"52210264fd4d1f5dea8ded94c61e9641309349b62f27fbffe807291f664e286bfb"
             "e6472103f4ece6dfccfa37b211eb3d0af4d0c61dba9ef698622dc17eecdf764bee"
             "b005a652ae"},
            {"5221022ccabda84c30bad578b13c89eb3b9544ce149787e5b538175b1d1ba259cb"
             "b83321024d902e1a2fc7a8755ab5b694c575fce742c48d9ff192e63df5193e4c7a"
             "fe1f9c52ae"}},
           {{0}, {1}, {2}, {0, 0, 0}, {0, 0, 1}, {0, 0, 2}});
     Check("sh(multi(2,"
           "xprv9s21ZrQH143K31xYSDQpPDxsXRTUcvj2iNHm5NUtrGiGG5e2DtALGdso3pGz6ssr"
           "dK4PFmM8NSpSBHNqPqm55Qn3LqFtT2emdEXVYsCzC2U/2147483647'/"
           "0,"
           "xprv9vHkqa6EV4sPZHYqZznhT2NPtPCjKuDKGY38FBWLvgaDx45zo9WQRUT3dKYnjwih"
           "2yJD9mkrocEZXo1ex8G81dwSM1fwqWpWkeS3v86pgKt/1/2/"
           "*,"
           "xprv9s21ZrQH143K3QTDL4LXw2F7HEK3wJUD2nW2nRk4stbPy6cq3jPPqjiChkVvvNKm"
           "PGJxWUtg6LnF5kejMRNNU3TGtRBeJgk33yuGBxrMPHi/10/20/30/40/*'))",
           "sh(multi(2,"
           "xpub661MyMwAqRbcFW31YEwpkMuc5THy2PSt5bDMsktWQcFF8syAmRUapSCGu8ED9W6o"
           "DMSgv6Zz8idoc4a6mr8BDzTJY47LJhkJ8UB7WEGuduB/2147483647'/"
           "0,"
           "xpub69H7F5d8KSRgmmdJg2KhpAK8SR3DjMwAdkxj3ZuxV27CprR9LgpeyGmXUbC6wb7E"
           "RfvrnKZjXoUmmDznezpbZb7ap6r1D3tgFxHmwMkQTPH/1/2/"
           "*,"
           "xpub661MyMwAqRbcFtXgS5sYJABqqG9YLmC4Q1Rdap9gSE8NqtwybGhePY2gZ29ESFjq"
           "JoCu1Rupje8YtGqsefD265TMg7usUDFdp6W1EGMcet8/10/20/30/40/*'))",
           HARDENED | RANGE,
           {{"a914261bbb58cd9714f92e91668d3eed7c4c860f4cdc87"},
            {"a914ff07ad97dc4458ed5236c52bb94ccb7339dedff887"},
            {"a91451f96613fdd66e75a026811ba4fdb9efec2c83a987"}},
           {{0xFFFFFFFFUL, 0},
            {1, 2, 0},
            {1, 2, 1},
            {1, 2, 2},
            {10, 20, 30, 40, 0x80000000UL},
            {10, 20, 30, 40, 0x80000001UL},
            {10, 20, 30, 40, 0x80000002UL}});
     // P2SH does not fit 16 compressed pubkeys in a redeemscript
     CheckUnparsable(
         "sh(multi(16,"
         "KzoAz5CanayRKex3fSLQ2BwJpN7U52gZvxMyk78nDMHuqrUxuSJy,"
         "KwGNz6YCCQtYvFzMtrC6D3tKTKdBBboMrLTsjr2NYVBwapCkn7Mr,"
         "KxogYhiNfwxuswvXV66eFyKcCpm7dZ7TqHVqujHAVUjJxyivxQ9X,"
         "L2BUNduTSyZwZjwNHynQTF14mv2uz2NRq5n5sYWTb4FkkmqgEE9f,"
         "L1okJGHGn1kFjdXHKxXjwVVtmCMR2JA5QsbKCSpSb7ReQjezKeoD,"
         "KxDCNSST75HFPaW5QKpzHtAyaCQC7p9Vo3FYfi2u4dXD1vgMiboK,"
         "L5edQjFtnkcf5UWURn6UuuoFrabgDQUHdheKCziwN42aLwS3KizU,"
         "KzF8UWFcEC7BYTq8Go1xVimMkDmyNYVmXV5PV7RuDicvAocoPB8i,"
         "L3nHUboKG2w4VSJ5jYZ5CBM97oeK6YuKvfZxrefdShECcjEYKMWZ,"
         "KyjHo36dWkYhimKmVVmQTq3gERv3pnqA4xFCpvUgbGDJad7eS8WE,"
         "KwsfyHKRUTZPQtysN7M3tZ4GXTnuov5XRgjdF2XCG8faAPmFruRF,"
         "KzCUbGhN9LJhdeFfL9zQgTJMjqxdBKEekRGZX24hXdgCNCijkkap,"
         "KzgpMBwwsDLwkaC5UrmBgCYaBD2WgZ7PBoGYXR8KT7gCA9UTN5a3,"
         "KyBXTPy4T7YG4q9tcAM3LkvfRpD1ybHMvcJ2ehaWXaSqeGUxEdkP,"
         "KzJDe9iwJRPtKP2F2AoN6zBgzS7uiuAwhWCfGdNeYJ3PC1HNJ8M8,"
         "L1xbHrxynrqLKkoYc4qtoQPx6uy5qYXR5ZDYVYBSRmCV5piU3JG9))",
         "sh(multi(16,"
         "03669b8afcec803a0d323e9a17f3ea8e68e8abe5a278020a929adbec52421adbd0,"
         "0260b2003c386519fc9eadf2b5cf124dd8eea4c4e68d5e154050a9346ea98ce600,"
         "0362a74e399c39ed5593852a30147f2959b56bb827dfa3e60e464b02ccf87dc5e8,"
         "0261345b53de74a4d721ef877c255429961b7e43714171ac06168d7e08c542a8b8,"
         "02da72e8b46901a65d4374fe6315538d8f368557dda3a1dcf9ea903f3afe7314c8,"
         "0318c82dd0b53fd3a932d16e0ba9e278fcc937c582d5781be626ff16e201f72286,"
         "0297ccef1ef99f9d73dec9ad37476ddb232f1238aff877af19e72ba04493361009,"
         "02e502cfd5c3f972fe9a3e2a18827820638f96b6f347e54d63deb839011fd5765d,"
         "03e687710f0e3ebe81c1037074da939d409c0025f17eb86adb9427d28f0f7ae0e9,"
         "02c04d3a5274952acdbc76987f3184b346a483d43be40874624b29e3692c1df5af,"
         "02ed06e0f418b5b43a7ec01d1d7d27290fa15f75771cb69b642a51471c29c84acd,"
         "036d46073cbb9ffee90473f3da429abc8de7f8751199da44485682a989a4bebb24,"
         "02f5d1ff7c9029a80a4e36b9a5497027ef7f3e73384a4a94fbfe7c4e9164eec8bc,"
         "02e41deffd1b7cce11cde209a781adcffdabd1b91c0ba0375857a2bfd9302419f3,"
         "02d76625f7956a7fc505ab02556c23ee72d832f1bac391bcd2d3abce5710a13d06,"
         "0399eb0a5487515802dc14544cf10b3666623762fbed2ec38a3975716e2c29c232))",
         "P2SH script is too large, 547 bytes is larger than 520 bytes");
     // Invalid threshold
     CheckUnparsable(
         "multi(a,L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1,"
         "5KYZdUEo39z3FPrtuX2QbbwGnNP5zTd7yyr2SC1j299sBCnWjss)",
         "multi(a,"
         "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd,"
         "04a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd5b8d"
         "ec5235a0fa8722476c7709c02559e3aa73aa03918ba2d492eea75abea235)",
         "Multi threshold 'a' is not valid");
     // Threshold of 0
     CheckUnparsable(
         "multi(0,L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1,"
         "5KYZdUEo39z3FPrtuX2QbbwGnNP5zTd7yyr2SC1j299sBCnWjss)",
         "multi(0,"
         "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd,"
         "04a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd5b8d"
         "ec5235a0fa8722476c7709c02559e3aa73aa03918ba2d492eea75abea235)",
         "Multisig threshold cannot be 0, must be at least 1");
     // Threshold larger than number of keys
     CheckUnparsable(
         "multi(3,L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1,"
         "5KYZdUEo39z3FPrtuX2QbbwGnNP5zTd7yyr2SC1j299sBCnWjss)",
         "multi(3,"
         "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd,"
         "04a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd5b8d"
         "ec5235a0fa8722476c7709c02559e3aa73aa03918ba2d492eea75abea235)",
         "Multisig threshold cannot be larger than the number of keys; "
         "threshold is 3 but only 2 keys specified");
     // Threshold larger than number of keys
     CheckUnparsable(
         "multi(3,KzoAz5CanayRKex3fSLQ2BwJpN7U52gZvxMyk78nDMHuqrUxuSJy,"
         "KwGNz6YCCQtYvFzMtrC6D3tKTKdBBboMrLTsjr2NYVBwapCkn7Mr,"
         "KxogYhiNfwxuswvXV66eFyKcCpm7dZ7TqHVqujHAVUjJxyivxQ9X,"
         "L2BUNduTSyZwZjwNHynQTF14mv2uz2NRq5n5sYWTb4FkkmqgEE9f)",
         "multi(3,"
         "03669b8afcec803a0d323e9a17f3ea8e68e8abe5a278020a929adbec52421adbd0,"
         "0260b2003c386519fc9eadf2b5cf124dd8eea4c4e68d5e154050a9346ea98ce600,"
         "0362a74e399c39ed5593852a30147f2959b56bb827dfa3e60e464b02ccf87dc5e8,"
         "0261345b53de74a4d721ef877c255429961b7e43714171ac06168d7e08c542a8b8)",
         "Cannot have 4 pubkeys in bare multisig; only at most 3 pubkeys");
     // Cannot have more than 16 keys in a multisig
     CheckUnparsable(
         "sh(multi(16,KzoAz5CanayRKex3fSLQ2BwJpN7U52gZvxMyk78nDMHuqrUxuSJy,"
         "KwGNz6YCCQtYvFzMtrC6D3tKTKdBBboMrLTsjr2NYVBwapCkn7Mr,"
         "KxogYhiNfwxuswvXV66eFyKcCpm7dZ7TqHVqujHAVUjJxyivxQ9X,"
         "L2BUNduTSyZwZjwNHynQTF14mv2uz2NRq5n5sYWTb4FkkmqgEE9f,"
         "L1okJGHGn1kFjdXHKxXjwVVtmCMR2JA5QsbKCSpSb7ReQjezKeoD,"
         "KxDCNSST75HFPaW5QKpzHtAyaCQC7p9Vo3FYfi2u4dXD1vgMiboK,"
         "L5edQjFtnkcf5UWURn6UuuoFrabgDQUHdheKCziwN42aLwS3KizU,"
         "KzF8UWFcEC7BYTq8Go1xVimMkDmyNYVmXV5PV7RuDicvAocoPB8i,"
         "L3nHUboKG2w4VSJ5jYZ5CBM97oeK6YuKvfZxrefdShECcjEYKMWZ,"
         "KyjHo36dWkYhimKmVVmQTq3gERv3pnqA4xFCpvUgbGDJad7eS8WE,"
         "KwsfyHKRUTZPQtysN7M3tZ4GXTnuov5XRgjdF2XCG8faAPmFruRF,"
         "KzCUbGhN9LJhdeFfL9zQgTJMjqxdBKEekRGZX24hXdgCNCijkkap,"
         "KzgpMBwwsDLwkaC5UrmBgCYaBD2WgZ7PBoGYXR8KT7gCA9UTN5a3,"
         "KyBXTPy4T7YG4q9tcAM3LkvfRpD1ybHMvcJ2ehaWXaSqeGUxEdkP,"
         "KzJDe9iwJRPtKP2F2AoN6zBgzS7uiuAwhWCfGdNeYJ3PC1HNJ8M8,"
         "L1xbHrxynrqLKkoYc4qtoQPx6uy5qYXR5ZDYVYBSRmCV5piU3JG9,"
         "L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1))",
         "sh(multi(16,"
         "03669b8afcec803a0d323e9a17f3ea8e68e8abe5a278020a929adbec52421adbd0,"
         "0260b2003c386519fc9eadf2b5cf124dd8eea4c4e68d5e154050a9346ea98ce600,"
         "0362a74e399c39ed5593852a30147f2959b56bb827dfa3e60e464b02ccf87dc5e8,"
         "0261345b53de74a4d721ef877c255429961b7e43714171ac06168d7e08c542a8b8,"
         "02da72e8b46901a65d4374fe6315538d8f368557dda3a1dcf9ea903f3afe7314c8,"
         "0318c82dd0b53fd3a932d16e0ba9e278fcc937c582d5781be626ff16e201f72286,"
         "0297ccef1ef99f9d73dec9ad37476ddb232f1238aff877af19e72ba04493361009,"
         "02e502cfd5c3f972fe9a3e2a18827820638f96b6f347e54d63deb839011fd5765d,"
         "03e687710f0e3ebe81c1037074da939d409c0025f17eb86adb9427d28f0f7ae0e9,"
         "02c04d3a5274952acdbc76987f3184b346a483d43be40874624b29e3692c1df5af,"
         "02ed06e0f418b5b43a7ec01d1d7d27290fa15f75771cb69b642a51471c29c84acd,"
         "036d46073cbb9ffee90473f3da429abc8de7f8751199da44485682a989a4bebb24,"
         "02f5d1ff7c9029a80a4e36b9a5497027ef7f3e73384a4a94fbfe7c4e9164eec8bc,"
         "02e41deffd1b7cce11cde209a781adcffdabd1b91c0ba0375857a2bfd9302419f3,"
         "02d76625f7956a7fc505ab02556c23ee72d832f1bac391bcd2d3abce5710a13d06,"
         "0399eb0a5487515802dc14544cf10b3666623762fbed2ec38a3975716e2c29c232,"
         "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd))",
         "Cannot have 17 keys in multisig; must have between 1 and 16 keys, "
         "inclusive");
 
     // Check for invalid nesting of structures
 
     // P2SH needs a script, not a key
     CheckUnparsable(
         "sh(L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1)",
         "sh("
         "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd)",
         "A function is needed within P2SH");
     // Old must be top level
     CheckUnparsable(
         "sh(combo("
         "L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1))",
         "sh(combo("
         "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd))",
         "Cannot have combo in non-top level");
     // Cannot embed P2SH inside P2SH
     CheckUnparsable(
         "sh(sh(pk(L4rK1yDtCWekvXuE6oXD9jCYfFNV2cWRpVuPLBcCU2z8TrisoyY1)))",
         "sh(sh(pk("
         "03a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd))"
         ")",
         "Cannot have sh in non-top level");
 
     // Checksums
     Check("sh(multi(2,[00000000/111'/"
           "222]"
           "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39"
           "njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc,"
           "xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7"
           "AANYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))#ggrsrxfy",
           "sh(multi(2,[00000000/111'/"
           "222]"
           "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4"
           "koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL,"
           "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHB"
           "aohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))#tjg09x5t",
           DEFAULT, {{"a91445a9a622a8b0a1269944be477640eedc447bbd8487"}},
           {{0x8000006FUL, 222}, {0}});
     Check("sh(multi(2,[00000000/111'/"
           "222]"
           "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39"
           "njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc,"
           "xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7"
           "AANYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))",
           "sh(multi(2,[00000000/111'/"
           "222]"
           "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4"
           "koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL,"
           "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHB"
           "aohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))",
           DEFAULT, {{"a91445a9a622a8b0a1269944be477640eedc447bbd8487"}},
           {{0x8000006FUL, 222}, {0}});
     // Empty checksum
     CheckUnparsable(
         "sh(multi(2,[00000000/111'/"
         "222]"
         "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39nj"
         "GVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc,"
         "xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AA"
         "NYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))#",
         "sh(multi(2,[00000000/111'/"
         "222]"
         "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4ko"
         "xb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL,"
         "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBao"
         "hPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))#",
         "Expected 8 character checksum, not 0 characters");
     // Too long checksum
     CheckUnparsable(
         "sh(multi(2,[00000000/111'/"
         "222]"
         "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39nj"
         "GVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc,"
         "xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AA"
         "NYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))#ggrsrxfyq",
         "sh(multi(2,[00000000/111'/"
         "222]"
         "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4ko"
         "xb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL,"
         "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBao"
         "hPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))#tjg09x5tq",
         "Expected 8 character checksum, not 9 characters");
     // Too short checksum
     CheckUnparsable(
         "sh(multi(2,[00000000/111'/"
         "222]"
         "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39nj"
         "GVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc,"
         "xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AA"
         "NYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))#ggrsrxf",
         "sh(multi(2,[00000000/111'/"
         "222]"
         "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4ko"
         "xb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL,"
         "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBao"
         "hPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))#tjg09x5",
         "Expected 8 character checksum, not 7 characters");
     // Error in payload
     CheckUnparsable(
         "sh(multi(3,[00000000/111'/"
         "222]"
         "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39nj"
         "GVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc,"
         "xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AA"
         "NYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))#ggrsrxfy",
         "sh(multi(3,[00000000/111'/"
         "222]"
         "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4ko"
         "xb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL,"
         "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBao"
         "hPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))#tjg09x5t",
         "Provided checksum 'tjg09x5t' does not match computed checksum "
         "'d4x0uxyv'");
     // Error in checksum
     CheckUnparsable(
         "sh(multi(2,[00000000/111'/"
         "222]"
         "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39nj"
         "GVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc,"
         "xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AA"
         "NYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))#ggssrxfy",
         "sh(multi(2,[00000000/111'/"
         "222]"
         "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4ko"
         "xb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL,"
         "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBao"
         "hPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))#tjq09x4t",
         "Provided checksum 'tjq09x4t' does not match computed checksum "
         "'tjg09x5t'");
     // Error in checksum
     CheckUnparsable(
         "sh(multi(2,[00000000/111'/"
         "222]"
         "xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39nj"
         "GVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc,"
         "xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AA"
         "NYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))##ggssrxfy",
         "sh(multi(2,[00000000/111'/"
         "222]"
         "xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4ko"
         "xb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL,"
         "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBao"
         "hPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))##tjq09x4t",
         "Multiple '#' symbols");
 
     // Addr and raw tests
     // Invalid address
     CheckUnparsable("", "addr(asdf)", "Address is not valid");
     // Invalid script
     CheckUnparsable("", "raw(asdf)", "Raw script is not hex");
     // Invalid chars
     CheckUnparsable("", "raw(Ü)#00000000", "Invalid characters in payload");
 }
 
 BOOST_AUTO_TEST_SUITE_END()