miden_objects/block/
nullifier_tree.rs

1use vm_core::EMPTY_WORD;
2
3use crate::{
4    Felt, FieldElement, Word,
5    block::{BlockNumber, NullifierWitness},
6    crypto::{
7        hash::rpo::RpoDigest,
8        merkle::{MutationSet, SMT_DEPTH, Smt},
9    },
10    errors::NullifierTreeError,
11    note::Nullifier,
12};
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.inner(), 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) -> RpoDigest {
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.inner()))
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.inner());
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.inner(), 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.inner(), 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        [Felt::from(block), Felt::ZERO, Felt::ZERO, Felt::ZERO]
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// NULLIFIER MUTATION SET
200// ================================================================================================
201
202/// A newtype wrapper around a [`MutationSet`] for use in the [`NullifierTree`].
203///
204/// It guarantees that applying the contained mutations will result in a nullifier tree where
205/// nullifier's block numbers are not updated (except if they were unspent before), ensuring that
206/// nullifiers are only spent once.
207///
208/// It is returned by and used in methods on the [`NullifierTree`].
209#[derive(Debug, Clone, PartialEq, Eq)]
210pub struct NullifierMutationSet {
211    mutation_set: MutationSet<{ NullifierTree::DEPTH }, RpoDigest, Word>,
212}
213
214impl NullifierMutationSet {
215    // CONSTRUCTORS
216    // --------------------------------------------------------------------------------------------
217
218    /// Creates a new [`AccountMutationSet`] from the provided raw mutation set.
219    fn new(mutation_set: MutationSet<{ NullifierTree::DEPTH }, RpoDigest, Word>) -> Self {
220        Self { mutation_set }
221    }
222
223    // PUBLIC ACCESSORS
224    // --------------------------------------------------------------------------------------------
225
226    /// Returns a reference to the underlying [`MutationSet`].
227    pub fn as_mutation_set(&self) -> &MutationSet<{ NullifierTree::DEPTH }, RpoDigest, Word> {
228        &self.mutation_set
229    }
230
231    // PUBLIC MUTATORS
232    // --------------------------------------------------------------------------------------------
233
234    /// Consumes self and returns the underlying [`MutationSet`].
235    pub fn into_mutation_set(self) -> MutationSet<{ NullifierTree::DEPTH }, RpoDigest, Word> {
236        self.mutation_set
237    }
238}
239
240// TESTS
241// ================================================================================================
242
243#[cfg(test)]
244mod tests {
245    use assert_matches::assert_matches;
246    use miden_objects::{Felt, ZERO};
247
248    use super::NullifierTree;
249    use crate::{NullifierTreeError, block::BlockNumber, note::Nullifier};
250
251    #[test]
252    fn leaf_value_encoding() {
253        let block_num = 123;
254        let nullifier_value = NullifierTree::block_num_to_leaf_value(block_num.into());
255
256        assert_eq!(nullifier_value, [Felt::from(block_num), ZERO, ZERO, ZERO]);
257    }
258
259    #[test]
260    fn leaf_value_decoding() {
261        let block_num = 123;
262        let nullifier_value = [Felt::from(block_num), ZERO, ZERO, ZERO];
263        let decoded_block_num = NullifierTree::leaf_value_to_block_num(nullifier_value);
264
265        assert_eq!(decoded_block_num, block_num.into());
266    }
267
268    #[test]
269    fn apply_mutations() {
270        let nullifier1 = Nullifier::dummy(1);
271        let nullifier2 = Nullifier::dummy(2);
272        let nullifier3 = Nullifier::dummy(3);
273
274        let block1 = BlockNumber::from(1);
275        let block2 = BlockNumber::from(2);
276        let block3 = BlockNumber::from(3);
277
278        let mut tree = NullifierTree::with_entries([(nullifier1, block1)]).unwrap();
279
280        // Check that passing nullifier2 twice with different values will use the last value.
281        let mutations = tree
282            .compute_mutations([(nullifier2, block1), (nullifier3, block3), (nullifier2, block2)])
283            .unwrap();
284
285        tree.apply_mutations(mutations).unwrap();
286
287        assert_eq!(tree.num_nullifiers(), 3);
288        assert_eq!(tree.get_block_num(&nullifier1).unwrap(), block1);
289        assert_eq!(tree.get_block_num(&nullifier2).unwrap(), block2);
290        assert_eq!(tree.get_block_num(&nullifier3).unwrap(), block3);
291    }
292
293    #[test]
294    fn nullifier_already_spent() {
295        let nullifier1 = Nullifier::dummy(1);
296
297        let block1 = BlockNumber::from(1);
298        let block2 = BlockNumber::from(2);
299
300        let mut tree = NullifierTree::with_entries([(nullifier1, block1)]).unwrap();
301
302        // Attempt to insert nullifier 1 again at _the same_ block number.
303        let err = tree.clone().compute_mutations([(nullifier1, block1)]).unwrap_err();
304        assert_matches!(err, NullifierTreeError::NullifierAlreadySpent(nullifier) if nullifier == nullifier1);
305
306        let err = tree.clone().mark_spent(nullifier1, block1).unwrap_err();
307        assert_matches!(err, NullifierTreeError::NullifierAlreadySpent(nullifier) if nullifier == nullifier1);
308
309        // Attempt to insert nullifier 1 again at a different block number.
310        let err = tree.clone().compute_mutations([(nullifier1, block2)]).unwrap_err();
311        assert_matches!(err, NullifierTreeError::NullifierAlreadySpent(nullifier) if nullifier == nullifier1);
312
313        let err = tree.mark_spent(nullifier1, block2).unwrap_err();
314        assert_matches!(err, NullifierTreeError::NullifierAlreadySpent(nullifier) if nullifier == nullifier1);
315    }
316}
miden_objects/block/nullifier_tree.rs

miden_objects/block/
nullifier_tree.rs
