miden_protocol/batch/
note_tree.rs

1use alloc::vec::Vec;
2
3use crate::crypto::merkle::MerkleError;
4use crate::crypto::merkle::smt::{LeafIndex, SimpleSmt};
5use crate::note::{NoteId, NoteMetadata, compute_note_commitment};
6use crate::utils::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable};
7use crate::{BATCH_NOTE_TREE_DEPTH, EMPTY_WORD, Word};
8
9/// Wrapper over [SimpleSmt<BATCH_NOTE_TREE_DEPTH>] for batch note tree.
10///
11/// Value of each leaf is computed as: `hash(note_id || note_metadata_commitment)`.
12#[derive(Debug, Clone, PartialEq, Eq)]
13pub struct BatchNoteTree(SimpleSmt<BATCH_NOTE_TREE_DEPTH>);
14
15impl BatchNoteTree {
16    /// Wrapper around [`SimpleSmt::with_contiguous_leaves`] which populates notes at contiguous
17    /// indices starting at index 0.
18    ///
19    /// # Errors
20    /// Returns an error if the number of entries exceeds the maximum tree capacity, that is
21    /// 2^{depth}.
22    pub fn with_contiguous_leaves<'a>(
23        entries: impl IntoIterator<Item = (NoteId, &'a NoteMetadata)>,
24    ) -> Result<Self, MerkleError> {
25        let leaves = entries
26            .into_iter()
27            .map(|(note_id, metadata)| compute_note_commitment(note_id, metadata));
28
29        SimpleSmt::with_contiguous_leaves(leaves).map(Self)
30    }
31
32    /// Returns the root of the tree
33    pub fn root(&self) -> Word {
34        self.0.root()
35    }
36
37    /// Returns the number of non-empty leaves in this tree.
38    pub fn num_leaves(&self) -> usize {
39        self.0.num_leaves()
40    }
41
42    /// Removes the note at the given `index` form the tree by inserting [`EMPTY_WORD`].
43    ///
44    /// # Errors
45    ///
46    /// Returns an error if:
47    /// - the `index` is equal to or exceeds
48    ///   [`MAX_OUTPUT_NOTES_PER_BATCH`](crate::constants::MAX_OUTPUT_NOTES_PER_BATCH).
49    pub fn remove(&mut self, index: u64) -> Result<(), MerkleError> {
50        let key = LeafIndex::new(index)?;
51        self.0.insert(key, EMPTY_WORD);
52
53        Ok(())
54    }
55
56    /// Consumes the batch note tree and returns the underlying [`SimpleSmt`].
57    pub fn into_smt(self) -> SimpleSmt<BATCH_NOTE_TREE_DEPTH> {
58        self.0
59    }
60}
61
62// SERIALIZATION
63// ================================================================================================
64
65impl Serializable for BatchNoteTree {
66    fn write_into<W: ByteWriter>(&self, target: &mut W) {
67        self.0.leaves().collect::<Vec<_>>().write_into(target);
68    }
69}
70
71impl Deserializable for BatchNoteTree {
72    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
73        let leaves = Vec::read_from(source)?;
74        let smt = SimpleSmt::with_leaves(leaves.into_iter()).map_err(|err| {
75            DeserializationError::UnknownError(format!(
76                "failed to deserialize BatchNoteTree: {err}"
77            ))
78        })?;
79        Ok(Self(smt))
80    }
81}
miden_protocol/batch/note_tree.rs

miden_protocol/batch/
note_tree.rs
