miden_objects/decoded/primitives/
smt.rs

1use miden_protobuf::unwrap_infallible;
2pub use proto::primitives::DecodedSmtLeafEntry as SmtLeafEntry;
3
4use crate::decoded::VerificationError;
5use crate::{Verify, proto};
6
7#[cfg(test)]
8mod tests;
9
10impl Verify for SmtLeafEntry {
11    type Verified = (miden_protocol::Word, miden_protocol::Word);
12    type Error = core::convert::Infallible;
13    fn verify(self) -> Result<Self::Verified, Self::Error> {
14        Ok((self.key, self.value))
15    }
16}
17
18pub use proto::primitives::DecodedPartialSmtNode as PartialSmtNode;
19
20impl Verify for PartialSmtNode {
21    type Verified = (u64, miden_protocol::Word);
22    type Error = core::convert::Infallible;
23    fn verify(self) -> Result<Self::Verified, Self::Error> {
24        Ok((self.index, self.digest))
25    }
26}
27
28pub use proto::primitives::DecodedPartialSmtNodeLevel as PartialSmtNodeLevel;
29
30impl Verify for PartialSmtNodeLevel {
31    type Verified = (u32, alloc::vec::Vec<(u64, miden_protocol::Word)>);
32    type Error = core::convert::Infallible;
33    fn verify(self) -> Result<Self::Verified, Self::Error> {
34        Ok((
35            self.depth,
36            self.nodes.into_iter().map(Verify::verify).collect::<Result<_, _>>()?,
37        ))
38    }
39}
40
41pub use proto::primitives::DecodedIndexedDigest as IndexedDigest;
42
43impl Verify for IndexedDigest {
44    type Verified = (u64, miden_protocol::Word);
45    type Error = core::convert::Infallible;
46    fn verify(self) -> Result<Self::Verified, Self::Error> {
47        Ok((self.index, self.value))
48    }
49}
50
51pub use proto::primitives::DecodedSmtLeafEntryList as SmtLeafEntryList;
52
53impl Verify for SmtLeafEntryList {
54    type Verified = alloc::vec::Vec<(miden_protocol::Word, miden_protocol::Word)>;
55    type Error = core::convert::Infallible;
56    fn verify(self) -> Result<Self::Verified, Self::Error> {
57        self.entries.into_iter().map(Verify::verify).collect()
58    }
59}
60
61pub use proto::primitives::DecodedSmtLeaf as SmtLeaf;
62
63impl Verify for SmtLeaf {
64    type Verified = miden_protocol::crypto::merkle::smt::SmtLeaf;
65    type Error = miden_protocol::crypto::merkle::smt::SmtLeafError;
66    fn verify(self) -> Result<Self::Verified, Self::Error> {
67        use miden_protocol::crypto::merkle::smt::LeafIndex;
68        use proto::primitives::smt_leaf::DecodedLeaf;
69        match self.leaf {
70            DecodedLeaf::EmptyLeafIndex(index) => {
71                Ok(Self::Verified::new_empty(LeafIndex::new_max_depth(index)))
72            },
73            DecodedLeaf::Single(entry) => Ok(Self::Verified::new_single(entry.key, entry.value)),
74            DecodedLeaf::Multiple(entries) => {
75                Self::Verified::new_multiple(unwrap_infallible(entries.verify()))
76            },
77        }
78    }
79}
80
81pub use proto::primitives::DecodedIndexedSmtLeaf as IndexedSmtLeaf;
82
83impl Verify for IndexedSmtLeaf {
84    type Verified = (u64, miden_protocol::crypto::merkle::smt::SmtLeaf);
85    type Error = miden_protocol::crypto::merkle::smt::SmtLeafError;
86    fn verify(self) -> Result<Self::Verified, Self::Error> {
87        Ok((self.index, self.leaf.verify()?))
88    }
89}
90
91pub use proto::primitives::DecodedSmtOpening as SmtOpening;
92
93impl Verify for SmtOpening {
94    type Verified = miden_protocol::crypto::merkle::smt::SmtProof;
95    type Error = VerificationError;
96    fn verify(self) -> Result<Self::Verified, Self::Error> {
97        Ok(Self::Verified::new(self.path.verify()?, self.leaf.verify()?)?)
98    }
99}
100
101pub use proto::primitives::DecodedPartialSmt as PartialSmt;
102
103impl Verify for PartialSmt {
104    type Verified = miden_protocol::crypto::merkle::smt::PartialSmt;
105    type Error = VerificationError;
106    fn verify(self) -> Result<Self::Verified, Self::Error> {
107        Ok(Self::Verified::from_unique_nodes(self.into_unique_nodes()?)?)
108    }
109}
110
111impl PartialSmt {
112    /// Checks duplicate indices and constructs reconstruction input, without checking its root.
113    pub fn into_unique_nodes(
114        self,
115    ) -> Result<miden_protocol::crypto::merkle::smt::UniqueNodes, VerificationError> {
116        use alloc::collections::{BTreeMap, BTreeSet};
117
118        use miden_protocol::crypto::merkle::NodeIndex;
119        use miden_protocol::crypto::merkle::smt::{SMT_DEPTH, UniqueNodes};
120        let mut depths = BTreeSet::new();
121        let mut nodes = BTreeMap::new();
122        for level in self.node_levels {
123            let depth = u8::try_from(level.depth)?;
124            if depth == 0 || depth >= SMT_DEPTH {
125                return Err(PartialSmtError::Depth(depth).into());
126            }
127            if !depths.insert(depth) {
128                return Err(PartialSmtError::DuplicateDepth(depth).into());
129            }
130            for node in level.nodes {
131                let index = NodeIndex::new(depth, node.index)?;
132                if nodes.insert(index, node.digest).is_some() {
133                    return Err(PartialSmtError::DuplicateNode { index: node.index, depth }.into());
134                }
135            }
136        }
137        let mut leaves = BTreeMap::new();
138        for indexed in self.leaves {
139            let (index, leaf) = indexed.verify()?;
140            if leaves.insert(index, leaf).is_some() {
141                return Err(PartialSmtError::DuplicateLeaf(index).into());
142            }
143        }
144        let mut value_only_leaves = BTreeMap::new();
145        for indexed in self.value_only_leaves {
146            if leaves.contains_key(&indexed.index) {
147                return Err(PartialSmtError::OverlappingLeaf(indexed.index).into());
148            }
149            if value_only_leaves.insert(indexed.index, indexed.value).is_some() {
150                return Err(PartialSmtError::DuplicateValueOnlyLeaf(indexed.index).into());
151            }
152        }
153        Ok(UniqueNodes {
154            root: self.root,
155            nodes,
156            leaves,
157            value_only_leaves,
158        })
159    }
160}
161
162#[derive(Debug, thiserror::Error)]
163pub enum PartialSmtError {
164    #[error("partial SMT node depth {0} must be in the range 1..64")]
165    Depth(u8),
166    #[error("partial SMT contains duplicate node depth {0}")]
167    DuplicateDepth(u8),
168    #[error("partial SMT contains duplicate node index {index} at depth {depth}")]
169    DuplicateNode { index: u64, depth: u8 },
170    #[error("partial SMT contains duplicate leaf index {0}")]
171    DuplicateLeaf(u64),
172    #[error("partial SMT contains duplicate value-only leaf index {0}")]
173    DuplicateValueOnlyLeaf(u64),
174    #[error("partial SMT leaf index {0} has both a leaf and a value-only leaf")]
175    OverlappingLeaf(u64),
176}
miden_objects/decoded/primitives/smt.rs

miden_objects/decoded/primitives/
smt.rs
