miden_protocol/block/
note_tree.rs

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

miden_protocol/block/
note_tree.rs
