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

petertodd · 2014-03-11T05:55:53Z

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 bitcoin/bips#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 · 2014-03-11T06:40:28Z

Interesting, bitcoinj is producing CHECKMULTISIG transactions that violate this rule. Fixed by @schildbach in schildbach/bitcoinj@e3d9775 (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 · 2014-03-11T15:32:05Z

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 · 2014-03-11T15:47:29Z

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 · 2014-03-11T15:49:24Z

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 · 2014-03-11T17:08:21Z

@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 · 2014-03-12T20:24:21Z

@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 · 2014-03-18T22:08:53Z

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 · 2014-03-31T03:11:48Z

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.

CodeShark · 2014-05-04T06:07:09Z

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 · 2014-05-05T05:05:44Z

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

laanwj · 2014-05-05T07:04:05Z

src/main.cpp

-                        // For now, check whether the failure was caused by non-canonical
-                        // encodings or not; if so, don't trigger DoS protection.
-                        CScriptCheck check(coins, tx, i, flags & (~SCRIPT_VERIFY_STRICTENC), 0);
+                    if (flags & (STANDARD_SCRIPT_VERIFY_FLAGS & ~MANDATORY_SCRIPT_VERIFY_FLAGS)) {


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.

laanwj · 2014-05-05T07:25:24Z

Looks good to me, ACK apart from above minor nits

Previously only P2SH could be set.

petertodd · 2014-05-05T10:07:17Z

@laanwj Fixed all minor nits.

laanwj · 2014-05-05T10:09:14Z

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

gavinandresen · 2014-05-05T12:58:59Z

Code-reviewed, but untested, ACK.

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.

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.

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.

petertodd · 2014-05-08T05:12:53Z

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

BitcoinPullTester · 2014-05-08T05:37:05Z

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.

787ee0c Check redeemScript size does not exceed 520 byte limit (Peter Todd) 4d79098 Increase IsStandard() scriptSig length (Peter Todd) f80cffa Do not trigger a DoS ban if SCRIPT_VERIFY_NULLDUMMY fails (Peter Todd) 6380180 Add rejection of non-null CHECKMULTISIG dummy values (Peter Todd) 29c1749 Let tx (in)valid tests use any SCRIPT_VERIFY flag (Peter Todd) 68f7d1d Create (MANDATORY|STANDARD)_SCRIPT_VERIFY_FLAGS constants (Peter Todd)

4c82579 Remove outdated comment about DER encoding (Elichai Turkel) Pull request description: This comment got me confused about the status of BIP66 (Thanks jnewbery for explaining) The comment was added in: #3843 But in #5713 strict DER encoding was enforced in consensus, and is now it's buried and enforced by the height of the block here: https://github.com/bitcoin/bitcoin/blob/4af01b37d40246cd1fdb54719855927e36a36b46/src/validation.cpp#L1889 P.S. This is also quite confusing: https://github.com/bitcoin/bitcoin/blob/4af01b37d40246cd1fdb54719855927e36a36b46/src/validation.cpp#L1560-L1563 But seems to be intentional: https://github.com/bitcoin/bitcoin/blob/4af01b37d40246cd1fdb54719855927e36a36b46/src/validation.cpp#L1510-L1511 ACKs for top commit: laanwj: ACK 4c82579 Tree-SHA512: 7afbbae84ed4ecfaa0a273ae024b14f2b7ffe65307f078086fe0b5b645c57722bc2952fb15d167d9e4fa5b052d1d0ac6e5e33f57e8fc881c0ea611d352bccc1e

4c82579 Remove outdated comment about DER encoding (Elichai Turkel) Pull request description: This comment got me confused about the status of BIP66 (Thanks jnewbery for explaining) The comment was added in: bitcoin#3843 But in bitcoin#5713 strict DER encoding was enforced in consensus, and is now it's buried and enforced by the height of the block here: https://github.com/bitcoin/bitcoin/blob/4af01b37d40246cd1fdb54719855927e36a36b46/src/validation.cpp#L1889 P.S. This is also quite confusing: https://github.com/bitcoin/bitcoin/blob/4af01b37d40246cd1fdb54719855927e36a36b46/src/validation.cpp#L1560-L1563 But seems to be intentional: https://github.com/bitcoin/bitcoin/blob/4af01b37d40246cd1fdb54719855927e36a36b46/src/validation.cpp#L1510-L1511 ACKs for top commit: laanwj: ACK 4c82579 Tree-SHA512: 7afbbae84ed4ecfaa0a273ae024b14f2b7ffe65307f078086fe0b5b645c57722bc2952fb15d167d9e4fa5b052d1d0ac6e5e33f57e8fc881c0ea611d352bccc1e

petertodd mentioned this pull request Mar 13, 2014

Test OP_CODESEPARATOR and FindAndDelete() #3861

Merged

laanwj added this to the 0.10.0 milestone Apr 11, 2014

laanwj reviewed May 5, 2014
View reviewed changes

petertodd added 2 commits May 5, 2014 05:35

Create (MANDATORY|STANDARD)_SCRIPT_VERIFY_FLAGS constants

68f7d1d

Let tx (in)valid tests use any SCRIPT_VERIFY flag

29c1749

Previously only P2SH could be set.

petertodd added 4 commits May 8, 2014 00:55

Add rejection of non-null CHECKMULTISIG dummy values

6380180

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.

Do not trigger a DoS ban if SCRIPT_VERIFY_NULLDUMMY fails

f80cffa

laanwj merged commit 787ee0c into bitcoin:master May 9, 2014

sum01 mentioned this pull request Oct 7, 2017

Possibly revisit workaround(s) openvcash/vcash#30

Open

elichai mentioned this pull request May 26, 2020

Remove outdated comment about DER encoding #19073

Merged

bitcoin locked as resolved and limited conversation to collaborators Sep 8, 2021

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

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

Uh oh!

Conversation

petertodd commented Mar 11, 2014

Uh oh!

petertodd commented Mar 11, 2014

Uh oh!

sipa commented Mar 11, 2014

Uh oh!

sipa commented Mar 11, 2014

Uh oh!

sipa commented Mar 11, 2014

Uh oh!

gmaxwell commented Mar 11, 2014

Uh oh!

petertodd commented Mar 12, 2014

Uh oh!

petertodd commented Mar 18, 2014

Uh oh!

CodeShark commented Mar 31, 2014

Uh oh!

CodeShark commented May 4, 2014

Uh oh!

petertodd commented May 5, 2014

Uh oh!

laanwj May 5, 2014

Choose a reason for hiding this comment

Uh oh!

laanwj commented May 5, 2014

Uh oh!

petertodd commented May 5, 2014

Uh oh!

laanwj commented May 5, 2014

Uh oh!

gavinandresen commented May 5, 2014

Uh oh!

petertodd commented May 8, 2014

Uh oh!

BitcoinPullTester commented May 8, 2014

Uh oh!

Uh oh!