commonware_storage/mmr/
mod.rs

1//! A Merkle Mountain Range (MMR) is an append-only data structure that allows for efficient
2//! verification of the inclusion of an element, or some range of consecutive elements, in a list.
3//!
4//! # Terminology
5//!
6//! An MMR is a list of perfect binary trees of strictly decreasing height. The roots of these trees
7//! are called the "peaks" of the MMR. Each "element" stored in the MMR is represented by some leaf
8//! node in one of these perfect trees, storing a positioned hash of the element. Non-leaf nodes
9//! store a positioned hash of their children.
10//!
11//! The "size" of an MMR is the total number of nodes summed over all trees.
12//!
13//! The nodes of the MMR are ordered by a post-order traversal of the MMR trees, starting from the
14//! from tallest tree to shortest. The "position" of a node in the MMR is defined as the 0-based
15//! index of the node in this ordering. This implies the positions of elements, which are always
16//! leaves, may not be contiguous even if they were consecutively added.
17//!
18//! As the MMR is an append-only data structure, node positions never change and can be used as
19//! stable identifiers.
20//!
21//! The "height" of a node is 0 for a leaf, 1 for the parent of 2 leaves, and so on.
22//!
23//! The "root hash" of an MMR is the result of hashing together the size of the MMR and the hashes
24//! of every peak in decreasing order of height.
25//!
26//! # Examples
27//!
28//! (Borrowed from <https://docs.grin.mw/wiki/chain-state/merkle-mountain-range/>): After adding 11
29//! elements to an MMR, it will have 19 nodes total with 3 peaks corresponding to 3 perfect binary
30//! trees as pictured below, with nodes identified by their positions:
31//!
32//! ```text
33//!    Height
34//!      3              14
35//!                   /    \
36//!                  /      \
37//!                 /        \
38//!                /          \
39//!      2        6            13
40//!             /   \        /    \
41//!      1     2     5      9     12     17
42//!           / \   / \    / \   /  \   /  \
43//!      0   0   1 3   4  7   8 10  11 15  16 18
44//! ```
45//!
46//! The root hash in this example is computed as:
47//!
48//! ```text
49//!
50//! Hash(19,
51//!   Hash(14,                                                  // first peak
52//!     Hash(6,
53//!       Hash(2, Hash(0, element_0), Hash(1, element_1)),
54//!       Hash(5, Hash(3, element_2), Hash(4, element_4))
55//!     )
56//!     Hash(13,
57//!       Hash(9, Hash(7, element_0), Hash(8, element_8)),
58//!       Hash(12, Hash(10, element_10), Hash(11, element_11))
59//!     )
60//!   )
61//!   Hash(17, Hash(15, element_15), Hash(16, element_16))      // second peak
62//!   Hash(18, element_18)                                      // third peak
63//! )
64//! ```
65
66use thiserror::Error;
67
68mod hasher;
69mod iterator;
70pub mod journaled;
71pub mod mem;
72pub mod verification;
73
74/// Errors that can occur when interacting with an MMR.
75#[derive(Error, Debug)]
76pub enum Error {
77    #[error("an element required for this operation has been pruned")]
78    ElementPruned,
79    #[error("journal error: {0}")]
80    JournalError(#[from] crate::journal::Error),
81}
commonware_storage/mmr/mod.rs

commonware_storage/mmr/
mod.rs
