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

miden_protocol/batch/
note_tree.rs
