Merkle mountain range

A generalized merkle mountain range implementation.

Notice this library is not stable yet, API and proof format may changes. Make sure you know what you do before using this library.

Features

Leaves accumulation
Multi leaves merkle proof
Accumulate from last leaf's merkle proof

Construct

``` txt

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 inserting 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.
the node 20 also has a left sibling 17, calculate parent node: merge(mmr[17], mmr[20]).
insert new node to next position 21.
the node 21 have no left sibling, complete the insertion.

Example MMR after insertion of a new leaf:

txt 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, we have a MMR with 3 peaks: 14, 17, 18, we bagging thses peaks from right to left to get the root: merge(merge(mmr[18], mmr[17]), mmr[14]).

Merkle proof

The merkle proof is an array of hashes constructed by the follows parts:

A merkle proof from the leaf's sibling to the peak that contains the leaf.
A hash that bagging all right-hand side peaks, skip this part if no right-hand peaks.
Hashes of all left-hand peaks, the from right to left, skip this part if no left-hand peaks.