diff options
Diffstat (limited to 'src/script')
| -rw-r--r-- | src/script/descriptor.cpp | 426 | ||||
| -rw-r--r-- | src/script/descriptor.h | 23 | ||||
| -rw-r--r-- | src/script/interpreter.cpp | 69 | ||||
| -rw-r--r-- | src/script/interpreter.h | 22 | ||||
| -rw-r--r-- | src/script/sign.cpp | 216 | ||||
| -rw-r--r-- | src/script/sign.h | 9 | ||||
| -rw-r--r-- | src/script/signingprovider.cpp | 13 | ||||
| -rw-r--r-- | src/script/signingprovider.h | 4 | ||||
| -rw-r--r-- | src/script/standard.cpp | 308 | ||||
| -rw-r--r-- | src/script/standard.h | 139 |
10 files changed, 1086 insertions, 143 deletions
diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp index b54ba204f0..682b55742a 100644 --- a/src/script/descriptor.cpp +++ b/src/script/descriptor.cpp @@ -166,7 +166,7 @@ public: * 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; + virtual bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const = 0; /** Whether this represent multiple public keys at different positions. */ virtual bool IsRange() const = 0; @@ -181,7 +181,7 @@ public: virtual bool ToPrivateString(const SigningProvider& arg, std::string& out) const = 0; /** Get the descriptor string form with the xpub at the last hardened derivation */ - virtual bool ToNormalizedString(const SigningProvider& arg, std::string& out, bool priv) const = 0; + virtual bool ToNormalizedString(const SigningProvider& arg, std::string& out, const DescriptorCache* cache = nullptr) const = 0; /** Derive a private key, if private data is available in arg. */ virtual bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const = 0; @@ -199,7 +199,7 @@ class OriginPubkeyProvider final : public PubkeyProvider public: OriginPubkeyProvider(uint32_t exp_index, KeyOriginInfo info, std::unique_ptr<PubkeyProvider> provider) : PubkeyProvider(exp_index), m_origin(std::move(info)), m_provider(std::move(provider)) {} - bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) override + bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override { if (!m_provider->GetPubKey(pos, arg, key, info, read_cache, write_cache)) return false; std::copy(std::begin(m_origin.fingerprint), std::end(m_origin.fingerprint), info.fingerprint); @@ -216,10 +216,10 @@ public: ret = "[" + OriginString() + "]" + std::move(sub); return true; } - bool ToNormalizedString(const SigningProvider& arg, std::string& ret, bool priv) const override + bool ToNormalizedString(const SigningProvider& arg, std::string& ret, const DescriptorCache* cache) const override { std::string sub; - if (!m_provider->ToNormalizedString(arg, sub, priv)) return false; + if (!m_provider->ToNormalizedString(arg, sub, cache)) return false; // If m_provider is a BIP32PubkeyProvider, we may get a string formatted like a OriginPubkeyProvider // In that case, we need to strip out the leading square bracket and fingerprint from the substring, // and append that to our own origin string. @@ -241,10 +241,11 @@ public: class ConstPubkeyProvider final : public PubkeyProvider { CPubKey m_pubkey; + bool m_xonly; public: - ConstPubkeyProvider(uint32_t exp_index, const CPubKey& pubkey) : PubkeyProvider(exp_index), m_pubkey(pubkey) {} - bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) override + ConstPubkeyProvider(uint32_t exp_index, const CPubKey& pubkey, bool xonly) : PubkeyProvider(exp_index), m_pubkey(pubkey), m_xonly(xonly) {} + bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override { key = m_pubkey; info.path.clear(); @@ -254,7 +255,7 @@ public: } bool IsRange() const override { return false; } size_t GetSize() const override { return m_pubkey.size(); } - std::string ToString() const override { return HexStr(m_pubkey); } + std::string ToString() const override { return m_xonly ? HexStr(m_pubkey).substr(2) : HexStr(m_pubkey); } bool ToPrivateString(const SigningProvider& arg, std::string& ret) const override { CKey key; @@ -262,9 +263,8 @@ public: ret = EncodeSecret(key); return true; } - bool ToNormalizedString(const SigningProvider& arg, std::string& ret, bool priv) const override + bool ToNormalizedString(const SigningProvider& arg, std::string& ret, const DescriptorCache* cache) const override { - if (priv) return ToPrivateString(arg, ret); ret = ToString(); return true; } @@ -287,9 +287,6 @@ class BIP32PubkeyProvider final : public PubkeyProvider 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 { @@ -304,11 +301,14 @@ class BIP32PubkeyProvider final : public PubkeyProvider } // Derives the last xprv - bool GetDerivedExtKey(const SigningProvider& arg, CExtKey& xprv) const + bool GetDerivedExtKey(const SigningProvider& arg, CExtKey& xprv, CExtKey& last_hardened) const { if (!GetExtKey(arg, xprv)) return false; for (auto entry : m_path) { xprv.Derive(xprv, entry); + if (entry >> 31) { + last_hardened = xprv; + } } return true; } @@ -326,7 +326,7 @@ public: BIP32PubkeyProvider(uint32_t exp_index, const CExtPubKey& extkey, KeyPath path, DeriveType derive) : PubkeyProvider(exp_index), m_root_extkey(extkey), m_path(std::move(path)), m_derive(derive) {} bool IsRange() const override { return m_derive != DeriveType::NO; } size_t GetSize() const override { return 33; } - bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key_out, KeyOriginInfo& final_info_out, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) override + bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key_out, KeyOriginInfo& final_info_out, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override { // Info of parent of the to be derived pubkey KeyOriginInfo parent_info; @@ -342,6 +342,7 @@ public: // Derive keys or fetch them from cache CExtPubKey final_extkey = m_root_extkey; CExtPubKey parent_extkey = m_root_extkey; + CExtPubKey last_hardened_extkey; bool der = true; if (read_cache) { if (!read_cache->GetCachedDerivedExtPubKey(m_expr_index, pos, final_extkey)) { @@ -351,16 +352,17 @@ public: 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; + CExtKey lh_xprv; + if (!GetDerivedExtKey(arg, xprv, lh_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(); + if (lh_xprv.key.IsValid()) { + last_hardened_extkey = lh_xprv.Neuter(); + } } else { for (auto entry : m_path) { der = parent_extkey.Derive(parent_extkey, entry); @@ -375,15 +377,14 @@ public: 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); + // Cache last hardened xpub if we have it + if (last_hardened_extkey.pubkey.IsValid()) { + write_cache->CacheLastHardenedExtPubKey(m_expr_index, last_hardened_extkey); + } } else if (final_info_out.path.size() > 0) { write_cache->CacheDerivedExtPubKey(m_expr_index, pos, final_extkey); } @@ -411,11 +412,10 @@ public: } return true; } - bool ToNormalizedString(const SigningProvider& arg, std::string& out, bool priv) const override + bool ToNormalizedString(const SigningProvider& arg, std::string& out, const DescriptorCache* cache) const override { // For hardened derivation type, just return the typical string, nothing to normalize if (m_derive == DeriveType::HARDENED) { - if (priv) return ToPrivateString(arg, out); out = ToString(); return true; } @@ -428,33 +428,42 @@ public: } // Either no derivation or all unhardened derivation if (i == -1) { - if (priv) return ToPrivateString(arg, out); out = ToString(); return true; } - // Derive the xpub at the last hardened step - CExtKey xprv; - if (!GetExtKey(arg, xprv)) return false; + // Get the path to the last hardened stup KeyOriginInfo origin; int k = 0; for (; k <= i; ++k) { - // Derive - xprv.Derive(xprv, m_path.at(k)); // Add to the path origin.path.push_back(m_path.at(k)); - // First derivation element, get the fingerprint for origin - if (k == 0) { - std::copy(xprv.vchFingerprint, xprv.vchFingerprint + 4, origin.fingerprint); - } } // Build the remaining path KeyPath end_path; for (; k < (int)m_path.size(); ++k) { end_path.push_back(m_path.at(k)); } + // Get the fingerprint + CKeyID id = m_root_extkey.pubkey.GetID(); + std::copy(id.begin(), id.begin() + 4, origin.fingerprint); + + CExtPubKey xpub; + CExtKey lh_xprv; + // If we have the cache, just get the parent xpub + if (cache != nullptr) { + cache->GetCachedLastHardenedExtPubKey(m_expr_index, xpub); + } + if (!xpub.pubkey.IsValid()) { + // Cache miss, or nor cache, or need privkey + CExtKey xprv; + if (!GetDerivedExtKey(arg, xprv, lh_xprv)) return false; + xpub = lh_xprv.Neuter(); + } + assert(xpub.pubkey.IsValid()); + // Build the string std::string origin_str = HexStr(origin.fingerprint) + FormatHDKeypath(origin.path); - out = "[" + origin_str + "]" + (priv ? EncodeExtKey(xprv) : EncodeExtPubKey(xprv.Neuter())) + FormatHDKeypath(end_path); + out = "[" + origin_str + "]" + EncodeExtPubKey(xpub) + FormatHDKeypath(end_path); if (IsRange()) { out += "/*"; assert(m_derive == DeriveType::UNHARDENED); @@ -464,7 +473,8 @@ public: bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const override { CExtKey extkey; - if (!GetDerivedExtKey(arg, extkey)) return false; + CExtKey dummy; + if (!GetDerivedExtKey(arg, extkey, dummy)) return false; if (m_derive == DeriveType::UNHARDENED) extkey.Derive(extkey, pos); if (m_derive == DeriveType::HARDENED) extkey.Derive(extkey, pos | 0x80000000UL); key = extkey.key; @@ -505,6 +515,14 @@ protected: public: DescriptorImpl(std::vector<std::unique_ptr<PubkeyProvider>> pubkeys, const std::string& name) : m_pubkey_args(std::move(pubkeys)), m_name(name), m_subdescriptor_args() {} DescriptorImpl(std::vector<std::unique_ptr<PubkeyProvider>> pubkeys, std::unique_ptr<DescriptorImpl> script, const std::string& name) : m_pubkey_args(std::move(pubkeys)), m_name(name), m_subdescriptor_args(Vector(std::move(script))) {} + DescriptorImpl(std::vector<std::unique_ptr<PubkeyProvider>> pubkeys, std::vector<std::unique_ptr<DescriptorImpl>> scripts, const std::string& name) : m_pubkey_args(std::move(pubkeys)), m_name(name), m_subdescriptor_args(std::move(scripts)) {} + + enum class StringType + { + PUBLIC, + PRIVATE, + NORMALIZED, + }; bool IsSolvable() const override { @@ -525,19 +543,19 @@ public: return false; } - virtual bool ToStringSubScriptHelper(const SigningProvider* arg, std::string& ret, bool priv, bool normalized) const + virtual bool ToStringSubScriptHelper(const SigningProvider* arg, std::string& ret, const StringType type, const DescriptorCache* cache = nullptr) const { size_t pos = 0; for (const auto& scriptarg : m_subdescriptor_args) { if (pos++) ret += ","; std::string tmp; - if (!scriptarg->ToStringHelper(arg, tmp, priv, normalized)) return false; + if (!scriptarg->ToStringHelper(arg, tmp, type, cache)) return false; ret += std::move(tmp); } return true; } - bool ToStringHelper(const SigningProvider* arg, std::string& out, bool priv, bool normalized) const + bool ToStringHelper(const SigningProvider* arg, std::string& out, const StringType type, const DescriptorCache* cache = nullptr) const { std::string extra = ToStringExtra(); size_t pos = extra.size() > 0 ? 1 : 0; @@ -545,17 +563,21 @@ public: for (const auto& pubkey : m_pubkey_args) { if (pos++) ret += ","; std::string tmp; - if (normalized) { - if (!pubkey->ToNormalizedString(*arg, tmp, priv)) return false; - } else if (priv) { - if (!pubkey->ToPrivateString(*arg, tmp)) return false; - } else { - tmp = pubkey->ToString(); + switch (type) { + case StringType::NORMALIZED: + if (!pubkey->ToNormalizedString(*arg, tmp, cache)) return false; + break; + case StringType::PRIVATE: + if (!pubkey->ToPrivateString(*arg, tmp)) return false; + break; + case StringType::PUBLIC: + tmp = pubkey->ToString(); + break; } ret += std::move(tmp); } std::string subscript; - if (!ToStringSubScriptHelper(arg, subscript, priv, normalized)) return false; + if (!ToStringSubScriptHelper(arg, subscript, type, cache)) return false; if (pos && subscript.size()) ret += ','; out = std::move(ret) + std::move(subscript) + ")"; return true; @@ -564,20 +586,20 @@ public: std::string ToString() const final { std::string ret; - ToStringHelper(nullptr, ret, false, false); + ToStringHelper(nullptr, ret, StringType::PUBLIC); return AddChecksum(ret); } bool ToPrivateString(const SigningProvider& arg, std::string& out) const final { - bool ret = ToStringHelper(&arg, out, true, false); + bool ret = ToStringHelper(&arg, out, StringType::PRIVATE); out = AddChecksum(out); return ret; } - bool ToNormalizedString(const SigningProvider& arg, std::string& out, bool priv) const override final + bool ToNormalizedString(const SigningProvider& arg, std::string& out, const DescriptorCache* cache) const override final { - bool ret = ToStringHelper(&arg, out, priv, true); + bool ret = ToStringHelper(&arg, out, StringType::NORMALIZED, cache); out = AddChecksum(out); return ret; } @@ -651,15 +673,7 @@ public: std::optional<OutputType> GetOutputType() const override { - switch (m_destination.index()) { - 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 std::nullopt; - } + return OutputTypeFromDestination(m_destination); } bool IsSingleType() const final { return true; } }; @@ -679,15 +693,7 @@ public: { CTxDestination dest; ExtractDestination(m_script, dest); - switch (dest.index()) { - 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 std::nullopt; - } + return OutputTypeFromDestination(dest); } bool IsSingleType() const final { return true; } }; @@ -695,10 +701,20 @@ public: /** A parsed pk(P) descriptor. */ class PKDescriptor final : public DescriptorImpl { +private: + const bool m_xonly; protected: - std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider&) const override { return Vector(GetScriptForRawPubKey(keys[0])); } + std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider&) const override + { + if (m_xonly) { + CScript script = CScript() << ToByteVector(XOnlyPubKey(keys[0])) << OP_CHECKSIG; + return Vector(std::move(script)); + } else { + return Vector(GetScriptForRawPubKey(keys[0])); + } + } public: - PKDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), "pk") {} + PKDescriptor(std::unique_ptr<PubkeyProvider> prov, bool xonly = false) : DescriptorImpl(Vector(std::move(prov)), "pk"), m_xonly(xonly) {} bool IsSingleType() const final { return true; } }; @@ -816,6 +832,58 @@ public: bool IsSingleType() const final { return true; } }; +/** A parsed tr(...) descriptor. */ +class TRDescriptor final : public DescriptorImpl +{ + std::vector<int> m_depths; +protected: + std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript> scripts, FlatSigningProvider& out) const override + { + TaprootBuilder builder; + assert(m_depths.size() == scripts.size()); + for (size_t pos = 0; pos < m_depths.size(); ++pos) { + builder.Add(m_depths[pos], scripts[pos], TAPROOT_LEAF_TAPSCRIPT); + } + if (!builder.IsComplete()) return {}; + assert(keys.size() == 1); + XOnlyPubKey xpk(keys[0]); + if (!xpk.IsFullyValid()) return {}; + builder.Finalize(xpk); + WitnessV1Taproot output = builder.GetOutput(); + out.tr_spenddata[output].Merge(builder.GetSpendData()); + return Vector(GetScriptForDestination(output)); + } + bool ToStringSubScriptHelper(const SigningProvider* arg, std::string& ret, const StringType type, const DescriptorCache* cache = nullptr) const override + { + if (m_depths.empty()) return true; + std::vector<bool> path; + for (size_t pos = 0; pos < m_depths.size(); ++pos) { + if (pos) ret += ','; + while ((int)path.size() <= m_depths[pos]) { + if (path.size()) ret += '{'; + path.push_back(false); + } + std::string tmp; + if (!m_subdescriptor_args[pos]->ToStringHelper(arg, tmp, type, cache)) return false; + ret += std::move(tmp); + while (!path.empty() && path.back()) { + if (path.size() > 1) ret += '}'; + path.pop_back(); + } + if (!path.empty()) path.back() = true; + } + return true; + } +public: + TRDescriptor(std::unique_ptr<PubkeyProvider> internal_key, std::vector<std::unique_ptr<DescriptorImpl>> descs, std::vector<int> depths) : + DescriptorImpl(Vector(std::move(internal_key)), std::move(descs), "tr"), m_depths(std::move(depths)) + { + assert(m_subdescriptor_args.size() == m_depths.size()); + } + std::optional<OutputType> GetOutputType() const override { return OutputType::BECH32M; } + bool IsSingleType() const final { return true; } +}; + //////////////////////////////////////////////////////////////////////////// // Parser // //////////////////////////////////////////////////////////////////////////// @@ -825,6 +893,7 @@ enum class ParseScriptContext { P2SH, //!< Inside sh() (script becomes P2SH redeemScript) P2WPKH, //!< Inside wpkh() (no script, pubkey only) P2WSH, //!< Inside wsh() (script becomes v0 witness script) + P2TR, //!< Inside tr() (either internal key, or BIP342 script leaf) }; /** Parse a key path, being passed a split list of elements (the first element is ignored). */ @@ -868,11 +937,18 @@ std::unique_ptr<PubkeyProvider> ParsePubkeyInner(uint32_t key_exp_index, const S CPubKey pubkey(data); if (pubkey.IsFullyValid()) { if (permit_uncompressed || pubkey.IsCompressed()) { - return std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey); + return std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey, false); } else { error = "Uncompressed keys are not allowed"; return nullptr; } + } else if (data.size() == 32 && ctx == ParseScriptContext::P2TR) { + unsigned char fullkey[33] = {0x02}; + std::copy(data.begin(), data.end(), fullkey + 1); + pubkey.Set(std::begin(fullkey), std::end(fullkey)); + if (pubkey.IsFullyValid()) { + return std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey, true); + } } error = strprintf("Pubkey '%s' is invalid", str); return nullptr; @@ -882,7 +958,7 @@ std::unique_ptr<PubkeyProvider> ParsePubkeyInner(uint32_t key_exp_index, const S if (permit_uncompressed || key.IsCompressed()) { CPubKey pubkey = key.GetPubKey(); out.keys.emplace(pubkey.GetID(), key); - return std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey); + return std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey, ctx == ParseScriptContext::P2TR); } else { error = "Uncompressed keys are not allowed"; return nullptr; @@ -960,13 +1036,16 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error); if (!pubkey) return nullptr; ++key_exp_index; - return std::make_unique<PKDescriptor>(std::move(pubkey)); + return std::make_unique<PKDescriptor>(std::move(pubkey), ctx == ParseScriptContext::P2TR); } - if (Func("pkh", expr)) { + if ((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH) && Func("pkh", expr)) { auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error); if (!pubkey) return nullptr; ++key_exp_index; return std::make_unique<PKHDescriptor>(std::move(pubkey)); + } else if (Func("pkh", expr)) { + error = "Can only have pkh at top level, in sh(), or in wsh()"; + return nullptr; } if (ctx == ParseScriptContext::TOP && Func("combo", expr)) { auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error); @@ -977,7 +1056,7 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const error = "Can only have combo() at top level"; return nullptr; } - if ((sorted_multi = Func("sortedmulti", expr)) || Func("multi", expr)) { + if ((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH) && ((sorted_multi = Func("sortedmulti", expr)) || Func("multi", expr))) { auto threshold = Expr(expr); uint32_t thres; std::vector<std::unique_ptr<PubkeyProvider>> providers; @@ -1022,6 +1101,9 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const } } return std::make_unique<MultisigDescriptor>(thres, std::move(providers), sorted_multi); + } else if (Func("sortedmulti", expr) || Func("multi", expr)) { + error = "Can only have multi/sortedmulti at top level, in sh(), or in wsh()"; + return nullptr; } if ((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH) && Func("wpkh", expr)) { auto pubkey = ParsePubkey(key_exp_index, expr, ParseScriptContext::P2WPKH, out, error); @@ -1059,6 +1141,67 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const error = "Can only have addr() at top level"; return nullptr; } + if (ctx == ParseScriptContext::TOP && Func("tr", expr)) { + auto arg = Expr(expr); + auto internal_key = ParsePubkey(key_exp_index, arg, ParseScriptContext::P2TR, out, error); + if (!internal_key) return nullptr; + ++key_exp_index; + std::vector<std::unique_ptr<DescriptorImpl>> subscripts; //!< list of script subexpressions + std::vector<int> depths; //!< depth in the tree of each subexpression (same length subscripts) + if (expr.size()) { + if (!Const(",", expr)) { + error = strprintf("tr: expected ',', got '%c'", expr[0]); + return nullptr; + } + /** The path from the top of the tree to what we're currently processing. + * branches[i] == false: left branch in the i'th step from the top; true: right branch. + */ + std::vector<bool> branches; + // Loop over all provided scripts. In every iteration exactly one script will be processed. + // Use a do-loop because inside this if-branch we expect at least one script. + do { + // First process all open braces. + while (Const("{", expr)) { + branches.push_back(false); // new left branch + if (branches.size() > TAPROOT_CONTROL_MAX_NODE_COUNT) { + error = strprintf("tr() supports at most %i nesting levels", TAPROOT_CONTROL_MAX_NODE_COUNT); + return nullptr; + } + } + // Process the actual script expression. + auto sarg = Expr(expr); + subscripts.emplace_back(ParseScript(key_exp_index, sarg, ParseScriptContext::P2TR, out, error)); + if (!subscripts.back()) return nullptr; + depths.push_back(branches.size()); + // Process closing braces; one is expected for every right branch we were in. + while (branches.size() && branches.back()) { + if (!Const("}", expr)) { + error = strprintf("tr(): expected '}' after script expression"); + return nullptr; + } + branches.pop_back(); // move up one level after encountering '}' + } + // If after that, we're at the end of a left branch, expect a comma. + if (branches.size() && !branches.back()) { + if (!Const(",", expr)) { + error = strprintf("tr(): expected ',' after script expression"); + return nullptr; + } + branches.back() = true; // And now we're in a right branch. + } + } while (branches.size()); + // After we've explored a whole tree, we must be at the end of the expression. + if (expr.size()) { + error = strprintf("tr(): expected ')' after script expression"); + return nullptr; + } + } + assert(TaprootBuilder::ValidDepths(depths)); + return std::make_unique<TRDescriptor>(std::move(internal_key), std::move(subscripts), std::move(depths)); + } else if (Func("tr", expr)) { + error = "Can only have tr at top level"; + return nullptr; + } if (ctx == ParseScriptContext::TOP && Func("raw", expr)) { std::string str(expr.begin(), expr.end()); if (!IsHex(str)) { @@ -1084,7 +1227,7 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const std::unique_ptr<PubkeyProvider> InferPubkey(const CPubKey& pubkey, ParseScriptContext, const SigningProvider& provider) { - std::unique_ptr<PubkeyProvider> key_provider = std::make_unique<ConstPubkeyProvider>(0, pubkey); + std::unique_ptr<PubkeyProvider> key_provider = std::make_unique<ConstPubkeyProvider>(0, pubkey, false); KeyOriginInfo info; if (provider.GetKeyOrigin(pubkey.GetID(), info)) { return std::make_unique<OriginPubkeyProvider>(0, std::move(info), std::move(key_provider)); @@ -1092,18 +1235,42 @@ std::unique_ptr<PubkeyProvider> InferPubkey(const CPubKey& pubkey, ParseScriptCo return key_provider; } +std::unique_ptr<PubkeyProvider> InferXOnlyPubkey(const XOnlyPubKey& xkey, ParseScriptContext ctx, const SigningProvider& provider) +{ + unsigned char full_key[CPubKey::COMPRESSED_SIZE] = {0x02}; + std::copy(xkey.begin(), xkey.end(), full_key + 1); + CPubKey pubkey(full_key); + std::unique_ptr<PubkeyProvider> key_provider = std::make_unique<ConstPubkeyProvider>(0, pubkey, true); + KeyOriginInfo info; + if (provider.GetKeyOrigin(pubkey.GetID(), info)) { + return std::make_unique<OriginPubkeyProvider>(0, std::move(info), std::move(key_provider)); + } else { + full_key[0] = 0x03; + pubkey = CPubKey(full_key); + if (provider.GetKeyOrigin(pubkey.GetID(), info)) { + return std::make_unique<OriginPubkeyProvider>(0, std::move(info), std::move(key_provider)); + } + } + return key_provider; +} + std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptContext ctx, const SigningProvider& provider) { + if (ctx == ParseScriptContext::P2TR && script.size() == 34 && script[0] == 32 && script[33] == OP_CHECKSIG) { + XOnlyPubKey key{Span<const unsigned char>{script.data() + 1, script.data() + 33}}; + return std::make_unique<PKDescriptor>(InferXOnlyPubkey(key, ctx, provider)); + } + std::vector<std::vector<unsigned char>> data; TxoutType txntype = Solver(script, data); - if (txntype == TxoutType::PUBKEY) { + if (txntype == TxoutType::PUBKEY && (ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH)) { CPubKey pubkey(data[0]); if (pubkey.IsValid()) { return std::make_unique<PKDescriptor>(InferPubkey(pubkey, ctx, provider)); } } - if (txntype == TxoutType::PUBKEYHASH) { + if (txntype == TxoutType::PUBKEYHASH && (ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH)) { uint160 hash(data[0]); CKeyID keyid(hash); CPubKey pubkey; @@ -1111,7 +1278,7 @@ std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptCo return std::make_unique<PKHDescriptor>(InferPubkey(pubkey, ctx, provider)); } } - if (txntype == TxoutType::WITNESS_V0_KEYHASH && ctx != ParseScriptContext::P2WSH) { + if (txntype == TxoutType::WITNESS_V0_KEYHASH && (ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH)) { uint160 hash(data[0]); CKeyID keyid(hash); CPubKey pubkey; @@ -1119,7 +1286,7 @@ std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptCo return std::make_unique<WPKHDescriptor>(InferPubkey(pubkey, ctx, provider)); } } - if (txntype == TxoutType::MULTISIG) { + if (txntype == TxoutType::MULTISIG && (ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH)) { std::vector<std::unique_ptr<PubkeyProvider>> providers; for (size_t i = 1; i + 1 < data.size(); ++i) { CPubKey pubkey(data[i]); @@ -1136,7 +1303,7 @@ std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptCo if (sub) return std::make_unique<SHDescriptor>(std::move(sub)); } } - if (txntype == TxoutType::WITNESS_V0_SCRIPTHASH && ctx != ParseScriptContext::P2WSH) { + if (txntype == TxoutType::WITNESS_V0_SCRIPTHASH && (ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH)) { CScriptID scriptid; CRIPEMD160().Write(data[0].data(), data[0].size()).Finalize(scriptid.begin()); CScript subscript; @@ -1145,6 +1312,40 @@ std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptCo if (sub) return std::make_unique<WSHDescriptor>(std::move(sub)); } } + if (txntype == TxoutType::WITNESS_V1_TAPROOT && ctx == ParseScriptContext::TOP) { + // Extract x-only pubkey from output. + XOnlyPubKey pubkey; + std::copy(data[0].begin(), data[0].end(), pubkey.begin()); + // Request spending data. + TaprootSpendData tap; + if (provider.GetTaprootSpendData(pubkey, tap)) { + // If found, convert it back to tree form. + auto tree = InferTaprootTree(tap, pubkey); + if (tree) { + // If that works, try to infer subdescriptors for all leaves. + bool ok = true; + std::vector<std::unique_ptr<DescriptorImpl>> subscripts; //!< list of script subexpressions + std::vector<int> depths; //!< depth in the tree of each subexpression (same length subscripts) + for (const auto& [depth, script, leaf_ver] : *tree) { + std::unique_ptr<DescriptorImpl> subdesc; + if (leaf_ver == TAPROOT_LEAF_TAPSCRIPT) { + subdesc = InferScript(script, ParseScriptContext::P2TR, provider); + } + if (!subdesc) { + ok = false; + break; + } else { + subscripts.push_back(std::move(subdesc)); + depths.push_back(depth); + } + } + if (ok) { + auto key = InferXOnlyPubkey(tap.internal_key, ParseScriptContext::P2TR, provider); + return std::make_unique<TRDescriptor>(std::move(key), std::move(subscripts), std::move(depths)); + } + } + } + } CTxDestination dest; if (ExtractDestination(script, dest)) { @@ -1230,6 +1431,11 @@ void DescriptorCache::CacheDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_i xpubs[der_index] = xpub; } +void DescriptorCache::CacheLastHardenedExtPubKey(uint32_t key_exp_pos, const CExtPubKey& xpub) +{ + m_last_hardened_xpubs[key_exp_pos] = xpub; +} + bool DescriptorCache::GetCachedParentExtPubKey(uint32_t key_exp_pos, CExtPubKey& xpub) const { const auto& it = m_parent_xpubs.find(key_exp_pos); @@ -1248,6 +1454,55 @@ bool DescriptorCache::GetCachedDerivedExtPubKey(uint32_t key_exp_pos, uint32_t d return true; } +bool DescriptorCache::GetCachedLastHardenedExtPubKey(uint32_t key_exp_pos, CExtPubKey& xpub) const +{ + const auto& it = m_last_hardened_xpubs.find(key_exp_pos); + if (it == m_last_hardened_xpubs.end()) return false; + xpub = it->second; + return true; +} + +DescriptorCache DescriptorCache::MergeAndDiff(const DescriptorCache& other) +{ + DescriptorCache diff; + for (const auto& parent_xpub_pair : other.GetCachedParentExtPubKeys()) { + CExtPubKey xpub; + if (GetCachedParentExtPubKey(parent_xpub_pair.first, xpub)) { + if (xpub != parent_xpub_pair.second) { + throw std::runtime_error(std::string(__func__) + ": New cached parent xpub does not match already cached parent xpub"); + } + continue; + } + CacheParentExtPubKey(parent_xpub_pair.first, parent_xpub_pair.second); + diff.CacheParentExtPubKey(parent_xpub_pair.first, parent_xpub_pair.second); + } + for (const auto& derived_xpub_map_pair : other.GetCachedDerivedExtPubKeys()) { + for (const auto& derived_xpub_pair : derived_xpub_map_pair.second) { + CExtPubKey xpub; + if (GetCachedDerivedExtPubKey(derived_xpub_map_pair.first, derived_xpub_pair.first, xpub)) { + if (xpub != derived_xpub_pair.second) { + throw std::runtime_error(std::string(__func__) + ": New cached derived xpub does not match already cached derived xpub"); + } + continue; + } + CacheDerivedExtPubKey(derived_xpub_map_pair.first, derived_xpub_pair.first, derived_xpub_pair.second); + diff.CacheDerivedExtPubKey(derived_xpub_map_pair.first, derived_xpub_pair.first, derived_xpub_pair.second); + } + } + for (const auto& lh_xpub_pair : other.GetCachedLastHardenedExtPubKeys()) { + CExtPubKey xpub; + if (GetCachedLastHardenedExtPubKey(lh_xpub_pair.first, xpub)) { + if (xpub != lh_xpub_pair.second) { + throw std::runtime_error(std::string(__func__) + ": New cached last hardened xpub does not match already cached last hardened xpub"); + } + continue; + } + CacheLastHardenedExtPubKey(lh_xpub_pair.first, lh_xpub_pair.second); + diff.CacheLastHardenedExtPubKey(lh_xpub_pair.first, lh_xpub_pair.second); + } + return diff; +} + const ExtPubKeyMap DescriptorCache::GetCachedParentExtPubKeys() const { return m_parent_xpubs; @@ -1257,3 +1512,8 @@ const std::unordered_map<uint32_t, ExtPubKeyMap> DescriptorCache::GetCachedDeriv { return m_derived_xpubs; } + +const ExtPubKeyMap DescriptorCache::GetCachedLastHardenedExtPubKeys() const +{ + return m_last_hardened_xpubs; +} diff --git a/src/script/descriptor.h b/src/script/descriptor.h index 332ae2f230..ecd7c4eea5 100644 --- a/src/script/descriptor.h +++ b/src/script/descriptor.h @@ -22,6 +22,8 @@ private: std::unordered_map<uint32_t, ExtPubKeyMap> m_derived_xpubs; /** Map key expression index -> parent xpub */ ExtPubKeyMap m_parent_xpubs; + /** Map key expression index -> last hardened xpub */ + ExtPubKeyMap m_last_hardened_xpubs; public: /** Cache a parent xpub @@ -50,11 +52,30 @@ public: * @param[in] xpub The CExtPubKey to get from cache */ bool GetCachedDerivedExtPubKey(uint32_t key_exp_pos, uint32_t der_index, CExtPubKey& xpub) const; + /** Cache a last hardened xpub + * + * @param[in] key_exp_pos Position of the key expression within the descriptor + * @param[in] xpub The CExtPubKey to cache + */ + void CacheLastHardenedExtPubKey(uint32_t key_exp_pos, const CExtPubKey& xpub); + /** Retrieve a cached last hardened xpub + * + * @param[in] key_exp_pos Position of the key expression within the descriptor + * @param[in] xpub The CExtPubKey to get from cache + */ + bool GetCachedLastHardenedExtPubKey(uint32_t key_exp_pos, 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; + /** Retrieve all cached last hardened xpubs */ + const ExtPubKeyMap GetCachedLastHardenedExtPubKeys() const; + + /** Combine another DescriptorCache into this one. + * Returns a cache containing the items from the other cache unknown to current cache + */ + DescriptorCache MergeAndDiff(const DescriptorCache& other); }; /** \brief Interface for parsed descriptor objects. @@ -94,7 +115,7 @@ struct Descriptor { virtual bool ToPrivateString(const SigningProvider& provider, std::string& out) const = 0; /** Convert the descriptor to a normalized string. Normalized descriptors have the xpub at the last hardened step. This fails if the provided provider does not have the private keys to derive that xpub. */ - virtual bool ToNormalizedString(const SigningProvider& provider, std::string& out, bool priv) const = 0; + virtual bool ToNormalizedString(const SigningProvider& provider, std::string& out, const DescriptorCache* cache = nullptr) const = 0; /** Expand a descriptor at a specified position. * diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp index dc0f165be0..dd7c0a4a05 100644 --- a/src/script/interpreter.cpp +++ b/src/script/interpreter.cpp @@ -1420,7 +1420,7 @@ uint256 GetSpentScriptsSHA256(const std::vector<CTxOut>& outputs_spent) } // namespace template <class T> -void PrecomputedTransactionData::Init(const T& txTo, std::vector<CTxOut>&& spent_outputs) +void PrecomputedTransactionData::Init(const T& txTo, std::vector<CTxOut>&& spent_outputs, bool force) { assert(!m_spent_outputs_ready); @@ -1431,9 +1431,9 @@ void PrecomputedTransactionData::Init(const T& txTo, std::vector<CTxOut>&& spent } // Determine which precomputation-impacting features this transaction uses. - bool uses_bip143_segwit = false; - bool uses_bip341_taproot = false; - for (size_t inpos = 0; inpos < txTo.vin.size(); ++inpos) { + bool uses_bip143_segwit = force; + bool uses_bip341_taproot = force; + for (size_t inpos = 0; inpos < txTo.vin.size() && !(uses_bip143_segwit && uses_bip341_taproot); ++inpos) { if (!txTo.vin[inpos].scriptWitness.IsNull()) { if (m_spent_outputs_ready && m_spent_outputs[inpos].scriptPubKey.size() == 2 + WITNESS_V1_TAPROOT_SIZE && m_spent_outputs[inpos].scriptPubKey[0] == OP_1) { @@ -1478,15 +1478,14 @@ PrecomputedTransactionData::PrecomputedTransactionData(const T& txTo) } // explicit instantiation -template void PrecomputedTransactionData::Init(const CTransaction& txTo, std::vector<CTxOut>&& spent_outputs); -template void PrecomputedTransactionData::Init(const CMutableTransaction& txTo, std::vector<CTxOut>&& spent_outputs); +template void PrecomputedTransactionData::Init(const CTransaction& txTo, std::vector<CTxOut>&& spent_outputs, bool force); +template void PrecomputedTransactionData::Init(const CMutableTransaction& txTo, std::vector<CTxOut>&& spent_outputs, bool force); template PrecomputedTransactionData::PrecomputedTransactionData(const CTransaction& txTo); template PrecomputedTransactionData::PrecomputedTransactionData(const CMutableTransaction& txTo); static const CHashWriter HASHER_TAPSIGHASH = TaggedHash("TapSighash"); -static const CHashWriter HASHER_TAPLEAF = TaggedHash("TapLeaf"); -static const CHashWriter HASHER_TAPBRANCH = TaggedHash("TapBranch"); -static const CHashWriter HASHER_TAPTWEAK = TaggedHash("TapTweak"); +const CHashWriter HASHER_TAPLEAF = TaggedHash("TapLeaf"); +const CHashWriter HASHER_TAPBRANCH = TaggedHash("TapBranch"); static bool HandleMissingData(MissingDataBehavior mdb) { @@ -1712,7 +1711,7 @@ bool GenericTransactionSignatureChecker<T>::CheckSchnorrSignature(Span<const uns if (hashtype == SIGHASH_DEFAULT) return set_error(serror, SCRIPT_ERR_SCHNORR_SIG_HASHTYPE); } uint256 sighash; - assert(this->txdata); + if (!this->txdata) return HandleMissingData(m_mdb); if (!SignatureHashSchnorr(sighash, execdata, *txTo, nIn, hashtype, sigversion, *this->txdata, m_mdb)) { return set_error(serror, SCRIPT_ERR_SCHNORR_SIG_HASHTYPE); } @@ -1741,9 +1740,9 @@ bool GenericTransactionSignatureChecker<T>::CheckLockTime(const CScriptNum& nLoc if (nLockTime > (int64_t)txTo->nLockTime) return false; - // Finally the nLockTime feature can be disabled and thus - // CHECKLOCKTIMEVERIFY bypassed if every txin has been - // finalized by setting nSequence to maxint. The + // Finally the nLockTime feature can be disabled in IsFinalTx() + // and thus CHECKLOCKTIMEVERIFY bypassed if every txin has + // been finalized by setting nSequence to maxint. The // transaction would be allowed into the blockchain, making // the opcode ineffective. // @@ -1808,16 +1807,16 @@ bool GenericTransactionSignatureChecker<T>::CheckSequence(const CScriptNum& nSeq template class GenericTransactionSignatureChecker<CTransaction>; template class GenericTransactionSignatureChecker<CMutableTransaction>; -static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CScript& scriptPubKey, unsigned int flags, SigVersion sigversion, const BaseSignatureChecker& checker, ScriptExecutionData& execdata, ScriptError* serror) +static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CScript& exec_script, unsigned int flags, SigVersion sigversion, const BaseSignatureChecker& checker, ScriptExecutionData& execdata, ScriptError* serror) { std::vector<valtype> stack{stack_span.begin(), stack_span.end()}; if (sigversion == SigVersion::TAPSCRIPT) { // OP_SUCCESSx processing overrides everything, including stack element size limits - CScript::const_iterator pc = scriptPubKey.begin(); - while (pc < scriptPubKey.end()) { + CScript::const_iterator pc = exec_script.begin(); + while (pc < exec_script.end()) { opcodetype opcode; - if (!scriptPubKey.GetOp(pc, opcode)) { + if (!exec_script.GetOp(pc, opcode)) { // Note how this condition would not be reached if an unknown OP_SUCCESSx was found return set_error(serror, SCRIPT_ERR_BAD_OPCODE); } @@ -1840,7 +1839,7 @@ static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CS } // Run the script interpreter. - if (!EvalScript(stack, scriptPubKey, flags, checker, sigversion, execdata, serror)) return false; + if (!EvalScript(stack, exec_script, flags, checker, sigversion, execdata, serror)) return false; // Scripts inside witness implicitly require cleanstack behaviour if (stack.size() != 1) return set_error(serror, SCRIPT_ERR_CLEANSTACK); @@ -1848,16 +1847,14 @@ static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CS return true; } -static bool VerifyTaprootCommitment(const std::vector<unsigned char>& control, const std::vector<unsigned char>& program, const CScript& script, uint256& tapleaf_hash) +uint256 ComputeTapleafHash(uint8_t leaf_version, const CScript& script) +{ + return (CHashWriter(HASHER_TAPLEAF) << leaf_version << script).GetSHA256(); +} + +uint256 ComputeTaprootMerkleRoot(Span<const unsigned char> control, const uint256& tapleaf_hash) { const int path_len = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE; - //! The internal pubkey (x-only, so no Y coordinate parity). - const XOnlyPubKey p{uint256(std::vector<unsigned char>(control.begin() + 1, control.begin() + TAPROOT_CONTROL_BASE_SIZE))}; - //! The output pubkey (taken from the scriptPubKey). - const XOnlyPubKey q{uint256(program)}; - // Compute the tapleaf hash. - tapleaf_hash = (CHashWriter(HASHER_TAPLEAF) << uint8_t(control[0] & TAPROOT_LEAF_MASK) << script).GetSHA256(); - // Compute the Merkle root from the leaf and the provided path. uint256 k = tapleaf_hash; for (int i = 0; i < path_len; ++i) { CHashWriter ss_branch{HASHER_TAPBRANCH}; @@ -1869,10 +1866,21 @@ static bool VerifyTaprootCommitment(const std::vector<unsigned char>& control, c } k = ss_branch.GetSHA256(); } - // Compute the tweak from the Merkle root and the internal pubkey. - k = (CHashWriter(HASHER_TAPTWEAK) << MakeSpan(p) << k).GetSHA256(); + return k; +} + +static bool VerifyTaprootCommitment(const std::vector<unsigned char>& control, const std::vector<unsigned char>& program, const uint256& tapleaf_hash) +{ + assert(control.size() >= TAPROOT_CONTROL_BASE_SIZE); + assert(program.size() >= uint256::size()); + //! The internal pubkey (x-only, so no Y coordinate parity). + const XOnlyPubKey p{uint256(std::vector<unsigned char>(control.begin() + 1, control.begin() + TAPROOT_CONTROL_BASE_SIZE))}; + //! The output pubkey (taken from the scriptPubKey). + const XOnlyPubKey q{uint256(program)}; + // Compute the Merkle root from the leaf and the provided path. + const uint256 merkle_root = ComputeTaprootMerkleRoot(control, tapleaf_hash); // Verify that the output pubkey matches the tweaked internal pubkey, after correcting for parity. - return q.CheckPayToContract(p, k, control[0] & 1); + return q.CheckTapTweak(p, merkle_root, control[0] & 1); } static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion, const std::vector<unsigned char>& program, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror, bool is_p2sh) @@ -1932,7 +1940,8 @@ static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion, if (control.size() < TAPROOT_CONTROL_BASE_SIZE || control.size() > TAPROOT_CONTROL_MAX_SIZE || ((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE) != 0) { return set_error(serror, SCRIPT_ERR_TAPROOT_WRONG_CONTROL_SIZE); } - if (!VerifyTaprootCommitment(control, program, exec_script, execdata.m_tapleaf_hash)) { + execdata.m_tapleaf_hash = ComputeTapleafHash(control[0] & TAPROOT_LEAF_MASK, exec_script); + if (!VerifyTaprootCommitment(control, program, execdata.m_tapleaf_hash)) { return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH); } execdata.m_tapleaf_hash_init = true; diff --git a/src/script/interpreter.h b/src/script/interpreter.h index 212de17c7b..93136a0b79 100644 --- a/src/script/interpreter.h +++ b/src/script/interpreter.h @@ -6,6 +6,7 @@ #ifndef BITCOIN_SCRIPT_INTERPRETER_H #define BITCOIN_SCRIPT_INTERPRETER_H +#include <hash.h> #include <script/script_error.h> #include <span.h> #include <primitives/transaction.h> @@ -38,8 +39,7 @@ enum * All flags are intended to be soft forks: the set of acceptable scripts under * flags (A | B) is a subset of the acceptable scripts under flag (A). */ -enum -{ +enum : uint32_t { SCRIPT_VERIFY_NONE = 0, // Evaluate P2SH subscripts (BIP16). @@ -139,6 +139,10 @@ enum // Making unknown public key versions (in BIP 342 scripts) non-standard SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_PUBKEYTYPE = (1U << 20), + + // Constants to point to the highest flag in use. Add new flags above this line. + // + SCRIPT_VERIFY_END_MARKER }; bool CheckSignatureEncoding(const std::vector<unsigned char> &vchSig, unsigned int flags, ScriptError* serror); @@ -167,7 +171,7 @@ struct PrecomputedTransactionData PrecomputedTransactionData() = default; template <class T> - void Init(const T& tx, std::vector<CTxOut>&& spent_outputs); + void Init(const T& tx, std::vector<CTxOut>&& spent_outputs, bool force = false); template <class T> explicit PrecomputedTransactionData(const T& tx); @@ -218,6 +222,9 @@ static constexpr size_t TAPROOT_CONTROL_NODE_SIZE = 32; static constexpr size_t TAPROOT_CONTROL_MAX_NODE_COUNT = 128; static constexpr size_t TAPROOT_CONTROL_MAX_SIZE = TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * TAPROOT_CONTROL_MAX_NODE_COUNT; +extern const CHashWriter HASHER_TAPLEAF; //!< Hasher with tag "TapLeaf" pre-fed to it. +extern const CHashWriter HASHER_TAPBRANCH; //!< Hasher with tag "TapBranch" pre-fed to it. + template <class T> uint256 SignatureHash(const CScript& scriptCode, const T& txTo, unsigned int nIn, int nHashType, const CAmount& amount, SigVersion sigversion, const PrecomputedTransactionData* cache = nullptr); @@ -256,6 +263,9 @@ enum class MissingDataBehavior FAIL, //!< Just act as if the signature was invalid }; +template<typename T> +bool SignatureHashSchnorr(uint256& hash_out, const ScriptExecutionData& execdata, const T& tx_to, uint32_t in_pos, uint8_t hash_type, SigVersion sigversion, const PrecomputedTransactionData& cache, MissingDataBehavior mdb); + template <class T> class GenericTransactionSignatureChecker : public BaseSignatureChecker { @@ -310,6 +320,12 @@ public: } }; +/** Compute the BIP341 tapleaf hash from leaf version & script. */ +uint256 ComputeTapleafHash(uint8_t leaf_version, const CScript& script); +/** Compute the BIP341 taproot script tree Merkle root from control block and leaf hash. + * Requires control block to have valid length (33 + k*32, with k in {0,1,..,128}). */ +uint256 ComputeTaprootMerkleRoot(Span<const unsigned char> control, const uint256& tapleaf_hash); + bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* error = nullptr); bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* error = nullptr); bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CScriptWitness* witness, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror = nullptr); diff --git a/src/script/sign.cpp b/src/script/sign.cpp index da0092f9e3..7864e690d8 100644 --- a/src/script/sign.cpp +++ b/src/script/sign.cpp @@ -11,13 +11,28 @@ #include <script/signingprovider.h> #include <script/standard.h> #include <uint256.h> +#include <util/vector.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, MissingDataBehavior::FAIL) {} +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, MissingDataBehavior::FAIL), + m_txdata(nullptr) +{ +} + +MutableTransactionSignatureCreator::MutableTransactionSignatureCreator(const CMutableTransaction* txToIn, unsigned int nInIn, const CAmount& amountIn, const PrecomputedTransactionData* txdata, int nHashTypeIn) + : txTo(txToIn), nIn(nInIn), nHashType(nHashTypeIn), amount(amountIn), + checker(txdata ? MutableTransactionSignatureChecker(txTo, nIn, amount, *txdata, MissingDataBehavior::FAIL) : + MutableTransactionSignatureChecker(txTo, nIn, amount, MissingDataBehavior::FAIL)), + m_txdata(txdata) +{ +} bool MutableTransactionSignatureCreator::CreateSig(const SigningProvider& provider, std::vector<unsigned char>& vchSig, const CKeyID& address, const CScript& scriptCode, SigVersion sigversion) const { + assert(sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0); + CKey key; if (!provider.GetKey(address, key)) return false; @@ -26,13 +41,61 @@ bool MutableTransactionSignatureCreator::CreateSig(const SigningProvider& provid if (sigversion == SigVersion::WITNESS_V0 && !key.IsCompressed()) return false; - // Signing for witness scripts needs the amount. - if (sigversion == SigVersion::WITNESS_V0 && amount < 0) return false; + // Signing without known amount does not work in witness scripts. + if (sigversion == SigVersion::WITNESS_V0 && !MoneyRange(amount)) return false; + + // BASE/WITNESS_V0 signatures don't support explicit SIGHASH_DEFAULT, use SIGHASH_ALL instead. + const int hashtype = nHashType == SIGHASH_DEFAULT ? SIGHASH_ALL : nHashType; - uint256 hash = SignatureHash(scriptCode, *txTo, nIn, nHashType, amount, sigversion); + uint256 hash = SignatureHash(scriptCode, *txTo, nIn, hashtype, amount, sigversion, m_txdata); if (!key.Sign(hash, vchSig)) return false; - vchSig.push_back((unsigned char)nHashType); + vchSig.push_back((unsigned char)hashtype); + return true; +} + +bool MutableTransactionSignatureCreator::CreateSchnorrSig(const SigningProvider& provider, std::vector<unsigned char>& sig, const XOnlyPubKey& pubkey, const uint256* leaf_hash, const uint256* merkle_root, SigVersion sigversion) const +{ + assert(sigversion == SigVersion::TAPROOT || sigversion == SigVersion::TAPSCRIPT); + + CKey key; + { + // For now, use the old full pubkey-based key derivation logic. As it indexed by + // Hash160(full pubkey), we need to try both a version prefixed with 0x02, and one + // with 0x03. + unsigned char b[33] = {0x02}; + std::copy(pubkey.begin(), pubkey.end(), b + 1); + CPubKey fullpubkey; + fullpubkey.Set(b, b + 33); + CKeyID keyid = fullpubkey.GetID(); + if (!provider.GetKey(keyid, key)) { + b[0] = 0x03; + fullpubkey.Set(b, b + 33); + CKeyID keyid = fullpubkey.GetID(); + if (!provider.GetKey(keyid, key)) return false; + } + } + + // BIP341/BIP342 signing needs lots of precomputed transaction data. While some + // (non-SIGHASH_DEFAULT) sighash modes exist that can work with just some subset + // of data present, for now, only support signing when everything is provided. + if (!m_txdata || !m_txdata->m_bip341_taproot_ready || !m_txdata->m_spent_outputs_ready) return false; + + ScriptExecutionData execdata; + execdata.m_annex_init = true; + execdata.m_annex_present = false; // Only support annex-less signing for now. + if (sigversion == SigVersion::TAPSCRIPT) { + execdata.m_codeseparator_pos_init = true; + execdata.m_codeseparator_pos = 0xFFFFFFFF; // Only support non-OP_CODESEPARATOR BIP342 signing for now. + if (!leaf_hash) return false; // BIP342 signing needs leaf hash. + execdata.m_tapleaf_hash_init = true; + execdata.m_tapleaf_hash = *leaf_hash; + } + uint256 hash; + if (!SignatureHashSchnorr(hash, execdata, *txTo, nIn, nHashType, sigversion, *m_txdata, MissingDataBehavior::FAIL)) return false; + sig.resize(64); + if (!key.SignSchnorr(hash, sig, merkle_root, nullptr)) return false; + if (nHashType) sig.push_back(nHashType); return true; } @@ -92,6 +155,86 @@ static bool CreateSig(const BaseSignatureCreator& creator, SignatureData& sigdat return false; } +static bool CreateTaprootScriptSig(const BaseSignatureCreator& creator, SignatureData& sigdata, const SigningProvider& provider, std::vector<unsigned char>& sig_out, const XOnlyPubKey& pubkey, const uint256& leaf_hash, SigVersion sigversion) +{ + auto lookup_key = std::make_pair(pubkey, leaf_hash); + auto it = sigdata.taproot_script_sigs.find(lookup_key); + if (it != sigdata.taproot_script_sigs.end()) { + sig_out = it->second; + } + if (creator.CreateSchnorrSig(provider, sig_out, pubkey, &leaf_hash, nullptr, sigversion)) { + sigdata.taproot_script_sigs[lookup_key] = sig_out; + return true; + } + return false; +} + +static bool SignTaprootScript(const SigningProvider& provider, const BaseSignatureCreator& creator, SignatureData& sigdata, int leaf_version, const CScript& script, std::vector<valtype>& result) +{ + // Only BIP342 tapscript signing is supported for now. + if (leaf_version != TAPROOT_LEAF_TAPSCRIPT) return false; + SigVersion sigversion = SigVersion::TAPSCRIPT; + + uint256 leaf_hash = (CHashWriter(HASHER_TAPLEAF) << uint8_t(leaf_version) << script).GetSHA256(); + + // <xonly pubkey> OP_CHECKSIG + if (script.size() == 34 && script[33] == OP_CHECKSIG && script[0] == 0x20) { + XOnlyPubKey pubkey(MakeSpan(script).subspan(1, 32)); + std::vector<unsigned char> sig; + if (CreateTaprootScriptSig(creator, sigdata, provider, sig, pubkey, leaf_hash, sigversion)) { + result = Vector(std::move(sig)); + return true; + } + } + + return false; +} + +static bool SignTaproot(const SigningProvider& provider, const BaseSignatureCreator& creator, const WitnessV1Taproot& output, SignatureData& sigdata, std::vector<valtype>& result) +{ + TaprootSpendData spenddata; + + // Gather information about this output. + if (provider.GetTaprootSpendData(output, spenddata)) { + sigdata.tr_spenddata.Merge(spenddata); + } + + // Try key path spending. + { + std::vector<unsigned char> sig; + if (sigdata.taproot_key_path_sig.size() == 0) { + if (creator.CreateSchnorrSig(provider, sig, spenddata.internal_key, nullptr, &spenddata.merkle_root, SigVersion::TAPROOT)) { + sigdata.taproot_key_path_sig = sig; + } + } + if (sigdata.taproot_key_path_sig.size()) { + result = Vector(sigdata.taproot_key_path_sig); + return true; + } + } + + // Try script path spending. + std::vector<std::vector<unsigned char>> smallest_result_stack; + for (const auto& [key, control_blocks] : sigdata.tr_spenddata.scripts) { + const auto& [script, leaf_ver] = key; + std::vector<std::vector<unsigned char>> result_stack; + if (SignTaprootScript(provider, creator, sigdata, leaf_ver, script, result_stack)) { + result_stack.emplace_back(std::begin(script), std::end(script)); // Push the script + result_stack.push_back(*control_blocks.begin()); // Push the smallest control block + if (smallest_result_stack.size() == 0 || + GetSerializeSize(result_stack, PROTOCOL_VERSION) < GetSerializeSize(smallest_result_stack, PROTOCOL_VERSION)) { + smallest_result_stack = std::move(result_stack); + } + } + } + if (smallest_result_stack.size() != 0) { + result = std::move(smallest_result_stack); + return true; + } + + return false; +} + /** * Sign scriptPubKey using signature made with creator. * Signatures are returned in scriptSigRet (or returns false if scriptPubKey can't be signed), @@ -113,7 +256,6 @@ static bool SignStep(const SigningProvider& provider, const BaseSignatureCreator case TxoutType::NONSTANDARD: case TxoutType::NULL_DATA: case TxoutType::WITNESS_UNKNOWN: - case TxoutType::WITNESS_V1_TAPROOT: return false; case TxoutType::PUBKEY: if (!CreateSig(creator, sigdata, provider, sig, CPubKey(vSolutions[0]), scriptPubKey, sigversion)) return false; @@ -175,6 +317,9 @@ static bool SignStep(const SigningProvider& provider, const BaseSignatureCreator // Could not find witnessScript, add to missing sigdata.missing_witness_script = uint256(vSolutions[0]); return false; + + case TxoutType::WITNESS_V1_TAPROOT: + return SignTaproot(provider, creator, WitnessV1Taproot(XOnlyPubKey{vSolutions[0]}), sigdata, ret); } // no default case, so the compiler can warn about missing cases assert(false); } @@ -205,7 +350,6 @@ bool ProduceSignature(const SigningProvider& provider, const BaseSignatureCreato bool solved = SignStep(provider, creator, fromPubKey, result, whichType, SigVersion::BASE, sigdata); bool P2SH = false; CScript subscript; - sigdata.scriptWitness.stack.clear(); if (solved && whichType == TxoutType::SCRIPTHASH) { @@ -238,10 +382,17 @@ bool ProduceSignature(const SigningProvider& provider, const BaseSignatureCreato sigdata.scriptWitness.stack = result; sigdata.witness = true; result.clear(); + } else if (whichType == TxoutType::WITNESS_V1_TAPROOT && !P2SH) { + sigdata.witness = true; + if (solved) { + sigdata.scriptWitness.stack = std::move(result); + } + result.clear(); } else if (solved && whichType == TxoutType::WITNESS_UNKNOWN) { sigdata.witness = true; } + if (!sigdata.witness) sigdata.scriptWitness.stack.clear(); if (P2SH) { result.push_back(std::vector<unsigned char>(subscript.begin(), subscript.end())); } @@ -402,6 +553,7 @@ class DummySignatureChecker final : public BaseSignatureChecker public: DummySignatureChecker() {} bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override { return true; } + bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, const ScriptExecutionData& execdata, ScriptError* serror) const override { return true; } }; const DummySignatureChecker DUMMY_CHECKER; @@ -427,6 +579,11 @@ public: vchSig[6 + m_r_len + m_s_len] = SIGHASH_ALL; return true; } + bool CreateSchnorrSig(const SigningProvider& provider, std::vector<unsigned char>& sig, const XOnlyPubKey& pubkey, const uint256* leaf_hash, const uint256* tweak, SigVersion sigversion) const override + { + sig.assign(64, '\000'); + return true; + } }; } @@ -455,15 +612,18 @@ bool IsSolvable(const SigningProvider& provider, const CScript& script) bool IsSegWitOutput(const SigningProvider& provider, const CScript& script) { - std::vector<valtype> solutions; - auto whichtype = Solver(script, solutions); - if (whichtype == TxoutType::WITNESS_V0_SCRIPTHASH || whichtype == TxoutType::WITNESS_V0_KEYHASH || whichtype == TxoutType::WITNESS_UNKNOWN) return true; - if (whichtype == TxoutType::SCRIPTHASH) { - auto h160 = uint160(solutions[0]); - CScript subscript; - if (provider.GetCScript(CScriptID{h160}, subscript)) { - whichtype = Solver(subscript, solutions); - if (whichtype == TxoutType::WITNESS_V0_SCRIPTHASH || whichtype == TxoutType::WITNESS_V0_KEYHASH || whichtype == TxoutType::WITNESS_UNKNOWN) return true; + int version; + valtype program; + if (script.IsWitnessProgram(version, program)) return true; + if (script.IsPayToScriptHash()) { + std::vector<valtype> solutions; + auto whichtype = Solver(script, solutions); + if (whichtype == TxoutType::SCRIPTHASH) { + auto h160 = uint160(solutions[0]); + CScript subscript; + if (provider.GetCScript(CScriptID{h160}, subscript)) { + if (subscript.IsWitnessProgram(version, program)) return true; + } } } return false; @@ -476,6 +636,26 @@ bool SignTransaction(CMutableTransaction& mtx, const SigningProvider* keystore, // Use CTransaction for the constant parts of the // transaction to avoid rehashing. const CTransaction txConst(mtx); + + PrecomputedTransactionData txdata; + std::vector<CTxOut> spent_outputs; + spent_outputs.resize(mtx.vin.size()); + bool have_all_spent_outputs = true; + 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()) { + have_all_spent_outputs = false; + } else { + spent_outputs[i] = CTxOut(coin->second.out.nValue, coin->second.out.scriptPubKey); + } + } + if (have_all_spent_outputs) { + txdata.Init(txConst, std::move(spent_outputs), true); + } else { + txdata.Init(txConst, {}, true); + } + // Sign what we can: for (unsigned int i = 0; i < mtx.vin.size(); i++) { CTxIn& txin = mtx.vin[i]; @@ -490,7 +670,7 @@ bool SignTransaction(CMutableTransaction& mtx, const SigningProvider* keystore, 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); + ProduceSignature(*keystore, MutableTransactionSignatureCreator(&mtx, i, amount, &txdata, nHashType), prevPubKey, sigdata); } UpdateInput(txin, sigdata); @@ -502,7 +682,7 @@ bool SignTransaction(CMutableTransaction& mtx, const SigningProvider* keystore, } ScriptError serror = SCRIPT_ERR_OK; - if (!VerifyScript(txin.scriptSig, prevPubKey, &txin.scriptWitness, STANDARD_SCRIPT_VERIFY_FLAGS, TransactionSignatureChecker(&txConst, i, amount, MissingDataBehavior::FAIL), &serror)) { + if (!VerifyScript(txin.scriptSig, prevPubKey, &txin.scriptWitness, STANDARD_SCRIPT_VERIFY_FLAGS, TransactionSignatureChecker(&txConst, i, amount, txdata, MissingDataBehavior::FAIL), &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)"; diff --git a/src/script/sign.h b/src/script/sign.h index a1cfe1574d..b4e7318892 100644 --- a/src/script/sign.h +++ b/src/script/sign.h @@ -11,13 +11,13 @@ #include <pubkey.h> #include <script/interpreter.h> #include <script/keyorigin.h> +#include <script/standard.h> #include <span.h> #include <streams.h> class CKey; class CKeyID; class CScript; -class CScriptID; class CTransaction; class SigningProvider; @@ -31,6 +31,7 @@ public: /** Create a singular (non-script) signature. */ virtual bool CreateSig(const SigningProvider& provider, std::vector<unsigned char>& vchSig, const CKeyID& keyid, const CScript& scriptCode, SigVersion sigversion) const =0; + virtual bool CreateSchnorrSig(const SigningProvider& provider, std::vector<unsigned char>& sig, const XOnlyPubKey& pubkey, const uint256* leaf_hash, const uint256* merkle_root, SigVersion sigversion) const =0; }; /** A signature creator for transactions. */ @@ -40,11 +41,14 @@ class MutableTransactionSignatureCreator : public BaseSignatureCreator { int nHashType; CAmount amount; const MutableTransactionSignatureChecker checker; + const PrecomputedTransactionData* m_txdata; public: MutableTransactionSignatureCreator(const CMutableTransaction* txToIn, unsigned int nInIn, const CAmount& amountIn, int nHashTypeIn = SIGHASH_ALL); + MutableTransactionSignatureCreator(const CMutableTransaction* txToIn, unsigned int nInIn, const CAmount& amountIn, const PrecomputedTransactionData* txdata, int nHashTypeIn = SIGHASH_ALL); const BaseSignatureChecker& Checker() const override { return checker; } bool CreateSig(const SigningProvider& provider, std::vector<unsigned char>& vchSig, const CKeyID& keyid, const CScript& scriptCode, SigVersion sigversion) const override; + bool CreateSchnorrSig(const SigningProvider& provider, std::vector<unsigned char>& sig, const XOnlyPubKey& pubkey, const uint256* leaf_hash, const uint256* merkle_root, SigVersion sigversion) const override; }; /** A signature creator that just produces 71-byte empty signatures. */ @@ -64,8 +68,11 @@ struct SignatureData { CScript redeem_script; ///< The redeemScript (if any) for the input CScript witness_script; ///< The witnessScript (if any) for the input. witnessScripts are used in P2WSH outputs. CScriptWitness scriptWitness; ///< The scriptWitness of an input. Contains complete signatures or the traditional partial signatures format. scriptWitness is part of a transaction input per BIP 144. + TaprootSpendData tr_spenddata; ///< Taproot spending data. std::map<CKeyID, SigPair> signatures; ///< BIP 174 style partial signatures for the input. May contain all signatures necessary for producing a final scriptSig or scriptWitness. std::map<CKeyID, std::pair<CPubKey, KeyOriginInfo>> misc_pubkeys; + std::vector<unsigned char> taproot_key_path_sig; /// Schnorr signature for key path spending + std::map<std::pair<XOnlyPubKey, uint256>, std::vector<unsigned char>> taproot_script_sigs; ///< (Partial) schnorr signatures, indexed by XOnlyPubKey and leaf_hash. std::vector<CKeyID> missing_pubkeys; ///< KeyIDs of pubkeys which could not be found std::vector<CKeyID> missing_sigs; ///< KeyIDs of pubkeys for signatures which could not be found uint160 missing_redeem_script; ///< ScriptID of the missing redeemScript (if any) diff --git a/src/script/signingprovider.cpp b/src/script/signingprovider.cpp index 9781ec32af..b80fbe22ce 100644 --- a/src/script/signingprovider.cpp +++ b/src/script/signingprovider.cpp @@ -44,6 +44,11 @@ bool HidingSigningProvider::GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& inf return m_provider->GetKeyOrigin(keyid, info); } +bool HidingSigningProvider::GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const +{ + return m_provider->GetTaprootSpendData(output_key, spenddata); +} + 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::GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const @@ -54,6 +59,10 @@ bool FlatSigningProvider::GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) return ret; } bool FlatSigningProvider::GetKey(const CKeyID& keyid, CKey& key) const { return LookupHelper(keys, keyid, key); } +bool FlatSigningProvider::GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const +{ + return LookupHelper(tr_spenddata, output_key, spenddata); +} FlatSigningProvider Merge(const FlatSigningProvider& a, const FlatSigningProvider& b) { @@ -66,6 +75,10 @@ FlatSigningProvider Merge(const FlatSigningProvider& a, const FlatSigningProvide ret.keys.insert(b.keys.begin(), b.keys.end()); ret.origins = a.origins; ret.origins.insert(b.origins.begin(), b.origins.end()); + ret.tr_spenddata = a.tr_spenddata; + for (const auto& [output_key, spenddata] : b.tr_spenddata) { + ret.tr_spenddata[output_key].Merge(spenddata); + } return ret; } diff --git a/src/script/signingprovider.h b/src/script/signingprovider.h index 76f31d2f6f..939ae10622 100644 --- a/src/script/signingprovider.h +++ b/src/script/signingprovider.h @@ -25,6 +25,7 @@ public: virtual bool GetKey(const CKeyID &address, CKey& key) const { return false; } virtual bool HaveKey(const CKeyID &address) const { return false; } virtual bool GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const { return false; } + virtual bool GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const { return false; } }; extern const SigningProvider& DUMMY_SIGNING_PROVIDER; @@ -42,6 +43,7 @@ public: bool GetPubKey(const CKeyID& keyid, CPubKey& pubkey) const override; bool GetKey(const CKeyID& keyid, CKey& key) const override; bool GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const override; + bool GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const override; }; struct FlatSigningProvider final : public SigningProvider @@ -50,11 +52,13 @@ struct FlatSigningProvider final : public SigningProvider std::map<CKeyID, CPubKey> pubkeys; std::map<CKeyID, std::pair<CPubKey, KeyOriginInfo>> origins; std::map<CKeyID, CKey> keys; + std::map<XOnlyPubKey, TaprootSpendData> tr_spenddata; /** Map from output key to spend data. */ bool GetCScript(const CScriptID& scriptid, CScript& script) const override; bool GetPubKey(const CKeyID& keyid, CPubKey& pubkey) const override; bool GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const override; bool GetKey(const CKeyID& keyid, CKey& key) const override; + bool GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const override; }; FlatSigningProvider Merge(const FlatSigningProvider& a, const FlatSigningProvider& b); diff --git a/src/script/standard.cpp b/src/script/standard.cpp index 364fac3c84..b8349bb9ab 100644 --- a/src/script/standard.cpp +++ b/src/script/standard.cpp @@ -6,8 +6,11 @@ #include <script/standard.h> #include <crypto/sha256.h> +#include <hash.h> #include <pubkey.h> +#include <script/interpreter.h> #include <script/script.h> +#include <util/strencodings.h> #include <string> @@ -155,15 +158,14 @@ TxoutType Solver(const CScript& scriptPubKey, std::vector<std::vector<unsigned c std::vector<unsigned char> witnessprogram; if (scriptPubKey.IsWitnessProgram(witnessversion, witnessprogram)) { if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_KEYHASH_SIZE) { - vSolutionsRet.push_back(witnessprogram); + vSolutionsRet.push_back(std::move(witnessprogram)); return TxoutType::WITNESS_V0_KEYHASH; } if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_SCRIPTHASH_SIZE) { - vSolutionsRet.push_back(witnessprogram); + vSolutionsRet.push_back(std::move(witnessprogram)); return TxoutType::WITNESS_V0_SCRIPTHASH; } if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE) { - vSolutionsRet.push_back(std::vector<unsigned char>{(unsigned char)witnessversion}); vSolutionsRet.push_back(std::move(witnessprogram)); return TxoutType::WITNESS_V1_TAPROOT; } @@ -242,8 +244,13 @@ bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet) addressRet = hash; return true; } - case TxoutType::WITNESS_UNKNOWN: case TxoutType::WITNESS_V1_TAPROOT: { + WitnessV1Taproot tap; + std::copy(vSolutions[0].begin(), vSolutions[0].end(), tap.begin()); + addressRet = tap; + return true; + } + case TxoutType::WITNESS_UNKNOWN: { WitnessUnknown unk; unk.version = vSolutions[0][0]; std::copy(vSolutions[1].begin(), vSolutions[1].end(), unk.program); @@ -329,6 +336,11 @@ public: return CScript() << OP_0 << ToByteVector(id); } + CScript operator()(const WitnessV1Taproot& tap) const + { + return CScript() << OP_1 << ToByteVector(tap); + } + CScript operator()(const WitnessUnknown& id) const { return CScript() << CScript::EncodeOP_N(id.version) << std::vector<unsigned char>(id.program, id.program + id.length); @@ -361,3 +373,291 @@ CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys) bool IsValidDestination(const CTxDestination& dest) { return dest.index() != 0; } + +/*static*/ TaprootBuilder::NodeInfo TaprootBuilder::Combine(NodeInfo&& a, NodeInfo&& b) +{ + NodeInfo ret; + /* Iterate over all tracked leaves in a, add b's hash to their Merkle branch, and move them to ret. */ + for (auto& leaf : a.leaves) { + leaf.merkle_branch.push_back(b.hash); + ret.leaves.emplace_back(std::move(leaf)); + } + /* Iterate over all tracked leaves in b, add a's hash to their Merkle branch, and move them to ret. */ + for (auto& leaf : b.leaves) { + leaf.merkle_branch.push_back(a.hash); + ret.leaves.emplace_back(std::move(leaf)); + } + /* Lexicographically sort a and b's hash, and compute parent hash. */ + if (a.hash < b.hash) { + ret.hash = (CHashWriter(HASHER_TAPBRANCH) << a.hash << b.hash).GetSHA256(); + } else { + ret.hash = (CHashWriter(HASHER_TAPBRANCH) << b.hash << a.hash).GetSHA256(); + } + return ret; +} + +void TaprootSpendData::Merge(TaprootSpendData other) +{ + // TODO: figure out how to better deal with conflicting information + // being merged. + if (internal_key.IsNull() && !other.internal_key.IsNull()) { + internal_key = other.internal_key; + } + if (merkle_root.IsNull() && !other.merkle_root.IsNull()) { + merkle_root = other.merkle_root; + } + for (auto& [key, control_blocks] : other.scripts) { + // Once P0083R3 is supported by all our targeted platforms, + // this loop body can be replaced with: + // scripts[key].merge(std::move(control_blocks)); + auto& target = scripts[key]; + for (auto& control_block: control_blocks) { + target.insert(std::move(control_block)); + } + } +} + +void TaprootBuilder::Insert(TaprootBuilder::NodeInfo&& node, int depth) +{ + assert(depth >= 0 && (size_t)depth <= TAPROOT_CONTROL_MAX_NODE_COUNT); + /* We cannot insert a leaf at a lower depth while a deeper branch is unfinished. Doing + * so would mean the Add() invocations do not correspond to a DFS traversal of a + * binary tree. */ + if ((size_t)depth + 1 < m_branch.size()) { + m_valid = false; + return; + } + /* As long as an entry in the branch exists at the specified depth, combine it and propagate up. + * The 'node' variable is overwritten here with the newly combined node. */ + while (m_valid && m_branch.size() > (size_t)depth && m_branch[depth].has_value()) { + node = Combine(std::move(node), std::move(*m_branch[depth])); + m_branch.pop_back(); + if (depth == 0) m_valid = false; /* Can't propagate further up than the root */ + --depth; + } + if (m_valid) { + /* Make sure the branch is big enough to place the new node. */ + if (m_branch.size() <= (size_t)depth) m_branch.resize((size_t)depth + 1); + assert(!m_branch[depth].has_value()); + m_branch[depth] = std::move(node); + } +} + +/*static*/ bool TaprootBuilder::ValidDepths(const std::vector<int>& depths) +{ + std::vector<bool> branch; + for (int depth : depths) { + // This inner loop corresponds to effectively the same logic on branch + // as what Insert() performs on the m_branch variable. Instead of + // storing a NodeInfo object, just remember whether or not there is one + // at that depth. + if (depth < 0 || (size_t)depth > TAPROOT_CONTROL_MAX_NODE_COUNT) return false; + if ((size_t)depth + 1 < branch.size()) return false; + while (branch.size() > (size_t)depth && branch[depth]) { + branch.pop_back(); + if (depth == 0) return false; + --depth; + } + if (branch.size() <= (size_t)depth) branch.resize((size_t)depth + 1); + assert(!branch[depth]); + branch[depth] = true; + } + // And this check corresponds to the IsComplete() check on m_branch. + return branch.size() == 0 || (branch.size() == 1 && branch[0]); +} + +TaprootBuilder& TaprootBuilder::Add(int depth, const CScript& script, int leaf_version, bool track) +{ + assert((leaf_version & ~TAPROOT_LEAF_MASK) == 0); + if (!IsValid()) return *this; + /* Construct NodeInfo object with leaf hash and (if track is true) also leaf information. */ + NodeInfo node; + node.hash = (CHashWriter{HASHER_TAPLEAF} << uint8_t(leaf_version) << script).GetSHA256(); + if (track) node.leaves.emplace_back(LeafInfo{script, leaf_version, {}}); + /* Insert into the branch. */ + Insert(std::move(node), depth); + return *this; +} + +TaprootBuilder& TaprootBuilder::AddOmitted(int depth, const uint256& hash) +{ + if (!IsValid()) return *this; + /* Construct NodeInfo object with the hash directly, and insert it into the branch. */ + NodeInfo node; + node.hash = hash; + Insert(std::move(node), depth); + return *this; +} + +TaprootBuilder& TaprootBuilder::Finalize(const XOnlyPubKey& internal_key) +{ + /* Can only call this function when IsComplete() is true. */ + assert(IsComplete()); + m_internal_key = internal_key; + auto ret = m_internal_key.CreateTapTweak(m_branch.size() == 0 ? nullptr : &m_branch[0]->hash); + assert(ret.has_value()); + std::tie(m_output_key, m_parity) = *ret; + return *this; +} + +WitnessV1Taproot TaprootBuilder::GetOutput() { return WitnessV1Taproot{m_output_key}; } + +TaprootSpendData TaprootBuilder::GetSpendData() const +{ + TaprootSpendData spd; + spd.merkle_root = m_branch.size() == 0 ? uint256() : m_branch[0]->hash; + spd.internal_key = m_internal_key; + if (m_branch.size()) { + // If any script paths exist, they have been combined into the root m_branch[0] + // by now. Compute the control block for each of its tracked leaves, and put them in + // spd.scripts. + for (const auto& leaf : m_branch[0]->leaves) { + std::vector<unsigned char> control_block; + control_block.resize(TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size()); + control_block[0] = leaf.leaf_version | (m_parity ? 1 : 0); + std::copy(m_internal_key.begin(), m_internal_key.end(), control_block.begin() + 1); + if (leaf.merkle_branch.size()) { + std::copy(leaf.merkle_branch[0].begin(), + leaf.merkle_branch[0].begin() + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size(), + control_block.begin() + TAPROOT_CONTROL_BASE_SIZE); + } + spd.scripts[{leaf.script, leaf.leaf_version}].insert(std::move(control_block)); + } + } + return spd; +} + +std::optional<std::vector<std::tuple<int, CScript, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output) +{ + // Verify that the output matches the assumed Merkle root and internal key. + auto tweak = spenddata.internal_key.CreateTapTweak(spenddata.merkle_root.IsNull() ? nullptr : &spenddata.merkle_root); + if (!tweak || tweak->first != output) return std::nullopt; + // If the Merkle root is 0, the tree is empty, and we're done. + std::vector<std::tuple<int, CScript, int>> ret; + if (spenddata.merkle_root.IsNull()) return ret; + + /** Data structure to represent the nodes of the tree we're going to build. */ + struct TreeNode { + /** Hash of this node, if known; 0 otherwise. */ + uint256 hash; + /** The left and right subtrees (note that their order is irrelevant). */ + std::unique_ptr<TreeNode> sub[2]; + /** If this is known to be a leaf node, a pointer to the (script, leaf_ver) pair. + * nullptr otherwise. */ + const std::pair<CScript, int>* leaf = nullptr; + /** Whether or not this node has been explored (is known to be a leaf, or known to have children). */ + bool explored = false; + /** Whether or not this node is an inner node (unknown until explored = true). */ + bool inner; + /** Whether or not we have produced output for this subtree. */ + bool done = false; + }; + + // Build tree from the provided branches. + TreeNode root; + root.hash = spenddata.merkle_root; + for (const auto& [key, control_blocks] : spenddata.scripts) { + const auto& [script, leaf_ver] = key; + for (const auto& control : control_blocks) { + // Skip script records with nonsensical leaf version. + if (leaf_ver < 0 || leaf_ver >= 0x100 || leaf_ver & 1) continue; + // Skip script records with invalid control block sizes. + if (control.size() < TAPROOT_CONTROL_BASE_SIZE || control.size() > TAPROOT_CONTROL_MAX_SIZE || + ((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE) != 0) continue; + // Skip script records that don't match the control block. + if ((control[0] & TAPROOT_LEAF_MASK) != leaf_ver) continue; + // Skip script records that don't match the provided Merkle root. + const uint256 leaf_hash = ComputeTapleafHash(leaf_ver, script); + const uint256 merkle_root = ComputeTaprootMerkleRoot(control, leaf_hash); + if (merkle_root != spenddata.merkle_root) continue; + + TreeNode* node = &root; + size_t levels = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE; + for (size_t depth = 0; depth < levels; ++depth) { + // Can't descend into a node which we already know is a leaf. + if (node->explored && !node->inner) return std::nullopt; + + // Extract partner hash from Merkle branch in control block. + uint256 hash; + std::copy(control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - 1 - depth) * TAPROOT_CONTROL_NODE_SIZE, + control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - depth) * TAPROOT_CONTROL_NODE_SIZE, + hash.begin()); + + if (node->sub[0]) { + // Descend into the existing left or right branch. + bool desc = false; + for (int i = 0; i < 2; ++i) { + if (node->sub[i]->hash == hash || (node->sub[i]->hash.IsNull() && node->sub[1-i]->hash != hash)) { + node->sub[i]->hash = hash; + node = &*node->sub[1-i]; + desc = true; + break; + } + } + if (!desc) return std::nullopt; // This probably requires a hash collision to hit. + } else { + // We're in an unexplored node. Create subtrees and descend. + node->explored = true; + node->inner = true; + node->sub[0] = std::make_unique<TreeNode>(); + node->sub[1] = std::make_unique<TreeNode>(); + node->sub[1]->hash = hash; + node = &*node->sub[0]; + } + } + // Cannot turn a known inner node into a leaf. + if (node->sub[0]) return std::nullopt; + node->explored = true; + node->inner = false; + node->leaf = &key; + node->hash = leaf_hash; + } + } + + // Recursive processing to turn the tree into flattened output. Use an explicit stack here to avoid + // overflowing the call stack (the tree may be 128 levels deep). + std::vector<TreeNode*> stack{&root}; + while (!stack.empty()) { + TreeNode& node = *stack.back(); + if (!node.explored) { + // Unexplored node, which means the tree is incomplete. + return std::nullopt; + } else if (!node.inner) { + // Leaf node; produce output. + ret.emplace_back(stack.size() - 1, node.leaf->first, node.leaf->second); + node.done = true; + stack.pop_back(); + } else if (node.sub[0]->done && !node.sub[1]->done && !node.sub[1]->explored && !node.sub[1]->hash.IsNull() && + (CHashWriter{HASHER_TAPBRANCH} << node.sub[1]->hash << node.sub[1]->hash).GetSHA256() == node.hash) { + // Whenever there are nodes with two identical subtrees under it, we run into a problem: + // the control blocks for the leaves underneath those will be identical as well, and thus + // they will all be matched to the same path in the tree. The result is that at the location + // where the duplicate occurred, the left child will contain a normal tree that can be explored + // and processed, but the right one will remain unexplored. + // + // This situation can be detected, by encountering an inner node with unexplored right subtree + // with known hash, and H_TapBranch(hash, hash) is equal to the parent node (this node)'s hash. + // + // To deal with this, simply process the left tree a second time (set its done flag to false; + // noting that the done flag of its children have already been set to false after processing + // those). To avoid ending up in an infinite loop, set the done flag of the right (unexplored) + // subtree to true. + node.sub[0]->done = false; + node.sub[1]->done = true; + } else if (node.sub[0]->done && node.sub[1]->done) { + // An internal node which we're finished with. + node.sub[0]->done = false; + node.sub[1]->done = false; + node.done = true; + stack.pop_back(); + } else if (!node.sub[0]->done) { + // An internal node whose left branch hasn't been processed yet. Do so first. + stack.push_back(&*node.sub[0]); + } else if (!node.sub[1]->done) { + // An internal node whose right branch hasn't been processed yet. Do so first. + stack.push_back(&*node.sub[1]); + } + } + + return ret; +} diff --git a/src/script/standard.h b/src/script/standard.h index 12ab9979a8..ac4e2f3276 100644 --- a/src/script/standard.h +++ b/src/script/standard.h @@ -6,10 +6,12 @@ #ifndef BITCOIN_SCRIPT_STANDARD_H #define BITCOIN_SCRIPT_STANDARD_H +#include <pubkey.h> #include <script/interpreter.h> #include <uint256.h> #include <util/hash_type.h> +#include <map> #include <string> #include <variant> @@ -113,6 +115,12 @@ struct WitnessV0KeyHash : public BaseHash<uint160> }; CKeyID ToKeyID(const WitnessV0KeyHash& key_hash); +struct WitnessV1Taproot : public XOnlyPubKey +{ + WitnessV1Taproot() : XOnlyPubKey() {} + explicit WitnessV1Taproot(const XOnlyPubKey& xpk) : XOnlyPubKey(xpk) {} +}; + //! CTxDestination subtype to encode any future Witness version struct WitnessUnknown { @@ -142,11 +150,11 @@ struct WitnessUnknown * * ScriptHash: TxoutType::SCRIPTHASH destination (P2SH) * * WitnessV0ScriptHash: TxoutType::WITNESS_V0_SCRIPTHASH destination (P2WSH) * * WitnessV0KeyHash: TxoutType::WITNESS_V0_KEYHASH destination (P2WPKH) - * * WitnessUnknown: TxoutType::WITNESS_UNKNOWN/WITNESS_V1_TAPROOT destination (P2W???) - * (taproot outputs do not require their own type as long as no wallet support exists) + * * WitnessV1Taproot: TxoutType::WITNESS_V1_TAPROOT destination (P2TR) + * * WitnessUnknown: TxoutType::WITNESS_UNKNOWN destination (P2W???) * A CTxDestination is the internal data type encoded in a bitcoin address */ -using CTxDestination = std::variant<CNoDestination, PKHash, ScriptHash, WitnessV0ScriptHash, WitnessV0KeyHash, WitnessUnknown>; +using CTxDestination = std::variant<CNoDestination, PKHash, ScriptHash, WitnessV0ScriptHash, WitnessV0KeyHash, WitnessV1Taproot, WitnessUnknown>; /** Check whether a CTxDestination is a CNoDestination. */ bool IsValidDestination(const CTxDestination& dest); @@ -202,4 +210,129 @@ CScript GetScriptForRawPubKey(const CPubKey& pubkey); /** Generate a multisig script. */ CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys); +struct ShortestVectorFirstComparator +{ + bool operator()(const std::vector<unsigned char>& a, const std::vector<unsigned char>& b) const + { + if (a.size() < b.size()) return true; + if (a.size() > b.size()) return false; + return a < b; + } +}; + +struct TaprootSpendData +{ + /** The BIP341 internal key. */ + XOnlyPubKey internal_key; + /** The Merkle root of the script tree (0 if no scripts). */ + uint256 merkle_root; + /** Map from (script, leaf_version) to (sets of) control blocks. + * The control blocks are sorted by size, so that the signing logic can + * easily prefer the cheapest one. */ + std::map<std::pair<CScript, int>, std::set<std::vector<unsigned char>, ShortestVectorFirstComparator>> scripts; + /** Merge other TaprootSpendData (for the same scriptPubKey) into this. */ + void Merge(TaprootSpendData other); +}; + +/** Utility class to construct Taproot outputs from internal key and script tree. */ +class TaprootBuilder +{ +private: + /** Information about a tracked leaf in the Merkle tree. */ + struct LeafInfo + { + CScript script; //!< The script. + int leaf_version; //!< The leaf version for that script. + std::vector<uint256> merkle_branch; //!< The hashing partners above this leaf. + }; + + /** Information associated with a node in the Merkle tree. */ + struct NodeInfo + { + /** Merkle hash of this node. */ + uint256 hash; + /** Tracked leaves underneath this node (either from the node itself, or its children). + * The merkle_branch field for each is the partners to get to *this* node. */ + std::vector<LeafInfo> leaves; + }; + /** Whether the builder is in a valid state so far. */ + bool m_valid = true; + + /** The current state of the builder. + * + * For each level in the tree, one NodeInfo object may be present. m_branch[0] + * is information about the root; further values are for deeper subtrees being + * explored. + * + * For every right branch taken to reach the position we're currently + * working in, there will be a (non-nullopt) entry in m_branch corresponding + * to the left branch at that level. + * + * For example, imagine this tree: - N0 - + * / \ + * N1 N2 + * / \ / \ + * A B C N3 + * / \ + * D E + * + * Initially, m_branch is empty. After processing leaf A, it would become + * {nullopt, nullopt, A}. When processing leaf B, an entry at level 2 already + * exists, and it would thus be combined with it to produce a level 1 one, + * resulting in {nullopt, N1}. Adding C and D takes us to {nullopt, N1, C} + * and {nullopt, N1, C, D} respectively. When E is processed, it is combined + * with D, and then C, and then N1, to produce the root, resulting in {N0}. + * + * This structure allows processing with just O(log n) overhead if the leaves + * are computed on the fly. + * + * As an invariant, there can never be nullopt entries at the end. There can + * also not be more than 128 entries (as that would mean more than 128 levels + * in the tree). The depth of newly added entries will always be at least + * equal to the current size of m_branch (otherwise it does not correspond + * to a depth-first traversal of a tree). m_branch is only empty if no entries + * have ever be processed. m_branch having length 1 corresponds to being done. + */ + std::vector<std::optional<NodeInfo>> m_branch; + + XOnlyPubKey m_internal_key; //!< The internal key, set when finalizing. + XOnlyPubKey m_output_key; //!< The output key, computed when finalizing. + bool m_parity; //!< The tweak parity, computed when finalizing. + + /** Combine information about a parent Merkle tree node from its child nodes. */ + static NodeInfo Combine(NodeInfo&& a, NodeInfo&& b); + /** Insert information about a node at a certain depth, and propagate information up. */ + void Insert(NodeInfo&& node, int depth); + +public: + /** Add a new script at a certain depth in the tree. Add() operations must be called + * in depth-first traversal order of binary tree. If track is true, it will be included in + * the GetSpendData() output. */ + TaprootBuilder& Add(int depth, const CScript& script, int leaf_version, bool track = true); + /** Like Add(), but for a Merkle node with a given hash to the tree. */ + TaprootBuilder& AddOmitted(int depth, const uint256& hash); + /** Finalize the construction. Can only be called when IsComplete() is true. + internal_key.IsFullyValid() must be true. */ + TaprootBuilder& Finalize(const XOnlyPubKey& internal_key); + + /** Return true if so far all input was valid. */ + bool IsValid() const { return m_valid; } + /** Return whether there were either no leaves, or the leaves form a Huffman tree. */ + bool IsComplete() const { return m_valid && (m_branch.size() == 0 || (m_branch.size() == 1 && m_branch[0].has_value())); } + /** Compute scriptPubKey (after Finalize()). */ + WitnessV1Taproot GetOutput(); + /** Check if a list of depths is legal (will lead to IsComplete()). */ + static bool ValidDepths(const std::vector<int>& depths); + /** Compute spending data (after Finalize()). */ + TaprootSpendData GetSpendData() const; +}; + +/** Given a TaprootSpendData and the output key, reconstruct its script tree. + * + * If the output doesn't match the spenddata, or if the data in spenddata is incomplete, + * std::nullopt is returned. Otherwise, a vector of (depth, script, leaf_ver) tuples is + * returned, corresponding to a depth-first traversal of the script tree. + */ +std::optional<std::vector<std::tuple<int, CScript, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output); + #endif // BITCOIN_SCRIPT_STANDARD_H |