Fix CHECKMULTISIG mutability and remove P2SH CHECKMULTISIG # of signatures limit

petertodd commented at 5:55 am on March 11, 2014: contributor

tl;dr: CHECKMULTISIG has a bug that causes it to consume an extra dummy argument on the stack. While normally OP_0 is used, the actual value of this argument is not checked, and thus creates a source of mutability for any transaction with CHECKMULTISIG inputs.

So to fix this we do a few things:

Introduce the notion of mandatory and standard script verification flags. The former is what all new blocks must adhere to - currently just P2SH - while the latter are soft restrictions that may later become mandatory in a soft-fork such as signature encoding checks. (the canonical PUSHDATA checks should become a verification flag as well in a future pull-req)
Modify tx_(in)valid unit tests to allow verification flags to be specified by name rather than only P2SH. (again, tests of the STRICTENC flags should be added in a future pull-req)
Add the SCRIPT_VERIFY_NULLDUMMY flag and corresponding code to EvalScript() to verify that the dummy argument is in fact null. Rational: checking this as a IsStandard() test would be awkward, and a future soft-fork should make this mandatory anyway. I also added more unittests, including an explicit check to tx_invalid.json that a lack of a dummy argument does fail the transaction. Tested that blocks breaking this rule are accepted, including a testnet and mainnet reindex.
Generalize the SCRIPTENC DoS-ban exemption to all non-mandatory SCRIPT_VERIFY flags so that we don’t split the network. Note the minor logic error we fixed: previously an invalid P2SH transaction with the inner script failing was classified as REJECT_NONSTANDARD with the message “non-canonical”; a future pull-req can make the new messages more useful if EvalScript() is modified to return rejection strings or similar. (or god forbid, something like the scary-complex exception based scheme in my python-bitcoinlib that’ll surely add a consensus bug) Tested by injecting non-compliant transactions elsewhere on the network and observing debug.log

With the dummy argument checked, we can remove the weird arbitrary limits on the # of signatures by upping the allowed scriptSig size, letting advanced escrow/oracle/etc. applications do as they wish within the 15 pubkey/520 byte redeemScript limit with P2SH. (see https://github.com/bitcoin/bips/pull/24) With the dummy value forced to always be null, the “stuff data in the chain” situation remains essentially unchanged as all the extra scriptSig space can only be used for signatures; the non-P2SH limit is kept as-is and remains <= 3 pubkeys.

Finally, now is a good time to teach addmultisigaddress/createmultisig/the wallet to raise an error on >520 byte redeemScripts.

petertodd commented at 6:40 am on March 11, 2014: contributor

Interesting, bitcoinj is producing CHECKMULTISIG transactions that violate this rule. Fixed by @schildbach in https://github.com/schildbach/bitcoinj/commit/e3d97759d5692791821e8f1ee71856a9e8231dd7 (pull-req, not yet merged)

bitcoinjs-lib does get it right however, which covers almost all real-world use of CHECKMULTISIG right now. (e.g. bitgo and bitrated) EDIT: litbitcoin gets it right too, which covers sx.

sipa commented at 3:32 pm on March 11, 2014: member

ACK.

I started working on some similar extra flags to implement my proposed version3 transaction/blocks, but didn’t get to extend the unit tests as you did, so preferring this code goes in first.

This pull-request does contain a bunch of only moderately-related commits though, so perhaps others prefer seeing it split up. I’m personally fine with all.

I’m not sure a separation into standard/mandatory will suffice in the future. Some flags may be mandatory in some context (nVersion=3 blocks) while not even being required in others. We’ll see as we go, I guess.

sipa commented at 3:47 pm on March 11, 2014: member

Verifying some math:

I think you can only fit a n-of-14 checkmultisig in a 510-byte redeem script IMHO. It requires an OP_(nRequired) + nKeys*(push of 33 bytes) + OP_(nKeys) + OP_CHECKMULTISIG. For nKeys=15, this requires 513 bytes.

So nKeys is at most 14, and the maximum standard redeemscript is 479 bytes.

The size limit on scriptSig can be made a bit more strict as well.

Since the even-s signature creation rule, signatures are never more than 72 bytes, so 14*(72+1) + 479+1 = 1502 bytes can be the scriptSig limit (instead of 1721). This is also enough for spending a 20-of-20 multisig, by the way.

sipa commented at 3:49 pm on March 11, 2014: member

Ugh. The limit is 520 bytes, not 510.

This means nKeys can indeed be 15, and the maximum redeemscript is 513 bytes.

