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 (aka _mountains_) of strictly decreasing height. The
7//! roots of these trees are called the _peaks_ of the MMR. Each _element_ stored in the MMR is
8//! represented by some leaf node in one of these perfect trees, storing a positioned hash of the
9//! element. Non-leaf nodes 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. An element's _location_ is
17//! its 0-based index in the order of element insertion (aka its leaf index). In the example below,
18//! the right-most element has position 18 and location 10.
19//!
20//! As the MMR is an append-only data structure, node positions never change and can be used as
21//! stable identifiers.
22//!
23//! The _height_ of a node is 0 for a leaf, 1 for the parent of 2 leaves, and so on.
24//!
25//! The _root digest_ (or just _root_) of an MMR is the result of hashing together the size of the
26//! MMR and the digests of every peak in decreasing order of height.
27//!
28//! # Examples
29//!
30//! (Borrowed from <https://docs.grin.mw/wiki/chain-state/merkle-mountain-range/>): After adding 11
31//! elements to an MMR, it will have 19 nodes total with 3 peaks corresponding to 3 perfect binary
32//! trees as pictured below, with nodes identified by their positions:
33//!
34//! ```text
35//!    Height
36//!      3              14
37//!                   /    \
38//!                  /      \
39//!                 /        \
40//!                /          \
41//!      2        6            13
42//!             /   \        /    \
43//!      1     2     5      9     12     17
44//!           / \   / \    / \   /  \   /  \
45//!      0   0   1 3   4  7   8 10  11 15  16 18
46//!
47//! Location 0   1 2   3  4   5  6   7  8   9 10
48//! ```
49//!
50//! The root hash in this example is computed as:
51//!
52//! ```text
53//!
54//! Hash(19,
55//!   Hash(14,                                                  // first peak
56//!     Hash(6,
57//!       Hash(2, Hash(0, element_0), Hash(1, element_1)),
58//!       Hash(5, Hash(3, element_2), Hash(4, element_3))
59//!     )
60//!     Hash(13,
61//!       Hash(9, Hash(7, element_4), Hash(8, element_5)),
62//!       Hash(12, Hash(10, element_6), Hash(11, element_7))
63//!     )
64//!   )
65//!   Hash(17, Hash(15, element_8), Hash(16, element_9))        // second peak
66//!   Hash(18, element_10)                                      // third peak
67//! )
68//! ```
69
70pub mod hasher;
71pub mod iterator;
72pub mod location;
73pub mod mem;
74pub mod position;
75pub mod proof;
76
77#[cfg(test)]
78pub(crate) mod conformance;
79
80cfg_if::cfg_if! {
81    if #[cfg(feature = "std")] {
82        pub mod grafting;
83        pub mod journaled;
84        pub mod storage;
85        pub mod verification;
86    }
87}
88
89pub use hasher::Standard as StandardHasher;
90pub use location::{Location, LocationError, MAX_LOCATION};
91pub use position::{Position, MAX_POSITION};
92pub use proof::{Proof, MAX_PROOF_DIGESTS_PER_ELEMENT};
93use thiserror::Error;
94
95/// Errors that can occur when interacting with an MMR.
96#[derive(Error, Debug)]
97pub enum Error {
98    #[cfg(feature = "std")]
99    #[error("metadata error: {0}")]
100    MetadataError(#[from] crate::metadata::Error),
101    #[cfg(feature = "std")]
102    #[error("journal error: {0}")]
103    JournalError(#[from] crate::journal::Error),
104    #[cfg(feature = "std")]
105    #[error("runtime error: {0}")]
106    Runtime(#[from] commonware_runtime::Error),
107    #[error("missing node: {0}")]
108    MissingNode(Position),
109    #[error("invalid proof")]
110    InvalidProof,
111    #[error("root mismatch")]
112    RootMismatch,
113    #[error("element pruned: {0}")]
114    ElementPruned(Position),
115    #[error("position is not a leaf: {0}")]
116    PositionNotLeaf(Position),
117    #[error("invalid position: {0}")]
118    InvalidPosition(Position),
119    #[error("missing digest: {0}")]
120    MissingDigest(Position),
121    #[error("missing grafted digest for leaf: {0}")]
122    MissingGraftedDigest(Location),
123    #[error("invalid proof length")]
124    InvalidProofLength,
125    #[error("invalid size: {0}")]
126    InvalidSize(u64),
127    #[error("empty")]
128    Empty,
129    #[error("pruned chunks causes u64 overflow")]
130    PrunedChunksOverflow,
131    #[error("location {0} > MAX_LOCATION")]
132    LocationOverflow(Location),
133    #[error("range out of bounds: end location {0} exceeds MMR size")]
134    RangeOutOfBounds(Location),
135    #[error("leaf location out of bounds: {0}")]
136    LeafOutOfBounds(Location),
137    #[error("bit offset {0} out of bounds (size: {1})")]
138    BitOutOfBounds(u64, u64),
139    #[error("invalid pinned nodes")]
140    InvalidPinnedNodes,
141    #[error("data corrupted: {0}")]
142    DataCorrupted(&'static str),
143}
144
145impl From<LocationError> for Error {
146    fn from(err: LocationError) -> Self {
147        match err {
148            LocationError::NonLeaf(pos) => Self::PositionNotLeaf(pos),
149            LocationError::Overflow(pos) => Self::InvalidPosition(pos),
150        }
151    }
152}
commonware_storage/mmr/mod.rs

commonware_storage/mmr/
mod.rs
