Crate tari_mmr

Crate tari_mmr 

Source
Expand description

§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
   ----------------------------------

Modules§

common
error
functions
pruned_hashset
A function for snapshotting and pruning a Merkle Mountain Range
sparse_merkle_tree
Sparse Merkle trees A sparse Merkle tree is a Merkle tree where the non-empty nodes are stored in a map with the key being the hash of the node and the value being the node itself.

Structs§

BalancedBinaryMerkleProof
BalancedBinaryMerkleTree
susceptible to second-preimage attacks. The caller must ensure that the hashers used to pre-hash leaf nodes and instantiate the tree cannot produce collisions.
MemBackendVec
MemBackendVec is a shareable, memory only, vector that can be be used with MmrCache to store checkpoints. MemBackendVec is a shareable, memory only, vector that can be be used with MmrCache to store checkpoints.
MergedBalancedBinaryMerkleProof
MerkleMountainRange
An immutable, append-only Merkle Mountain range (MMR) data structure 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 data structure for proving a hash inclusion in an MMR A Merkle proof that proves a particular element at a particular position exists in an MMR.

Enums§

BalancedBinaryMerkleProofError
BalancedBinaryMerkleTreeError
MerkleProofError
A data structure for proving a hash inclusion in an MMR Merkle proof errors.

Traits§

ArrayLike
A vector-based backend for MerkleMountainRange A trait describing generic array-like behaviour, without imposing any specific details on how this is actually done.
ArrayLikeExt
A vector-based backend for MerkleMountainRange

Type Aliases§

Hash
HashSlice