Optimize OP_CHECKMULTISIG signature hashing #2275

gavinandresen commented at 2:47 PM on February 5, 2013: contributor

Three commits: a straight refactor, a new unit test, then an optimization.

This makes OP_CHECKMULTISIG more efficient, only recomputing the transaction signature hash once-per-different-SIGHASH-used-by-its-signatures.

Insignificant for small transactions, but could be as much as a 2x speedup for very large transactions spending 1-of-3 multisig inputs.

Thanks to Sergio Demian Lerner for warning that an attacker might try to mount a CPU exhaustion attack using OP_CHECKMULTISIG.

This fix is low priority (post-0.8.0) because transaction fees are high enough to make a CPU exhaustion attack based on this economically irrational.

BitcoinPullTester commented at 4:34 PM on February 5, 2013: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/c78a5175be9fd9a9af6a778713054ca3a999f4d2 for binaries and test log.

gavinandresen commented at 11:32 PM on February 12, 2013: contributor

@SergioDemianLerner : RE: nSigHT & 0x83 : good idea.

RE: why not extend to OP_CHECKSIG: the cache only exists during the execution of a single OP_CHECKSIG, because standard transaction types only contain either a single OP_CHECKSIG or an OP_CHECKMULTISIG in each scriptPubKey.

If we ever have lots of transaction scriptPubKeys with multiple OP_*SIGs, then it would make sense to extend the cache to any signature operation.

Note that this is not intended to help with attackers who might create blocks full of non-standard transactions; I believe that is expensive enough (attacker has to be willing to create blocks that are very likely to be orphaned) that it isn't a problem.

Refactor CheckSig (prep for OP_CHECKMULTISIG optimization) 451cf680a9

Unit test: OP_CHECKMULTISIG multiple signatures with different hash types 3f916d018f

OP_CHECKMULTISIG signature hash optimization

Rework OP_CHECKMULTISIG so each OP_CHECKMULTISIG only
hashes the transaction once for each different SIGHASH_ type.

61a29a7c06

in src/script.cpp:None in c78a5175be outdated

1063 | @@ -1061,16 +1064,29 @@ bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, co
1064 |                          scriptCode.FindAndDelete(CScript(vchSig));
1065 |                      }
1066 |  
1067 | +                    // Avoid repeatedly recomputing signature hashes
1068 | +                    map<int, uint256> mapSigHashCache;

sipa commented at 6:29 PM on April 7, 2013:

Why not a single mapSigHashCache for the whole EvalScript evaluation?

gavinandresen commented at 2:42 PM on April 8, 2013:

Why not indeed.... I'll change it.

gavinandresen commented at 11:50 PM on April 8, 2013: contributor

Implemented @sipa and @SergioDemianLerner suggestions, and rebased to master so pull-tester is happy.

BitcoinPullTester commented at 12:35 AM on April 9, 2013: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/61a29a7c0676eb0d422ff828f0ba006ba0fc8e2e 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.

sipa commented at 4:29 PM on April 14, 2013: member

@gavinandresen Sorry, this was a dangerous suggestion of mine: the sighash depends on the position of the CHECKSIG in the script, when there are OP_CODESEPARATORs present. You should probably index the map by pbegincodehash as well.

gavinandresen commented at 12:43 AM on April 15, 2013: contributor

Bah. OP_CODESEPARATOR is evil and should be abolished.

This optimization isn't high on my list of things to fix, and before pulling we should create some tricky OP_CODESEPARATOR unit tests, so if anybody else is motivated, feel free to do that (I'm buy with payment protocol stuff).

SergioDemianLerner commented at 7:01 PM on April 15, 2013: contributor

First, good to know Sipa catched the problem before it was too late. Excellent job!

I've been pushing to remove OP_CODESEPARATOR and adopt a simpler verification system with a hard-fork in many forum posts, showing strange uses of it.

It's clear than it can make enormous damage and makes no good at all. We've experienced that programmed hard-forks can be carried out without much danger. I Suggested putting a single "*" in the script to be verified and ban OP_CODESEPARATOR for ever.

sipa commented at 8:30 PM on April 15, 2013: member

@SergioDemianLerner I'm in favor of removing OP_CODESEPARATOR, but I think you mean a soft fork. As far as I know, there has never ever been a hard fork in Bitcoin's history (but we'll do one in 1 month...). Also, there's no need for one here. Simpy turn OP_CODESEPARATOR into a 'return false' - no need to add new semantics.

What do you mean by putting a "*" in the script?

SergioDemianLerner commented at 7:46 PM on April 16, 2013: contributor

Nothing really important, any opcode could be used. Just a way to mark which script is the one being signed. The idea is not to insert parts of the script of the previous output in the scriptsig for verification. Currently to explain to a new user how a transaction input is verified we need 200 words. It could be simplified to "insert * in the scriptsig, clear all other scriptsigs and hash" (well, sort of).

sipa commented at 7:50 PM on April 16, 2013: member

If we're going to do an actual hard fork for the script language, give me a few days and I can come up with tons of small fixes. If we're not scared of redoing the scripting language from scratch (I am, however), I think we can come up with something vastly better (except for being tested).

However, removing the atrocity that is OP_CODESEPARATOR is as easy as replacing it with "return false;", and can be done with a simple soft fork like we've done several times already now.

SergioDemianLerner commented at 7:52 PM on April 16, 2013: contributor

If ever the signature verification procedure is changed, I would simplify it more: Let T0 be the original transaction. T1 = T0 with all scriptsigs cleared. Let X = SHA-256 ( SHA-256 ( T1 ) ) Then HashTransaction(T) = SHA-256 ( X || n )) ) Where n is the input number to be verified. Then X could be cached and computed only once for the whole transaction (here I'm not taking into account the SIG_ flags)

But this is only a dream. I doubt the the signature verification system would ever be changed.

gavinandresen closed this on Jun 4, 2013

gavinandresen deleted the branch on Nov 4, 2013

DrahtBot locked this on Sep 8, 2021