miden_protocol/block/nullifier_tree/
backend.rs

1use alloc::boxed::Box;
2
3use super::{BlockNumber, Nullifier, NullifierBlock, NullifierTree, NullifierTreeError};
4use crate::Word;
5use crate::crypto::merkle::MerkleError;
6#[cfg(feature = "std")]
7use crate::crypto::merkle::smt::{LargeSmt, LargeSmtError, SmtStorage};
8use crate::crypto::merkle::smt::{MutationSet, SMT_DEPTH, Smt, SmtProof};
9
10// NULLIFIER TREE BACKEND
11// ================================================================================================
12
13/// This trait abstracts over different SMT backends (e.g., `Smt` and `LargeSmt`) to allow
14/// the `NullifierTree` to work with either implementation transparently.
15///
16/// Users should instantiate the backend directly (potentially with entries) and then
17/// pass it to [`NullifierTree::new_unchecked`].
18///
19/// # Invariants
20///
21/// Assumes the provided SMT upholds the guarantees of the [`NullifierTree`]. Specifically:
22/// - Nullifiers are only spent once and their block numbers do not change.
23/// - Nullifier leaf values must be valid according to [`NullifierBlock`].
24pub trait NullifierTreeBackend: Sized {
25    type Error: core::error::Error + Send + 'static;
26
27    /// Returns the number of entries in the SMT.
28    fn num_entries(&self) -> usize;
29
30    /// Returns all entries in the SMT as an iterator over key-value pairs.
31    fn entries(&self) -> Box<dyn Iterator<Item = (Word, Word)> + '_>;
32
33    /// Opens the leaf at the given key, returning a Merkle proof.
34    fn open(&self, key: &Word) -> SmtProof;
35
36    /// Applies the given mutation set to the SMT.
37    fn apply_mutations(
38        &mut self,
39        set: MutationSet<SMT_DEPTH, Word, Word>,
40    ) -> Result<(), Self::Error>;
41
42    /// Computes the mutation set required to apply the given updates to the SMT.
43    fn compute_mutations(
44        &self,
45        updates: impl IntoIterator<Item = (Word, Word)>,
46    ) -> Result<MutationSet<SMT_DEPTH, Word, Word>, Self::Error>;
47
48    /// Inserts a key-value pair into the SMT, returning the previous value at that key.
49    fn insert(&mut self, key: Word, value: NullifierBlock) -> Result<NullifierBlock, Self::Error>;
50
51    /// Returns the value associated with the given key.
52    fn get_value(&self, key: &Word) -> NullifierBlock;
53
54    /// Returns the root of the SMT.
55    fn root(&self) -> Word;
56}
57
58// BACKEND IMPLEMENTATION FOR SMT
59// ================================================================================================
60
61impl NullifierTreeBackend for Smt {
62    type Error = MerkleError;
63
64    fn num_entries(&self) -> usize {
65        Smt::num_entries(self)
66    }
67
68    fn entries(&self) -> Box<dyn Iterator<Item = (Word, Word)> + '_> {
69        Box::new(Smt::entries(self).map(|(k, v)| (*k, *v)))
70    }
71
72    fn open(&self, key: &Word) -> SmtProof {
73        Smt::open(self, key)
74    }
75
76    fn apply_mutations(
77        &mut self,
78        set: MutationSet<SMT_DEPTH, Word, Word>,
79    ) -> Result<(), Self::Error> {
80        Smt::apply_mutations(self, set)
81    }
82
83    fn compute_mutations(
84        &self,
85        updates: impl IntoIterator<Item = (Word, Word)>,
86    ) -> Result<MutationSet<SMT_DEPTH, Word, Word>, Self::Error> {
87        Smt::compute_mutations(self, updates)
88    }
89
90    fn insert(&mut self, key: Word, value: NullifierBlock) -> Result<NullifierBlock, Self::Error> {
91        Smt::insert(self, key, value.into()).map(|word| {
92            NullifierBlock::try_from(word).expect("SMT should only store valid NullifierBlocks")
93        })
94    }
95
96    fn get_value(&self, key: &Word) -> NullifierBlock {
97        NullifierBlock::new(Smt::get_value(self, key))
98            .expect("SMT should only store valid NullifierBlocks")
99    }
100
101    fn root(&self) -> Word {
102        Smt::root(self)
103    }
104}
105
106// NULLIFIER TREE BACKEND FOR LARGE SMT
107// ================================================================================================
108
109#[cfg(feature = "std")]
110impl<Backend> NullifierTreeBackend for LargeSmt<Backend>
111where
112    Backend: SmtStorage,
113{
114    type Error = MerkleError;
115
116    fn num_entries(&self) -> usize {
117        // SAFETY: We panic on storage errors here as they represent unrecoverable I/O failures.
118        // This maintains API compatibility with the non-fallible Smt::num_entries().
119        // See issue #2010 for future improvements to error handling.
120        LargeSmt::num_entries(self)
121            .map_err(large_smt_error_to_merkle_error)
122            .expect("Storage I/O error accessing num_entries")
123    }
124
125    fn entries(&self) -> Box<dyn Iterator<Item = (Word, Word)> + '_> {
126        // SAFETY: We expect here as only I/O errors can occur. Storage failures are considered
127        // unrecoverable at this layer. See issue #2010 for future error handling improvements.
128        Box::new(LargeSmt::entries(self).expect("Storage I/O error accessing entries"))
129    }
130
131    fn open(&self, key: &Word) -> SmtProof {
132        LargeSmt::open(self, key)
133    }
134
135    fn apply_mutations(
136        &mut self,
137        set: MutationSet<SMT_DEPTH, Word, Word>,
138    ) -> Result<(), Self::Error> {
139        LargeSmt::apply_mutations(self, set).map_err(large_smt_error_to_merkle_error)
140    }
141
142    fn compute_mutations(
143        &self,
144        updates: impl IntoIterator<Item = (Word, Word)>,
145    ) -> Result<MutationSet<SMT_DEPTH, Word, Word>, Self::Error> {
146        LargeSmt::compute_mutations(self, updates).map_err(large_smt_error_to_merkle_error)
147    }
148
149    fn insert(&mut self, key: Word, value: NullifierBlock) -> Result<NullifierBlock, Self::Error> {
150        LargeSmt::insert(self, key, value.into()).map(|word| {
151            NullifierBlock::try_from(word).expect("SMT should only store valid NullifierBlocks")
152        })
153    }
154
155    fn get_value(&self, key: &Word) -> NullifierBlock {
156        LargeSmt::get_value(self, key)
157            .try_into()
158            .expect("unable to create NullifierBlock")
159    }
160
161    fn root(&self) -> Word {
162        LargeSmt::root(self)
163    }
164}
165
166// CONVENIENCE METHODS
167// ================================================================================================
168
169impl NullifierTree<Smt> {
170    /// Creates a new nullifier tree from the provided entries.
171    ///
172    /// This is a convenience method that creates an SMT backend with the provided entries and
173    /// wraps it in a NullifierTree.
174    ///
175    /// # Errors
176    ///
177    /// Returns an error if:
178    /// - the provided entries contain multiple block numbers for the same nullifier.
179    pub fn with_entries(
180        entries: impl IntoIterator<Item = (Nullifier, BlockNumber)>,
181    ) -> Result<Self, NullifierTreeError> {
182        let leaves = entries.into_iter().map(|(nullifier, block_num)| {
183            (nullifier.as_word(), NullifierBlock::from(block_num).into())
184        });
185
186        let smt = Smt::with_entries(leaves)
187            .map_err(NullifierTreeError::DuplicateNullifierBlockNumbers)?;
188
189        Ok(Self::new_unchecked(smt))
190    }
191}
192
193#[cfg(feature = "std")]
194impl<Backend> NullifierTree<LargeSmt<Backend>>
195where
196    Backend: SmtStorage,
197{
198    /// Creates a new nullifier tree from the provided entries using the given storage backend
199    ///
200    /// This is a convenience method that creates an SMT on the provided storage backend using the
201    /// provided entries and wraps it in a NullifierTree.
202    ///
203    /// # Errors
204    ///
205    /// Returns an error if:
206    /// - the provided entries contain multiple block numbers for the same nullifier.
207    /// - a storage error is encountered.
208    pub fn with_storage_from_entries(
209        storage: Backend,
210        entries: impl IntoIterator<Item = (Nullifier, BlockNumber)>,
211    ) -> Result<Self, NullifierTreeError> {
212        let leaves = entries.into_iter().map(|(nullifier, block_num)| {
213            (nullifier.as_word(), NullifierBlock::from(block_num).into())
214        });
215
216        let smt = LargeSmt::<Backend>::with_entries(storage, leaves)
217            .map_err(large_smt_error_to_merkle_error)
218            .map_err(NullifierTreeError::DuplicateNullifierBlockNumbers)?;
219
220        Ok(Self::new_unchecked(smt))
221    }
222}
223
224// HELPER FUNCTIONS
225// ================================================================================================
226
227#[cfg(feature = "std")]
228pub(super) fn large_smt_error_to_merkle_error(err: LargeSmtError) -> MerkleError {
229    match err {
230        LargeSmtError::Storage(storage_err) => {
231            panic!("Storage error encountered: {:?}", storage_err)
232        },
233        LargeSmtError::Merkle(merkle_err) => merkle_err,
234    }
235}
miden_protocol/block/nullifier_tree/backend.rs

miden_protocol/block/nullifier_tree/
backend.rs
