blockchain: rolling merkle root #1421
Closed
Conversation
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
39b1775 to
bd42fc6
Compare
bd42fc6 to
3a6c0e3
Compare
This commit adds an explicit assertion that the merkle root is properly computed when an odd number of leaves are present, and a left node must be hashed with itself to create a valid root.
3a6c0e3 to
c3ee68e
Compare
Roasbeef
reviewed
Oct 10, 2019
| type RollingMerkleTree struct { | ||
| // nodes contains all nodes in the tree. The nodes may correspond to | ||
| // interior nodes if their children have already been pruned. | ||
| nodes map[uint32]chainhash.Hash |
There was a problem hiding this comment.
Wouldn't this be better served as a slice? So we just index in rather than having the overhead of a map. We'd also gain memory locality for all the items as well.
| merkleStoreTree := BuildMerkleTreeStore(block.Transactions(), false) | ||
| merkleStoreRoot := merkleStoreTree[len(merkleStoreTree)-1] | ||
|
|
||
| if calcMerkleRoot != *merkleStoreRoot { |
|
@jcvernaleo (as per #1530)
|
|
@cfromknecht mind rebasing so the actions can run? |
|
Superseded by #1979 |
|
I noticed BuildMerkleTreeStore is still in the codebase even though it's replaced with RollingMerkleTree and CalcMerkleRoot. Should we remove it from blockchain/merkle.go and blockchain/merkle_test.go? |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.
This PR adds a new
RollingMerkleTreetype for efficiently computing merkle roots. The leavesof the tree are iteratively pushed onto the tree, and any complete substrees are evaluated and
stored so that subsequent pushes may consume them when their sibling tree is complete. As a
result, this requires
O(log n)additional memory be allocated. The currentBuildMerkleTreeStoreallocates an array of up to 4 times the number of leaves, which is used to store internal nodes and the root.
For 2000 leaves, the benchmarks show that this method is about 7% slower (~90 microseconds), but uses 99.04% less memory and 99.85% fewer allocations. These allocations reduce gc pressure, especially during IBD when the large slices of hashes currently used are almost immediately discarded.
alternative to #1377