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        LargeSmt::num_entries(self)
118    }
119
120    fn entries(&self) -> Box<dyn Iterator<Item = (Word, Word)> + '_> {
121        // SAFETY: We expect here as only I/O errors can occur. Storage failures are considered
122        // unrecoverable at this layer. See issue #2010 for future error handling improvements.
123        Box::new(LargeSmt::entries(self).expect("Storage I/O error accessing entries"))
124    }
125
126    fn open(&self, key: &Word) -> SmtProof {
127        LargeSmt::open(self, key)
128    }
129
130    fn apply_mutations(
131        &mut self,
132        set: MutationSet<SMT_DEPTH, Word, Word>,
133    ) -> Result<(), Self::Error> {
134        LargeSmt::apply_mutations(self, set).map_err(large_smt_error_to_merkle_error)
135    }
136
137    fn compute_mutations(
138        &self,
139        updates: impl IntoIterator<Item = (Word, Word)>,
140    ) -> Result<MutationSet<SMT_DEPTH, Word, Word>, Self::Error> {
141        LargeSmt::compute_mutations(self, updates).map_err(large_smt_error_to_merkle_error)
142    }
143
144    fn insert(&mut self, key: Word, value: NullifierBlock) -> Result<NullifierBlock, Self::Error> {
145        LargeSmt::insert(self, key, value.into()).map(|word| {
146            NullifierBlock::try_from(word).expect("SMT should only store valid NullifierBlocks")
147        })
148    }
149
150    fn get_value(&self, key: &Word) -> NullifierBlock {
151        LargeSmt::get_value(self, key)
152            .try_into()
153            .expect("unable to create NullifierBlock")
154    }
155
156    fn root(&self) -> Word {
157        LargeSmt::root(self)
158    }
159}
160
161// CONVENIENCE METHODS
162// ================================================================================================
163
164impl NullifierTree<Smt> {
165    /// Creates a new nullifier tree from the provided entries.
166    ///
167    /// This is a convenience method that creates an SMT backend with the provided entries and
168    /// wraps it in a NullifierTree.
169    ///
170    /// # Errors
171    ///
172    /// Returns an error if:
173    /// - the provided entries contain multiple block numbers for the same nullifier.
174    pub fn with_entries(
175        entries: impl IntoIterator<Item = (Nullifier, BlockNumber)>,
176    ) -> Result<Self, NullifierTreeError> {
177        let leaves = entries.into_iter().map(|(nullifier, block_num)| {
178            (nullifier.as_word(), NullifierBlock::from(block_num).into())
179        });
180
181        let smt = Smt::with_entries(leaves)
182            .map_err(NullifierTreeError::DuplicateNullifierBlockNumbers)?;
183
184        Ok(Self::new_unchecked(smt))
185    }
186}
187
188#[cfg(feature = "std")]
189impl<Backend> NullifierTree<LargeSmt<Backend>>
190where
191    Backend: SmtStorage,
192{
193    /// Creates a new nullifier tree from the provided entries using the given storage backend
194    ///
195    /// This is a convenience method that creates an SMT on the provided storage backend using the
196    /// provided entries and wraps it in a NullifierTree.
197    ///
198    /// # Errors
199    ///
200    /// Returns an error if:
201    /// - the provided entries contain multiple block numbers for the same nullifier.
202    /// - a storage error is encountered.
203    pub fn with_storage_from_entries(
204        storage: Backend,
205        entries: impl IntoIterator<Item = (Nullifier, BlockNumber)>,
206    ) -> Result<Self, NullifierTreeError> {
207        let leaves = entries.into_iter().map(|(nullifier, block_num)| {
208            (nullifier.as_word(), NullifierBlock::from(block_num).into())
209        });
210
211        let smt = LargeSmt::<Backend>::with_entries(storage, leaves)
212            .map_err(large_smt_error_to_merkle_error)
213            .map_err(NullifierTreeError::DuplicateNullifierBlockNumbers)?;
214
215        Ok(Self::new_unchecked(smt))
216    }
217}
218
219// HELPER FUNCTIONS
220// ================================================================================================
221
222#[cfg(feature = "std")]
223pub(super) fn large_smt_error_to_merkle_error(err: LargeSmtError) -> MerkleError {
224    match err {
225        LargeSmtError::Storage(storage_err) => {
226            panic!("Storage error encountered: {:?}", storage_err)
227        },
228        LargeSmtError::StorageNotEmpty => {
229            panic!("StorageNotEmpty error encountered: {:?}", err)
230        },
231        LargeSmtError::Merkle(merkle_err) => merkle_err,
232        LargeSmtError::RootMismatch { expected, actual } => MerkleError::ConflictingRoots {
233            expected_root: expected,
234            actual_root: actual,
235        },
236    }
237}
miden_protocol/block/nullifier_tree/backend.rs

miden_protocol/block/nullifier_tree/
backend.rs
