commonware_storage/merkle/
read.rs

1//! Shared read-only trait for merkleized data structures.
2
3use crate::merkle::{hasher::Hasher, proof::Proof, Family, Location, Position};
4use alloc::sync::Arc;
5use commonware_cryptography::Digest;
6use core::ops::Range;
7
8/// Read-only interface for a merkleized data structure.
9pub trait Readable: Send + Sync {
10    /// The Merkle family implemented by this structure.
11    type Family: Family;
12
13    /// The digest type used by this structure.
14    type Digest: Digest;
15
16    /// The error type returned by proof construction.
17    type Error;
18
19    /// Total number of nodes (retained + pruned).
20    fn size(&self) -> Position<Self::Family>;
21
22    /// Digest of the node at `pos`, or `None` if pruned / out of bounds.
23    fn get_node(&self, pos: Position<Self::Family>) -> Option<Self::Digest>;
24
25    /// Root digest of the structure.
26    fn root(&self) -> Self::Digest;
27
28    /// Leaf location up to which pruning has been performed, or 0 if never pruned.
29    fn pruning_boundary(&self) -> Location<Self::Family>;
30
31    /// Inclusion proof for the element at `loc`.
32    fn proof(
33        &self,
34        hasher: &impl Hasher<Self::Family, Digest = Self::Digest>,
35        loc: Location<Self::Family>,
36    ) -> Result<Proof<Self::Family, Self::Digest>, Self::Error>;
37
38    /// Inclusion proof for all elements in `range`.
39    fn range_proof(
40        &self,
41        hasher: &impl Hasher<Self::Family, Digest = Self::Digest>,
42        range: Range<Location<Self::Family>>,
43    ) -> Result<Proof<Self::Family, Self::Digest>, Self::Error>;
44
45    /// Total number of leaves.
46    fn leaves(&self) -> Location<Self::Family> {
47        Location::try_from(self.size()).expect("invalid merkle size")
48    }
49
50    /// `[start, end)` range of retained leaf locations.
51    fn bounds(&self) -> Range<Location<Self::Family>> {
52        self.pruning_boundary()..self.leaves()
53    }
54}
55
56impl<T: Readable> Readable for Arc<T> {
57    type Family = T::Family;
58    type Digest = T::Digest;
59    type Error = T::Error;
60
61    fn size(&self) -> Position<Self::Family> {
62        (**self).size()
63    }
64
65    fn get_node(&self, pos: Position<Self::Family>) -> Option<Self::Digest> {
66        (**self).get_node(pos)
67    }
68
69    fn root(&self) -> Self::Digest {
70        (**self).root()
71    }
72
73    fn pruning_boundary(&self) -> Location<Self::Family> {
74        (**self).pruning_boundary()
75    }
76
77    fn proof(
78        &self,
79        hasher: &impl Hasher<Self::Family, Digest = Self::Digest>,
80        loc: Location<Self::Family>,
81    ) -> Result<Proof<Self::Family, Self::Digest>, Self::Error> {
82        (**self).proof(hasher, loc)
83    }
84
85    fn range_proof(
86        &self,
87        hasher: &impl Hasher<Self::Family, Digest = Self::Digest>,
88        range: Range<Location<Self::Family>>,
89    ) -> Result<Proof<Self::Family, Self::Digest>, Self::Error> {
90        (**self).range_proof(hasher, range)
91    }
92}
commonware_storage/merkle/read.rs

commonware_storage/merkle/
read.rs