The maximum scriptSig then becomes 15*(72+1) + 513+1 = 1609.

gmaxwell commented at 5:08 pm on March 11, 2014: contributor

@petertodd was that reindex with checkpoints=0 ? I’d also suggest adding to your testplan a quick test of the test by turning on the rule like a blockchain rule and making sure it rejects the chain.

petertodd commented at 8:24 pm on March 12, 2014: contributor

@gmaxwell Good point; checkpoints=0 does pass. I also did a testnet reindex with the test forced on, and as expected it fails at height 180683 due to tx 013b1d2d37f77ec0b6861b396d594ace1d6bbff97d1cc64e401c396e89ba0462. @sipa I lowered the limit to a rounded off 1650 bytes and updated the comment to be clear it wasn’t the absolute lower-limit. I agree re: nVersion=3, and actually was going to suggest we think about whether or not treating that as a transaction-level flag and/or passing the transaction nVersion into EvalScript made sense, but that’s a discussion for elsewhere. Mandatory/standard at least gives us a starting point for those more complex changes.

petertodd commented at 10:08 pm on March 18, 2014: contributor

I’ve been running a node for about a week now with this patch applied. No issues seen, and on top of that other than some of my own test transactions I haven’t seen any CHECKMULTISIG usage that would be blocked by this patch; looks like all the implementations actually out there getting used are compliant.

CodeShark commented at 3:11 am on March 31, 2014: contributor

Looks good. Haven’t throughly tested it, but I am running a node and it seems to work fine.

This is a much desired fix.

laanwj added this to the milestone 0.10.0 on Apr 11, 2014

CodeShark commented at 6:07 am on May 4, 2014: contributor

I’ve been running this patch for several weeks now and haven’t run into any issues - any chance of this getting merged soon?

petertodd commented at 5:05 am on May 5, 2014: contributor

Lemme know if this needs a rebase; pull-reqs #3860 and #3861 depend on it as well.

in src/main.cpp: in b3eb5a208e outdated

