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