#merkle-proof #leave #merkle-root #range #generalized #leaf #mountain

no-std polkadot-ckb-merkle-mountain-range

A generalized merkle mountain range implementation (polkadot fork)

2 unstable releases

new 0.8.0 Nov 4, 2024
0.7.0 May 23, 2024
0.6.0 May 23, 2024

#228 in Magic Beans

Download history 26857/week @ 2024-07-16 30646/week @ 2024-07-23 22499/week @ 2024-07-30 31549/week @ 2024-08-06 37347/week @ 2024-08-13 27038/week @ 2024-08-20 38019/week @ 2024-08-27 42988/week @ 2024-09-03 38412/week @ 2024-09-10 37385/week @ 2024-09-17 37343/week @ 2024-09-24 41112/week @ 2024-10-01 37733/week @ 2024-10-08 40081/week @ 2024-10-15 39329/week @ 2024-10-22 24375/week @ 2024-10-29

150,588 downloads per month
Used in 77 crates (via sp-mmr-primitives)

MIT license

90KB
2K SLoC

Merkle mountain range

Crates.io

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:

  1. insert leaf or node to next position.
  2. 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:

  1. insert leaf to next position: 19.
  2. now check the left sibling 18 and calculate parent node: merge(mmr[18], mmr[19]).
  3. insert parent node to position 20.
  4. since the node 20 also has a left sibling 17, calculate parent node: merge(mmr[17], mmr[20]).
  5. insert new node to next position 21.
  6. 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:

  1. A merkle proof from the leaf's sibling to the peak that contains the leaf.
  2. A hash that bags all right-hand side peaks, skip this part if no right-hand peaks.
  3. 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