Merge #13697: Support output descriptors in scantxoutset

f6b7fc349ccf9cfbeb7e91e19c20e2a2fcc9026f Support h instead of ' in hardened descriptor paths (Pieter Wuille)
fddea672eb8f63012f2e9ce04fa477e5d4140750 Add experimental warning to scantxoutset (Jonas Schnelli)
6495849bfd362d6a2f128bac5982fa9e3e2e3396 [QA] Extend tests to more combinations (Pieter Wuille)
1af237faefc316bd708e25d6901ee6f17b706e57 [QA] Add xpub range tests in scantxoutset tests (Jonas Schnelli)
151600bb4972f7bab4ed4a03d1f67c38e081fefe Swap in descriptors support into scantxoutset (Pieter Wuille)
0652c3284fe12941b28624dbbf5e0862c5d0dbc3 Descriptor tests (Pieter Wuille)
fe8a7dcd78cfeedc9a7c705e91384f793822912b Output descriptors module (Pieter Wuille)
e54d76044b3a2c625e53f2116c5f6a7c40105d5d Add simple FlatSigningProvider (Pieter Wuille)
29943a904a11607787d28b1f4288f500bd076dde Add more methods to Span class (Pieter Wuille)

Pull request description:

  As promised, here is an implementation of my output descriptor concept (https://gist.github.com/sipa/e3d23d498c430bb601c5bca83523fa82) and integration within the `scantxoutset` RPC that was just added through #12196.

  It changes the RPC to use descriptors for everything; I hope the interface is simple enough to encompass all use cases. It includes support for P2PK, P2PKH, P2WPKH, P2SH, P2WSH, multisig, xpubs, xprvs, and chains of keys - combined in every possible way.

Tree-SHA512: 63b54a96e7a72f5b04a8d645b8517d43ecd6a65a41f9f4e593931ce725a8845ab0baa1e9db6a7243190d8ac841f6e7e2f520d98c539312d78f7fd687d2c7b88f

4 files changed, 709 insertions, 2 deletions

diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp
new file mode 100644
index 0000000000..f366b99ec3
--- /dev/null
+++ b/src/script/descriptor.cpp
@@ -0,0 +1,566 @@
+// 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 <key_io.h>
+#include <pubkey.h>
+#include <script/script.h>
+#include <script/standard.h>
+
+#include <span.h>
+#include <util.h>
+#include <utilstrencodings.h>
+
+#include <memory>
+#include <string>
+#include <vector>
+
+namespace {
+
+////////////////////////////////////////////////////////////////////////////
+// Internal representation                                                //
+////////////////////////////////////////////////////////////////////////////
+
+typedef std::vector<uint32_t> KeyPath;
+
+std::string FormatKeyPath(const KeyPath& path)
+{
+    std::string ret;
+    for (auto i : path) {
+        ret += strprintf("/%i", (i << 1) >> 1);
+        if (i >> 31) ret += '\'';
+    }
+    return ret;
+}
+
+/** Interface for public key objects in descriptors. */
+struct PubkeyProvider
+{
+    virtual ~PubkeyProvider() = default;
+
+    /** Derive a public key. */
+    virtual bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& out) 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;
+};
+
+/** An object representing a parsed constant public key in a descriptor. */
+class ConstPubkeyProvider final : public PubkeyProvider
+{
+    CPubKey m_pubkey;
+
+public:
+    ConstPubkeyProvider(const CPubKey& pubkey) : m_pubkey(pubkey) {}
+    bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& out) const override
+    {
+        out = m_pubkey;
+        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;
+    }
+};
+
+enum class DeriveType {
+    NO,
+    UNHARDENED,
+    HARDENED,
+};
+
+/** An object representing a parsed extended public key in a descriptor. */
+class BIP32PubkeyProvider final : public PubkeyProvider
+{
+    CExtPubKey m_extkey;
+    KeyPath m_path;
+    DeriveType m_derive;
+
+    bool GetExtKey(const SigningProvider& arg, CExtKey& ret) const
+    {
+        CKey key;
+        if (!arg.GetKey(m_extkey.pubkey.GetID(), key)) return false;
+        ret.nDepth = m_extkey.nDepth;
+        std::copy(m_extkey.vchFingerprint, m_extkey.vchFingerprint + 4, ret.vchFingerprint);
+        ret.nChild = m_extkey.nChild;
+        ret.chaincode = m_extkey.chaincode;
+        ret.key = key;
+        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(const CExtPubKey& extkey, KeyPath path, DeriveType derive) : m_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& out) const override
+    {
+        if (IsHardened()) {
+            CExtKey key;
+            if (!GetExtKey(arg, key)) return false;
+            for (auto entry : m_path) {
+                key.Derive(key, entry);
+            }
+            if (m_derive == DeriveType::UNHARDENED) key.Derive(key, pos);
+            if (m_derive == DeriveType::HARDENED) key.Derive(key, pos | 0x80000000UL);
+            out = key.Neuter().pubkey;
+        } else {
+            // TODO: optimize by caching
+            CExtPubKey key = m_extkey;
+            for (auto entry : m_path) {
+                key.Derive(key, entry);
+            }
+            if (m_derive == DeriveType::UNHARDENED) key.Derive(key, pos);
+            assert(m_derive != DeriveType::HARDENED);
+            out = key.pubkey;
+        }
+        return true;
+    }
+    std::string ToString() const override
+    {
+        std::string ret = EncodeExtPubKey(m_extkey) + FormatKeyPath(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) + FormatKeyPath(m_path);
+        if (IsRange()) {
+            out += "/*";
+            if (m_derive == DeriveType::HARDENED) out += '\'';
+        }
+        return true;
+    }
+};
+
+/** A parsed addr(A) descriptor. */
+class AddressDescriptor final : public Descriptor
+{
+    CTxDestination m_destination;
+
+public:
+    AddressDescriptor(CTxDestination destination) : m_destination(std::move(destination)) {}
+
+    bool IsRange() const override { return false; }
+    std::string ToString() const override { return "addr(" + EncodeDestination(m_destination) + ")"; }
+    bool ToPrivateString(const SigningProvider& arg, std::string& out) const override { out = ToString(); return true; }
+    bool Expand(int pos, const SigningProvider& arg, std::vector<CScript>& output_scripts, FlatSigningProvider& out) const override
+    {
+        output_scripts = std::vector<CScript>{GetScriptForDestination(m_destination)};
+        return true;
+    }
+};
+
+/** A parsed raw(H) descriptor. */
+class RawDescriptor final : public Descriptor
+{
+    CScript m_script;
+
+public:
+    RawDescriptor(CScript script) : m_script(std::move(script)) {}
+
+    bool IsRange() const override { return false; }
+    std::string ToString() const override { return "raw(" + HexStr(m_script.begin(), m_script.end()) + ")"; }
+    bool ToPrivateString(const SigningProvider& arg, std::string& out) const override { out = ToString(); return true; }
+    bool Expand(int pos, const SigningProvider& arg, std::vector<CScript>& output_scripts, FlatSigningProvider& out) const override
+    {
+        output_scripts = std::vector<CScript>{m_script};
+        return true;
+    }
+};
+
+/** A parsed pk(P), pkh(P), or wpkh(P) descriptor. */
+class SingleKeyDescriptor final : public Descriptor
+{
+    const std::function<CScript(const CPubKey&)> m_script_fn;
+    const std::string m_fn_name;
+    std::unique_ptr<PubkeyProvider> m_provider;
+
+public:
+    SingleKeyDescriptor(std::unique_ptr<PubkeyProvider> prov, const std::function<CScript(const CPubKey&)>& fn, const std::string& name) : m_script_fn(fn), m_fn_name(name), m_provider(std::move(prov)) {}
+
+    bool IsRange() const override { return m_provider->IsRange(); }
+    std::string ToString() const override { return m_fn_name + "(" + m_provider->ToString() + ")"; }
+    bool ToPrivateString(const SigningProvider& arg, std::string& out) const override
+    {
+        std::string ret;
+        if (!m_provider->ToPrivateString(arg, ret)) return false;
+        out = m_fn_name + "(" + std::move(ret) + ")";
+        return true;
+    }
+    bool Expand(int pos, const SigningProvider& arg, std::vector<CScript>& output_scripts, FlatSigningProvider& out) const override
+    {
+        CPubKey key;
+        if (!m_provider->GetPubKey(pos, arg, key)) return false;
+        output_scripts = std::vector<CScript>{m_script_fn(key)};
+        out.pubkeys.emplace(key.GetID(), std::move(key));
+        return true;
+    }
+};
+
+CScript P2PKHGetScript(const CPubKey& pubkey) { return GetScriptForDestination(pubkey.GetID()); }
+CScript P2PKGetScript(const CPubKey& pubkey) { return GetScriptForRawPubKey(pubkey); }
+CScript P2WPKHGetScript(const CPubKey& pubkey) { return GetScriptForDestination(WitnessV0KeyHash(pubkey.GetID())); }
+
+/** A parsed multi(...) descriptor. */
+class MultisigDescriptor : public Descriptor
+{
+    int m_threshold;
+    std::vector<std::unique_ptr<PubkeyProvider>> m_providers;
+
+public:
+    MultisigDescriptor(int threshold, std::vector<std::unique_ptr<PubkeyProvider>> providers) : m_threshold(threshold), m_providers(std::move(providers)) {}
+
+    bool IsRange() const override
+    {
+        for (const auto& p : m_providers) {
+            if (p->IsRange()) return true;
+        }
+        return false;
+    }
+
+    std::string ToString() const override
+    {
+        std::string ret = strprintf("multi(%i", m_threshold);
+        for (const auto& p : m_providers) {
+            ret += "," + p->ToString();
+        }
+        return std::move(ret) + ")";
+    }
+
+    bool ToPrivateString(const SigningProvider& arg, std::string& out) const override
+    {
+        std::string ret = strprintf("multi(%i", m_threshold);
+        for (const auto& p : m_providers) {
+            std::string sub;
+            if (!p->ToPrivateString(arg, sub)) return false;
+            ret += "," + std::move(sub);
+        }
+        out = std::move(ret) + ")";
+        return true;
+    }
+
+    bool Expand(int pos, const SigningProvider& arg, std::vector<CScript>& output_scripts, FlatSigningProvider& out) const override
+    {
+        std::vector<CPubKey> pubkeys;
+        pubkeys.reserve(m_providers.size());
+        for (const auto& p : m_providers) {
+            CPubKey key;
+            if (!p->GetPubKey(pos, arg, key)) return false;
+            pubkeys.push_back(key);
+        }
+        for (const CPubKey& key : pubkeys) {
+            out.pubkeys.emplace(key.GetID(), std::move(key));
+        }
+        output_scripts = std::vector<CScript>{GetScriptForMultisig(m_threshold, pubkeys)};
+        return true;
+    }
+};
+
+/** A parsed sh(S) or wsh(S) descriptor. */
+class ConvertorDescriptor : public Descriptor
+{
+    const std::function<CScript(const CScript&)> m_convert_fn;
+    const std::string m_fn_name;
+    std::unique_ptr<Descriptor> m_descriptor;
+
+public:
+    ConvertorDescriptor(std::unique_ptr<Descriptor> descriptor, const std::function<CScript(const CScript&)>& fn, const std::string& name) : m_convert_fn(fn), m_fn_name(name), m_descriptor(std::move(descriptor)) {}
+
+    bool IsRange() const override { return m_descriptor->IsRange(); }
+    std::string ToString() const override { return m_fn_name + "(" + m_descriptor->ToString() + ")"; }
+    bool ToPrivateString(const SigningProvider& arg, std::string& out) const override
+    {
+        std::string ret;
+        if (!m_descriptor->ToPrivateString(arg, ret)) return false;
+        out = m_fn_name + "(" + std::move(ret) + ")";
+        return true;
+    }
+    bool Expand(int pos, const SigningProvider& arg, std::vector<CScript>& output_scripts, FlatSigningProvider& out) const override
+    {
+        std::vector<CScript> sub;
+        if (!m_descriptor->Expand(pos, arg, sub, out)) return false;
+        output_scripts.clear();
+        for (const auto& script : sub) {
+            CScriptID id(script);
+            out.scripts.emplace(CScriptID(script), script);
+            output_scripts.push_back(m_convert_fn(script));
+        }
+        return true;
+    }
+};
+
+CScript ConvertP2SH(const CScript& script) { return GetScriptForDestination(CScriptID(script)); }
+CScript ConvertP2WSH(const CScript& script) { return GetScriptForDestination(WitnessV0ScriptHash(script)); }
+
+/** A parsed combo(P) descriptor. */
+class ComboDescriptor final : public Descriptor
+{
+    std::unique_ptr<PubkeyProvider> m_provider;
+
+public:
+    ComboDescriptor(std::unique_ptr<PubkeyProvider> provider) : m_provider(std::move(provider)) {}
+
+    bool IsRange() const override { return m_provider->IsRange(); }
+    std::string ToString() const override { return "combo(" + m_provider->ToString() + ")"; }
+    bool ToPrivateString(const SigningProvider& arg, std::string& out) const override
+    {
+        std::string ret;
+        if (!m_provider->ToPrivateString(arg, ret)) return false;
+        out = "combo(" + std::move(ret) + ")";
+        return true;
+    }
+    bool Expand(int pos, const SigningProvider& arg, std::vector<CScript>& output_scripts, FlatSigningProvider& out) const override
+    {
+        CPubKey key;
+        if (!m_provider->GetPubKey(pos, arg, key)) return false;
+        CKeyID keyid = key.GetID();
+        {
+            CScript p2pk = GetScriptForRawPubKey(key);
+            CScript p2pkh = GetScriptForDestination(keyid);
+            output_scripts = std::vector<CScript>{std::move(p2pk), std::move(p2pkh)};
+            out.pubkeys.emplace(keyid, key);
+        }
+        if (key.IsCompressed()) {
+            CScript p2wpkh = GetScriptForDestination(WitnessV0KeyHash(keyid));
+            CScriptID p2wpkh_id(p2wpkh);
+            CScript p2sh_p2wpkh = GetScriptForDestination(p2wpkh_id);
+            out.scripts.emplace(p2wpkh_id, p2wpkh);
+            output_scripts.push_back(std::move(p2wpkh));
+            output_scripts.push_back(std::move(p2sh_p2wpkh));
+        }
+        return true;
+    }
+};
+
+////////////////////////////////////////////////////////////////////////////
+// Parser                                                                 //
+////////////////////////////////////////////////////////////////////////////
+
+enum class ParseScriptContext {
+    TOP,
+    P2SH,
+    P2WSH,
+};
+
+/** Parse a constant. If succesful, sp is updated to skip the constant and return true. */
+bool Const(const std::string& str, Span<const char>& sp)
+{
+    if ((size_t)sp.size() >= str.size() && std::equal(str.begin(), str.end(), sp.begin())) {
+        sp = sp.subspan(str.size());
+        return true;
+    }
+    return false;
+}
+
+/** Parse a function call. If succesful, sp is updated to be the function's argument(s). */
+bool Func(const std::string& str, Span<const char>& sp)
+{
+    if ((size_t)sp.size() >= str.size() + 2 && sp[str.size()] == '(' && sp[sp.size() - 1] == ')' && std::equal(str.begin(), str.end(), sp.begin())) {
+        sp = sp.subspan(str.size() + 1, sp.size() - str.size() - 2);
+        return true;
+    }
+    return false;
+}
+
+/** Return the expression that sp begins with, and update sp to skip it. */
+Span<const char> Expr(Span<const char>& sp)
+{
+    int level = 0;
+    auto it = sp.begin();
+    while (it != sp.end()) {
+        if (*it == '(') {
+            ++level;
+        } else if (level && *it == ')') {
+            --level;
+        } else if (level == 0 && (*it == ')' || *it == ',')) {
+            break;
+        }
+        ++it;
+    }
+    Span<const char> ret = sp.first(it - sp.begin());
+    sp = sp.subspan(it - sp.begin());
+    return ret;
+}
+
+/** Split a string on every instance of sep, returning a vector. */
+std::vector<Span<const char>> Split(const Span<const char>& sp, char sep)
+{
+    std::vector<Span<const char>> ret;
+    auto it = sp.begin();
+    auto start = it;
+    while (it != sp.end()) {
+        if (*it == sep) {
+            ret.emplace_back(start, it);
+            start = it + 1;
+        }
+        ++it;
+    }
+    ret.emplace_back(start, it);
+    return ret;
+}
+
+/** Parse a key path, being passed a split list of elements (the first element is ignored). */
+bool ParseKeyPath(const std::vector<Span<const char>>& split, KeyPath& out)
+{
+    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) || p > 0x7FFFFFFFUL) return false;
+        out.push_back(p | (((uint32_t)hardened) << 31));
+    }
+    return true;
+}
+
+std::unique_ptr<PubkeyProvider> ParsePubkey(const Span<const char>& sp, bool permit_uncompressed, FlatSigningProvider& out)
+{
+    auto split = Split(sp, '/');
+    std::string str(split[0].begin(), split[0].end());
+    if (split.size() == 1) {
+        if (IsHex(str)) {
+            std::vector<unsigned char> data = ParseHex(str);
+            CPubKey pubkey(data);
+            if (pubkey.IsFullyValid() && (permit_uncompressed || pubkey.IsCompressed())) return MakeUnique<ConstPubkeyProvider>(pubkey);
+        }
+        CKey key = DecodeSecret(str);
+        if (key.IsValid() && (permit_uncompressed || key.IsCompressed())) {
+            CPubKey pubkey = key.GetPubKey();
+            out.keys.emplace(pubkey.GetID(), key);
+            return MakeUnique<ConstPubkeyProvider>(pubkey);
+        }
+    }
+    CExtKey extkey = DecodeExtKey(str);
+    CExtPubKey extpubkey = DecodeExtPubKey(str);
+    if (!extkey.key.IsValid() && !extpubkey.pubkey.IsValid()) 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)) return nullptr;
+    if (extkey.key.IsValid()) {
+        extpubkey = extkey.Neuter();
+        out.keys.emplace(extpubkey.pubkey.GetID(), extkey.key);
+    }
+    return MakeUnique<BIP32PubkeyProvider>(extpubkey, std::move(path), type);
+}
+
+/** Parse a script in a particular context. */
+std::unique_ptr<Descriptor> ParseScript(Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out)
+{
+    auto expr = Expr(sp);
+    if (Func("pk", expr)) {
+        auto pubkey = ParsePubkey(expr, ctx != ParseScriptContext::P2WSH, out);
+        if (!pubkey) return nullptr;
+        return MakeUnique<SingleKeyDescriptor>(std::move(pubkey), P2PKGetScript, "pk");
+    }
+    if (Func("pkh", expr)) {
+        auto pubkey = ParsePubkey(expr, ctx != ParseScriptContext::P2WSH, out);
+        if (!pubkey) return nullptr;
+        return MakeUnique<SingleKeyDescriptor>(std::move(pubkey), P2PKHGetScript, "pkh");
+    }
+    if (ctx == ParseScriptContext::TOP && Func("combo", expr)) {
+        auto pubkey = ParsePubkey(expr, true, out);
+        if (!pubkey) return nullptr;
+        return MakeUnique<ComboDescriptor>(std::move(pubkey));
+    }
+    if (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)) return nullptr;
+        size_t script_size = 0;
+        while (expr.size()) {
+            if (!Const(",", expr)) return nullptr;
+            auto arg = Expr(expr);
+            auto pk = ParsePubkey(arg, ctx != ParseScriptContext::P2WSH, out);
+            if (!pk) return nullptr;
+            script_size += pk->GetSize() + 1;
+            providers.emplace_back(std::move(pk));
+        }
+        if (providers.size() < 1 || providers.size() > 16 || thres < 1 || thres > providers.size()) return nullptr;
+        if (ctx == ParseScriptContext::TOP) {
+            if (providers.size() > 3) return nullptr; // Not more than 3 pubkeys for raw multisig
+        }
+        if (ctx == ParseScriptContext::P2SH) {
+            if (script_size + 3 > 520) return nullptr; // Enforce P2SH script size limit
+        }
+        return MakeUnique<MultisigDescriptor>(thres, std::move(providers));
+    }
+    if (ctx != ParseScriptContext::P2WSH && Func("wpkh", expr)) {
+        auto pubkey = ParsePubkey(expr, false, out);
+        if (!pubkey) return nullptr;
+        return MakeUnique<SingleKeyDescriptor>(std::move(pubkey), P2WPKHGetScript, "wpkh");
+    }
+    if (ctx == ParseScriptContext::TOP && Func("sh", expr)) {
+        auto desc = ParseScript(expr, ParseScriptContext::P2SH, out);
+        if (!desc || expr.size()) return nullptr;
+        return MakeUnique<ConvertorDescriptor>(std::move(desc), ConvertP2SH, "sh");
+    }
+    if (ctx != ParseScriptContext::P2WSH && Func("wsh", expr)) {
+        auto desc = ParseScript(expr, ParseScriptContext::P2WSH, out);
+        if (!desc || expr.size()) return nullptr;
+        return MakeUnique<ConvertorDescriptor>(std::move(desc), ConvertP2WSH, "wsh");
+    }
+    if (ctx == ParseScriptContext::TOP && Func("addr", expr)) {
+        CTxDestination dest = DecodeDestination(std::string(expr.begin(), expr.end()));
+        if (!IsValidDestination(dest)) return nullptr;
+        return MakeUnique<AddressDescriptor>(std::move(dest));
+    }
+    if (ctx == ParseScriptContext::TOP && Func("raw", expr)) {
+        std::string str(expr.begin(), expr.end());
+        if (!IsHex(str)) return nullptr;
+        auto bytes = ParseHex(str);
+        return MakeUnique<RawDescriptor>(CScript(bytes.begin(), bytes.end()));
+    }
+    return nullptr;
+}
+
+} // namespace
+
+std::unique_ptr<Descriptor> Parse(const std::string& descriptor, FlatSigningProvider& out)
+{
+    Span<const char> sp(descriptor.data(), descriptor.size());
+    auto ret = ParseScript(sp, ParseScriptContext::TOP, out);
+    if (sp.size() == 0 && ret) return ret;
+    return nullptr;
+}
diff --git a/src/script/descriptor.h b/src/script/descriptor.h
new file mode 100644
index 0000000000..e079c72e92
--- /dev/null
+++ b/src/script/descriptor.h
@@ -0,0 +1,102 @@
+// 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 <vector>
+
+// 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.
+//
+// 1. Examples
+//
+// A P2PK descriptor with a fixed public key:
+// - pk(0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798)
+//
+// A P2SH-P2WSH-P2PKH descriptor with a fixed public key:
+// - sh(wsh(pkh(02e493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13)))
+//
+// A bare 1-of-2 multisig descriptor:
+// - multi(1,022f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4,025cbdf0646e5db4eaa398f365f2ea7a0e3d419b7e0330e39ce92bddedcac4f9bc)
+//
+// A chain of P2PKH outputs (this needs the corresponding private key to derive):
+// - pkh(xpub68Gmy5EdvgibQVfPdqkBBCHxA5htiqg55crXYuXoQRKfDBFA1WEjWgP6LHhwBZeNK1VTsfTFUHCdrfp1bgwQ9xv5ski8PX9rL2dZXvgGDnw/1'/2/*)
+//
+// 2. Grammar description:
+//
+// X: xpub or xprv encoded extended key
+// I: decimal encoded integer
+// H: Hex encoded byte array
+// A: Address in P2PKH, P2SH, or Bech32 encoding
+//
+// S (Scripts):
+// * pk(P): Pay-to-pubkey (P2PK) output for public key P.
+// * pkh(P): Pay-to-pubkey-hash (P2PKH) output for public key P.
+// * wpkh(P): Pay-to-witness-pubkey-hash (P2WPKH) output for public key P.
+// * sh(S): Pay-to-script-hash (P2SH) output for script S
+// * wsh(S): Pay-to-witness-script-hash (P2WSH) output for script S
+// * combo(P): combination of P2PK, P2PKH, P2WPKH, and P2SH-P2WPKH for public key P.
+// * multi(I,L): k-of-n multisig for given public keys
+// * addr(A): Output to address
+// * raw(H): scriptPubKey with raw bytes
+//
+// P (Public keys):
+// * H: fixed public key (or WIF-encoded private key)
+// * E: extended public key
+// * E/*: (ranged) all unhardened direct children of an extended public key
+// * E/*': (ranged) all hardened direct children of an extended public key
+//
+// L (Comma-separated lists of public keys):
+// * P
+// * L,P
+//
+// E (Extended public keys):
+// * X
+// * E/I: unhardened child
+// * E/I': hardened child
+// * E/Ih: hardened child (alternative notation)
+//
+// The top level is S.
+
+/** Interface for parsed descriptor objects. */
+struct Descriptor {
+    virtual ~Descriptor() = default;
+
+    /** Whether the expansion of this descriptor depends on the position. */
+    virtual bool IsRange() 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.
+     *
+     * pos: the position at which to expand the descriptor. If IsRange() is false, this is ignored.
+     * provider: the provider to query for private keys in case of hardened derivation.
+     * output_script: the expanded scriptPubKeys will be put here.
+     * out: scripts and public keys necessary for solving the expanded scriptPubKeys will be put here (may be equal to provider).
+     */
+    virtual bool Expand(int pos, const SigningProvider& provider, std::vector<CScript>& output_scripts, FlatSigningProvider& out) const = 0;
+};
+
+/** Parse a descriptor string. Included private keys are put in out. Returns nullptr if parsing fails. */
+std::unique_ptr<Descriptor> Parse(const std::string& descriptor, FlatSigningProvider& out);
+
+#endif // BITCOIN_SCRIPT_DESCRIPTOR_H
+
diff --git a/src/script/sign.cpp b/src/script/sign.cpp
index d10b1c4fd7..fa09adbaf8 100644
--- a/src/script/sign.cpp
+++ b/src/script/sign.cpp
@@ -11,7 +11,6 @@
 #include <script/standard.h>
 #include <uint256.h>
 
