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 = self
127            .smt
128            .compute_mutations(nullifiers.into_iter().map(|(nullifier, block_num)| {
129                (nullifier.as_word(), Self::block_num_to_leaf_value(block_num))
130            }))
131            .map_err(NullifierTreeError::ComputeMutations)?;
132
133        Ok(NullifierMutationSet::new(mutation_set))
134    }
135
136    // PUBLIC MUTATORS
137    // --------------------------------------------------------------------------------------------
138
139    /// Marks the given nullifier as spent at the given block number.
140    ///
141    /// # Errors
142    ///
143    /// Returns an error if:
144    /// - the nullifier was already spent.
145    pub fn mark_spent(
146        &mut self,
147        nullifier: Nullifier,
148        block_num: BlockNumber,
149    ) -> Result<(), NullifierTreeError> {
150        let prev_nullifier_value = self
151            .smt
152            .insert(nullifier.as_word(), Self::block_num_to_leaf_value(block_num))
153            .map_err(NullifierTreeError::MaxLeafEntriesExceeded)?;
154
155        if prev_nullifier_value != Self::UNSPENT_NULLIFIER {
156            Err(NullifierTreeError::NullifierAlreadySpent(nullifier))
157        } else {
158            Ok(())
159        }
160    }
161
162    /// Applies mutations to the nullifier tree.
163    ///
164    /// # Errors
165    ///
166    /// Returns an error if:
167    /// - `mutations` was computed on a tree with a different root than this one.
168    pub fn apply_mutations(
169        &mut self,
170        mutations: NullifierMutationSet,
171    ) -> Result<(), NullifierTreeError> {
172        self.smt
173            .apply_mutations(mutations.into_mutation_set())
174            .map_err(NullifierTreeError::TreeRootConflict)
175    }
176
177    // HELPER FUNCTIONS
178    // --------------------------------------------------------------------------------------------
179
180    /// Returns the nullifier's leaf value in the SMT by its block number.
181    pub(super) fn block_num_to_leaf_value(block: BlockNumber) -> Word {
182        Word::from([block.as_u32(), 0, 0, 0])
183    }
184
185    /// Given the leaf value of the nullifier SMT, returns the nullifier's block number.
186    ///
187    /// There are no nullifiers in the genesis block. The value zero is instead used to signal
188    /// absence of a value.
189    fn leaf_value_to_block_num(value: Word) -> BlockNumber {
190        let block_num: u32 =
191            value[0].as_int().try_into().expect("invalid block number found in store");
192
193        block_num.into()
194    }
195}
196
197impl Default for NullifierTree {
198    fn default() -> Self {
199        Self::new()
200    }
201}
202
203// SERIALIZATION
204// ================================================================================================
205
206impl Serializable for NullifierTree {
207    fn write_into<W: ByteWriter>(&self, target: &mut W) {
208        self.entries().collect::<Vec<_>>().write_into(target);
209    }
210}
211
212impl Deserializable for NullifierTree {
213    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
214        let entries = Vec::<(Nullifier, BlockNumber)>::read_from(source)?;
215        Self::with_entries(entries)
216            .map_err(|err| DeserializationError::InvalidValue(err.to_string()))
217    }
218}
219
220// NULLIFIER MUTATION SET
221// ================================================================================================
222
223/// A newtype wrapper around a [`MutationSet`] for use in the [`NullifierTree`].
224///
225/// It guarantees that applying the contained mutations will result in a nullifier tree where
226/// nullifier's block numbers are not updated (except if they were unspent before), ensuring that
227/// nullifiers are only spent once.
228///
229/// It is returned by and used in methods on the [`NullifierTree`].
230#[derive(Debug, Clone, PartialEq, Eq)]
231pub struct NullifierMutationSet {
232    mutation_set: MutationSet<{ NullifierTree::DEPTH }, Word, Word>,
233}
234
235impl NullifierMutationSet {
236    // CONSTRUCTORS
237    // --------------------------------------------------------------------------------------------
238
239    /// Creates a new [`AccountMutationSet`] from the provided raw mutation set.
240    fn new(mutation_set: MutationSet<{ NullifierTree::DEPTH }, Word, Word>) -> Self {
241        Self { mutation_set }
242    }
243
244    // PUBLIC ACCESSORS
245    // --------------------------------------------------------------------------------------------
246
247    /// Returns a reference to the underlying [`MutationSet`].
248    pub fn as_mutation_set(&self) -> &MutationSet<{ NullifierTree::DEPTH }, Word, Word> {
249        &self.mutation_set
250    }
251
252    // PUBLIC MUTATORS
253    // --------------------------------------------------------------------------------------------
254
255    /// Consumes self and returns the underlying [`MutationSet`].
256    pub fn into_mutation_set(self) -> MutationSet<{ NullifierTree::DEPTH }, Word, Word> {
257        self.mutation_set
258    }
259}
260
261// TESTS
262// ================================================================================================
263
264#[cfg(test)]
265mod tests {
266    use assert_matches::assert_matches;
267
268    use super::NullifierTree;
269    use crate::block::BlockNumber;
270    use crate::note::Nullifier;
271    use crate::{NullifierTreeError, Word};
272
273    #[test]
274    fn leaf_value_encoding() {
275        let block_num = 123;
276        let nullifier_value = NullifierTree::block_num_to_leaf_value(block_num.into());
277        assert_eq!(nullifier_value, Word::from([block_num, 0, 0, 0u32]));
278    }
279
280    #[test]
281    fn leaf_value_decoding() {
282        let block_num = 123;
283        let nullifier_value = Word::from([block_num, 0, 0, 0u32]);
284        let decoded_block_num = NullifierTree::leaf_value_to_block_num(nullifier_value);
285
286        assert_eq!(decoded_block_num, block_num.into());
287    }
288
289    #[test]
290    fn apply_mutations() {
291        let nullifier1 = Nullifier::dummy(1);
292        let nullifier2 = Nullifier::dummy(2);
293        let nullifier3 = Nullifier::dummy(3);
294
295        let block1 = BlockNumber::from(1);
296        let block2 = BlockNumber::from(2);
297        let block3 = BlockNumber::from(3);
298
299        let mut tree = NullifierTree::with_entries([(nullifier1, block1)]).unwrap();
300
301        // Check that passing nullifier2 twice with different values will use the last value.
302        let mutations = tree
303            .compute_mutations([(nullifier2, block1), (nullifier3, block3), (nullifier2, block2)])
304            .unwrap();
305
306        tree.apply_mutations(mutations).unwrap();
307
308        assert_eq!(tree.num_nullifiers(), 3);
309        assert_eq!(tree.get_block_num(&nullifier1).unwrap(), block1);
310        assert_eq!(tree.get_block_num(&nullifier2).unwrap(), block2);
311        assert_eq!(tree.get_block_num(&nullifier3).unwrap(), block3);
312    }
313
314    #[test]
315    fn nullifier_already_spent() {
316        let nullifier1 = Nullifier::dummy(1);
317
318        let block1 = BlockNumber::from(1);
319        let block2 = BlockNumber::from(2);
320
321        let mut tree = NullifierTree::with_entries([(nullifier1, block1)]).unwrap();
322
323        // Attempt to insert nullifier 1 again at _the same_ block number.
324        let err = tree.clone().compute_mutations([(nullifier1, block1)]).unwrap_err();
325        assert_matches!(err, NullifierTreeError::NullifierAlreadySpent(nullifier) if nullifier == nullifier1);
326
327        let err = tree.clone().mark_spent(nullifier1, block1).unwrap_err();
328        assert_matches!(err, NullifierTreeError::NullifierAlreadySpent(nullifier) if nullifier == nullifier1);
329
330        // Attempt to insert nullifier 1 again at a different block number.
331        let err = tree.clone().compute_mutations([(nullifier1, block2)]).unwrap_err();
332        assert_matches!(err, NullifierTreeError::NullifierAlreadySpent(nullifier) if nullifier == nullifier1);
333
334        let err = tree.mark_spent(nullifier1, block2).unwrap_err();
335        assert_matches!(err, NullifierTreeError::NullifierAlreadySpent(nullifier) if nullifier == nullifier1);
336    }
337}
miden_objects/block/nullifier_tree.rs

miden_objects/block/
nullifier_tree.rs
