test: Add Compact Block Encoding test `ReceiveWithExtraTransactions` covering non-empty `extra_txn` #30237

AngusP · 2024-06-06T11:17:28Z

This test uses the extra_txn (vExtraTxnForCompact) vector of optional orphan/conflicted/etc. transactions to provide transactions to a PartiallyDownloadedBlock that are not otherwise present in the mempool, and check that they are used.

This also covers a former nullptr deref bug that was fixed in #29752 (bf031a5) where the extra_txn vec/circular-buffer was null-initialized and not yet filled when dereferenced in PartiallyDownloadedBlock::InitData.

…pty in all test cases

DrahtBot · 2024-06-06T11:17:31Z

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	marcofleon, dergoegge, glozow
Concept ACK	instagibbs

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#29625 (Several randomness improvements by sipa)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

This new test uses the `vExtraTxnForCompact` (`extra_txn`) vector of optional orphan/conflicted/etc. transactions to provide a transaction in a compact block that was not otherwise present in our mempool. This also covers an improbable nullptr deref bug addressed in bf031a5 (bitcoin#29752) where the `extra_txn` vec/circular-buffer was sometimes null-initialized and not yet filled when dereferenced in `PartiallyDownloadedBlock::InitData`.

DrahtBot · 2024-06-06T12:08:36Z

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the
documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

_{Debug: https://github.com/bitcoin/bitcoin/runs/25888431395}

instagibbs

concept ACK!

instagibbs · 2024-06-06T13:40:49Z

src/test/blockencodings_tests.cpp

+        // Add an unrelated tx to extra_txn:
+        extra_txn[0] = non_block_tx;
+        // and a tx from the block that's not in the mempool:
+        extra_txn[1] = block.vtx[1];


I think another useful case is a transaction that's also in your mempool

L325 has pool.addUnchecked(entry.FromTx(block.vtx[2])); which adds a tx from the block to the mempool, giving .IsTxAvailable(2) (.IsTxAvailable(0) should always be true as that's the coinbase which is in the compact block header, IIUC).

SimpleRoundTripTest and a couple others in here also already covered the add to mempool case.

dergoegge

Code review ACK 4c99301

I've verified that this can reproduce the nullptr deref bug by reverting a8203e9 and making short id collisions more likely (see top commits on: https://github.com/dergoegge/bitcoin/commits/2024-06-cmpctblk-extra-txn-test/).

$ n=0; while (( n++ < 100 )); do src/test/test_bitcoin --run_test=blockencodings_tests/ReceiveWithExtraTransactions ; done
...
Running 1 test case...
unknown location(0): fatal error: in "blockencodings_tests/ReceiveWithExtraTransactions": memory access violation at address: 0x00000059: no mapping at fault address
../../src/test/blockencodings_tests.cpp(333): last checkpoint

*** 1 failure is detected in the test module "Bitcoin Core Test Suite"
...

While it might be extremely rare, I believe this test is flaky due to possible short id collisions. Flakes can be observed by cherry picking just dergoegge@540fb4e (i.e. increasing the likelyhood of collisions):

$ n=0; while (( n++ < 100 )); do src/test/test_bitcoin --run_test=blockencodings_tests/ReceiveWithExtraTransactions ; done
...
Running 1 test case...
../../src/test/blockencodings_tests.cpp(347): error: in "blockencodings_tests/ReceiveWithExtraTransactions": check partial_block_with_extra.IsTxAvailable(2) has failed

*** 1 failure is detected in the test module "Bitcoin Core Test Suite"
...
Running 1 test case...
../../src/test/blockencodings_tests.cpp(333): error: in "blockencodings_tests/ReceiveWithExtraTransactions": check partial_block.InitData(cmpctblock, extra_txn) == READ_STATUS_OK has failed
../../src/test/blockencodings_tests.cpp(336): error: in "blockencodings_tests/ReceiveWithExtraTransactions": check partial_block.IsTxAvailable(2) has failed
../../src/test/blockencodings_tests.cpp(343): error: in "blockencodings_tests/ReceiveWithExtraTransactions": check partial_block_with_extra.InitData(cmpctblock, extra_txn) == READ_STATUS_OK has failed
../../src/test/blockencodings_tests.cpp(346): error: in "blockencodings_tests/ReceiveWithExtraTransactions": check partial_block_with_extra.IsTxAvailable(1) has failed
../../src/test/blockencodings_tests.cpp(347): error: in "blockencodings_tests/ReceiveWithExtraTransactions": check partial_block_with_extra.IsTxAvailable(2) has failed

*** 5 failures are detected in the test module "Bitcoin Core Test Suite"

Not sure if that is worth addressing since it's so rare but perhaps simply adding a comment that the test might fail every 2^48 runs is good?

AngusP · 2024-06-07T07:51:48Z

Not sure if that is worth addressing since it's so rare but perhaps simply adding a comment that the test might fail every 2^48 runs is good?

I think it's worth avoiding, I don't really like the notion of flaky tests maybe failing for a random reason, even if it is very improbable. I'd guess short-ID collisions would also affect some of the other existing tests in here so there's additional benefit in them not being flaky too.

glozow · 2024-06-07T10:42:27Z

Concept ACK

Not sure if that is worth addressing since it's so rare but perhaps simply adding a comment that the test might fail every 2^48 runs is good?

I think it's worth avoiding, I don't really like the notion of flaky tests maybe failing for a random reason, even if it is very improbable. I'd guess short-ID collisions would also affect some of the other existing tests in here so there's additional benefit in them not being flaky too.

Not sure exactly how flaky it is and don't want to blow this out of proportion. Comment sounds good to save a future debugger from headache. If we might hit it, you can knock it down closer to 0 by running it e.g. 5 times and asserting that it doesn't fail every time, like in coinselector_tests:

bitcoin/src/wallet/test/coinselector_tests.cpp

Lines 752 to 777 in 4a020ca

    
           // Again, we only create the wallet once to save time, but we still run the coin selection RUN_TESTS times. 
        
           for (int i = 0; i < RUN_TESTS; i++) { 
        
               // picking 50 from 100 coins doesn't depend on the shuffle, 
        
               // but does depend on randomness in the stochastic approximation code 
        
               const auto result25 = KnapsackSolver(GroupCoins(available_coins.All()), 50 * COIN, CENT); 
        
               BOOST_CHECK(result25); 
        
               const auto result26 = KnapsackSolver(GroupCoins(available_coins.All()), 50 * COIN, CENT); 
        
               BOOST_CHECK(result26); 
        
               BOOST_CHECK(!EqualResult(*result25, *result26)); 
        
               int fails = 0; 
        
               for (int j = 0; j < RANDOM_REPEATS; j++) 
        
               { 
        
                   // Test that the KnapsackSolver selects randomly from equivalent coins (same value and same input size). 
        
                   // When choosing 1 from 100 identical coins, 1% of the time, this test will choose the same coin twice 
        
                   // which will cause it to fail. 
        
                   // To avoid that issue, run the test RANDOM_REPEATS times and only complain if all of them fail 
        
                   const auto result27 = KnapsackSolver(GroupCoins(available_coins.All()), COIN, CENT); 
        
                   BOOST_CHECK(result27); 
        
                   const auto result28 = KnapsackSolver(GroupCoins(available_coins.All()), COIN, CENT); 
        
                   BOOST_CHECK(result28); 
        
                   if (EqualResult(*result27, *result28)) 
        
                       fails++; 
        
               } 
        
               BOOST_CHECK_NE(fails, RANDOM_REPEATS); 
        
           }

maflcko · 2024-06-07T13:24:06Z

Would it be difficult to make the test deterministic?

AngusP · 2024-06-12T08:54:11Z

Would it be difficult to make the test deterministic?

Yes, the straightforward way would be to replace the InsecureRand256() with fixed hashes that don't result in transaction short IDs that collide. Less-straightforward but maybe better would be to keep using random hashes but check for a short ID collision and try again with a different random hash until the collision is gone -- or start with one random hash and change it in a way that guarantees the short ID (siphash) will be different, but I'm not sure if siphash is easily 'attackable' in that sense.

maflcko · 2024-06-12T09:01:06Z

InsecureRand256

I'd say longer them those global non-deterministic functions should go away anyway. Not something you need to do here, but if you want you can create a commit to accept a FastRandomContext reference as param to BuildBlockTestCase, then in each unit test, create a local FastRandomContext and bind it to a lambda named BuildBlockTestCase.

AngusP · 2024-06-12T21:36:20Z

Pushed 09b90c6 which makes the tests deterministic by using predictable 'random' numbers. I've jsut picked them, there's nothing particularly special about their values.

Using this to reproduce the issue @dergoegge pointed out:

diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp
index 695e8d806a..64d635a97a 100644
--- a/src/blockencodings.cpp
+++ b/src/blockencodings.cpp
@@ -44,7 +44,8 @@ void CBlockHeaderAndShortTxIDs::FillShortTxIDSelector() const {

 uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const Wtxid& wtxid) const {
     static_assert(SHORTTXIDS_LENGTH == 6, "shorttxids calculation assumes 6-byte shorttxids");
-    return SipHashUint256(shorttxidk0, shorttxidk1, wtxid) & 0xffffffffffffL;
+    // return SipHashUint256(shorttxidk0, shorttxidk1, wtxid) & 0xffffffffffffL;
+    return SipHashUint256(shorttxidk0, shorttxidk1, wtxid) & 0x0f;
 }

and then running

set -e;
n=0;
while (( n++ < 5000 )); do
    src/test/test_bitcoin --run_test=blockencodings_tests;
done

the failures were either READ_STATUS_FAILED from InitData, or IsTxAvailable(...) == false when we were expecting true.

On the above-patched 09b90c6, I've not seen any failures with 0x0f short IDs and ~10k re-runs of all the blockencodings tests.

Use a new FastRandomContext with a fixed seed in each test, to ensure 'random' uint256s used as fake prevouts are deterministic, so in-turn test txids and short IDs are deterministic and don't collide causing very rare but flaky test failures.
Add new test-only/internal initializer for CBlockHeaderAndShortTxIDs that takes a specified nonce to further ensure determinism and avoid rare but undesireable short ID collisions.
In a test context this nonce is set to a fixed known-good value. Normally it is random, as previously.

dergoegge

tACK 09b90c6

src/blockencodings.h

src/test/blockencodings_tests.cpp

src/test/fuzz/partially_downloaded_block.cpp

src/blockencodings.h

refactor: CBlockHeaderAndShortTxIDs constructor now always takes an explicit nonce. test: Make blockencodings_tests deterministic using fixed seed providing deterministic CBlockHeaderAndShortTxID nonces and dummy transaction IDs. Fixes very rare flaky test failures, where the ShortIDs of test transactions collide, leading to `READ_STATUS_FAILED` from PartiallyDownloadedBlock::InitData and/or `IsTxAvailable` giving `false` when the transaction should actually be available. * Use a new `FastRandomContext` with a fixed seed in each test, to ensure 'random' uint256s used as fake prevouts are deterministic, so in-turn test txids and short IDs are deterministic and don't collide causing very rare but flaky test failures. * Add new test-only/internal initializer for `CBlockHeaderAndShortTxIDs` that takes a specified nonce to further ensure determinism and avoid rare but undesireable short ID collisions. In a test context this nonce is set to a fixed known-good value. Normally it is random, as previously. Flaky test failures can be reproduced with: ```patch diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp index 695e8d8..64d635a97a 100644 --- a/src/blockencodings.cpp +++ b/src/blockencodings.cpp @@ -44,7 +44,8 @@ void CBlockHeaderAndShortTxIDs::FillShortTxIDSelector() const { uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const Wtxid& wtxid) const { static_assert(SHORTTXIDS_LENGTH == 6, "shorttxids calculation assumes 6-byte shorttxids"); - return SipHashUint256(shorttxidk0, shorttxidk1, wtxid) & 0xffffffffffffL; + // return SipHashUint256(shorttxidk0, shorttxidk1, wtxid) & 0xffffffffffffL; + return SipHashUint256(shorttxidk0, shorttxidk1, wtxid) & 0x0f; } ``` to increase the likelihood of a short ID collision; and running ```shell set -e; n=0; while (( n++ < 5000 )); do src/test/test_bitcoin --run_test=blockencodings_tests; done ```

marcofleon

Code review ACK 55eea00. I ran the blockencodings unit test and no issues with the new test case.

dergoegge

Code review ACK 55eea00

glozow

ACK 55eea00

glozow · 2024-07-01T12:30:51Z

src/net_processing.cpp

@@ -2549,7 +2549,7 @@ void PeerManagerImpl::ProcessGetBlockData(CNode& pfrom, Peer& peer, const CInv&
                if (a_recent_compact_block && a_recent_compact_block->header.GetHash() == pindex->GetBlockHash()) {
                    MakeAndPushMessage(pfrom, NetMsgType::CMPCTBLOCK, *a_recent_compact_block);
                } else {
-                    CBlockHeaderAndShortTxIDs cmpctblock{*pblock};
+                    CBlockHeaderAndShortTxIDs cmpctblock{*pblock, GetRand<uint64_t>()};


Another PR could change these calls to use PeerManagerImpl::m_rng though it would require taking off the g_msgproc_mutex guard.

test: refactor: Rename extra_txn to const empty_extra_txn as it is em…

4621e7c

…pty in all test cases

DrahtBot added the Tests label Jun 6, 2024

AngusP force-pushed the 2024-06-cmpctblk-extra-txn-test branch from b9e1704 to 4c99301 Compare June 6, 2024 12:08

DrahtBot added the CI failed label Jun 6, 2024

DrahtBot removed the CI failed label Jun 6, 2024

instagibbs reviewed Jun 6, 2024

View reviewed changes

dergoegge approved these changes Jun 6, 2024

View reviewed changes

DrahtBot requested a review from instagibbs June 6, 2024 15:18

AngusP requested a review from dergoegge June 12, 2024 21:36

dergoegge approved these changes Jun 17, 2024

View reviewed changes

DrahtBot requested a review from glozow June 17, 2024 10:35

glozow reviewed Jun 17, 2024

View reviewed changes

src/blockencodings.h Outdated Show resolved Hide resolved

src/test/blockencodings_tests.cpp Outdated Show resolved Hide resolved

DrahtBot requested a review from glozow June 17, 2024 11:58

AngusP force-pushed the 2024-06-cmpctblk-extra-txn-test branch 2 times, most recently from 8df9d16 to bba77a2 Compare June 18, 2024 22:15

DrahtBot added the CI failed label Jun 18, 2024

This comment was marked as outdated.

Sign in to view

DrahtBot removed the CI failed label Jun 19, 2024

AngusP commented Jun 19, 2024

View reviewed changes

src/test/fuzz/partially_downloaded_block.cpp Outdated Show resolved Hide resolved

AngusP requested a review from dergoegge June 19, 2024 12:28

dergoegge reviewed Jun 19, 2024

View reviewed changes

src/test/fuzz/partially_downloaded_block.cpp Outdated Show resolved Hide resolved

glozow reviewed Jun 19, 2024

View reviewed changes

src/blockencodings.h Show resolved Hide resolved

AngusP force-pushed the 2024-06-cmpctblk-extra-txn-test branch 2 times, most recently from 34159eb to c24d2bb Compare June 19, 2024 21:50

AngusP force-pushed the 2024-06-cmpctblk-extra-txn-test branch from c24d2bb to 55eea00 Compare June 19, 2024 21:56

AngusP requested review from glozow and dergoegge June 20, 2024 07:45

DrahtBot mentioned this pull request Jun 28, 2024

Several randomness improvements #29625

Merged

marcofleon reviewed Jun 28, 2024

View reviewed changes

dergoegge approved these changes Jul 1, 2024

View reviewed changes

glozow reviewed Jul 1, 2024

View reviewed changes

glozow merged commit 0bd2bd1 into bitcoin:master Jul 1, 2024

bitcoin locked and limited conversation to collaborators Jul 1, 2025

test: Add Compact Block Encoding test ReceiveWithExtraTransactions covering non-empty extra_txn #30237

test: Add Compact Block Encoding test ReceiveWithExtraTransactions covering non-empty extra_txn #30237

Uh oh!

Conversation

AngusP commented Jun 6, 2024

Uh oh!

DrahtBot commented Jun 6, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Code Coverage

Reviews

Conflicts

Uh oh!

DrahtBot commented Jun 6, 2024

Uh oh!

instagibbs left a comment

Choose a reason for hiding this comment

Uh oh!

instagibbs Jun 6, 2024

Choose a reason for hiding this comment

Uh oh!

AngusP Jun 6, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

dergoegge left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

AngusP commented Jun 7, 2024

Uh oh!

glozow commented Jun 7, 2024

Uh oh!

maflcko commented Jun 7, 2024

Uh oh!

AngusP commented Jun 12, 2024

Uh oh!

maflcko commented Jun 12, 2024

Uh oh!

AngusP commented Jun 12, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

dergoegge left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

This comment was marked as outdated.

Uh oh!

Uh oh!

Uh oh!

marcofleon left a comment

Choose a reason for hiding this comment

Uh oh!

dergoegge left a comment

Choose a reason for hiding this comment

Uh oh!

glozow left a comment

Choose a reason for hiding this comment

Uh oh!

glozow Jul 1, 2024

Choose a reason for hiding this comment

Uh oh!

Uh oh!

test: Add Compact Block Encoding test `ReceiveWithExtraTransactions` covering non-empty `extra_txn` #30237

test: Add Compact Block Encoding test `ReceiveWithExtraTransactions` covering non-empty `extra_txn` #30237

DrahtBot commented Jun 6, 2024 •

edited

Loading

AngusP Jun 6, 2024 •

edited

Loading

dergoegge left a comment •

edited

Loading

AngusP commented Jun 12, 2024 •

edited

Loading