9 unstable releases (4 breaking)
0.17.0pre 


0.5.2  Oct 20, 2022 
0.5.1  Sep 6, 2022 
0.4.0  May 30, 2022 
0.1.0  Sep 20, 2019 
#46 in Cryptography
40,727 downloads per month
Used in 58 crates
(10 directly)
48KB
1K
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 righthand side peaks, skip this part if no righthand peaks.
 Hashes of all lefthand peaks from right to left, skip this part if no lefthand peaks.
We can reconstruct the merkle root from the proofs. Precalculating the peak positions from the size of MMR may help us do the bagging.