commonware_storage/mmr/
read.rs

1//! Read-only trait for merkleized MMRs.
2//!
3//! [`Readable`] provides an interface for reading from a merkleized MMR.
4//!
5//! [`BatchChainInfo`] is used to walk chains of batches.
6
7use crate::mmr::{iterator::PeakIterator, proof, Error, Location, Position, Proof};
8use alloc::{collections::BTreeMap, vec::Vec};
9use commonware_cryptography::Digest;
10use core::ops::Range;
11
12/// Read-only interface for a merkleized MMR.
13pub trait Readable<D: Digest>: Send + Sync {
14    /// Total number of nodes (retained + pruned).
15    fn size(&self) -> Position;
16
17    /// Digest of the node at `pos`, or `None` if pruned / out of bounds.
18    fn get_node(&self, pos: Position) -> Option<D>;
19
20    /// Root digest of the MMR.
21    fn root(&self) -> D;
22
23    /// Items before this position have been pruned.
24    fn pruned_to_pos(&self) -> Position;
25
26    /// Total number of leaves.
27    fn leaves(&self) -> Location {
28        Location::try_from(self.size()).expect("invalid mmr size")
29    }
30
31    /// Iterator over (peak_position, height) in decreasing height order.
32    fn peak_iterator(&self) -> PeakIterator {
33        PeakIterator::new(self.size())
34    }
35
36    /// [start, end) range of retained node positions.
37    fn bounds(&self) -> Range<Position> {
38        self.pruned_to_pos()..self.size()
39    }
40
41    /// Inclusion proof for the element at `loc`.
42    fn proof(&self, loc: Location) -> Result<Proof<D>, Error> {
43        if !loc.is_valid() {
44            return Err(Error::LocationOverflow(loc));
45        }
46        self.range_proof(loc..loc + 1).map_err(|e| match e {
47            Error::RangeOutOfBounds(loc) => Error::LeafOutOfBounds(loc),
48            _ => e,
49        })
50    }
51
52    /// Inclusion proof for all elements in `range`.
53    fn range_proof(&self, range: Range<Location>) -> Result<Proof<D>, Error> {
54        let leaves = self.leaves();
55        let positions = proof::nodes_required_for_range_proof(leaves, range)?;
56        let digests = positions
57            .into_iter()
58            .map(|pos| self.get_node(pos).ok_or(Error::ElementPruned(pos)))
59            .collect::<Result<Vec<_>, _>>()?;
60        Ok(Proof { leaves, digests })
61    }
62}
63
64/// Information needed to flatten a chain of batches into a single [`super::batch::Changeset`].
65pub trait BatchChainInfo<D: Digest> {
66    /// Number of nodes in the original MMR that the batch chain was forked
67    /// from. This is constant through the entire chain.
68    fn base_size(&self) -> Position;
69
70    /// Collect all overwrites that target nodes in the original MMR
71    /// (i.e. positions < `base_size()`), walking from the deepest
72    /// ancestor to the current batch. Later batches overwrite earlier ones.
73    fn collect_overwrites(&self, into: &mut BTreeMap<Position, D>);
74}
commonware_storage/mmr/read.rs

commonware_storage/mmr/
read.rs
