refactor: Use typesafe Wtxid in compact block encodings #29752

AngusP · 2024-03-27T17:00:12Z

The first commit replaces uint256 with typesafe Wtxid (or Txid) types introduced in #28107.

The second commit then simplifies the extra tx vector to just be of CTransactionRefs instead of a std::pair<Wtxid, CTransactionRef>, as it's easy to get a Wtxid from a transaction ref.

DrahtBot · 2024-03-27T17:00:15Z

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	glozow, dergoegge

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

src/blockencodings.cpp

…ad of ambiguous uint256. Wtxid/Txid types introduced in bitcoin#28107

dergoegge

Code review ACK e178a52

AngusP · 2024-04-02T11:09:58Z

src/blockencodings.cpp

+        if (extra_txn[i] == nullptr)
+            continue;


I added this mullptr check because some functional tests failed -- as I understand it, this was sort-of a bug in the previous implementation but didn't cause a crash, just 'potentially bad' behaviour?

It may be worth adding a new test to explicitly check this case (and see what the previous impl did with the pair<uint256, CTransactionRef>), but I'd need someone to point to where that test should live.

Also self-nit, a break; instead of continue; may be better as AFAIK this is a ring buffer that'll be sequentially added-to? But again as I'm not that familiar with the code, unsure.

I haven't looked at this, but it may have been intentional to compare against a default constructed uint256 (an array of zeros), so that the runtime is constant and does not depend on the current fill-level of the data structure.

as I understand it, this was sort-of a bug in the previous implementation but didn't cause a crash, just 'potentially bad' behaviour?

It would actually be a crash. Just to recap the bug that exists on master:

If the ring buffer is not fully filled, then it contains default initialized uint256s (as the first pair element)

We loop over the entire ring buffer in PartiallyDownloadedBlock::InitData, compute the short id from the wtxid stored in the first pair element and check if that short id exists for the current compact block.

If a short id computed from the default initialized uint256 collides with an existing short id, then we might end up de-referencing a nullptr here.

This would only happen if the ring buffer has not been fully filled (i.e. there are nullptrs present) and there is a short id collision (short ids are 6 bytes in size), so this is extremely rare and it can also not be remotely triggered by a peer.

To verify this bug I've amended our partially_downloaded_block fuzz harness and changed the short id size to 1 byte here: dergoegge@c6580c0.

It may be worth adding a new test to explicitly check this case (and see what the previous impl did with the pair<uint256, CTransactionRef>), but I'd need someone to point to where that test should live.

I like that thought. As noted above, I've verified the bug on master by amending one of our fuzz tests. On master, that test does not include default initialized pairs in the ring buffer, which is probably why that bug wasn't found so far (It would still be very rare with 6 byte short ids).

I think allowing the short id creation to be mocked (or maybe just the short id size) would be helpful to create a test. This would also generally help with getting various other short id collision edge cases under test (through unit or fuzz testing). My amended fuzz test might be a good starting point but the changes I have made to blockencodings.cpp should be configurable by a test instead of being hard-coded.

