[WIP] Reuse sighash computations across evaluation

jl2012 commented at 3:44 pm on September 2, 2016: contributor

The effect of doing this would not be very obvious in normal use, but could have >10x improvement for a O(n^2) hashing attack

in src/script/interpreter.h: in 498d52f806 outdated

110+    bool set[6];
111+    uint256 value[6];
112+
113+    void Clear()
114+    {
115+        for (int i=0; i<12; i++) {

sipa commented at 3:56 pm on September 2, 2016:

s/12/6/ ?

jl2012 commented at 4:55 pm on September 2, 2016:

fixed

in src/script/interpreter.cpp: in 498d52f806 outdated

1230@@ -1229,7 +1231,12 @@ bool TransactionSignatureChecker::CheckSig(const vector<unsigned char>& vchSigIn
1231     int nHashType = vchSig.back();
1232     vchSig.pop_back();
1233 
1234-    uint256 sighash = SignatureHash(scriptCode, *txTo, nIn, nHashType, amount, sigversion, this->txdata);
1235+    int entry = ((nHashType & 0x1F) == SIGHASH_SINGLE ? 0 : ((nHashType & 0x1F) == SIGHASH_NONE ? 1 : 2)) + ((nHashType & 0x80) ? 3 : 0);

sipa commented at 4:03 pm on September 2, 2016:

Perhaps add a comment here that sigversion is not used in the entry calculation because we know there will only be one sigversion across an entire input. Also, if future extra sighashes are defined, this may need extension (or, alternatively, cache read/write could be skipped for sigversion != 0).

jl2012 commented at 4:46 pm on September 2, 2016:

yes, I changed that to 12 as I thought there are 12 combinations (sw and pre-sw). Later I figured out that was not needed but forgot to change it back

jl2012 force-pushed on Sep 2, 2016

fanquake added the label Refactoring on Sep 3, 2016

jl2012 force-pushed on Sep 4, 2016

jl2012 commented at 6:23 am on September 5, 2016: contributor

fixed a bug in #4562. It requires 256 cache slots instead of just 6 for the common types, since the nHashType is part of the sighash so each one is unique.

Need more tests for witness txs.

sipa commented at 3:17 pm on September 5, 2016: member

Nice work with the tests so far!

jl2012 force-pushed on Sep 5, 2016

jl2012 force-pushed on Sep 6, 2016

jl2012 commented at 6:48 am on September 6, 2016: contributor

Test updated to cover #8524

Benchmarking with and without #8524/#8654: https://gist.github.com/jl2012/f3262fd7cf47664ce43f036b9539e831

in qa/rpc-tests/test_framework/script.py: in 93b2d5c2e1 outdated

881@@ -882,7 +882,7 @@ def SignatureHash(script, txTo, inIdx, hashtype):
882         tmp = txtmp.vout[outIdx]
883         txtmp.vout = []
884         for i in range(outIdx):
885-            txtmp.vout.append(CTxOut())
886+            txtmp.vout.append(CTxOut(-1))

jl2012 commented at 6:49 am on September 6, 2016:

See #8667

jl2012 force-pushed on Sep 6, 2016

NicolasDorier commented at 9:16 am on September 6, 2016: contributor

is it be possible to put the cache as a field of the TransactionChecker rather than as yet another parameter in CheckSig ?

sipa commented at 9:19 am on September 6, 2016: member

@NicolasDorier I believe so, yes!

sipa commented at 9:24 am on September 6, 2016: member

@NicolasDorier Actually, no. Not until we outlaw OP_CODESEPARATOR, as the script execution needs to be able to wipe the cache.

NicolasDorier commented at 9:37 am on September 6, 2016: contributor

@sipa you can add a ScriptCode field to SigHashCache, and add a check in CheckSig to use the cache only if the ScriptCode match.

NicolasDorier commented at 9:39 am on September 6, 2016: contributor

I hope nobody intend to outlaw OP_CODESEPARATOR, it is a nice way for a signer to sign a particular executed path without requiring multiple public key. May have potential cool things to do with it and MAST, as with MAST we can have lots of different branches.

sipa commented at 9:55 am on September 6, 2016: member

@NicolasDorier Nice idea. Implemented in https://github.com/sipa/bitcoin/commits/sighashcache. (@jl2012: feel free to squash if you like it)

I don’t understand what you’re suggesting about OP_CODESEPARATOR. Perhaps we should discuss that on IRC instead.

NicolasDorier commented at 10:17 am on September 6, 2016: contributor

Code Review ACK for https://github.com/sipa/bitcoin/commits/sighashcache (this PR + the commit removing the param to CheckSig)

However, I’m not sure it is really useful, in a case of O(n^2) hashing attack, having a 10x performance improvement for a 5 second block verification is not going to do huge difference.

jl2012 force-pushed on Sep 6, 2016

jl2012 commented at 10:52 am on September 6, 2016: contributor

Squashed with @sipa ’s patch @NicolasDorier, the effect would be limited for a miner-initiated attack. However, for standard transaction, 10x could be a make or break difference

sipa commented at 11:57 am on September 6, 2016: member

utACK 9e4cf76412e17efa8fdeb3e7626ccf25b578e036

NicolasDorier commented at 12:21 pm on September 6, 2016: contributor

@jl2012 as implemented now, the cache is per input. So how can it increase 10x for standard transaction ? Right now it improve the case of one input with lots of checksig.

sipa commented at 12:23 pm on September 6, 2016: member

@NicolasDorier Please move back-on-forth discussions to IRC.

NicolasDorier commented at 2:21 pm on September 6, 2016: contributor

utACK 9e4cf76

jl2012 force-pushed on Sep 8, 2016

jl2012 commented at 5:00 pm on September 8, 2016: contributor

Is this a target of 0.13.1?

laanwj added this to the milestone 0.13.1 on Sep 8, 2016

MarcoFalke added the label Needs backport on Sep 9, 2016

btcdrak commented at 12:01 pm on September 9, 2016: contributor

utACK 9e4cf76

NicolasDorier commented at 4:25 am on September 17, 2016: contributor

I think it would be even better to tie the lifetime of the cache to the EvalScript function only instead of the TransactionSignatureChecker. Just dropping it as an idea, still utACK 9e4cf76.

jl2012 referenced this in commit de93019e41 on Sep 19, 2016

jl2012 referenced this in commit 63db0c6b09 on Sep 19, 2016

jl2012 referenced this in commit ed71079971 on Sep 19, 2016

jl2012 commented at 1:01 pm on September 19, 2016: contributor

I have an alternative implementation as ed71079 in #8756. It only reuse a sighash for a signature within CHECKMULTISIG. It is less risky as we don’t need to worry about any unexpected behavior due to OP_CODESEPARATOR and FindAndDelete. Nonetheless, #8756 could provide the same level of sighash attack protection as #8654 combined with #8755.

jl2012 commented at 3:14 pm on September 22, 2016: contributor

I think it would take more time to analysis this issue and figure out the best approach. I’m inclined not to include this in 0.13.1

laanwj removed this from the milestone 0.13.1 on Sep 22, 2016

MarcoFalke removed the label Needs backport on Sep 24, 2016

jl2012 referenced this in commit 6b194c8b80 on Sep 30, 2016

jl2012 referenced this in commit c1eea2ccce on Oct 27, 2016

jl2012 force-pushed on Oct 29, 2016

jl2012 commented at 4:48 am on October 29, 2016: contributor

Tests are updated with FindAndDelete tests. The earlier version (#4562) did not reset the cache after FindAndDelete and the new tests would have caught the bug.

However, the tests require the public key recovery code from https://github.com/petertodd/python-bitcoinlib , which may have copyright issues. Any suggestions?

Add sighash cache 3cef0a96ab

[qa] add rpc-test for sighash cache 838a00eb5f

[qa] Add public key recovery to test_framework e79ab64425

[qa] add FindAndDelete tests for sighash cache c70b828979

jl2012 force-pushed on Dec 22, 2016

jonasschnelli added this to the milestone 0.14.0 on Dec 22, 2016

morcos commented at 6:35 pm on January 5, 2017: member

I’m interested in understanding the benchmark results a little bit more.

It seems there are huge speed ups in big CHECKMULTISIG transactions, but there appear to be a non-neglible slowdown in more regular transactions (the last test in the benchmark).

I’d be concerned that this code will on average be a slow down to block validation. Has it been benchmarked for typical blocks either during IBD or normal operation.

jl2012 commented at 7:36 pm on January 5, 2017: contributor

@morcos: good question. I’ll try to do some benchmarking in real operation

morcos commented at 7:38 pm on January 9, 2017: member

I did some benchmarking but did not see any noticeable performance difference either way for typical usage

laanwj removed this from the milestone 0.14.0 on Jan 12, 2017

laanwj commented at 7:26 pm on January 12, 2017: member

Untagging this for 0.14 as discussed in the meeting

TheBlueMatt commented at 8:44 pm on July 11, 2017: member

Needs rebase (though if you dont get to it early this week maybe just wait until post-15).

kallewoof commented at 7:40 am on February 23, 2018: member

@jl2012 Should this have the “up for grabs” label so someone can pick it up, in case you’re busy elsewhere?

jl2012 commented at 5:45 am on February 26, 2018: contributor

@kallewoof This PR is quite risky (might introduce consensus bug), but not very helpful unless we have the following softforks: 1. limiting SIGHASH to 6 types; 2. disallow OP_CODESEPARATOR; 3. disallow FindAndDelete(). The first one is already a policy and the other two are proposed in #11423. However policy is not enough

kallewoof commented at 6:31 am on February 26, 2018: member

@jl2012 Got it! Maybe add [WIP] to it so we know not to review it until it’s ready for merging.

jl2012 renamed this:
~~Reuse sighash computations across evaluation (rebase of #4562)~~
[WIP] Reuse sighash computations across evaluation
on Mar 5, 2018

jnewbery commented at 5:09 pm on April 4, 2018: member

Recommend we close this PR for now. If the following events happen:

limiting SIGHASH to 6 types;
disallow OP_CODESEPARATOR;
disallow FindAndDelete()

we can reopen.

Does that sound reasonable @jl2012 ?

jl2012 commented at 4:54 pm on April 5, 2018: contributor

agree with @jnewbery

jl2012 closed this on Apr 5, 2018

Rspigler commented at 11:48 pm on November 6, 2018: contributor

@fanquake shouldn’t this and #8755 be added to ‘Segwit’ as well? (If this were merged, #8755 could be merged).

MarcoFalke locked this on Sep 8, 2021

[WIP] Reuse sighash computations across evaluation #8654