miden_objects/batch/
note_tree.rs

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

miden_objects/batch/
note_tree.rs
