miden-crypto/src/merkle/store/mod.rs
src/merkle/store/mod.rsRaw
1use super::{
2 mmr::Mmr, BTreeMap, EmptySubtreeRoots, InnerNodeInfo, KvMap, MerkleError, MerklePath,
3 MerkleStoreDelta, MerkleTree, NodeIndex, PartialMerkleTree, RecordingMap, RootPath, Rpo256,
4 RpoDigest, SimpleSmt, TieredSmt, TryApplyDiff, ValuePath, Vec, EMPTY_WORD,
5};
6use crate::utils::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable};
7use core::borrow::Borrow;
8
9#[cfg(test)]
10mod tests;
11
12// MERKLE STORE
13// ================================================================================================
14
15/// A default [MerkleStore] which uses a simple [BTreeMap] as the backing storage.
16pub type DefaultMerkleStore = MerkleStore<BTreeMap<RpoDigest, StoreNode>>;
17
18/// A [MerkleStore] with recording capabilities which uses [RecordingMap] as the backing storage.
19pub type RecordingMerkleStore = MerkleStore<RecordingMap<RpoDigest, StoreNode>>;
20
21#[derive(Debug, Default, Copy, Clone, Eq, PartialEq)]
22#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
23pub struct StoreNode {
24 left: RpoDigest,
25 right: RpoDigest,
26}
27
28/// An in-memory data store for Merkelized data.
29///
30/// This is a in memory data store for Merkle trees, this store allows all the nodes of multiple
31/// trees to live as long as necessary and without duplication, this allows the implementation of
32/// space efficient persistent data structures.
33///
34/// Example usage:
35///
36/// ```rust
37/// # use miden_crypto::{ZERO, Felt, Word};
38/// # use miden_crypto::merkle::{NodeIndex, MerkleStore, MerkleTree};
39/// # use miden_crypto::hash::rpo::Rpo256;
40/// # const fn int_to_node(value: u64) -> Word {
41/// # [Felt::new(value), ZERO, ZERO, ZERO]
42/// # }
43/// # let A = int_to_node(1);
44/// # let B = int_to_node(2);
45/// # let C = int_to_node(3);
46/// # let D = int_to_node(4);
47/// # let E = int_to_node(5);
48/// # let F = int_to_node(6);
49/// # let G = int_to_node(7);
50/// # let H0 = int_to_node(8);
51/// # let H1 = int_to_node(9);
52/// # let T0 = MerkleTree::new([A, B, C, D, E, F, G, H0].to_vec()).expect("even number of leaves provided");
53/// # let T1 = MerkleTree::new([A, B, C, D, E, F, G, H1].to_vec()).expect("even number of leaves provided");
54/// # let ROOT0 = T0.root();
55/// # let ROOT1 = T1.root();
56/// let mut store: MerkleStore = MerkleStore::new();
57///
58/// // the store is initialized with the SMT empty nodes
59/// assert_eq!(store.num_internal_nodes(), 255);
60///
61/// let tree1 = MerkleTree::new(vec![A, B, C, D, E, F, G, H0]).unwrap();
62/// let tree2 = MerkleTree::new(vec![A, B, C, D, E, F, G, H1]).unwrap();
63///
64/// // populates the store with two merkle trees, common nodes are shared
65/// store.extend(tree1.inner_nodes());
66/// store.extend(tree2.inner_nodes());
67///
68/// // every leaf except the last are the same
69/// for i in 0..7 {
70/// let idx0 = NodeIndex::new(3, i).unwrap();
71/// let d0 = store.get_node(ROOT0, idx0).unwrap();
72/// let idx1 = NodeIndex::new(3, i).unwrap();
73/// let d1 = store.get_node(ROOT1, idx1).unwrap();
74/// assert_eq!(d0, d1, "Both trees have the same leaf at pos {i}");
75/// }
76///
77/// // The leafs A-B-C-D are the same for both trees, so are their 2 immediate parents
78/// for i in 0..4 {
79/// let idx0 = NodeIndex::new(3, i).unwrap();
80/// let d0 = store.get_path(ROOT0, idx0).unwrap();
81/// let idx1 = NodeIndex::new(3, i).unwrap();
82/// let d1 = store.get_path(ROOT1, idx1).unwrap();
83/// assert_eq!(d0.path[0..2], d1.path[0..2], "Both sub-trees are equal up to two levels");
84/// }
85///
86/// // Common internal nodes are shared, the two added trees have a total of 30, but the store has
87/// // only 10 new entries, corresponding to the 10 unique internal nodes of these trees.
88/// assert_eq!(store.num_internal_nodes() - 255, 10);
89/// ```
90#[derive(Debug, Clone, Eq, PartialEq)]
91#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
92pub struct MerkleStore<T: KvMap<RpoDigest, StoreNode> = BTreeMap<RpoDigest, StoreNode>> {
93 nodes: T,
94}
95
96impl<T: KvMap<RpoDigest, StoreNode>> Default for MerkleStore<T> {
97 fn default() -> Self {
98 Self::new()
99 }
100}
101
102impl<T: KvMap<RpoDigest, StoreNode>> MerkleStore<T> {
103 // CONSTRUCTORS
104 // --------------------------------------------------------------------------------------------
105
106 /// Creates an empty `MerkleStore` instance.
107 pub fn new() -> MerkleStore<T> {
108 // pre-populate the store with the empty hashes
109 let nodes = empty_hashes().into_iter().collect();
110 MerkleStore { nodes }
111 }
112
113 // PUBLIC ACCESSORS
114 // --------------------------------------------------------------------------------------------
115
116 /// Return a count of the non-leaf nodes in the store.
117 pub fn num_internal_nodes(&self) -> usize {
118 self.nodes.len()
119 }
120
121 /// Returns the node at `index` rooted on the tree `root`.
122 ///
123 /// # Errors
124 /// This method can return the following errors:
125 /// - `RootNotInStore` if the `root` is not present in the store.
126 /// - `NodeNotInStore` if a node needed to traverse from `root` to `index` is not present in
127 /// the store.
128 pub fn get_node(&self, root: RpoDigest, index: NodeIndex) -> Result<RpoDigest, MerkleError> {
129 let mut hash = root;
130
131 // corner case: check the root is in the store when called with index `NodeIndex::root()`
132 self.nodes.get(&hash).ok_or(MerkleError::RootNotInStore(hash))?;
133
134 for i in (0..index.depth()).rev() {
135 let node = self.nodes.get(&hash).ok_or(MerkleError::NodeNotInStore(hash, index))?;
136
137 let bit = (index.value() >> i) & 1;
138 hash = if bit == 0 { node.left } else { node.right }
139 }
140
141 Ok(hash)
142 }
143
144 /// Returns the node at the specified `index` and its opening to the `root`.
145 ///
146 /// The path starts at the sibling of the target leaf.
147 ///
148 /// # Errors
149 /// This method can return the following errors:
150 /// - `RootNotInStore` if the `root` is not present in the store.
151 /// - `NodeNotInStore` if a node needed to traverse from `root` to `index` is not present in
152 /// the store.
153 pub fn get_path(&self, root: RpoDigest, index: NodeIndex) -> Result<ValuePath, MerkleError> {
154 let mut hash = root;
155 let mut path = Vec::with_capacity(index.depth().into());
156
157 // corner case: check the root is in the store when called with index `NodeIndex::root()`
158 self.nodes.get(&hash).ok_or(MerkleError::RootNotInStore(hash))?;
159
160 for i in (0..index.depth()).rev() {
161 let node = self.nodes.get(&hash).ok_or(MerkleError::NodeNotInStore(hash, index))?;
162
163 let bit = (index.value() >> i) & 1;
164 hash = if bit == 0 {
165 path.push(node.right);
166 node.left
167 } else {
168 path.push(node.left);
169 node.right
170 }
171 }
172
173 // the path is computed from root to leaf, so it must be reversed
174 path.reverse();
175
176 Ok(ValuePath::new(hash, path))
177 }
178
179 // LEAF TRAVERSAL
180 // --------------------------------------------------------------------------------------------
181
182 /// Returns the depth of the first leaf or an empty node encountered while traversing the tree
183 /// from the specified root down according to the provided index.
184 ///
185 /// The `tree_depth` parameter specifies the depth of the tree rooted at `root`. The
186 /// maximum value the argument accepts is [u64::BITS].
187 ///
188 /// # Errors
189 /// Will return an error if:
190 /// - The provided root is not found.
191 /// - The provided `tree_depth` is greater than 64.
192 /// - The provided `index` is not valid for a depth equivalent to `tree_depth`.
193 /// - No leaf or an empty node was found while traversing the tree down to `tree_depth`.
194 pub fn get_leaf_depth(
195 &self,
196 root: RpoDigest,
197 tree_depth: u8,
198 index: u64,
199 ) -> Result<u8, MerkleError> {
200 // validate depth and index
201 if tree_depth > 64 {
202 return Err(MerkleError::DepthTooBig(tree_depth as u64));
203 }
204 NodeIndex::new(tree_depth, index)?;
205
206 // check if the root exists, providing the proper error report if it doesn't
207 let empty = EmptySubtreeRoots::empty_hashes(tree_depth);
208 let mut hash = root;
209 if !self.nodes.contains_key(&hash) {
210 return Err(MerkleError::RootNotInStore(hash));
211 }
212
213 // we traverse from root to leaf, so the path is reversed
214 let mut path = (index << (64 - tree_depth)).reverse_bits();
215
216 // iterate every depth and reconstruct the path from root to leaf
217 for depth in 0..=tree_depth {
218 // we short-circuit if an empty node has been found
219 if hash == empty[depth as usize] {
220 return Ok(depth);
221 }
222
223 // fetch the children pair, mapped by its parent hash
224 let children = match self.nodes.get(&hash) {
225 Some(node) => node,
226 None => return Ok(depth),
227 };
228
229 // traverse down
230 hash = if path & 1 == 0 { children.left } else { children.right };
231 path >>= 1;
232 }
233
234 // return an error because we exhausted the index but didn't find either a leaf or an
235 // empty node
236 Err(MerkleError::DepthTooBig(tree_depth as u64 + 1))
237 }
238
239 /// Returns index and value of a leaf node which is the only leaf node in a subtree defined by
240 /// the provided root. If the subtree contains zero or more than one leaf nodes None is
241 /// returned.
242 ///
243 /// The `tree_depth` parameter specifies the depth of the parent tree such that `root` is
244 /// located in this tree at `root_index`. The maximum value the argument accepts is
245 /// [u64::BITS].
246 ///
247 /// # Errors
248 /// Will return an error if:
249 /// - The provided root is not found.
250 /// - The provided `tree_depth` is greater than 64.
251 /// - The provided `root_index` has depth greater than `tree_depth`.
252 /// - A lone node at depth `tree_depth` is not a leaf node.
253 pub fn find_lone_leaf(
254 &self,
255 root: RpoDigest,
256 root_index: NodeIndex,
257 tree_depth: u8,
258 ) -> Result<Option<(NodeIndex, RpoDigest)>, MerkleError> {
259 // we set max depth at u64::BITS as this is the largest meaningful value for a 64-bit index
260 const MAX_DEPTH: u8 = u64::BITS as u8;
261 if tree_depth > MAX_DEPTH {
262 return Err(MerkleError::DepthTooBig(tree_depth as u64));
263 }
264 let empty = EmptySubtreeRoots::empty_hashes(MAX_DEPTH);
265
266 let mut node = root;
267 if !self.nodes.contains_key(&node) {
268 return Err(MerkleError::RootNotInStore(node));
269 }
270
271 let mut index = root_index;
272 if index.depth() > tree_depth {
273 return Err(MerkleError::DepthTooBig(index.depth() as u64));
274 }
275
276 // traverse down following the path of single non-empty nodes; this works because if a
277 // node has two empty children it cannot contain a lone leaf. similarly if a node has
278 // two non-empty children it must contain at least two leaves.
279 for depth in index.depth()..tree_depth {
280 // if the node is a leaf, return; otherwise, examine the node's children
281 let children = match self.nodes.get(&node) {
282 Some(node) => node,
283 None => return Ok(Some((index, node))),
284 };
285
286 let empty_node = empty[depth as usize + 1];
287 node = if children.left != empty_node && children.right == empty_node {
288 index = index.left_child();
289 children.left
290 } else if children.left == empty_node && children.right != empty_node {
291 index = index.right_child();
292 children.right
293 } else {
294 return Ok(None);
295 };
296 }
297
298 // if we are here, we got to `tree_depth`; thus, either the current node is a leaf node,
299 // and so we return it, or it is an internal node, and then we return an error
300 if self.nodes.contains_key(&node) {
301 Err(MerkleError::DepthTooBig(tree_depth as u64 + 1))
302 } else {
303 Ok(Some((index, node)))
304 }
305 }
306
307 // DATA EXTRACTORS
308 // --------------------------------------------------------------------------------------------
309
310 /// Returns a subset of this Merkle store such that the returned Merkle store contains all
311 /// nodes which are descendants of the specified roots.
312 ///
313 /// The roots for which no descendants exist in this Merkle store are ignored.
314 pub fn subset<I, R>(&self, roots: I) -> MerkleStore<T>
315 where
316 I: Iterator<Item = R>,
317 R: Borrow<RpoDigest>,
318 {
319 let mut store = MerkleStore::new();
320 for root in roots {
321 let root = *root.borrow();
322 store.clone_tree_from(root, self);
323 }
324 store
325 }
326
327 /// Iterator over the inner nodes of the [MerkleStore].
328 pub fn inner_nodes(&self) -> impl Iterator<Item = InnerNodeInfo> + '_ {
329 self.nodes.iter().map(|(r, n)| InnerNodeInfo {
330 value: *r,
331 left: n.left,
332 right: n.right,
333 })
334 }
335
336 /// Iterator over the non-empty leaves of the Merkle tree associated with the specified `root`
337 /// and `max_depth`.
338 pub fn non_empty_leaves(
339 &self,
340 root: RpoDigest,
341 max_depth: u8,
342 ) -> impl Iterator<Item = (NodeIndex, RpoDigest)> + '_ {
343 let empty_roots = EmptySubtreeRoots::empty_hashes(max_depth);
344 let mut stack = Vec::new();
345 stack.push((NodeIndex::new_unchecked(0, 0), root));
346
347 core::iter::from_fn(move || {
348 while let Some((index, node_hash)) = stack.pop() {
349 // if we are at the max depth then we have reached a leaf
350 if index.depth() == max_depth {
351 return Some((index, node_hash));
352 }
353
354 // fetch the nodes children and push them onto the stack if they are not the roots
355 // of empty subtrees
356 if let Some(node) = self.nodes.get(&node_hash) {
357 if !empty_roots.contains(&node.left) {
358 stack.push((index.left_child(), node.left));
359 }
360 if !empty_roots.contains(&node.right) {
361 stack.push((index.right_child(), node.right));
362 }
363
364 // if the node is not in the store assume it is a leaf
365 } else {
366 // assert that if we have a leaf that is not at the max depth then it must be
367 // at the depth of one of the tiers of an TSMT.
368 debug_assert!(TieredSmt::TIER_DEPTHS[..3].contains(&index.depth()));
369 return Some((index, node_hash));
370 }
371 }
372
373 None
374 })
375 }
376
377 // STATE MUTATORS
378 // --------------------------------------------------------------------------------------------
379
380 /// Adds all the nodes of a Merkle path represented by `path`, opening to `node`. Returns the
381 /// new root.
382 ///
383 /// This will compute the sibling elements determined by the Merkle `path` and `node`, and
384 /// include all the nodes into the store.
385 pub fn add_merkle_path(
386 &mut self,
387 index: u64,
388 node: RpoDigest,
389 path: MerklePath,
390 ) -> Result<RpoDigest, MerkleError> {
391 let root = path.inner_nodes(index, node)?.fold(RpoDigest::default(), |_, node| {
392 let value: RpoDigest = node.value;
393 let left: RpoDigest = node.left;
394 let right: RpoDigest = node.right;
395
396 debug_assert_eq!(Rpo256::merge(&[left, right]), value);
397 self.nodes.insert(value, StoreNode { left, right });
398
399 node.value
400 });
401 Ok(root)
402 }
403
404 /// Adds all the nodes of multiple Merkle paths into the store.
405 ///
406 /// This will compute the sibling elements for each Merkle `path` and include all the nodes
407 /// into the store.
408 ///
409 /// For further reference, check [MerkleStore::add_merkle_path].
410 pub fn add_merkle_paths<I>(&mut self, paths: I) -> Result<(), MerkleError>
411 where
412 I: IntoIterator<Item = (u64, RpoDigest, MerklePath)>,
413 {
414 for (index_value, node, path) in paths.into_iter() {
415 self.add_merkle_path(index_value, node, path)?;
416 }
417 Ok(())
418 }
419
420 /// Sets a node to `value`.
421 ///
422 /// # Errors
423 /// This method can return the following errors:
424 /// - `RootNotInStore` if the `root` is not present in the store.
425 /// - `NodeNotInStore` if a node needed to traverse from `root` to `index` is not present in
426 /// the store.
427 pub fn set_node(
428 &mut self,
429 mut root: RpoDigest,
430 index: NodeIndex,
431 value: RpoDigest,
432 ) -> Result<RootPath, MerkleError> {
433 let node = value;
434 let ValuePath { value, path } = self.get_path(root, index)?;
435
436 // performs the update only if the node value differs from the opening
437 if node != value {
438 root = self.add_merkle_path(index.value(), node, path.clone())?;
439 }
440
441 Ok(RootPath { root, path })
442 }
443
444 /// Merges two elements and adds the resulting node into the store.
445 ///
446 /// Merges arbitrary values. They may be leafs, nodes, or a mixture of both.
447 pub fn merge_roots(
448 &mut self,
449 left_root: RpoDigest,
450 right_root: RpoDigest,
451 ) -> Result<RpoDigest, MerkleError> {
452 let parent = Rpo256::merge(&[left_root, right_root]);
453 self.nodes.insert(
454 parent,
455 StoreNode {
456 left: left_root,
457 right: right_root,
458 },
459 );
460
461 Ok(parent)
462 }
463
464 // DESTRUCTURING
465 // --------------------------------------------------------------------------------------------
466
467 /// Returns the inner storage of this MerkleStore while consuming `self`.
468 pub fn into_inner(self) -> T {
469 self.nodes
470 }
471
472 // HELPER METHODS
473 // --------------------------------------------------------------------------------------------
474
475 /// Recursively clones a tree with the specified root from the specified source into self.
476 ///
477 /// If the source store does not contain a tree with the specified root, this is a noop.
478 fn clone_tree_from(&mut self, root: RpoDigest, source: &Self) {
479 // process the node only if it is in the source
480 if let Some(node) = source.nodes.get(&root) {
481 // if the node has already been inserted, no need to process it further as all of its
482 // descendants should be already cloned from the source store
483 if self.nodes.insert(root, *node).is_none() {
484 self.clone_tree_from(node.left, source);
485 self.clone_tree_from(node.right, source);
486 }
487 }
488 }
489}
490
491// CONVERSIONS
492// ================================================================================================
493
494impl<T: KvMap<RpoDigest, StoreNode>> From<&MerkleTree> for MerkleStore<T> {
495 fn from(value: &MerkleTree) -> Self {
496 let nodes = combine_nodes_with_empty_hashes(value.inner_nodes()).collect();
497 Self { nodes }
498 }
499}
500
501impl<T: KvMap<RpoDigest, StoreNode>> From<&SimpleSmt> for MerkleStore<T> {
502 fn from(value: &SimpleSmt) -> Self {
503 let nodes = combine_nodes_with_empty_hashes(value.inner_nodes()).collect();
504 Self { nodes }
505 }
506}
507
508impl<T: KvMap<RpoDigest, StoreNode>> From<&Mmr> for MerkleStore<T> {
509 fn from(value: &Mmr) -> Self {
510 let nodes = combine_nodes_with_empty_hashes(value.inner_nodes()).collect();
511 Self { nodes }
512 }
513}
514
515impl<T: KvMap<RpoDigest, StoreNode>> From<&TieredSmt> for MerkleStore<T> {
516 fn from(value: &TieredSmt) -> Self {
517 let nodes = combine_nodes_with_empty_hashes(value.inner_nodes()).collect();
518 Self { nodes }
519 }
520}
521
522impl<T: KvMap<RpoDigest, StoreNode>> From<&PartialMerkleTree> for MerkleStore<T> {
523 fn from(value: &PartialMerkleTree) -> Self {
524 let nodes = combine_nodes_with_empty_hashes(value.inner_nodes()).collect();
525 Self { nodes }
526 }
527}
528
529impl<T: KvMap<RpoDigest, StoreNode>> From<T> for MerkleStore<T> {
530 fn from(values: T) -> Self {
531 let nodes = values.into_iter().chain(empty_hashes()).collect();
532 Self { nodes }
533 }
534}
535
536impl<T: KvMap<RpoDigest, StoreNode>> FromIterator<InnerNodeInfo> for MerkleStore<T> {
537 fn from_iter<I: IntoIterator<Item = InnerNodeInfo>>(iter: I) -> Self {
538 let nodes = combine_nodes_with_empty_hashes(iter).collect();
539 Self { nodes }
540 }
541}
542
543impl<T: KvMap<RpoDigest, StoreNode>> FromIterator<(RpoDigest, StoreNode)> for MerkleStore<T> {
544 fn from_iter<I: IntoIterator<Item = (RpoDigest, StoreNode)>>(iter: I) -> Self {
545 let nodes = iter.into_iter().chain(empty_hashes()).collect();
546 Self { nodes }
547 }
548}
549
550// ITERATORS
551// ================================================================================================
552impl<T: KvMap<RpoDigest, StoreNode>> Extend<InnerNodeInfo> for MerkleStore<T> {
553 fn extend<I: IntoIterator<Item = InnerNodeInfo>>(&mut self, iter: I) {
554 self.nodes.extend(iter.into_iter().map(|info| {
555 (
556 info.value,
557 StoreNode {
558 left: info.left,
559 right: info.right,
560 },
561 )
562 }));
563 }
564}
565
566// DiffT & ApplyDiffT TRAIT IMPLEMENTATION
567// ================================================================================================
568impl<T: KvMap<RpoDigest, StoreNode>> TryApplyDiff<RpoDigest, StoreNode> for MerkleStore<T> {
569 type Error = MerkleError;
570 type DiffType = MerkleStoreDelta;
571
572 fn try_apply(&mut self, diff: Self::DiffType) -> Result<(), MerkleError> {
573 for (root, delta) in diff.0 {
574 let mut root = root;
575 for cleared_slot in delta.cleared_slots() {
576 root = self
577 .set_node(
578 root,
579 NodeIndex::new(delta.depth(), *cleared_slot)?,
580 EMPTY_WORD.into(),
581 )?
582 .root;
583 }
584 for (updated_slot, updated_value) in delta.updated_slots() {
585 root = self
586 .set_node(
587 root,
588 NodeIndex::new(delta.depth(), *updated_slot)?,
589 (*updated_value).into(),
590 )?
591 .root;
592 }
593 }
594
595 Ok(())
596 }
597}
598
599// SERIALIZATION
600// ================================================================================================
601
602impl Serializable for StoreNode {
603 fn write_into<W: ByteWriter>(&self, target: &mut W) {
604 self.left.write_into(target);
605 self.right.write_into(target);
606 }
607}
608
609impl Deserializable for StoreNode {
610 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
611 let left = RpoDigest::read_from(source)?;
612 let right = RpoDigest::read_from(source)?;
613 Ok(StoreNode { left, right })
614 }
615}
616
617impl<T: KvMap<RpoDigest, StoreNode>> Serializable for MerkleStore<T> {
618 fn write_into<W: ByteWriter>(&self, target: &mut W) {
619 target.write_u64(self.nodes.len() as u64);
620
621 for (k, v) in self.nodes.iter() {
622 k.write_into(target);
623 v.write_into(target);
624 }
625 }
626}
627
628impl<T: KvMap<RpoDigest, StoreNode>> Deserializable for MerkleStore<T> {
629 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
630 let len = source.read_u64()?;
631 let mut nodes: Vec<(RpoDigest, StoreNode)> = Vec::with_capacity(len as usize);
632
633 for _ in 0..len {
634 let key = RpoDigest::read_from(source)?;
635 let value = StoreNode::read_from(source)?;
636 nodes.push((key, value));
637 }
638
639 Ok(nodes.into_iter().collect())
640 }
641}
642
643// HELPER FUNCTIONS
644// ================================================================================================
645
646/// Creates empty hashes for all the subtrees of a tree with a max depth of 255.
647fn empty_hashes() -> impl IntoIterator<Item = (RpoDigest, StoreNode)> {
648 let subtrees = EmptySubtreeRoots::empty_hashes(255);
649 subtrees.iter().rev().copied().zip(subtrees.iter().rev().skip(1).copied()).map(
650 |(child, parent)| {
651 (
652 parent,
653 StoreNode {
654 left: child,
655 right: child,
656 },
657 )
658 },
659 )
660}
661
662/// Consumes an iterator of [InnerNodeInfo] and returns an iterator of `(value, node)` tuples
663/// which includes the nodes associate with roots of empty subtrees up to a depth of 255.
664fn combine_nodes_with_empty_hashes(
665 nodes: impl IntoIterator<Item = InnerNodeInfo>,
666) -> impl Iterator<Item = (RpoDigest, StoreNode)> {
667 nodes
668 .into_iter()
669 .map(|info| {
670 (
671 info.value,
672 StoreNode {
673 left: info.left,
674 right: info.right,
675 },
676 )
677 })
678 .chain(empty_hashes())
679}