Crate tari_mmr[−][src]
Expand description
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 4Looking 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
Structs
MemBackendVec is a shareable, memory only, vector that can be be used with MmrCache to store checkpoints.
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.
A Merkle proof that proves a particular element at a particular position exists in an MMR.
The MMR cache is used to calculate Merkle and Merklish roots based on the state of the set of shared checkpoints. It can efficiently create an updated cache state when small checkpoint rewinds were detected or the checkpoint state has been expanded.
Configuration for the MmrCache.
Unlike a pure MMR, which is append-only, in MutableMmr, leaf nodes can be marked as deleted.
The MutableMmrLeafNodes is used to create and share a restorable state for an MMR.
Enums
Merkle proof errors.
Traits
A trait describing generic array-like behaviour, without imposing any specific details on how this is actually done.