miden_objects/block/
nullifier_tree.rs

1use alloc::string::ToString;
2use alloc::vec::Vec;
3
4use miden_core::EMPTY_WORD;
5use miden_core::utils::{ByteReader, ByteWriter, Deserializable, Serializable};
6use miden_processor::DeserializationError;
7
8use crate::Word;
9use crate::block::{BlockNumber, NullifierWitness};
10use crate::crypto::merkle::{MutationSet, SMT_DEPTH, Smt};
11use crate::errors::NullifierTreeError;
12use crate::note::Nullifier;
13
14/// The sparse merkle tree of all nullifiers in the blockchain.
15///
16/// A nullifier can only ever be spent once and its value in the tree is the block number at which
17/// it was spent.
18///
19/// The tree guarantees that once a nullifier has been inserted into the tree, its block number does
20/// not change. Note that inserting the nullifier multiple times with the same block number is
21/// valid.
22#[derive(Debug, Clone, PartialEq, Eq)]
23pub struct NullifierTree {
24    smt: Smt,
25}
26
27impl NullifierTree {
28    // CONSTANTS
29    // --------------------------------------------------------------------------------------------
30
31    /// The depth of the nullifier tree.
32    pub const DEPTH: u8 = SMT_DEPTH;
33
34    /// The value of an unspent nullifier in the tree.
35    pub const UNSPENT_NULLIFIER: Word = EMPTY_WORD;
36
37    // CONSTRUCTORS
38    // --------------------------------------------------------------------------------------------
39
40    /// Creates a new, empty nullifier tree.
41    pub fn new() -> Self {
42        Self { smt: Smt::new() }
43    }
44
45    /// Construct a new nullifier tree from the provided entries.
46    ///
47    /// # Errors
48    ///
49    /// Returns an error if:
50    /// - the provided entries contain multiple block numbers for the same nullifier.
51    pub fn with_entries(
52        entries: impl IntoIterator<Item = (Nullifier, BlockNumber)>,
53    ) -> Result<Self, NullifierTreeError> {
54        let leaves = entries.into_iter().map(|(nullifier, block_num)| {
55            (nullifier.as_word(), Self::block_num_to_leaf_value(block_num))
56        });
57
58        let smt = Smt::with_entries(leaves)
59            .map_err(NullifierTreeError::DuplicateNullifierBlockNumbers)?;
60
61        Ok(Self { smt })
62    }
63
64    // PUBLIC ACCESSORS
65    // --------------------------------------------------------------------------------------------
66
67    /// Returns the root of the nullifier SMT.
68    pub fn root(&self) -> Word {
69        self.smt.root()
70    }
71
72    /// Returns the number of spent nullifiers in this tree.
73    pub fn num_nullifiers(&self) -> usize {
74        self.smt.num_entries()
75    }
76
77    /// Returns an iterator over the nullifiers and their block numbers in the tree.
78    pub fn entries(&self) -> impl Iterator<Item = (Nullifier, BlockNumber)> {
79        self.smt.entries().map(|(nullifier, block_num)| {
80            (Nullifier::from(*nullifier), Self::leaf_value_to_block_num(*block_num))
81        })
82    }
83
84    /// Returns a [`NullifierWitness`] of the leaf associated with the `nullifier`.
85    ///
86    /// Conceptually, such a witness is a Merkle path to the leaf, as well as the leaf itself.
87    ///
88    /// This witness is a proof of the current block number of the given nullifier. If that block
89    /// number is zero, it proves that the nullifier is unspent.
90    pub fn open(&self, nullifier: &Nullifier) -> NullifierWitness {
91        NullifierWitness::new(self.smt.open(&nullifier.as_word()))
92    }
93
94    /// Returns the block number for the given nullifier or `None` if the nullifier wasn't spent
95    /// yet.
96    pub fn get_block_num(&self, nullifier: &Nullifier) -> Option<BlockNumber> {
97        let value = self.smt.get_value(&nullifier.as_word());
98        if value == Self::UNSPENT_NULLIFIER {
99            return None;
100        }
101
102        Some(Self::leaf_value_to_block_num(value))
103    }
104
105    /// Computes a mutation set resulting from inserting the provided nullifiers into this nullifier
106    /// tree.
107    ///
108    /// # Errors
109    ///
110    /// Returns an error if:
111    /// - a nullifier in the provided iterator was already spent.
112    pub fn compute_mutations<I>(
113        &self,
114        nullifiers: impl IntoIterator<Item = (Nullifier, BlockNumber), IntoIter = I>,
115    ) -> Result<NullifierMutationSet, NullifierTreeError>
116    where
117        I: Iterator<Item = (Nullifier, BlockNumber)> + Clone,
118    {
119        let nullifiers = nullifiers.into_iter();
120        for (nullifier, _) in nullifiers.clone() {
121            if self.get_block_num(&nullifier).is_some() {
122                return Err(NullifierTreeError::NullifierAlreadySpent(nullifier));
123            }
124        }
125
126        let mutation_set =
127            self.smt.compute_mutations(nullifiers.into_iter().map(|(nullifier, block_num)| {
128                (nullifier.as_word(), Self::block_num_to_leaf_value(block_num))
129            }));
130
131        Ok(NullifierMutationSet::new(mutation_set))
132    }
133
134    // PUBLIC MUTATORS
135    // --------------------------------------------------------------------------------------------
136
137    /// Marks the given nullifier as spent at the given block number.
138    ///
139    /// # Errors
140    ///
141    /// Returns an error if:
142    /// - the nullifier was already spent.
143    pub fn mark_spent(
144        &mut self,
145        nullifier: Nullifier,
146        block_num: BlockNumber,
147    ) -> Result<(), NullifierTreeError> {
148        let prev_nullifier_value =
149            self.smt.insert(nullifier.as_word(), Self::block_num_to_leaf_value(block_num));
150
151        if prev_nullifier_value != Self::UNSPENT_NULLIFIER {
152            Err(NullifierTreeError::NullifierAlreadySpent(nullifier))
153        } else {
154            Ok(())
155        }
156    }
157
158    /// Applies mutations to the nullifier tree.
159    ///
160    /// # Errors
161    ///
162    /// Returns an error if:
163    /// - `mutations` was computed on a tree with a different root than this one.
164    pub fn apply_mutations(
165        &mut self,
166        mutations: NullifierMutationSet,
167    ) -> Result<(), NullifierTreeError> {
168        self.smt
169            .apply_mutations(mutations.into_mutation_set())
170            .map_err(NullifierTreeError::TreeRootConflict)
171    }
172
173    // HELPER FUNCTIONS
174    // --------------------------------------------------------------------------------------------
175
176    /// Returns the nullifier's leaf value in the SMT by its block number.
177    pub(super) fn block_num_to_leaf_value(block: BlockNumber) -> Word {
178        Word::from([block.as_u32(), 0, 0, 0])
179    }
180
181    /// Given the leaf value of the nullifier SMT, returns the nullifier's block number.
182    ///
183    /// There are no nullifiers in the genesis block. The value zero is instead used to signal
184    /// absence of a value.
185    fn leaf_value_to_block_num(value: Word) -> BlockNumber {
186        let block_num: u32 =
187            value[0].as_int().try_into().expect("invalid block number found in store");
188
189        block_num.into()
190    }
191}
192
193impl Default for NullifierTree {
194    fn default() -> Self {
195        Self::new()
196    }
197}
198
199// SERIALIZATION
200// ================================================================================================
201
202impl Serializable for NullifierTree {
203    fn write_into<W: ByteWriter>(&self, target: &mut W) {
204        self.entries().collect::<Vec<_>>().write_into(target);
205    }
206}
207
208impl Deserializable for NullifierTree {
209    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
210        let entries = Vec::<(Nullifier, BlockNumber)>::read_from(source)?;
211        Self::with_entries(entries)
212            .map_err(|err| DeserializationError::InvalidValue(err.to_string()))
213    }
214}
215
216// NULLIFIER MUTATION SET
217// ================================================================================================
218
219/// A newtype wrapper around a [`MutationSet`] for use in the [`NullifierTree`].
220///
221/// It guarantees that applying the contained mutations will result in a nullifier tree where
222/// nullifier's block numbers are not updated (except if they were unspent before), ensuring that
223/// nullifiers are only spent once.
224///
225/// It is returned by and used in methods on the [`NullifierTree`].
226#[derive(Debug, Clone, PartialEq, Eq)]
227pub struct NullifierMutationSet {
228    mutation_set: MutationSet<{ NullifierTree::DEPTH }, Word, Word>,
229}
230
231impl NullifierMutationSet {
232    // CONSTRUCTORS
233    // --------------------------------------------------------------------------------------------
234
235    /// Creates a new [`AccountMutationSet`] from the provided raw mutation set.
236    fn new(mutation_set: MutationSet<{ NullifierTree::DEPTH }, Word, Word>) -> Self {
237        Self { mutation_set }
238    }
239
240    // PUBLIC ACCESSORS
241    // --------------------------------------------------------------------------------------------
242
243    /// Returns a reference to the underlying [`MutationSet`].
244    pub fn as_mutation_set(&self) -> &MutationSet<{ NullifierTree::DEPTH }, Word, Word> {
245        &self.mutation_set
246    }
247
248    // PUBLIC MUTATORS
249    // --------------------------------------------------------------------------------------------
250
251    /// Consumes self and returns the underlying [`MutationSet`].
252    pub fn into_mutation_set(self) -> MutationSet<{ NullifierTree::DEPTH }, Word, Word> {
253        self.mutation_set
254    }
255}
256
257// TESTS
258// ================================================================================================
259
260#[cfg(test)]
261mod tests {
262    use assert_matches::assert_matches;
263
264    use super::NullifierTree;
265    use crate::block::BlockNumber;
266    use crate::note::Nullifier;
267    use crate::{NullifierTreeError, Word};
268
269    #[test]
270    fn leaf_value_encoding() {
271        let block_num = 123;
272        let nullifier_value = NullifierTree::block_num_to_leaf_value(block_num.into());
273        assert_eq!(nullifier_value, Word::from([block_num, 0, 0, 0u32]));
274    }
275
276    #[test]
277    fn leaf_value_decoding() {
278        let block_num = 123;
279        let nullifier_value = Word::from([block_num, 0, 0, 0u32]);
280        let decoded_block_num = NullifierTree::leaf_value_to_block_num(nullifier_value);
281
282        assert_eq!(decoded_block_num, block_num.into());
283    }
284
285    #[test]
286    fn apply_mutations() {
287        let nullifier1 = Nullifier::dummy(1);
288        let nullifier2 = Nullifier::dummy(2);
289        let nullifier3 = Nullifier::dummy(3);
290
291        let block1 = BlockNumber::from(1);
292        let block2 = BlockNumber::from(2);
293        let block3 = BlockNumber::from(3);
294
295        let mut tree = NullifierTree::with_entries([(nullifier1, block1)]).unwrap();
296
297        // Check that passing nullifier2 twice with different values will use the last value.
298        let mutations = tree
299            .compute_mutations([(nullifier2, block1), (nullifier3, block3), (nullifier2, block2)])
300            .unwrap();
301
302        tree.apply_mutations(mutations).unwrap();
303
304        assert_eq!(tree.num_nullifiers(), 3);
305        assert_eq!(tree.get_block_num(&nullifier1).unwrap(), block1);
306        assert_eq!(tree.get_block_num(&nullifier2).unwrap(), block2);
307        assert_eq!(tree.get_block_num(&nullifier3).unwrap(), block3);
308    }
309
310    #[test]
311    fn nullifier_already_spent() {
312        let nullifier1 = Nullifier::dummy(1);
313
314        let block1 = BlockNumber::from(1);
315        let block2 = BlockNumber::from(2);
316
317        let mut tree = NullifierTree::with_entries([(nullifier1, block1)]).unwrap();
318
319        // Attempt to insert nullifier 1 again at _the same_ block number.
320        let err = tree.clone().compute_mutations([(nullifier1, block1)]).unwrap_err();
321        assert_matches!(err, NullifierTreeError::NullifierAlreadySpent(nullifier) if nullifier == nullifier1);
322
323        let err = tree.clone().mark_spent(nullifier1, block1).unwrap_err();
324        assert_matches!(err, NullifierTreeError::NullifierAlreadySpent(nullifier) if nullifier == nullifier1);
325
326        // Attempt to insert nullifier 1 again at a different block number.
327        let err = tree.clone().compute_mutations([(nullifier1, block2)]).unwrap_err();
328        assert_matches!(err, NullifierTreeError::NullifierAlreadySpent(nullifier) if nullifier == nullifier1);
329
330        let err = tree.mark_spent(nullifier1, block2).unwrap_err();
331        assert_matches!(err, NullifierTreeError::NullifierAlreadySpent(nullifier) if nullifier == nullifier1);
332    }
333}
miden_objects/block/nullifier_tree.rs

miden_objects/block/
nullifier_tree.rs
