diff options
Diffstat (limited to 'src/script/descriptor.cpp')
| -rw-r--r-- | src/script/descriptor.cpp | 566 |
1 files changed, 566 insertions, 0 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; +} |