Crate geen

Gene: Over the Mountains

• MMR
• Dynamic Accumulator

Merkle Mountain Ranges

Introduction

The Merkle mountain range was invented by Peter Todd more about them 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 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.

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 tree's 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. Lets 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:

//! ```plaintext 14 /
/
6 13 21 <-- MMR indices / \ / \ /
/ \ / \ /
2 5 9 12 17 21 / \ / \ / \ / \ / \ /
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

Modules

algos	Hiker Common Algorithms to climb the Mountain
pruned_hashset	A function for snapshotting and pruning a Merkle Mountain Range Trimmed MMR
pruned_mmr	Trimmed MMR methods

Structs

MerkleChangeTracker	A struct that wraps an MMR to keep track of changes to the MMR over time. This enables one to roll back changes to a point in history. Think of MerkleChangeTracker as 'git' for MMRs.
MerkleChangeTrackerConfig	Configuration for the MerkleChangeTracker.
MerkleCheckPoint
MerkleMountainRange	An implementation of a Merkle Mountain Range (MMR). The MMR is append-only and immutable. Only the hashes are stored in this data structure. The data itself can be stored anywhere as long as you can maintain a 1:1 mapping of the hash of that data to the leaf nodes in the MMR.
MerkleProof	A Merkle proof that proves a particular element at a particular position exists in an MMR.
MutableMmr	Unlike a pure MMR, which is append-only, in MutableMmr, leaf nodes can be marked as deleted.
MutableMmrLeafNodes	The MutableMmrLeafNodes is used to create and share a restorable state for an MMR.

Enums

GeneError

Represents an error in proof creation, verification, or parsing.

Traits

Storage	A trait describing generic array-like behaviour, without imposing any specific details on how this is actually done.
StorageExt

Type Definitions

Bitmap