Details

Reviewers

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

Repository

rABC Bitcoin ABC

Lint

Lint Not Applicable

Unit

Tests Not Applicable

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

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);
+    }
+}

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

need to uncomment a test (debugging leftover)

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

@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 ↗	(On Diff #56347)
src/script/interpreter.h
31 ↗	(On Diff #56347)	layout
34–40 ↗	(On Diff #56347)	This doesn't match the implementation, let's try to make it easier to follow
43 ↗	(On Diff #56347)
44 ↗	(On Diff #56347)
48 ↗	(On Diff #56347)
51 ↗	(On Diff #56347)
src/test/sighash_tests.cpp
297 ↗	(On Diff #56347)	Please reorder, at least the first 12

This revision now requires changes to proceed.Thu, Oct 30, 09:54

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

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

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.

script: (optimization) introduce sighash midstate caching
ClosedPublic
Actions

Details

Diff Detail

Event Timeline

Revision Contents
Changeset List

Diff 56373

src/script/interpreter.h

src/script/interpreter.cpp

src/test/fuzz/script_interpreter.cpp

src/test/sighash_tests.cpp

script: (optimization) introduce sighash midstate cachingClosedPublicActions

Details

Diff Detail

Event Timeline

Revision ContentsChangeset List

Diff 56373

src/script/interpreter.h

src/script/interpreter.cpp

src/test/fuzz/script_interpreter.cpp

src/test/sighash_tests.cpp

script: (optimization) introduce sighash midstate caching
ClosedPublic
Actions

Revision Contents
Changeset List