Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Cached Merkle Trees #35

Closed
DanieleDiBenedetto opened this issue Mar 31, 2020 · 1 comment · Fixed by #69
Closed

Cached Merkle Trees #35

DanieleDiBenedetto opened this issue Mar 31, 2020 · 1 comment · Fixed by #69
Labels
new feature optimization Performance improvement for the current codebase sw design SW design choice to be made or implemented

Comments

@DanieleDiBenedetto
Copy link
Collaborator

In the actual Merkle Tree implementation a minimum number of leaves/nodes is actually generated to create a tree of height MIN_HEIGHT with respect to the one you would expect by setting the HEIGHT parameter in MerkleTreeConfig.
This is obviously done for efficiency reason, but: padding nodes are added only between MIN_HEIGHT and HEIGHT , therefore you won't actually have 2^(HEIGHT - 1) leaves: this means that if you want to create a Merkle Proof starting from a specific padding leaf, or reconstruct the Merkle Root starting from all the leaves, you can't;
Of course if we want to keep this implementation the most immediate solution would be to explicitly pass all the leaves according to the desired HEIGHT and keep everything in memory.
But, if a given subtree has all or some of the leaves all to null, sure there is a smarter way to quickly and efficiently compute the root of that tree via pre-computation and caching:
it is worth to investigate this and implement optimizations in order to efficiently compute and represent a "full" Merkle Tree and not a "virtually full" like the actual one.

@DanieleDiBenedetto DanieleDiBenedetto added optimization Performance improvement for the current codebase sw design SW design choice to be made or implemented labels Mar 31, 2020
@DanieleDiBenedetto DanieleDiBenedetto linked a pull request Aug 28, 2020 that will close this issue
@DanieleDiBenedetto
Copy link
Collaborator Author

DanieleDiBenedetto commented Jul 7, 2021

Closed with #69.
We have now a FieldBasedOptimizedMHT, suitable for small sized Merkle Trees, exploiting batch hash and precomputed node values to boost the performances.
For bigger Merkle Trees we have introduced Sparse Merkle Trees using DB as a support and using lazy root computation to speed up performances where needed. This last one is still WIP and tracked in issue #75

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
new feature optimization Performance improvement for the current codebase sw design SW design choice to be made or implemented
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant