miden_objects/block/
note_tree.rs

1use alloc::string::ToString;
2
3use miden_crypto::merkle::SparseMerklePath;
4
5use crate::batch::BatchNoteTree;
6use crate::crypto::merkle::{LeafIndex, MerkleError, SimpleSmt};
7use crate::note::{NoteId, NoteMetadata, compute_note_commitment};
8use crate::utils::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable};
9use crate::{
10    BLOCK_NOTE_TREE_DEPTH,
11    MAX_BATCHES_PER_BLOCK,
12    MAX_OUTPUT_NOTES_PER_BATCH,
13    MAX_OUTPUT_NOTES_PER_BLOCK,
14    Word,
15};
16
17/// Wrapper over [SimpleSmt<BLOCK_NOTE_TREE_DEPTH>] for notes tree.
18///
19/// Each note is stored as two adjacent leaves: odd leaf for id, even leaf for metadata hash.
20/// ID's leaf index is calculated as [(batch_idx * MAX_NOTES_PER_BATCH + note_idx_in_batch) * 2].
21/// Metadata hash leaf is stored the next after id leaf: [id_index + 1].
22#[derive(Debug, Clone, PartialEq, Eq)]
23pub struct BlockNoteTree(SimpleSmt<BLOCK_NOTE_TREE_DEPTH>);
24
25impl BlockNoteTree {
26    /// Returns a new [`BlockNoteTree`] instantiated with entries set as specified by the provided
27    /// entries.
28    ///
29    /// Entry format: (note_index, note_id, note_metadata).
30    ///
31    /// Value of each leaf is computed as: `hash(note_id || note_metadata)`.
32    /// All leaves omitted from the entries list are set to [crate::EMPTY_WORD].
33    ///
34    /// # Errors
35    /// Returns an error if:
36    /// - The number of entries exceeds the maximum notes tree capacity, that is 2^16.
37    /// - The provided entries contain multiple values for the same key.
38    pub fn with_entries(
39        entries: impl IntoIterator<Item = (BlockNoteIndex, NoteId, NoteMetadata)>,
40    ) -> Result<Self, MerkleError> {
41        let leaves = entries.into_iter().map(|(index, note_id, metadata)| {
42            (index.leaf_index_value() as u64, compute_note_commitment(note_id, &metadata))
43        });
44
45        SimpleSmt::with_leaves(leaves).map(Self)
46    }
47
48    /// Returns a new, empty [`BlockNoteTree`].
49    pub fn empty() -> Self {
50        Self(SimpleSmt::new().expect("depth should be 16 and thus > 0 and <= 64"))
51    }
52
53    /// Inserts the given [`BatchNoteTree`] as a subtree into the block note tree at the specified
54    /// index.
55    ///
56    /// # Errors
57    ///
58    /// Returns an error if:
59    /// - the given batch index is greater or equal to [`MAX_BATCHES_PER_BLOCK`]
60    pub fn insert_batch_note_subtree(
61        &mut self,
62        batch_idx: u64,
63        batch_note_tree: BatchNoteTree,
64    ) -> Result<(), MerkleError> {
65        // Note that the subtree depth > depth error cannot occur, as the batch note tree's depth is
66        // smaller than the block note tree's depth.
67        // This is guaranteed through the definition of MAX_BATCHES_PER_BLOCK.
68        self.0.set_subtree(batch_idx, batch_note_tree.into_smt()).map(|_| ())
69    }
70
71    /// Returns the root of the tree
72    pub fn root(&self) -> Word {
73        self.0.root()
74    }
75
76    /// Returns merkle path for the note with specified batch/note indexes.
77    pub fn open(&self, index: BlockNoteIndex) -> SparseMerklePath {
78        // get the path to the leaf containing the note (path len = 16)
79        self.0.open(&index.leaf_index()).path
80    }
81
82    /// Returns the number of notes in this block note tree.
83    pub fn num_notes(&self) -> usize {
84        self.0.num_leaves()
85    }
86
87    /// Returns a boolean value indicating whether the block note tree is empty.
88    pub fn is_empty(&self) -> bool {
89        self.0.is_empty()
90    }
91}
92
93impl Default for BlockNoteTree {
94    fn default() -> Self {
95        Self(SimpleSmt::new().expect("Unreachable"))
96    }
97}
98
99// BLOCK NOTE INDEX
100// ================================================================================================
101
102/// Index of a block note.
103#[derive(Debug, Clone, Copy, PartialEq, Eq)]
104pub struct BlockNoteIndex {
105    batch_idx: usize,
106    note_idx_in_batch: usize,
107}
108
109impl BlockNoteIndex {
110    /// Creates a new [BlockNoteIndex].
111    ///
112    /// # Errors
113    ///
114    /// Returns `None` if the batch index is equal to or greater than [`MAX_BATCHES_PER_BLOCK`] or
115    /// if the note index is equal to or greater than [`MAX_OUTPUT_NOTES_PER_BATCH`].
116    pub fn new(batch_idx: usize, note_idx_in_batch: usize) -> Option<Self> {
117        if batch_idx >= MAX_BATCHES_PER_BLOCK || note_idx_in_batch >= MAX_OUTPUT_NOTES_PER_BATCH {
118            return None;
119        }
120
121        Some(Self { batch_idx, note_idx_in_batch })
122    }
123
124    /// Returns the batch index.
125    pub fn batch_idx(&self) -> usize {
126        self.batch_idx
127    }
128
129    /// Returns the note index in the batch.
130    pub fn note_idx_in_batch(&self) -> usize {
131        self.note_idx_in_batch
132    }
133
134    /// Returns the leaf index of the note in the note tree.
135    pub fn leaf_index(&self) -> LeafIndex<BLOCK_NOTE_TREE_DEPTH> {
136        LeafIndex::new(
137            (self.batch_idx() * MAX_OUTPUT_NOTES_PER_BATCH + self.note_idx_in_batch()) as u64,
138        )
139        .expect("Unreachable: Input values must be valid at this point")
140    }
141
142    /// Returns the leaf index value of the note in the note tree.
143    pub fn leaf_index_value(&self) -> u16 {
144        const _: () = assert!(
145            MAX_OUTPUT_NOTES_PER_BLOCK <= u16::MAX as usize + 1,
146            "Any note index is expected to fit in `u16`"
147        );
148
149        self.leaf_index()
150            .value()
151            .try_into()
152            .expect("Unreachable: Input values must be valid at this point")
153    }
154}
155
156// SERIALIZATION
157// ================================================================================================
158
159impl Serializable for BlockNoteTree {
160    fn write_into<W: ByteWriter>(&self, target: &mut W) {
161        target.write_u32(self.0.num_leaves() as u32);
162        target.write_many(self.0.leaves());
163    }
164}
165
166impl Deserializable for BlockNoteTree {
167    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
168        let count = source.read_u32()?;
169        let leaves = source.read_many(count as usize)?;
170
171        SimpleSmt::with_leaves(leaves)
172            .map(Self)
173            .map_err(|err| DeserializationError::InvalidValue(err.to_string()))
174    }
175}
176
177#[cfg(test)]
178mod tests {
179    use miden_crypto::merkle::SimpleSmt;
180    use miden_crypto::utils::{Deserializable, Serializable};
181
182    use super::BlockNoteTree;
183    use crate::Word;
184
185    #[test]
186    fn test_serialization() {
187        let data = core::iter::repeat(())
188            .enumerate()
189            .map(|(idx, ())| (idx as u64, Word::from([1, 0, 1, idx as u32])))
190            .take(100);
191        let initial_tree = BlockNoteTree(SimpleSmt::with_leaves(data).unwrap());
192
193        let serialized = initial_tree.to_bytes();
194        let deserialized_tree = BlockNoteTree::read_from_bytes(&serialized).unwrap();
195
196        assert_eq!(deserialized_tree, initial_tree);
197    }
198}
miden_objects/block/note_tree.rs

miden_objects/block/
note_tree.rs
