Ran
|
Files
0
|
Run time
0s
|
Badge
Embed ▾
README BADGES
|
push
github
feat: sparse merkle trees (#5457) # Sparse Merkle trees ## Description A sparse Merkle tree is a Merkle tree where the non-empty nodes are stored in a map with the key being the hash of the node and the value being the node itself. Merkle trees are a mutable Merkle-ish tree structure, that supports full CRUD operations. ### Todo in this PR * [x] Insert new values * [x] Update existing values * [x] Delete values * [x] Inclusion proofs * [x] exclusion proofs. * [x] Benchmarks This implementation assumed that there is a key-value store elsewhere. Only the tree hashes themselves are handled in this data structure. When constructing a new tree, a hashing algorithm is specified. This is used to hash the non-leaf nodes. The "values" provided to the tree must already be a hash, and should have been generated from a different hashing algorithm to the one driving the tree, in order to prevent second pre-image attacks. ## Motivation and Context tl;dr: * Bandwidth savings * Scalability benefits * Privacy benefits * Compact inclusion _and_ exclusion proofs! ### Details The SMT implementation is faster than `MutableMMR` up to around 10,000 nodes, and then the average depth starts to affect it. By 1,000,000 nodes, it is significantly slower than MMR. This makes sense since MMR is basically O(1) for inserts, while SMT is O(log(n)). You can see some results here: ```text Starting: SMT: Inserting 1000000 keys Finished: SMT: Inserting 1000000 keys - 1.921310493s Starting: SMT: Calculating root hash Tree size: 1000000. Root hash: 3e42ca40db120bc3c882fc29bf05dc1d7 Finished: SMT: Calculating root hash - 644.226062ms Starting: SMT: Deleting 500000 keys Finished: SMT: Deleting 500000 keys - 863.873761ms Starting: SMT: Calculating root hash Tree size: 500000. Root hash: 2a7b51f11160a5eab0d90f89a3bcf09f8 Finished: SMT: Calculating root hash ... (continued)
0 of 0 relevant lines covered (NaN%)
0.0 hits per line
Coverage | ∆ | File | Lines | Relevant | Covered | Missed | Hits/Line |
---|