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, 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-->
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.
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
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 {
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.
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.