-
 typedef std::vector<unsigned char> valtype;
 
 MutableTransactionSignatureCreator::MutableTransactionSignatureCreator(const CMutableTransaction* txToIn, unsigned int nInIn, const CAmount& amountIn, int nHashTypeIn) : txTo(txToIn), nIn(nInIn), nHashType(nHashTypeIn), amount(amountIn), checker(txTo, nIn, amountIn) {}
@@ -437,6 +436,18 @@ public:
         return true;
     }
 };
+
+template<typename M, typename K, typename V>
+bool LookupHelper(const M& map, const K& key, V& value)
+{
+    auto it = map.find(key);
+    if (it != map.end()) {
+        value = it->second;
+        return true;
+    }
+    return false;
+}
+
 }
 
 const BaseSignatureCreator& DUMMY_SIGNATURE_CREATOR = DummySignatureCreator();
@@ -460,7 +471,6 @@ bool IsSolvable(const SigningProvider& provider, const CScript& script)
     return false;
 }
 
-
 bool PartiallySignedTransaction::IsNull() const
 {
     return !tx && inputs.empty() && outputs.empty() && unknown.empty();
@@ -618,3 +628,19 @@ bool PublicOnlySigningProvider::GetPubKey(const CKeyID &address, CPubKey& pubkey
 {
     return m_provider->GetPubKey(address, pubkey);
 }
+
+bool FlatSigningProvider::GetCScript(const CScriptID& scriptid, CScript& script) const { return LookupHelper(scripts, scriptid, script); }
+bool FlatSigningProvider::GetPubKey(const CKeyID& keyid, CPubKey& pubkey) const { return LookupHelper(pubkeys, keyid, pubkey); }
+bool FlatSigningProvider::GetKey(const CKeyID& keyid, CKey& key) const { return LookupHelper(keys, keyid, key); }
+
+FlatSigningProvider Merge(const FlatSigningProvider& a, const FlatSigningProvider& b)
+{
+    FlatSigningProvider ret;
+    ret.scripts = a.scripts;
+    ret.scripts.insert(b.scripts.begin(), b.scripts.end());
+    ret.pubkeys = a.pubkeys;
+    ret.pubkeys.insert(b.pubkeys.begin(), b.pubkeys.end());
+    ret.keys = a.keys;
+    ret.keys.insert(b.keys.begin(), b.keys.end());
+    return ret;
+}
diff --git a/src/script/sign.h b/src/script/sign.h
index d12d0b5874..96ef59fbe8 100644
--- a/src/script/sign.h
+++ b/src/script/sign.h
@@ -43,6 +43,19 @@ public:
     bool GetPubKey(const CKeyID &address, CPubKey& pubkey) const;
 };
 
+struct FlatSigningProvider final : public SigningProvider
+{
+    std::map<CScriptID, CScript> scripts;
+    std::map<CKeyID, CPubKey> pubkeys;
+    std::map<CKeyID, CKey> keys;
+
+    bool GetCScript(const CScriptID& scriptid, CScript& script) const override;
+    bool GetPubKey(const CKeyID& keyid, CPubKey& pubkey) const override;
+    bool GetKey(const CKeyID& keyid, CKey& key) const override;
+};
+
+FlatSigningProvider Merge(const FlatSigningProvider& a, const FlatSigningProvider& b);
+
 /** Interface for signature creators. */
 class BaseSignatureCreator {
 public: