miden_objects/decoded/primitives/
merkle.rs

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

miden_objects/decoded/primitives/
merkle.rs
