miden-crypto/src/merkle/mmr/full.rs
src/merkle/mmr/full.rsRaw
1//! A fully materialized Merkle mountain range (MMR).
2//!
3//! A MMR is a forest structure, i.e. it is an ordered set of disjoint rooted trees. The trees are
4//! ordered by size, from the most to least number of leaves. Every tree is a perfect binary tree,
5//! meaning a tree has all its leaves at the same depth, and every inner node has a branch-factor
6//! of 2 with both children set.
7//!
8//! Additionally the structure only supports adding leaves to the right-most tree, the one with the
9//! least number of leaves. The structure preserves the invariant that each tree has different
10//! depths, i.e. as part of adding adding a new element to the forest the trees with same depth are
11//! merged, creating a new tree with depth d+1, this process is continued until the property is
12//! reestablished.
13use super::{
14 super::{InnerNodeInfo, MerklePath},
15 bit::TrueBitPositionIterator,
16 leaf_to_corresponding_tree, nodes_in_forest, MmrDelta, MmrError, MmrPeaks, MmrProof, Rpo256,
17 RpoDigest,
18};
19use alloc::vec::Vec;
20
21// MMR
22// ===============================================================================================
23
24/// A fully materialized Merkle Mountain Range, with every tree in the forest and all their
25/// elements.
26///
27/// Since this is a full representation of the MMR, elements are never removed and the MMR will
28/// grow roughly `O(2n)` in number of leaf elements.
29#[derive(Debug, Clone)]
30#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
31pub struct Mmr {
32 /// Refer to the `forest` method documentation for details of the semantics of this value.
33 pub(super) forest: usize,
34
35 /// Contains every element of the forest.
36 ///
37 /// The trees are in postorder sequential representation. This representation allows for all
38 /// the elements of every tree in the forest to be stored in the same sequential buffer. It
39 /// also means new elements can be added to the forest, and merging of trees is very cheap with
40 /// no need to copy elements.
41 pub(super) nodes: Vec<RpoDigest>,
42}
43
44impl Default for Mmr {
45 fn default() -> Self {
46 Self::new()
47 }
48}
49
50impl Mmr {
51 // CONSTRUCTORS
52 // ============================================================================================
53
54 /// Constructor for an empty `Mmr`.
55 pub fn new() -> Mmr {
56 Mmr { forest: 0, nodes: Vec::new() }
57 }
58
59 // ACCESSORS
60 // ============================================================================================
61
62 /// Returns the MMR forest representation.
63 ///
64 /// The forest value has the following interpretations:
65 /// - its value is the number of elements in the forest
66 /// - bit count corresponds to the number of trees in the forest
67 /// - each true bit position determines the depth of a tree in the forest
68 pub const fn forest(&self) -> usize {
69 self.forest
70 }
71
72 // FUNCTIONALITY
73 // ============================================================================================
74
75 /// Returns an [MmrProof] for the leaf at the specified position.
76 ///
77 /// Note: The leaf position is the 0-indexed number corresponding to the order the leaves were
78 /// added, this corresponds to the MMR size _prior_ to adding the element. So the 1st element
79 /// has position 0, the second position 1, and so on.
80 ///
81 /// # Errors
82 /// Returns an error if the specified leaf position is out of bounds for this MMR.
83 pub fn open(&self, pos: usize) -> Result<MmrProof, MmrError> {
84 self.open_at(pos, self.forest)
85 }
86
87 /// Returns an [MmrProof] for the leaf at the specified position using the state of the MMR
88 /// at the specified `forest`.
89 ///
90 /// Note: The leaf position is the 0-indexed number corresponding to the order the leaves were
91 /// added, this corresponds to the MMR size _prior_ to adding the element. So the 1st element
92 /// has position 0, the second position 1, and so on.
93 ///
94 /// # Errors
95 /// Returns an error if:
96 /// - The specified leaf position is out of bounds for this MMR.
97 /// - The specified `forest` value is not valid for this MMR.
98 pub fn open_at(&self, pos: usize, forest: usize) -> Result<MmrProof, MmrError> {
99 // find the target tree responsible for the MMR position
100 let tree_bit =
101 leaf_to_corresponding_tree(pos, forest).ok_or(MmrError::InvalidPosition(pos))?;
102
103 // isolate the trees before the target
104 let forest_before = forest & high_bitmask(tree_bit + 1);
105 let index_offset = nodes_in_forest(forest_before);
106
107 // update the value position from global to the target tree
108 let relative_pos = pos - forest_before;
109
110 // collect the path and the final index of the target value
111 let (_, path) = self.collect_merkle_path_and_value(tree_bit, relative_pos, index_offset);
112
113 Ok(MmrProof {
114 forest,
115 position: pos,
116 merkle_path: MerklePath::new(path),
117 })
118 }
119
120 /// Returns the leaf value at position `pos`.
121 ///
122 /// Note: The leaf position is the 0-indexed number corresponding to the order the leaves were
123 /// added, this corresponds to the MMR size _prior_ to adding the element. So the 1st element
124 /// has position 0, the second position 1, and so on.
125 pub fn get(&self, pos: usize) -> Result<RpoDigest, MmrError> {
126 // find the target tree responsible for the MMR position
127 let tree_bit =
128 leaf_to_corresponding_tree(pos, self.forest).ok_or(MmrError::InvalidPosition(pos))?;
129
130 // isolate the trees before the target
131 let forest_before = self.forest & high_bitmask(tree_bit + 1);
132 let index_offset = nodes_in_forest(forest_before);
133
134 // update the value position from global to the target tree
135 let relative_pos = pos - forest_before;
136
137 // collect the path and the final index of the target value
138 let (value, _) = self.collect_merkle_path_and_value(tree_bit, relative_pos, index_offset);
139
140 Ok(value)
141 }
142
143 /// Adds a new element to the MMR.
144 pub fn add(&mut self, el: RpoDigest) {
145 // Note: every node is also a tree of size 1, adding an element to the forest creates a new
146 // rooted-tree of size 1. This may temporarily break the invariant that every tree in the
147 // forest has different sizes, the loop below will eagerly merge trees of same size and
148 // restore the invariant.
149 self.nodes.push(el);
150
151 let mut left_offset = self.nodes.len().saturating_sub(2);
152 let mut right = el;
153 let mut left_tree = 1;
154 while self.forest & left_tree != 0 {
155 right = Rpo256::merge(&[self.nodes[left_offset], right]);
156 self.nodes.push(right);
157
158 left_offset = left_offset.saturating_sub(nodes_in_forest(left_tree));
159 left_tree <<= 1;
160 }
161
162 self.forest += 1;
163 }
164
165 /// Returns the current peaks of the MMR.
166 pub fn peaks(&self) -> MmrPeaks {
167 self.peaks_at(self.forest).expect("failed to get peaks at current forest")
168 }
169
170 /// Returns the peaks of the MMR at the state specified by `forest`.
171 ///
172 /// # Errors
173 /// Returns an error if the specified `forest` value is not valid for this MMR.
174 pub fn peaks_at(&self, forest: usize) -> Result<MmrPeaks, MmrError> {
175 if forest > self.forest {
176 return Err(MmrError::InvalidPeaks);
177 }
178
179 let peaks: Vec<RpoDigest> = TrueBitPositionIterator::new(forest)
180 .rev()
181 .map(|bit| nodes_in_forest(1 << bit))
182 .scan(0, |offset, el| {
183 *offset += el;
184 Some(*offset)
185 })
186 .map(|offset| self.nodes[offset - 1])
187 .collect();
188
189 // Safety: the invariant is maintained by the [Mmr]
190 let peaks = MmrPeaks::new(forest, peaks).unwrap();
191
192 Ok(peaks)
193 }
194
195 /// Compute the required update to `original_forest`.
196 ///
197 /// The result is a packed sequence of the authentication elements required to update the trees
198 /// that have been merged together, followed by the new peaks of the [Mmr].
199 pub fn get_delta(&self, from_forest: usize, to_forest: usize) -> Result<MmrDelta, MmrError> {
200 if to_forest > self.forest || from_forest > to_forest {
201 return Err(MmrError::InvalidPeaks);
202 }
203
204 if from_forest == to_forest {
205 return Ok(MmrDelta { forest: to_forest, data: Vec::new() });
206 }
207
208 let mut result = Vec::new();
209
210 // Find the largest tree in this [Mmr] which is new to `from_forest`.
211 let candidate_trees = to_forest ^ from_forest;
212 let mut new_high = 1 << candidate_trees.ilog2();
213
214 // Collect authentication nodes used for tree merges
215 // ----------------------------------------------------------------------------------------
216
217 // Find the trees from `from_forest` that have been merged into `new_high`.
218 let mut merges = from_forest & (new_high - 1);
219
220 // Find the peaks that are common to `from_forest` and this [Mmr]
221 let common_trees = from_forest ^ merges;
222
223 if merges != 0 {
224 // Skip the smallest trees unknown to `from_forest`.
225 let mut target = 1 << merges.trailing_zeros();
226
227 // Collect siblings required to computed the merged tree's peak
228 while target < new_high {
229 // Computes the offset to the smallest know peak
230 // - common_trees: peaks unchanged in the current update, target comes after these.
231 // - merges: peaks that have not been merged so far, target comes after these.
232 // - target: tree from which to load the sibling. On the first iteration this is a
233 // value known by the partial mmr, on subsequent iterations this value is to be
234 // computed from the known peaks and provided authentication nodes.
235 let known = nodes_in_forest(common_trees | merges | target);
236 let sibling = nodes_in_forest(target);
237 result.push(self.nodes[known + sibling - 1]);
238
239 // Update the target and account for tree merges
240 target <<= 1;
241 while merges & target != 0 {
242 target <<= 1;
243 }
244 // Remove the merges done so far
245 merges ^= merges & (target - 1);
246 }
247 } else {
248 // The new high tree may not be the result of any merges, if it is smaller than all the
249 // trees of `from_forest`.
250 new_high = 0;
251 }
252
253 // Collect the new [Mmr] peaks
254 // ----------------------------------------------------------------------------------------
255
256 let mut new_peaks = to_forest ^ common_trees ^ new_high;
257 let old_peaks = to_forest ^ new_peaks;
258 let mut offset = nodes_in_forest(old_peaks);
259 while new_peaks != 0 {
260 let target = 1 << new_peaks.ilog2();
261 offset += nodes_in_forest(target);
262 result.push(self.nodes[offset - 1]);
263 new_peaks ^= target;
264 }
265
266 Ok(MmrDelta { forest: to_forest, data: result })
267 }
268
269 /// An iterator over inner nodes in the MMR. The order of iteration is unspecified.
270 pub fn inner_nodes(&self) -> MmrNodes {
271 MmrNodes {
272 mmr: self,
273 forest: 0,
274 last_right: 0,
275 index: 0,
276 }
277 }
278
279 // UTILITIES
280 // ============================================================================================
281
282 /// Internal function used to collect the Merkle path of a value.
283 ///
284 /// The arguments are relative to the target tree. To compute the opening of the second leaf
285 /// for a tree with depth 2 in the forest `0b110`:
286 ///
287 /// - `tree_bit`: Depth of the target tree, e.g. 2 for the smallest tree.
288 /// - `relative_pos`: 0-indexed leaf position in the target tree, e.g. 1 for the second leaf.
289 /// - `index_offset`: Node count prior to the target tree, e.g. 7 for the tree of depth 3.
290 fn collect_merkle_path_and_value(
291 &self,
292 tree_bit: u32,
293 relative_pos: usize,
294 index_offset: usize,
295 ) -> (RpoDigest, Vec<RpoDigest>) {
296 // see documentation of `leaf_to_corresponding_tree` for details
297 let tree_depth = (tree_bit + 1) as usize;
298 let mut path = Vec::with_capacity(tree_depth);
299
300 // The tree walk below goes from the root to the leaf, compute the root index to start
301 let mut forest_target = 1usize << tree_bit;
302 let mut index = nodes_in_forest(forest_target) - 1;
303
304 // Loop until the leaf is reached
305 while forest_target > 1 {
306 // Update the depth of the tree to correspond to a subtree
307 forest_target >>= 1;
308
309 // compute the indices of the right and left subtrees based on the post-order
310 let right_offset = index - 1;
311 let left_offset = right_offset - nodes_in_forest(forest_target);
312
313 let left_or_right = relative_pos & forest_target;
314 let sibling = if left_or_right != 0 {
315 // going down the right subtree, the right child becomes the new root
316 index = right_offset;
317 // and the left child is the authentication
318 self.nodes[index_offset + left_offset]
319 } else {
320 index = left_offset;
321 self.nodes[index_offset + right_offset]
322 };
323
324 path.push(sibling);
325 }
326
327 debug_assert!(path.len() == tree_depth - 1);
328
329 // the rest of the codebase has the elements going from leaf to root, adjust it here for
330 // easy of use/consistency sake
331 path.reverse();
332
333 let value = self.nodes[index_offset + index];
334 (value, path)
335 }
336}
337
338// CONVERSIONS
339// ================================================================================================
340
341impl<T> From<T> for Mmr
342where
343 T: IntoIterator<Item = RpoDigest>,
344{
345 fn from(values: T) -> Self {
346 let mut mmr = Mmr::new();
347 for v in values {
348 mmr.add(v)
349 }
350 mmr
351 }
352}
353
354// ITERATOR
355// ===============================================================================================
356
357/// Yields inner nodes of the [Mmr].
358pub struct MmrNodes<'a> {
359 /// [Mmr] being yielded, when its `forest` value is matched, the iterations is finished.
360 mmr: &'a Mmr,
361 /// Keeps track of the left nodes yielded so far waiting for a right pair, this matches the
362 /// semantics of the [Mmr]'s forest attribute, since that too works as a buffer of left nodes
363 /// waiting for a pair to be hashed together.
364 forest: usize,
365 /// Keeps track of the last right node yielded, after this value is set, the next iteration
366 /// will be its parent with its corresponding left node that has been yield already.
367 last_right: usize,
368 /// The current index in the `nodes` vector.
369 index: usize,
370}
371
372impl<'a> Iterator for MmrNodes<'a> {
373 type Item = InnerNodeInfo;
374
375 fn next(&mut self) -> Option<Self::Item> {
376 debug_assert!(self.last_right.count_ones() <= 1, "last_right tracks zero or one element");
377
378 // only parent nodes are emitted, remove the single node tree from the forest
379 let target = self.mmr.forest & (usize::MAX << 1);
380
381 if self.forest < target {
382 if self.last_right == 0 {
383 // yield the left leaf
384 debug_assert!(self.last_right == 0, "left must be before right");
385 self.forest |= 1;
386 self.index += 1;
387
388 // yield the right leaf
389 debug_assert!((self.forest & 1) == 1, "right must be after left");
390 self.last_right |= 1;
391 self.index += 1;
392 };
393
394 debug_assert!(
395 self.forest & self.last_right != 0,
396 "parent requires both a left and right",
397 );
398
399 // compute the number of nodes in the right tree, this is the offset to the
400 // previous left parent
401 let right_nodes = nodes_in_forest(self.last_right);
402 // the next parent position is one above the position of the pair
403 let parent = self.last_right << 1;
404
405 // the left node has been paired and the current parent yielded, removed it from the forest
406 self.forest ^= self.last_right;
407 if self.forest & parent == 0 {
408 // this iteration yielded the left parent node
409 debug_assert!(self.forest & 1 == 0, "next iteration yields a left leaf");
410 self.last_right = 0;
411 self.forest ^= parent;
412 } else {
413 // the left node of the parent level has been yielded already, this iteration
414 // was the right parent. Next iteration yields their parent.
415 self.last_right = parent;
416 }
417
418 // yields a parent
419 let value = self.mmr.nodes[self.index];
420 let right = self.mmr.nodes[self.index - 1];
421 let left = self.mmr.nodes[self.index - 1 - right_nodes];
422 self.index += 1;
423 let node = InnerNodeInfo { value, left, right };
424
425 Some(node)
426 } else {
427 None
428 }
429 }
430}
431
432// UTILITIES
433// ===============================================================================================
434
435/// Return a bitmask for the bits including and above the given position.
436pub(crate) const fn high_bitmask(bit: u32) -> usize {
437 if bit > usize::BITS - 1 {
438 0
439 } else {
440 usize::MAX << bit
441 }
442}