2 unstable releases
new 0.8.0 | Nov 4, 2024 |
---|---|
0.7.0 | May 23, 2024 |
0.6.0 |
|
#228 in Magic Beans
150,588 downloads per month
Used in 77 crates
(via sp-mmr-primitives)
90KB
2K
SLoC
Merkle mountain range
A generalized merkle mountain range implementation.
Features
- Leaves accumulation
- Multi leaves merkle proof
- Accumulate from last leaf's merkle proof
Construct
# An 11 leaves MMR
14
/ \
6 13
/ \ / \
2 5 9 12 17
/ \ / \ / \ / \ / \
0 1 3 4 7 8 10 11 15 16 18
In MMR, we use the insertion order to reference leaves and nodes.
We insert a new leaf to MMR by the following:
- insert leaf or node to next position.
- if the current position has a left sibling, we merge the left and right nodes to produce a new parent node, then go back to step 1 to insert the node.
For example, we insert a leaf to the example MMR:
- insert leaf to next position:
19
. - now check the left sibling
18
and calculate parent node:merge(mmr[18], mmr[19])
. - insert parent node to position
20
. - since the node
20
also has a left sibling17
, calculate parent node:merge(mmr[17], mmr[20])
. - insert new node to next position
21
. - since the node
21
have no left sibling, complete the insertion.
Example MMR after insertion of a new leaf:
14
/ \
6 13 21
/ \ / \ / \
2 5 9 12 17 20
/ \ / \ / \ / \ / \ / \
0 1 3 4 7 8 10 11 15 16 18 19
Merkle root
An MMR is constructed by one or more sub merkle trees (or mountains). Each sub merkle tree's root is a peak in MMR, we calculate the MMR root by bagging these peaks from right to left.
For example, in the 11 leaf MMR we have 3 peaks: 14, 17, 18
, we bag these peaks from right to left to get the root: merge(mmr[14], merge(mmr[17], mmr[18]))
.
Merkle proof
The merkle proof is an array of hashes constructed with the following parts:
- A merkle proof from the leaf's sibling to the peak that contains the leaf.
- A hash that bags all right-hand side peaks, skip this part if no right-hand peaks.
- Hashes of all left-hand peaks from right to left, skip this part if no left-hand peaks.
We can reconstruct the merkle root from the proofs. Pre-calculating the peak positions from the size of MMR may help us do the bagging.
References
Dependencies
~430KB