diff options
author | Andrew Chow <achow101-github@achow101.com> | 2022-03-04 07:12:16 -0500 |
---|---|---|
committer | Andrew Chow <achow101-github@achow101.com> | 2022-03-04 07:28:23 -0500 |
commit | bada9636d7f2efbc620fd89107baa2bf3e64a6b8 (patch) | |
tree | 89bb23c7472e0c52330c0ef809ddd138dbb0b802 /src/script | |
parent | 4fae737f4b749b0e2e3cf3fd4dc28db7a1a93b19 (diff) | |
parent | 4828d53eccd52a67631c64cef0ba7df90dff138d (diff) | |
download | bitcoin-bada9636d7f2efbc620fd89107baa2bf3e64a6b8.tar.xz |
Merge bitcoin/bitcoin#24043: Add (sorted)multi_a descriptor for k-of-n multisig inside tr
4828d53eccd52a67631c64cef0ba7df90dff138d Add (sorted)multi_a descriptors to doc/descriptors.md (Pieter Wuille)
b5f33ac1f82aea290b4653af36ac2ad1bf1cce7b Simplify wallet_taproot.py functional test (Pieter Wuille)
eb0667ea96d52db9135514a5e95ab943f6abd8a6 Add tests for (sorted)multi_a derivation/signing (Pieter Wuille)
c17c6aa08df81aa0086d80b50187c8cd60ecc222 Add signing support for (sorted)multi_a scripts (Pieter Wuille)
3eed6fca57d1fa7544f372e6e7de0a9ae1b5715a Add multi_a descriptor inference (Pieter Wuille)
79728c4a3d8a74f276daf1e72abbdecdab85a5d8 Add (sorted)multi_a descriptor and script derivation (Pieter Wuille)
25e95f9ff89a97b87ce218f28274c3c821b2d54d Merge/generalize IsValidMultisigKeyCount/GetMultisigKeyCount (Pieter Wuille)
Pull request description:
This adds a new `multi_a(k,key_1,key_2,...,key_n)` (and corresponding `sortedmulti_a`) descriptor for k-of-n policies inside `tr()`. Semantically it is very similar to the existing `multi()` descriptor, but with the following changes:
* The corresponding script is `<key1> OP_CHECKSIG <key2> OP_CHECKSIGADD <key3> OP_CHECKSIGADD ... <key_n> OP_CHECKSIGADD <k> OP_NUMEQUAL`, rather than the traditional `OP_CHECKMULTISIG`-based script, making it usable inside the `tr()` descriptor.
* The keys can optionally be specified in x-only notation.
* Both the number of keys and the threshold can be as high as 999; this is the limit due to the consensus stacksize=1000 limit
I expect that this functionality will later be replaced with a miniscript-based implementation, but I don't think it's necessary to wait for that.
Limitations:
* The wallet code will for not estimate witness size incorrectly for script path spends, which may result in a (dramatic) fee underpayment with large multi_a scripts.
* The multi_a script construction is (slightly) suboptimal for n-of-n (where a `<key1> OP_CHECKSIGVERIFY ... <key_n-1> OP_CHECKSIGVERIFY <key_n> OP_CHECKSIG` would be better). Such a construction is not included here.
ACKs for top commit:
achow101:
ACK 4828d53eccd52a67631c64cef0ba7df90dff138d
gruve-p:
ACK https://github.com/bitcoin/bitcoin/pull/24043/commits/4828d53eccd52a67631c64cef0ba7df90dff138d
sanket1729:
code review ACK 4828d53eccd52a67631c64cef0ba7df90dff138d
darosior:
Code review ACK 4828d53eccd52a67631c64cef0ba7df90dff138d
Tree-SHA512: 5dcd434b79585f0ff830f7d501d27df5e346f5749f47a3109ec309ebf2cbbad0e1da541eec654026d911ab67fd7cf7793fab0f765628d68d81b96ef2a4d234ce
Diffstat (limited to 'src/script')
-rw-r--r-- | src/script/descriptor.cpp | 68 | ||||
-rw-r--r-- | src/script/script.h | 3 | ||||
-rw-r--r-- | src/script/sign.cpp | 23 | ||||
-rw-r--r-- | src/script/standard.cpp | 72 | ||||
-rw-r--r-- | src/script/standard.h | 4 |
5 files changed, 145 insertions, 25 deletions
diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp index 798c4b3ea0..23540f6aef 100644 --- a/src/script/descriptor.cpp +++ b/src/script/descriptor.cpp @@ -802,6 +802,30 @@ public: bool IsSingleType() const final { return true; } }; +/** A parsed (sorted)multi_a(...) descriptor. Always uses x-only pubkeys. */ +class MultiADescriptor final : public DescriptorImpl +{ + const int m_threshold; + const bool m_sorted; +protected: + std::string ToStringExtra() const override { return strprintf("%i", m_threshold); } + std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider&) const override { + CScript ret; + std::vector<XOnlyPubKey> xkeys; + for (const auto& key : keys) xkeys.emplace_back(key); + if (m_sorted) std::sort(xkeys.begin(), xkeys.end()); + ret << ToByteVector(xkeys[0]) << OP_CHECKSIG; + for (size_t i = 1; i < keys.size(); ++i) { + ret << ToByteVector(xkeys[i]) << OP_CHECKSIGADD; + } + ret << m_threshold << OP_NUMEQUAL; + return Vector(std::move(ret)); + } +public: + MultiADescriptor(int threshold, std::vector<std::unique_ptr<PubkeyProvider>> providers, bool sorted = false) : DescriptorImpl(std::move(providers), sorted ? "sortedmulti_a" : "multi_a"), m_threshold(threshold), m_sorted(sorted) {} + bool IsSingleType() const final { return true; } +}; + /** A parsed sh(...) descriptor. */ class SHDescriptor final : public DescriptorImpl { @@ -1040,7 +1064,6 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const using namespace spanparsing; auto expr = Expr(sp); - bool sorted_multi = false; if (Func("pk", expr)) { auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error); if (!pubkey) return nullptr; @@ -1065,7 +1088,12 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const error = "Can only have combo() at top level"; return nullptr; } - if ((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH) && ((sorted_multi = Func("sortedmulti", expr)) || Func("multi", expr))) { + const bool multi = Func("multi", expr); + const bool sortedmulti = !multi && Func("sortedmulti", expr); + const bool multi_a = !(multi || sortedmulti) && Func("multi_a", expr); + const bool sortedmulti_a = !(multi || sortedmulti || multi_a) && Func("sortedmulti_a", expr); + if (((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH) && (multi || sortedmulti)) || + (ctx == ParseScriptContext::P2TR && (multi_a || sortedmulti_a))) { auto threshold = Expr(expr); uint32_t thres; std::vector<std::unique_ptr<PubkeyProvider>> providers; @@ -1086,9 +1114,12 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const providers.emplace_back(std::move(pk)); key_exp_index++; } - if (providers.empty() || providers.size() > MAX_PUBKEYS_PER_MULTISIG) { + 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; + } 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; } else if (thres < 1) { error = strprintf("Multisig threshold cannot be %d, must be at least 1", thres); return nullptr; @@ -1109,10 +1140,17 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const return nullptr; } } - return std::make_unique<MultisigDescriptor>(thres, std::move(providers), sorted_multi); - } else if (Func("sortedmulti", expr) || Func("multi", expr)) { + 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); + } + } else if (multi || sortedmulti) { error = "Can only have multi/sortedmulti at top level, in sh(), or in wsh()"; return nullptr; + } else if (multi_a || sortedmulti_a) { + error = "Can only have multi_a/sortedmulti_a inside tr()"; + return nullptr; } if ((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH) && Func("wpkh", expr)) { auto pubkey = ParsePubkey(key_exp_index, expr, ParseScriptContext::P2WPKH, out, error); @@ -1257,6 +1295,21 @@ std::unique_ptr<PubkeyProvider> InferXOnlyPubkey(const XOnlyPubKey& xkey, ParseS return key_provider; } +std::unique_ptr<DescriptorImpl> InferMultiA(const CScript& script, ParseScriptContext ctx, const SigningProvider& provider) +{ + auto match = MatchMultiA(script); + if (!match) return {}; + std::vector<std::unique_ptr<PubkeyProvider>> keys; + keys.reserve(match->second.size()); + for (const auto keyspan : match->second) { + if (keyspan.size() != 32) return {}; + auto key = InferXOnlyPubkey(XOnlyPubKey{keyspan}, ctx, provider); + if (!key) return {}; + keys.push_back(std::move(key)); + } + return std::make_unique<MultiADescriptor>(match->first, std::move(keys)); +} + std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptContext ctx, const SigningProvider& provider) { if (ctx == ParseScriptContext::P2TR && script.size() == 34 && script[0] == 32 && script[33] == OP_CHECKSIG) { @@ -1264,6 +1317,11 @@ std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptCo return std::make_unique<PKDescriptor>(InferXOnlyPubkey(key, ctx, provider), true); } + if (ctx == ParseScriptContext::P2TR) { + auto ret = InferMultiA(script, ctx, provider); + if (ret) return ret; + } + std::vector<std::vector<unsigned char>> data; TxoutType txntype = Solver(script, data); diff --git a/src/script/script.h b/src/script/script.h index 8b7a7bb7b3..a89c987306 100644 --- a/src/script/script.h +++ b/src/script/script.h @@ -29,6 +29,9 @@ static const int MAX_OPS_PER_SCRIPT = 201; // Maximum number of public keys per multisig static const int MAX_PUBKEYS_PER_MULTISIG = 20; +/** The limit of keys in OP_CHECKSIGADD-based scripts. It is due to the stack limit in BIP342. */ +static constexpr unsigned int MAX_PUBKEYS_PER_MULTI_A = 999; + // Maximum script length in bytes static const int MAX_SCRIPT_SIZE = 10000; diff --git a/src/script/sign.cpp b/src/script/sign.cpp index 371a937bc8..2e5c49e0b6 100644 --- a/src/script/sign.cpp +++ b/src/script/sign.cpp @@ -174,6 +174,29 @@ static bool SignTaprootScript(const SigningProvider& provider, const BaseSignatu result = Vector(std::move(sig)); return true; } + return false; + } + + // multi_a scripts (<key> OP_CHECKSIG <key> OP_CHECKSIGADD <key> OP_CHECKSIGADD <k> OP_NUMEQUAL) + if (auto match = MatchMultiA(script)) { + std::vector<std::vector<unsigned char>> sigs; + int good_sigs = 0; + for (size_t i = 0; i < match->second.size(); ++i) { + XOnlyPubKey pubkey{*(match->second.rbegin() + i)}; + std::vector<unsigned char> sig; + bool good_sig = CreateTaprootScriptSig(creator, sigdata, provider, sig, pubkey, leaf_hash, sigversion); + if (good_sig && good_sigs < match->first) { + ++good_sigs; + sigs.push_back(std::move(sig)); + } else { + sigs.emplace_back(); + } + } + if (good_sigs == match->first) { + result = std::move(sigs); + return true; + } + return false; } return false; diff --git a/src/script/standard.cpp b/src/script/standard.cpp index 5fb98cc307..806b3169cd 100644 --- a/src/script/standard.cpp +++ b/src/script/standard.cpp @@ -96,51 +96,83 @@ 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) +/** Retrieve a minimally-encoded number in range [min,max] from an (opcode, data) pair, + * whether it's OP_n or through a push. */ +static std::optional<int> GetScriptNumber(opcodetype opcode, valtype data, int min, int max) { + int count; if (IsSmallInteger(opcode)) { count = CScript::DecodeOP_N(opcode); - return IsValidMultisigKeyCount(count); - } - - if (IsPushdataOp(opcode)) { - if (!CheckMinimalPush(data, opcode)) return false; + } else if (IsPushdataOp(opcode)) { + if (!CheckMinimalPush(data, opcode)) return {}; try { count = CScriptNum(data, /* fRequireMinimal = */ true).getint(); - return IsValidMultisigKeyCount(count); } catch (const scriptnum_error&) { - return false; + return {}; } + } else { + return {}; } - - return false; + if (count < min || count > max) return {}; + return count; } 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) || !GetMultisigKeyCount(opcode, data, required_sigs)) return false; + if (!script.GetOp(it, opcode, data)) return false; + auto req_sigs = GetScriptNumber(opcode, data, 1, MAX_PUBKEYS_PER_MULTISIG); + if (!req_sigs) return false; + required_sigs = *req_sigs; while (script.GetOp(it, opcode, data) && CPubKey::ValidSize(data)) { pubkeys.emplace_back(std::move(data)); } - if (!GetMultisigKeyCount(opcode, data, num_keys)) return false; - - if (pubkeys.size() != static_cast<unsigned long>(num_keys) || num_keys < required_sigs) return false; + auto num_keys = GetScriptNumber(opcode, data, required_sigs, MAX_PUBKEYS_PER_MULTISIG); + if (!num_keys) return false; + if (pubkeys.size() != static_cast<unsigned long>(*num_keys)) return false; return (it + 1 == script.end()); } +std::optional<std::pair<int, std::vector<Span<const unsigned char>>>> MatchMultiA(const CScript& script) +{ + std::vector<Span<const unsigned char>> keyspans; + + // Redundant, but very fast and selective test. + if (script.size() == 0 || script[0] != 32 || script.back() != OP_NUMEQUAL) return {}; + + // Parse keys + auto it = script.begin(); + while (script.end() - it >= 34) { + if (*it != 32) return {}; + ++it; + keyspans.emplace_back(&*it, 32); + it += 32; + if (*it != (keyspans.size() == 1 ? OP_CHECKSIG : OP_CHECKSIGADD)) return {}; + ++it; + } + if (keyspans.size() == 0 || keyspans.size() > MAX_PUBKEYS_PER_MULTI_A) return {}; + + // Parse threshold. + opcodetype opcode; + std::vector<unsigned char> data; + if (!script.GetOp(it, opcode, data)) return {}; + if (it == script.end()) return {}; + if (*it != OP_NUMEQUAL) return {}; + ++it; + if (it != script.end()) return {}; + auto threshold = GetScriptNumber(opcode, data, 1, (int)keyspans.size()); + if (!threshold) return {}; + + // Construct result. + return std::pair{*threshold, std::move(keyspans)}; +} + TxoutType Solver(const CScript& scriptPubKey, std::vector<std::vector<unsigned char>>& vSolutionsRet) { vSolutionsRet.clear(); diff --git a/src/script/standard.h b/src/script/standard.h index eb50421768..75bfe2db38 100644 --- a/src/script/standard.h +++ b/src/script/standard.h @@ -191,6 +191,10 @@ CScript GetScriptForDestination(const CTxDestination& dest); /** Generate a P2PK script for the given pubkey. */ CScript GetScriptForRawPubKey(const CPubKey& pubkey); +/** Determine if script is a "multi_a" script. Returns (threshold, keyspans) if so, and nullopt otherwise. + * The keyspans refer to bytes in the passed script. */ +std::optional<std::pair<int, std::vector<Span<const unsigned char>>>> MatchMultiA(const CScript& script LIFETIMEBOUND); + /** Generate a multisig script. */ CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys); |