diff options
Diffstat (limited to 'src/script')
| -rw-r--r-- | src/script/descriptor.cpp | 308 | ||||
| -rw-r--r-- | src/script/descriptor.h | 78 | ||||
| -rw-r--r-- | src/script/interpreter.cpp | 132 | ||||
| -rw-r--r-- | src/script/interpreter.h | 2 | ||||
| -rw-r--r-- | src/script/script.cpp | 2 | ||||
| -rw-r--r-- | src/script/script.h | 2 | ||||
| -rw-r--r-- | src/script/sigcache.cpp | 2 | ||||
| -rw-r--r-- | src/script/sign.cpp | 62 | ||||
| -rw-r--r-- | src/script/sign.h | 8 | ||||
| -rw-r--r-- | src/script/signingprovider.h | 50 | ||||
| -rw-r--r-- | src/script/standard.cpp | 10 | ||||
| -rw-r--r-- | src/script/standard.h | 9 |
12 files changed, 508 insertions, 157 deletions
diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp index 4b27ef0ca..83dc046ca 100644 --- a/src/script/descriptor.cpp +++ b/src/script/descriptor.cpp @@ -1,4 +1,4 @@ -// Copyright (c) 2018 The Bitcoin Core developers +// 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. @@ -36,7 +36,7 @@ namespace { // 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 unparseable descriptor. +// 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. @@ -150,10 +150,22 @@ 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) = 0; /** Whether this represent multiple public keys at different positions. */ virtual bool IsRange() const = 0; @@ -182,10 +194,10 @@ class OriginPubkeyProvider final : public PubkeyProvider } public: - OriginPubkeyProvider(KeyOriginInfo info, std::unique_ptr<PubkeyProvider> provider) : m_origin(std::move(info)), m_provider(std::move(provider)) {} - bool GetPubKey(int pos, const SigningProvider& arg, CPubKey* key, KeyOriginInfo& info) const override + 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 DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) override { - if (!m_provider->GetPubKey(pos, arg, key, info)) return false; + 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; @@ -212,10 +224,10 @@ class ConstPubkeyProvider final : public PubkeyProvider CPubKey m_pubkey; public: - ConstPubkeyProvider(const CPubKey& pubkey) : m_pubkey(pubkey) {} - bool GetPubKey(int pos, const SigningProvider& arg, CPubKey* key, KeyOriginInfo& info) const override + 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 DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) override { - if (key) *key = m_pubkey; + key = m_pubkey; info.path.clear(); CKeyID keyid = m_pubkey.GetID(); std::copy(keyid.begin(), keyid.begin() + sizeof(info.fingerprint), info.fingerprint); @@ -246,22 +258,36 @@ enum class DeriveType { /** An object representing a parsed extended public key in a descriptor. */ class BIP32PubkeyProvider final : public PubkeyProvider { - CExtPubKey m_extkey; + // Root xpub, path, and final derivation step type being used, if any + CExtPubKey m_root_extkey; KeyPath m_path; DeriveType m_derive; + // Cache of the parent of the final derived pubkeys. + // Primarily useful for situations when no read_cache is provided + CExtPubKey m_cached_xpub; 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 + sizeof(ret.vchFingerprint), ret.vchFingerprint); - ret.nChild = m_extkey.nChild; - ret.chaincode = m_extkey.chaincode; + 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; @@ -272,37 +298,77 @@ class BIP32PubkeyProvider final : public PubkeyProvider } public: - BIP32PubkeyProvider(const CExtPubKey& extkey, KeyPath path, DeriveType derive) : m_extkey(extkey), m_path(std::move(path)), m_derive(derive) {} + 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 + bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key_out, KeyOriginInfo& final_info_out, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) 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_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; + // 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(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) final_info_out_tmp.path.push_back((uint32_t)pos); + if (m_derive == DeriveType::HARDENED) final_info_out_tmp.path.push_back(((uint32_t)pos) | 0x80000000L); + + // Derive keys or fetch them from cache + CExtPubKey final_extkey = m_root_extkey; + CExtPubKey parent_extkey = m_root_extkey; + bool der = true; + if (read_cache) { + if (!read_cache->GetCachedDerivedExtPubKey(m_expr_index, pos, final_extkey)) { + if (m_derive == DeriveType::HARDENED) return false; + // Try to get the derivation parent + if (!read_cache->GetCachedParentExtPubKey(m_expr_index, parent_extkey)) return false; + final_extkey = parent_extkey; + if (m_derive == DeriveType::UNHARDENED) der = parent_extkey.Derive(final_extkey, pos); + } + } else if (m_cached_xpub.pubkey.IsValid() && m_derive != DeriveType::HARDENED) { + parent_extkey = final_extkey = m_cached_xpub; + if (m_derive == DeriveType::UNHARDENED) der = parent_extkey.Derive(final_extkey, pos); + } else if (IsHardened()) { + CExtKey xprv; + if (!GetDerivedExtKey(arg, xprv)) return false; + parent_extkey = xprv.Neuter(); + 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 = parent_extkey.Derive(parent_extkey, entry); + assert(der); } + final_extkey = parent_extkey; + if (m_derive == DeriveType::UNHARDENED) der = parent_extkey.Derive(final_extkey, pos); + assert(m_derive != DeriveType::HARDENED); } - CKeyID keyid = m_extkey.pubkey.GetID(); - std::copy(keyid.begin(), keyid.begin() + sizeof(info.fingerprint), info.fingerprint); - info.path = m_path; - if (m_derive == DeriveType::UNHARDENED) info.path.push_back((uint32_t)pos); - if (m_derive == DeriveType::HARDENED) info.path.push_back(((uint32_t)pos) | 0x80000000L); + assert(der); + + final_info_out = final_info_out_tmp; + key_out = final_extkey.pubkey; + + // We rely on the consumer to check that m_derive isn't HARDENED as above + // But we can't have already cached something in case we read something from the cache + // and parent_extkey isn't actually the parent. + if (!m_cached_xpub.pubkey.IsValid()) m_cached_xpub = parent_extkey; + + if (write_cache) { + // Only cache parent if there is any unhardened derivation + if (m_derive != DeriveType::HARDENED) { + write_cache->CacheParentExtPubKey(m_expr_index, parent_extkey); + } else if (final_info_out.path.size() > 0) { + write_cache->CacheDerivedExtPubKey(m_expr_index, pos, final_extkey); + } + } + return true; } std::string ToString() const override { - std::string ret = EncodeExtPubKey(m_extkey) + FormatHDKeypath(m_path); + std::string ret = EncodeExtPubKey(m_root_extkey) + FormatHDKeypath(m_path); if (IsRange()) { ret += "/*"; if (m_derive == DeriveType::HARDENED) ret += '\''; @@ -323,10 +389,7 @@ public: bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const override { CExtKey extkey; - if (!GetExtKey(arg, extkey)) return false; - for (auto entry : m_path) { - extkey.Derive(extkey, entry); - } + if (!GetDerivedExtKey(arg, extkey)) return false; if (m_derive == DeriveType::UNHARDENED) extkey.Derive(extkey, pos); if (m_derive == DeriveType::HARDENED) extkey.Derive(extkey, pos | 0x80000000UL); key = extkey.key; @@ -339,14 +402,15 @@ class DescriptorImpl : public Descriptor { //! Public key arguments for this descriptor (size 1 for PK, PKH, WPKH; any size for Multisig). const std::vector<std::unique_ptr<PubkeyProvider>> m_pubkey_args; + //! The string name of the descriptor function. + const std::string m_name; + +protected: //! The sub-descriptor argument (nullptr for everything but SH and WSH). //! In doc/descriptors.m this is referred to as SCRIPT expressions sh(SCRIPT) //! and wsh(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 ""; } @@ -364,7 +428,7 @@ protected: 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) {} + DescriptorImpl(std::vector<std::unique_ptr<PubkeyProvider>> pubkeys, std::unique_ptr<DescriptorImpl> script, const std::string& name) : m_pubkey_args(std::move(pubkeys)), m_name(name), m_subdescriptor_arg(std::move(script)) {} bool IsSolvable() const override { @@ -424,7 +488,7 @@ public: return ret; } - bool ExpandHelper(int pos, const SigningProvider& arg, Span<const unsigned char>* cache_read, std::vector<CScript>& output_scripts, FlatSigningProvider& out, std::vector<unsigned char>* cache_write) const + bool ExpandHelper(int pos, const SigningProvider& arg, const DescriptorCache* read_cache, std::vector<CScript>& output_scripts, FlatSigningProvider& out, DescriptorCache* write_cache) const { std::vector<std::pair<CPubKey, KeyOriginInfo>> entries; entries.reserve(m_pubkey_args.size()); @@ -432,27 +496,12 @@ public: // 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)) 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()); - } + if (!p->GetPubKey(pos, arg, entries.back().first, entries.back().second, read_cache, write_cache)) return false; } std::vector<CScript> subscripts; if (m_subdescriptor_arg) { FlatSigningProvider subprovider; - if (!m_subdescriptor_arg->ExpandHelper(pos, arg, cache_read, subscripts, subprovider, cache_write)) return false; + if (!m_subdescriptor_arg->ExpandHelper(pos, arg, read_cache, subscripts, subprovider, write_cache)) return false; out = Merge(out, subprovider); } @@ -476,15 +525,14 @@ public: return true; } - bool Expand(int pos, const SigningProvider& provider, std::vector<CScript>& output_scripts, FlatSigningProvider& out, std::vector<unsigned char>* cache = nullptr) const final + bool Expand(int pos, const SigningProvider& provider, std::vector<CScript>& output_scripts, FlatSigningProvider& out, DescriptorCache* write_cache = nullptr) const final { - return ExpandHelper(pos, provider, nullptr, output_scripts, out, cache); + return ExpandHelper(pos, provider, nullptr, output_scripts, out, write_cache); } - bool ExpandFromCache(int pos, const std::vector<unsigned char>& cache, std::vector<CScript>& output_scripts, FlatSigningProvider& out) const final + bool ExpandFromCache(int pos, const DescriptorCache& read_cache, std::vector<CScript>& output_scripts, FlatSigningProvider& out) const final { - Span<const unsigned char> 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 @@ -500,6 +548,8 @@ public: out = Merge(out, subprovider); } } + + Optional<OutputType> GetOutputType() const override { return nullopt; } }; /** A parsed addr(A) descriptor. */ @@ -512,6 +562,19 @@ protected: public: AddressDescriptor(CTxDestination destination) : DescriptorImpl({}, {}, "addr"), m_destination(std::move(destination)) {} bool IsSolvable() const final { return false; } + + Optional<OutputType> GetOutputType() const override + { + switch (m_destination.which()) { + case 1 /* PKHash */: + case 2 /* ScriptHash */: return OutputType::LEGACY; + case 3 /* WitnessV0ScriptHash */: + case 4 /* WitnessV0KeyHash */: + case 5 /* WitnessUnknown */: return OutputType::BECH32; + case 0 /* CNoDestination */: + default: return nullopt; + } + } }; /** A parsed raw(H) descriptor. */ @@ -524,6 +587,21 @@ protected: public: RawDescriptor(CScript script) : DescriptorImpl({}, {}, "raw"), m_script(std::move(script)) {} bool IsSolvable() const final { return false; } + + Optional<OutputType> GetOutputType() const override + { + CTxDestination dest; + ExtractDestination(m_script, dest); + switch (dest.which()) { + case 1 /* PKHash */: + case 2 /* ScriptHash */: return OutputType::LEGACY; + case 3 /* WitnessV0ScriptHash */: + case 4 /* WitnessV0KeyHash */: + case 5 /* WitnessUnknown */: return OutputType::BECH32; + case 0 /* CNoDestination */: + default: return nullopt; + } + } }; /** A parsed pk(P) descriptor. */ @@ -547,6 +625,7 @@ protected: } public: PKHDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), {}, "pkh") {} + Optional<OutputType> GetOutputType() const override { return OutputType::LEGACY; } }; /** A parsed wpkh(P) descriptor. */ @@ -561,6 +640,7 @@ protected: } public: WPKHDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), {}, "wpkh") {} + Optional<OutputType> GetOutputType() const override { return OutputType::BECH32; } }; /** A parsed combo(P) descriptor. */ @@ -612,6 +692,13 @@ 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") {} + + Optional<OutputType> GetOutputType() const override + { + assert(m_subdescriptor_arg); + if (m_subdescriptor_arg->GetOutputType() == OutputType::BECH32) return OutputType::P2SH_SEGWIT; + return OutputType::LEGACY; + } }; /** A parsed wsh(...) descriptor. */ @@ -621,6 +708,7 @@ protected: std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, const CScript* script, FlatSigningProvider&) const override { return Vector(GetScriptForDestination(WitnessV0ScriptHash(*script))); } public: WSHDescriptor(std::unique_ptr<DescriptorImpl> desc) : DescriptorImpl({}, std::move(desc), "wsh") {} + Optional<OutputType> GetOutputType() const override { return OutputType::BECH32; } }; //////////////////////////////////////////////////////////////////////////// @@ -657,7 +745,7 @@ NODISCARD bool ParseKeyPath(const std::vector<Span<const char>>& split, KeyPath& } /** Parse a public key that excludes origin information. */ -std::unique_ptr<PubkeyProvider> ParsePubkeyInner(const Span<const char>& sp, bool permit_uncompressed, FlatSigningProvider& out, std::string& error) +std::unique_ptr<PubkeyProvider> ParsePubkeyInner(uint32_t key_exp_index, const Span<const char>& sp, bool permit_uncompressed, FlatSigningProvider& out, std::string& error) { using namespace spanparsing; @@ -673,7 +761,7 @@ std::unique_ptr<PubkeyProvider> ParsePubkeyInner(const Span<const char>& sp, boo CPubKey pubkey(data); if (pubkey.IsFullyValid()) { if (permit_uncompressed || pubkey.IsCompressed()) { - return MakeUnique<ConstPubkeyProvider>(pubkey); + return MakeUnique<ConstPubkeyProvider>(key_exp_index, pubkey); } else { error = "Uncompressed keys are not allowed"; return nullptr; @@ -687,7 +775,7 @@ std::unique_ptr<PubkeyProvider> ParsePubkeyInner(const Span<const char>& sp, boo if (permit_uncompressed || key.IsCompressed()) { CPubKey pubkey = key.GetPubKey(); out.keys.emplace(pubkey.GetID(), key); - return MakeUnique<ConstPubkeyProvider>(pubkey); + return MakeUnique<ConstPubkeyProvider>(key_exp_index, pubkey); } else { error = "Uncompressed keys are not allowed"; return nullptr; @@ -714,11 +802,11 @@ std::unique_ptr<PubkeyProvider> ParsePubkeyInner(const Span<const char>& sp, boo extpubkey = extkey.Neuter(); out.keys.emplace(extpubkey.pubkey.GetID(), extkey.key); } - return MakeUnique<BIP32PubkeyProvider>(extpubkey, std::move(path), type); + return MakeUnique<BIP32PubkeyProvider>(key_exp_index, extpubkey, std::move(path), type); } /** Parse a public key including origin information (if enabled). */ -std::unique_ptr<PubkeyProvider> ParsePubkey(const Span<const char>& sp, bool permit_uncompressed, FlatSigningProvider& out, std::string& error) +std::unique_ptr<PubkeyProvider> ParsePubkey(uint32_t key_exp_index, const Span<const char>& sp, bool permit_uncompressed, FlatSigningProvider& out, std::string& error) { using namespace spanparsing; @@ -727,7 +815,7 @@ std::unique_ptr<PubkeyProvider> ParsePubkey(const Span<const char>& sp, bool per error = "Multiple ']' characters found for a single pubkey"; return nullptr; } - if (origin_split.size() == 1) return ParsePubkeyInner(origin_split[0], permit_uncompressed, out, error); + if (origin_split.size() == 1) return ParsePubkeyInner(key_exp_index, origin_split[0], permit_uncompressed, 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; @@ -748,30 +836,30 @@ std::unique_ptr<PubkeyProvider> ParsePubkey(const Span<const char>& sp, bool per 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(origin_split[1], permit_uncompressed, out, error); + auto provider = ParsePubkeyInner(key_exp_index, origin_split[1], permit_uncompressed, out, error); if (!provider) return nullptr; - return MakeUnique<OriginPubkeyProvider>(std::move(info), std::move(provider)); + return MakeUnique<OriginPubkeyProvider>(key_exp_index, std::move(info), std::move(provider)); } /** Parse a script in a particular context. */ -std::unique_ptr<DescriptorImpl> ParseScript(Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error) +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(expr, ctx != ParseScriptContext::P2WSH, out, error); + auto pubkey = ParsePubkey(key_exp_index, expr, ctx != ParseScriptContext::P2WSH, out, error); if (!pubkey) return nullptr; return MakeUnique<PKDescriptor>(std::move(pubkey)); } if (Func("pkh", expr)) { - auto pubkey = ParsePubkey(expr, ctx != ParseScriptContext::P2WSH, out, error); + auto pubkey = ParsePubkey(key_exp_index, expr, ctx != ParseScriptContext::P2WSH, out, error); if (!pubkey) return nullptr; return MakeUnique<PKHDescriptor>(std::move(pubkey)); } if (ctx == ParseScriptContext::TOP && Func("combo", expr)) { - auto pubkey = ParsePubkey(expr, true, out, error); + auto pubkey = ParsePubkey(key_exp_index, expr, true, out, error); if (!pubkey) return nullptr; return MakeUnique<ComboDescriptor>(std::move(pubkey)); } else if (ctx != ParseScriptContext::TOP && Func("combo", expr)) { @@ -793,10 +881,11 @@ std::unique_ptr<DescriptorImpl> ParseScript(Span<const char>& sp, ParseScriptCon return nullptr; } auto arg = Expr(expr); - auto pk = ParsePubkey(arg, ctx != ParseScriptContext::P2WSH, out, error); + auto pk = ParsePubkey(key_exp_index, arg, ctx != ParseScriptContext::P2WSH, 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()); @@ -815,15 +904,15 @@ std::unique_ptr<DescriptorImpl> ParseScript(Span<const char>& sp, ParseScriptCon } } if (ctx == ParseScriptContext::P2SH) { - if (script_size + 3 > 520) { - error = strprintf("P2SH script is too large, %d bytes is larger than 520 bytes", script_size + 3); + 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 MakeUnique<MultisigDescriptor>(thres, std::move(providers), sorted_multi); } if (ctx != ParseScriptContext::P2WSH && Func("wpkh", expr)) { - auto pubkey = ParsePubkey(expr, false, out, error); + auto pubkey = ParsePubkey(key_exp_index, expr, false, out, error); if (!pubkey) return nullptr; return MakeUnique<WPKHDescriptor>(std::move(pubkey)); } else if (ctx == ParseScriptContext::P2WSH && Func("wpkh", expr)) { @@ -831,7 +920,7 @@ std::unique_ptr<DescriptorImpl> ParseScript(Span<const char>& sp, ParseScriptCon return nullptr; } if (ctx == ParseScriptContext::TOP && Func("sh", expr)) { - auto desc = ParseScript(expr, ParseScriptContext::P2SH, out, error); + auto desc = ParseScript(key_exp_index, expr, ParseScriptContext::P2SH, out, error); if (!desc || expr.size()) return nullptr; return MakeUnique<SHDescriptor>(std::move(desc)); } else if (ctx != ParseScriptContext::TOP && Func("sh", expr)) { @@ -839,7 +928,7 @@ std::unique_ptr<DescriptorImpl> ParseScript(Span<const char>& sp, ParseScriptCon return nullptr; } if (ctx != ParseScriptContext::P2WSH && Func("wsh", expr)) { - auto desc = ParseScript(expr, ParseScriptContext::P2WSH, out, error); + auto desc = ParseScript(key_exp_index, expr, ParseScriptContext::P2WSH, out, error); if (!desc || expr.size()) return nullptr; return MakeUnique<WSHDescriptor>(std::move(desc)); } else if (ctx == ParseScriptContext::P2WSH && Func("wsh", expr)) { @@ -876,10 +965,10 @@ std::unique_ptr<DescriptorImpl> ParseScript(Span<const char>& sp, ParseScriptCon std::unique_ptr<PubkeyProvider> InferPubkey(const CPubKey& pubkey, ParseScriptContext, const SigningProvider& provider) { - std::unique_ptr<PubkeyProvider> key_provider = MakeUnique<ConstPubkeyProvider>(pubkey); + std::unique_ptr<PubkeyProvider> key_provider = MakeUnique<ConstPubkeyProvider>(0, pubkey); KeyOriginInfo info; if (provider.GetKeyOrigin(pubkey.GetID(), info)) { - return MakeUnique<OriginPubkeyProvider>(std::move(info), std::move(key_provider)); + return MakeUnique<OriginPubkeyProvider>(0, std::move(info), std::move(key_provider)); } return key_provider; } @@ -991,7 +1080,7 @@ std::unique_ptr<Descriptor> Parse(const std::string& descriptor, FlatSigningProv { Span<const char> sp(descriptor.data(), descriptor.size()); if (!CheckChecksum(sp, require_checksum, error)) return nullptr; - auto ret = ParseScript(sp, ParseScriptContext::TOP, out, error); + auto ret = ParseScript(0, sp, ParseScriptContext::TOP, out, error); if (sp.size() == 0 && ret) return std::unique_ptr<Descriptor>(std::move(ret)); return nullptr; } @@ -1009,3 +1098,42 @@ std::unique_ptr<Descriptor> InferDescriptor(const CScript& script, const Signing { 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 5a1b55259..34cd5760d 100644 --- a/src/script/descriptor.h +++ b/src/script/descriptor.h @@ -1,16 +1,61 @@ -// Copyright (c) 2018 The Bitcoin Core developers +// 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. #ifndef BITCOIN_SCRIPT_DESCRIPTOR_H #define BITCOIN_SCRIPT_DESCRIPTOR_H +#include <optional.h> +#include <outputtype.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. * @@ -47,30 +92,33 @@ struct Descriptor { /** 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[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] 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<unsigned char>* cache = nullptr) const = 0; + virtual bool Expand(int pos, const SigningProvider& provider, std::vector<CScript>& output_scripts, FlatSigningProvider& out, 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[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[in] pos The position at which to expand the descriptor. If IsRange() is false, this is ignored. + * @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<unsigned char>& cache, std::vector<CScript>& output_scripts, FlatSigningProvider& out) const = 0; + 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`. + * @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; + + /** @return The OutputType of the scriptPubKey(s) produced by this descriptor. Or nullopt if indeterminate (multiple or none) */ + virtual Optional<OutputType> GetOutputType() const = 0; }; /** Parse a `descriptor` string. Included private keys are put in `out`. diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp index 20fae2eeb..5bf418472 100644 --- a/src/script/interpreter.cpp +++ b/src/script/interpreter.cpp @@ -1,5 +1,5 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto -// Copyright (c) 2009-2018 The Bitcoin Core developers +// Copyright (c) 2009-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. @@ -61,17 +61,17 @@ static inline void popstack(std::vector<valtype>& stack) } bool static IsCompressedOrUncompressedPubKey(const valtype &vchPubKey) { - if (vchPubKey.size() < CPubKey::COMPRESSED_PUBLIC_KEY_SIZE) { + if (vchPubKey.size() < CPubKey::COMPRESSED_SIZE) { // Non-canonical public key: too short return false; } if (vchPubKey[0] == 0x04) { - if (vchPubKey.size() != CPubKey::PUBLIC_KEY_SIZE) { + if (vchPubKey.size() != CPubKey::SIZE) { // Non-canonical public key: invalid length for uncompressed key return false; } } else if (vchPubKey[0] == 0x02 || vchPubKey[0] == 0x03) { - if (vchPubKey.size() != CPubKey::COMPRESSED_PUBLIC_KEY_SIZE) { + if (vchPubKey.size() != CPubKey::COMPRESSED_SIZE) { // Non-canonical public key: invalid length for compressed key return false; } @@ -83,7 +83,7 @@ bool static IsCompressedOrUncompressedPubKey(const valtype &vchPubKey) { } bool static IsCompressedPubKey(const valtype &vchPubKey) { - if (vchPubKey.size() != CPubKey::COMPRESSED_PUBLIC_KEY_SIZE) { + if (vchPubKey.size() != CPubKey::COMPRESSED_SIZE) { // Non-canonical public key: invalid length for compressed key return false; } @@ -278,6 +278,70 @@ int FindAndDelete(CScript& script, const CScript& b) return nFound; } +namespace { +/** A data type to abstract out the condition stack during script execution. + * + * Conceptually it acts like a vector of booleans, one for each level of nested + * IF/THEN/ELSE, indicating whether we're in the active or inactive branch of + * each. + * + * The elements on the stack cannot be observed individually; we only need to + * expose whether the stack is empty and whether or not any false values are + * present at all. To implement OP_ELSE, a toggle_top modifier is added, which + * flips the last value without returning it. + * + * This uses an optimized implementation that does not materialize the + * actual stack. Instead, it just stores the size of the would-be stack, + * and the position of the first false value in it. + */ +class ConditionStack { +private: + //! A constant for m_first_false_pos to indicate there are no falses. + static constexpr uint32_t NO_FALSE = std::numeric_limits<uint32_t>::max(); + + //! The size of the implied stack. + uint32_t m_stack_size = 0; + //! The position of the first false value on the implied stack, or NO_FALSE if all true. + uint32_t m_first_false_pos = NO_FALSE; + +public: + bool empty() { return m_stack_size == 0; } + bool all_true() { return m_first_false_pos == NO_FALSE; } + void push_back(bool f) + { + if (m_first_false_pos == NO_FALSE && !f) { + // The stack consists of all true values, and a false is added. + // The first false value will appear at the current size. + m_first_false_pos = m_stack_size; + } + ++m_stack_size; + } + void pop_back() + { + assert(m_stack_size > 0); + --m_stack_size; + if (m_first_false_pos == m_stack_size) { + // When popping off the first false value, everything becomes true. + m_first_false_pos = NO_FALSE; + } + } + void toggle_top() + { + assert(m_stack_size > 0); + if (m_first_false_pos == NO_FALSE) { + // The current stack is all true values; the first false will be the top. + m_first_false_pos = m_stack_size - 1; + } else if (m_first_false_pos == m_stack_size - 1) { + // The top is the first false value; toggling it will make everything true. + m_first_false_pos = NO_FALSE; + } else { + // There is a false value, but not on top. No action is needed as toggling + // anything but the first false value is unobservable. + } + } +}; +} + bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror) { static const CScriptNum bnZero(0); @@ -293,7 +357,7 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& CScript::const_iterator pbegincodehash = script.begin(); opcodetype opcode; valtype vchPushValue; - std::vector<bool> vfExec; + ConditionStack vfExec; std::vector<valtype> altstack; set_error(serror, SCRIPT_ERR_UNKNOWN_ERROR); if (script.size() > MAX_SCRIPT_SIZE) @@ -305,7 +369,7 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& { while (pc < pend) { - bool fExec = !count(vfExec.begin(), vfExec.end(), false); + bool fExec = vfExec.all_true(); // // Read instruction @@ -494,7 +558,7 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& { if (vfExec.empty()) return set_error(serror, SCRIPT_ERR_UNBALANCED_CONDITIONAL); - vfExec.back() = !vfExec.back(); + vfExec.toggle_top(); } break; @@ -1281,13 +1345,11 @@ uint256 SignatureHash(const CScript& scriptCode, const T& txTo, unsigned int nIn return ss.GetHash(); } - static const uint256 one(uint256S("0000000000000000000000000000000000000000000000000000000000000001")); - // Check for invalid use of SIGHASH_SINGLE if ((nHashType & 0x1f) == SIGHASH_SINGLE) { if (nIn >= txTo.vout.size()) { // nOut out of range - return one; + return UINT256_ONE(); } } @@ -1416,9 +1478,26 @@ bool GenericTransactionSignatureChecker<T>::CheckSequence(const CScriptNum& nSeq template class GenericTransactionSignatureChecker<CTransaction>; template class GenericTransactionSignatureChecker<CMutableTransaction>; +static bool ExecuteWitnessScript(std::vector<valtype>::const_iterator begin, std::vector<valtype>::const_iterator end, const CScript& scriptPubKey, unsigned int flags, SigVersion sigversion, const BaseSignatureChecker& checker, ScriptError* serror) +{ + std::vector<valtype> stack{begin, end}; + + // Disallow stack item size > MAX_SCRIPT_ELEMENT_SIZE in witness stack + for (const valtype& elem : stack) { + if (elem.size() > MAX_SCRIPT_ELEMENT_SIZE) return set_error(serror, SCRIPT_ERR_PUSH_SIZE); + } + + // Run the script interpreter. + if (!EvalScript(stack, scriptPubKey, flags, checker, sigversion, serror)) return false; + + // Scripts inside witness implicitly require cleanstack behaviour + if (stack.size() != 1) return set_error(serror, SCRIPT_ERR_CLEANSTACK); + if (!CastToBool(stack.back())) return set_error(serror, SCRIPT_ERR_EVAL_FALSE); + return true; +} + static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion, const std::vector<unsigned char>& program, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror) { - std::vector<std::vector<unsigned char> > stack; CScript scriptPubKey; if (witversion == 0) { @@ -1428,45 +1507,30 @@ static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion, return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_WITNESS_EMPTY); } scriptPubKey = CScript(witness.stack.back().begin(), witness.stack.back().end()); - stack = std::vector<std::vector<unsigned char> >(witness.stack.begin(), witness.stack.end() - 1); uint256 hashScriptPubKey; CSHA256().Write(&scriptPubKey[0], scriptPubKey.size()).Finalize(hashScriptPubKey.begin()); if (memcmp(hashScriptPubKey.begin(), program.data(), 32)) { return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH); } + return ExecuteWitnessScript(witness.stack.begin(), witness.stack.end() - 1, scriptPubKey, flags, SigVersion::WITNESS_V0, checker, serror); } else if (program.size() == WITNESS_V0_KEYHASH_SIZE) { // Special case for pay-to-pubkeyhash; signature + pubkey in witness if (witness.stack.size() != 2) { return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH); // 2 items in witness } scriptPubKey << OP_DUP << OP_HASH160 << program << OP_EQUALVERIFY << OP_CHECKSIG; - stack = witness.stack; + return ExecuteWitnessScript(witness.stack.begin(), witness.stack.end(), scriptPubKey, flags, SigVersion::WITNESS_V0, checker, serror); } else { return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_WRONG_LENGTH); } - } else if (flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM) { - return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM); } else { + if (flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM) { + return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM); + } // Higher version witness scripts return true for future softfork compatibility - return set_success(serror); - } - - // Disallow stack item size > MAX_SCRIPT_ELEMENT_SIZE in witness stack - for (unsigned int i = 0; i < stack.size(); i++) { - if (stack.at(i).size() > MAX_SCRIPT_ELEMENT_SIZE) - return set_error(serror, SCRIPT_ERR_PUSH_SIZE); - } - - if (!EvalScript(stack, scriptPubKey, flags, checker, SigVersion::WITNESS_V0, serror)) { - return false; + return true; } - - // Scripts inside witness implicitly require cleanstack behaviour - if (stack.size() != 1) - return set_error(serror, SCRIPT_ERR_CLEANSTACK); - if (!CastToBool(stack.back())) - return set_error(serror, SCRIPT_ERR_EVAL_FALSE); - return true; + // There is intentionally no return statement here, to be able to use "control reaches end of non-void function" warnings to detect gaps in the logic above. } bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CScriptWitness* witness, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror) diff --git a/src/script/interpreter.h b/src/script/interpreter.h index d63d8b85b..2b104a608 100644 --- a/src/script/interpreter.h +++ b/src/script/interpreter.h @@ -1,5 +1,5 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto -// Copyright (c) 2009-2018 The Bitcoin Core developers +// Copyright (c) 2009-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. diff --git a/src/script/script.cpp b/src/script/script.cpp index 0666a385d..ae0de1d24 100644 --- a/src/script/script.cpp +++ b/src/script/script.cpp @@ -1,5 +1,5 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto -// Copyright (c) 2009-2018 The Bitcoin Core developers +// Copyright (c) 2009-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. diff --git a/src/script/script.h b/src/script/script.h index 6355b8a70..7aaa10b60 100644 --- a/src/script/script.h +++ b/src/script/script.h @@ -1,5 +1,5 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto -// Copyright (c) 2009-2018 The Bitcoin Core developers +// Copyright (c) 2009-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. diff --git a/src/script/sigcache.cpp b/src/script/sigcache.cpp index eaf5363bd..e7b6df3ce 100644 --- a/src/script/sigcache.cpp +++ b/src/script/sigcache.cpp @@ -1,5 +1,5 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto -// Copyright (c) 2009-2018 The Bitcoin Core developers +// Copyright (c) 2009-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. diff --git a/src/script/sign.cpp b/src/script/sign.cpp index 0ed92e8d5..fe8292fe5 100644 --- a/src/script/sign.cpp +++ b/src/script/sign.cpp @@ -1,5 +1,5 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto -// Copyright (c) 2009-2018 The Bitcoin Core developers +// Copyright (c) 2009-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. @@ -144,8 +144,13 @@ static bool SignStep(const SigningProvider& provider, const BaseSignatureCreator ret.push_back(valtype()); // workaround CHECKMULTISIG bug for (size_t i = 1; i < vSolutions.size() - 1; ++i) { CPubKey pubkey = CPubKey(vSolutions[i]); - if (ret.size() < required + 1 && CreateSig(creator, sigdata, provider, sig, pubkey, scriptPubKey, sigversion)) { - ret.push_back(std::move(sig)); + // We need to always call CreateSig in order to fill sigdata with all + // possible signatures that we can create. This will allow further PSBT + // processing to work as it needs all possible signature and pubkey pairs + if (CreateSig(creator, sigdata, provider, sig, pubkey, scriptPubKey, sigversion)) { + if (ret.size() < required + 1) { + ret.push_back(std::move(sig)); + } } } bool ok = ret.size() == required + 1; @@ -460,3 +465,54 @@ bool IsSegWitOutput(const SigningProvider& provider, const CScript& script) } return false; } + +bool SignTransaction(CMutableTransaction& mtx, const SigningProvider* keystore, const std::map<COutPoint, Coin>& coins, int nHashType, std::map<int, std::string>& input_errors) +{ + bool fHashSingle = ((nHashType & ~SIGHASH_ANYONECANPAY) == SIGHASH_SINGLE); + + // Use CTransaction for the constant parts of the + // transaction to avoid rehashing. + const CTransaction txConst(mtx); + // Sign what we can: + for (unsigned int i = 0; i < mtx.vin.size(); i++) { + CTxIn& txin = mtx.vin[i]; + auto coin = coins.find(txin.prevout); + if (coin == coins.end() || coin->second.IsSpent()) { + input_errors[i] = "Input not found or already spent"; + continue; + } + const CScript& prevPubKey = coin->second.out.scriptPubKey; + const CAmount& amount = coin->second.out.nValue; + + SignatureData sigdata = DataFromTransaction(mtx, i, coin->second.out); + // Only sign SIGHASH_SINGLE if there's a corresponding output: + if (!fHashSingle || (i < mtx.vout.size())) { + ProduceSignature(*keystore, MutableTransactionSignatureCreator(&mtx, i, amount, nHashType), prevPubKey, sigdata); + } + + UpdateInput(txin, sigdata); + + // amount must be specified for valid segwit signature + if (amount == MAX_MONEY && !txin.scriptWitness.IsNull()) { + input_errors[i] = "Missing amount"; + continue; + } + + ScriptError serror = SCRIPT_ERR_OK; + if (!VerifyScript(txin.scriptSig, prevPubKey, &txin.scriptWitness, STANDARD_SCRIPT_VERIFY_FLAGS, TransactionSignatureChecker(&txConst, i, amount), &serror)) { + if (serror == SCRIPT_ERR_INVALID_STACK_OPERATION) { + // Unable to sign input and verification failed (possible attempt to partially sign). + input_errors[i] = "Unable to sign input, invalid stack size (possibly missing key)"; + } else if (serror == SCRIPT_ERR_SIG_NULLFAIL) { + // Verification failed (possibly due to insufficient signatures). + input_errors[i] = "CHECK(MULTI)SIG failing with non-zero signature (possibly need more signatures)"; + } else { + input_errors[i] = ScriptErrorString(serror); + } + } else { + // If this input succeeds, make sure there is no error set for it + input_errors.erase(i); + } + } + return input_errors.empty(); +} diff --git a/src/script/sign.h b/src/script/sign.h index 9d0a5b4d7..f03af0713 100644 --- a/src/script/sign.h +++ b/src/script/sign.h @@ -1,11 +1,12 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto -// Copyright (c) 2009-2018 The Bitcoin Core developers +// Copyright (c) 2009-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. #ifndef BITCOIN_SCRIPT_SIGN_H #define BITCOIN_SCRIPT_SIGN_H +#include <coins.h> #include <hash.h> #include <pubkey.h> #include <script/interpreter.h> @@ -101,7 +102,7 @@ template<typename Stream> void DeserializeHDKeypaths(Stream& s, const std::vector<unsigned char>& key, std::map<CPubKey, KeyOriginInfo>& hd_keypaths) { // Make sure that the key is the size of pubkey + 1 - if (key.size() != CPubKey::PUBLIC_KEY_SIZE + 1 && key.size() != CPubKey::COMPRESSED_PUBLIC_KEY_SIZE + 1) { + if (key.size() != CPubKey::SIZE + 1 && key.size() != CPubKey::COMPRESSED_SIZE + 1) { throw std::ios_base::failure("Size of key was not the expected size for the type BIP32 keypath"); } // Read in the pubkey from key @@ -168,4 +169,7 @@ bool IsSolvable(const SigningProvider& provider, const CScript& script); /** Check whether a scriptPubKey is known to be segwit. */ bool IsSegWitOutput(const SigningProvider& provider, const CScript& script); +/** Sign the CMutableTransaction */ +bool SignTransaction(CMutableTransaction& mtx, const SigningProvider* provider, const std::map<COutPoint, Coin>& coins, int sighash, std::map<int, std::string>& input_errors); + #endif // BITCOIN_SCRIPT_SIGN_H diff --git a/src/script/signingprovider.h b/src/script/signingprovider.h index c40fecac5..76f31d2f6 100644 --- a/src/script/signingprovider.h +++ b/src/script/signingprovider.h @@ -1,5 +1,5 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto -// Copyright (c) 2009-2019 The Bitcoin Core developers +// Copyright (c) 2009-2020 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. @@ -66,13 +66,59 @@ protected: using KeyMap = std::map<CKeyID, CKey>; using ScriptMap = std::map<CScriptID, CScript>; + /** + * Map of key id to unencrypted private keys known by the signing provider. + * Map may be empty if the provider has another source of keys, like an + * encrypted store. + */ KeyMap mapKeys GUARDED_BY(cs_KeyStore); + + /** + * Map of script id to scripts known by the signing provider. + * + * This map originally just held P2SH redeemScripts, and was used by wallet + * code to look up script ids referenced in "OP_HASH160 <script id> + * OP_EQUAL" P2SH outputs. Later in 605e8473a7d it was extended to hold + * P2WSH witnessScripts as well, and used to look up nested scripts + * referenced in "OP_0 <script hash>" P2WSH outputs. Later in commits + * f4691ab3a9d and 248f3a76a82, it was extended once again to hold segwit + * "OP_0 <key or script hash>" scriptPubKeys, in order to give the wallet a + * way to distinguish between segwit outputs that it generated addresses for + * and wanted to receive payments from, and segwit outputs that it never + * generated addresses for, but it could spend just because of having keys. + * (Before segwit activation it was also important to not treat segwit + * outputs to arbitrary wallet keys as payments, because these could be + * spent by anyone without even needing to sign with the keys.) + * + * Some of the scripts stored in mapScripts are memory-only and + * intentionally not saved to disk. Specifically, scripts added by + * ImplicitlyLearnRelatedKeyScripts(pubkey) calls are not written to disk so + * future wallet code can have flexibility to be more selective about what + * transaction outputs it recognizes as payments, instead of having to treat + * all outputs spending to keys it knows as payments. By contrast, + * mapScripts entries added by AddCScript(script), + * LearnRelatedScripts(pubkey, type), and LearnAllRelatedScripts(pubkey) + * calls are saved because they are all intentionally used to receive + * payments. + * + * The FillableSigningProvider::mapScripts script map should not be confused + * with LegacyScriptPubKeyMan::setWatchOnly script set. The two collections + * can hold the same scripts, but they serve different purposes. The + * setWatchOnly script set is intended to expand the set of outputs the + * wallet considers payments. Every output with a script it contains is + * considered to belong to the wallet, regardless of whether the script is + * solvable or signable. By contrast, the scripts in mapScripts are only + * used for solving, and to restrict which outputs are considered payments + * by the wallet. An output with a script in mapScripts, unlike + * setWatchOnly, is not automatically considered to belong to the wallet if + * it can't be solved and signed for. + */ ScriptMap mapScripts GUARDED_BY(cs_KeyStore); void ImplicitlyLearnRelatedKeyScripts(const CPubKey& pubkey) EXCLUSIVE_LOCKS_REQUIRED(cs_KeyStore); public: - mutable CCriticalSection cs_KeyStore; + mutable RecursiveMutex cs_KeyStore; virtual bool AddKeyPubKey(const CKey& key, const CPubKey &pubkey); virtual bool AddKey(const CKey &key) { return AddKeyPubKey(key, key.GetPubKey()); } diff --git a/src/script/standard.cpp b/src/script/standard.cpp index fc6898f44..7d89a336f 100644 --- a/src/script/standard.cpp +++ b/src/script/standard.cpp @@ -1,5 +1,5 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto -// Copyright (c) 2009-2018 The Bitcoin Core developers +// Copyright (c) 2009-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. @@ -44,12 +44,12 @@ const char* GetTxnOutputType(txnouttype t) static bool MatchPayToPubkey(const CScript& script, valtype& pubkey) { - if (script.size() == CPubKey::PUBLIC_KEY_SIZE + 2 && script[0] == CPubKey::PUBLIC_KEY_SIZE && script.back() == OP_CHECKSIG) { - pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::PUBLIC_KEY_SIZE + 1); + if (script.size() == CPubKey::SIZE + 2 && script[0] == CPubKey::SIZE && script.back() == OP_CHECKSIG) { + pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::SIZE + 1); return CPubKey::ValidSize(pubkey); } - if (script.size() == CPubKey::COMPRESSED_PUBLIC_KEY_SIZE + 2 && script[0] == CPubKey::COMPRESSED_PUBLIC_KEY_SIZE && script.back() == OP_CHECKSIG) { - pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::COMPRESSED_PUBLIC_KEY_SIZE + 1); + if (script.size() == CPubKey::COMPRESSED_SIZE + 2 && script[0] == CPubKey::COMPRESSED_SIZE && script.back() == OP_CHECKSIG) { + pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::COMPRESSED_SIZE + 1); return CPubKey::ValidSize(pubkey); } return false; diff --git a/src/script/standard.h b/src/script/standard.h index 6db28dbc2..49a45f3eb 100644 --- a/src/script/standard.h +++ b/src/script/standard.h @@ -1,5 +1,5 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto -// Copyright (c) 2009-2018 The Bitcoin Core developers +// Copyright (c) 2009-2020 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. @@ -47,7 +47,7 @@ extern unsigned nMaxDatacarrierBytes; * but in the future other flags may be added, such as a soft-fork to enforce * strict DER encoding. * - * Failing one of these tests may trigger a DoS ban - see CheckInputs() for + * Failing one of these tests may trigger a DoS ban - see CheckInputScripts() for * details. */ static const unsigned int MANDATORY_SCRIPT_VERIFY_FLAGS = SCRIPT_VERIFY_P2SH; @@ -80,9 +80,14 @@ struct PKHash : public uint160 using uint160::uint160; }; +struct WitnessV0KeyHash; struct ScriptHash : public uint160 { ScriptHash() : uint160() {} + // These don't do what you'd expect. + // Use ScriptHash(GetScriptForDestination(...)) instead. + explicit ScriptHash(const WitnessV0KeyHash& hash) = delete; + explicit ScriptHash(const PKHash& hash) = delete; explicit ScriptHash(const uint160& hash) : uint160(hash) {} explicit ScriptHash(const CScript& script); using uint160::uint160; |