1576@@ -1573,14 +1577,30 @@ bool CheckInputs(const CTransaction& tx, CValidationState &state, CCoinsViewCach
1577                     pvChecks->push_back(CScriptCheck());
1578                     check.swap(pvChecks->back());
1579                 } else if (!check()) {
1580-                    if (flags & SCRIPT_VERIFY_STRICTENC) {
1581-                        // For now, check whether the failure was caused by non-canonical
1582-                        // encodings or not; if so, don't trigger DoS protection.
1583-                        CScriptCheck check(coins, tx, i, flags & (~SCRIPT_VERIFY_STRICTENC), 0);
1584+                    if (flags & (STANDARD_SCRIPT_VERIFY_FLAGS & ~MANDATORY_SCRIPT_VERIFY_FLAGS)) {

laanwj commented at 7:04 am on May 5, 2014:

Maybe define a constant STANDARD_NOT_MANDATORY_VERIFY_FLAGS that’s (STANDARD_SCRIPT_VERIFY_FLAGS & ~MANDATORY_SCRIPT_VERIFY_FLAGS) instead of doing the bit twiddling here inline, twice.

in src/test/transaction_tests.cpp: in b3eb5a208e outdated

39+        mapFlagNames["EVEN_S"] = SCRIPT_VERIFY_EVEN_S;
40+        mapFlagNames["NULLDUMMY"] = SCRIPT_VERIFY_NULLDUMMY;
41+    }
42+
43+    BOOST_FOREACH(string word, words)
44+        flags |= mapFlagNames[word];

laanwj commented at 7:07 am on May 5, 2014:

I’d make this parsing a bit more strict: fail if the word is not in mapFlagNames instead of treating it as 0. This avoids tests testing something else than you think due to a typo.

petertodd commented at 10:02 am on May 5, 2014:

Oh! I didn’t realize C++ modified a map if you used [] on a unknown key, weird.

laanwj commented at 10:05 am on May 5, 2014:

It’s really a pitfall. To paraphrase the horse_unix twitter account: “the definition of operator[] is extremely simple: m[k] is equivalent to (*((m.insert(value_type(k, data_type()))).first)).second.”

I wouldn’t be surprised if Bitcoin Core itself also had a minor bug or two due to strangeness with [. In general using the explicit .find() results in more clear (though also more verbose…) code.

in src/keystore.cpp: in b3eb5a208e outdated

32@@ -33,6 +33,9 @@ bool CBasicKeyStore::AddKeyPubKey(const CKey& key, const CPubKey &pubkey)
33 
34 bool CBasicKeyStore::AddCScript(const CScript& redeemScript)
35 {
36+    if (redeemScript.size() > MAX_SCRIPT_ELEMENT_SIZE)
37+        return error("CBasicKeyStore::AddCScript() : redeemScripts > 520 bytes are invalid");

laanwj commented at 7:09 am on May 5, 2014:

Maybe

0return error("CBasicKeyStore::AddCScript() : redeemScripts > %i bytes are invalid", MAX_SCRIPT_ELEMENT_SIZE);

laanwj commented at 7:25 am on May 5, 2014: member

Looks good to me, ACK apart from above minor nits

Create (MANDATORY|STANDARD)_SCRIPT_VERIFY_FLAGS constants 68f7d1d7af

Let tx (in)valid tests use any SCRIPT_VERIFY flag

Previously only P2SH could be set.

29c17498a5

petertodd commented at 10:07 am on May 5, 2014: contributor

@laanwj Fixed all minor nits.

laanwj commented at 10:09 am on May 5, 2014: member

@gavinandresen can you have a final look at this before merging?

gavinandresen commented at 12:58 pm on May 5, 2014: contributor

Code-reviewed, but untested, ACK.

Add rejection of non-null CHECKMULTISIG dummy values

This is a source of transaction mutability as the dummy value was
previously not checked and could be modified to something other than the
usual OP_0 value.

6380180821

Do not trigger a DoS ban if SCRIPT_VERIFY_NULLDUMMY fails f80cffa213

Increase IsStandard() scriptSig length

Removes the limits on number of pubkeys for P2SH CHECKMULTISIG outputs.
Previously with the 500 byte scriptSig limit there were odd restrictions
where even a 1-of-12 P2SH could be spent in a standard transaction(1),
yet multisig scriptPubKey's requiring more signatures quickly ran out of
scriptSig space.

From a "stuff-data-in-the-blockchain" point of view not much has changed
as with the prior commit now only allowing the dummy value to be null
the newly allowed scriptSig space can only be used for signatures. In
any case, just using more outputs is trivial and doesn't cost much.

1) See 779b519480d8c5346de6e635119c7ee772e97ec872240c45e558f582a37b4b73
   Mined by BTC Guild.

4d79098ad5

Check redeemScript size does not exceed 520 byte limit

redeemScripts >520bytes can't be spent due to the
MAX_SCRIPT_ELEMENT_SIZE limit; previously the addmultisigaddress and
createmultisig RPC calls would let you violate that limit unknowingly.

Also made the wallet code itself check the redeemScript prior to adding
it to the wallet, which in the (rare) instance that a user has added an
invalid oversized redeemScript to their wallet causes an error on
startup. The affected key isn't added to the wallet; other keys are
unaffected.

787ee0c913

petertodd commented at 5:12 am on May 8, 2014: contributor

@sipa Fixed that comment and added a test for stack size prior to stacktop().

BitcoinPullTester commented at 5:37 am on May 8, 2014: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/787ee0c91394b0ae16ca2500dbacf9349e65b6bc for binaries and test log. This test script verifies pulls every time they are updated. It, however, dies sometimes and fails to test properly. If you are waiting on a test, please check timestamps to verify that the test.log is moving at http://jenkins.bluematt.me/pull-tester/current/ Contact BlueMatt on freenode if something looks broken.

laanwj merged this on May 9, 2014

laanwj closed this on May 9, 2014

laanwj referenced this in commit 54f102248b on May 9, 2014

fanquake referenced this in commit cffbf1eb9a on May 27, 2020

sidhujag referenced this in commit bf5ca922fd on May 27, 2020

PastaPastaPasta referenced this in commit eb91540645 on Jun 27, 2021

PastaPastaPasta referenced this in commit aaa99155ea on Jun 28, 2021

PastaPastaPasta referenced this in commit 7e867e95e1 on Jun 29, 2021

PastaPastaPasta referenced this in commit e1dc813f55 on Jul 1, 2021

PastaPastaPasta referenced this in commit c333a6fc91 on Jul 1, 2021

PastaPastaPasta referenced this in commit f3f00f446e on Jul 14, 2021

PastaPastaPasta referenced this in commit 7ac32ac79f on Jul 15, 2021

DrahtBot locked this on Sep 8, 2021

Fix CHECKMULTISIG mutability and remove P2SH CHECKMULTISIG # of signatures limit #3843