aboutsummaryrefslogtreecommitdiff
path: root/src/script
diff options
context:
space:
mode:
Diffstat (limited to 'src/script')
-rw-r--r--src/script/descriptor.cpp279
-rw-r--r--src/script/descriptor.h23
-rw-r--r--src/script/interpreter.cpp52
-rw-r--r--src/script/interpreter.h11
-rw-r--r--src/script/sign.cpp195
-rw-r--r--src/script/sign.h9
-rw-r--r--src/script/signingprovider.cpp13
-rw-r--r--src/script/signingprovider.h4
-rw-r--r--src/script/standard.cpp198
-rw-r--r--src/script/standard.h54
10 files changed, 723 insertions, 115 deletions
diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp
index 51cf8a7d62..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.
@@ -244,8 +244,8 @@ class ConstPubkeyProvider final : public PubkeyProvider
bool m_xonly;
public:
- ConstPubkeyProvider(uint32_t exp_index, const CPubKey& pubkey, bool xonly = false) : 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) 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();
@@ -263,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;
}
@@ -288,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
{
@@ -305,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;
}
@@ -327,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;
@@ -343,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)) {
@@ -352,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);
@@ -376,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);
}
@@ -412,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;
}
@@ -429,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);
@@ -465,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;
@@ -508,6 +517,13 @@ 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_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
{
for (const auto& arg : m_subdescriptor_args) {
@@ -527,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;
@@ -547,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;
@@ -566,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;
}
@@ -640,20 +660,6 @@ public:
std::optional<OutputType> GetOutputType() const override { return std::nullopt; }
};
-static std::optional<OutputType> OutputTypeFromDestination(const CTxDestination& dest) {
- if (std::holds_alternative<PKHash>(dest) ||
- std::holds_alternative<ScriptHash>(dest)) {
- return OutputType::LEGACY;
- }
- if (std::holds_alternative<WitnessV0KeyHash>(dest) ||
- std::holds_alternative<WitnessV0ScriptHash>(dest) ||
- std::holds_alternative<WitnessV1Taproot>(dest) ||
- std::holds_alternative<WitnessUnknown>(dest)) {
- return OutputType::BECH32;
- }
- return std::nullopt;
-}
-
/** A parsed addr(A) descriptor. */
class AddressDescriptor final : public DescriptorImpl
{
@@ -843,9 +849,11 @@ protected:
XOnlyPubKey xpk(keys[0]);
if (!xpk.IsFullyValid()) return {};
builder.Finalize(xpk);
- return Vector(GetScriptForDestination(builder.GetOutput()));
+ WitnessV1Taproot output = builder.GetOutput();
+ out.tr_spenddata[output].Merge(builder.GetSpendData());
+ return Vector(GetScriptForDestination(output));
}
- bool ToStringSubScriptHelper(const SigningProvider* arg, std::string& ret, bool priv, bool normalized) const override
+ 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;
@@ -856,7 +864,7 @@ protected:
path.push_back(false);
}
std::string tmp;
- if (!m_subdescriptor_args[pos]->ToStringHelper(arg, tmp, priv, normalized)) return false;
+ 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 += '}';
@@ -872,7 +880,7 @@ public:
{
assert(m_subdescriptor_args.size() == m_depths.size());
}
- std::optional<OutputType> GetOutputType() const override { return OutputType::BECH32; }
+ std::optional<OutputType> GetOutputType() const override { return OutputType::BECH32M; }
bool IsSingleType() const final { return true; }
};
@@ -929,7 +937,7 @@ 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;
@@ -950,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;
@@ -1219,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));
@@ -1227,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;
@@ -1246,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;
@@ -1254,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]);
@@ -1271,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;
@@ -1280,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)) {
@@ -1365,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);
@@ -1383,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;
@@ -1392,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 3c3c3ac1a8..ef48f89965 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,8 +1478,8 @@ 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);
@@ -1711,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);
}
@@ -1740,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.
//
@@ -1847,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};
@@ -1868,8 +1866,21 @@ static bool VerifyTaprootCommitment(const std::vector<unsigned char>& control, c
}
k = ss_branch.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.CheckTapTweak(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)
@@ -1929,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 fa4ee83e04..034c937b99 100644
--- a/src/script/interpreter.h
+++ b/src/script/interpreter.h
@@ -168,7 +168,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);
@@ -260,6 +260,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
{
@@ -314,6 +317,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..65276f641f 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;
+ }
};
}
@@ -476,6 +633,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 +667,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 +679,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 a4b11cc0a9..b8349bb9ab 100644
--- a/src/script/standard.cpp
+++ b/src/script/standard.cpp
@@ -377,6 +377,16 @@ bool IsValidDestination(const CTxDestination& dest) {
/*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();
@@ -386,6 +396,27 @@ bool IsValidDestination(const CTxDestination& dest) {
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);
@@ -435,13 +466,14 @@ void TaprootBuilder::Insert(TaprootBuilder::NodeInfo&& node, int depth)
return branch.size() == 0 || (branch.size() == 1 && branch[0]);
}
-TaprootBuilder& TaprootBuilder::Add(int depth, const CScript& script, int leaf_version)
+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. */
+ /* 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;
@@ -464,8 +496,168 @@ TaprootBuilder& TaprootBuilder::Finalize(const XOnlyPubKey& internal_key)
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, std::ignore) = *ret;
+ 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 d7ea5cef27..ac4e2f3276 100644
--- a/src/script/standard.h
+++ b/src/script/standard.h
@@ -11,6 +11,7 @@
#include <uint256.h>
#include <util/hash_type.h>
+#include <map>
#include <string>
#include <variant>
@@ -209,15 +210,50 @@ 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;
@@ -260,7 +296,8 @@ private:
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. */
+ 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);
@@ -269,8 +306,9 @@ private:
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. */
- TaprootBuilder& Add(int depth, const CScript& script, int leaf_version);
+ * 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.
@@ -285,6 +323,16 @@ public:
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
generated by cgit v1.2.3 (git 2.26.2) at 2024-09-19 20:33:34 +0000