miden_protocol/block/
note_tree.rs

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

miden_protocol/block/
note_tree.rs
