aboutsummaryrefslogtreecommitdiff
path: root/src/script
diff options
context:
space:
mode:
Diffstat (limited to 'src/script')
-rw-r--r--src/script/bitcoinconsensus.cpp2
-rw-r--r--src/script/bitcoinconsensus.h12
-rw-r--r--src/script/descriptor.cpp531
-rw-r--r--src/script/descriptor.h7
-rw-r--r--src/script/interpreter.cpp54
-rw-r--r--src/script/interpreter.h53
-rw-r--r--src/script/sigcache.cpp16
-rw-r--r--src/script/sigcache.h2
-rw-r--r--src/script/sign.cpp213
-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.cpp251
-rw-r--r--src/script/standard.h198
14 files changed, 1070 insertions, 295 deletions
diff --git a/src/script/bitcoinconsensus.cpp b/src/script/bitcoinconsensus.cpp
index 76609f01a7..a9aa6a0060 100644
--- a/src/script/bitcoinconsensus.cpp
+++ b/src/script/bitcoinconsensus.cpp
@@ -92,7 +92,7 @@ static int verify_script(const unsigned char *scriptPubKey, unsigned int scriptP
set_error(err, bitcoinconsensus_ERR_OK);
PrecomputedTransactionData txdata(tx);
- return VerifyScript(tx.vin[nIn].scriptSig, CScript(scriptPubKey, scriptPubKey + scriptPubKeyLen), &tx.vin[nIn].scriptWitness, flags, TransactionSignatureChecker(&tx, nIn, amount, txdata), nullptr);
+ return VerifyScript(tx.vin[nIn].scriptSig, CScript(scriptPubKey, scriptPubKey + scriptPubKeyLen), &tx.vin[nIn].scriptWitness, flags, TransactionSignatureChecker(&tx, nIn, amount, txdata, MissingDataBehavior::FAIL), nullptr);
} catch (const std::exception&) {
return set_error(err, bitcoinconsensus_ERR_TX_DESERIALIZE); // Error deserializing
}
diff --git a/src/script/bitcoinconsensus.h b/src/script/bitcoinconsensus.h
index c5dceac848..b6939127e1 100644
--- a/src/script/bitcoinconsensus.h
+++ b/src/script/bitcoinconsensus.h
@@ -11,14 +11,12 @@
#if defined(BUILD_BITCOIN_INTERNAL) && defined(HAVE_CONFIG_H)
#include <config/bitcoin-config.h>
#if defined(_WIN32)
- #if defined(DLL_EXPORT)
- #if defined(HAVE_FUNC_ATTRIBUTE_DLLEXPORT)
- #define EXPORT_SYMBOL __declspec(dllexport)
- #else
- #define EXPORT_SYMBOL
- #endif
+ #if defined(HAVE_DLLEXPORT_ATTRIBUTE)
+ #define EXPORT_SYMBOL __declspec(dllexport)
+ #else
+ #define EXPORT_SYMBOL
#endif
- #elif defined(HAVE_FUNC_ATTRIBUTE_VISIBILITY)
+ #elif defined(HAVE_DEFAULT_VISIBILITY_ATTRIBUTE)
#define EXPORT_SYMBOL __attribute__ ((visibility ("default")))
#endif
#elif defined(MSC_VER) && !defined(STATIC_LIBBITCOINCONSENSUS)
diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp
index 9e4b8a9dd6..84a8b06c5c 100644
--- a/src/script/descriptor.cpp
+++ b/src/script/descriptor.cpp
@@ -17,6 +17,7 @@
#include <util/vector.h>
#include <memory>
+#include <optional>
#include <string>
#include <vector>
@@ -179,6 +180,9 @@ public:
/** Get the descriptor string form including private data (if available in arg). */
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;
+
/** Derive a private key, if private data is available in arg. */
virtual bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const = 0;
};
@@ -212,6 +216,21 @@ public:
ret = "[" + OriginString() + "]" + std::move(sub);
return true;
}
+ bool ToNormalizedString(const SigningProvider& arg, std::string& ret, bool priv) const override
+ {
+ std::string sub;
+ if (!m_provider->ToNormalizedString(arg, sub, priv)) 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.
+ if (sub[0] == '[') {
+ sub = sub.substr(9);
+ ret = "[" + OriginString() + std::move(sub);
+ } else {
+ ret = "[" + OriginString() + "]" + std::move(sub);
+ }
+ return true;
+ }
bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const override
{
return m_provider->GetPrivKey(pos, arg, key);
@@ -222,9 +241,10 @@ 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) {}
+ 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
{
key = m_pubkey;
@@ -235,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;
@@ -243,6 +263,12 @@ public:
ret = EncodeSecret(key);
return true;
}
+ bool ToNormalizedString(const SigningProvider& arg, std::string& ret, bool priv) const override
+ {
+ if (priv) return ToPrivateString(arg, ret);
+ ret = ToString();
+ return true;
+ }
bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const override
{
return arg.GetKey(m_pubkey.GetID(), key);
@@ -386,6 +412,56 @@ public:
}
return true;
}
+ bool ToNormalizedString(const SigningProvider& arg, std::string& out, bool priv) 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;
+ }
+ // Step backwards to find the last hardened step in the path
+ int i = (int)m_path.size() - 1;
+ for (; i >= 0; --i) {
+ if (m_path.at(i) >> 31) {
+ break;
+ }
+ }
+ // 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;
+ 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));
+ }
+ // 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);
+ if (IsRange()) {
+ out += "/*";
+ assert(m_derive == DeriveType::UNHARDENED);
+ }
+ return true;
+ }
bool GetPrivKey(int pos, const SigningProvider& arg, CKey& key) const override
{
CExtKey extkey;
@@ -406,34 +482,36 @@ class DescriptorImpl : public Descriptor
const std::string m_name;
protected:
- //! The sub-descriptor argument (nullptr for everything but SH and WSH).
+ //! The sub-descriptor arguments (empty for everything but SH and WSH).
//! In doc/descriptors.m this is referred to as SCRIPT expressions sh(SCRIPT)
//! and wsh(SCRIPT), and distinct from KEY expressions and ADDR expressions.
- const std::unique_ptr<DescriptorImpl> m_subdescriptor_arg;
+ //! Subdescriptors can only ever generate a single script.
+ const std::vector<std::unique_ptr<DescriptorImpl>> m_subdescriptor_args;
//! Return a serialization of anything except pubkey and script arguments, to be prepended to those.
virtual std::string ToStringExtra() const { return ""; }
/** A helper function to construct the scripts for this descriptor.
*
- * This function is invoked once for every CScript produced by evaluating
- * m_subdescriptor_arg, or just once in case m_subdescriptor_arg is nullptr.
-
+ * This function is invoked once by ExpandHelper.
+ *
* @param pubkeys The evaluations of the m_pubkey_args field.
- * @param script The evaluation of m_subdescriptor_arg (or nullptr when m_subdescriptor_arg is nullptr).
+ * @param scripts The evaluations of m_subdescriptor_args (one for each m_subdescriptor_args element).
* @param out A FlatSigningProvider to put scripts or public keys in that are necessary to the solver.
- * The script arguments to this function are automatically added, as is the origin info of the provided pubkeys.
+ * The origin info of the provided pubkeys is automatically added.
* @return A vector with scriptPubKeys for this descriptor.
*/
- virtual std::vector<CScript> MakeScripts(const std::vector<CPubKey>& pubkeys, const CScript* script, FlatSigningProvider& out) const = 0;
+ virtual std::vector<CScript> MakeScripts(const std::vector<CPubKey>& pubkeys, Span<const CScript> scripts, FlatSigningProvider& out) const = 0;
public:
- DescriptorImpl(std::vector<std::unique_ptr<PubkeyProvider>> pubkeys, std::unique_ptr<DescriptorImpl> script, const std::string& name) : m_pubkey_args(std::move(pubkeys)), m_name(name), m_subdescriptor_arg(std::move(script)) {}
+ 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)) {}
bool IsSolvable() const override
{
- if (m_subdescriptor_arg) {
- if (!m_subdescriptor_arg->IsSolvable()) return false;
+ for (const auto& arg : m_subdescriptor_args) {
+ if (!arg->IsSolvable()) return false;
}
return true;
}
@@ -443,13 +521,25 @@ public:
for (const auto& pubkey : m_pubkey_args) {
if (pubkey->IsRange()) return true;
}
- if (m_subdescriptor_arg) {
- if (m_subdescriptor_arg->IsRange()) return true;
+ for (const auto& arg : m_subdescriptor_args) {
+ if (arg->IsRange()) return true;
}
return false;
}
- bool ToStringHelper(const SigningProvider* arg, std::string& out, bool priv) const
+ virtual bool ToStringSubScriptHelper(const SigningProvider* arg, std::string& ret, bool priv, bool normalized) 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;
+ ret += std::move(tmp);
+ }
+ return true;
+ }
+
+ bool ToStringHelper(const SigningProvider* arg, std::string& out, bool priv, bool normalized) const
{
std::string extra = ToStringExtra();
size_t pos = extra.size() > 0 ? 1 : 0;
@@ -457,33 +547,39 @@ public:
for (const auto& pubkey : m_pubkey_args) {
if (pos++) ret += ",";
std::string tmp;
- if (priv) {
+ if (normalized) {
+ if (!pubkey->ToNormalizedString(*arg, tmp, priv)) return false;
+ } else if (priv) {
if (!pubkey->ToPrivateString(*arg, tmp)) return false;
} else {
tmp = pubkey->ToString();
}
ret += std::move(tmp);
}
- if (m_subdescriptor_arg) {
- if (pos++) ret += ",";
- std::string tmp;
- if (!m_subdescriptor_arg->ToStringHelper(arg, tmp, priv)) return false;
- ret += std::move(tmp);
- }
- out = std::move(ret) + ")";
+ std::string subscript;
+ if (!ToStringSubScriptHelper(arg, subscript, priv, normalized)) return false;
+ if (pos && subscript.size()) ret += ',';
+ out = std::move(ret) + std::move(subscript) + ")";
return true;
}
std::string ToString() const final
{
std::string ret;
- ToStringHelper(nullptr, ret, false);
+ ToStringHelper(nullptr, ret, false, false);
return AddChecksum(ret);
}
bool ToPrivateString(const SigningProvider& arg, std::string& out) const final
{
- bool ret = ToStringHelper(&arg, out, true);
+ bool ret = ToStringHelper(&arg, out, true, false);
+ out = AddChecksum(out);
+ return ret;
+ }
+
+ bool ToNormalizedString(const SigningProvider& arg, std::string& out, bool priv) const override final
+ {
+ bool ret = ToStringHelper(&arg, out, priv, true);
out = AddChecksum(out);
return ret;
}
@@ -493,17 +589,20 @@ public:
std::vector<std::pair<CPubKey, KeyOriginInfo>> entries;
entries.reserve(m_pubkey_args.size());
- // Construct temporary data in `entries` and `subscripts`, to avoid producing output in case of failure.
+ // Construct temporary data in `entries`, `subscripts`, and `subprovider` to avoid producing output in case of failure.
for (const auto& p : m_pubkey_args) {
entries.emplace_back();
if (!p->GetPubKey(pos, arg, entries.back().first, entries.back().second, read_cache, write_cache)) return false;
}
std::vector<CScript> subscripts;
- if (m_subdescriptor_arg) {
- FlatSigningProvider subprovider;
- if (!m_subdescriptor_arg->ExpandHelper(pos, arg, read_cache, subscripts, subprovider, write_cache)) return false;
- out = Merge(out, subprovider);
+ FlatSigningProvider subprovider;
+ for (const auto& subarg : m_subdescriptor_args) {
+ std::vector<CScript> outscripts;
+ if (!subarg->ExpandHelper(pos, arg, read_cache, outscripts, subprovider, write_cache)) return false;
+ assert(outscripts.size() == 1);
+ subscripts.emplace_back(std::move(outscripts[0]));
}
+ out = Merge(std::move(out), std::move(subprovider));
std::vector<CPubKey> pubkeys;
pubkeys.reserve(entries.size());
@@ -511,17 +610,8 @@ public:
pubkeys.push_back(entry.first);
out.origins.emplace(entry.first.GetID(), std::make_pair<CPubKey, KeyOriginInfo>(CPubKey(entry.first), std::move(entry.second)));
}
- if (m_subdescriptor_arg) {
- for (const auto& subscript : subscripts) {
- out.scripts.emplace(CScriptID(subscript), subscript);
- std::vector<CScript> addscripts = MakeScripts(pubkeys, &subscript, out);
- for (auto& addscript : addscripts) {
- output_scripts.push_back(std::move(addscript));
- }
- }
- } else {
- output_scripts = MakeScripts(pubkeys, nullptr, out);
- }
+
+ output_scripts = MakeScripts(pubkeys, MakeSpan(subscripts), out);
return true;
}
@@ -542,38 +632,42 @@ public:
if (!p->GetPrivKey(pos, provider, key)) continue;
out.keys.emplace(key.GetPubKey().GetID(), key);
}
- if (m_subdescriptor_arg) {
- FlatSigningProvider subprovider;
- m_subdescriptor_arg->ExpandPrivate(pos, provider, subprovider);
- out = Merge(out, subprovider);
+ for (const auto& arg : m_subdescriptor_args) {
+ arg->ExpandPrivate(pos, provider, out);
}
}
- Optional<OutputType> GetOutputType() const override { return nullopt; }
+ 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
{
const CTxDestination m_destination;
protected:
std::string ToStringExtra() const override { return EncodeDestination(m_destination); }
- std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, const CScript*, FlatSigningProvider&) const override { return Vector(GetScriptForDestination(m_destination)); }
+ std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, Span<const CScript>, FlatSigningProvider&) const override { return Vector(GetScriptForDestination(m_destination)); }
public:
- AddressDescriptor(CTxDestination destination) : DescriptorImpl({}, {}, "addr"), m_destination(std::move(destination)) {}
+ AddressDescriptor(CTxDestination destination) : DescriptorImpl({}, "addr"), m_destination(std::move(destination)) {}
bool IsSolvable() const final { return false; }
- Optional<OutputType> GetOutputType() const override
+ 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 nullopt;
- }
+ return OutputTypeFromDestination(m_destination);
}
bool IsSingleType() const final { return true; }
};
@@ -584,24 +678,16 @@ class RawDescriptor final : public DescriptorImpl
const CScript m_script;
protected:
std::string ToStringExtra() const override { return HexStr(m_script); }
- std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, const CScript*, FlatSigningProvider&) const override { return Vector(m_script); }
+ std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, Span<const CScript>, FlatSigningProvider&) const override { return Vector(m_script); }
public:
- RawDescriptor(CScript script) : DescriptorImpl({}, {}, "raw"), m_script(std::move(script)) {}
+ RawDescriptor(CScript script) : DescriptorImpl({}, "raw"), m_script(std::move(script)) {}
bool IsSolvable() const final { return false; }
- Optional<OutputType> GetOutputType() const override
+ std::optional<OutputType> GetOutputType() const override
{
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 nullopt;
- }
+ return OutputTypeFromDestination(dest);
}
bool IsSingleType() const final { return true; }
};
@@ -609,10 +695,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, 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; }
};
@@ -620,15 +716,15 @@ public:
class PKHDescriptor final : public DescriptorImpl
{
protected:
- std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, const CScript*, FlatSigningProvider& out) const override
+ std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider& out) const override
{
CKeyID id = keys[0].GetID();
out.pubkeys.emplace(id, keys[0]);
return Vector(GetScriptForDestination(PKHash(id)));
}
public:
- PKHDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), {}, "pkh") {}
- Optional<OutputType> GetOutputType() const override { return OutputType::LEGACY; }
+ PKHDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), "pkh") {}
+ std::optional<OutputType> GetOutputType() const override { return OutputType::LEGACY; }
bool IsSingleType() const final { return true; }
};
@@ -636,15 +732,15 @@ public:
class WPKHDescriptor final : public DescriptorImpl
{
protected:
- std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, const CScript*, FlatSigningProvider& out) const override
+ std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider& out) const override
{
CKeyID id = keys[0].GetID();
out.pubkeys.emplace(id, keys[0]);
return Vector(GetScriptForDestination(WitnessV0KeyHash(id)));
}
public:
- WPKHDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), {}, "wpkh") {}
- Optional<OutputType> GetOutputType() const override { return OutputType::BECH32; }
+ WPKHDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), "wpkh") {}
+ std::optional<OutputType> GetOutputType() const override { return OutputType::BECH32; }
bool IsSingleType() const final { return true; }
};
@@ -652,7 +748,7 @@ public:
class ComboDescriptor final : public DescriptorImpl
{
protected:
- std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, const CScript*, FlatSigningProvider& out) const override
+ std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider& out) const override
{
std::vector<CScript> ret;
CKeyID id = keys[0].GetID();
@@ -668,7 +764,7 @@ protected:
return ret;
}
public:
- ComboDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), {}, "combo") {}
+ ComboDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), "combo") {}
bool IsSingleType() const final { return false; }
};
@@ -679,7 +775,7 @@ class MultisigDescriptor final : public DescriptorImpl
const bool m_sorted;
protected:
std::string ToStringExtra() const override { return strprintf("%i", m_threshold); }
- std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, const CScript*, FlatSigningProvider&) const override {
+ std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider&) const override {
if (m_sorted) {
std::vector<CPubKey> sorted_keys(keys);
std::sort(sorted_keys.begin(), sorted_keys.end());
@@ -688,7 +784,7 @@ protected:
return Vector(GetScriptForMultisig(m_threshold, keys));
}
public:
- MultisigDescriptor(int threshold, std::vector<std::unique_ptr<PubkeyProvider>> providers, bool sorted = false) : DescriptorImpl(std::move(providers), {}, sorted ? "sortedmulti" : "multi"), m_threshold(threshold), m_sorted(sorted) {}
+ MultisigDescriptor(int threshold, std::vector<std::unique_ptr<PubkeyProvider>> providers, bool sorted = false) : DescriptorImpl(std::move(providers), sorted ? "sortedmulti" : "multi"), m_threshold(threshold), m_sorted(sorted) {}
bool IsSingleType() const final { return true; }
};
@@ -696,14 +792,19 @@ public:
class SHDescriptor final : public DescriptorImpl
{
protected:
- std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, const CScript* script, FlatSigningProvider&) const override { return Vector(GetScriptForDestination(ScriptHash(*script))); }
+ std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, Span<const CScript> scripts, FlatSigningProvider& out) const override
+ {
+ auto ret = Vector(GetScriptForDestination(ScriptHash(scripts[0])));
+ if (ret.size()) out.scripts.emplace(CScriptID(scripts[0]), scripts[0]);
+ return ret;
+ }
public:
SHDescriptor(std::unique_ptr<DescriptorImpl> desc) : DescriptorImpl({}, std::move(desc), "sh") {}
- Optional<OutputType> GetOutputType() const override
+ std::optional<OutputType> GetOutputType() const override
{
- assert(m_subdescriptor_arg);
- if (m_subdescriptor_arg->GetOutputType() == OutputType::BECH32) return OutputType::P2SH_SEGWIT;
+ assert(m_subdescriptor_args.size() == 1);
+ if (m_subdescriptor_args[0]->GetOutputType() == OutputType::BECH32) return OutputType::P2SH_SEGWIT;
return OutputType::LEGACY;
}
bool IsSingleType() const final { return true; }
@@ -713,10 +814,67 @@ public:
class WSHDescriptor final : public DescriptorImpl
{
protected:
- std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, const CScript* script, FlatSigningProvider&) const override { return Vector(GetScriptForDestination(WitnessV0ScriptHash(*script))); }
+ std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, Span<const CScript> scripts, FlatSigningProvider& out) const override
+ {
+ auto ret = Vector(GetScriptForDestination(WitnessV0ScriptHash(scripts[0])));
+ if (ret.size()) out.scripts.emplace(CScriptID(scripts[0]), scripts[0]);
+ return ret;
+ }
public:
WSHDescriptor(std::unique_ptr<DescriptorImpl> desc) : DescriptorImpl({}, std::move(desc), "wsh") {}
- Optional<OutputType> GetOutputType() const override { return OutputType::BECH32; }
+ std::optional<OutputType> GetOutputType() const override { return OutputType::BECH32; }
+ 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, bool priv, bool normalized) 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, priv, normalized)) 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::BECH32; }
bool IsSingleType() const final { return true; }
};
@@ -725,9 +883,11 @@ public:
////////////////////////////////////////////////////////////////////////////
enum class ParseScriptContext {
- TOP,
- P2SH,
- P2WSH,
+ TOP, //!< Top-level context (script goes directly in scriptPubKey)
+ 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). */
@@ -754,10 +914,11 @@ enum class ParseScriptContext {
}
/** Parse a public key that excludes origin information. */
-std::unique_ptr<PubkeyProvider> ParsePubkeyInner(uint32_t key_exp_index, const Span<const char>& sp, bool permit_uncompressed, FlatSigningProvider& out, std::string& error)
+std::unique_ptr<PubkeyProvider> ParsePubkeyInner(uint32_t key_exp_index, const Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error)
{
using namespace spanparsing;
+ bool permit_uncompressed = ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH;
auto split = Split(sp, '/');
std::string str(split[0].begin(), split[0].end());
if (str.size() == 0) {
@@ -770,11 +931,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 MakeUnique<ConstPubkeyProvider>(key_exp_index, pubkey);
+ return std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey);
} 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;
@@ -784,7 +952,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 MakeUnique<ConstPubkeyProvider>(key_exp_index, pubkey);
+ return std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey);
} else {
error = "Uncompressed keys are not allowed";
return nullptr;
@@ -811,11 +979,11 @@ std::unique_ptr<PubkeyProvider> ParsePubkeyInner(uint32_t key_exp_index, const S
extpubkey = extkey.Neuter();
out.keys.emplace(extpubkey.pubkey.GetID(), extkey.key);
}
- return MakeUnique<BIP32PubkeyProvider>(key_exp_index, extpubkey, std::move(path), type);
+ return std::make_unique<BIP32PubkeyProvider>(key_exp_index, extpubkey, std::move(path), type);
}
/** Parse a public key including origin information (if enabled). */
-std::unique_ptr<PubkeyProvider> ParsePubkey(uint32_t key_exp_index, const Span<const char>& sp, bool permit_uncompressed, FlatSigningProvider& out, std::string& error)
+std::unique_ptr<PubkeyProvider> ParsePubkey(uint32_t key_exp_index, const Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error)
{
using namespace spanparsing;
@@ -824,7 +992,7 @@ std::unique_ptr<PubkeyProvider> ParsePubkey(uint32_t key_exp_index, const Span<c
error = "Multiple ']' characters found for a single pubkey";
return nullptr;
}
- if (origin_split.size() == 1) return ParsePubkeyInner(key_exp_index, origin_split[0], permit_uncompressed, out, error);
+ if (origin_split.size() == 1) return ParsePubkeyInner(key_exp_index, origin_split[0], ctx, out, error);
if (origin_split[0].empty() || origin_split[0][0] != '[') {
error = strprintf("Key origin start '[ character expected but not found, got '%c' instead",
origin_split[0].empty() ? /** empty, implies split char */ ']' : origin_split[0][0]);
@@ -846,37 +1014,43 @@ std::unique_ptr<PubkeyProvider> ParsePubkey(uint32_t key_exp_index, const Span<c
assert(fpr_bytes.size() == 4);
std::copy(fpr_bytes.begin(), fpr_bytes.end(), info.fingerprint);
if (!ParseKeyPath(slash_split, info.path, error)) return nullptr;
- auto provider = ParsePubkeyInner(key_exp_index, origin_split[1], permit_uncompressed, out, error);
+ auto provider = ParsePubkeyInner(key_exp_index, origin_split[1], ctx, out, error);
if (!provider) return nullptr;
- return MakeUnique<OriginPubkeyProvider>(key_exp_index, std::move(info), std::move(provider));
+ return std::make_unique<OriginPubkeyProvider>(key_exp_index, std::move(info), std::move(provider));
}
/** Parse a script in a particular context. */
-std::unique_ptr<DescriptorImpl> ParseScript(uint32_t key_exp_index, Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error)
+std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error)
{
using namespace spanparsing;
auto expr = Expr(sp);
bool sorted_multi = false;
if (Func("pk", expr)) {
- auto pubkey = ParsePubkey(key_exp_index, expr, ctx != ParseScriptContext::P2WSH, out, error);
+ auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error);
if (!pubkey) return nullptr;
- return MakeUnique<PKDescriptor>(std::move(pubkey));
+ ++key_exp_index;
+ return std::make_unique<PKDescriptor>(std::move(pubkey), ctx == ParseScriptContext::P2TR);
}
- if (Func("pkh", expr)) {
- auto pubkey = ParsePubkey(key_exp_index, expr, ctx != ParseScriptContext::P2WSH, out, error);
+ 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;
- return MakeUnique<PKHDescriptor>(std::move(pubkey));
+ ++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, true, out, error);
+ auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error);
if (!pubkey) return nullptr;
- return MakeUnique<ComboDescriptor>(std::move(pubkey));
- } else if (ctx != ParseScriptContext::TOP && Func("combo", expr)) {
- error = "Cannot have combo in non-top level";
+ ++key_exp_index;
+ return std::make_unique<ComboDescriptor>(std::move(pubkey));
+ } else if (Func("combo", expr)) {
+ 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;
@@ -891,14 +1065,14 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t key_exp_index, Span<const c
return nullptr;
}
auto arg = Expr(expr);
- auto pk = ParsePubkey(key_exp_index, arg, ctx != ParseScriptContext::P2WSH, out, error);
+ auto pk = ParsePubkey(key_exp_index, arg, ctx, out, error);
if (!pk) return nullptr;
script_size += pk->GetSize() + 1;
providers.emplace_back(std::move(pk));
key_exp_index++;
}
- if (providers.empty() || providers.size() > 16) {
- error = strprintf("Cannot have %u keys in multisig; must have between 1 and 16 keys, inclusive", providers.size());
+ if (providers.empty() || providers.size() > MAX_PUBKEYS_PER_MULTISIG) {
+ error = strprintf("Cannot have %u keys in multisig; must have between 1 and %d keys, inclusive", providers.size(), MAX_PUBKEYS_PER_MULTISIG);
return nullptr;
} else if (thres < 1) {
error = strprintf("Multisig threshold cannot be %d, must be at least 1", thres);
@@ -914,35 +1088,40 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t key_exp_index, Span<const c
}
}
if (ctx == ParseScriptContext::P2SH) {
+ // This limits the maximum number of compressed pubkeys to 15.
if (script_size + 3 > MAX_SCRIPT_ELEMENT_SIZE) {
error = strprintf("P2SH script is too large, %d bytes is larger than %d bytes", script_size + 3, MAX_SCRIPT_ELEMENT_SIZE);
return nullptr;
}
}
- return MakeUnique<MultisigDescriptor>(thres, std::move(providers), sorted_multi);
+ 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::P2WSH && Func("wpkh", expr)) {
- auto pubkey = ParsePubkey(key_exp_index, expr, false, out, error);
+ if ((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH) && Func("wpkh", expr)) {
+ auto pubkey = ParsePubkey(key_exp_index, expr, ParseScriptContext::P2WPKH, out, error);
if (!pubkey) return nullptr;
- return MakeUnique<WPKHDescriptor>(std::move(pubkey));
- } else if (ctx == ParseScriptContext::P2WSH && Func("wpkh", expr)) {
- error = "Cannot have wpkh within wsh";
+ key_exp_index++;
+ return std::make_unique<WPKHDescriptor>(std::move(pubkey));
+ } else if (Func("wpkh", expr)) {
+ error = "Can only have wpkh() at top level or inside sh()";
return nullptr;
}
if (ctx == ParseScriptContext::TOP && Func("sh", expr)) {
auto desc = ParseScript(key_exp_index, expr, ParseScriptContext::P2SH, out, error);
if (!desc || expr.size()) return nullptr;
- return MakeUnique<SHDescriptor>(std::move(desc));
- } else if (ctx != ParseScriptContext::TOP && Func("sh", expr)) {
- error = "Cannot have sh in non-top level";
+ return std::make_unique<SHDescriptor>(std::move(desc));
+ } else if (Func("sh", expr)) {
+ error = "Can only have sh() at top level";
return nullptr;
}
- if (ctx != ParseScriptContext::P2WSH && Func("wsh", expr)) {
+ if ((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH) && Func("wsh", expr)) {
auto desc = ParseScript(key_exp_index, expr, ParseScriptContext::P2WSH, out, error);
if (!desc || expr.size()) return nullptr;
- return MakeUnique<WSHDescriptor>(std::move(desc));
- } else if (ctx == ParseScriptContext::P2WSH && Func("wsh", expr)) {
- error = "Cannot have wsh within wsh";
+ return std::make_unique<WSHDescriptor>(std::move(desc));
+ } else if (Func("wsh", expr)) {
+ error = "Can only have wsh() at top level or inside sh()";
return nullptr;
}
if (ctx == ParseScriptContext::TOP && Func("addr", expr)) {
@@ -951,7 +1130,71 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t key_exp_index, Span<const c
error = "Address is not valid";
return nullptr;
}
- return MakeUnique<AddressDescriptor>(std::move(dest));
+ return std::make_unique<AddressDescriptor>(std::move(dest));
+ } else if (Func("addr", expr)) {
+ 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());
@@ -960,7 +1203,10 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t key_exp_index, Span<const c
return nullptr;
}
auto bytes = ParseHex(str);
- return MakeUnique<RawDescriptor>(CScript(bytes.begin(), bytes.end()));
+ return std::make_unique<RawDescriptor>(CScript(bytes.begin(), bytes.end()));
+ } else if (Func("raw", expr)) {
+ error = "Can only have raw() at top level";
+ return nullptr;
}
if (ctx == ParseScriptContext::P2SH) {
error = "A function is needed within P2SH";
@@ -975,10 +1221,10 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t key_exp_index, Span<const c
std::unique_ptr<PubkeyProvider> InferPubkey(const CPubKey& pubkey, ParseScriptContext, const SigningProvider& provider)
{
- std::unique_ptr<PubkeyProvider> key_provider = MakeUnique<ConstPubkeyProvider>(0, pubkey);
+ std::unique_ptr<PubkeyProvider> key_provider = std::make_unique<ConstPubkeyProvider>(0, pubkey);
KeyOriginInfo info;
if (provider.GetKeyOrigin(pubkey.GetID(), info)) {
- return MakeUnique<OriginPubkeyProvider>(0, std::move(info), std::move(key_provider));
+ return std::make_unique<OriginPubkeyProvider>(0, std::move(info), std::move(key_provider));
}
return key_provider;
}
@@ -989,9 +1235,9 @@ std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptCo
TxoutType txntype = Solver(script, data);
if (txntype == TxoutType::PUBKEY) {
- CPubKey pubkey(data[0].begin(), data[0].end());
+ CPubKey pubkey(data[0]);
if (pubkey.IsValid()) {
- return MakeUnique<PKDescriptor>(InferPubkey(pubkey, ctx, provider));
+ return std::make_unique<PKDescriptor>(InferPubkey(pubkey, ctx, provider));
}
}
if (txntype == TxoutType::PUBKEYHASH) {
@@ -999,7 +1245,7 @@ std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptCo
CKeyID keyid(hash);
CPubKey pubkey;
if (provider.GetPubKey(keyid, pubkey)) {
- return MakeUnique<PKHDescriptor>(InferPubkey(pubkey, ctx, provider));
+ return std::make_unique<PKHDescriptor>(InferPubkey(pubkey, ctx, provider));
}
}
if (txntype == TxoutType::WITNESS_V0_KEYHASH && ctx != ParseScriptContext::P2WSH) {
@@ -1007,16 +1253,16 @@ std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptCo
CKeyID keyid(hash);
CPubKey pubkey;
if (provider.GetPubKey(keyid, pubkey)) {
- return MakeUnique<WPKHDescriptor>(InferPubkey(pubkey, ctx, provider));
+ return std::make_unique<WPKHDescriptor>(InferPubkey(pubkey, ctx, provider));
}
}
if (txntype == TxoutType::MULTISIG) {
std::vector<std::unique_ptr<PubkeyProvider>> providers;
for (size_t i = 1; i + 1 < data.size(); ++i) {
- CPubKey pubkey(data[i].begin(), data[i].end());
+ CPubKey pubkey(data[i]);
providers.push_back(InferPubkey(pubkey, ctx, provider));
}
- return MakeUnique<MultisigDescriptor>((int)data[0][0], std::move(providers));
+ return std::make_unique<MultisigDescriptor>((int)data[0][0], std::move(providers));
}
if (txntype == TxoutType::SCRIPTHASH && ctx == ParseScriptContext::TOP) {
uint160 hash(data[0]);
@@ -1024,7 +1270,7 @@ std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptCo
CScript subscript;
if (provider.GetCScript(scriptid, subscript)) {
auto sub = InferScript(subscript, ParseScriptContext::P2SH, provider);
- if (sub) return MakeUnique<SHDescriptor>(std::move(sub));
+ if (sub) return std::make_unique<SHDescriptor>(std::move(sub));
}
}
if (txntype == TxoutType::WITNESS_V0_SCRIPTHASH && ctx != ParseScriptContext::P2WSH) {
@@ -1033,18 +1279,18 @@ std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptCo
CScript subscript;
if (provider.GetCScript(scriptid, subscript)) {
auto sub = InferScript(subscript, ParseScriptContext::P2WSH, provider);
- if (sub) return MakeUnique<WSHDescriptor>(std::move(sub));
+ if (sub) return std::make_unique<WSHDescriptor>(std::move(sub));
}
}
CTxDestination dest;
if (ExtractDestination(script, dest)) {
if (GetScriptForDestination(dest) == script) {
- return MakeUnique<AddressDescriptor>(std::move(dest));
+ return std::make_unique<AddressDescriptor>(std::move(dest));
}
}
- return MakeUnique<RawDescriptor>(script);
+ return std::make_unique<RawDescriptor>(script);
}
@@ -1090,7 +1336,8 @@ std::unique_ptr<Descriptor> Parse(const std::string& descriptor, FlatSigningProv
{
Span<const char> sp{descriptor};
if (!CheckChecksum(sp, require_checksum, error)) return nullptr;
- auto ret = ParseScript(0, sp, ParseScriptContext::TOP, out, error);
+ uint32_t key_exp_index = 0;
+ auto ret = ParseScript(key_exp_index, sp, ParseScriptContext::TOP, out, error);
if (sp.size() == 0 && ret) return std::unique_ptr<Descriptor>(std::move(ret));
return nullptr;
}
diff --git a/src/script/descriptor.h b/src/script/descriptor.h
index 17b43e7c81..332ae2f230 100644
--- a/src/script/descriptor.h
+++ b/src/script/descriptor.h
@@ -5,12 +5,12 @@
#ifndef BITCOIN_SCRIPT_DESCRIPTOR_H
#define BITCOIN_SCRIPT_DESCRIPTOR_H
-#include <optional.h>
#include <outputtype.h>
#include <script/script.h>
#include <script/sign.h>
#include <script/signingprovider.h>
+#include <optional>
#include <vector>
using ExtPubKeyMap = std::unordered_map<uint32_t, CExtPubKey>;
@@ -93,6 +93,9 @@ struct Descriptor {
/** Convert the descriptor to a private string. This fails if the provided provider does not have the relevant private keys. */
virtual bool ToPrivateString(const SigningProvider& provider, std::string& out) const = 0;
+ /** 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;
+
/** Expand a descriptor at a specified position.
*
* @param[in] pos The position at which to expand the descriptor. If IsRange() is false, this is ignored.
@@ -121,7 +124,7 @@ struct Descriptor {
virtual void ExpandPrivate(int pos, const SigningProvider& provider, FlatSigningProvider& out) const = 0;
/** @return The OutputType of the scriptPubKey(s) produced by this descriptor. Or nullopt if indeterminate (multiple or none) */
- virtual Optional<OutputType> GetOutputType() const = 0;
+ virtual std::optional<OutputType> GetOutputType() const = 0;
};
/** Parse a `descriptor` string. Included private keys are put in `out`.
diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
index ecac3b9e7e..2dd173ee20 100644
--- a/src/script/interpreter.cpp
+++ b/src/script/interpreter.cpp
@@ -225,7 +225,7 @@ bool static CheckPubKeyEncoding(const valtype &vchPubKey, unsigned int flags, co
return true;
}
-bool static CheckMinimalPush(const valtype& data, opcodetype opcode) {
+bool CheckMinimalPush(const valtype& data, opcodetype opcode) {
// Excludes OP_1NEGATE, OP_1-16 since they are by definition minimal
assert(0 <= opcode && opcode <= OP_PUSHDATA4);
if (data.size() == 0) {
@@ -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,18 +1478,29 @@ 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)
+{
+ switch (mdb) {
+ case MissingDataBehavior::ASSERT_FAIL:
+ assert(!"Missing data");
+ break;
+ case MissingDataBehavior::FAIL:
+ return false;
+ }
+ assert(!"Unknown MissingDataBehavior value");
+}
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)
+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)
{
uint8_t ext_flag, key_version;
switch (sigversion) {
@@ -1509,7 +1520,9 @@ bool SignatureHashSchnorr(uint256& hash_out, const ScriptExecutionData& execdata
assert(false);
}
assert(in_pos < tx_to.vin.size());
- assert(cache.m_bip341_taproot_ready && cache.m_spent_outputs_ready);
+ if (!(cache.m_bip341_taproot_ready && cache.m_spent_outputs_ready)) {
+ return HandleMissingData(mdb);
+ }
CHashWriter ss = HASHER_TAPSIGHASH;
@@ -1667,6 +1680,9 @@ bool GenericTransactionSignatureChecker<T>::CheckECDSASignature(const std::vecto
int nHashType = vchSig.back();
vchSig.pop_back();
+ // Witness sighashes need the amount.
+ if (sigversion == SigVersion::WITNESS_V0 && amount < 0) return HandleMissingData(m_mdb);
+
uint256 sighash = SignatureHash(scriptCode, *txTo, nIn, nHashType, amount, sigversion, this->txdata);
if (!VerifyECDSASignature(vchSig, pubkey, sighash))
@@ -1695,8 +1711,8 @@ 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 (!SignatureHashSchnorr(sighash, execdata, *txTo, nIn, hashtype, sigversion, *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);
}
if (!VerifySchnorrSignature(sig, pubkey, sighash)) return set_error(serror, SCRIPT_ERR_SCHNORR_SIG);
@@ -1834,7 +1850,7 @@ static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CS
static bool VerifyTaprootCommitment(const std::vector<unsigned char>& control, const std::vector<unsigned char>& program, const CScript& script, uint256& tapleaf_hash)
{
const int path_len = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE;
- //! The inner pubkey (x-only, so no Y coordinate parity).
+ //! 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)};
@@ -1852,10 +1868,8 @@ static bool VerifyTaprootCommitment(const std::vector<unsigned char>& control, c
}
k = ss_branch.GetSHA256();
}
- // Compute the tweak from the Merkle root and the inner pubkey.
- k = (CHashWriter(HASHER_TAPTWEAK) << MakeSpan(p) << k).GetSHA256();
- // Verify that the output pubkey matches the tweaked inner pubkey, after correcting for parity.
- return q.CheckPayToContract(p, k, control[0] & 1);
+ // Verify that the output pubkey matches the tweaked internal pubkey, after correcting for parity.
+ return q.CheckTapTweak(p, k, 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)
@@ -1873,7 +1887,7 @@ static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion,
const valtype& script_bytes = SpanPopBack(stack);
exec_script = CScript(script_bytes.begin(), script_bytes.end());
uint256 hash_exec_script;
- CSHA256().Write(&exec_script[0], exec_script.size()).Finalize(hash_exec_script.begin());
+ CSHA256().Write(exec_script.data(), exec_script.size()).Finalize(hash_exec_script.begin());
if (memcmp(hash_exec_script.begin(), program.data(), 32)) {
return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH);
}
diff --git a/src/script/interpreter.h b/src/script/interpreter.h
index b4c163c841..ced5c28bc1 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>
@@ -167,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);
@@ -218,6 +219,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);
@@ -247,11 +251,24 @@ public:
virtual ~BaseSignatureChecker() {}
};
+/** Enum to specify what *TransactionSignatureChecker's behavior should be
+ * when dealing with missing transaction data.
+ */
+enum class MissingDataBehavior
+{
+ ASSERT_FAIL, //!< Abort execution through assertion failure (for consensus code)
+ 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
{
private:
const T* txTo;
+ const MissingDataBehavior m_mdb;
unsigned int nIn;
const CAmount amount;
const PrecomputedTransactionData* txdata;
@@ -261,8 +278,8 @@ protected:
virtual bool VerifySchnorrSignature(Span<const unsigned char> sig, const XOnlyPubKey& pubkey, const uint256& sighash) const;
public:
- GenericTransactionSignatureChecker(const T* txToIn, unsigned int nInIn, const CAmount& amountIn) : txTo(txToIn), nIn(nInIn), amount(amountIn), txdata(nullptr) {}
- GenericTransactionSignatureChecker(const T* txToIn, unsigned int nInIn, const CAmount& amountIn, const PrecomputedTransactionData& txdataIn) : txTo(txToIn), nIn(nInIn), amount(amountIn), txdata(&txdataIn) {}
+ GenericTransactionSignatureChecker(const T* txToIn, unsigned int nInIn, const CAmount& amountIn, MissingDataBehavior mdb) : txTo(txToIn), m_mdb(mdb), nIn(nInIn), amount(amountIn), txdata(nullptr) {}
+ GenericTransactionSignatureChecker(const T* txToIn, unsigned int nInIn, const CAmount& amountIn, const PrecomputedTransactionData& txdataIn, MissingDataBehavior mdb) : txTo(txToIn), m_mdb(mdb), nIn(nInIn), amount(amountIn), txdata(&txdataIn) {}
bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override;
bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, const ScriptExecutionData& execdata, ScriptError* serror = nullptr) const override;
bool CheckLockTime(const CScriptNum& nLockTime) const override;
@@ -272,12 +289,42 @@ public:
using TransactionSignatureChecker = GenericTransactionSignatureChecker<CTransaction>;
using MutableTransactionSignatureChecker = GenericTransactionSignatureChecker<CMutableTransaction>;
+class DeferringSignatureChecker : public BaseSignatureChecker
+{
+protected:
+ BaseSignatureChecker& m_checker;
+
+public:
+ DeferringSignatureChecker(BaseSignatureChecker& checker) : m_checker(checker) {}
+
+ bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override
+ {
+ return m_checker.CheckECDSASignature(scriptSig, vchPubKey, scriptCode, sigversion);
+ }
+
+ bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, const ScriptExecutionData& execdata, ScriptError* serror = nullptr) const override
+ {
+ return m_checker.CheckSchnorrSignature(sig, pubkey, sigversion, execdata, serror);
+ }
+
+ bool CheckLockTime(const CScriptNum& nLockTime) const override
+ {
+ return m_checker.CheckLockTime(nLockTime);
+ }
+ bool CheckSequence(const CScriptNum& nSequence) const override
+ {
+ return m_checker.CheckSequence(nSequence);
+ }
+};
+
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);
size_t CountWitnessSigOps(const CScript& scriptSig, const CScript& scriptPubKey, const CScriptWitness* witness, unsigned int flags);
+bool CheckMinimalPush(const std::vector<unsigned char>& data, opcodetype opcode);
+
int FindAndDelete(CScript& script, const CScript& b);
#endif // BITCOIN_SCRIPT_INTERPRETER_H
diff --git a/src/script/sigcache.cpp b/src/script/sigcache.cpp
index cf47d37e70..65867c1c14 100644
--- a/src/script/sigcache.cpp
+++ b/src/script/sigcache.cpp
@@ -12,8 +12,10 @@
#include <cuckoocache.h>
-#include <boost/thread/lock_types.hpp>
-#include <boost/thread/shared_mutex.hpp>
+#include <algorithm>
+#include <mutex>
+#include <shared_mutex>
+#include <vector>
namespace {
/**
@@ -29,7 +31,7 @@ private:
CSHA256 m_salted_hasher_schnorr;
typedef CuckooCache::cache<uint256, SignatureCacheHasher> map_type;
map_type setValid;
- boost::shared_mutex cs_sigcache;
+ std::shared_mutex cs_sigcache;
public:
CSignatureCache()
@@ -51,26 +53,26 @@ public:
ComputeEntryECDSA(uint256& entry, const uint256 &hash, const std::vector<unsigned char>& vchSig, const CPubKey& pubkey) const
{
CSHA256 hasher = m_salted_hasher_ecdsa;
- hasher.Write(hash.begin(), 32).Write(&pubkey[0], pubkey.size()).Write(&vchSig[0], vchSig.size()).Finalize(entry.begin());
+ hasher.Write(hash.begin(), 32).Write(pubkey.data(), pubkey.size()).Write(vchSig.data(), vchSig.size()).Finalize(entry.begin());
}
void
ComputeEntrySchnorr(uint256& entry, const uint256 &hash, Span<const unsigned char> sig, const XOnlyPubKey& pubkey) const
{
CSHA256 hasher = m_salted_hasher_schnorr;
- hasher.Write(hash.begin(), 32).Write(&pubkey[0], pubkey.size()).Write(sig.data(), sig.size()).Finalize(entry.begin());
+ hasher.Write(hash.begin(), 32).Write(pubkey.data(), pubkey.size()).Write(sig.data(), sig.size()).Finalize(entry.begin());
}
bool
Get(const uint256& entry, const bool erase)
{
- boost::shared_lock<boost::shared_mutex> lock(cs_sigcache);
+ std::shared_lock<std::shared_mutex> lock(cs_sigcache);
return setValid.contains(entry, erase);
}
void Set(const uint256& entry)
{
- boost::unique_lock<boost::shared_mutex> lock(cs_sigcache);
+ std::unique_lock<std::shared_mutex> lock(cs_sigcache);
setValid.insert(entry);
}
uint32_t setup_bytes(size_t n)
diff --git a/src/script/sigcache.h b/src/script/sigcache.h
index bf0ba38c2d..7b6b91c963 100644
--- a/src/script/sigcache.h
+++ b/src/script/sigcache.h
@@ -27,7 +27,7 @@ private:
bool store;
public:
- CachingTransactionSignatureChecker(const CTransaction* txToIn, unsigned int nInIn, const CAmount& amountIn, bool storeIn, PrecomputedTransactionData& txdataIn) : TransactionSignatureChecker(txToIn, nInIn, amountIn, txdataIn), store(storeIn) {}
+ CachingTransactionSignatureChecker(const CTransaction* txToIn, unsigned int nInIn, const CAmount& amountIn, bool storeIn, PrecomputedTransactionData& txdataIn) : TransactionSignatureChecker(txToIn, nInIn, amountIn, txdataIn, MissingDataBehavior::ASSERT_FAIL), store(storeIn) {}
bool VerifyECDSASignature(const std::vector<unsigned char>& vchSig, const CPubKey& vchPubKey, const uint256& sighash) const override;
bool VerifySchnorrSignature(Span<const unsigned char> sig, const XOnlyPubKey& pubkey, const uint256& sighash) const override;
diff --git a/src/script/sign.cpp b/src/script/sign.cpp
index 8afbe9ebed..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) {}
+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,10 +41,61 @@ bool MutableTransactionSignatureCreator::CreateSig(const SigningProvider& provid
if (sigversion == SigVersion::WITNESS_V0 && !key.IsCompressed())
return false;
- uint256 hash = SignatureHash(scriptCode, *txTo, nIn, nHashType, amount, sigversion);
+ // 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, 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;
}
@@ -89,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),
@@ -106,12 +252,10 @@ static bool SignStep(const SigningProvider& provider, const BaseSignatureCreator
std::vector<valtype> vSolutions;
whichTypeRet = Solver(scriptPubKey, vSolutions);
- switch (whichTypeRet)
- {
+ switch (whichTypeRet) {
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;
@@ -165,7 +309,7 @@ static bool SignStep(const SigningProvider& provider, const BaseSignatureCreator
return true;
case TxoutType::WITNESS_V0_SCRIPTHASH:
- CRIPEMD160().Write(&vSolutions[0][0], vSolutions[0].size()).Finalize(h160.begin());
+ CRIPEMD160().Write(vSolutions[0].data(), vSolutions[0].size()).Finalize(h160.begin());
if (GetCScript(provider, sigdata, CScriptID{h160}, scriptRet)) {
ret.push_back(std::vector<unsigned char>(scriptRet.begin(), scriptRet.end()));
return true;
@@ -174,9 +318,10 @@ static bool SignStep(const SigningProvider& provider, const BaseSignatureCreator
sigdata.missing_witness_script = uint256(vSolutions[0]);
return false;
- default:
- 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);
}
static CScript PushAll(const std::vector<valtype>& values)
@@ -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()));
}
@@ -253,17 +404,17 @@ bool ProduceSignature(const SigningProvider& provider, const BaseSignatureCreato
}
namespace {
-class SignatureExtractorChecker final : public BaseSignatureChecker
+class SignatureExtractorChecker final : public DeferringSignatureChecker
{
private:
SignatureData& sigdata;
- BaseSignatureChecker& checker;
public:
- SignatureExtractorChecker(SignatureData& sigdata, BaseSignatureChecker& checker) : sigdata(sigdata), checker(checker) {}
+ SignatureExtractorChecker(SignatureData& sigdata, BaseSignatureChecker& checker) : DeferringSignatureChecker(checker), sigdata(sigdata) {}
+
bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override
{
- if (checker.CheckECDSASignature(scriptSig, vchPubKey, scriptCode, sigversion)) {
+ if (m_checker.CheckECDSASignature(scriptSig, vchPubKey, scriptCode, sigversion)) {
CPubKey pubkey(vchPubKey);
sigdata.signatures.emplace(pubkey.GetID(), SigPair(pubkey, scriptSig));
return true;
@@ -295,7 +446,7 @@ SignatureData DataFromTransaction(const CMutableTransaction& tx, unsigned int nI
Stacks stack(data);
// Get signatures
- MutableTransactionSignatureChecker tx_checker(&tx, nIn, txout.nValue);
+ MutableTransactionSignatureChecker tx_checker(&tx, nIn, txout.nValue, MissingDataBehavior::FAIL);
SignatureExtractorChecker extractor_checker(data, tx_checker);
if (VerifyScript(data.scriptSig, txout.scriptPubKey, &data.scriptWitness, STANDARD_SCRIPT_VERIFY_FLAGS, extractor_checker)) {
data.complete = true;
@@ -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), &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 7967c01858..748f00dda5 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>
@@ -45,8 +48,7 @@ WitnessV0ScriptHash::WitnessV0ScriptHash(const CScript& in)
std::string GetTxnOutputType(TxoutType t)
{
- switch (t)
- {
+ switch (t) {
case TxoutType::NONSTANDARD: return "nonstandard";
case TxoutType::PUBKEY: return "pubkey";
case TxoutType::PUBKEYHASH: return "pubkeyhash";
@@ -89,21 +91,53 @@ static constexpr bool IsSmallInteger(opcodetype opcode)
return opcode >= OP_1 && opcode <= OP_16;
}
-static bool MatchMultisig(const CScript& script, unsigned int& required, std::vector<valtype>& pubkeys)
+static constexpr bool IsPushdataOp(opcodetype opcode)
+{
+ return opcode > OP_FALSE && opcode <= OP_PUSHDATA4;
+}
+
+static constexpr bool IsValidMultisigKeyCount(int n_keys)
+{
+ return n_keys > 0 && n_keys <= MAX_PUBKEYS_PER_MULTISIG;
+}
+
+static bool GetMultisigKeyCount(opcodetype opcode, valtype data, int& count)
+{
+ if (IsSmallInteger(opcode)) {
+ count = CScript::DecodeOP_N(opcode);
+ return IsValidMultisigKeyCount(count);
+ }
+
+ if (IsPushdataOp(opcode)) {
+ if (!CheckMinimalPush(data, opcode)) return false;
+ try {
+ count = CScriptNum(data, /* fRequireMinimal = */ true).getint();
+ return IsValidMultisigKeyCount(count);
+ } catch (const scriptnum_error&) {
+ return false;
+ }
+ }
+
+ return false;
+}
+
+static bool MatchMultisig(const CScript& script, int& required_sigs, std::vector<valtype>& pubkeys)
{
opcodetype opcode;
valtype data;
+ int num_keys;
+
CScript::const_iterator it = script.begin();
if (script.size() < 1 || script.back() != OP_CHECKMULTISIG) return false;
- if (!script.GetOp(it, opcode, data) || !IsSmallInteger(opcode)) return false;
- required = CScript::DecodeOP_N(opcode);
+ if (!script.GetOp(it, opcode, data) || !GetMultisigKeyCount(opcode, data, required_sigs)) return false;
while (script.GetOp(it, opcode, data) && CPubKey::ValidSize(data)) {
pubkeys.emplace_back(std::move(data));
}
- if (!IsSmallInteger(opcode)) return false;
- unsigned int keys = CScript::DecodeOP_N(opcode);
- if (pubkeys.size() != keys || keys < required) return false;
+ if (!GetMultisigKeyCount(opcode, data, num_keys)) return false;
+
+ if (pubkeys.size() != static_cast<unsigned long>(num_keys) || num_keys < required_sigs) return false;
+
return (it + 1 == script.end());
}
@@ -124,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;
}
@@ -164,12 +197,12 @@ TxoutType Solver(const CScript& scriptPubKey, std::vector<std::vector<unsigned c
return TxoutType::PUBKEYHASH;
}
- unsigned int required;
+ int required;
std::vector<std::vector<unsigned char>> keys;
if (MatchMultisig(scriptPubKey, required, keys)) {
- vSolutionsRet.push_back({static_cast<unsigned char>(required)}); // safe as required is in range 1..16
+ vSolutionsRet.push_back({static_cast<unsigned char>(required)}); // safe as required is in range 1..20
vSolutionsRet.insert(vSolutionsRet.end(), keys.begin(), keys.end());
- vSolutionsRet.push_back({static_cast<unsigned char>(keys.size())}); // safe as size is in range 1..16
+ vSolutionsRet.push_back({static_cast<unsigned char>(keys.size())}); // safe as size is in range 1..20
return TxoutType::MULTISIG;
}
@@ -182,7 +215,8 @@ bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet)
std::vector<valtype> vSolutions;
TxoutType whichType = Solver(scriptPubKey, vSolutions);
- if (whichType == TxoutType::PUBKEY) {
+ switch (whichType) {
+ case TxoutType::PUBKEY: {
CPubKey pubKey(vSolutions[0]);
if (!pubKey.IsValid())
return false;
@@ -190,26 +224,33 @@ bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet)
addressRet = PKHash(pubKey);
return true;
}
- else if (whichType == TxoutType::PUBKEYHASH)
- {
+ case TxoutType::PUBKEYHASH: {
addressRet = PKHash(uint160(vSolutions[0]));
return true;
}
- else if (whichType == TxoutType::SCRIPTHASH)
- {
+ case TxoutType::SCRIPTHASH: {
addressRet = ScriptHash(uint160(vSolutions[0]));
return true;
- } else if (whichType == TxoutType::WITNESS_V0_KEYHASH) {
+ }
+ case TxoutType::WITNESS_V0_KEYHASH: {
WitnessV0KeyHash hash;
std::copy(vSolutions[0].begin(), vSolutions[0].end(), hash.begin());
addressRet = hash;
return true;
- } else if (whichType == TxoutType::WITNESS_V0_SCRIPTHASH) {
+ }
+ case TxoutType::WITNESS_V0_SCRIPTHASH: {
WitnessV0ScriptHash hash;
std::copy(vSolutions[0].begin(), vSolutions[0].end(), hash.begin());
addressRet = hash;
return true;
- } else if (whichType == TxoutType::WITNESS_UNKNOWN || whichType == TxoutType::WITNESS_V1_TAPROOT) {
+ }
+ 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);
@@ -217,10 +258,15 @@ bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet)
addressRet = unk;
return true;
}
- // Multisig txns have more than one address...
- return false;
+ case TxoutType::MULTISIG:
+ case TxoutType::NULL_DATA:
+ case TxoutType::NONSTANDARD:
+ return false;
+ } // no default case, so the compiler can warn about missing cases
+ assert(false);
}
+// TODO: from v23 ("addresses" and "reqSigs" deprecated) "ExtractDestinations" should be removed
bool ExtractDestinations(const CScript& scriptPubKey, TxoutType& typeRet, std::vector<CTxDestination>& addressRet, int& nRequiredRet)
{
addressRet.clear();
@@ -290,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);
@@ -311,13 +362,161 @@ CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys)
{
CScript script;
- script << CScript::EncodeOP_N(nRequired);
+ script << nRequired;
for (const CPubKey& key : keys)
script << ToByteVector(key);
- script << CScript::EncodeOP_N(keys.size()) << OP_CHECKMULTISIG;
+ script << keys.size() << OP_CHECKMULTISIG;
+
return script;
}
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) {
+ scripts[key].merge(std::move(control_blocks));
+ }
+}
+
+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;
+}
diff --git a/src/script/standard.h b/src/script/standard.h
index d5d87392ad..285dd4c116 100644
--- a/src/script/standard.h
+++ b/src/script/standard.h
@@ -6,9 +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>
@@ -18,70 +21,6 @@ class CKeyID;
class CScript;
struct ScriptHash;
-template<typename HashType>
-class BaseHash
-{
-protected:
- HashType m_hash;
-
-public:
- BaseHash() : m_hash() {}
- explicit BaseHash(const HashType& in) : m_hash(in) {}
-
- unsigned char* begin()
- {
- return m_hash.begin();
- }
-
- const unsigned char* begin() const
- {
- return m_hash.begin();
- }
-
- unsigned char* end()
- {
- return m_hash.end();
- }
-
- const unsigned char* end() const
- {
- return m_hash.end();
- }
-
- operator std::vector<unsigned char>() const
- {
- return std::vector<unsigned char>{m_hash.begin(), m_hash.end()};
- }
-
- std::string ToString() const
- {
- return m_hash.ToString();
- }
-
- bool operator==(const BaseHash<HashType>& other) const noexcept
- {
- return m_hash == other.m_hash;
- }
-
- bool operator!=(const BaseHash<HashType>& other) const noexcept
- {
- return !(m_hash == other.m_hash);
- }
-
- bool operator<(const BaseHash<HashType>& other) const noexcept
- {
- return m_hash < other.m_hash;
- }
-
- size_t size() const
- {
- return m_hash.size();
- }
-
- unsigned char* data() { return m_hash.data(); }
- const unsigned char* data() const { return m_hash.data(); }
-};
-
/** A reference to a CScript: the Hash160 of its serialization (see script.h) */
class CScriptID : public BaseHash<uint160>
{
@@ -176,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
{
@@ -205,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);
@@ -247,6 +192,8 @@ bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet)
* Note: this function confuses destinations (a subset of CScripts that are
* encodable as an address) with key identifiers (of keys involved in a
* CScript), and its use should be phased out.
+ *
+ * TODO: from v23 ("addresses" and "reqSigs" deprecated) "ExtractDestinations" should be removed
*/
bool ExtractDestinations(const CScript& scriptPubKey, TxoutType& typeRet, std::vector<CTxDestination>& addressRet, int& nRequiredRet);
@@ -263,4 +210,121 @@ 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;
+};
+
#endif // BITCOIN_SCRIPT_STANDARD_H
generated by cgit v1.2.3 (git 2.26.2) at 2025-03-23 14:10:57 +0000