miden_objects/batch/
note_tree.rs

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

miden_objects/batch/
note_tree.rs
