miden-crypto/src/merkle/mmr/partial.rs
src/merkle/mmr/partial.rsRaw
1use super::{MmrDelta, MmrProof, Rpo256, RpoDigest};
2use crate::{
3 merkle::{
4 mmr::{leaf_to_corresponding_tree, nodes_in_forest},
5 InOrderIndex, InnerNodeInfo, MerklePath, MmrError, MmrPeaks,
6 },
7 utils::{
8 collections::{BTreeMap, BTreeSet, Vec},
9 vec,
10 },
11};
12
13// PARTIAL MERKLE MOUNTAIN RANGE
14// ================================================================================================
15/// Partially materialized Merkle Mountain Range (MMR), used to efficiently store and update the
16/// authentication paths for a subset of the elements in a full MMR.
17///
18/// This structure store only the authentication path for a value, the value itself is stored
19/// separately.
20#[derive(Debug, Clone, PartialEq, Eq)]
21pub struct PartialMmr {
22 /// The version of the MMR.
23 ///
24 /// This value serves the following purposes:
25 ///
26 /// - The forest is a counter for the total number of elements in the MMR.
27 /// - Since the MMR is an append-only structure, every change to it causes a change to the
28 /// `forest`, so this value has a dual purpose as a version tag.
29 /// - The bits in the forest also corresponds to the count and size of every perfect binary
30 /// tree that composes the MMR structure, which server to compute indexes and perform
31 /// validation.
32 pub(crate) forest: usize,
33
34 /// The MMR peaks.
35 ///
36 /// The peaks are used for two reasons:
37 ///
38 /// 1. It authenticates the addition of an element to the [PartialMmr], ensuring only valid
39 /// elements are tracked.
40 /// 2. During a MMR update peaks can be merged by hashing the left and right hand sides. The
41 /// peaks are used as the left hand.
42 ///
43 /// All the peaks of every tree in the MMR forest. The peaks are always ordered by number of
44 /// leaves, starting from the peak with most children, to the one with least.
45 pub(crate) peaks: Vec<RpoDigest>,
46
47 /// Authentication nodes used to construct merkle paths for a subset of the MMR's leaves.
48 ///
49 /// This does not include the MMR's peaks nor the tracked nodes, only the elements required
50 /// to construct their authentication paths. This property is used to detect when elements can
51 /// be safely removed from, because they are no longer required to authenticate any element in
52 /// the [PartialMmr].
53 ///
54 /// The elements in the MMR are referenced using a in-order tree index. This indexing scheme
55 /// permits for easy computation of the relative nodes (left/right children, sibling, parent),
56 /// which is useful for traversal. The indexing is also stable, meaning that merges to the
57 /// trees in the MMR can be represented without rewrites of the indexes.
58 pub(crate) nodes: BTreeMap<InOrderIndex, RpoDigest>,
59
60 /// Flag indicating if the odd element should be tracked.
61 ///
62 /// This flag is necessary because the sibling of the odd doesn't exist yet, so it can not be
63 /// added into `nodes` to signal the value is being tracked.
64 pub(crate) track_latest: bool,
65}
66
67impl PartialMmr {
68 // CONSTRUCTORS
69 // --------------------------------------------------------------------------------------------
70
71 /// Constructs a [PartialMmr] from the given [MmrPeaks].
72 pub fn from_peaks(peaks: MmrPeaks) -> Self {
73 let forest = peaks.num_leaves();
74 let peaks = peaks.peaks().to_vec();
75 let nodes = BTreeMap::new();
76 let track_latest = false;
77
78 Self { forest, peaks, nodes, track_latest }
79 }
80
81 // PUBLIC ACCESSORS
82 // --------------------------------------------------------------------------------------------
83
84 /// Returns the current `forest` of this [PartialMmr].
85 ///
86 /// This value corresponds to the version of the [PartialMmr] and the number of leaves in the
87 /// underlying MMR.
88 pub fn forest(&self) -> usize {
89 self.forest
90 }
91
92 /// Returns the number of leaves in the underlying MMR for this [PartialMmr].
93 pub fn num_leaves(&self) -> usize {
94 self.forest
95 }
96
97 /// Returns the peaks of the MMR for this [PartialMmr].
98 pub fn peaks(&self) -> MmrPeaks {
99 // expect() is OK here because the constructor ensures that MMR peaks can be constructed
100 // correctly
101 MmrPeaks::new(self.forest, self.peaks.clone()).expect("invalid MMR peaks")
102 }
103
104 /// Given a leaf position, returns the Merkle path to its corresponding peak.
105 ///
106 /// If the position is greater-or-equal than the tree size an error is returned. If the
107 /// requested value is not tracked returns `None`.
108 ///
109 /// Note: The leaf position is the 0-indexed number corresponding to the order the leaves were
110 /// added, this corresponds to the MMR size _prior_ to adding the element. So the 1st element
111 /// has position 0, the second position 1, and so on.
112 pub fn open(&self, pos: usize) -> Result<Option<MmrProof>, MmrError> {
113 let tree_bit =
114 leaf_to_corresponding_tree(pos, self.forest).ok_or(MmrError::InvalidPosition(pos))?;
115 let depth = tree_bit as usize;
116
117 let mut nodes = Vec::with_capacity(depth);
118 let mut idx = InOrderIndex::from_leaf_pos(pos);
119
120 while let Some(node) = self.nodes.get(&idx.sibling()) {
121 nodes.push(*node);
122 idx = idx.parent();
123 }
124
125 // If there are nodes then the path must be complete, otherwise it is a bug
126 debug_assert!(nodes.is_empty() || nodes.len() == depth);
127
128 if nodes.len() != depth {
129 // The requested `pos` is not being tracked.
130 Ok(None)
131 } else {
132 Ok(Some(MmrProof {
133 forest: self.forest,
134 position: pos,
135 merkle_path: MerklePath::new(nodes),
136 }))
137 }
138 }
139
140 // ITERATORS
141 // --------------------------------------------------------------------------------------------
142
143 /// Returns an iterator nodes of all authentication paths of this [PartialMmr].
144 pub fn nodes(&self) -> impl Iterator<Item = (&InOrderIndex, &RpoDigest)> {
145 self.nodes.iter()
146 }
147
148 /// Returns an iterator over inner nodes of this [PartialMmr] for the specified leaves.
149 ///
150 /// The order of iteration is not defined. If a leaf is not presented in this partial MMR it
151 /// is silently ignored.
152 pub fn inner_nodes<'a, I: Iterator<Item = &'a (usize, RpoDigest)> + 'a>(
153 &'a self,
154 mut leaves: I,
155 ) -> impl Iterator<Item = InnerNodeInfo> + '_ {
156 let stack = if let Some((pos, leaf)) = leaves.next() {
157 let idx = InOrderIndex::from_leaf_pos(*pos);
158 vec![(idx, *leaf)]
159 } else {
160 Vec::new()
161 };
162
163 InnerNodeIterator {
164 nodes: &self.nodes,
165 leaves,
166 stack,
167 seen_nodes: BTreeSet::new(),
168 }
169 }
170
171 // STATE MUTATORS
172 // --------------------------------------------------------------------------------------------
173
174 /// Add the authentication path represented by [MerklePath] if it is valid.
175 ///
176 /// The `index` refers to the global position of the leaf in the MMR, these are 0-indexed
177 /// values assigned in a strictly monotonic fashion as elements are inserted into the MMR,
178 /// this value corresponds to the values used in the MMR structure.
179 ///
180 /// The `node` corresponds to the value at `index`, and `path` is the authentication path for
181 /// that element up to its corresponding Mmr peak. The `node` is only used to compute the root
182 /// from the authentication path to valid the data, only the authentication data is saved in
183 /// the structure. If the value is required it should be stored out-of-band.
184 pub fn add(
185 &mut self,
186 index: usize,
187 node: RpoDigest,
188 path: &MerklePath,
189 ) -> Result<(), MmrError> {
190 // Checks there is a tree with same depth as the authentication path, if not the path is
191 // invalid.
192 let tree = 1 << path.depth();
193 if tree & self.forest == 0 {
194 return Err(MmrError::UnknownPeak);
195 };
196
197 if index + 1 == self.forest
198 && path.depth() == 0
199 && self.peaks.last().map_or(false, |v| *v == node)
200 {
201 self.track_latest = true;
202 return Ok(());
203 }
204
205 // ignore the trees smaller than the target (these elements are position after the current
206 // target and don't affect the target index)
207 let target_forest = self.forest ^ (self.forest & (tree - 1));
208 let peak_pos = (target_forest.count_ones() - 1) as usize;
209
210 // translate from mmr index to merkle path
211 let path_idx = index - (target_forest ^ tree);
212
213 // Compute the root of the authentication path, and check it matches the current version of
214 // the PartialMmr.
215 let computed = path.compute_root(path_idx as u64, node).map_err(MmrError::MerkleError)?;
216 if self.peaks[peak_pos] != computed {
217 return Err(MmrError::InvalidPeak);
218 }
219
220 let mut idx = InOrderIndex::from_leaf_pos(index);
221 for node in path.nodes() {
222 self.nodes.insert(idx.sibling(), *node);
223 idx = idx.parent();
224 }
225
226 Ok(())
227 }
228
229 /// Remove a leaf of the [PartialMmr] and the unused nodes from the authentication path.
230 ///
231 /// Note: `leaf_pos` corresponds to the position in the MMR and not on an individual tree.
232 pub fn remove(&mut self, leaf_pos: usize) {
233 let mut idx = InOrderIndex::from_leaf_pos(leaf_pos);
234
235 self.nodes.remove(&idx.sibling());
236
237 // `idx` represent the element that can be computed by the authentication path, because
238 // these elements can be computed they are not saved for the authentication of the current
239 // target. In other words, if the idx is present it was added for the authentication of
240 // another element, and no more elements should be removed otherwise it would remove that
241 // element's authentication data.
242 while !self.nodes.contains_key(&idx) {
243 idx = idx.parent();
244 self.nodes.remove(&idx.sibling());
245 }
246 }
247
248 /// Applies updates to this [PartialMmr] and returns a vector of new authentication nodes
249 /// inserted into the partial MMR.
250 pub fn apply(&mut self, delta: MmrDelta) -> Result<Vec<(InOrderIndex, RpoDigest)>, MmrError> {
251 if delta.forest < self.forest {
252 return Err(MmrError::InvalidPeaks);
253 }
254
255 let mut inserted_nodes = Vec::new();
256
257 if delta.forest == self.forest {
258 if !delta.data.is_empty() {
259 return Err(MmrError::InvalidUpdate);
260 }
261
262 return Ok(inserted_nodes);
263 }
264
265 // find the tree merges
266 let changes = self.forest ^ delta.forest;
267 let largest = 1 << changes.ilog2();
268 let merges = self.forest & (largest - 1);
269
270 debug_assert!(
271 !self.track_latest || (merges & 1) == 1,
272 "if there is an odd element, a merge is required"
273 );
274
275 // count the number elements needed to produce largest from the current state
276 let (merge_count, new_peaks) = if merges != 0 {
277 let depth = largest.trailing_zeros();
278 let skipped = merges.trailing_zeros();
279 let computed = merges.count_ones() - 1;
280 let merge_count = depth - skipped - computed;
281
282 let new_peaks = delta.forest & (largest - 1);
283
284 (merge_count, new_peaks)
285 } else {
286 (0, changes)
287 };
288
289 // verify the delta size
290 if (delta.data.len() as u32) != merge_count + new_peaks.count_ones() {
291 return Err(MmrError::InvalidUpdate);
292 }
293
294 // keeps track of how many data elements from the update have been consumed
295 let mut update_count = 0;
296
297 if merges != 0 {
298 // starts at the smallest peak and follows the merged peaks
299 let mut peak_idx = forest_to_root_index(self.forest);
300
301 // match order of the update data while applying it
302 self.peaks.reverse();
303
304 // set to true when the data is needed for authentication paths updates
305 let mut track = self.track_latest;
306 self.track_latest = false;
307
308 let mut peak_count = 0;
309 let mut target = 1 << merges.trailing_zeros();
310 let mut new = delta.data[0];
311 update_count += 1;
312
313 while target < largest {
314 // check if either the left or right subtrees have saved for authentication paths.
315 // If so, turn tracking on to update those paths.
316 if target != 1 && !track {
317 track = self.is_tracked_node(&peak_idx);
318 }
319
320 // update data only contains the nodes from the right subtrees, left nodes are
321 // either previously known peaks or computed values
322 let (left, right) = if target & merges != 0 {
323 let peak = self.peaks[peak_count];
324 let sibling_idx = peak_idx.sibling();
325
326 // if the sibling peak is tracked, add this peaks to the set of
327 // authentication nodes
328 if self.is_tracked_node(&sibling_idx) {
329 self.nodes.insert(peak_idx, new);
330 inserted_nodes.push((peak_idx, new));
331 }
332 peak_count += 1;
333 (peak, new)
334 } else {
335 let update = delta.data[update_count];
336 update_count += 1;
337 (new, update)
338 };
339
340 if track {
341 let sibling_idx = peak_idx.sibling();
342 if peak_idx.is_left_child() {
343 self.nodes.insert(sibling_idx, right);
344 inserted_nodes.push((sibling_idx, right));
345 } else {
346 self.nodes.insert(sibling_idx, left);
347 inserted_nodes.push((sibling_idx, left));
348 }
349 }
350
351 peak_idx = peak_idx.parent();
352 new = Rpo256::merge(&[left, right]);
353 target <<= 1;
354 }
355
356 debug_assert!(peak_count == (merges.count_ones() as usize));
357
358 // restore the peaks order
359 self.peaks.reverse();
360 // remove the merged peaks
361 self.peaks.truncate(self.peaks.len() - peak_count);
362 // add the newly computed peak, the result of the merges
363 self.peaks.push(new);
364 }
365
366 // The rest of the update data is composed of peaks. None of these elements can contain
367 // tracked elements because the peaks were unknown, and it is not possible to add elements
368 // for tacking without authenticating it to a peak.
369 self.peaks.extend_from_slice(&delta.data[update_count..]);
370 self.forest = delta.forest;
371
372 debug_assert!(self.peaks.len() == (self.forest.count_ones() as usize));
373
374 Ok(inserted_nodes)
375 }
376
377 // HELPER METHODS
378 // --------------------------------------------------------------------------------------------
379
380 /// Returns true if this [PartialMmr] tracks authentication path for the node at the specified
381 /// index.
382 fn is_tracked_node(&self, node_index: &InOrderIndex) -> bool {
383 if node_index.is_leaf() {
384 self.nodes.contains_key(&node_index.sibling())
385 } else {
386 let left_child = node_index.left_child();
387 let right_child = node_index.right_child();
388 self.nodes.contains_key(&left_child) | self.nodes.contains_key(&right_child)
389 }
390 }
391}
392
393// CONVERSIONS
394// ================================================================================================
395
396impl From<MmrPeaks> for PartialMmr {
397 fn from(peaks: MmrPeaks) -> Self {
398 Self::from_peaks(peaks)
399 }
400}
401
402impl From<PartialMmr> for MmrPeaks {
403 fn from(partial_mmr: PartialMmr) -> Self {
404 // Safety: the [PartialMmr] maintains the constraints the number of true bits in the forest
405 // matches the number of peaks, as required by the [MmrPeaks]
406 MmrPeaks::new(partial_mmr.forest, partial_mmr.peaks).unwrap()
407 }
408}
409
410impl From<&MmrPeaks> for PartialMmr {
411 fn from(peaks: &MmrPeaks) -> Self {
412 Self::from_peaks(peaks.clone())
413 }
414}
415
416impl From<&PartialMmr> for MmrPeaks {
417 fn from(partial_mmr: &PartialMmr) -> Self {
418 // Safety: the [PartialMmr] maintains the constraints the number of true bits in the forest
419 // matches the number of peaks, as required by the [MmrPeaks]
420 MmrPeaks::new(partial_mmr.forest, partial_mmr.peaks.clone()).unwrap()
421 }
422}
423
424// ITERATORS
425// ================================================================================================
426
427/// An iterator over every inner node of the [PartialMmr].
428pub struct InnerNodeIterator<'a, I: Iterator<Item = &'a (usize, RpoDigest)>> {
429 nodes: &'a BTreeMap<InOrderIndex, RpoDigest>,
430 leaves: I,
431 stack: Vec<(InOrderIndex, RpoDigest)>,
432 seen_nodes: BTreeSet<InOrderIndex>,
433}
434
435impl<'a, I: Iterator<Item = &'a (usize, RpoDigest)>> Iterator for InnerNodeIterator<'a, I> {
436 type Item = InnerNodeInfo;
437
438 fn next(&mut self) -> Option<Self::Item> {
439 while let Some((idx, node)) = self.stack.pop() {
440 let parent_idx = idx.parent();
441 let new_node = self.seen_nodes.insert(parent_idx);
442
443 // if we haven't seen this node's parent before, and the node has a sibling, return
444 // the inner node defined by the parent of this node, and move up the branch
445 if new_node {
446 if let Some(sibling) = self.nodes.get(&idx.sibling()) {
447 let (left, right) = if parent_idx.left_child() == idx {
448 (node, *sibling)
449 } else {
450 (*sibling, node)
451 };
452 let parent = Rpo256::merge(&[left, right]);
453 let inner_node = InnerNodeInfo { value: parent, left, right };
454
455 self.stack.push((parent_idx, parent));
456 return Some(inner_node);
457 }
458 }
459
460 // the previous leaf has been processed, try to process the next leaf
461 if let Some((pos, leaf)) = self.leaves.next() {
462 let idx = InOrderIndex::from_leaf_pos(*pos);
463 self.stack.push((idx, *leaf));
464 }
465 }
466
467 None
468 }
469}
470
471// UTILS
472// ================================================================================================
473
474/// Given the description of a `forest`, returns the index of the root element of the smallest tree
475/// in it.
476fn forest_to_root_index(forest: usize) -> InOrderIndex {
477 // Count total size of all trees in the forest.
478 let nodes = nodes_in_forest(forest);
479
480 // Add the count for the parent nodes that separate each tree. These are allocated but
481 // currently empty, and correspond to the nodes that will be used once the trees are merged.
482 let open_trees = (forest.count_ones() - 1) as usize;
483
484 // Remove the count of the right subtree of the target tree, target tree root index comes
485 // before the subtree for the in-order tree walk.
486 let right_subtree_count = ((1u32 << forest.trailing_zeros()) - 1) as usize;
487
488 let idx = nodes + open_trees - right_subtree_count;
489
490 InOrderIndex::new(idx.try_into().unwrap())
491}
492
493// TESTS
494// ================================================================================================
495
496#[cfg(test)]
497mod tests {
498 use super::{forest_to_root_index, BTreeSet, InOrderIndex, PartialMmr, RpoDigest, Vec};
499 use crate::merkle::{int_to_node, MerkleStore, Mmr, NodeIndex};
500
501 const LEAVES: [RpoDigest; 7] = [
502 int_to_node(0),
503 int_to_node(1),
504 int_to_node(2),
505 int_to_node(3),
506 int_to_node(4),
507 int_to_node(5),
508 int_to_node(6),
509 ];
510
511 #[test]
512 fn test_forest_to_root_index() {
513 fn idx(pos: usize) -> InOrderIndex {
514 InOrderIndex::new(pos.try_into().unwrap())
515 }
516
517 // When there is a single tree in the forest, the index is equivalent to the number of
518 // leaves in that tree, which is `2^n`.
519 assert_eq!(forest_to_root_index(0b0001), idx(1));
520 assert_eq!(forest_to_root_index(0b0010), idx(2));
521 assert_eq!(forest_to_root_index(0b0100), idx(4));
522 assert_eq!(forest_to_root_index(0b1000), idx(8));
523
524 assert_eq!(forest_to_root_index(0b0011), idx(5));
525 assert_eq!(forest_to_root_index(0b0101), idx(9));
526 assert_eq!(forest_to_root_index(0b1001), idx(17));
527 assert_eq!(forest_to_root_index(0b0111), idx(13));
528 assert_eq!(forest_to_root_index(0b1011), idx(21));
529 assert_eq!(forest_to_root_index(0b1111), idx(29));
530
531 assert_eq!(forest_to_root_index(0b0110), idx(10));
532 assert_eq!(forest_to_root_index(0b1010), idx(18));
533 assert_eq!(forest_to_root_index(0b1100), idx(20));
534 assert_eq!(forest_to_root_index(0b1110), idx(26));
535 }
536
537 #[test]
538 fn test_partial_mmr_apply_delta() {
539 // build an MMR with 10 nodes (2 peaks) and a partial MMR based on it
540 let mut mmr = Mmr::default();
541 (0..10).for_each(|i| mmr.add(int_to_node(i)));
542 let mut partial_mmr: PartialMmr = mmr.peaks(mmr.forest()).unwrap().into();
543
544 // add authentication path for position 1 and 8
545 {
546 let node = mmr.get(1).unwrap();
547 let proof = mmr.open(1, mmr.forest()).unwrap();
548 partial_mmr.add(1, node, &proof.merkle_path).unwrap();
549 }
550
551 {
552 let node = mmr.get(8).unwrap();
553 let proof = mmr.open(8, mmr.forest()).unwrap();
554 partial_mmr.add(8, node, &proof.merkle_path).unwrap();
555 }
556
557 // add 2 more nodes into the MMR and validate apply_delta()
558 (10..12).for_each(|i| mmr.add(int_to_node(i)));
559 validate_apply_delta(&mmr, &mut partial_mmr);
560
561 // add 1 more node to the MMR, validate apply_delta() and start tracking the node
562 mmr.add(int_to_node(12));
563 validate_apply_delta(&mmr, &mut partial_mmr);
564 {
565 let node = mmr.get(12).unwrap();
566 let proof = mmr.open(12, mmr.forest()).unwrap();
567 partial_mmr.add(12, node, &proof.merkle_path).unwrap();
568 assert!(partial_mmr.track_latest);
569 }
570
571 // by this point we are tracking authentication paths for positions: 1, 8, and 12
572
573 // add 3 more nodes to the MMR (collapses to 1 peak) and validate apply_delta()
574 (13..16).for_each(|i| mmr.add(int_to_node(i)));
575 validate_apply_delta(&mmr, &mut partial_mmr);
576 }
577
578 fn validate_apply_delta(mmr: &Mmr, partial: &mut PartialMmr) {
579 let tracked_leaves = partial
580 .nodes
581 .iter()
582 .filter_map(|(index, _)| if index.is_leaf() { Some(index.sibling()) } else { None })
583 .collect::<Vec<_>>();
584 let nodes_before = partial.nodes.clone();
585
586 // compute and apply delta
587 let delta = mmr.get_delta(partial.forest(), mmr.forest()).unwrap();
588 let nodes_delta = partial.apply(delta).unwrap();
589
590 // new peaks were computed correctly
591 assert_eq!(mmr.peaks(mmr.forest()).unwrap(), partial.peaks());
592
593 let mut expected_nodes = nodes_before;
594 for (key, value) in nodes_delta {
595 // nodes should not be duplicated
596 assert!(expected_nodes.insert(key, value).is_none());
597 }
598
599 // new nodes should be a combination of original nodes and delta
600 assert_eq!(expected_nodes, partial.nodes);
601
602 // make sure tracked leaves open to the same proofs as in the underlying MMR
603 for index in tracked_leaves {
604 let index_value: u64 = index.into();
605 let pos = index_value / 2;
606 let proof1 = partial.open(pos as usize).unwrap().unwrap();
607 let proof2 = mmr.open(pos as usize, mmr.forest()).unwrap();
608 assert_eq!(proof1, proof2);
609 }
610 }
611
612 #[test]
613 fn test_partial_mmr_inner_nodes_iterator() {
614 // build the MMR
615 let mmr: Mmr = LEAVES.into();
616 let first_peak = mmr.peaks(mmr.forest).unwrap().peaks()[0];
617
618 // -- test single tree ----------------------------
619
620 // get path and node for position 1
621 let node1 = mmr.get(1).unwrap();
622 let proof1 = mmr.open(1, mmr.forest()).unwrap();
623
624 // create partial MMR and add authentication path to node at position 1
625 let mut partial_mmr: PartialMmr = mmr.peaks(mmr.forest()).unwrap().into();
626 partial_mmr.add(1, node1, &proof1.merkle_path).unwrap();
627
628 // empty iterator should have no nodes
629 assert_eq!(partial_mmr.inner_nodes([].iter()).next(), None);
630
631 // build Merkle store from authentication paths in partial MMR
632 let mut store: MerkleStore = MerkleStore::new();
633 store.extend(partial_mmr.inner_nodes([(1, node1)].iter()));
634
635 let index1 = NodeIndex::new(2, 1).unwrap();
636 let path1 = store.get_path(first_peak, index1).unwrap().path;
637
638 assert_eq!(path1, proof1.merkle_path);
639
640 // -- test no duplicates --------------------------
641
642 // build the partial MMR
643 let mut partial_mmr: PartialMmr = mmr.peaks(mmr.forest()).unwrap().into();
644
645 let node0 = mmr.get(0).unwrap();
646 let proof0 = mmr.open(0, mmr.forest()).unwrap();
647
648 let node2 = mmr.get(2).unwrap();
649 let proof2 = mmr.open(2, mmr.forest()).unwrap();
650
651 partial_mmr.add(0, node0, &proof0.merkle_path).unwrap();
652 partial_mmr.add(1, node1, &proof1.merkle_path).unwrap();
653 partial_mmr.add(2, node2, &proof2.merkle_path).unwrap();
654
655 // make sure there are no duplicates
656 let leaves = [(0, node0), (1, node1), (2, node2)];
657 let mut nodes = BTreeSet::new();
658 for node in partial_mmr.inner_nodes(leaves.iter()) {
659 assert!(nodes.insert(node.value));
660 }
661
662 // and also that the store is still be built correctly
663 store.extend(partial_mmr.inner_nodes(leaves.iter()));
664
665 let index0 = NodeIndex::new(2, 0).unwrap();
666 let index1 = NodeIndex::new(2, 1).unwrap();
667 let index2 = NodeIndex::new(2, 2).unwrap();
668
669 let path0 = store.get_path(first_peak, index0).unwrap().path;
670 let path1 = store.get_path(first_peak, index1).unwrap().path;
671 let path2 = store.get_path(first_peak, index2).unwrap().path;
672
673 assert_eq!(path0, proof0.merkle_path);
674 assert_eq!(path1, proof1.merkle_path);
675 assert_eq!(path2, proof2.merkle_path);
676
677 // -- test multiple trees -------------------------
678
679 // build the partial MMR
680 let mut partial_mmr: PartialMmr = mmr.peaks(mmr.forest()).unwrap().into();
681
682 let node5 = mmr.get(5).unwrap();
683 let proof5 = mmr.open(5, mmr.forest()).unwrap();
684
685 partial_mmr.add(1, node1, &proof1.merkle_path).unwrap();
686 partial_mmr.add(5, node5, &proof5.merkle_path).unwrap();
687
688 // build Merkle store from authentication paths in partial MMR
689 let mut store: MerkleStore = MerkleStore::new();
690 store.extend(partial_mmr.inner_nodes([(1, node1), (5, node5)].iter()));
691
692 let index1 = NodeIndex::new(2, 1).unwrap();
693 let index5 = NodeIndex::new(1, 1).unwrap();
694
695 let second_peak = mmr.peaks(mmr.forest).unwrap().peaks()[1];
696
697 let path1 = store.get_path(first_peak, index1).unwrap().path;
698 let path5 = store.get_path(second_peak, index5).unwrap().path;
699
700 assert_eq!(path1, proof1.merkle_path);
701 assert_eq!(path5, proof5.merkle_path);
702 }
703}