(I don't think adding a test is a blocker for this PR but perhaps a nice follow up)

A relatively simple test could be to a extra_txn.resize(1) within src/test/blockencodings_tests.cpp (currently it is empty)?

This bug description looks correct to me.

glozow

ACK e178a52

The second commit seems sensible as wtxid is cached instead of being calculated on the fly since fac1223 (nit maybe mention in the commit message), though I don't think having the pair is that bad either.

glozow · 2024-04-03T12:00:43Z

src/blockencodings.cpp

+        if (extra_txn[i] == nullptr)
+            continue;


A relatively simple test could be to a extra_txn.resize(1) within src/test/blockencodings_tests.cpp (currently it is empty)?

This bug description looks correct to me.

src/blockencodings.cpp

… of a vec of pair<Wtxid, CTransactionRef> All `CTransactionRef` have `.GetWitnessHash()` that returns a cached `const Wtxid` (since fac1223), so we don't need to pass transaction refs around with their IDs as they're easy to get from a ref.

glozow

ACK a8203e9

dergoegge

ACK a8203e9

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`.

…Transactions` covering non-empty `extra_txn` 55eea00 test: Make blockencodings_tests deterministic (AngusP) 4c99301 test: Add ReceiveWithExtraTransactions Compact Block receive test. (AngusP) 4621e7c test: refactor: Rename extra_txn to const empty_extra_txn as it is empty in all test cases (AngusP) Pull request description: 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`. ACKs for top commit: 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 Tree-SHA512: d7909c212bb069e1f6184b26390a5000dcc5f2b18e49b86cceccb9f1ec4f874dd43bc9bc92abd4207c71dd78112ba58400042c230c42e93afe55ba51b943262c

sipa · 2025-08-23T12:15:42Z

FWIW, having the wtxids in the vector directly here was intentional, to minimize pointer indirection and cache effects during compact block reconstruction.

It may be worth benchmarking to see if this didn't inadvertently introduced a performance regression.
If not, there is no point in having vExtraTxnForCompact in the first place - reconstruction can just iterate over the mempool's mapTx directly.

ajtowns · 2025-08-27T02:59:07Z

(vExtraTxnForCompact are additional txs to what's in the mempool; CTxMemPool::txns_randomized is what could be removed if there wasn't a performance regression)

b7b249d Revert "[refactor] rewrite vTxHashes as a vector of CTransactionRef" (Anthony Towns) b9300d8 Revert "refactor: Simplify `extra_txn` to be a vec of CTransactionRef instead of a vec of pair<Wtxid, CTransactionRef>" (Anthony Towns) df5a50e bench/blockencodings: add compact block reconstruction benchmark (Anthony Towns) Pull request description: Reconstructing compact blocks is on the hot path for block relay, so revert changes from #28391 and #29752 that made it slower. Also add a benchmark to validate reconstruction performance, and a comment giving some background as to the approach. ACKs for top commit: achow101: ACK b7b249d polespinasa: lgtm code review and tested ACK b7b249d cedwies: code-review ACK b7b249d davidgumberg: crACK b7b249d instagibbs: ACK b7b249d Tree-SHA512: dc266e7ac08281a5899fb1d8d0ad43eb4085f8ec42606833832800a568f4a43e3931f942d4dc53cf680af620b7e893e80c9fe9220f83894b4609184b1b3b3b42

DrahtBot added Refactoring CI failed labels Mar 27, 2024

glozow reviewed Mar 28, 2024

View reviewed changes

src/blockencodings.cpp Outdated Show resolved Hide resolved

AngusP force-pushed the typesafe-txid-in-cmpctblock branch from 58ba422 to ea8570b Compare March 28, 2024 22:29

refactor: Use typesafe Wtxid in compact block encoding message, inste…

c3c1843

…ad of ambiguous uint256. Wtxid/Txid types introduced in bitcoin#28107

AngusP force-pushed the typesafe-txid-in-cmpctblock branch from ea8570b to e178a52 Compare March 28, 2024 22:30

DrahtBot removed the CI failed label Mar 28, 2024

AngusP requested a review from glozow March 31, 2024 22:42

dergoegge approved these changes Apr 2, 2024

View reviewed changes

AngusP commented Apr 2, 2024

View reviewed changes

glozow reviewed Apr 3, 2024

View reviewed changes

AngusP force-pushed the typesafe-txid-in-cmpctblock branch from e178a52 to a8203e9 Compare April 6, 2024 18:35

glozow reviewed Apr 6, 2024

View reviewed changes

DrahtBot requested a review from dergoegge April 6, 2024 21:58

dergoegge approved these changes Apr 8, 2024

View reviewed changes

glozow merged commit bf031a5 into bitcoin:master Apr 9, 2024

AngusP deleted the typesafe-txid-in-cmpctblock branch April 9, 2024 12:47

Pttn added a commit to RiecoinTeam/Riecoin that referenced this pull request Apr 13, 2024

Merge bitcoin#29752

ce3f090

AngusP mentioned this pull request Jun 6, 2024

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

Merged

bitcoin locked and limited conversation to collaborators Apr 9, 2025

ajtowns mentioned this pull request Aug 25, 2025

Revert compact block cache inefficiencies #33253

Merged

bitcoin unlocked this conversation Aug 25, 2025

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

refactor: Use typesafe Wtxid in compact block encodings #29752

refactor: Use typesafe Wtxid in compact block encodings #29752

Uh oh!

AngusP commented Mar 27, 2024 •

edited by fanquake

Loading

Uh oh!

DrahtBot commented Mar 27, 2024 •

edited

Loading

Uh oh!

Uh oh!

dergoegge left a comment

Uh oh!

AngusP Apr 2, 2024

Uh oh!

maflcko Apr 2, 2024

Uh oh!

dergoegge Apr 3, 2024

Uh oh!

glozow Apr 3, 2024

Uh oh!

glozow left a comment

Uh oh!

glozow Apr 3, 2024

Uh oh!

Uh oh!

glozow left a comment

Uh oh!

dergoegge left a comment

Uh oh!

sipa commented Aug 23, 2025 •

edited

Loading

Uh oh!

ajtowns commented Aug 27, 2025

Uh oh!

Uh oh!

refactor: Use typesafe Wtxid in compact block encodings #29752

refactor: Use typesafe Wtxid in compact block encodings #29752

Uh oh!

Conversation

AngusP commented Mar 27, 2024 • edited by fanquake Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

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

Uh oh!

Code Coverage

Reviews

Uh oh!

Uh oh!

dergoegge left a comment

Choose a reason for hiding this comment

Uh oh!

AngusP Apr 2, 2024

Choose a reason for hiding this comment

Uh oh!

maflcko Apr 2, 2024

Choose a reason for hiding this comment

Uh oh!

dergoegge Apr 3, 2024

Choose a reason for hiding this comment

Uh oh!

glozow Apr 3, 2024

Choose a reason for hiding this comment

Uh oh!

glozow left a comment

Choose a reason for hiding this comment

Uh oh!

glozow Apr 3, 2024

Choose a reason for hiding this comment

Uh oh!

Uh oh!

glozow 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!

sipa commented Aug 23, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ajtowns commented Aug 27, 2025

Uh oh!

Uh oh!

AngusP commented Mar 27, 2024 •

edited by fanquake

Loading

DrahtBot commented Mar 27, 2024 •

edited

Loading

sipa commented Aug 23, 2025 •

edited

Loading