miden_objects/transaction/
chain_mmr.rs

1use alloc::{collections::BTreeMap, vec::Vec};
2
3use vm_core::utils::{Deserializable, Serializable};
4
5use crate::{
6    block::{BlockHeader, BlockNumber},
7    crypto::merkle::{InnerNodeInfo, MmrPeaks, PartialMmr},
8    ChainMmrError,
9};
10
11// CHAIN MMR
12// ================================================================================================
13
14/// A struct that represents the chain Merkle Mountain Range (MMR).
15///
16/// The MMR allows for efficient authentication of input notes during transaction execution.
17/// Authentication is achieved by providing inclusion proofs for the notes consumed in the
18/// transaction against the chain MMR root associated with the latest block known at the time
19/// of transaction execution.
20///
21/// [ChainMmr] represents a partial view into the actual MMR and contains authentication paths
22/// for a limited set of blocks. The intent is to include only the blocks relevant for execution
23/// of a specific transaction (i.e., the blocks corresponding to all input notes and the one needed
24/// to validate the seed of a new account, if applicable).
25#[derive(Debug, Clone, PartialEq, Eq)]
26pub struct ChainMmr {
27    /// Partial view of the Chain MMR with authentication paths for the blocks listed below.
28    mmr: PartialMmr,
29    /// A map of block_num |-> block_header for all blocks for which the partial MMR contains
30    /// authentication paths.
31    blocks: BTreeMap<BlockNumber, BlockHeader>,
32}
33
34impl ChainMmr {
35    // CONSTRUCTOR
36    // --------------------------------------------------------------------------------------------
37    /// Returns a new [ChainMmr] instantiated from the provided partial MMR and a list of block
38    /// headers.
39    ///
40    /// # Errors
41    /// Returns an error if:
42    /// - block_num for any of the blocks is greater than the chain length implied by the provided
43    ///   partial MMR.
44    /// - The same block appears more than once in the provided list of block headers.
45    /// - The partial MMR does not track authentication paths for any of the specified blocks.
46    pub fn new(mmr: PartialMmr, blocks: Vec<BlockHeader>) -> Result<Self, ChainMmrError> {
47        let chain_length = mmr.forest();
48
49        let mut block_map = BTreeMap::new();
50        for block in blocks.into_iter() {
51            if block.block_num().as_usize() >= chain_length {
52                return Err(ChainMmrError::block_num_too_big(chain_length, block.block_num()));
53            }
54
55            if block_map.insert(block.block_num(), block).is_some() {
56                return Err(ChainMmrError::duplicate_block(block.block_num()));
57            }
58
59            if !mmr.is_tracked(block.block_num().as_usize()) {
60                return Err(ChainMmrError::untracked_block(block.block_num()));
61            }
62        }
63
64        Ok(Self { mmr, blocks: block_map })
65    }
66
67    // PUBLIC ACCESSORS
68    // --------------------------------------------------------------------------------------------
69
70    /// Returns peaks of this MMR.
71    pub fn peaks(&self) -> MmrPeaks {
72        self.mmr.peaks()
73    }
74
75    /// Returns total number of blocks contain in the chain described by this MMR.
76    pub fn chain_length(&self) -> BlockNumber {
77        BlockNumber::from(
78            u32::try_from(self.mmr.forest())
79                .expect("chain mmr should never contain more than u32::MAX blocks"),
80        )
81    }
82
83    /// Returns true if the block is present in this chain MMR.
84    pub fn contains_block(&self, block_num: BlockNumber) -> bool {
85        self.blocks.contains_key(&block_num)
86    }
87
88    /// Returns the block header for the specified block, or None if the block is not present in
89    /// this chain MMR.
90    pub fn get_block(&self, block_num: BlockNumber) -> Option<&BlockHeader> {
91        self.blocks.get(&block_num)
92    }
93
94    // DATA MUTATORS
95    // --------------------------------------------------------------------------------------------
96
97    /// Appends the provided block header to this chain MMR. This method assumes that the provided
98    /// block header is for the next block in the chain.
99    ///
100    /// If `track` parameter is set to true, the authentication path for the provided block header
101    /// will be added to this chain MMR.
102    ///
103    /// # Panics
104    /// Panics if the `block_header.block_num` is not equal to the current chain length (i.e., the
105    /// provided block header is not the next block in the chain).
106    pub fn add_block(&mut self, block_header: BlockHeader, track: bool) {
107        assert_eq!(block_header.block_num(), self.chain_length());
108        self.mmr.add(block_header.hash(), track);
109    }
110
111    // ITERATORS
112    // --------------------------------------------------------------------------------------------
113
114    /// Returns an iterator over the inner nodes of authentication paths contained in this chain
115    /// MMR.
116    pub fn inner_nodes(&self) -> impl Iterator<Item = InnerNodeInfo> + '_ {
117        self.mmr.inner_nodes(
118            self.blocks.values().map(|block| (block.block_num().as_usize(), block.hash())),
119        )
120    }
121}
122
123impl Serializable for ChainMmr {
124    fn write_into<W: miden_crypto::utils::ByteWriter>(&self, target: &mut W) {
125        self.mmr.write_into(target);
126        self.blocks.len().write_into(target);
127        for block in self.blocks.values() {
128            block.write_into(target);
129        }
130    }
131}
132
133impl Deserializable for ChainMmr {
134    fn read_from<R: miden_crypto::utils::ByteReader>(
135        source: &mut R,
136    ) -> Result<Self, miden_crypto::utils::DeserializationError> {
137        let mmr = PartialMmr::read_from(source)?;
138        let block_count = usize::read_from(source)?;
139        let mut blocks = BTreeMap::new();
140        for _ in 0..block_count {
141            let block = BlockHeader::read_from(source)?;
142            blocks.insert(block.block_num(), block);
143        }
144        Ok(Self { mmr, blocks })
145    }
146}
147// TESTS
148// ================================================================================================
149
150#[cfg(test)]
151mod tests {
152    use vm_core::utils::{Deserializable, Serializable};
153
154    use super::ChainMmr;
155    use crate::{
156        alloc::vec::Vec,
157        block::{BlockHeader, BlockNumber},
158        crypto::merkle::{Mmr, PartialMmr},
159        Digest,
160    };
161
162    #[test]
163    fn test_chain_mmr_add() {
164        // create chain MMR with 3 blocks - i.e., 2 peaks
165        let mut mmr = Mmr::default();
166        for i in 0..3 {
167            let block_header = int_to_block_header(i);
168            mmr.add(block_header.hash());
169        }
170        let partial_mmr: PartialMmr = mmr.peaks().into();
171        let mut chain_mmr = ChainMmr::new(partial_mmr, Vec::new()).unwrap();
172
173        // add a new block to the chain MMR, this reduces the number of peaks to 1
174        let block_num = 3;
175        let bock_header = int_to_block_header(block_num);
176        mmr.add(bock_header.hash());
177        chain_mmr.add_block(bock_header, true);
178
179        assert_eq!(
180            mmr.open(block_num as usize).unwrap(),
181            chain_mmr.mmr.open(block_num as usize).unwrap().unwrap()
182        );
183
184        // add one more block to the chain MMR, the number of peaks is again 2
185        let block_num = 4;
186        let bock_header = int_to_block_header(block_num);
187        mmr.add(bock_header.hash());
188        chain_mmr.add_block(bock_header, true);
189
190        assert_eq!(
191            mmr.open(block_num as usize).unwrap(),
192            chain_mmr.mmr.open(block_num as usize).unwrap().unwrap()
193        );
194
195        // add one more block to the chain MMR, the number of peaks is still 2
196        let block_num = 5;
197        let bock_header = int_to_block_header(block_num);
198        mmr.add(bock_header.hash());
199        chain_mmr.add_block(bock_header, true);
200
201        assert_eq!(
202            mmr.open(block_num as usize).unwrap(),
203            chain_mmr.mmr.open(block_num as usize).unwrap().unwrap()
204        );
205    }
206
207    #[test]
208    fn tst_chain_mmr_serialization() {
209        // create chain MMR with 3 blocks - i.e., 2 peaks
210        let mut mmr = Mmr::default();
211        for i in 0..3 {
212            let block_header = int_to_block_header(i);
213            mmr.add(block_header.hash());
214        }
215        let partial_mmr: PartialMmr = mmr.peaks().into();
216        let chain_mmr = ChainMmr::new(partial_mmr, Vec::new()).unwrap();
217
218        let bytes = chain_mmr.to_bytes();
219        let deserialized = ChainMmr::read_from_bytes(&bytes).unwrap();
220
221        assert_eq!(chain_mmr, deserialized);
222    }
223
224    fn int_to_block_header(block_num: impl Into<BlockNumber>) -> BlockHeader {
225        BlockHeader::new(
226            0,
227            Digest::default(),
228            block_num.into(),
229            Digest::default(),
230            Digest::default(),
231            Digest::default(),
232            Digest::default(),
233            Digest::default(),
234            Digest::default(),
235            Digest::default(),
236            0,
237        )
238    }
239}
miden_objects/transaction/chain_mmr.rs

miden_objects/transaction/
chain_mmr.rs
