Page MenuHomePhabricator
Differential D18849

script: (optimization) introduce sighash midstate caching
ClosedPublic
Actions

Authored by PiRK on Wed, Oct 29, 09:42.

Details

Reviewers
Fabien
Group Reviewers
Restricted Project
Commits
rABC36bd4d929e25: script: (optimization) introduce sighash midstate caching
Summary

This introduces a per-txin cache for sighash midstate computation to the script interpreter for legacy (bare) and P2SH.
This reduces the impact of certain types of quadratic hashing attacks that use standard transactions. It is not known to improve the situation for attacks involving non-standard transaction attacks.

The cache works by remembering for each of the 12 sighash modes a (scriptCode, midstate) tuple, which gives a midstate CSHA256 object right before the appending of the sighash type itself (to permit all 256, rather than just the 12 ones that match the modes). The midstate is only reused if the scriptCode matches. This works because - within a single input - only the sighash type and the scriptCode affect the actual sighash used.

This concludes backport of core#32473
https://github.com/bitcoin/bitcoin/pull/32473/commits/92af9f74d74e76681f7d98f293eab226972137b4
https://github.com/bitcoin/bitcoin/pull/32473/commits/b221aa80a081579b8d3b460e3403f7ac0daa7139
https://github.com/bitcoin/bitcoin/pull/32473/commits/83950275eddacac56c58a7a3648ed435a5593328

Depends on D18848

Test Plan

ninja all check-all bitcoin-fuzzers

Diff Detail

Event Timeline

