/sparse-merkle-tree

Primary LanguageRust

Sparse merkle tree

This is a fork from Nervos, but we replaced the working mode of the hash function blake2b

Crates.io Docs

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:

  • Multi-leaves existence / non-existence 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

Environment Setup

$ rustc --version
rustc 1.63.0 (4b91a6ea7 2022-08-08)
$ cargo --version
cargo 1.63.0 (fd9c4297c 2022-07-01)

$ cargo build
$ cargo test