miden_objects/block/
note_tree.rs

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

miden_objects/block/
note_tree.rs
