diff options
author | glozow <gloriajzhao@gmail.com> | 2024-08-28 15:41:00 +0100 |
---|---|---|
committer | glozow <gloriajzhao@gmail.com> | 2024-08-28 15:56:15 +0100 |
commit | f93d5553d1e8525d24273be1179f60e39748618e (patch) | |
tree | c83d251ea1fbce7b098c4775e4f5f83ebe325706 /src/script | |
parent | f175a737c9e113c9df0f9e6c28d8fc379bffc620 (diff) | |
parent | a0abcbd3822bd17a1d73c42ccd5b040a150b0501 (diff) |
Merge bitcoin/bitcoin#22838: descriptors: Be able to specify change and receiving in a single descriptor string
a0abcbd3822bd17a1d73c42ccd5b040a150b0501 doc: Mention multipath specifier (Ava Chow)
0019f61fc546b4d5f42eb4086f42560863fe0efb tests: Test importing of multipath descriptors (Ava Chow)
f97d5c137d605ac48f1122a836c9aa5f834957ba wallet, rpc: Allow importdescriptors to import multipath descriptors (Ava Chow)
32dcbca3fb918bc899a0637f876db31c3419aafd rpc: Allow importmulti to import multipath descriptors correctly (Ava Chow)
64dfe3ce4bed9ac168d0b08def8af7485db94ef1 wallet: Move internal to be per key when importing (Ava Chow)
16922455253f47fae0466c4ec6c3adfadcfe9182 tests: Multipath descriptors for scantxoutset and deriveaddresses (Ava Chow)
cddc0ba9a9dca3ca5873d768b3b504cdb2ab947b rpc: Have deriveaddresses derive receiving and change (Ava Chow)
360456cd221501fde3efe11bdba5c6d999dbb323 tests: Multipath descriptors for getdescriptorinfo (Ava Chow)
a90eee444c965bbd7bcddf9656eca9cee14c3aec tests: Add unit tests for multipath descriptors (Ava Chow)
1bbf46e2dae4599d04c79aaacf7c5db00b2e707f descriptors: Change Parse to return vector of descriptors (Ava Chow)
0d640c6f02bc20e5c1be773443dd74d8806d953b descriptors: Have ParseKeypath handle multipath specifiers (Ava Chow)
a5f39b103461a98689fd5d382e8da29037f55bea descriptors: Change ParseScript to return vector of descriptors (Ava Chow)
0d55deae157f4f8226b2419d55e7dc0dfb6e4aec descriptors: Add DescriptorImpl::Clone (Ava Chow)
7e86541f723d62c7ec6768f7f592c09ba2047d9e descriptors: Add PubkeyProvider::Clone (Ava Chow)
Pull request description:
It is convenient to have a descriptor which specifies both receiving and change addresses in a single string. However, as discussed in https://github.com/bitcoin/bitcoin/issues/17190#issuecomment-895515768, it is not feasible to use a generic multipath specification like BIP 88 due to combinatorial blow up and that it would result in unexpected descriptors.
To resolve that problem, this PR proposes a targeted solution which allows only a single pair of 2 derivation indexes to be inserted in the place of a single derivation index. So instead of two descriptor `wpkh(xpub.../0/0/*)` and `wpkh(xpub.../0/1/*)` to represent receive and change addresses, this could be written as `wpkh(xpub.../0/<0;1>/*)`. The multipath specifier is of the form `<NUM;NUM>`. Each `NUM` can have its own hardened specifier, e.g. `<0;1h>` is valid. The multipath specifier can also only appear in one path index in the derivation path.
This results in the parser returning two descriptors. The first descriptor uses the first `NUM` in all pairs present, and the second uses the second `NUM`. In our implementation, if a multipath descriptor is not provided, a pair is still returned, but the second element is just `nullptr`.
The wallet will not output the multipath descriptors (yet). Furthermore, when a multipath descriptor is imported, it is expanded to the two descriptors and each imported on its own, with the second descriptor being implicitly for internal (change) addresses. There is no change to how the wallet stores or outputs descriptors (yet).
Note that the path specifier is different from what was proposed. It uses angle brackets and the semicolon because these are unused characters available in the character set and I wanted to avoid conflicts with characters already in use in descriptors.
Closes #17190
ACKs for top commit:
darosior:
re-ACK a0abcbd3822bd17a1d73c42ccd5b040a150b0501
mjdietzx:
reACK a0abcbd3822bd17a1d73c42ccd5b040a150b0501
pythcoiner:
reACK a0abcbd
furszy:
Code review ACK a0abcbd
glozow:
light code review ACK a0abcbd3822
Tree-SHA512: 84ea40b3fd1b762194acd021cae018c2f09b98e595f5e87de5c832c265cfe8a6d0bc4dae25785392fa90db0f6301ddf9aea787980a29c74f81d04b711ac446c2
Diffstat (limited to 'src/script')
-rw-r--r-- | src/script/descriptor.cpp | 570 | ||||
-rw-r--r-- | src/script/descriptor.h | 4 |
2 files changed, 439 insertions, 135 deletions
diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp index 83b07ae459..5026470edc 100644 --- a/src/script/descriptor.cpp +++ b/src/script/descriptor.cpp @@ -220,6 +220,9 @@ public: virtual std::optional<CPubKey> GetRootPubKey() const = 0; /** Return the extended public key for this PubkeyProvider, if it has one. */ virtual std::optional<CExtPubKey> GetRootExtPubKey() const = 0; + + /** Make a deep copy of this PubkeyProvider */ + virtual std::unique_ptr<PubkeyProvider> Clone() const = 0; }; class OriginPubkeyProvider final : public PubkeyProvider @@ -281,6 +284,10 @@ public: { return m_provider->GetRootExtPubKey(); } + std::unique_ptr<PubkeyProvider> Clone() const override + { + return std::make_unique<OriginPubkeyProvider>(m_expr_index, m_origin, m_provider->Clone(), m_apostrophe); + } }; /** An object representing a parsed constant public key in a descriptor. */ @@ -334,6 +341,10 @@ public: { return std::nullopt; } + std::unique_ptr<PubkeyProvider> Clone() const override + { + return std::make_unique<ConstPubkeyProvider>(m_expr_index, m_pubkey, m_xonly); + } }; enum class DeriveType { @@ -557,6 +568,10 @@ public: { return m_root_extkey; } + std::unique_ptr<PubkeyProvider> Clone() const override + { + return std::make_unique<BIP32PubkeyProvider>(m_expr_index, m_root_extkey, m_path, m_derive, m_apostrophe); + } }; /** Base class for all Descriptor implementations. */ @@ -772,6 +787,8 @@ public: arg->GetPubKeys(pubkeys, ext_pubs); } } + + virtual std::unique_ptr<DescriptorImpl> Clone() const = 0; }; /** A parsed addr(A) descriptor. */ @@ -793,6 +810,10 @@ public: bool ToPrivateString(const SigningProvider& arg, std::string& out) const final { return false; } std::optional<int64_t> ScriptSize() const override { return GetScriptForDestination(m_destination).size(); } + std::unique_ptr<DescriptorImpl> Clone() const override + { + return std::make_unique<AddressDescriptor>(m_destination); + } }; /** A parsed raw(H) descriptor. */ @@ -816,6 +837,11 @@ public: bool ToPrivateString(const SigningProvider& arg, std::string& out) const final { return false; } std::optional<int64_t> ScriptSize() const override { return m_script.size(); } + + std::unique_ptr<DescriptorImpl> Clone() const override + { + return std::make_unique<RawDescriptor>(m_script); + } }; /** A parsed pk(P) descriptor. */ @@ -851,6 +877,11 @@ public: } std::optional<int64_t> MaxSatisfactionElems() const override { return 1; } + + std::unique_ptr<DescriptorImpl> Clone() const override + { + return std::make_unique<PKDescriptor>(m_pubkey_args.at(0)->Clone(), m_xonly); + } }; /** A parsed pkh(P) descriptor. */ @@ -880,6 +911,11 @@ public: } std::optional<int64_t> MaxSatisfactionElems() const override { return 2; } + + std::unique_ptr<DescriptorImpl> Clone() const override + { + return std::make_unique<PKHDescriptor>(m_pubkey_args.at(0)->Clone()); + } }; /** A parsed wpkh(P) descriptor. */ @@ -909,6 +945,11 @@ public: } std::optional<int64_t> MaxSatisfactionElems() const override { return 2; } + + std::unique_ptr<DescriptorImpl> Clone() const override + { + return std::make_unique<WPKHDescriptor>(m_pubkey_args.at(0)->Clone()); + } }; /** A parsed combo(P) descriptor. */ @@ -933,6 +974,10 @@ protected: public: ComboDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), "combo") {} bool IsSingleType() const final { return false; } + std::unique_ptr<DescriptorImpl> Clone() const override + { + return std::make_unique<ComboDescriptor>(m_pubkey_args.at(0)->Clone()); + } }; /** A parsed multi(...) or sortedmulti(...) descriptor */ @@ -971,6 +1016,14 @@ public: } std::optional<int64_t> MaxSatisfactionElems() const override { return 1 + m_threshold; } + + std::unique_ptr<DescriptorImpl> Clone() const override + { + std::vector<std::unique_ptr<PubkeyProvider>> providers; + providers.reserve(m_pubkey_args.size()); + std::transform(m_pubkey_args.begin(), m_pubkey_args.end(), providers.begin(), [](const std::unique_ptr<PubkeyProvider>& p) { return p->Clone(); }); + return std::make_unique<MultisigDescriptor>(m_threshold, std::move(providers), m_sorted); + } }; /** A parsed (sorted)multi_a(...) descriptor. Always uses x-only pubkeys. */ @@ -1007,6 +1060,16 @@ public: } std::optional<int64_t> MaxSatisfactionElems() const override { return m_pubkey_args.size(); } + + std::unique_ptr<DescriptorImpl> Clone() const override + { + std::vector<std::unique_ptr<PubkeyProvider>> providers; + providers.reserve(m_pubkey_args.size()); + for (const auto& arg : m_pubkey_args) { + providers.push_back(arg->Clone()); + } + return std::make_unique<MultiADescriptor>(m_threshold, std::move(providers), m_sorted); + } }; /** A parsed sh(...) descriptor. */ @@ -1052,6 +1115,11 @@ public: if (const auto sub_elems = m_subdescriptor_args[0]->MaxSatisfactionElems()) return 1 + *sub_elems; return {}; } + + std::unique_ptr<DescriptorImpl> Clone() const override + { + return std::make_unique<SHDescriptor>(m_subdescriptor_args.at(0)->Clone()); + } }; /** A parsed wsh(...) descriptor. */ @@ -1088,6 +1156,11 @@ public: if (const auto sub_elems = m_subdescriptor_args[0]->MaxSatisfactionElems()) return 1 + *sub_elems; return {}; } + + std::unique_ptr<DescriptorImpl> Clone() const override + { + return std::make_unique<WSHDescriptor>(m_subdescriptor_args.at(0)->Clone()); + } }; /** A parsed tr(...) descriptor. */ @@ -1153,6 +1226,14 @@ public: // FIXME: See above, we assume keypath spend. return 1; } + + std::unique_ptr<DescriptorImpl> Clone() const override + { + std::vector<std::unique_ptr<DescriptorImpl>> subdescs; + subdescs.reserve(m_subdescriptor_args.size()); + std::transform(m_subdescriptor_args.begin(), m_subdescriptor_args.end(), subdescs.begin(), [](const std::unique_ptr<DescriptorImpl>& d) { return d->Clone(); }); + return std::make_unique<TRDescriptor>(m_pubkey_args.at(0)->Clone(), std::move(subdescs), m_depths); + } }; /* We instantiate Miniscript here with a simple integer as key type. @@ -1271,6 +1352,16 @@ public: std::optional<int64_t> MaxSatisfactionElems() const override { return m_node->GetStackSize(); } + + std::unique_ptr<DescriptorImpl> Clone() const override + { + std::vector<std::unique_ptr<PubkeyProvider>> providers; + providers.reserve(m_pubkey_args.size()); + for (const auto& arg : m_pubkey_args) { + providers.push_back(arg->Clone()); + } + return std::make_unique<MiniscriptDescriptor>(std::move(providers), miniscript::MakeNodeRef<uint32_t>(*m_node)); + } }; /** A parsed rawtr(...) descriptor. */ @@ -1301,6 +1392,11 @@ public: // See above, we assume keypath spend. return 1; } + + std::unique_ptr<DescriptorImpl> Clone() const override + { + return std::make_unique<RawTRDescriptor>(m_pubkey_args.at(0)->Clone()); + } }; //////////////////////////////////////////////////////////////////////////// @@ -1315,50 +1411,110 @@ enum class ParseScriptContext { P2TR, //!< Inside tr() (either internal key, or BIP342 script leaf) }; +std::optional<uint32_t> ParseKeyPathNum(Span<const char> elem, bool& apostrophe, std::string& error) +{ + bool hardened = false; + if (elem.size() > 0) { + const char last = elem[elem.size() - 1]; + if (last == '\'' || last == 'h') { + elem = elem.first(elem.size() - 1); + hardened = true; + apostrophe = last == '\''; + } + } + uint32_t p; + if (!ParseUInt32(std::string(elem.begin(), elem.end()), &p)) { + error = strprintf("Key path value '%s' is not a valid uint32", std::string(elem.begin(), elem.end())); + return std::nullopt; + } else if (p > 0x7FFFFFFFUL) { + error = strprintf("Key path value %u is out of range", p); + return std::nullopt; + } + + return std::make_optional<uint32_t>(p | (((uint32_t)hardened) << 31)); +} + /** - * Parse a key path, being passed a split list of elements (the first element is ignored). + * Parse a key path, being passed a split list of elements (the first element is ignored because it is always the key). * * @param[in] split BIP32 path string, using either ' or h for hardened derivation - * @param[out] out the key path + * @param[out] out Vector of parsed key paths * @param[out] apostrophe only updated if hardened derivation is found * @param[out] error parsing error message + * @param[in] allow_multipath Allows the parsed path to use the multipath specifier * @returns false if parsing failed **/ -[[nodiscard]] bool ParseKeyPath(const std::vector<Span<const char>>& split, KeyPath& out, bool& apostrophe, std::string& error) +[[nodiscard]] bool ParseKeyPath(const std::vector<Span<const char>>& split, std::vector<KeyPath>& out, bool& apostrophe, std::string& error, bool allow_multipath) { + KeyPath path; + std::optional<size_t> multipath_segment_index; + std::vector<uint32_t> multipath_values; + std::unordered_set<uint32_t> seen_multipath; + for (size_t i = 1; i < split.size(); ++i) { - Span<const char> elem = split[i]; - bool hardened = false; - if (elem.size() > 0) { - const char last = elem[elem.size() - 1]; - if (last == '\'' || last == 'h') { - elem = elem.first(elem.size() - 1); - hardened = true; - apostrophe = last == '\''; + const Span<const char>& elem = split[i]; + + // Check if element contain multipath specifier + if (!elem.empty() && elem.front() == '<' && elem.back() == '>') { + if (!allow_multipath) { + error = strprintf("Key path value '%s' specifies multipath in a section where multipath is not allowed", std::string(elem.begin(), elem.end())); + return false; + } + if (multipath_segment_index) { + error = "Multiple multipath key path specifiers found"; + return false; + } + + // Parse each possible value + std::vector<Span<const char>> nums = Split(Span(elem.begin()+1, elem.end()-1), ";"); + if (nums.size() < 2) { + error = "Multipath key path specifiers must have at least two items"; + return false; } + + for (const auto& num : nums) { + const auto& op_num = ParseKeyPathNum(num, apostrophe, error); + if (!op_num) return false; + auto [_, inserted] = seen_multipath.insert(*op_num); + if (!inserted) { + error = strprintf("Duplicated key path value %u in multipath specifier", *op_num); + return false; + } + multipath_values.emplace_back(*op_num); + } + + path.emplace_back(); // Placeholder for multipath segment + multipath_segment_index = path.size()-1; + } else { + const auto& op_num = ParseKeyPathNum(elem, apostrophe, error); + if (!op_num) return false; + path.emplace_back(*op_num); } - uint32_t p; - if (!ParseUInt32(std::string(elem.begin(), elem.end()), &p)) { - error = strprintf("Key path value '%s' is not a valid uint32", std::string(elem.begin(), elem.end())); - return false; - } else if (p > 0x7FFFFFFFUL) { - error = strprintf("Key path value %u is out of range", p); - return false; + } + + if (!multipath_segment_index) { + out.emplace_back(std::move(path)); + } else { + // Replace the multipath placeholder with each value while generating paths + for (size_t i = 0; i < multipath_values.size(); i++) { + KeyPath branch_path = path; + branch_path[*multipath_segment_index] = multipath_values[i]; + out.emplace_back(std::move(branch_path)); } - out.push_back(p | (((uint32_t)hardened) << 31)); } return true; } /** Parse a public key that excludes origin information. */ -std::unique_ptr<PubkeyProvider> ParsePubkeyInner(uint32_t key_exp_index, const Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, bool& apostrophe, std::string& error) +std::vector<std::unique_ptr<PubkeyProvider>> ParsePubkeyInner(uint32_t key_exp_index, const Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, bool& apostrophe, std::string& error) { + std::vector<std::unique_ptr<PubkeyProvider>> ret; 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) { error = "No key provided"; - return nullptr; + return {}; } if (split.size() == 1) { if (IsHex(str)) { @@ -1366,35 +1522,38 @@ std::unique_ptr<PubkeyProvider> ParsePubkeyInner(uint32_t key_exp_index, const S CPubKey pubkey(data); if (pubkey.IsValid() && !pubkey.IsValidNonHybrid()) { error = "Hybrid public keys are not allowed"; - return nullptr; + return {}; } if (pubkey.IsFullyValid()) { if (permit_uncompressed || pubkey.IsCompressed()) { - return std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey, false); + ret.emplace_back(std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey, false)); + return ret; } else { error = "Uncompressed keys are not allowed"; - return nullptr; + return {}; } } 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); + ret.emplace_back(std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey, true)); + return ret; } } error = strprintf("Pubkey '%s' is invalid", str); - return nullptr; + return {}; } CKey key = DecodeSecret(str); if (key.IsValid()) { if (permit_uncompressed || key.IsCompressed()) { CPubKey pubkey = key.GetPubKey(); out.keys.emplace(pubkey.GetID(), key); - return std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey, ctx == ParseScriptContext::P2TR); + ret.emplace_back(std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey, ctx == ParseScriptContext::P2TR)); + return ret; } else { error = "Uncompressed keys are not allowed"; - return nullptr; + return {}; } } } @@ -1402,9 +1561,9 @@ std::unique_ptr<PubkeyProvider> ParsePubkeyInner(uint32_t key_exp_index, const S CExtPubKey extpubkey = DecodeExtPubKey(str); if (!extkey.key.IsValid() && !extpubkey.pubkey.IsValid()) { error = strprintf("key '%s' is not valid", str); - return nullptr; + return {}; } - KeyPath path; + std::vector<KeyPath> paths; DeriveType type = DeriveType::NO; if (std::ranges::equal(split.back(), Span{"*"}.first(1))) { split.pop_back(); @@ -1414,21 +1573,25 @@ std::unique_ptr<PubkeyProvider> ParsePubkeyInner(uint32_t key_exp_index, const S split.pop_back(); type = DeriveType::HARDENED; } - if (!ParseKeyPath(split, path, apostrophe, error)) return nullptr; + if (!ParseKeyPath(split, paths, apostrophe, error, /*allow_multipath=*/true)) return {}; if (extkey.key.IsValid()) { extpubkey = extkey.Neuter(); out.keys.emplace(extpubkey.pubkey.GetID(), extkey.key); } - return std::make_unique<BIP32PubkeyProvider>(key_exp_index, extpubkey, std::move(path), type, apostrophe); + for (auto& path : paths) { + ret.emplace_back(std::make_unique<BIP32PubkeyProvider>(key_exp_index, extpubkey, std::move(path), type, apostrophe)); + } + return ret; } /** Parse a public key including origin information (if enabled). */ -std::unique_ptr<PubkeyProvider> ParsePubkey(uint32_t key_exp_index, const Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error) +std::vector<std::unique_ptr<PubkeyProvider>> ParsePubkey(uint32_t key_exp_index, const Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error) { + std::vector<std::unique_ptr<PubkeyProvider>> ret; auto origin_split = Split(sp, ']'); if (origin_split.size() > 2) { error = "Multiple ']' characters found for a single pubkey"; - return nullptr; + return {}; } // This is set if either the origin or path suffix contains a hardened derivation. bool apostrophe = false; @@ -1438,27 +1601,33 @@ std::unique_ptr<PubkeyProvider> ParsePubkey(uint32_t key_exp_index, const Span<c 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]); - return nullptr; + return {}; } auto slash_split = Split(origin_split[0].subspan(1), '/'); if (slash_split[0].size() != 8) { error = strprintf("Fingerprint is not 4 bytes (%u characters instead of 8 characters)", slash_split[0].size()); - return nullptr; + return {}; } std::string fpr_hex = std::string(slash_split[0].begin(), slash_split[0].end()); if (!IsHex(fpr_hex)) { error = strprintf("Fingerprint '%s' is not hex", fpr_hex); - return nullptr; + return {}; } auto fpr_bytes = ParseHex(fpr_hex); KeyOriginInfo info; static_assert(sizeof(info.fingerprint) == 4, "Fingerprint must be 4 bytes"); assert(fpr_bytes.size() == 4); std::copy(fpr_bytes.begin(), fpr_bytes.end(), info.fingerprint); - if (!ParseKeyPath(slash_split, info.path, apostrophe, error)) return nullptr; - auto provider = ParsePubkeyInner(key_exp_index, origin_split[1], ctx, out, apostrophe, error); - if (!provider) return nullptr; - return std::make_unique<OriginPubkeyProvider>(key_exp_index, std::move(info), std::move(provider), apostrophe); + std::vector<KeyPath> path; + if (!ParseKeyPath(slash_split, path, apostrophe, error, /*allow_multipath=*/false)) return {}; + info.path = path.at(0); + auto providers = ParsePubkeyInner(key_exp_index, origin_split[1], ctx, out, apostrophe, error); + if (providers.empty()) return {}; + ret.reserve(providers.size()); + for (auto& prov : providers) { + ret.emplace_back(std::make_unique<OriginPubkeyProvider>(key_exp_index, info, std::move(prov), apostrophe)); + } + return ret; } std::unique_ptr<PubkeyProvider> InferPubkey(const CPubKey& pubkey, ParseScriptContext ctx, const SigningProvider& provider) @@ -1500,8 +1669,8 @@ struct KeyParser { FlatSigningProvider* m_out; //! Must not be nullptr if parsing from Script. const SigningProvider* m_in; - //! List of keys contained in the Miniscript. - mutable std::vector<std::unique_ptr<PubkeyProvider>> m_keys; + //! List of multipath expanded keys contained in the Miniscript. + mutable std::vector<std::vector<std::unique_ptr<PubkeyProvider>>> m_keys; //! Used to detect key parsing errors within a Miniscript. mutable std::string m_key_parsing_error; //! The script context we're operating within (Tapscript or P2WSH). @@ -1514,7 +1683,7 @@ struct KeyParser { : m_out(out), m_in(in), m_script_ctx(ctx), m_offset(offset) {} bool KeyCompare(const Key& a, const Key& b) const { - return *m_keys.at(a) < *m_keys.at(b); + return *m_keys.at(a).at(0) < *m_keys.at(b).at(0); } ParseScriptContext ParseContext() const { @@ -1530,14 +1699,14 @@ struct KeyParser { assert(m_out); Key key = m_keys.size(); auto pk = ParsePubkey(m_offset + key, {&*begin, &*end}, ParseContext(), *m_out, m_key_parsing_error); - if (!pk) return {}; - m_keys.push_back(std::move(pk)); + if (pk.empty()) return {}; + m_keys.emplace_back(std::move(pk)); return key; } std::optional<std::string> ToString(const Key& key) const { - return m_keys.at(key)->ToString(); + return m_keys.at(key).at(0)->ToString(); } template<typename I> std::optional<Key> FromPKBytes(I begin, I end) const @@ -1548,13 +1717,15 @@ struct KeyParser { XOnlyPubKey pubkey; std::copy(begin, end, pubkey.begin()); if (auto pubkey_provider = InferPubkey(pubkey.GetEvenCorrespondingCPubKey(), ParseContext(), *m_in)) { - m_keys.push_back(std::move(pubkey_provider)); + m_keys.emplace_back(); + m_keys.back().push_back(std::move(pubkey_provider)); return key; } } else if (!miniscript::IsTapscript(m_script_ctx)) { CPubKey pubkey(begin, end); if (auto pubkey_provider = InferPubkey(pubkey, ParseContext(), *m_in)) { - m_keys.push_back(std::move(pubkey_provider)); + m_keys.emplace_back(); + m_keys.back().push_back(std::move(pubkey_provider)); return key; } } @@ -1572,7 +1743,8 @@ struct KeyParser { if (m_in->GetPubKey(keyid, pubkey)) { if (auto pubkey_provider = InferPubkey(pubkey, ParseContext(), *m_in)) { Key key = m_keys.size(); - m_keys.push_back(std::move(pubkey_provider)); + m_keys.emplace_back(); + m_keys.back().push_back(std::move(pubkey_provider)); return key; } } @@ -1586,44 +1758,54 @@ struct KeyParser { /** Parse a script in a particular context. */ // NOLINTNEXTLINE(misc-no-recursion) -std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error) +std::vector<std::unique_ptr<DescriptorImpl>> ParseScript(uint32_t& key_exp_index, Span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error) { using namespace script; + std::vector<std::unique_ptr<DescriptorImpl>> ret; auto expr = Expr(sp); if (Func("pk", expr)) { - auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error); - if (!pubkey) { + auto pubkeys = ParsePubkey(key_exp_index, expr, ctx, out, error); + if (pubkeys.empty()) { error = strprintf("pk(): %s", error); - return nullptr; + return {}; } ++key_exp_index; - return std::make_unique<PKDescriptor>(std::move(pubkey), ctx == ParseScriptContext::P2TR); + for (auto& pubkey : pubkeys) { + ret.emplace_back(std::make_unique<PKDescriptor>(std::move(pubkey), ctx == ParseScriptContext::P2TR)); + } + return ret; } 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) { + auto pubkeys = ParsePubkey(key_exp_index, expr, ctx, out, error); + if (pubkeys.empty()) { error = strprintf("pkh(): %s", error); - return nullptr; + return {}; } ++key_exp_index; - return std::make_unique<PKHDescriptor>(std::move(pubkey)); + for (auto& pubkey : pubkeys) { + ret.emplace_back(std::make_unique<PKHDescriptor>(std::move(pubkey))); + } + return ret; } else if (ctx != ParseScriptContext::P2TR && Func("pkh", expr)) { // Under Taproot, always the Miniscript parser deal with it. error = "Can only have pkh at top level, in sh(), wsh(), or in tr()"; - return nullptr; + return {}; } if (ctx == ParseScriptContext::TOP && Func("combo", expr)) { - auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error); - if (!pubkey) { + auto pubkeys = ParsePubkey(key_exp_index, expr, ctx, out, error); + if (pubkeys.empty()) { error = strprintf("combo(): %s", error); - return nullptr; + return {}; } ++key_exp_index; - return std::make_unique<ComboDescriptor>(std::move(pubkey)); + for (auto& pubkey : pubkeys) { + ret.emplace_back(std::make_unique<ComboDescriptor>(std::move(pubkey))); + } + return ret; } else if (Func("combo", expr)) { error = "Can only have combo() at top level"; - return nullptr; + return {}; } const bool multi = Func("multi", expr); const bool sortedmulti = !multi && Func("sortedmulti", expr); @@ -1633,118 +1815,157 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const (ctx == ParseScriptContext::P2TR && (multi_a || sortedmulti_a))) { auto threshold = Expr(expr); uint32_t thres; - std::vector<std::unique_ptr<PubkeyProvider>> providers; + std::vector<std::vector<std::unique_ptr<PubkeyProvider>>> providers; // List of multipath expanded pubkeys if (!ParseUInt32(std::string(threshold.begin(), threshold.end()), &thres)) { error = strprintf("Multi threshold '%s' is not valid", std::string(threshold.begin(), threshold.end())); - return nullptr; + return {}; } size_t script_size = 0; + size_t max_providers_len = 0; while (expr.size()) { if (!Const(",", expr)) { error = strprintf("Multi: expected ',', got '%c'", expr[0]); - return nullptr; + return {}; } auto arg = Expr(expr); - auto pk = ParsePubkey(key_exp_index, arg, ctx, out, error); - if (!pk) { + auto pks = ParsePubkey(key_exp_index, arg, ctx, out, error); + if (pks.empty()) { error = strprintf("Multi: %s", error); - return nullptr; + return {}; } - script_size += pk->GetSize() + 1; - providers.emplace_back(std::move(pk)); + script_size += pks.at(0)->GetSize() + 1; + max_providers_len = std::max(max_providers_len, pks.size()); + providers.emplace_back(std::move(pks)); key_exp_index++; } if ((multi || sortedmulti) && (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; + return {}; } else if ((multi_a || sortedmulti_a) && (providers.empty() || providers.size() > MAX_PUBKEYS_PER_MULTI_A)) { error = strprintf("Cannot have %u keys in multi_a; must have between 1 and %d keys, inclusive", providers.size(), MAX_PUBKEYS_PER_MULTI_A); - return nullptr; + return {}; } else if (thres < 1) { error = strprintf("Multisig threshold cannot be %d, must be at least 1", thres); - return nullptr; + return {}; } else if (thres > providers.size()) { error = strprintf("Multisig threshold cannot be larger than the number of keys; threshold is %d but only %u keys specified", thres, providers.size()); - return nullptr; + return {}; } if (ctx == ParseScriptContext::TOP) { if (providers.size() > 3) { error = strprintf("Cannot have %u pubkeys in bare multisig; only at most 3 pubkeys", providers.size()); - return nullptr; + return {}; } } 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 {}; } } - if (multi || sortedmulti) { - return std::make_unique<MultisigDescriptor>(thres, std::move(providers), sortedmulti); - } else { - return std::make_unique<MultiADescriptor>(thres, std::move(providers), sortedmulti_a); + + // Make sure all vecs are of the same length, or exactly length 1 + // For length 1 vectors, clone key providers until vector is the same length + for (auto& vec : providers) { + if (vec.size() == 1) { + for (size_t i = 1; i < max_providers_len; ++i) { + vec.emplace_back(vec.at(0)->Clone()); + } + } else if (vec.size() != max_providers_len) { + error = strprintf("multi(): Multipath derivation paths have mismatched lengths"); + return {}; + } } + + // Build the final descriptors vector + for (size_t i = 0; i < max_providers_len; ++i) { + // Build final pubkeys vectors by retrieving the i'th subscript for each vector in subscripts + std::vector<std::unique_ptr<PubkeyProvider>> pubs; + pubs.reserve(providers.size()); + for (auto& pub : providers) { + pubs.emplace_back(std::move(pub.at(i))); + } + if (multi || sortedmulti) { + ret.emplace_back(std::make_unique<MultisigDescriptor>(thres, std::move(pubs), sortedmulti)); + } else { + ret.emplace_back(std::make_unique<MultiADescriptor>(thres, std::move(pubs), sortedmulti_a)); + } + } + return ret; } else if (multi || sortedmulti) { error = "Can only have multi/sortedmulti at top level, in sh(), or in wsh()"; - return nullptr; + return {}; } else if (multi_a || sortedmulti_a) { error = "Can only have multi_a/sortedmulti_a inside tr()"; - return nullptr; + return {}; } if ((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH) && Func("wpkh", expr)) { - auto pubkey = ParsePubkey(key_exp_index, expr, ParseScriptContext::P2WPKH, out, error); - if (!pubkey) { + auto pubkeys = ParsePubkey(key_exp_index, expr, ParseScriptContext::P2WPKH, out, error); + if (pubkeys.empty()) { error = strprintf("wpkh(): %s", error); - return nullptr; + return {}; } key_exp_index++; - return std::make_unique<WPKHDescriptor>(std::move(pubkey)); + for (auto& pubkey : pubkeys) { + ret.emplace_back(std::make_unique<WPKHDescriptor>(std::move(pubkey))); + } + return ret; } else if (Func("wpkh", expr)) { error = "Can only have wpkh() at top level or inside sh()"; - return nullptr; + return {}; } 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 std::make_unique<SHDescriptor>(std::move(desc)); + auto descs = ParseScript(key_exp_index, expr, ParseScriptContext::P2SH, out, error); + if (descs.empty() || expr.size()) return {}; + std::vector<std::unique_ptr<DescriptorImpl>> ret; + ret.reserve(descs.size()); + for (auto& desc : descs) { + ret.push_back(std::make_unique<SHDescriptor>(std::move(desc))); + } + return ret; } else if (Func("sh", expr)) { error = "Can only have sh() at top level"; - return nullptr; + return {}; } 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 std::make_unique<WSHDescriptor>(std::move(desc)); + auto descs = ParseScript(key_exp_index, expr, ParseScriptContext::P2WSH, out, error); + if (descs.empty() || expr.size()) return {}; + for (auto& desc : descs) { + ret.emplace_back(std::make_unique<WSHDescriptor>(std::move(desc))); + } + return ret; } else if (Func("wsh", expr)) { error = "Can only have wsh() at top level or inside sh()"; - return nullptr; + return {}; } if (ctx == ParseScriptContext::TOP && Func("addr", expr)) { CTxDestination dest = DecodeDestination(std::string(expr.begin(), expr.end())); if (!IsValidDestination(dest)) { error = "Address is not valid"; - return nullptr; + return {}; } - return std::make_unique<AddressDescriptor>(std::move(dest)); + ret.emplace_back(std::make_unique<AddressDescriptor>(std::move(dest))); + return ret; } else if (Func("addr", expr)) { error = "Can only have addr() at top level"; - return nullptr; + return {}; } 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) { + auto internal_keys = ParsePubkey(key_exp_index, arg, ParseScriptContext::P2TR, out, error); + if (internal_keys.empty()) { error = strprintf("tr(): %s", error); - return nullptr; + return {}; } + size_t max_providers_len = internal_keys.size(); ++key_exp_index; - std::vector<std::unique_ptr<DescriptorImpl>> subscripts; //!< list of script subexpressions + std::vector<std::vector<std::unique_ptr<DescriptorImpl>>> subscripts; //!< list of multipath expanded 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; + return {}; } /** 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. @@ -1758,19 +1979,20 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const 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; + return {}; } } // 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; + if (subscripts.back().empty()) return {}; + max_providers_len = std::max(max_providers_len, subscripts.back().size()); 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; + return {}; } branches.pop_back(); // move up one level after encountering '}' } @@ -1778,7 +2000,7 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const if (branches.size() && !branches.back()) { if (!Const(",", expr)) { error = strprintf("tr(): expected ',' after script expression"); - return nullptr; + return {}; } branches.back() = true; // And now we're in a right branch. } @@ -1786,40 +2008,82 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const // 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; + return {}; } } assert(TaprootBuilder::ValidDepths(depths)); - return std::make_unique<TRDescriptor>(std::move(internal_key), std::move(subscripts), std::move(depths)); + + // Make sure all vecs are of the same length, or exactly length 1 + // For length 1 vectors, clone subdescs until vector is the same length + for (auto& vec : subscripts) { + if (vec.size() == 1) { + for (size_t i = 1; i < max_providers_len; ++i) { + vec.emplace_back(vec.at(0)->Clone()); + } + } else if (vec.size() != max_providers_len) { + error = strprintf("tr(): Multipath subscripts have mismatched lengths"); + return {}; + } + } + + if (internal_keys.size() > 1 && internal_keys.size() != max_providers_len) { + error = strprintf("tr(): Multipath internal key mismatches multipath subscripts lengths"); + return {}; + } + + while (internal_keys.size() < max_providers_len) { + internal_keys.emplace_back(internal_keys.at(0)->Clone()); + } + + // Build the final descriptors vector + for (size_t i = 0; i < max_providers_len; ++i) { + // Build final subscripts vectors by retrieving the i'th subscript for each vector in subscripts + std::vector<std::unique_ptr<DescriptorImpl>> this_subs; + this_subs.reserve(subscripts.size()); + for (auto& subs : subscripts) { + this_subs.emplace_back(std::move(subs.at(i))); + } + ret.emplace_back(std::make_unique<TRDescriptor>(std::move(internal_keys.at(i)), std::move(this_subs), depths)); + } + return ret; + + } else if (Func("tr", expr)) { error = "Can only have tr at top level"; - return nullptr; + return {}; } if (ctx == ParseScriptContext::TOP && Func("rawtr", expr)) { auto arg = Expr(expr); if (expr.size()) { error = strprintf("rawtr(): only one key expected."); - return nullptr; + return {}; + } + auto output_keys = ParsePubkey(key_exp_index, arg, ParseScriptContext::P2TR, out, error); + if (output_keys.empty()) { + error = strprintf("rawtr(): %s", error); + return {}; } - auto output_key = ParsePubkey(key_exp_index, arg, ParseScriptContext::P2TR, out, error); - if (!output_key) return nullptr; ++key_exp_index; - return std::make_unique<RawTRDescriptor>(std::move(output_key)); + for (auto& pubkey : output_keys) { + ret.emplace_back(std::make_unique<RawTRDescriptor>(std::move(pubkey))); + } + return ret; } else if (Func("rawtr", expr)) { error = "Can only have rawtr at top level"; - return nullptr; + return {}; } if (ctx == ParseScriptContext::TOP && Func("raw", expr)) { std::string str(expr.begin(), expr.end()); if (!IsHex(str)) { error = "Raw script is not hex"; - return nullptr; + return {}; } auto bytes = ParseHex(str); - return std::make_unique<RawDescriptor>(CScript(bytes.begin(), bytes.end())); + ret.emplace_back(std::make_unique<RawDescriptor>(CScript(bytes.begin(), bytes.end()))); + return ret; } else if (Func("raw", expr)) { error = "Can only have raw() at top level"; - return nullptr; + return {}; } // Process miniscript expressions. { @@ -1828,12 +2092,12 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const auto node = miniscript::FromString(std::string(expr.begin(), expr.end()), parser); if (parser.m_key_parsing_error != "") { error = std::move(parser.m_key_parsing_error); - return nullptr; + return {}; } if (node) { if (ctx != ParseScriptContext::P2WSH && ctx != ParseScriptContext::P2TR) { error = "Miniscript expressions can only be used in wsh or tr."; - return nullptr; + return {}; } if (!node->IsSane() || node->IsNotSatisfiable()) { // Try to find the first insane sub for better error reporting. @@ -1858,24 +2122,52 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const } else { error += " is not satisfiable"; } - return nullptr; + return {}; } // A signature check is required for a miniscript to be sane. Therefore no sane miniscript // may have an empty list of public keys. CHECK_NONFATAL(!parser.m_keys.empty()); key_exp_index += parser.m_keys.size(); - return std::make_unique<MiniscriptDescriptor>(std::move(parser.m_keys), std::move(node)); + // Make sure all vecs are of the same length, or exactly length 1 + // For length 1 vectors, clone subdescs until vector is the same length + size_t num_multipath = std::max_element(parser.m_keys.begin(), parser.m_keys.end(), + [](const std::vector<std::unique_ptr<PubkeyProvider>>& a, const std::vector<std::unique_ptr<PubkeyProvider>>& b) { + return a.size() < b.size(); + })->size(); + + for (auto& vec : parser.m_keys) { + if (vec.size() == 1) { + for (size_t i = 1; i < num_multipath; ++i) { + vec.emplace_back(vec.at(0)->Clone()); + } + } else if (vec.size() != num_multipath) { + error = strprintf("Miniscript: Multipath derivation paths have mismatched lengths"); + return {}; + } + } + + // Build the final descriptors vector + for (size_t i = 0; i < num_multipath; ++i) { + // Build final pubkeys vectors by retrieving the i'th subscript for each vector in subscripts + std::vector<std::unique_ptr<PubkeyProvider>> pubs; + pubs.reserve(parser.m_keys.size()); + for (auto& pub : parser.m_keys) { + pubs.emplace_back(std::move(pub.at(i))); + } + ret.emplace_back(std::make_unique<MiniscriptDescriptor>(std::move(pubs), node)); + } + return ret; } } if (ctx == ParseScriptContext::P2SH) { error = "A function is needed within P2SH"; - return nullptr; + return {}; } else if (ctx == ParseScriptContext::P2WSH) { error = "A function is needed within P2WSH"; - return nullptr; + return {}; } error = strprintf("'%s' is not a valid descriptor function", std::string(expr.begin(), expr.end())); - return nullptr; + return {}; } std::unique_ptr<DescriptorImpl> InferMultiA(const CScript& script, ParseScriptContext ctx, const SigningProvider& provider) @@ -2013,7 +2305,12 @@ std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptCo KeyParser parser(/* out = */nullptr, /* in = */&provider, /* ctx = */script_ctx); auto node = miniscript::FromScript(script, parser); if (node && node->IsSane()) { - return std::make_unique<MiniscriptDescriptor>(std::move(parser.m_keys), std::move(node)); + std::vector<std::unique_ptr<PubkeyProvider>> keys; + keys.reserve(parser.m_keys.size()); + for (auto& key : parser.m_keys) { + keys.emplace_back(std::move(key.at(0))); + } + return std::make_unique<MiniscriptDescriptor>(std::move(keys), std::move(node)); } } @@ -2068,14 +2365,21 @@ bool CheckChecksum(Span<const char>& sp, bool require_checksum, std::string& err return true; } -std::unique_ptr<Descriptor> Parse(const std::string& descriptor, FlatSigningProvider& out, std::string& error, bool require_checksum) +std::vector<std::unique_ptr<Descriptor>> Parse(const std::string& descriptor, FlatSigningProvider& out, std::string& error, bool require_checksum) { Span<const char> sp{descriptor}; - if (!CheckChecksum(sp, require_checksum, error)) return nullptr; + if (!CheckChecksum(sp, require_checksum, error)) return {}; 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; + if (sp.size() == 0 && !ret.empty()) { + std::vector<std::unique_ptr<Descriptor>> descs; + descs.reserve(ret.size()); + for (auto& r : ret) { + descs.emplace_back(std::unique_ptr<Descriptor>(std::move(r))); + } + return descs; + } + return {}; } std::string GetDescriptorChecksum(const std::string& descriptor) diff --git a/src/script/descriptor.h b/src/script/descriptor.h index e78a775330..473649a314 100644 --- a/src/script/descriptor.h +++ b/src/script/descriptor.h @@ -173,9 +173,9 @@ struct Descriptor { * is set, the checksum is mandatory - otherwise it is optional. * * If a parse error occurs, or the checksum is missing/invalid, or anything - * else is wrong, `nullptr` is returned. + * else is wrong, an empty vector is returned. */ -std::unique_ptr<Descriptor> Parse(const std::string& descriptor, FlatSigningProvider& out, std::string& error, bool require_checksum = false); +std::vector<std::unique_ptr<Descriptor>> Parse(const std::string& descriptor, FlatSigningProvider& out, std::string& error, bool require_checksum = false); /** Get the checksum for a `descriptor`. * |