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

miden_objects/decoded/primitives/
smt.rs
