miden_protocol/block/
smt_backend.rs

1use alloc::boxed::Box;
2use alloc::vec::Vec;
3
4use crate::Word;
5use crate::crypto::merkle::MerkleError;
6#[cfg(feature = "std")]
7use crate::crypto::merkle::smt::{LargeSmt, LargeSmtError, SmtStorage, SmtStorageReader};
8use crate::crypto::merkle::smt::{LeafIndex, MutationSet, SMT_DEPTH, Smt, SmtLeaf, SmtProof};
9
10// SMT BACKEND READER
11// ================================================================================================
12
13/// Abstracts over the read-only operations of the different SMT backends (e.g. [`Smt`] and
14/// [`LargeSmt`]), so that the block trees can work with either implementation transparently.
15///
16/// This trait is value-agnostic: leaves are stored as raw [`Word`]s. Trees that wrap a more
17/// specific value type (such as the nullifier tree) are responsible for converting to and from
18/// [`Word`] in their own accessors.
19///
20/// The method set is intentionally the superset required by both the account and nullifier trees,
21/// so a given tree only uses the subset relevant to it (e.g. the account tree iterates
22/// [`leaves`](Self::leaves), the nullifier tree iterates [`entries`](Self::entries)).
23///
24/// This trait contains only read-only methods. For write methods, see [`SmtBackend`].
25pub trait SmtBackendReader: Sized {
26    type Error: core::error::Error + Send + 'static;
27
28    /// Returns the number of leaves in the SMT.
29    fn num_leaves(&self) -> usize;
30
31    /// Returns the number of key-value entries in the SMT.
32    ///
33    /// This can exceed [`Self::num_leaves`] when keys collide into the same leaf.
34    fn num_entries(&self) -> usize;
35
36    /// Returns all leaves in the SMT as an iterator over leaf index and leaf pairs.
37    fn leaves(&self) -> Box<dyn Iterator<Item = (LeafIndex<SMT_DEPTH>, SmtLeaf)> + '_>;
38
39    /// Returns all key-value entries in the SMT.
40    fn entries(&self) -> Box<dyn Iterator<Item = (Word, Word)> + '_>;
41
42    /// Opens the leaf at the given key, returning a Merkle proof.
43    fn open(&self, key: &Word) -> SmtProof;
44
45    /// Returns the value associated with the given key.
46    fn get_value(&self, key: &Word) -> Word;
47
48    /// Returns the leaf at the given key.
49    fn get_leaf(&self, key: &Word) -> SmtLeaf;
50
51    /// Returns the root of the SMT.
52    fn root(&self) -> Word;
53}
54
55// SMT BACKEND
56// ================================================================================================
57
58/// Extension trait for [`SmtBackendReader`] that provides write methods.
59pub trait SmtBackend: SmtBackendReader {
60    /// Computes the mutation set required to apply the given updates to the SMT.
61    fn compute_mutations(
62        &self,
63        updates: Vec<(Word, Word)>,
64    ) -> Result<MutationSet<SMT_DEPTH, Word, Word>, Self::Error>;
65
66    /// Applies the given mutation set to the SMT.
67    fn apply_mutations(
68        &mut self,
69        set: MutationSet<SMT_DEPTH, Word, Word>,
70    ) -> Result<(), Self::Error>;
71
72    /// Applies the given mutation set to the SMT and returns the reverse mutation set.
73    ///
74    /// The reverse mutation set can be used to revert the changes made by this operation.
75    fn apply_mutations_with_reversion(
76        &mut self,
77        set: MutationSet<SMT_DEPTH, Word, Word>,
78    ) -> Result<MutationSet<SMT_DEPTH, Word, Word>, Self::Error>;
79
80    /// Inserts a key-value pair into the SMT, returning the previous value at that key.
81    fn insert(&mut self, key: Word, value: Word) -> Result<Word, Self::Error>;
82}
83
84// BACKEND READER IMPLEMENTATION FOR SMT
85// ================================================================================================
86
87impl SmtBackendReader for Smt {
88    type Error = MerkleError;
89
90    fn num_leaves(&self) -> usize {
91        Smt::num_leaves(self)
92    }
93
94    fn num_entries(&self) -> usize {
95        Smt::num_entries(self)
96    }
97
98    fn leaves(&self) -> Box<dyn Iterator<Item = (LeafIndex<SMT_DEPTH>, SmtLeaf)> + '_> {
99        Box::new(Smt::leaves(self).map(|(idx, leaf)| (idx, leaf.clone())))
100    }
101
102    fn entries(&self) -> Box<dyn Iterator<Item = (Word, Word)> + '_> {
103        Box::new(Smt::entries(self).map(|(k, v)| (*k, *v)))
104    }
105
106    fn open(&self, key: &Word) -> SmtProof {
107        Smt::open(self, key)
108    }
109
110    fn get_value(&self, key: &Word) -> Word {
111        Smt::get_value(self, key)
112    }
113
114    fn get_leaf(&self, key: &Word) -> SmtLeaf {
115        Smt::get_leaf(self, key)
116    }
117
118    fn root(&self) -> Word {
119        Smt::root(self)
120    }
121}
122
123// BACKEND WRITER IMPLEMENTATION FOR SMT
124// ================================================================================================
125
126impl SmtBackend for Smt {
127    fn compute_mutations(
128        &self,
129        updates: Vec<(Word, Word)>,
130    ) -> Result<MutationSet<SMT_DEPTH, Word, Word>, Self::Error> {
131        Smt::compute_mutations(self, updates)
132    }
133
134    fn apply_mutations(
135        &mut self,
136        set: MutationSet<SMT_DEPTH, Word, Word>,
137    ) -> Result<(), Self::Error> {
138        Smt::apply_mutations(self, set)
139    }
140
141    fn apply_mutations_with_reversion(
142        &mut self,
143        set: MutationSet<SMT_DEPTH, Word, Word>,
144    ) -> Result<MutationSet<SMT_DEPTH, Word, Word>, Self::Error> {
145        Smt::apply_mutations_with_reversion(self, set)
146    }
147
148    fn insert(&mut self, key: Word, value: Word) -> Result<Word, Self::Error> {
149        Smt::insert(self, key, value)
150    }
151}
152
153// BACKEND READER IMPLEMENTATION FOR LARGE SMT
154// ================================================================================================
155
156#[cfg(feature = "std")]
157impl<Backend> SmtBackendReader for LargeSmt<Backend>
158where
159    Backend: SmtStorageReader,
160{
161    type Error = MerkleError;
162
163    fn num_leaves(&self) -> usize {
164        LargeSmt::num_leaves(self)
165    }
166
167    fn num_entries(&self) -> usize {
168        LargeSmt::num_entries(self)
169    }
170
171    fn leaves(&self) -> Box<dyn Iterator<Item = (LeafIndex<SMT_DEPTH>, SmtLeaf)> + '_> {
172        Box::new(
173            LargeSmt::leaves(self)
174                .expect("Only IO can error out here")
175                .map(|leaf| leaf.expect("Only IO can error out here")),
176        )
177    }
178
179    fn entries(&self) -> Box<dyn Iterator<Item = (Word, Word)> + '_> {
180        // SAFETY: We expect here as only I/O errors can occur. Storage failures are considered
181        // unrecoverable at this layer. See issue #2010 for future error handling improvements.
182        Box::new(
183            LargeSmt::entries(self)
184                .expect("Storage I/O error accessing entries")
185                .map(|entry| entry.expect("Storage I/O error accessing entries")),
186        )
187    }
188
189    fn open(&self, key: &Word) -> SmtProof {
190        LargeSmt::open(self, key)
191    }
192
193    fn get_value(&self, key: &Word) -> Word {
194        LargeSmt::get_value(self, key)
195    }
196
197    fn get_leaf(&self, key: &Word) -> SmtLeaf {
198        LargeSmt::get_leaf(self, key)
199    }
200
201    fn root(&self) -> Word {
202        LargeSmt::root(self)
203    }
204}
205
206// BACKEND WRITER IMPLEMENTATION FOR LARGE SMT
207// ================================================================================================
208
209#[cfg(feature = "std")]
210impl<Backend> SmtBackend for LargeSmt<Backend>
211where
212    Backend: SmtStorage,
213{
214    fn compute_mutations(
215        &self,
216        updates: Vec<(Word, Word)>,
217    ) -> Result<MutationSet<SMT_DEPTH, Word, Word>, Self::Error> {
218        LargeSmt::compute_mutations(self, updates).map_err(large_smt_error_to_merkle_error)
219    }
220
221    fn apply_mutations(
222        &mut self,
223        set: MutationSet<SMT_DEPTH, Word, Word>,
224    ) -> Result<(), Self::Error> {
225        LargeSmt::apply_mutations(self, set).map_err(large_smt_error_to_merkle_error)
226    }
227
228    fn apply_mutations_with_reversion(
229        &mut self,
230        set: MutationSet<SMT_DEPTH, Word, Word>,
231    ) -> Result<MutationSet<SMT_DEPTH, Word, Word>, Self::Error> {
232        LargeSmt::apply_mutations_with_reversion(self, set).map_err(large_smt_error_to_merkle_error)
233    }
234
235    fn insert(&mut self, key: Word, value: Word) -> Result<Word, Self::Error> {
236        LargeSmt::insert(self, key, value)
237    }
238}
239
240// HELPER FUNCTIONS
241// ================================================================================================
242
243/// Converts a [`LargeSmtError`] into a [`MerkleError`].
244///
245/// Storage failures are treated as unrecoverable at this layer and cause a panic. See issue #2010
246/// for future error handling improvements.
247#[cfg(feature = "std")]
248pub(crate) fn large_smt_error_to_merkle_error(err: LargeSmtError) -> MerkleError {
249    match err {
250        LargeSmtError::Storage(storage_err) => {
251            panic!("Storage error encountered: {:?}", storage_err)
252        },
253        LargeSmtError::StorageNotEmpty => {
254            panic!("StorageNotEmpty error encountered: {:?}", err)
255        },
256        LargeSmtError::Merkle(merkle_err) => merkle_err,
257        LargeSmtError::RootMismatch { expected, actual } => MerkleError::ConflictingRoots {
258            expected_root: expected,
259            actual_root: actual,
260        },
261    }
262}
miden_protocol/block/smt_backend.rs

miden_protocol/block/
smt_backend.rs
