Support up to 20 keys for multisig under Segwit context

darosior commented at 2:12 pm on January 6, 2021: member

As described in #20620 multisigs are currently limited to 16 keys in descriptors and RPC helpers, even for P2WSH and P2SH-P2WSH.

This adds support for multisig with up to 20 keys (which are already standard) for Segwit v0 context for descriptors (wsh(), sh(wsh())) and RPC helpers.

Fixes https://github.com/bitcoin/bitcoin/issues/20620

DrahtBot added the label RPC/REST/ZMQ on Jan 6, 2021

darosior force-pushed on Jan 6, 2021

in src/rpc/util.cpp:189 in 97198085ae outdated

184@@ -185,16 +185,12 @@ CTxDestination AddAndGetMultisigDestination(const int required, const std::vecto
185     if ((int)pubkeys.size() < required) {
186         throw JSONRPCError(RPC_INVALID_PARAMETER, strprintf("not enough keys supplied (got %u keys, but need at least %d to redeem)", pubkeys.size(), required));
187     }
188-    if (pubkeys.size() > 16) {
189-        throw JSONRPCError(RPC_INVALID_PARAMETER, "Number of keys involved in the multisignature address creation > 16\nReduce the number");
190+    if (pubkeys.size() > MAX_PUBKEYS_PER_MULTISIG) {
191+        throw JSONRPCError(RPC_INVALID_PARAMETER, "Number of keys involved in the multisignature address creation > 20\nReduce the number");

luke-jr commented at 5:19 pm on January 6, 2021:

Perhaps should strprintf the 20 from the constant

darosior commented at 6:57 pm on January 6, 2021:

Done

in src/rpc/util.cpp:248 in 97198085ae outdated

198@@ -203,6 +199,10 @@ CTxDestination AddAndGetMultisigDestination(const int required, const std::vecto
199         }
200     }
201 
202+    if (type == OutputType::LEGACY && script_out.size() > MAX_SCRIPT_ELEMENT_SIZE) {

luke-jr commented at 5:19 pm on January 6, 2021:

Shouldn’t this be OutputType::P2SH_SEGWIT?

darosior commented at 5:58 pm on January 6, 2021:

No, the limit only applies to raw P2SH not to embedded witness programs

in src/script/descriptor.cpp:901 in 97198085ae outdated

896@@ -897,8 +897,8 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t key_exp_index, Span<const c
897             providers.emplace_back(std::move(pk));
898             key_exp_index++;
899         }
900-        if (providers.empty() || providers.size() > 16) {
901-            error = strprintf("Cannot have %u keys in multisig; must have between 1 and 16 keys, inclusive", providers.size());
902+        if (providers.empty() || providers.size() > MAX_PUBKEYS_PER_MULTISIG) {
903+            error = strprintf("Cannot have %u keys in multisig; must have between 1 and %i keys, inclusive", providers.size(), MAX_PUBKEYS_PER_MULTISIG);

luke-jr commented at 5:21 pm on January 6, 2021:

Please use %d or %s here.

%i is explicitly locale-involved, which we don’t want in RPC.

darosior commented at 6:57 pm on January 6, 2021:

Done

in src/script/standard.cpp:93 in 97198085ae outdated

88@@ -89,21 +89,49 @@ static constexpr bool IsSmallInteger(opcodetype opcode)
89     return opcode >= OP_1 && opcode <= OP_16;
90 }
91 
92+/** Valid number of keys in a multisig are [1,20]. */
93+static constexpr bool IsValidKeysNumber(unsigned int n_keys)

luke-jr commented at 5:23 pm on January 6, 2021:

IsValidMultisigKeyCount?

in src/script/standard.cpp:116 in 97198085ae outdated

113+        try {
114+            required = CScriptNum(data, true).getint();
115+        } catch (const scriptnum_error&) {
116+            return false;
117+        }
118+    }

luke-jr commented at 5:28 pm on January 6, 2021:

This wants to be a function of its own I think :)

darosior commented at 6:57 pm on January 6, 2021:

Yep :) Done

DrahtBot commented at 6:56 pm on January 6, 2021: member

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#19651 (wallet: importdescriptors update existing by S3RK)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

darosior force-pushed on Jan 6, 2021

in src/script/standard.cpp:109 in bf7f509902 outdated

104+            count = CScriptNum(data, true).getint();
105+        } catch (const scriptnum_error&) {
106+            return false;
107+        }
108+    }
109+    if (!IsValidMultisigKeyCount(count)) return false;

mjdietzx commented at 9:30 pm on January 6, 2021:

What are your thoughts on just doing: return IsValidMultisigKeyCount(count); here?

darosior commented at 9:43 pm on January 6, 2021:

Right, it’s cleaner :) Done

in src/script/standard.cpp:98 in bf7f509902 outdated

93+static constexpr bool IsValidMultisigKeyCount(unsigned int n_keys)
94+{
95+    return n_keys > 0 && n_keys <= MAX_PUBKEYS_PER_MULTISIG;
96+}
97+
98+static bool GetMultisigKeyCount(const CScript& script, CScript::const_iterator& it, unsigned int& count, opcodetype opcode, valtype data)

mjdietzx commented at 9:32 pm on January 6, 2021:

It seems the params script and it aren’t used?

darosior commented at 9:40 pm on January 6, 2021:

Arg they were part of a (incorrect) previous version, good catch!

in src/script/standard.cpp:127 in bf7f509902 outdated

126     while (script.GetOp(it, opcode, data) && CPubKey::ValidSize(data)) {
127         pubkeys.emplace_back(std::move(data));
128     }
129-    if (!IsSmallInteger(opcode)) return false;
130-    unsigned int keys = CScript::DecodeOP_N(opcode);
131+    if (!GetMultisigKeyCount(script, it, keys, opcode, data)) return false;

mjdietzx commented at 9:36 pm on January 6, 2021:

Is this necessary? Seems you already return false on this condition at L123?

darosior commented at 9:44 pm on January 6, 2021:

On L123 i get the count of the required number of keys (the M of the M of N) and here the total number of keys (the N of the M of N)

in src/script/standard.cpp:123 in bf7f509902 outdated

120     CScript::const_iterator it = script.begin();
121     if (script.size() < 1 || script.back() != OP_CHECKMULTISIG) return false;
122 
123-    if (!script.GetOp(it, opcode, data) || !IsSmallInteger(opcode)) return false;
124-    required = CScript::DecodeOP_N(opcode);
125+    if (!script.GetOp(it, opcode, data) || !GetMultisigKeyCount(script, it, required, opcode, data)) return false;

mjdietzx commented at 9:37 pm on January 6, 2021:

Does this change behavior, and if so is it intended? bc of the else condition https://github.com/bitcoin/bitcoin/pull/20867/files#diff-a1732fc4dc1526b294a41db3f2d3d5e863ec76e68ee3f73449618551f7a469ebR102 I would think !GetMultisigKeyCount evaluates differently than the original !IsSmallInteger(opcode)

darosior commented at 9:42 pm on January 6, 2021:

It does, that’s actually the feature implemented in this PR: handle up to 20 keys (therefore we need to handle not only small integers (<=16) but also pushed ones).

in src/script/standard.cpp:353 in bf7f509902 outdated

