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

miden_protocol/block/
note_tree.rs
