Fix merkle proof calculation with proper coinbase replacement#993
Merged
Conversation
Contributor
|
🤖 Claude Code Review Status: Complete SummaryThis PR correctly fixes merkle proof generation to mirror
The implementation aligns with BRC-74 and ensures proofs are verifiable by reference implementations. Issues Found[Minor] ConstructSubtreeMerkleProof doesn't apply the same coinbase/padding transformations as ConstructMerkleProof — see comment below for details. Overall this is a solid fix with excellent test coverage. The one minor issue doesn't affect the main use case (transaction proofs) that this PR addresses. |
Contributor
|
[Minor] Missing coinbase/padding transformations in subtree-level proofs ConstructSubtreeMerkleProof (merkle_proof.go:388) uses raw block.Subtrees hashes without the coinbase replacement and final-subtree padding that ConstructMerkleProof applies (lines 225-241). This inconsistency means subtree-level proofs won't verify against the block header merkle root for blocks with coinbase placeholders or incomplete final subtrees. Recommendation: Apply the same firstRoot/lastRoot logic, or document why subtree-level proofs are exempt. |
|
Contributor
Benchmark Comparison ReportBaseline: Current: Summary
All benchmark results (sec/op)
Threshold: >10% with p < 0.05 | Generated: 2026-05-30 02:49 UTC |
oskarszoon
approved these changes
May 31, 2026
oskarszoon
left a comment
Contributor
There was a problem hiding this comment.
Approve. All three defects from #992 plus the incomplete-final-subtree lift are fixed, and the proof path now mirrors CheckMerkleRoot — verified via go-bc CalculateRootGivenTxid across coinbase, first-subtree (idx 1 & 2), multi-subtree, and incomplete-final cases (incl. a brute-force sweep of all positions in a 4-subtree block; all reconstruct the header root, no placeholder leaks). The coinbase-replaced subtree clone is a genuine deep copy, so the cached subtree isn't mutated; offset/bit math checks out; build + tests green. Good call building the test subtrees with the real CoinbasePlaceholderHashValue — that's the exact gap the old tests had.
One fast-follow, not blocking this PR: ConstructSubtreeMerkleProof (merkle_proof.go:388) still builds from raw block.Subtrees without the coinbase-replace/lift, so subtree-inclusion proofs — the GetMerkleProof fallback when the queried hash is a subtree root rather than a txid — stay invalid for first-subtree / incomplete-final blocks. Same bug class, different entry point, currently untested. Worth the same fix + a go-bc crosscheck before GET /api/v1/merkle_proof/{subtreeHash} is relied on.
ordishs
approved these changes
Jun 2, 2026
ordishs
left a comment
Collaborator
There was a problem hiding this comment.
Approve — careful, well-reasoned correctness fix backed by go-bc reference cross-checks.
Verified locally:
go test ./util/bump/... ./util/merkleproof/...passes;go vetclean.- Proof construction faithfully mirrors
model.Block.CheckMerkleRoot(coinbase replacement for subtree 0, lift only the incomplete final subtree, top tree over effective roots). - Traced the global-offset model through a non-power-of-2 subtree count with an incomplete final subtree — offsets, top-level odd-duplication, and lift levels all reconstruct the same root, confirmed end-to-end via the go-bc parser in the new cross-check test.
Duplicate()deep-copies Nodes, so the clone-and-replace path does not mutate the cached subtree.
The bugs fixed are real: multi-subtree BUMP proofs were previously unverifiable. Test coverage is strong (odd-index/flag bug, coinbase tx, multi-subtree, incomplete final subtree, placeholder-exclusion assertion).
Non-blocking follow-ups:
- BUMP emits self-duplicate/lift siblings as FlagData with explicit hash rather than FlagDuplicate (0x01). Reconstructs correctly in go-bc but is non-canonical vs BRC-74 and larger; a brief comment documenting the deliberate go-bc-compatibility tradeoff would help future readers.
- ConstructMerkleProof assumes (rather than re-checks) the power-of-two/single-incomplete-final invariants that CheckMerkleRoot enforces; a defense-in-depth guard would be cheap insurance.
- Minor extra I/O per proof (first/last subtree fetches) — acceptable.
freemans13
added a commit
to freemans13/teranode
that referenced
this pull request
Jun 2, 2026
…tegration Merge stu/blockvalidation-inmemory-checkold (ca7ef31) — off-chain prefetch for checkOldBlockIDs plus the upstream/main it carried (bsv-blockchain#1005, bsv-blockchain#993, bsv-blockchain#1022). Conflict resolutions: - services/legacy/netsync/manager.go: kept integration's gap-watchdog self-heal (requestBlocksFromTip / maybeResyncOnMissingParent / missingParentResyncInterval); the incoming side had no content there. - stores/utxo/aerospike/batch_create.go: pass nil for the new GetBinsToStore arena param (main added *bt.Arena; integration-only BatchCreate caller predates it). nil = non-arena route, output-equivalent per create_arena_test.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Fixes #992
This pull request significantly improves the correctness and robustness of Merkle proof generation and BUMP encoding, especially around coinbase transaction handling and subtree padding. It ensures that proofs are compatible with the go-bc reference implementation and conform to BRC-74 by treating the block's Merkle tree as a single flat structure, correctly handling global offsets, and mirroring all block header calculations (including coinbase placeholder replacement and subtree padding). The changes also introduce comprehensive end-to-end regression tests to prevent future regressions.
Key changes include:
Correctness of Merkle Proof Construction and BUMP Encoding
ConvertToBUMPinformat.goto compute and use global transaction offsets (not subtree-local), ensuring BUMP proofs are valid for blocks with multiple subtrees and compatible with go-bc. Sibling offsets at each level are now calculated using the transaction's global leaf offset.format_test.goto match the new global offset logic, ensuring tests verify the correct BUMP structure and offsets.Coinbase Placeholder and Subtree Padding Handling
merkle_proof.go, added logic to detect and replace the coinbase placeholder in the first subtree with the actual coinbase txid, mirroring block header calculation. Also, implemented logic to pad the final subtree if incomplete, ensuring the Merkle root matches the block header. [1] [2]Proof Flags and Offset Calculation
Testing and Regression Coverage
coinbase_placeholder_crosscheck_test.gothat covers coinbase placeholder replacement, subtree padding, and BUMP verification with go-bc, preventing regressions for these critical cases.Minor Improvements
math/bitsinmerkle_proof.gofor efficient bit operations when calculating subtree heights and offsets.