A short ID collision can invalidate a mempool-sourced transaction after an unrelated transaction was found in extra_txn.
Track each slot's source so extra_count is decremented only when the invalidated slot came from extra_txn. Retain the source after a collision to preserve the rule that later candidates do not refill the slot.
<!--e57a25ab6845829454e8d69fc972939a-->
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
<!--006a51241073e994b41acfe9ec718e94-->
For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/35727.
<!--021abf342d371248e50ceaed478a90ca-->
See the guideline and AI policy for information on the review process.
| Type | Reviewers |
|---|---|
| ACK | l0rinc, andrewtoth, sedited |
| Stale ACK | davidgumberg |
If your review is incorrectly listed, please copy-paste <code><!--meta-tag:bot-skip--></code> into the comment that the bot should ignore.
<!--174a7506f384e20aa4161008e828411d-->
Reviewers, this pull request conflicts with the following ones:
cmpctblock message reconstruction statistics [part of prefill series] by davidgumberg)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.
<!--5faf32d7da4f0f540f40219e4f7537a3-->
161 | @@ -162,7 +162,9 @@ ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& c 162 | txn_available[idit->second]->GetWitnessHash() != extra_txn[i].second->GetWitnessHash()) { 163 | txn_available[idit->second].reset(); 164 | mempool_count--; 165 | - extra_count--; 166 | + // The incumbent may have come from the mempool, so keep 167 | + // extra_count as a conservative lower bound. 168 | + if (extra_count > 0) extra_count--;
My main concern is that this masks the accounting problem rather than fixing it.
If the collision invalidates a mempool-sourced transaction after an unrelated extra transaction has been counted, extra_count > 0, so the guard still subtracts that unrelated credit.
I've reimplemented it in https://github.com/l0rinc/bitcoin/pull/229, which fails with [0 != 1] against this implementation.
Could we track the source of each slot and decrement extra_count only when the invalidated transaction came from extra_txn?
yes, but I think it involves another vector allocation of bools, and I'm not sure it's worth slowing down anything for a log detail... thoughts? Maybe something simpler I didn't consider
tx_source replaces the previous have_txn, extending the two states to three - but we don't have an extra vector allocation there.
ah sorry I have reading comprehension at the end of the day, will look
feel free to open the PR, I'll close this one
edit: Was told to just take it, so I shall
163 | @@ -162,7 +164,7 @@ ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& c 164 | txn_available[idit->second]->GetWitnessHash() != extra_txn[i].second->GetWitnessHash()) { 165 | txn_available[idit->second].reset(); 166 | mempool_count--; 167 | - extra_count--; 168 | + if (tx_source[idit->second] == TxSource::EXTRA) extra_count--;
feel-free-to-ignore: Would be nice to separate the extra_count vs the mempool_count e.g.:
https://github.com/bitcoin/bitcoin/commit/c9632a4cc1fa47d5a07d8f1207a2dce2982c2be8
But that can also be done after this PR
On second thought I think this should definitely be done outside of this PR, since there should probably be tests added
yes I have an eye for a follow-up; I'd like to increase fuzz coverage and might be a good fit
done
371 | + extra_txn[2] = {block.vtx[2]->GetWitnessHash(), non_block_tx}; 372 | + TestPartiallyDownloadedBlock partial_block_with_extra_collision{&pool}; 373 | + BOOST_CHECK_EQUAL(partial_block_with_extra_collision.InitData(cmpctblock, extra_txn), READ_STATUS_OK); 374 | + BOOST_CHECK(partial_block_with_extra_collision.IsTxAvailable(1)); 375 | + BOOST_CHECK(!partial_block_with_extra_collision.IsTxAvailable(2)); 376 | + BOOST_CHECK_EQUAL(partial_block_with_extra_collision.GetExtraCount(), 1U);
not blocking: probably a good idea to assert the mempool count here.
143 | @@ -144,6 +144,13 @@ class TestHeaderAndShortIDs { 144 | SERIALIZE_METHODS(TestHeaderAndShortIDs, obj) { READWRITE(obj.header, obj.nonce, Using<VectorFormatter<CustomUintFormatter<CBlockHeaderAndShortTxIDs::SHORTTXIDS_LENGTH>>>(obj.shorttxids), obj.prefilledtxn); } 145 | }; 146 | 147 | +class TestPartiallyDownloadedBlock : public PartiallyDownloadedBlock {
done
112 | @@ -113,16 +113,18 @@ ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& c 113 | if (shorttxids.size() != cmpctblock.shorttxids.size()) 114 | return READ_STATUS_FAILED; // Short ID collision 115 | 116 | - std::vector<bool> have_txn(txn_available.size()); 117 | + enum class TxSource : uint8_t { NONE, MEMPOOL, EXTRA }; 118 | + // A non-NONE source also marks a collided slot as seen
+1 and then COLLIDED can be used in place of the txn_available check, e.g.:
} else if (tx_source[idit->second] != TxSource::COLLIDED) {
// If we find two mempool txn that match the short id, just request it.
// This should be rare enough that the extra bandwidth doesn't matter,
// but eating a round-trip due to FillBlock failure would be annoying
txn_available[idit->second].reset();
mempool_count--;
tx_source[idit->second] = TxSource::COLLIDED;
}
That makes the collision logic a lot less subtle.
done, readability improvements are good if we're already here
ACK 0c69909e3a2e8671e48ed360cec20b232674605c
Left a few non-blocking nits (applied them to https://github.com/l0rinc/bitcoin/pull/229 for convenience) - happy to reack if you take them.
crACK https://github.com/bitcoin/bitcoin/commit/0c69909e3a2e8671e48ed360cec20b232674605c
TxSource is nice, IMO makes this code easier to reason about. I think adding an explicit COLLIDED state as suggested above by l0rinc is a good idea.
A short ID collision can invalidate a mempool-sourced transaction after an unrelated transaction was found in extra_txn.
Track each slot's source so extra_count is decremented only when the invalidated slot came from extra_txn. Mark collided slots explicitly so later candidates do not refill them.
addressed all feedback, pushed a couple more coverage cases. will work on making fuzz coverage of collisions as a followup
nit: not necessarily suggesting we add them, but it's what I used to test the changes locally.
Assume(size_t(std::ranges::count_if(txn_available, [](auto& tx) { return tx != nullptr; })) == prefilled_count + mempool_count);
Assume(size_t(std::ranges::count(tx_source, TxSource::EXTRA)) == extra_count);
Assume(extra_count <= mempool_count);
146 | @@ -147,6 +147,7 @@ class TestHeaderAndShortIDs { 147 | struct TestPartiallyDownloadedBlock : PartiallyDownloadedBlock { 148 | using PartiallyDownloadedBlock::PartiallyDownloadedBlock; 149 | 150 | + size_t GetMempoolCount() const { return mempool_count; }
will consider if I need to retouch
382 | + TestPartiallyDownloadedBlock partial_block_with_extra_source_collision{&pool}; 383 | + BOOST_CHECK_EQUAL(partial_block_with_extra_source_collision.InitData(cmpctblock, extra_txn), READ_STATUS_OK); 384 | + BOOST_CHECK(!partial_block_with_extra_source_collision.IsTxAvailable(1)); 385 | + BOOST_CHECK(!partial_block_with_extra_source_collision.IsTxAvailable(2)); 386 | + BOOST_CHECK_EQUAL(partial_block_with_extra_source_collision.GetMempoolCount(), 0U); 387 | + BOOST_CHECK_EQUAL(partial_block_with_extra_source_collision.GetExtraCount(), 0U);
6aa5d8d blockencodings: fix extra transaction count:
Same here, the first test commit is meant to help us characterize the extent of the fix. It's not immediately obvious, for example, if this line would have passed before the fix as well.
<details><summary>test: characterize extra transaction miscount</summary>
diff --git a/src/test/blockencodings_tests.cpp b/src/test/blockencodings_tests.cpp
index e4200cace2..45ecfcc595 100644
--- a/src/test/blockencodings_tests.cpp
+++ b/src/test/blockencodings_tests.cpp
@@ -144,6 +144,13 @@ public:
SERIALIZE_METHODS(TestHeaderAndShortIDs, obj) { READWRITE(obj.header, obj.nonce, Using<VectorFormatter<CustomUintFormatter<CBlockHeaderAndShortTxIDs::SHORTTXIDS_LENGTH>>>(obj.shorttxids), obj.prefilledtxn); }
};
+struct TestPartiallyDownloadedBlock : PartiallyDownloadedBlock {
+ using PartiallyDownloadedBlock::PartiallyDownloadedBlock;
+
+ size_t GetMempoolCount() const { return mempool_count; }
+ size_t GetExtraCount() const { return extra_count; }
+};
+
BOOST_AUTO_TEST_CASE(NonCoinbasePreforwardRTTest)
{
CTxMemPool& pool = *Assert(m_node.mempool);
@@ -319,6 +326,13 @@ BOOST_AUTO_TEST_CASE(ReceiveWithExtraTransactions) {
const CTransactionRef non_block_tx = MakeTransactionRef(std::move(mtx));
CBlock block(BuildBlockTestCase(rand_ctx));
+ // Leave one transaction missing so scanning doesn't stop before the collision.
+ mtx = BuildTransactionTestCase();
+ mtx.vin[0].prevout.hash = Txid::FromUint256(rand_ctx.rand256());
+ block.vtx.push_back(MakeTransactionRef(std::move(mtx)));
+ block.hashMerkleRoot = BlockMerkleRoot(block);
+ while (!CheckProofOfWork(block.GetHash(), block.nBits, Params().GetConsensus())) ++block.nNonce;
+
std::vector<std::pair<Wtxid, CTransactionRef>> extra_txn;
extra_txn.resize(10);
@@ -352,6 +366,34 @@ BOOST_AUTO_TEST_CASE(ReceiveWithExtraTransactions) {
// This transaction is now available via extra_txn:
BOOST_CHECK(partial_block_with_extra.IsTxAvailable(1));
BOOST_CHECK(partial_block_with_extra.IsTxAvailable(2));
+
+ // Simulate a mempool collision after finding an unrelated extra transaction.
+ extra_txn[2] = {block.vtx[2]->GetWitnessHash(), non_block_tx};
+ TestPartiallyDownloadedBlock partial_block_with_extra_collision{&pool};
+ BOOST_CHECK_EQUAL(partial_block_with_extra_collision.InitData(cmpctblock, extra_txn), READ_STATUS_OK);
+ BOOST_CHECK( partial_block_with_extra_collision.IsTxAvailable(1));
+ BOOST_CHECK(!partial_block_with_extra_collision.IsTxAvailable(2));
+ BOOST_CHECK_EQUAL(partial_block_with_extra_collision.GetMempoolCount(), 1);
+ BOOST_CHECK_EQUAL(partial_block_with_extra_collision.GetExtraCount(), 0); // TODO: This should be 1
+
+ // Now also collide the extra-sourced slot: both counters decrement exactly once.
+ extra_txn[3] = {block.vtx[1]->GetWitnessHash(), non_block_tx};
+ TestPartiallyDownloadedBlock partial_block_with_extra_source_collision{&pool};
+ BOOST_CHECK_EQUAL(partial_block_with_extra_source_collision.InitData(cmpctblock, extra_txn), READ_STATUS_OK);
+ BOOST_CHECK(!partial_block_with_extra_source_collision.IsTxAvailable(1));
+ BOOST_CHECK(!partial_block_with_extra_source_collision.IsTxAvailable(2));
+ BOOST_CHECK_EQUAL(partial_block_with_extra_source_collision.GetMempoolCount(), 0);
+ BOOST_CHECK_NE(partial_block_with_extra_source_collision.GetExtraCount(), 0); // TODO: This should be 0
+
+ // Collided slots are terminal: not even the genuine transactions refill them.
+ extra_txn[4] = {block.vtx[2]->GetWitnessHash(), block.vtx[2]};
+ extra_txn[5] = {block.vtx[1]->GetWitnessHash(), block.vtx[1]};
+ TestPartiallyDownloadedBlock partial_block_no_refill{&pool};
+ BOOST_CHECK_EQUAL(partial_block_no_refill.InitData(cmpctblock, extra_txn), READ_STATUS_OK);
+ BOOST_CHECK(!partial_block_no_refill.IsTxAvailable(1));
+ BOOST_CHECK(!partial_block_no_refill.IsTxAvailable(2));
+ BOOST_CHECK_EQUAL(partial_block_no_refill.GetMempoolCount(), 0);
+ BOOST_CHECK_NE(partial_block_no_refill.GetExtraCount(), 0); // TODO: This should be 0
}
}
</details>
In which case the critical fix commit would be minimal and would show the extend of its reach:
diff --git a/src/test/blockencodings_tests.cpp b/src/test/blockencodings_tests.cpp
--- a/src/test/blockencodings_tests.cpp (revision fa4411f8f31e2ea4397e929e706e003e3ba4762f)
+++ b/src/test/blockencodings_tests.cpp (revision 1a6233f82bb6e8f88379360be5b6b94694a8fd04)
@@ -374,7 +374,7 @@
BOOST_CHECK( partial_block_with_extra_collision.IsTxAvailable(1));
BOOST_CHECK(!partial_block_with_extra_collision.IsTxAvailable(2));
BOOST_CHECK_EQUAL(partial_block_with_extra_collision.GetMempoolCount(), 1);
- BOOST_CHECK_EQUAL(partial_block_with_extra_collision.GetExtraCount(), 0); // TODO: This should be 1
+ BOOST_CHECK_EQUAL(partial_block_with_extra_collision.GetExtraCount(), 1);
// Now also collide the extra-sourced slot: both counters decrement exactly once.
extra_txn[3] = {block.vtx[1]->GetWitnessHash(), non_block_tx};
@@ -383,7 +383,7 @@
BOOST_CHECK(!partial_block_with_extra_source_collision.IsTxAvailable(1));
BOOST_CHECK(!partial_block_with_extra_source_collision.IsTxAvailable(2));
BOOST_CHECK_EQUAL(partial_block_with_extra_source_collision.GetMempoolCount(), 0);
- BOOST_CHECK_NE(partial_block_with_extra_source_collision.GetExtraCount(), 0); // TODO: This should be 0
+ BOOST_CHECK_EQUAL(partial_block_with_extra_source_collision.GetExtraCount(), 0);
// Collided slots are terminal: not even the genuine transactions refill them.
extra_txn[4] = {block.vtx[2]->GetWitnessHash(), block.vtx[2]};
@@ -393,7 +393,7 @@
BOOST_CHECK(!partial_block_no_refill.IsTxAvailable(1));
BOOST_CHECK(!partial_block_no_refill.IsTxAvailable(2));
BOOST_CHECK_EQUAL(partial_block_no_refill.GetMempoolCount(), 0);
- BOOST_CHECK_NE(partial_block_no_refill.GetExtraCount(), 0); // TODO: This should be 0
+ BOOST_CHECK_EQUAL(partial_block_no_refill.GetExtraCount(), 0);
}
}
will consider if I need to retouch
121 | for (const auto& [wtxid, txit] : pool->txns_randomized) {
122 | uint64_t shortid = cmpctblock.GetShortID(wtxid);
123 | std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
124 | if (idit != shorttxids.end()) {
125 | - if (!have_txn[idit->second]) {
126 | + if (tx_source[idit->second] == TxSource::NONE) {
super-nit: if you feel like refactoring we could extract the repeated index here and below:
const uint16_t idx{idit->second};
will consider if I need to retouch
retested ACK 6aa5d8d9481f5e06b10095df7f46f0532f7ecdb7
Left a few nits, I'm also fine with merging as is.
PR description needs updating, we no longer retain the original source:
Track each slot's source so extra_count is decremented only when the invalidated slot came from extra_txn. Mark collided slots explicitly to preserve the rule that later candidates do not refill them.
ACK 6aa5d8d9481f5e06b10095df7f46f0532f7ecdb7
ACK 6aa5d8d9481f5e06b10095df7f46f0532f7ecdb7