335@@ -312,10 +336,11 @@ CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys)
336 {
337     CScript script;
338 
339-    script << CScript::EncodeOP_N(nRequired);
340+    script << nRequired;

mjdietzx commented at 9:38 pm on January 6, 2021:

Why does this change (and L342) belong in this PR?

darosior commented at 9:45 pm on January 6, 2021:

Look at the implementation of operator<< in CScript. It handles all integers while EncodeOP_N only supports small (<=16) ones.

darosior force-pushed on Jan 6, 2021

sipa commented at 0:29 am on January 7, 2021: member

Some thing to test:

Descriptors for P2WSH or P2SH-P2WSH multisig can be expanded, signed for, and those spends relay if keys <= 20.
Descriptors for P2SH multisig can be expanded, signed for, and those spends relay if keys <= 15 (if compressed) or <= 7 (if uncompressed).
Inferring descriptor from a multisig script with keys <= 16, but using a direct push rather than OP_n, fails.

in src/script/standard.cpp:102 in 0fd1bf6539 outdated

 97+
 98+static bool GetMultisigKeyCount(opcodetype opcode, valtype data, unsigned int& count)
 99+{
100+    if (IsSmallInteger(opcode)) {
101+        count = CScript::DecodeOP_N(opcode);
102+    } else {

laanwj commented at 12:57 pm on January 7, 2021:

Doesn’t this need to check what opcode is ?

darosior commented at 1:22 pm on January 7, 2021:

data would be empty if opcode is not a PUSHDATA and therefore count would be 0 and we’d return false. Would an explicitly check be preferable ?

EDIT: … But that’s relying on the content of data which is not set in this function (i previously had GetOp here that’s the reason for my initial comment). Will add a check, thanks!

darosior force-pushed on Jan 7, 2021

darosior force-pushed on Jan 9, 2021

darosior commented at 7:26 pm on January 9, 2021: member

Descriptors for P2WSH or P2SH-P2WSH multisig can be expanded, signed for, and those spends relay if keys <= 20.

I think this one is adressed in the functional tests commit ?

Descriptors for P2SH multisig can be expanded, signed for, and those spends relay if keys <= 15 (if compressed) or <= 7 (if uncompressed).

Added a P2SH multisig standardness check in the functional tests commit.

 0diff --git a/test/functional/wallet_importdescriptors.py b/test/functional/wallet_importdescriptors.py
 1index 2cd185720..292ada606 100755
 2--- a/test/functional/wallet_importdescriptors.py
 3+++ b/test/functional/wallet_importdescriptors.py
 4@@ -459,7 +459,7 @@ class ImportDescriptorsTest(BitcoinTestFramework):
 5         assert_equal(tx_signed_2['complete'], True)
 6         self.nodes[1].sendrawtransaction(tx_signed_2['hex'])
 7 
 8-        self.log.info("We can create and use a huge multisig")
 9+        self.log.info("We can create and use a huge multisig under P2WSH")
10         self.nodes[1].createwallet(wallet_name='wmulti_priv_big', blank=True, descriptors=True)
11         wmulti_priv_big = self.nodes[1].get_wallet_rpc('wmulti_priv_big')
12         res = wmulti_priv_big.importdescriptors([
13@@ -493,6 +493,43 @@ class ImportDescriptorsTest(BitcoinTestFramework):
14         assert_equal(len(decoded['vin'][0]['txinwitness']), 22)
15 
16 
17+        self.log.info("Under P2SH, multisig are standard with up to 15 "
18+                      "compressed keys")
19+        self.nodes[1].createwallet(wallet_name='multi_priv_big_legacy',
20+                                   blank=True, descriptors=True)
21+        multi_priv_big = self.nodes[1].get_wallet_rpc('multi_priv_big_legacy')
22+        res = multi_priv_big.importdescriptors([
23+        {
24+            "desc": descsum_create("sh(multi(15,tprv8ZgxMBicQKsPeAjsABad2QinheaMrvqvCkkBZwBRttYcMALE8yVG5GUsQdLmLWNFeYjUuqKiSay7z2bcvhbi1DEdYMRi5JeedkTKbTuJCda/*,tprv8ZgxMBicQKsPeJ59P23D5yq4HpFgfbqph7kYPCnMVPhNdktyAwbusJoMc9QgksGyV9LQwqPQQjMzjTLVtvkwb2Z6EmFiVtTHQyq2WKVrfRT/*,tprv8ZgxMBicQKsPeZ2m1aQaPA1BJ27xPphNfQQ354z77W8mRLKqwyUyonvusrZgQX3bwAQ2WFo1PPjHoAqiWnM1LMvkkmd3ZkXc5HdjxDarhYk/*,tprv8ZgxMBicQKsPeQ2FPA64vJ91G1Bb9kTARbusYSN9QwNmP9dF5M8xhuX8u8coWD8mq24xjwftnT8hteJ4riMYyjeSsxKMaBd1PX1NDDbxqV2/*,tprv8ZgxMBicQKsPe7nycwReBmFGn5HuTJbzLN7iUpDhFESMGvEZWnurvjrV4otDDEnvsrZ2a8X4o19xGXaTkEJsPUApHvMCeVTmAf2i5bBaSez/*,tprv8ZgxMBicQKsPdauRxSzxXTi85dQd4sSwS5sot1gFLUrJUoUGqzohDgPxTpmBjtmDfYjmNidA1hoF6b5gXh83JBdjcosm5rFeN7xUAM4DFxo/*,tprv8ZgxMBicQKsPfAhMFUPNJMkKVMYebxr1A1bdm8itERTuoDXXhpSQvsXjUQmrTmXsM8x5BxuQjaqF2H5tUXMXuGbiPTpzQKj2NZ6hCsUYJNX/*,tprv8ZgxMBicQKsPddHiYzgaoQthYpCCnnG8TQXaBfQEcoqt2xvzCVXHW7FF1n34LDLoJYghmArzW6ej7xiJpWCDn8sng4XT3uPHxc3MysiE3GS/*,tprv8ZgxMBicQKsPdyon5QGdU6tStoUPSJxidv8u75MWCVjCRhEzoFL2zhEHEx2ejmLExRxANbbqGc84jx3EVjWUVxYShEfDvCeMk3a2Fcqk1Qa/*,tprv8ZgxMBicQKsPcv2k7VmW4rKybZ5QpMUtNWdARqs8rYDoZ7tpg27njFquM2GmdXPgCKpqykwKpZ9mqBn7h7umz1sBm6avKmxcbzs1K8C6bVt/*,tprv8ZgxMBicQKsPea6F9YnfAPrzAQbn1Zeb5h9tp1pjnZQ9WqAds1JYhq9mFBumjBhWn3xmsJ4QmBqDGMeJQ5gPXmZrPBjX5hB8NfUgm7HvUyc/*,tprv8ZgxMBicQKsPf2RCn731KSorsuEjA8hwJqwub6BUBJYGpZV5Z6VQPKGEKqGJxEDtgFxeGpkU9zhjNn82SiiiaSqNXnqXofhZAgn8YirN5y2/*,tprv8ZgxMBicQKsPf94VtPAD9Czz4SButGX49W8PM6nxecBrWACbrULsUb9KRBo6gJs9mCQpX4q7DGCWTtkf27htQwXJGhNCDNJ3WCufeV2CE5T/*,tprv8ZgxMBicQKsPdoKuEXhCT2vPyojxxf1C9U75madMvMdqhQf1sET2ToeaDJRP8mzbjYjYq7DV8C233tMmBoPzubVukuNyfu8uxrUJcbdGEhP/*,tprv8ZgxMBicQKsPetrYKgU8APCNusa2Sq2px2TaNNJ6TKhzcBfzCbrVKArA3tXc6JYa3VZN6ose6564Far2ikD2DKguYQahVd7dSa9BAnVbRJe/*))"),
25+            "active": True,
26+            "range": 1000,
27+            "next_index": 0,
28+            "timestamp": "now"
29+        },
30+        {
31+            "desc":
32+            descsum_create("sh(multi(15,tprv8ZgxMBicQKsPeAjsABad2QinheaMrvqvCkkBZwBRttYcMALE8yVG5GUsQdLmLWNFeYjUuqKiSay7z2bcvhbi1DEdYMRi5JeedkTKbTuJCda/1/*,tprv8ZgxMBicQKsPeJ59P23D5yq4HpFgfbqph7kYPCnMVPhNdktyAwbusJoMc9QgksGyV9LQwqPQQjMzjTLVtvkwb2Z6EmFiVtTHQyq2WKVrfRT/1/*,tprv8ZgxMBicQKsPeZ2m1aQaPA1BJ27xPphNfQQ354z77W8mRLKqwyUyonvusrZgQX3bwAQ2WFo1PPjHoAqiWnM1LMvkkmd3ZkXc5HdjxDarhYk/1/*,tprv8ZgxMBicQKsPeQ2FPA64vJ91G1Bb9kTARbusYSN9QwNmP9dF5M8xhuX8u8coWD8mq24xjwftnT8hteJ4riMYyjeSsxKMaBd1PX1NDDbxqV2/1/*,tprv8ZgxMBicQKsPe7nycwReBmFGn5HuTJbzLN7iUpDhFESMGvEZWnurvjrV4otDDEnvsrZ2a8X4o19xGXaTkEJsPUApHvMCeVTmAf2i5bBaSez/1/*,tprv8ZgxMBicQKsPdauRxSzxXTi85dQd4sSwS5sot1gFLUrJUoUGqzohDgPxTpmBjtmDfYjmNidA1hoF6b5gXh83JBdjcosm5rFeN7xUAM4DFxo/1/*,tprv8ZgxMBicQKsPfAhMFUPNJMkKVMYebxr1A1bdm8itERTuoDXXhpSQvsXjUQmrTmXsM8x5BxuQjaqF2H5tUXMXuGbiPTpzQKj2NZ6hCsUYJNX/1/*,tprv8ZgxMBicQKsPddHiYzgaoQthYpCCnnG8TQXaBfQEcoqt2xvzCVXHW7FF1n34LDLoJYghmArzW6ej7xiJpWCDn8sng4XT3uPHxc3MysiE3GS/1/*,tprv8ZgxMBicQKsPdyon5QGdU6tStoUPSJxidv8u75MWCVjCRhEzoFL2zhEHEx2ejmLExRxANbbqGc84jx3EVjWUVxYShEfDvCeMk3a2Fcqk1Qa/1/*,tprv8ZgxMBicQKsPcv2k7VmW4rKybZ5QpMUtNWdARqs8rYDoZ7tpg27njFquM2GmdXPgCKpqykwKpZ9mqBn7h7umz1sBm6avKmxcbzs1K8C6bVt/1/*,tprv8ZgxMBicQKsPea6F9YnfAPrzAQbn1Zeb5h9tp1pjnZQ9WqAds1JYhq9mFBumjBhWn3xmsJ4QmBqDGMeJQ5gPXmZrPBjX5hB8NfUgm7HvUyc/1/*,tprv8ZgxMBicQKsPf2RCn731KSorsuEjA8hwJqwub6BUBJYGpZV5Z6VQPKGEKqGJxEDtgFxeGpkU9zhjNn82SiiiaSqNXnqXofhZAgn8YirN5y2/1/*,tprv8ZgxMBicQKsPf94VtPAD9Czz4SButGX49W8PM6nxecBrWACbrULsUb9KRBo6gJs9mCQpX4q7DGCWTtkf27htQwXJGhNCDNJ3WCufeV2CE5T/1/*,tprv8ZgxMBicQKsPdoKuEXhCT2vPyojxxf1C9U75madMvMdqhQf1sET2ToeaDJRP8mzbjYjYq7DV8C233tMmBoPzubVukuNyfu8uxrUJcbdGEhP/1/*,tprv8ZgxMBicQKsPetrYKgU8APCNusa2Sq2px2TaNNJ6TKhzcBfzCbrVKArA3tXc6JYa3VZN6ose6564Far2ikD2DKguYQahVd7dSa9BAnVbRJe/1/*))"),
33+            "active": True,
34+            "internal" : True,
35+            "range": 1000,
36+            "next_index": 0,
37+            "timestamp": "now"
38+        }])
39+        assert_equal(res[0]['success'], True)
40+        assert_equal(res[1]['success'], True)
41+
42+        addr = multi_priv_big.getnewaddress("", "legacy")
43+        w0.sendtoaddress(addr, 10)
44+        self.nodes[0].generate(6)
45+        self.sync_all()
46+        # It is standard and would relay.
47+        txid = multi_priv_big.sendtoaddress(w0.getnewaddress(), 10, "", "",
48+                                            True)
49+        decoded = multi_priv_big.decoderawtransaction(
50+            multi_priv_big.gettransaction(txid)['hex']
51+        )
52+
53+
54         self.log.info("Combo descriptors cannot be active")
55         self.test_importdesc({"desc": descsum_create("combo(tpubDCJtdt5dgJpdhW4MtaVYDhG4T4tF6jcLR1PxL43q9pq1mxvXgMS9Mzw1HnXG15vxUGQJMMSqCQHMTy3F1eW5VkgVroWzchsPD5BUojrcWs8/*)"),
56                               "active": True,

Inferring descriptor from a multisig script with keys <= 16, but using a direct push rather than OP_n, fails.

Added a test for this, and fixed the implementation to require minimal encoding.

 0diff --git a/src/script/standard.cpp b/src/script/standard.cpp
 1index 8a2666e48..422eeef1d 100644
 2--- a/src/script/standard.cpp
 3+++ b/src/script/standard.cpp
 4@@ -110,6 +110,8 @@ static bool GetMultisigKeyCount(opcodetype opcode, valtype data, unsigned int& c
 5     if (IsPushdataOp(opcode)) {
 6         try {
 7             count = CScriptNum(data, true).getint();
 8+            // Not minimally encoded count.
 9+            if (count <= 16) return false;
10             return IsValidMultisigKeyCount(count);
11         } catch (const scriptnum_error&) {
12             return false;
13diff --git a/src/test/descriptor_tests.cpp b/src/test/descriptor_tests.cpp
14index 3a3c30407..9f508a7d6 100644
15--- a/src/test/descriptor_tests.cpp
16+++ b/src/test/descriptor_tests.cpp
17@@ -2,6 +2,7 @@
18 // Distributed under the MIT software license, see the accompanying
19 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
20 
21+#include <pubkey.h>
22 #include <script/descriptor.h>
23 #include <script/sign.h>
24 #include <script/standard.h>
25@@ -26,6 +27,14 @@ void CheckUnparsable(const std::string& prv, const std::string& pub, const std::
26     BOOST_CHECK(error == expected_error);
27 }
28 
29+/** Check that the script is inferred as non-standard */
30+void CheckInferRaw(const CScript& script)
31+{
32+    FlatSigningProvider dummy_provider;
33+    std::unique_ptr<Descriptor> desc = InferDescriptor(script, dummy_provider);
34+    BOOST_CHECK(desc->ToString().rfind("raw(", 0) == 0);
35+}
36+
37 constexpr int DEFAULT = 0;
38 constexpr int RANGE = 1; // Expected to be ranged descriptor
39 constexpr int HARDENED = 2; // Derivation needs access to private keys
40@@ -364,6 +373,27 @@ Check("sh(wsh(multi(20,KzoAz5CanayRKex3fSLQ2BwJpN7U52gZvxMyk78nDMHuqrUxuSJy,KwGN
41     CheckUnparsable("", "addr(asdf)", "Address is not valid"); // Invalid address
42     CheckUnparsable("", "raw(asdf)", "Raw script is not hex"); // Invalid script
43     CheckUnparsable("", "raw(Ü)#00000000", "Invalid characters in payload"); // Invalid chars
44+
45+    // A 2of4 but using a direct push rather than OP_2
46+    CScript nonminimalmultisig;
47+    CKey keys[4];
48+    nonminimalmultisig << std::vector<unsigned char>{2};
49+    for (int i = 0; i < 4; i++) {
50+        keys[i].MakeNewKey(true);
51+        nonminimalmultisig << ToByteVector(keys[i].GetPubKey());
52+    }
53+    nonminimalmultisig << 4 << OP_CHECKMULTISIG;
54+    CheckInferRaw(nonminimalmultisig);
55+
56+    // A 2of4 but using a direct push rather than OP_4
57+    nonminimalmultisig.clear();
58+    nonminimalmultisig << 2;
59+    for (int i = 0; i < 4; i++) {
60+        keys[i].MakeNewKey(true);
61+        nonminimalmultisig << ToByteVector(keys[i].GetPubKey());
62+    }
63+    nonminimalmultisig << std::vector<unsigned char>{4} << OP_CHECKMULTISIG;
64+    CheckInferRaw(nonminimalmultisig);
65 }
66 
67 BOOST_AUTO_TEST_SUITE_END()

darosior force-pushed on Jan 10, 2021

darosior commented at 11:32 am on January 10, 2021: member

Changed the first commit’s message to clarify the sigop count calculation for 17-20 keys multisigs:

Note that this does not change the sigOpCount calculation (as it would break consensus). Therefore 1-16 keys multisigs are counted as 1-16 sigops and 17-20 keys multisigs are counted as 20 sigops.

DrahtBot commented at 11:45 am on January 13, 2021: member

🕵️ @achow101 has been requested to review this pull request as specified in the REVIEWERS file.

in src/script/standard.cpp:98 in 149948d681 outdated

 95+}
 96+
 97+/** Valid number of keys in a multisig are [1,20]. */
 98+static constexpr bool IsValidMultisigKeyCount(unsigned int n_keys)
 99+{
100+    return n_keys > 0 && n_keys <= MAX_PUBKEYS_PER_MULTISIG;

achow101 commented at 6:32 pm on February 19, 2021:

0 is a valid value for number of keys, so this should be

0    return n_keys >= 0 && n_keys <= MAX_PUBKEYS_PER_MULTISIG;

darosior commented at 6:53 pm on February 19, 2021:

I don’t think it’s valid according to policy: IsSmallInteger currently requires the number of keys to be >= OP_1

luke-jr commented at 7:29 pm on February 19, 2021:

Policy is not validity…

darosior commented at 7:35 pm on February 19, 2021:

@luke-jr i think here the term was used to refer to policy, as MatchMultisig is only used to define standardness. What i meant is that i don’t think i changed behaviour here (IsSmallInteger was already required for both counts).

luke-jr commented at 7:38 pm on February 19, 2021:

Maybe the function should get renamed for clarity :)

IsAcceptableMultisigKeyCount or such

achow101 commented at 7:45 pm on February 19, 2021:

Ah, IsSmallInteger also disallows 0, so behavior is not changing in this area.

achow101 commented at 6:45 pm on February 19, 2021: member

Concept ACK

achow101 commented at 7:46 pm on February 19, 2021: member

Code Review ACK 773e853dd4e506bf06a1381f95f80523ac66c663

in src/script/descriptor.cpp:917 in 8c24b50a6e outdated

913@@ -914,6 +914,7 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t key_exp_index, Span<const c
914             }
915         }
916         if (ctx == ParseScriptContext::P2SH) {
917+            // This limits the maximum number of pubkeys to 15.

sipa commented at 7:54 pm on February 19, 2021:

Perhaps clarify that this depends on whether they’re compressed or uncompressed (but it’s 15 for all compressed)?

sipa commented at 7:57 pm on February 19, 2021: member

utACK 773e853dd4e506bf06a1381f95f80523ac66c663

darosior force-pushed on Feb 19, 2021

darosior commented at 10:06 pm on February 19, 2021: member

Clarified limit is 15 only for compressed key as per @sipa comment, and added release notes for wallet and RPC changes.

 01:  149948d68 = 1:  858d652a3 script: match multisigs with up to MAX_PUBKEYS_PER_MULTISIG keys
 12:  8c24b50a6 ! 2:  af7977d62 script: allow up to 20 keys in wsh() descriptors
 2    @@ src/script/descriptor.cpp: std::unique_ptr<DescriptorImpl> ParseScript(uint32_t
 3                  }
 4              }
 5              if (ctx == ParseScriptContext::P2SH) {
 6    -+            // This limits the maximum number of pubkeys to 15.
 7    ++            // This limits the maximum number of compressed pubkeys to 15.
 8                  if (script_size + 3 > MAX_SCRIPT_ELEMENT_SIZE) {
 9                      error = strprintf("P2SH script is too large, %d bytes is larger than %d bytes", script_size + 3, MAX_SCRIPT_ELEMENT_SIZE);
10                      return nullptr;
113:  77a336643 = 3:  4f673fec9 test/functional: standarness sanity checks for P2(W)SH multisig
124:  773e853dd = 4:  b5656ce02 rpc/util: multisig: only check redeemScript size is <= 520 for P2SH
13-:  --------- > 5:  c6db00c9a doc: add release notes for 20867

darosior force-pushed on Feb 19, 2021

darosior force-pushed on Feb 20, 2021

darosior commented at 0:25 am on February 20, 2021: member

Force pushed again as the fuzzer found an UB (that can not be triggered under normal conditions though) when using CScriptNum().get_int().

Fixed by just using int instead of unsigned int in MatchMultisig (which is fine, since required to be in [1, 20]).

0SUMMARY: UndefinedBehaviorSanitizer: implicit-integer-sign-change script/standard.cpp:111:21 in 
1MS: 0 ; base unit: 0000000000000000000000000000000000000000
20x5c,0x1c,0x5c,0x1,0x1,0x1,0x1,0x1,0x1,0x1,0x1,0x1,0x9,0x59,0x0,0xf,0x1,0x1,0x1,0x1,0x1,0x0,0x1,0x1,0x1,0x11,0x1,0x1,0x1,0x1,0x1,0x41,0x21,0x1,0x1,0x1,0x1,0x1,0x5,0x26,0x1,0x1,0x1,0x1,0x0,0x0,0x0,0xf9,0x1,0x1,0x2,0x1,0x1,0x1,0x1,0x1,0x1,0x1,0x1,0x11,0x1,0xbe,0x1,0x1,0x1,0x1,0x1,0x1,0x1,0x1,0x1,0xae,0xae,0xae,0xae,0xae,0xae,0xae,0x1,0x9,0x1,0x1,0x1,0x1,0x1,0x1,0x10,0xff,0xfd,0x0,0xff,0x1,0xf3,0x76,0x32,0x76,0x1,0x1,0x1,0x1,0x1,0x3,0xf4,0xc3,0x0,0x1a,0x55,
3\\\x1c\\\x01\x01\x01\x01\x01\x01\x01\x01\x01\x09Y\x00\x0f\x01\x01\x01\x01\x01\x00\x01\x01\x01\x11\x01\x01\x01\x01\x01A!\x01\x01\x01\x01\x01\x05&\x01\x01\x01\x01\x00\x00\x00\xf9\x01\x01\x02\x01\x01\x01\x01\x01\x01\x01\x01\x11\x01\xbe\x01\x01\x01\x01\x01\x01\x01\x01\x01\xae\xae\xae\xae\xae\xae\xae\x01\x09\x01\x01\x01\x01\x01\x01\x10\xff\xfd\x00\xff\x01\xf3v2v\x01\x01\x01\x01\x01\x03\xf4\xc3\x00\x1aU
4artifact_prefix='./'; Test unit written to ./crash-c456b1fe61b6ce9ed56247da7294b3be77a12bba
5Base64: XBxcAQEBAQEBAQEBCVkADwEBAQEBAAEBAREBAQEBAUEhAQEBAQEFJgEBAQEAAAD5AQECAQEBAQEBAQERAb4BAQEBAQEBAQGurq6urq6uAQkBAQEBAQEQ//0A/wHzdjJ2AQEBAQED9MMAGlU=

 0diff --git a/src/script/standard.cpp b/src/script/standard.cpp
 1index 84a3a0557..4ad8d8925 100644
 2--- a/src/script/standard.cpp
 3+++ b/src/script/standard.cpp
 4@@ -99,7 +99,7 @@ static constexpr bool IsValidMultisigKeyCount(unsigned int n_keys)
 5     return n_keys > 0 && n_keys <= MAX_PUBKEYS_PER_MULTISIG;
 6 }
 7 
 8-static bool GetMultisigKeyCount(opcodetype opcode, valtype data, unsigned int& count)
 9+static bool GetMultisigKeyCount(opcodetype opcode, valtype data, int& count)
10 {
11     if (IsSmallInteger(opcode)) {
12         count = CScript::DecodeOP_N(opcode);
13@@ -120,11 +120,11 @@ static bool GetMultisigKeyCount(opcodetype opcode, valtype data, unsigned int& c
14     return false;
15 }
16 
17-static bool MatchMultisig(const CScript& script, unsigned int& required, std::vector<valtype>& pubkeys)
18+static bool MatchMultisig(const CScript& script, int& required, std::vector<valtype>& pubkeys)
19 {
20     opcodetype opcode;
21     valtype data;
22-    unsigned int keys;
23+    int keys;
24 
25     CScript::const_iterator it = script.begin();
26     if (script.size() < 1 || script.back() != OP_CHECKMULTISIG) return false;
27@@ -135,7 +135,7 @@ static bool MatchMultisig(const CScript& script, unsigned int& required, std::ve
28     }
29     if (!GetMultisigKeyCount(opcode, data, keys)) return false;
30 
31-    if (pubkeys.size() != keys || keys < required) return false;
32+    if (pubkeys.size() != static_cast<unsigned long>(keys) || keys < required) return false;
33 
34     return (it + 1 == script.end());
35 }
36@@ -197,7 +197,7 @@ TxoutType Solver(const CScript& scriptPubKey, std::vector<std::vector<unsigned c
37         return TxoutType::PUBKEYHASH;
38     }
39 
40-    unsigned int required;
41+    int required;
42     std::vector<std::vector<unsigned char>> keys;
43     if (MatchMultisig(scriptPubKey, required, keys)) {
44         vSolutionsRet.push_back({static_cast<unsigned char>(required)}); // safe as required is in range 1..20

MarcoFalke commented at 7:44 am on February 20, 2021: member

Thanks, added to https://github.com/bitcoin-core/bitcoin-devwiki/wiki/Fuzz-Trophies-(vulnerabilities)#non-exploitable-issues

darosior commented at 8:56 am on March 22, 2021: member

@achow101 @sipa : small ping as it’s been a month since you ACKed and the only changes are addressing Pieter’s nit and fixing a fuzzer finding regarding our casts.

achow101 commented at 4:18 pm on March 22, 2021: member

re-ACK e839b4c57560ede17d9de94d6814b49576a9450f

fanquake requested review from meshcollider on Mar 23, 2021

fanquake requested review from instagibbs on Mar 23, 2021

in src/script/standard.cpp:96 in 3e2a93575c outdated

92+static constexpr bool IsPushdataOp(opcodetype opcode)
93+{
94+    return opcode > OP_FALSE && opcode <= OP_PUSHDATA4;
95+}
96+
97+/** Valid number of keys in a multisig are [1,20]. */

instagibbs commented at 6:42 am on March 24, 2021:

minor nit: I don’t think the comment serves much purpose

in src/script/standard.cpp:111 in 3e2a93575c outdated

107+        return IsValidMultisigKeyCount(count);
108+    }
109+
110+    if (IsPushdataOp(opcode)) {
111+        try {
112+            count = CScriptNum(data, true).getint();

instagibbs commented at 6:46 am on March 24, 2021:

nit: please annotate the boolean arg

instagibbs commented at 6:52 am on March 24, 2021:

should we be writing to the value before we’re sure it succeeds?

darosior commented at 9:34 am on March 24, 2021:

The caller should (and does) only regard the value of count if the getter returns true. I could make sure that on error we always return before writing to count but it would make the logic even more convoluted than it already is in order to support an usage that should not exist in the first place?

in src/script/standard.cpp:127 in 3e2a93575c outdated

123+
124+static bool MatchMultisig(const CScript& script, int& required, std::vector<valtype>& pubkeys)
125 {
126     opcodetype opcode;
127     valtype data;
128+    int keys;

instagibbs commented at 6:53 am on March 24, 2021:

suggestion for clarity: s/keys/num_keys/

in src/script/standard.cpp:123 in 3e2a93575c outdated

119+    }
120+
121+    return false;
122+}
123+
124+static bool MatchMultisig(const CScript& script, int& required, std::vector<valtype>& pubkeys)

instagibbs commented at 6:54 am on March 24, 2021:

while you’re at it, maybe s/required/required_sigs/

in src/script/standard.cpp:101 in 3e2a93575c outdated

 98+static constexpr bool IsValidMultisigKeyCount(unsigned int n_keys)
 99+{
100+    return n_keys > 0 && n_keys <= MAX_PUBKEYS_PER_MULTISIG;
101+}
102+
103+static bool GetMultisigKeyCount(opcodetype opcode, valtype data, int& count)

instagibbs commented at 6:55 am on March 24, 2021:

slight misnomer, we’re using it to check for ranges of keys and sig counts…

darosior commented at 9:31 am on March 24, 2021:

We do some checks, but its primary function is to affect a value to count, hence getting the key count?

in src/script/standard.cpp:203 in 3e2a93575c outdated

196@@ -163,7 +197,7 @@ TxoutType Solver(const CScript& scriptPubKey, std::vector<std::vector<unsigned c
197         return TxoutType::PUBKEYHASH;
198     }
199 
200-    unsigned int required;
201+    int required;
202     std::vector<std::vector<unsigned char>> keys;
203     if (MatchMultisig(scriptPubKey, required, keys)) {
204         vSolutionsRet.push_back({static_cast<unsigned char>(required)}); // safe as required is in range 1..16

instagibbs commented at 6:57 am on March 24, 2021:

comments out of date

instagibbs commented at 8:57 am on March 24, 2021:

this gets changed in another commit, nevermind

in test/functional/wallet_importdescriptors.py:467 in f02ce6e17b outdated

458@@ -459,6 +459,77 @@ def run_test(self):
459         assert_equal(tx_signed_2['complete'], True)
460         self.nodes[1].sendrawtransaction(tx_signed_2['hex'])
461 
462+        self.log.info("We can create and use a huge multisig under P2WSH")
463+        self.nodes[1].createwallet(wallet_name='wmulti_priv_big', blank=True, descriptors=True)
464+        wmulti_priv_big = self.nodes[1].get_wallet_rpc('wmulti_priv_big')
465+        res = wmulti_priv_big.importdescriptors([
466+        {
467+            "desc": descsum_create("wsh(sortedmulti(20,tprv8ZgxMBicQKsPd46RGA7DzyDpfBN1TACK2ChMHo89RQ3KaPmutZ24WszUaRBCBs53rGtqMVphPsU7tUrkP1DiPR3uUFtH5uk8g2rkzniWnoa/*,tprv8ZgxMBicQKsPeZSeYx7VXDDTs3XrTcmZQpRLbAeSQFCQGgKwR4gKpcxHaKdoTNHniv4EPDJNdzA3KxRrrBHcAgth8fU5X4oCndkkxk39iAt/*,tprv8ZgxMBicQKsPfC9EhMMAk6RWfSBSF1U9DxVDjTemmxrFYZnKXHtPsJkKQf5yq72Ee5bwTi7bUswK2k9gcSRntp7M8dksDt4jZdSWyB8PSAF/*,tprv8ZgxMBicQKsPe6ZEmpUg1T1njzZGuu8B8ohbUjTQXcHDs9tntGUDgmRtHVxoDd2AKQMjefN2FJY8xWfNDRfzrJzX9ud6euttDsTYa8Sv2MM/*,tprv8ZgxMBicQKsPdNANjQngj3KvAWpEfoTD1b5cxNTxuCnBXrfFRAjDFCec7mSWMeAS6AnEJhLGVmXuw9ZuoeRtbdJXMoBBk7A3Uo5nT3rPUfd/*,tprv8ZgxMBicQKsPeAjsABad2QinheaMrvqvCkkBZwBRttYcMALE8yVG5GUsQdLmLWNFeYjUuqKiSay7z2bcvhbi1DEdYMRi5JeedkTKbTuJCda/*,tprv8ZgxMBicQKsPeJ59P23D5yq4HpFgfbqph7kYPCnMVPhNdktyAwbusJoMc9QgksGyV9LQwqPQQjMzjTLVtvkwb2Z6EmFiVtTHQyq2WKVrfRT/*,tprv8ZgxMBicQKsPeZ2m1aQaPA1BJ27xPphNfQQ354z77W8mRLKqwyUyonvusrZgQX3bwAQ2WFo1PPjHoAqiWnM1LMvkkmd3ZkXc5HdjxDarhYk/*,tprv8ZgxMBicQKsPeQ2FPA64vJ91G1Bb9kTARbusYSN9QwNmP9dF5M8xhuX8u8coWD8mq24xjwftnT8hteJ4riMYyjeSsxKMaBd1PX1NDDbxqV2/*,tprv8ZgxMBicQKsPe7nycwReBmFGn5HuTJbzLN7iUpDhFESMGvEZWnurvjrV4otDDEnvsrZ2a8X4o19xGXaTkEJsPUApHvMCeVTmAf2i5bBaSez/*,tprv8ZgxMBicQKsPdauRxSzxXTi85dQd4sSwS5sot1gFLUrJUoUGqzohDgPxTpmBjtmDfYjmNidA1hoF6b5gXh83JBdjcosm5rFeN7xUAM4DFxo/*,tprv8ZgxMBicQKsPfAhMFUPNJMkKVMYebxr1A1bdm8itERTuoDXXhpSQvsXjUQmrTmXsM8x5BxuQjaqF2H5tUXMXuGbiPTpzQKj2NZ6hCsUYJNX/*,tprv8ZgxMBicQKsPddHiYzgaoQthYpCCnnG8TQXaBfQEcoqt2xvzCVXHW7FF1n34LDLoJYghmArzW6ej7xiJpWCDn8sng4XT3uPHxc3MysiE3GS/*,tprv8ZgxMBicQKsPdyon5QGdU6tStoUPSJxidv8u75MWCVjCRhEzoFL2zhEHEx2ejmLExRxANbbqGc84jx3EVjWUVxYShEfDvCeMk3a2Fcqk1Qa/*,tprv8ZgxMBicQKsPcv2k7VmW4rKybZ5QpMUtNWdARqs8rYDoZ7tpg27njFquM2GmdXPgCKpqykwKpZ9mqBn7h7umz1sBm6avKmxcbzs1K8C6bVt/*,tprv8ZgxMBicQKsPea6F9YnfAPrzAQbn1Zeb5h9tp1pjnZQ9WqAds1JYhq9mFBumjBhWn3xmsJ4QmBqDGMeJQ5gPXmZrPBjX5hB8NfUgm7HvUyc/*,tprv8ZgxMBicQKsPf2RCn731KSorsuEjA8hwJqwub6BUBJYGpZV5Z6VQPKGEKqGJxEDtgFxeGpkU9zhjNn82SiiiaSqNXnqXofhZAgn8YirN5y2/*,tprv8ZgxMBicQKsPf94VtPAD9Czz4SButGX49W8PM6nxecBrWACbrULsUb9KRBo6gJs9mCQpX4q7DGCWTtkf27htQwXJGhNCDNJ3WCufeV2CE5T/*,tprv8ZgxMBicQKsPdoKuEXhCT2vPyojxxf1C9U75madMvMdqhQf1sET2ToeaDJRP8mzbjYjYq7DV8C233tMmBoPzubVukuNyfu8uxrUJcbdGEhP/*,tprv8ZgxMBicQKsPetrYKgU8APCNusa2Sq2px2TaNNJ6TKhzcBfzCbrVKArA3tXc6JYa3VZN6ose6564Far2ikD2DKguYQahVd7dSa9BAnVbRJe/*))"),

instagibbs commented at 8:54 am on March 24, 2021:

nit: I might suggest building this string programmatically, just re-using the same key 15 times?

darosior commented at 10:39 am on March 24, 2021:

Yes, fstrings ftw :)

in test/functional/wallet_importdescriptors.py:475 in f02ce6e17b outdated

470+            "next_index": 0,
471+            "timestamp": "now"
472+        },
473+        {
474+            "desc":
475+            descsum_create("wsh(sortedmulti(20,tprv8ZgxMBicQKsPd46RGA7DzyDpfBN1TACK2ChMHo89RQ3KaPmutZ24WszUaRBCBs53rGtqMVphPsU7tUrkP1DiPR3uUFtH5uk8g2rkzniWnoa/*,tprv8ZgxMBicQKsPeZSeYx7VXDDTs3XrTcmZQpRLbAeSQFCQGgKwR4gKpcxHaKdoTNHniv4EPDJNdzA3KxRrrBHcAgth8fU5X4oCndkkxk39iAt/1/*,tprv8ZgxMBicQKsPfC9EhMMAk6RWfSBSF1U9DxVDjTemmxrFYZnKXHtPsJkKQf5yq72Ee5bwTi7bUswK2k9gcSRntp7M8dksDt4jZdSWyB8PSAF/1/*,tprv8ZgxMBicQKsPe6ZEmpUg1T1njzZGuu8B8ohbUjTQXcHDs9tntGUDgmRtHVxoDd2AKQMjefN2FJY8xWfNDRfzrJzX9ud6euttDsTYa8Sv2MM/1/*,tprv8ZgxMBicQKsPdNANjQngj3KvAWpEfoTD1b5cxNTxuCnBXrfFRAjDFCec7mSWMeAS6AnEJhLGVmXuw9ZuoeRtbdJXMoBBk7A3Uo5nT3rPUfd/1/*,tprv8ZgxMBicQKsPeAjsABad2QinheaMrvqvCkkBZwBRttYcMALE8yVG5GUsQdLmLWNFeYjUuqKiSay7z2bcvhbi1DEdYMRi5JeedkTKbTuJCda/1/*,tprv8ZgxMBicQKsPeJ59P23D5yq4HpFgfbqph7kYPCnMVPhNdktyAwbusJoMc9QgksGyV9LQwqPQQjMzjTLVtvkwb2Z6EmFiVtTHQyq2WKVrfRT/1/*,tprv8ZgxMBicQKsPeZ2m1aQaPA1BJ27xPphNfQQ354z77W8mRLKqwyUyonvusrZgQX3bwAQ2WFo1PPjHoAqiWnM1LMvkkmd3ZkXc5HdjxDarhYk/1/*,tprv8ZgxMBicQKsPeQ2FPA64vJ91G1Bb9kTARbusYSN9QwNmP9dF5M8xhuX8u8coWD8mq24xjwftnT8hteJ4riMYyjeSsxKMaBd1PX1NDDbxqV2/1/*,tprv8ZgxMBicQKsPe7nycwReBmFGn5HuTJbzLN7iUpDhFESMGvEZWnurvjrV4otDDEnvsrZ2a8X4o19xGXaTkEJsPUApHvMCeVTmAf2i5bBaSez/1/*,tprv8ZgxMBicQKsPdauRxSzxXTi85dQd4sSwS5sot1gFLUrJUoUGqzohDgPxTpmBjtmDfYjmNidA1hoF6b5gXh83JBdjcosm5rFeN7xUAM4DFxo/1/*,tprv8ZgxMBicQKsPfAhMFUPNJMkKVMYebxr1A1bdm8itERTuoDXXhpSQvsXjUQmrTmXsM8x5BxuQjaqF2H5tUXMXuGbiPTpzQKj2NZ6hCsUYJNX/1/*,tprv8ZgxMBicQKsPddHiYzgaoQthYpCCnnG8TQXaBfQEcoqt2xvzCVXHW7FF1n34LDLoJYghmArzW6ej7xiJpWCDn8sng4XT3uPHxc3MysiE3GS/1/*,tprv8ZgxMBicQKsPdyon5QGdU6tStoUPSJxidv8u75MWCVjCRhEzoFL2zhEHEx2ejmLExRxANbbqGc84jx3EVjWUVxYShEfDvCeMk3a2Fcqk1Qa/1/*,tprv8ZgxMBicQKsPcv2k7VmW4rKybZ5QpMUtNWdARqs8rYDoZ7tpg27njFquM2GmdXPgCKpqykwKpZ9mqBn7h7umz1sBm6avKmxcbzs1K8C6bVt/1/*,tprv8ZgxMBicQKsPea6F9YnfAPrzAQbn1Zeb5h9tp1pjnZQ9WqAds1JYhq9mFBumjBhWn3xmsJ4QmBqDGMeJQ5gPXmZrPBjX5hB8NfUgm7HvUyc/1/*,tprv8ZgxMBicQKsPf2RCn731KSorsuEjA8hwJqwub6BUBJYGpZV5Z6VQPKGEKqGJxEDtgFxeGpkU9zhjNn82SiiiaSqNXnqXofhZAgn8YirN5y2/1/*,tprv8ZgxMBicQKsPf94VtPAD9Czz4SButGX49W8PM6nxecBrWACbrULsUb9KRBo6gJs9mCQpX4q7DGCWTtkf27htQwXJGhNCDNJ3WCufeV2CE5T/1/*,tprv8ZgxMBicQKsPdoKuEXhCT2vPyojxxf1C9U75madMvMdqhQf1sET2ToeaDJRP8mzbjYjYq7DV8C233tMmBoPzubVukuNyfu8uxrUJcbdGEhP/1/*,tprv8ZgxMBicQKsPetrYKgU8APCNusa2Sq2px2TaNNJ6TKhzcBfzCbrVKArA3tXc6JYa3VZN6ose6564Far2ikD2DKguYQahVd7dSa9BAnVbRJe/1/*))"),

instagibbs commented at 8:54 am on March 24, 2021:

nit: I might suggest building this string programmatically, just re-using the same key 15 times?

in test/functional/wallet_importdescriptors.py:503 in f02ce6e17b outdated

498+        self.nodes[1].createwallet(wallet_name='multi_priv_big_legacy',
499+                                   blank=True, descriptors=True)
500+        multi_priv_big = self.nodes[1].get_wallet_rpc('multi_priv_big_legacy')
501+        res = multi_priv_big.importdescriptors([
502+        {
503+            "desc": descsum_create("sh(multi(15,tprv8ZgxMBicQKsPeAjsABad2QinheaMrvqvCkkBZwBRttYcMALE8yVG5GUsQdLmLWNFeYjUuqKiSay7z2bcvhbi1DEdYMRi5JeedkTKbTuJCda/*,tprv8ZgxMBicQKsPeJ59P23D5yq4HpFgfbqph7kYPCnMVPhNdktyAwbusJoMc9QgksGyV9LQwqPQQjMzjTLVtvkwb2Z6EmFiVtTHQyq2WKVrfRT/*,tprv8ZgxMBicQKsPeZ2m1aQaPA1BJ27xPphNfQQ354z77W8mRLKqwyUyonvusrZgQX3bwAQ2WFo1PPjHoAqiWnM1LMvkkmd3ZkXc5HdjxDarhYk/*,tprv8ZgxMBicQKsPeQ2FPA64vJ91G1Bb9kTARbusYSN9QwNmP9dF5M8xhuX8u8coWD8mq24xjwftnT8hteJ4riMYyjeSsxKMaBd1PX1NDDbxqV2/*,tprv8ZgxMBicQKsPe7nycwReBmFGn5HuTJbzLN7iUpDhFESMGvEZWnurvjrV4otDDEnvsrZ2a8X4o19xGXaTkEJsPUApHvMCeVTmAf2i5bBaSez/*,tprv8ZgxMBicQKsPdauRxSzxXTi85dQd4sSwS5sot1gFLUrJUoUGqzohDgPxTpmBjtmDfYjmNidA1hoF6b5gXh83JBdjcosm5rFeN7xUAM4DFxo/*,tprv8ZgxMBicQKsPfAhMFUPNJMkKVMYebxr1A1bdm8itERTuoDXXhpSQvsXjUQmrTmXsM8x5BxuQjaqF2H5tUXMXuGbiPTpzQKj2NZ6hCsUYJNX/*,tprv8ZgxMBicQKsPddHiYzgaoQthYpCCnnG8TQXaBfQEcoqt2xvzCVXHW7FF1n34LDLoJYghmArzW6ej7xiJpWCDn8sng4XT3uPHxc3MysiE3GS/*,tprv8ZgxMBicQKsPdyon5QGdU6tStoUPSJxidv8u75MWCVjCRhEzoFL2zhEHEx2ejmLExRxANbbqGc84jx3EVjWUVxYShEfDvCeMk3a2Fcqk1Qa/*,tprv8ZgxMBicQKsPcv2k7VmW4rKybZ5QpMUtNWdARqs8rYDoZ7tpg27njFquM2GmdXPgCKpqykwKpZ9mqBn7h7umz1sBm6avKmxcbzs1K8C6bVt/*,tprv8ZgxMBicQKsPea6F9YnfAPrzAQbn1Zeb5h9tp1pjnZQ9WqAds1JYhq9mFBumjBhWn3xmsJ4QmBqDGMeJQ5gPXmZrPBjX5hB8NfUgm7HvUyc/*,tprv8ZgxMBicQKsPf2RCn731KSorsuEjA8hwJqwub6BUBJYGpZV5Z6VQPKGEKqGJxEDtgFxeGpkU9zhjNn82SiiiaSqNXnqXofhZAgn8YirN5y2/*,tprv8ZgxMBicQKsPf94VtPAD9Czz4SButGX49W8PM6nxecBrWACbrULsUb9KRBo6gJs9mCQpX4q7DGCWTtkf27htQwXJGhNCDNJ3WCufeV2CE5T/*,tprv8ZgxMBicQKsPdoKuEXhCT2vPyojxxf1C9U75madMvMdqhQf1sET2ToeaDJRP8mzbjYjYq7DV8C233tMmBoPzubVukuNyfu8uxrUJcbdGEhP/*,tprv8ZgxMBicQKsPetrYKgU8APCNusa2Sq2px2TaNNJ6TKhzcBfzCbrVKArA3tXc6JYa3VZN6ose6564Far2ikD2DKguYQahVd7dSa9BAnVbRJe/*))"),

instagibbs commented at 8:54 am on March 24, 2021:

nit: I might suggest building this string programmatically, just re-using the same key 15 times?

in test/functional/wallet_importdescriptors.py:511 in f02ce6e17b outdated

506+            "next_index": 0,
507+            "timestamp": "now"
508+        },
509+        {
510+            "desc":
511+            descsum_create("sh(multi(15,tprv8ZgxMBicQKsPeAjsABad2QinheaMrvqvCkkBZwBRttYcMALE8yVG5GUsQdLmLWNFeYjUuqKiSay7z2bcvhbi1DEdYMRi5JeedkTKbTuJCda/1/*,tprv8ZgxMBicQKsPeJ59P23D5yq4HpFgfbqph7kYPCnMVPhNdktyAwbusJoMc9QgksGyV9LQwqPQQjMzjTLVtvkwb2Z6EmFiVtTHQyq2WKVrfRT/1/*,tprv8ZgxMBicQKsPeZ2m1aQaPA1BJ27xPphNfQQ354z77W8mRLKqwyUyonvusrZgQX3bwAQ2WFo1PPjHoAqiWnM1LMvkkmd3ZkXc5HdjxDarhYk/1/*,tprv8ZgxMBicQKsPeQ2FPA64vJ91G1Bb9kTARbusYSN9QwNmP9dF5M8xhuX8u8coWD8mq24xjwftnT8hteJ4riMYyjeSsxKMaBd1PX1NDDbxqV2/1/*,tprv8ZgxMBicQKsPe7nycwReBmFGn5HuTJbzLN7iUpDhFESMGvEZWnurvjrV4otDDEnvsrZ2a8X4o19xGXaTkEJsPUApHvMCeVTmAf2i5bBaSez/1/*,tprv8ZgxMBicQKsPdauRxSzxXTi85dQd4sSwS5sot1gFLUrJUoUGqzohDgPxTpmBjtmDfYjmNidA1hoF6b5gXh83JBdjcosm5rFeN7xUAM4DFxo/1/*,tprv8ZgxMBicQKsPfAhMFUPNJMkKVMYebxr1A1bdm8itERTuoDXXhpSQvsXjUQmrTmXsM8x5BxuQjaqF2H5tUXMXuGbiPTpzQKj2NZ6hCsUYJNX/1/*,tprv8ZgxMBicQKsPddHiYzgaoQthYpCCnnG8TQXaBfQEcoqt2xvzCVXHW7FF1n34LDLoJYghmArzW6ej7xiJpWCDn8sng4XT3uPHxc3MysiE3GS/1/*,tprv8ZgxMBicQKsPdyon5QGdU6tStoUPSJxidv8u75MWCVjCRhEzoFL2zhEHEx2ejmLExRxANbbqGc84jx3EVjWUVxYShEfDvCeMk3a2Fcqk1Qa/1/*,tprv8ZgxMBicQKsPcv2k7VmW4rKybZ5QpMUtNWdARqs8rYDoZ7tpg27njFquM2GmdXPgCKpqykwKpZ9mqBn7h7umz1sBm6avKmxcbzs1K8C6bVt/1/*,tprv8ZgxMBicQKsPea6F9YnfAPrzAQbn1Zeb5h9tp1pjnZQ9WqAds1JYhq9mFBumjBhWn3xmsJ4QmBqDGMeJQ5gPXmZrPBjX5hB8NfUgm7HvUyc/1/*,tprv8ZgxMBicQKsPf2RCn731KSorsuEjA8hwJqwub6BUBJYGpZV5Z6VQPKGEKqGJxEDtgFxeGpkU9zhjNn82SiiiaSqNXnqXofhZAgn8YirN5y2/1/*,tprv8ZgxMBicQKsPf94VtPAD9Czz4SButGX49W8PM6nxecBrWACbrULsUb9KRBo6gJs9mCQpX4q7DGCWTtkf27htQwXJGhNCDNJ3WCufeV2CE5T/1/*,tprv8ZgxMBicQKsPdoKuEXhCT2vPyojxxf1C9U75madMvMdqhQf1sET2ToeaDJRP8mzbjYjYq7DV8C233tMmBoPzubVukuNyfu8uxrUJcbdGEhP/1/*,tprv8ZgxMBicQKsPetrYKgU8APCNusa2Sq2px2TaNNJ6TKhzcBfzCbrVKArA3tXc6JYa3VZN6ose6564Far2ikD2DKguYQahVd7dSa9BAnVbRJe/1/*))"),

instagibbs commented at 8:54 am on March 24, 2021:

nit: I might suggest building this string programmatically, just re-using the same key 15 times?

instagibbs commented at 8:56 am on March 24, 2021: member

Looks good, dropping some comments for now

darosior force-pushed on Mar 24, 2021

darosior commented at 12:31 pm on March 24, 2021: member

Addressed @instagibbs ’s comments.

in test/functional/wallet_importdescriptors.py:469 in 6bf498b944 outdated

464+        wmulti_priv_big = self.nodes[1].get_wallet_rpc('wmulti_priv_big')
465+        xkey = "tprv8ZgxMBicQKsPeZSeYx7VXDDTs3XrTcmZQpRLbAeSQFCQGgKwR4gKpcxHaKdoTNHniv4EPDJNdzA3KxRrrBHcAgth8fU5X4oCndkkxk39iAt/*"
466+        xkey_int = "tprv8ZgxMBicQKsPeZSeYx7VXDDTs3XrTcmZQpRLbAeSQFCQGgKwR4gKpcxHaKdoTNHniv4EPDJNdzA3KxRrrBHcAgth8fU5X4oCndkkxk39iAt/1/*"
467+        res = wmulti_priv_big.importdescriptors([
468+        {
469+            "desc": descsum_create(f"wsh(sortedmulti(20,{(xkey + ',') * 19}{xkey}))"),

instagibbs commented at 6:26 am on March 25, 2021:

phew

instagibbs approved

instagibbs commented at 6:27 am on March 25, 2021: member

utACK https://github.com/bitcoin/bitcoin/pull/20867/commits/1336830a04d3e4128624da33de5db658af60596d

fanquake requested review from achow101 on Apr 24, 2021

in src/script/standard.cpp:111 in be65a0214d outdated

107+    }
108+
109+    if (IsPushdataOp(opcode)) {
110+        try {
111+            count = CScriptNum(data, /* fRequireMinimal = */ true).getint();
112+            // Not minimally encoded count.

meshcollider commented at 4:49 am on April 27, 2021:

There is a function called CheckMinimalPush() which is a more complete check, I think you could use that here

darosior commented at 1:40 pm on April 27, 2021:

Thanks, done:

 0diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
 1index abc0625bb..7e119bb3c 100644
 2--- a/src/script/interpreter.cpp
 3+++ b/src/script/interpreter.cpp
 4@@ -225,7 +225,7 @@ bool static CheckPubKeyEncoding(const valtype &vchPubKey, unsigned int flags, co
 5     return true;
 6 }
 7 
 8-bool static CheckMinimalPush(const valtype& data, opcodetype opcode) {
 9+bool CheckMinimalPush(const valtype& data, opcodetype opcode) {
10     // Excludes OP_1NEGATE, OP_1-16 since they are by definition minimal
11     assert(0 <= opcode && opcode <= OP_PUSHDATA4);
12     if (data.size() == 0) {
13diff --git a/src/script/interpreter.h b/src/script/interpreter.h
14index c76b3acb2..212de17c7 100644
15--- a/src/script/interpreter.h
16+++ b/src/script/interpreter.h
17@@ -316,6 +316,8 @@ bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const C
18 
19 size_t CountWitnessSigOps(const CScript& scriptSig, const CScript& scriptPubKey, const CScriptWitness* witness, unsigned int flags);
20 
21+bool CheckMinimalPush(const std::vector<unsigned char>& data, opcodetype opcode);
22+
23 int FindAndDelete(CScript& script, const CScript& b);
24 
25 #endif // BITCOIN_SCRIPT_INTERPRETER_H
26diff --git a/src/script/standard.cpp b/src/script/standard.cpp
27index 1cc15bf9b..880bd49f8 100644
28--- a/src/script/standard.cpp
29+++ b/src/script/standard.cpp
30@@ -106,10 +106,9 @@ static bool GetMultisigKeyCount(opcodetype opcode, valtype data, int& count)
31     }
32 
33     if (IsPushdataOp(opcode)) {
34+        if (!CheckMinimalPush(data, opcode)) return false;
35         try {
36             count = CScriptNum(data, /* fRequireMinimal = */ true).getint();
37-            // Not minimally encoded count.
38-            if (count <= 16) return false;
39             return IsValidMultisigKeyCount(count);
40         } catch (const scriptnum_error&) {
41             return false;

meshcollider commented at 5:04 am on April 27, 2021: contributor

Concept ACK.

Typo in commit message test/functional: standarness sanity checks for P2(W)SH multisig

I think you should add a test that P2SH multisig is still non-standard with more than 16 sigs.

darosior force-pushed on Apr 27, 2021

darosior commented at 1:41 pm on April 27, 2021: member

I think you should add a test that P2SH multisig is still non-standard with more than 16 sigs.

There is one already, line 263 of descriptor_tests.cpp

darosior force-pushed on Apr 27, 2021

script: match multisigs with up to MAX_PUBKEYS_PER_MULTISIG keys

We were previously ruling out 17-20 pubkeys multisig, while they are
only invalid under P2SH context.
This makes multisigs with up to 20 keys be detected as valid by the
solver. This is however *not* a policy change as it would only apply
to bare multisigs, which are already limited to 3 pubkeys.

Note that this does not change the sigOpCount calculation (as it would
break consensus). Therefore 1-16 keys multisigs are counted as 1-16 sigops
and 17-20 keys multisigs are counted as 20 sigops.

Signed-off-by: Antoine Poinsot <darosior@protonmail.com>

9fc68faf35

script: allow up to 20 keys in wsh() descriptors

Signed-off-by: Antoine Poinsot <darosior@protonmail.com>

ae0429d3af

test/functional: standardness sanity checks for P2(W)SH multisig

Note that it also test for sortedmulti(), which the previous commit didn't.

Signed-off-by: Antoine Poinsot <darosior@protonmail.com>

063df9e897

rpc/util: multisig: only check redeemScript size is <= 520 for P2SH

This increase the maximum number of pubkeys to 20 (valid in P2WSH and
P2SH-P2WSH) and only checks the redeemScript doesn't exceed
MAX_SCRIPT_ELEMENT_SIZE for P2SH, as this checked is removed under
Segwit context.

Signed-off-by: Antoine Poinsot <darosior@protonmail.com>

5aa50ab9cc

doc: add release notes for 20867

Signed-off-by: Antoine Poinsot <darosior@protonmail.com>

ebd4be43cc

darosior force-pushed on Apr 28, 2021

meshcollider commented at 5:24 am on April 30, 2021: contributor

re-utACK ebd4be43cc945e643f91d3a91007b5a35bbbd5a1

MarcoFalke requested review from instagibbs on Apr 30, 2021

in src/script/standard.cpp:111 in ebd4be43cc

107+    }
108+
109+    if (IsPushdataOp(opcode)) {
110+        if (!CheckMinimalPush(data, opcode)) return false;
111+        try {
112+            count = CScriptNum(data, /* fRequireMinimal = */ true).getint();

instagibbs commented at 2:19 am on May 3, 2021:

just noting the minimal encoding requirement is no longer necessary here due to new check above

instagibbs approved

instagibbs commented at 2:20 am on May 3, 2021: member

re-ACK https://github.com/bitcoin/bitcoin/pull/20867/commits/ebd4be43cc945e643f91d3a91007b5a35bbbd5a1

fanquake merged this on May 3, 2021

fanquake closed this on May 3, 2021

sidhujag referenced this in commit 18b80ef3c1 on May 3, 2021

darosior deleted the branch on Jun 18, 2021

gwillen referenced this in commit fb60da4597 on Jun 1, 2022

DrahtBot locked this on Aug 18, 2022

Support up to 20 keys for multisig under Segwit context #20867

Conflicts