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

miden_protocol/batch/
note_tree.rs
