sparse-merkle-tree

Crates.io	sparse-merkle-tree
lib.rs	sparse-merkle-tree
version	0.6.1
source	src
created_at	2019-09-01 13:29:28.167846
updated_at	2022-11-22 10:56:40.758379
description	Sparse merkle tree implement in rust
homepage
repository	https://github.com/nervosnetwork/sparse-merkle-tree
max_upload_size
id	161335
size	633,578

Quake Wang (quake)

documentation

README

Sparse merkle tree

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