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>

3 files changed, 42 insertions, 8 deletions

diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
index abc0625bb1..7e119bb3c4 100644
--- a/src/script/interpreter.cpp
+++ b/src/script/interpreter.cpp
@@ -225,7 +225,7 @@ bool static CheckPubKeyEncoding(const valtype &vchPubKey, unsigned int flags, co
     return true;
 }
 
-bool static CheckMinimalPush(const valtype& data, opcodetype opcode) {
+bool CheckMinimalPush(const valtype& data, opcodetype opcode) {
     // Excludes OP_1NEGATE, OP_1-16 since they are by definition minimal
     assert(0 <= opcode && opcode <= OP_PUSHDATA4);
     if (data.size() == 0) {
diff --git a/src/script/interpreter.h b/src/script/interpreter.h
index c76b3acb22..212de17c7b 100644
--- a/src/script/interpreter.h
+++ b/src/script/interpreter.h
@@ -316,6 +316,8 @@ bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const C
 
 size_t CountWitnessSigOps(const CScript& scriptSig, const CScript& scriptPubKey, const CScriptWitness* witness, unsigned int flags);
 
+bool CheckMinimalPush(const std::vector<unsigned char>& data, opcodetype opcode);
+
 int FindAndDelete(CScript& script, const CScript& b);
 
 #endif // BITCOIN_SCRIPT_INTERPRETER_H
diff --git a/src/script/standard.cpp b/src/script/standard.cpp
index 700155c8d4..e6f99f3034 100644
--- a/src/script/standard.cpp
+++ b/src/script/standard.cpp
@@ -88,21 +88,53 @@ static constexpr bool IsSmallInteger(opcodetype opcode)
     return opcode >= OP_1 && opcode <= OP_16;
 }
 
-static bool MatchMultisig(const CScript& script, unsigned int& required, std::vector<valtype>& pubkeys)
+static constexpr bool IsPushdataOp(opcodetype opcode)
+{
+    return opcode > OP_FALSE && opcode <= OP_PUSHDATA4;
+}
+
+static constexpr bool IsValidMultisigKeyCount(int n_keys)
+{
+    return n_keys > 0 && n_keys <= MAX_PUBKEYS_PER_MULTISIG;
+}
+
+static bool GetMultisigKeyCount(opcodetype opcode, valtype data, int& count)
+{
+    if (IsSmallInteger(opcode)) {
+        count = CScript::DecodeOP_N(opcode);
+        return IsValidMultisigKeyCount(count);
+    }
+
+    if (IsPushdataOp(opcode)) {
+        if (!CheckMinimalPush(data, opcode)) return false;
+        try {
+            count = CScriptNum(data, /* fRequireMinimal = */ true).getint();
+            return IsValidMultisigKeyCount(count);
+        } catch (const scriptnum_error&) {
+            return false;
+        }
+    }
+
+    return false;
+}
+
+static bool MatchMultisig(const CScript& script, int& required_sigs, std::vector<valtype>& pubkeys)
 {
     opcodetype opcode;
     valtype data;
+    int num_keys;
+
     CScript::const_iterator it = script.begin();
     if (script.size() < 1 || script.back() != OP_CHECKMULTISIG) return false;
 
-    if (!script.GetOp(it, opcode, data) || !IsSmallInteger(opcode)) return false;
-    required = CScript::DecodeOP_N(opcode);
+    if (!script.GetOp(it, opcode, data) || !GetMultisigKeyCount(opcode, data, required_sigs)) return false;
     while (script.GetOp(it, opcode, data) && CPubKey::ValidSize(data)) {
         pubkeys.emplace_back(std::move(data));
     }
-    if (!IsSmallInteger(opcode)) return false;
-    unsigned int keys = CScript::DecodeOP_N(opcode);
-    if (pubkeys.size() != keys || keys < required) return false;
+    if (!GetMultisigKeyCount(opcode, data, num_keys)) return false;
+
+    if (pubkeys.size() != static_cast<unsigned long>(num_keys) || num_keys < required_sigs) return false;
+
     return (it + 1 == script.end());
 }
 
@@ -163,7 +195,7 @@ TxoutType Solver(const CScript& scriptPubKey, std::vector<std::vector<unsigned c
         return TxoutType::PUBKEYHASH;
     }
 
-    unsigned int required;
+    int required;
     std::vector<std::vector<unsigned char>> keys;
     if (MatchMultisig(scriptPubKey, required, keys)) {
         vSolutionsRet.push_back({static_cast<unsigned char>(required)}); // safe as required is in range 1..16