9 releases
0.6.1  Nov 22, 2022 

0.5.4  Sep 27, 2022 
0.5.3  Nov 15, 2021 
0.5.2rc1  Jul 25, 2021 
0.1.0alpha2 

#139 in Data structures
3,434 downloads per month
Used in 14 crates
(via ckbsdk)
270KB
7K
SLoC
Sparse merkle tree
An optimized sparse merkle tree.
size  proof size  update  get  merkle proof  verify proof 

2n + log(n)  log(n)  log(n)  log(n)  log(n)  log(n) 
Features:
 Multileaves existence / nonexistence merkle proof
 Customizable hash function
 Storage backend agnostic
 Rust
no_std
support
This article describes algorithm of this data structure An optimized compacted sparse merkle tree
Construction
A sparse merkle tree is a perfectly balanced tree contains 2 ^ N
leaves:
# N = 256 sparse merkle tree
height:
0
/ \
255 0 1
.............................
/ \ / \
1 0 1 0 1
/ \ / \ / \ / \
0 0 1 0 1 ... 0 1 0 1
0x00..00 0x00..01 ... 0x11..11
The above graph demonstrates a sparse merkle tree with 2 ^ 256
leaves, which can mapping every possible H256
value into leaves. The height of the tree is 256
, from top to bottom, we denote 0
for each left branch and denote 1
for each right branch, so we can get a 256 bits path, which also can represent in H256
, we use the path as the key of leaves, the most left leaf's key is 0x00..00
, and the next key is 0x00..01
, the most right key is 0x11..11
.
License
MIT
Dependencies
~210KB