PiRK created this revision.Wed, Oct 29, 09:42
Herald added a reviewer: Restricted Project. · View Herald TranscriptWed, Oct 29, 09:42
PiRK requested review of this revision.Wed, Oct 29, 09:42
teamcity edited the summary of this revision. (Show Details)Wed, Oct 29, 09:42
PiRK added inline comments.Wed, Oct 29, 09:45
src/test/fuzz/script_interpreter.cpp
95 ↗(On Diff #56346)

on it

Harbormaster completed remote builds in B34900: Diff 56346.Wed, Oct 29, 09:46
teamcity added a comment.Wed, Oct 29, 09:47
Build Bitcoin ABC Diffs / Diff Testing (build-clang) failed.

Tail of the build log:

[208/540] Running utility command for check-pow-eda_tests
[209/540] pow: testing grasberg_tests
[210/540] Running utility command for check-pow-grasberg_tests
[211/540] seeder: testing db_tests
[212/540] Running utility command for check-seeder-db_tests
[213/540] seeder: testing message_writer_tests
[214/540] Running utility command for check-seeder-message_writer_tests
[215/540] seeder: testing options_tests
[216/540] Running utility command for check-seeder-options_tests
[217/540] seeder: testing p2p_messaging_tests
[218/540] Running utility command for check-seeder-p2p_messaging_tests
[219/540] seeder: testing parse_name_tests
[220/540] Running utility command for check-seeder-parse_name_tests
[221/540] Building CXX object src/test/CMakeFiles/test_bitcoin.dir/__/wallet/test/ismine_tests.cpp.o
[222/540] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/test_bitcoin-qt_autogen/mocs_compilation.cpp.o
[223/540] seeder: testing write_name_tests
[224/540] Running utility command for check-seeder-write_name_tests
[225/540] Running seeder test suite
PASSED: seeder test suite
[226/540] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/bitcoinaddressvalidatortests.cpp.o
[227/540] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/compattests.cpp.o
[228/540] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/guiutiltests.cpp.o
[229/540] Building CXX object src/test/CMakeFiles/test_bitcoin.dir/transaction_tests.cpp.o
[230/540] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/optiontests.cpp.o
[231/540] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/test_main.cpp.o
[232/540] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/uritests.cpp.o
[233/540] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/util.cpp.o
[234/540] avalanche: testing voterecord_tests
[235/540] pow: testing aserti32d_tests
[236/540] Running utility command for check-avalanche-voterecord_tests
[237/540] Running utility command for check-pow-aserti32d_tests
[238/540] Running pow test suite
PASSED: pow test suite
[239/540] Building CXX object src/test/CMakeFiles/test_bitcoin.dir/__/wallet/test/scriptpubkeyman_tests.cpp.o
[240/540] Building CXX object src/test/CMakeFiles/test_bitcoin.dir/__/wallet/test/coinselector_tests.cpp.o
[241/540] Building CXX object src/test/CMakeFiles/test_bitcoin.dir/__/wallet/test/walletdb_tests.cpp.o
[242/540] Building CXX object src/test/CMakeFiles/test_bitcoin.dir/__/wallet/test/psbt_wallet_tests.cpp.o
[243/540] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/paymentservertests.cpp.o
[244/540] avalanche: testing peermanager_tests
[245/540] Running utility command for check-avalanche-peermanager_tests
[246/540] avalanche: testing processor_tests
[247/540] Running utility command for check-avalanche-processor_tests
[248/540] Running avalanche test suite
PASSED: avalanche test suite
[249/540] Building CXX object src/test/CMakeFiles/test_bitcoin.dir/__/wallet/test/wallet_tests.cpp.o
[250/540] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/apptests.cpp.o
[251/540] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/addressbooktests.cpp.o
[252/540] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/rpcnestedtests.cpp.o
[253/540] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/__/__/wallet/test/wallet_test_fixture.cpp.o
[254/540] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/wallettests.cpp.o
[255/540] Linking CXX executable src/qt/test/test_bitcoin-qt
[256/540] Building CXX object src/test/CMakeFiles/test_bitcoin.dir/script_tests.cpp.o
[257/540] bitcoin-qt: testing test_bitcoin-qt
[258/540] Running bitcoin-qt test suite
PASSED: bitcoin-qt test suite
[259/540] secp256k1: testing secp256k1-tests
[260/540] Running secp256k1 test suite
PASSED: secp256k1 test suite
ninja: build stopped: cannot make progress due to previous errors.
Build build-clang failed with exit code 1
PiRK added inline comments.Wed, Oct 29, 09:56
src/script/interpreter.cpp
1537–1541 ↗(On Diff #56346)

Just to be super-duper sure, I made this public and wrote a unit test on my dev branch.
Not sure if it is worth doing this on master, though. It is pretty simple math.

+BOOST_AUTO_TEST_CASE(sighash_cache_index) {
+    const std::vector<std::tuple<uint32_t, int>> test_cases{
+        {SIGHASH_ALL, 0},
+        {SIGHASH_NONE, 1},
+        {SIGHASH_SINGLE, 2},
+        {SIGHASH_ALL | SIGHASH_ANYONECANPAY, 3},
+        {SIGHASH_NONE | SIGHASH_ANYONECANPAY, 4},
+        {SIGHASH_SINGLE | SIGHASH_ANYONECANPAY, 5},
+        {SIGHASH_ALL | SIGHASH_FORKID, 6},
+        {SIGHASH_NONE | SIGHASH_FORKID, 7},
+        {SIGHASH_SINGLE | SIGHASH_FORKID, 8},
+        {SIGHASH_ALL | SIGHASH_FORKID | SIGHASH_ANYONECANPAY, 9},
+        {SIGHASH_NONE | SIGHASH_FORKID | SIGHASH_ANYONECANPAY, 10},
+        {SIGHASH_SINGLE | SIGHASH_FORKID | SIGHASH_ANYONECANPAY, 11}};
+    for (const auto &[hash_type_value, expected_index] : test_cases) {
+        const SigHashType hash_type{hash_type_value};
+        SigHashCache cache;
+        const int index = cache.CacheIndex(hash_type);
+        BOOST_CHECK_EQUAL(index, expected_index);
+    }
+}
teamcity added a comment.Wed, Oct 29, 09:57
Build Bitcoin ABC Diffs / Diff Testing (build-clang-tidy) failed.

Tail of the build log:

============================== 20 passed in 0.70s ==============================
[207/545] Building CXX object src/seeder/test/CMakeFiles/test-seeder.dir/parse_name_tests.cpp.o
[208/545] Building CXX object src/seeder/test/CMakeFiles/test-seeder.dir/message_writer_tests.cpp.o
[209/545] Test Bitcoin utilities...
[210/545] Building CXX object src/seeder/test/CMakeFiles/test-seeder.dir/write_name_tests.cpp.o
[211/545] Building CXX object src/pow/test/CMakeFiles/test-pow.dir/daa_tests.cpp.o
[212/545] Building CXX object src/pow/test/CMakeFiles/test-pow.dir/eda_tests.cpp.o
[213/545] Building CXX object src/test/CMakeFiles/test_bitcoin.dir/__/__/chronik/test/bridgeprimitives_tests.cpp.o
[214/545] Building CXX object src/pow/test/CMakeFiles/test-pow.dir/aserti32d_tests.cpp.o
[215/545] Building CXX object src/pow/test/CMakeFiles/test-pow.dir/grasberg_tests.cpp.o
[216/545] Building CXX object src/seeder/test/CMakeFiles/test-seeder.dir/p2p_messaging_tests.cpp.o
[217/545] Building CXX object src/pow/test/CMakeFiles/test-pow.dir/fixture.cpp.o
[218/545] Linking CXX executable src/pow/test/test-pow
[219/545] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/bitcoinaddressvalidatortests.cpp.o
[220/545] pow: testing daa_tests
[221/545] Running utility command for check-pow-daa_tests
[222/545] pow: testing eda_tests
[223/545] Running utility command for check-pow-eda_tests
[224/545] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/util.cpp.o
[225/545] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/compattests.cpp.o
[226/545] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/test_bitcoin-qt_autogen/mocs_compilation.cpp.o
[227/545] pow: testing grasberg_tests
[228/545] Running utility command for check-pow-grasberg_tests
[229/545] pow: testing aserti32d_tests
[230/545] Running utility command for check-pow-aserti32d_tests
[231/545] Running pow test suite
PASSED: pow test suite
[232/545] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/uritests.cpp.o
[233/545] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/guiutiltests.cpp.o
[234/545] Building CXX object src/seeder/test/CMakeFiles/test-seeder.dir/fixture.cpp.o
[235/545] Linking CXX executable src/seeder/test/test-seeder
[236/545] seeder: testing options_tests
[237/545] seeder: testing p2p_messaging_tests
[238/545] seeder: testing message_writer_tests
[239/545] seeder: testing db_tests
[240/545] seeder: testing parse_name_tests
[241/545] Running utility command for check-seeder-options_tests
[242/545] seeder: testing write_name_tests
[243/545] Running utility command for check-seeder-message_writer_tests
[244/545] Running utility command for check-seeder-p2p_messaging_tests
[245/545] Running utility command for check-seeder-parse_name_tests
[246/545] Running utility command for check-seeder-db_tests
[247/545] Running utility command for check-seeder-write_name_tests
[248/545] Running seeder test suite
PASSED: seeder test suite
[249/545] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/optiontests.cpp.o
[250/545] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/apptests.cpp.o
[251/545] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/test_main.cpp.o
[252/545] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/rpcnestedtests.cpp.o
[253/545] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/paymentservertests.cpp.o
[254/545] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/__/__/wallet/test/wallet_test_fixture.cpp.o
[255/545] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/addressbooktests.cpp.o
[256/545] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/wallettests.cpp.o
[257/545] Linking CXX executable src/qt/test/test_bitcoin-qt
[258/545] bitcoin-qt: testing test_bitcoin-qt
[259/545] Running bitcoin-qt test suite
PASSED: bitcoin-qt test suite
ninja: build stopped: cannot make progress due to previous errors.
Build build-clang-tidy failed with exit code 1
PiRK planned changes to this revision.Wed, Oct 29, 09:58

need to uncomment a test (debugging leftover)

PiRK updated this revision to Diff 56347.Wed, Oct 29, 10:22

uncomment and fix the mutated cache test. We need to xor the sig_hash_type with 0xdead the same way it is done in SignatureHash in the SCRIPT_ENABLE_REPLAY_PROTECTION case

Harbormaster completed remote builds in B34901: Diff 56347.Wed, Oct 29, 10:36
PiRK added a comment.Wed, Oct 29, 16:04

@bot build-chronik

teamcity awarded a token.Wed, Oct 29, 16:04
Fabien requested changes to this revision.Thu, Oct 30, 09:54
Fabien added a subscriber: Fabien.
Fabien added inline comments.
src/script/interpreter.cpp
1546–1551
src/script/interpreter.h
31

layout

34–40

This doesn't match the implementation, let's try to make it easier to follow

43
44
48
51
src/test/sighash_tests.cpp
297

Please reorder, at least the first 12

This revision now requires changes to proceed.Thu, Oct 30, 09:54
PiRK updated this revision to Diff 56363.Thu, Oct 30, 12:31

rebase

PiRK planned changes to this revision.Thu, Oct 30, 12:32
Harbormaster completed remote builds in B34912: Diff 56363.Thu, Oct 30, 12:43
teamcity added a comment.Thu, Oct 30, 12:43
Build Bitcoin ABC Diffs / Diff Testing (build-clang-tidy) failed.

Tail of the build log:

[489/545] Running utility command for check-bitcoin-server_tests
[490/545] Running utility command for check-bitcoin-txrequest_tests
[491/545] bitcoin: testing txvalidationcache_tests
[492/545] bitcoin: testing db_tests
[493/545] Running utility command for check-bitcoin-txvalidationcache_tests
[494/545] Running utility command for check-bitcoin-db_tests
[495/545] bitcoin: testing validation_tests
[496/545] bitcoin: testing util_tests
[497/545] Running utility command for check-bitcoin-util_tests
[498/545] Running utility command for check-bitcoin-validation_tests
[499/545] bitcoin: testing validationinterface_tests
[500/545] bitcoin: testing ismine_tests
[501/545] bitcoin: testing init_tests
[502/545] Running utility command for check-bitcoin-validationinterface_tests
[503/545] Running utility command for check-bitcoin-ismine_tests
[504/545] Running utility command for check-bitcoin-init_tests
[505/545] bitcoin: testing scriptpubkeyman_tests
[506/545] Running utility command for check-bitcoin-scriptpubkeyman_tests
[507/545] bitcoin: testing validation_block_tests
[508/545] bitcoin: testing bridgecompression_tests
[509/545] Running utility command for check-bitcoin-validation_block_tests
[510/545] Running utility command for check-bitcoin-bridgecompression_tests
[511/545] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/addressbooktests.cpp.o
[512/545] Running utility command for check-pow-aserti32d_tests
[513/545] Running pow test suite
PASSED: pow test suite
[514/545] Running utility command for check-seeder-write_name_tests
[515/545] Running seeder test suite
PASSED: seeder test suite
[516/545] bitcoin: testing walletdb_tests
[517/545] Running utility command for check-bitcoin-walletdb_tests
[518/545] bitcoin: testing psbt_wallet_tests
[519/545] Running utility command for check-bitcoin-psbt_wallet_tests
[520/545] bitcoin: testing validation_chainstatemanager_tests
[521/545] Running utility command for check-bitcoin-validation_chainstatemanager_tests
[522/545] bitcoin: testing wallet_crypto_tests
[523/545] Running utility command for check-bitcoin-wallet_crypto_tests
[524/545] bitcoin: testing chronikbridge_tests
[525/545] Running utility command for check-bitcoin-chronikbridge_tests
[526/545] bitcoin: testing transaction_tests
[527/545] Running utility command for check-bitcoin-transaction_tests
[528/545] bitcoin: testing wallet_tests
[529/545] bitcoin: testing coins_tests
[530/545] Running utility command for check-bitcoin-wallet_tests
[531/545] Running utility command for check-bitcoin-coins_tests
[532/545] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/wallettests.cpp.o
[533/545] bitcoin: testing coinselector_tests
[534/545] Running utility command for check-bitcoin-coinselector_tests
[535/545] bitcoin: testing bridgeprimitives_tests
[536/545] Running utility command for check-bitcoin-bridgeprimitives_tests
[537/545] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/paymentservertests.cpp.o
[538/545] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/__/__/wallet/test/wallet_test_fixture.cpp.o
[539/545] Linking CXX executable src/qt/test/test_bitcoin-qt
[540/545] bitcoin-qt: testing test_bitcoin-qt
[541/545] Running bitcoin-qt test suite
PASSED: bitcoin-qt test suite
[542/545] bitcoin: testing scriptnum_63bit_tests
[543/545] Running utility command for check-bitcoin-scriptnum_63bit_tests
ninja: build stopped: cannot make progress due to previous errors.
Build build-clang-tidy failed with exit code 1
PiRK updated this revision to Diff 56364.Thu, Oct 30, 14:05

fix expect_one in unit test after similar fix in D18848, feedback

Harbormaster completed remote builds in B34913: Diff 56364.Thu, Oct 30, 14:21
PiRK added inline comments.Thu, Oct 30, 15:34
src/test/sighash_tests.cpp
370–371 ↗(On Diff #56364)

additional coverage to what is covered by D18851

Fabien accepted this revision.Thu, Oct 30, 20:54
This revision is now accepted and ready to land.Thu, Oct 30, 20:54
Closed by commit rABC36bd4d929e25: script: (optimization) introduce sighash midstate caching (authored by Pieter Wuille <pieter@wuille.net>, committed by PiRK). · Explain WhyFri, Oct 31, 09:57
This revision was automatically updated to reflect the committed changes.
PiRK added a commit: rABC36bd4d929e25: script: (optimization) introduce sighash midstate caching.

Revision Contents
Changeset List

PathSize
src/
script/
32 lines
40 lines
test/
fuzz/
37 lines
160 lines

Diff 56347

View Options

src/script/interpreter.h

Loading...
View Options

src/script/interpreter.cpp

Loading...
View Options

src/test/fuzz/script_interpreter.cpp

Loading...
View Options

src/test/sighash_tests.cpp

Loading...