miden_protocol/block/nullifier_tree/
mod.rs

1use alloc::string::ToString;
2use alloc::vec::Vec;
3
4#[cfg(feature = "std")]
5use miden_crypto::merkle::smt::{LargeSmt, LargeSmtError, SmtStorage};
6
7use crate::block::{BlockNumber, SmtBackend, SmtBackendReader};
8use crate::crypto::merkle::MerkleError;
9use crate::crypto::merkle::smt::{MutationSet, SMT_DEPTH, Smt};
10use crate::errors::NullifierTreeError;
11use crate::note::Nullifier;
12use crate::utils::serde::{
13    ByteReader,
14    ByteWriter,
15    Deserializable,
16    DeserializationError,
17    Serializable,
18};
19use crate::{Felt, Word};
20
21mod witness;
22pub use witness::NullifierWitness;
23
24mod partial;
25pub use partial::PartialNullifierTree;
26
27// NULLIFIER TREE
28// ================================================================================================
29
30/// The sparse merkle tree of all nullifiers in the blockchain.
31///
32/// A nullifier can only ever be spent once and its value in the tree is the block number at which
33/// it was spent.
34///
35/// The tree guarantees that once a nullifier has been inserted into the tree, its block number does
36/// not change. Note that inserting the nullifier multiple times with the same block number is
37/// valid.
38#[derive(Debug, Clone, PartialEq, Eq)]
39pub struct NullifierTree<Backend = Smt> {
40    smt: Backend,
41}
42
43impl<Backend> Default for NullifierTree<Backend>
44where
45    Backend: Default,
46{
47    fn default() -> Self {
48        Self { smt: Default::default() }
49    }
50}
51
52impl<Backend> NullifierTree<Backend>
53where
54    Backend: SmtBackendReader<Error = MerkleError>,
55{
56    // CONSTANTS
57    // --------------------------------------------------------------------------------------------
58
59    /// The depth of the nullifier tree.
60    pub const DEPTH: u8 = SMT_DEPTH;
61
62    // CONSTRUCTORS
63    // --------------------------------------------------------------------------------------------
64
65    /// Creates a new `NullifierTree` from its inner representation.
66    ///
67    /// # Invariants
68    ///
69    /// Assumes the provided SMT upholds the guarantees of the [`NullifierTree`]. Specifically:
70    /// - Nullifiers are only spent once and their block numbers do not change.
71    /// - Nullifier leaf values must be valid according to [`NullifierBlock`].
72    pub fn new_unchecked(backend: Backend) -> Self {
73        NullifierTree { smt: backend }
74    }
75
76    // PUBLIC ACCESSORS
77    // --------------------------------------------------------------------------------------------
78
79    /// Returns the root of the nullifier SMT.
80    pub fn root(&self) -> Word {
81        self.smt.root()
82    }
83
84    /// Returns the number of spent nullifiers in this tree.
85    pub fn num_nullifiers(&self) -> usize {
86        self.smt.num_entries()
87    }
88
89    /// Returns an iterator over the nullifiers and their block numbers in the tree.
90    pub fn entries(&self) -> impl Iterator<Item = (Nullifier, BlockNumber)> {
91        self.smt.entries().map(|(nullifier, value)| {
92            (
93                Nullifier::from_raw(nullifier),
94                NullifierBlock::new(value)
95                    .expect("SMT should only store valid NullifierBlocks")
96                    .into(),
97            )
98        })
99    }
100
101    /// Returns a [`NullifierWitness`] of the leaf associated with the `nullifier`.
102    ///
103    /// Conceptually, such a witness is a Merkle path to the leaf, as well as the leaf itself.
104    ///
105    /// This witness is a proof of the current block number of the given nullifier. If that block
106    /// number is zero, it proves that the nullifier is unspent.
107    pub fn open(&self, nullifier: &Nullifier) -> NullifierWitness {
108        NullifierWitness::new(self.smt.open(&nullifier.as_word()))
109    }
110
111    /// Returns the block number for the given nullifier or `None` if the nullifier wasn't spent
112    /// yet.
113    pub fn get_block_num(&self, nullifier: &Nullifier) -> Option<BlockNumber> {
114        let nullifier_block = NullifierBlock::new(self.smt.get_value(&nullifier.as_word()))
115            .expect("SMT should only store valid NullifierBlocks");
116        if nullifier_block.is_unspent() {
117            return None;
118        }
119
120        Some(nullifier_block.into())
121    }
122}
123
124impl<Backend> NullifierTree<Backend>
125where
126    Backend: SmtBackend<Error = MerkleError>,
127{
128    // PUBLIC MUTATORS
129    // --------------------------------------------------------------------------------------------
130
131    /// Computes a mutation set resulting from inserting the provided nullifiers into this nullifier
132    /// tree.
133    ///
134    /// # Errors
135    ///
136    /// Returns an error if:
137    /// - a nullifier in the provided iterator was already spent.
138    /// - the list of provided nullifiers contains duplicates.
139    pub fn compute_mutations<I>(
140        &self,
141        nullifiers: impl IntoIterator<Item = (Nullifier, BlockNumber), IntoIter = I>,
142    ) -> Result<NullifierMutationSet, NullifierTreeError>
143    where
144        I: Iterator<Item = (Nullifier, BlockNumber)> + Clone,
145    {
146        let nullifiers = nullifiers.into_iter();
147        for (nullifier, _) in nullifiers.clone() {
148            if self.get_block_num(&nullifier).is_some() {
149                return Err(NullifierTreeError::NullifierAlreadySpent(nullifier));
150            }
151        }
152
153        let mutation_set = self
154            .smt
155            .compute_mutations(
156                nullifiers
157                    .into_iter()
158                    .map(|(nullifier, block_num)| {
159                        (nullifier.as_word(), NullifierBlock::from(block_num).into())
160                    })
161                    .collect::<Vec<_>>(),
162            )
163            .map_err(NullifierTreeError::ComputeMutations)?;
164
165        Ok(NullifierMutationSet::new(mutation_set))
166    }
167
168    /// Marks the given nullifier as spent at the given block number.
169    ///
170    /// # Errors
171    ///
172    /// Returns an error if:
173    /// - the nullifier was already spent.
174    pub fn mark_spent(
175        &mut self,
176        nullifier: Nullifier,
177        block_num: BlockNumber,
178    ) -> Result<(), NullifierTreeError> {
179        let prev_value = self
180            .smt
181            .insert(nullifier.as_word(), NullifierBlock::from(block_num).into())
182            .map_err(NullifierTreeError::MaxLeafEntriesExceeded)?;
183        let prev_nullifier_value = NullifierBlock::try_from(prev_value)
184            .expect("SMT should only store valid NullifierBlocks");
185
186        if prev_nullifier_value.is_spent() {
187            Err(NullifierTreeError::NullifierAlreadySpent(nullifier))
188        } else {
189            Ok(())
190        }
191    }
192
193    /// Applies mutations to the nullifier tree.
194    ///
195    /// # Errors
196    ///
197    /// Returns an error if:
198    /// - `mutations` was computed on a tree with a different root than this one.
199    pub fn apply_mutations(
200        &mut self,
201        mutations: NullifierMutationSet,
202    ) -> Result<(), NullifierTreeError> {
203        self.smt
204            .apply_mutations(mutations.into_mutation_set())
205            .map_err(NullifierTreeError::TreeRootConflict)
206    }
207}
208
209impl NullifierTree<Smt> {
210    /// Creates a new nullifier tree from the provided entries.
211    ///
212    /// This is a convenience method that creates an SMT backend with the provided entries and
213    /// wraps it in a NullifierTree.
214    ///
215    /// # Errors
216    ///
217    /// Returns an error if:
218    /// - the provided entries contain multiple block numbers for the same nullifier.
219    pub fn with_entries(
220        entries: impl IntoIterator<Item = (Nullifier, BlockNumber)>,
221    ) -> Result<Self, NullifierTreeError> {
222        let leaves = entries.into_iter().map(|(nullifier, block_num)| {
223            (nullifier.as_word(), NullifierBlock::from(block_num).into())
224        });
225
226        let smt = Smt::with_entries(leaves)
227            .map_err(NullifierTreeError::DuplicateNullifierBlockNumbers)?;
228
229        Ok(Self::new_unchecked(smt))
230    }
231}
232
233#[cfg(feature = "std")]
234impl<Backend> NullifierTree<LargeSmt<Backend>>
235where
236    Backend: SmtStorage,
237{
238    /// Creates a new nullifier tree from the provided entries using the given storage backend
239    ///
240    /// This is a convenience method that creates an SMT on the provided storage backend using the
241    /// provided entries and wraps it in a NullifierTree.
242    ///
243    /// # Errors
244    ///
245    /// Returns an error if:
246    /// - the provided entries contain multiple block numbers for the same nullifier.
247    ///
248    /// # Panics
249    ///
250    /// Panics if a storage error is encountered.
251    pub fn with_storage_from_entries(
252        storage: Backend,
253        entries: impl IntoIterator<Item = (Nullifier, BlockNumber)>,
254    ) -> Result<Self, NullifierTreeError> {
255        use crate::block::smt_backend::large_smt_error_to_merkle_error;
256
257        let leaves = entries.into_iter().map(|(nullifier, block_num)| {
258            (nullifier.as_word(), NullifierBlock::from(block_num).into())
259        });
260
261        let smt = LargeSmt::<Backend>::with_entries(storage, leaves)
262            .map_err(large_smt_error_to_merkle_error)
263            .map_err(NullifierTreeError::DuplicateNullifierBlockNumbers)?;
264
265        Ok(Self::new_unchecked(smt))
266    }
267
268    /// Returns a read-only nullifier tree backed by a reader view of this tree's storage.
269    ///
270    /// The returned tree shares the same root and entries as `self`, but its storage is a
271    /// read-only snapshot produced by [`SmtStorage::reader`]. The returned tree cannot be
272    /// mutated.
273    pub fn reader(&self) -> Result<NullifierTree<LargeSmt<Backend::Reader>>, LargeSmtError> {
274        Ok(NullifierTree::new_unchecked(self.smt.reader()?))
275    }
276}
277
278// SERIALIZATION
279// ================================================================================================
280
281impl Serializable for NullifierTree {
282    fn write_into<W: ByteWriter>(&self, target: &mut W) {
283        self.entries().collect::<Vec<_>>().write_into(target);
284    }
285}
286
287impl Deserializable for NullifierTree {
288    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
289        let entries = Vec::<(Nullifier, BlockNumber)>::read_from(source)?;
290        Self::with_entries(entries)
291            .map_err(|err| DeserializationError::InvalidValue(err.to_string()))
292    }
293}
294
295// NULLIFIER MUTATION SET
296// ================================================================================================
297
298/// A newtype wrapper around a [`MutationSet`] for use in the [`NullifierTree`].
299///
300/// It guarantees that applying the contained mutations will result in a nullifier tree where
301/// nullifier's block numbers are not updated (except if they were unspent before), ensuring that
302/// nullifiers are only spent once.
303///
304/// It is returned by and used in methods on the [`NullifierTree`].
305#[derive(Debug, Clone, PartialEq, Eq)]
306pub struct NullifierMutationSet {
307    mutation_set: MutationSet<SMT_DEPTH, Word, Word>,
308}
309
310impl NullifierMutationSet {
311    // CONSTRUCTORS
312    // --------------------------------------------------------------------------------------------
313
314    /// Creates a new [`NullifierMutationSet`] from the provided raw mutation set.
315    fn new(mutation_set: MutationSet<SMT_DEPTH, Word, Word>) -> Self {
316        Self { mutation_set }
317    }
318
319    // PUBLIC ACCESSORS
320    // --------------------------------------------------------------------------------------------
321
322    /// Returns a reference to the underlying [`MutationSet`].
323    pub fn as_mutation_set(&self) -> &MutationSet<SMT_DEPTH, Word, Word> {
324        &self.mutation_set
325    }
326
327    // PUBLIC MUTATORS
328    // --------------------------------------------------------------------------------------------
329
330    /// Consumes self and returns the underlying [`MutationSet`].
331    pub fn into_mutation_set(self) -> MutationSet<SMT_DEPTH, Word, Word> {
332        self.mutation_set
333    }
334}
335
336// NULLIFIER BLOCK
337// ================================================================================================
338
339/// The [`BlockNumber`] at which a [`Nullifier`] was consumed.
340///
341/// Since there are no nullifiers in the genesis block the [`BlockNumber::GENESIS`] is used to
342/// signal an unconsumed nullifier.
343///
344/// This type can be converted to a [`Word`] which is laid out like this:
345///
346/// ```text
347/// [block_num, 0, 0, 0]
348/// ```
349#[derive(Debug, PartialEq, Eq, Copy, Clone)]
350pub struct NullifierBlock(BlockNumber);
351
352impl NullifierBlock {
353    pub const UNSPENT: NullifierBlock = NullifierBlock(BlockNumber::GENESIS);
354
355    /// Returns a new [NullifierBlock] constructed from the provided word.
356    ///
357    /// # Errors
358    /// Returns an error if:
359    /// - The 0th element in the word is not a valid [BlockNumber].
360    /// - Any of the remaining elements is non-zero.
361    pub fn new(word: Word) -> Result<Self, NullifierTreeError> {
362        let block_num = u32::try_from(word[0].as_canonical_u64())
363            .map(BlockNumber::from)
364            .map_err(|_| NullifierTreeError::InvalidNullifierBlockNumber(word))?;
365
366        if word[1..4].iter().any(|felt| *felt != Felt::ZERO) {
367            return Err(NullifierTreeError::InvalidNullifierBlockNumber(word));
368        }
369
370        Ok(NullifierBlock(block_num))
371    }
372
373    /// Returns true if the nullifier has already been spent.
374    pub fn is_spent(&self) -> bool {
375        !self.is_unspent()
376    }
377
378    /// Returns true if the nullifier has not yet been spent.
379    pub fn is_unspent(&self) -> bool {
380        self == &Self::UNSPENT
381    }
382}
383
384impl From<BlockNumber> for NullifierBlock {
385    fn from(block_num: BlockNumber) -> Self {
386        Self(block_num)
387    }
388}
389
390impl From<NullifierBlock> for BlockNumber {
391    fn from(value: NullifierBlock) -> BlockNumber {
392        value.0
393    }
394}
395
396impl From<NullifierBlock> for Word {
397    fn from(value: NullifierBlock) -> Word {
398        Word::from([Felt::from(value.0), Felt::ZERO, Felt::ZERO, Felt::ZERO])
399    }
400}
401
402impl TryFrom<Word> for NullifierBlock {
403    type Error = NullifierTreeError;
404
405    fn try_from(value: Word) -> Result<Self, Self::Error> {
406        Self::new(value)
407    }
408}
409
410// TESTS
411// ================================================================================================
412
413#[cfg(test)]
414mod tests {
415    use assert_matches::assert_matches;
416
417    use super::NullifierTree;
418    use crate::Word;
419    use crate::block::BlockNumber;
420    use crate::block::nullifier_tree::NullifierBlock;
421    use crate::errors::NullifierTreeError;
422    use crate::note::Nullifier;
423
424    #[test]
425    fn leaf_value_encode_decode() {
426        let block_num = BlockNumber::from(0xffff_ffff_u32);
427        let nullifier_block = NullifierBlock::from(block_num);
428        let block_num_recovered = nullifier_block.into();
429        assert_eq!(block_num, block_num_recovered);
430    }
431
432    #[test]
433    fn leaf_value_encoding() {
434        let block_num = BlockNumber::from(123);
435        let nullifier_value = NullifierBlock::from(block_num);
436        assert_eq!(
437            nullifier_value,
438            NullifierBlock::new(Word::from([block_num.as_u32(), 0, 0, 0u32])).unwrap()
439        );
440    }
441
442    #[test]
443    fn leaf_value_decoding() {
444        let block_num = 123;
445        let nullifier_value = NullifierBlock::new(Word::from([block_num, 0, 0, 0u32])).unwrap();
446        let decoded_block_num: BlockNumber = nullifier_value.into();
447
448        assert_eq!(decoded_block_num, block_num.into());
449    }
450
451    #[test]
452    fn apply_mutations() {
453        let nullifier1 = Nullifier::dummy(1);
454        let nullifier2 = Nullifier::dummy(2);
455        let nullifier3 = Nullifier::dummy(3);
456
457        let block1 = BlockNumber::from(1);
458        let block2 = BlockNumber::from(2);
459        let block3 = BlockNumber::from(3);
460
461        let mut tree = NullifierTree::with_entries([(nullifier1, block1)]).unwrap();
462
463        let mutations =
464            tree.compute_mutations([(nullifier2, block2), (nullifier3, block3)]).unwrap();
465
466        tree.apply_mutations(mutations).unwrap();
467
468        assert_eq!(tree.num_nullifiers(), 3);
469        assert_eq!(tree.get_block_num(&nullifier1).unwrap(), block1);
470        assert_eq!(tree.get_block_num(&nullifier2).unwrap(), block2);
471        assert_eq!(tree.get_block_num(&nullifier3).unwrap(), block3);
472    }
473
474    #[test]
475    fn nullifier_already_spent() {
476        let nullifier1 = Nullifier::dummy(1);
477
478        let block1 = BlockNumber::from(1);
479        let block2 = BlockNumber::from(2);
480
481        let mut tree = NullifierTree::with_entries([(nullifier1, block1)]).unwrap();
482
483        // Attempt to insert nullifier 1 again at _the same_ block number.
484        let err = tree.clone().compute_mutations([(nullifier1, block1)]).unwrap_err();
485        assert_matches!(err, NullifierTreeError::NullifierAlreadySpent(nullifier) if nullifier == nullifier1);
486
487        let err = tree.clone().mark_spent(nullifier1, block1).unwrap_err();
488        assert_matches!(err, NullifierTreeError::NullifierAlreadySpent(nullifier) if nullifier == nullifier1);
489
490        // Attempt to insert nullifier 1 again at a different block number.
491        let err = tree.clone().compute_mutations([(nullifier1, block2)]).unwrap_err();
492        assert_matches!(err, NullifierTreeError::NullifierAlreadySpent(nullifier) if nullifier == nullifier1);
493
494        let err = tree.mark_spent(nullifier1, block2).unwrap_err();
495        assert_matches!(err, NullifierTreeError::NullifierAlreadySpent(nullifier) if nullifier == nullifier1);
496    }
497
498    #[cfg(feature = "std")]
499    #[test]
500    fn large_smt_backend_basic_operations() {
501        use miden_crypto::merkle::smt::{LargeSmt, MemoryStorage};
502
503        // Create test data
504        let nullifier1 = Nullifier::dummy(1);
505        let nullifier2 = Nullifier::dummy(2);
506        let nullifier3 = Nullifier::dummy(3);
507
508        let block1 = BlockNumber::from(1);
509        let block2 = BlockNumber::from(2);
510        let block3 = BlockNumber::from(3);
511
512        // Create NullifierTree with LargeSmt backend
513        let mut tree = NullifierTree::new_unchecked(
514            LargeSmt::with_entries(
515                MemoryStorage::default(),
516                [
517                    (nullifier1.as_word(), NullifierBlock::from(block1).into()),
518                    (nullifier2.as_word(), NullifierBlock::from(block2).into()),
519                ],
520            )
521            .unwrap(),
522        );
523
524        // Test basic operations
525        assert_eq!(tree.num_nullifiers(), 2);
526        assert_eq!(tree.get_block_num(&nullifier1).unwrap(), block1);
527        assert_eq!(tree.get_block_num(&nullifier2).unwrap(), block2);
528
529        // Test opening
530        let _witness1 = tree.open(&nullifier1);
531
532        // Test mutations
533        tree.mark_spent(nullifier3, block3).unwrap();
534        assert_eq!(tree.num_nullifiers(), 3);
535        assert_eq!(tree.get_block_num(&nullifier3).unwrap(), block3);
536    }
537
538    #[cfg(feature = "std")]
539    #[test]
540    fn large_smt_backend_nullifier_already_spent() {
541        use miden_crypto::merkle::smt::{LargeSmt, MemoryStorage};
542
543        let nullifier1 = Nullifier::dummy(1);
544
545        let block1 = BlockNumber::from(1);
546        let block2 = BlockNumber::from(2);
547
548        let mut tree = NullifierTree::new_unchecked(
549            LargeSmt::with_entries(
550                MemoryStorage::default(),
551                [(nullifier1.as_word(), NullifierBlock::from(block1).into())],
552            )
553            .unwrap(),
554        );
555
556        assert_eq!(tree.get_block_num(&nullifier1).unwrap(), block1);
557
558        let err = tree.mark_spent(nullifier1, block2).unwrap_err();
559        assert_matches!(err, NullifierTreeError::NullifierAlreadySpent(nullifier) if nullifier == nullifier1);
560    }
561
562    #[cfg(feature = "std")]
563    #[test]
564    fn large_smt_backend_apply_mutations() {
565        use miden_crypto::merkle::smt::{LargeSmt, MemoryStorage};
566
567        let nullifier1 = Nullifier::dummy(1);
568        let nullifier2 = Nullifier::dummy(2);
569        let nullifier3 = Nullifier::dummy(3);
570
571        let block1 = BlockNumber::from(1);
572        let block2 = BlockNumber::from(2);
573        let block3 = BlockNumber::from(3);
574
575        let mut tree = LargeSmt::with_entries(
576            MemoryStorage::default(),
577            [(nullifier1.as_word(), NullifierBlock::from(block1).into())],
578        )
579        .map(NullifierTree::new_unchecked)
580        .unwrap();
581
582        let mutations =
583            tree.compute_mutations([(nullifier2, block2), (nullifier3, block3)]).unwrap();
584
585        tree.apply_mutations(mutations).unwrap();
586
587        assert_eq!(tree.num_nullifiers(), 3);
588        assert_eq!(tree.get_block_num(&nullifier1).unwrap(), block1);
589        assert_eq!(tree.get_block_num(&nullifier2).unwrap(), block2);
590        assert_eq!(tree.get_block_num(&nullifier3).unwrap(), block3);
591    }
592
593    #[cfg(feature = "std")]
594    #[test]
595    fn large_smt_backend_same_root_as_regular_smt() {
596        use miden_crypto::merkle::smt::{LargeSmt, MemoryStorage};
597
598        let nullifier1 = Nullifier::dummy(1);
599        let nullifier2 = Nullifier::dummy(2);
600
601        let block1 = BlockNumber::from(1);
602        let block2 = BlockNumber::from(2);
603
604        // Create tree with LargeSmt backend
605        let large_tree = LargeSmt::with_entries(
606            MemoryStorage::default(),
607            [
608                (nullifier1.as_word(), NullifierBlock::from(block1).into()),
609                (nullifier2.as_word(), NullifierBlock::from(block2).into()),
610            ],
611        )
612        .map(NullifierTree::new_unchecked)
613        .unwrap();
614
615        // Create tree with regular Smt backend
616        let regular_tree =
617            NullifierTree::with_entries([(nullifier1, block1), (nullifier2, block2)]).unwrap();
618
619        // Both should have the same root
620        assert_eq!(large_tree.root(), regular_tree.root());
621
622        // Both should have the same nullifier entries
623        let large_entries: std::collections::BTreeMap<_, _> = large_tree.entries().collect();
624        let regular_entries: std::collections::BTreeMap<_, _> = regular_tree.entries().collect();
625
626        assert_eq!(large_entries, regular_entries);
627    }
628}
miden_protocol/block/nullifier_tree/mod.rs

miden_protocol/block/nullifier_tree/
mod.rs
