Merkle Mountain Range

This crate is part of the Tari Cryptocurrency project.

The Merkle mountain range was invented by Peter Todd. More about them can be read here and here

A Merkle mountain range(MMR) is a binary tree where each parent is the concatenated hash of its two children. The leaves at the bottom of the MMR is the hashes of the data. The MMR allows easy to add and proof of existence inside of the tree. MMR always tries to have the largest possible single binary tree, so in effect it is possible to have more than one binary tree. Every time you have to get the merkle root (the single merkle proof of the whole MMR) you have the bag the peaks of the individual trees, or mountain peaks.

lib.rs:

Merkle Mountain Ranges

Introduction

The Merkle mountain range was invented by Peter Todd. More detalis can be read at Open Timestamps and the Grin project.

A Merkle mountain range (MMR) is a binary tree where each parent is the concatenated hash of its two children. The leaves at the bottom of the MMR are the hashes of the data. The MMR makes it easy to add to, and prove existence inside of the tree. MMR always tries to have the largest possible single binary tree, so in effect it is possible to have more than one binary tree. Every time you have to get the merkle root (the single merkle proof of the whole MMR) you have to bag the peaks of the individual trees, or mountain peaks.

Lets take an example of how to construct one. Say you have the following MMR already made:

      /\
     /  \
    /\  /\   /\
   /\/\/\/\ /\/\ /\

From this we can see we have 3 trees or mountains. We have constructed the largest possible trees we can. If we want to calculate the merkle root we simply concatenate and then hash the three peaks.

Lets continue the example, by adding a single object. Our MMR now looks as follows

      /\
     /  \
    /\  /\   /\
   /\/\/\/\ /\/\ /\ /

We now have 4 mountains. Calculating the root means hashing the concatenation of the (now) four peaks.

Lets continue thw example, by adding a single object. Our MMR now looks as follows

          /\
         /  \
        /    \
       /      \
      /\      /\
     /  \    /  \
    /\  /\  /\  /\
   /\/\/\/\/\/\/\/\

Now we only have a single binary tree, and the root is now the hash of the single peak's hash. This process continues as you add more objects to the MMR.

                /\
               /  \
              /    \
             /      \
            /        \
           /          \
          /            \
         /\             \
        /\ \            /\
       /  \ \          /  \
      /\   \ \        /\   \
     /  \   \ \      /  \   \
    /\  /\  /\ \    /\  /\  /\
   /\/\/\/\/\/\/\  /\/\/\/\/\/\

Due to the unique way the MMR is constructed we can easily represent the MMR as a linear list of the nodes. Let's take the following MMR and number the nodes in the order we create them.

        6
      /  \
     /    \
    2      5
   / \    / \
  0   1  3   4

Looking above at the example of when you create the nodes, you will see the MMR nodes will have been created in the order as they are named. This means we can easily represent them as a list: Height: 0 | 0 | 1 | 0 | 0 | 1 | 2 Node: 0 | 1 | 2 | 3 | 4 | 5 | 6

Because of the list nature of the MMR we can easily navigate around the MMR using the following formulas:

Jump to right sibling : $$ n + 2^{H+1} - 1 $$ Jump to left sibling : $$ n - 2^{H+1} - 1 $$ peak of binary tree : $$ 2^{ H+1 } - 2 $$ left down : $$ n - 2^H $$ right down: $$ n-1 $$

Node numbering

There can be some confusion about how nodes are numbered in an MMR. The following conventions are used in this crate:

• All indices are numbered starting from zero.
• MMR nodes refer to all the nodes in the Merkle Mountain Range and are ordered in the canonical mmr ordering described above.
• Leaf nodes are numbered counting from zero and increment by one each time a leaf is added.

To illustrate, consider this MMR:

           14
         /     \
        /       \
       6        13          21          <-- MMR indices
     /  \      /  \        /  \
    /    \    /    \      /    \
    2    5    9    12    17    20
   / \  / \  / \  / \   / \   / \
   0 1  3 4  7 8 10 11 15 16 18 19 22
   ----------------------------------
   0 1  2 3  4 5  6  7  8  9 10 11 12  <-- Leaf node indices
   ----------------------------------