Skip to content

fix(model): reject duplicate subtree roots in top-level merkle tree#761

Merged
ordishs merged 3 commits into
bsv-blockchain:mainfrom
ordishs:security/4593-merkle-top-dup-guard
May 12, 2026
Merged

fix(model): reject duplicate subtree roots in top-level merkle tree#761
ordishs merged 3 commits into
bsv-blockchain:mainfrom
ordishs:security/4593-merkle-top-dup-guard

Conversation

@ordishs

@ordishs ordishs commented Apr 28, 2026

Copy link
Copy Markdown
Collaborator

Closes #4593.

Summary

Defense-in-depth: Block.CheckMerkleRoot builds a top-level merkle tree from subtree-root hashes without an explicit duplicate-hash guard. Duplicates at this layer would indicate a bug elsewhere (per-tx duplicates are caught upstream), but the missing guard means a malformed block passing earlier checks could still produce a coincidentally-valid merkle root. The audit (#4593) flagged this as a hardening gap with no current consensus impact.

Fix

Add an O(n) map[chainhash.Hash]struct{} dedup pass folded into the existing AddNode loop. On any collision, return BlockInvalidError before continuing tree construction.

Test plan

  • Regression test in model/Block_test.go constructs a block with two subtrees sharing the same root hash; asserts CheckMerkleRoot returns BlockInvalidError and the message identifies the colliding hash.
  • go test -race ./model/... passes (no regression in existing CheckMerkleRoot tests).

@github-actions

github-actions Bot commented Apr 28, 2026 •
edited
Loading

Copy link
Copy Markdown
Contributor

🤖 Claude Code Review

Status: Complete

Current Review:

This PR adds defense-in-depth validation to CheckMerkleRoot by rejecting duplicate subtree root hashes before building the top-level merkle tree. The implementation is sound:

✅ Implementation Quality:

  • O(n) dedup check folded into existing loop (lines 1338-1350)
  • Correct error type (BlockInvalidError) with clear diagnostic message
  • Efficient map-based collision detection with pre-sized allocation
  • No performance regression risk for valid blocks

✅ Test Coverage:

  • Regression test explicitly constructs colliding subtree roots using RootHashWithReplaceRootNode
  • Validates error type and message content
  • Test setup properly verifies hash collision before exercising the guard

✅ Context Verification:

  • Per-transaction duplicates are caught upstream by checkDuplicateTransactions (model/Block.go:596-658)
  • This guard catches subtree-level collisions, which would indicate a bug elsewhere but could theoretically produce coincidentally-valid merkle roots
  • Aligns with defense-in-depth principle from CVE-2012-2459 guard pattern in the codebase

No issues found. The fix appropriately closes the hardening gap identified in the audit without introducing side effects.

@github-actions

github-actions Bot commented Apr 28, 2026 •
edited
Loading

Copy link
Copy Markdown
Contributor

Benchmark Comparison Report

Baseline: main (unknown)

Current: PR-761 (88dff72)

Summary

  • Regressions: 0
  • Improvements: 0
  • Unchanged: 142
  • Significance level: p < 0.05
All benchmark results (sec/op)
Benchmark Baseline Current Change p-value
_NewBlockFromBytes-4 1.550µ 1.792µ ~ 0.200
SplitSyncedParentMap_SetIfNotExists/256_buckets-4 71.39n 71.24n ~ 0.700
SplitSyncedParentMap_SetIfNotExists/16_buckets-4 71.34n 71.01n ~ 0.200
SplitSyncedParentMap_SetIfNotExists/1_bucket-4 71.47n 71.33n ~ 0.400
SplitSyncedParentMap_ConcurrentSetIfNotExists/256_buckets... 32.84n 32.64n ~ 1.000
SplitSyncedParentMap_ConcurrentSetIfNotExists/16_buckets_... 56.15n 55.12n ~ 0.700
SplitSyncedParentMap_ConcurrentSetIfNotExists/1_bucket_pa... 126.3n 129.7n ~ 1.000
MiningCandidate_Stringify_Short-4 219.0n 217.3n ~ 1.000
MiningCandidate_Stringify_Long-4 1.663µ 1.644µ ~ 0.200
MiningSolution_Stringify-4 854.0n 853.2n ~ 1.000
BlockInfo_MarshalJSON-4 1.734µ 1.721µ ~ 0.100
NewFromBytes-4 132.5n 133.6n ~ 0.100
Mine_EasyDifficulty-4 60.60µ 60.81µ ~ 0.700
Mine_WithAddress-4 6.745µ 6.883µ ~ 0.100
BlockAssembler_AddTx-4 0.02860n 0.03036n ~ 0.400
AddNode-4 11.05 10.66 ~ 0.400
AddNodeWithMap-4 11.14 10.87 ~ 0.700
DirectSubtreeAdd/4_per_subtree-4 63.58n 61.55n ~ 1.000
DirectSubtreeAdd/64_per_subtree-4 31.56n 32.01n ~ 0.100
DirectSubtreeAdd/256_per_subtree-4 30.30n 30.62n ~ 0.100
DirectSubtreeAdd/1024_per_subtree-4 29.20n 29.45n ~ 0.700
DirectSubtreeAdd/2048_per_subtree-4 28.62n 28.85n ~ 0.100
SubtreeProcessorAdd/4_per_subtree-4 279.3n 283.2n ~ 0.400
SubtreeProcessorAdd/64_per_subtree-4 277.0n 276.5n ~ 1.000
SubtreeProcessorAdd/256_per_subtree-4 278.5n 277.3n ~ 1.000
SubtreeProcessorAdd/1024_per_subtree-4 270.0n 268.9n ~ 0.700
SubtreeProcessorAdd/2048_per_subtree-4 270.8n 269.1n ~ 0.100
SubtreeProcessorRotate/4_per_subtree-4 273.2n 272.9n ~ 1.000
SubtreeProcessorRotate/64_per_subtree-4 273.4n 276.0n ~ 0.400
SubtreeProcessorRotate/256_per_subtree-4 273.9n 271.6n ~ 0.700
SubtreeProcessorRotate/1024_per_subtree-4 273.0n 272.5n ~ 0.300
SubtreeNodeAddOnly/4_per_subtree-4 54.28n 54.45n ~ 1.000
SubtreeNodeAddOnly/64_per_subtree-4 34.47n 34.29n ~ 0.400
SubtreeNodeAddOnly/256_per_subtree-4 33.63n 33.27n ~ 0.100
SubtreeNodeAddOnly/1024_per_subtree-4 32.80n 32.61n ~ 0.100
SubtreeCreationOnly/4_per_subtree-4 112.7n 111.8n ~ 0.700
SubtreeCreationOnly/64_per_subtree-4 401.7n 403.5n ~ 0.200
SubtreeCreationOnly/256_per_subtree-4 1.359µ 1.453µ ~ 0.100
SubtreeCreationOnly/1024_per_subtree-4 4.332µ 4.424µ ~ 0.100
SubtreeCreationOnly/2048_per_subtree-4 8.141µ 8.254µ ~ 0.100
SubtreeProcessorOverheadBreakdown/64_per_subtree-4 268.3n 272.5n ~ 0.400
SubtreeProcessorOverheadBreakdown/1024_per_subtree-4 269.3n 272.9n ~ 0.100
ParallelGetAndSetIfNotExists/1k_nodes-4 589.4µ 821.2µ ~ 0.100
ParallelGetAndSetIfNotExists/10k_nodes-4 1.323m 1.597m ~ 0.100
ParallelGetAndSetIfNotExists/50k_nodes-4 6.669m 6.710m ~ 0.100
ParallelGetAndSetIfNotExists/100k_nodes-4 13.33m 13.29m ~ 0.400
SequentialGetAndSetIfNotExists/1k_nodes-4 658.1µ 660.5µ ~ 0.200
SequentialGetAndSetIfNotExists/10k_nodes-4 2.791m 2.771m ~ 1.000
SequentialGetAndSetIfNotExists/50k_nodes-4 10.49m 10.40m ~ 1.000
SequentialGetAndSetIfNotExists/100k_nodes-4 20.16m 20.28m ~ 0.100
ProcessOwnBlockSubtreeNodesParallel/1k_nodes-4 630.1µ 641.4µ ~ 0.400
ProcessOwnBlockSubtreeNodesParallel/10k_nodes-4 4.202m 4.211m ~ 0.700
ProcessOwnBlockSubtreeNodesParallel/100k_nodes-4 16.55m 16.77m ~ 0.100
ProcessOwnBlockSubtreeNodesSequential/1k_nodes-4 691.6µ 697.2µ ~ 0.100
ProcessOwnBlockSubtreeNodesSequential/10k_nodes-4 5.816m 5.746m ~ 0.200
ProcessOwnBlockSubtreeNodesSequential/100k_nodes-4 37.69m 37.70m ~ 0.700
DiskTxMap_SetIfNotExists-4 3.811µ 3.885µ ~ 0.700
DiskTxMap_SetIfNotExists_Parallel-4 3.589µ 3.662µ ~ 0.400
DiskTxMap_ExistenceOnly-4 323.6n 347.9n ~ 0.100
Queue-4 196.6n 198.0n ~ 0.400
AtomicPointer-4 3.625n 3.811n ~ 0.700
ReorgOptimizations/DedupFilterPipeline/Old/10K-4 869.4µ 835.7µ ~ 0.100
ReorgOptimizations/DedupFilterPipeline/New/10K-4 853.3µ 819.2µ ~ 0.100
ReorgOptimizations/AllMarkFalse/Old/10K-4 110.8µ 115.1µ ~ 0.200
ReorgOptimizations/AllMarkFalse/New/10K-4 64.27µ 64.12µ ~ 0.400
ReorgOptimizations/HashSlicePool/Old/10K-4 65.05µ 60.33µ ~ 0.700
ReorgOptimizations/HashSlicePool/New/10K-4 11.08µ 11.06µ ~ 1.000
ReorgOptimizations/NodeFlags/Old/10K-4 5.153µ 5.094µ ~ 0.400
ReorgOptimizations/NodeFlags/New/10K-4 1.739µ 1.870µ ~ 0.200
ReorgOptimizations/DedupFilterPipeline/Old/100K-4 9.554m 10.109m ~ 0.400
ReorgOptimizations/DedupFilterPipeline/New/100K-4 9.439m 10.020m ~ 0.100
ReorgOptimizations/AllMarkFalse/Old/100K-4 1.164m 1.119m ~ 0.200
ReorgOptimizations/AllMarkFalse/New/100K-4 705.2µ 707.3µ ~ 0.700
ReorgOptimizations/HashSlicePool/Old/100K-4 603.5µ 580.5µ ~ 0.100
ReorgOptimizations/HashSlicePool/New/100K-4 194.7µ 197.0µ ~ 0.400
ReorgOptimizations/NodeFlags/Old/100K-4 55.23µ 54.02µ ~ 0.700
ReorgOptimizations/NodeFlags/New/100K-4 18.77µ 18.98µ ~ 1.000
TxMapSetIfNotExists-4 46.29n 46.83n ~ 0.100
TxMapSetIfNotExistsDuplicate-4 38.92n 38.74n ~ 0.200
ChannelSendReceive-4 577.8n 596.8n ~ 0.100
CalcBlockWork-4 528.0n 528.1n ~ 1.000
CalculateWork-4 717.1n 721.7n ~ 1.000
BuildBlockLocatorString_Helpers/Size_10-4 1.351µ 1.351µ ~ 1.000
BuildBlockLocatorString_Helpers/Size_100-4 15.72µ 14.41µ ~ 1.000
BuildBlockLocatorString_Helpers/Size_1000-4 126.1µ 126.8µ ~ 0.200
CatchupWithHeaderCache-4 104.4m 104.6m ~ 0.200
SubtreeSizes/10k_tx_4_per_subtree-4 1.373m 1.373m ~ 1.000
SubtreeSizes/10k_tx_16_per_subtree-4 329.8µ 325.7µ ~ 0.400
SubtreeSizes/10k_tx_64_per_subtree-4 77.09µ 77.05µ ~ 0.700
SubtreeSizes/10k_tx_256_per_subtree-4 19.55µ 19.19µ ~ 0.100
SubtreeSizes/10k_tx_512_per_subtree-4 9.652µ 9.616µ ~ 0.400
SubtreeSizes/10k_tx_1024_per_subtree-4 4.818µ 4.706µ ~ 0.200
SubtreeSizes/10k_tx_2k_per_subtree-4 2.414µ 2.384µ ~ 0.400
BlockSizeScaling/10k_tx_64_per_subtree-4 76.68µ 75.14µ ~ 0.200
BlockSizeScaling/10k_tx_256_per_subtree-4 19.32µ 18.89µ ~ 0.100
BlockSizeScaling/10k_tx_1024_per_subtree-4 4.788µ 4.679µ ~ 0.200
BlockSizeScaling/50k_tx_64_per_subtree-4 406.0µ 393.7µ ~ 0.200
BlockSizeScaling/50k_tx_256_per_subtree-4 97.04µ 94.85µ ~ 0.100
BlockSizeScaling/50k_tx_1024_per_subtree-4 23.63µ 23.27µ ~ 0.400
SubtreeAllocations/small_subtrees_exists_check-4 159.6µ 160.0µ ~ 1.000
SubtreeAllocations/small_subtrees_data_fetch-4 171.0µ 170.4µ ~ 1.000
SubtreeAllocations/small_subtrees_full_validation-4 334.7µ 328.4µ ~ 0.100
SubtreeAllocations/medium_subtrees_exists_check-4 9.285µ 9.677µ ~ 0.200
SubtreeAllocations/medium_subtrees_data_fetch-4 10.02µ 10.18µ ~ 0.100
SubtreeAllocations/medium_subtrees_full_validation-4 19.36µ 19.16µ ~ 0.200
SubtreeAllocations/large_subtrees_exists_check-4 2.230µ 2.312µ ~ 0.100
SubtreeAllocations/large_subtrees_data_fetch-4 2.455µ 2.463µ ~ 0.700
SubtreeAllocations/large_subtrees_full_validation-4 4.874µ 4.829µ ~ 0.100
_BufferPoolAllocation/16KB-4 3.829µ 3.416µ ~ 0.200
_BufferPoolAllocation/32KB-4 8.847µ 9.540µ ~ 0.400
_BufferPoolAllocation/64KB-4 16.95µ 16.73µ ~ 0.200
_BufferPoolAllocation/128KB-4 32.53µ 32.28µ ~ 0.700
_BufferPoolAllocation/512KB-4 125.5µ 108.6µ ~ 0.100
_BufferPoolConcurrent/32KB-4 18.37µ 17.34µ ~ 0.100
_BufferPoolConcurrent/64KB-4 28.96µ 27.37µ ~ 0.100
_BufferPoolConcurrent/512KB-4 146.3µ 145.7µ ~ 0.400
_SubtreeDeserializationWithBufferSizes/16KB-4 675.1µ 646.4µ ~ 0.100
_SubtreeDeserializationWithBufferSizes/32KB-4 665.2µ 640.0µ ~ 0.100
_SubtreeDeserializationWithBufferSizes/64KB-4 670.3µ 632.4µ ~ 0.100
_SubtreeDeserializationWithBufferSizes/128KB-4 670.1µ 621.0µ ~ 0.100
_SubtreeDeserializationWithBufferSizes/512KB-4 679.3µ 633.9µ ~ 0.100
_SubtreeDataDeserializationWithBufferSizes/16KB-4 36.41m 36.98m ~ 0.100
_SubtreeDataDeserializationWithBufferSizes/32KB-4 36.05m 36.55m ~ 0.100
_SubtreeDataDeserializationWithBufferSizes/64KB-4 35.46m 36.34m ~ 0.200
_SubtreeDataDeserializationWithBufferSizes/128KB-4 35.20m 36.23m ~ 0.100
_SubtreeDataDeserializationWithBufferSizes/512KB-4 35.32m 35.96m ~ 0.400
_PooledVsNonPooled/Pooled-4 832.0n 832.2n ~ 1.000
_PooledVsNonPooled/NonPooled-4 7.081µ 7.449µ ~ 0.400
_MemoryFootprint/Current_512KB_32concurrent-4 7.620µ 8.034µ ~ 0.100
_MemoryFootprint/Proposed_32KB_32concurrent-4 10.68µ 10.13µ ~ 0.100
_MemoryFootprint/Alternative_64KB_32concurrent-4 10.914µ 9.895µ ~ 0.100
_prepareTxsPerLevel-4 404.0m 411.1m ~ 1.000
_prepareTxsPerLevelOrdered-4 3.975m 4.110m ~ 0.700
_prepareTxsPerLevel_Comparison/Original-4 418.7m 419.3m ~ 1.000
_prepareTxsPerLevel_Comparison/Optimized-4 3.691m 3.669m ~ 0.400
StoreBlock_Sequential/BelowCSVHeight-4 335.5µ 335.1µ ~ 1.000
StoreBlock_Sequential/AboveCSVHeight-4 346.2µ 335.8µ ~ 0.200
GetUtxoHashes-4 259.1n 260.6n ~ 1.000
GetUtxoHashes_ManyOutputs-4 48.22µ 45.70µ ~ 0.100
_NewMetaDataFromBytes-4 238.4n 239.9n ~ 0.200
_Bytes-4 635.1n 633.2n ~ 1.000
_MetaBytes-4 588.0n 571.2n ~ 0.100

Threshold: >10% with p < 0.05 | Generated: 2026-05-12 08:24 UTC

@ordishs ordishs requested review from freemans13 and icellan and removed request for icellan May 12, 2026 08:10
@ordishs ordishs enabled auto-merge (squash) May 12, 2026 08:11
@ordishs ordishs merged commit 7fb7d89 into bsv-blockchain:main May 12, 2026
24 checks passed
@sonarqubecloud

sonarqubecloud Bot commented May 12, 2026

Copy link
Copy Markdown

Quality Gate Passed Quality Gate passed

Issues
0 New issues
0 Accepted issues

Measures
0 Security Hotspots
100.0% Coverage on New Code
0.0% Duplication on New Code

See analysis details on SonarQube Cloud

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@icellan icellan icellan approved these changes

@freemans13 freemans13 freemans13 approved these changes

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@ordishs @icellan @freemans13