miden_objects/decoded/primitives/
merkle.rs

1pub use proto::primitives::DecodedMerklePath as MerklePath;
2
3use crate::decoded::VerificationError;
4use crate::{Verify, proto};
5
6#[cfg(test)]
7mod tests;
8
9impl Verify for MerklePath {
10    type Verified = miden_protocol::crypto::merkle::MerklePath;
11    type Error = core::convert::Infallible;
12    fn verify(self) -> Result<Self::Verified, Self::Error> {
13        Ok(Self::Verified::new(self.siblings.into_inner()))
14    }
15}
16
17pub use proto::primitives::DecodedSparseMerklePath as SparseMerklePath;
18
19impl Verify for SparseMerklePath {
20    type Verified = miden_protocol::crypto::merkle::SparseMerklePath;
21    type Error = miden_protocol::crypto::merkle::MerkleError;
22    fn verify(self) -> Result<Self::Verified, Self::Error> {
23        Self::Verified::from_parts(self.empty_nodes_mask, self.siblings.into_inner())
24    }
25}
26
27pub use proto::primitives::DecodedMmrDelta as MmrDelta;
28
29impl Verify for MmrDelta {
30    type Verified = miden_protocol::crypto::merkle::mmr::MmrDelta;
31    type Error = VerificationError;
32    fn verify(self) -> Result<Self::Verified, Self::Error> {
33        let forest = miden_protocol::crypto::merkle::mmr::Forest::new(self.forest.try_into()?)?;
34        Ok(Self::Verified {
35            forest,
36            data: self.update_data.into_inner(),
37        })
38    }
39}
40
41pub use proto::primitives::DecodedTrackedMmrLeaf as TrackedMmrLeaf;
42
43impl Verify for TrackedMmrLeaf {
44    type Verified = (u64, miden_protocol::Word, alloc::vec::Vec<miden_protocol::Word>);
45    type Error = core::convert::Infallible;
46    fn verify(self) -> Result<Self::Verified, Self::Error> {
47        Ok((self.position, self.leaf, self.path.into_inner()))
48    }
49}
50
51pub use proto::primitives::DecodedPartialMmr as PartialMmr;
52
53/// Checks reconstruction against the supplied peaks without authenticating those peaks.
54impl Verify for PartialMmr {
55    type Verified = miden_protocol::crypto::merkle::mmr::PartialMmr;
56    type Error = VerificationError;
57
58    fn verify(self) -> Result<Self::Verified, Self::Error> {
59        use miden_protocol::crypto::merkle::MerklePath;
60        use miden_protocol::crypto::merkle::mmr::{Forest, MmrPeaks, PartialMmr};
61
62        let size = usize::try_from(self.forest)?;
63        let peaks = MmrPeaks::new(Forest::new(size)?, self.peaks.into_inner())?;
64        let leaves = self.tracked_leaves.into_inner();
65
66        if !leaves.is_sorted_by(|a, b| a.position < b.position) {
67            return Err(PartialMmrError::LeafOrder.into());
68        }
69
70        if let Some(last_leaf) = leaves.last() {
71            let last_position = usize::try_from(last_leaf.position)?;
72            if last_position >= size {
73                return Err(PartialMmrError::Position { position: last_position, size }.into());
74            }
75        }
76
77        let mut mmr = PartialMmr::from_peaks(peaks);
78        for tracked in leaves {
79            let position = usize::try_from(tracked.position)?;
80            mmr.track(position, tracked.leaf, &MerklePath::new(tracked.path.into_inner()))?;
81        }
82        Ok(mmr)
83    }
84}
85
86#[derive(Debug, thiserror::Error)]
87#[non_exhaustive]
88pub enum PartialMmrError {
89    #[error("tracked leaf position {position} is outside forest of size {size}")]
90    Position { position: usize, size: usize },
91    #[error("tracked leaf positions must be unique and strictly increasing")]
92    LeafOrder,
93}
miden_objects/decoded/primitives/merkle.rs

miden_objects/decoded/primitives/
merkle.rs
