miden-crypto/src/merkle/store/mod.rs
src/merkle/store/mod.rsRaw
1use super::{
2 BTreeMap, BTreeSet, EmptySubtreeRoots, MerkleError, MerklePath, MerklePathSet, MerkleTree,
3 NodeIndex, RootPath, Rpo256, RpoDigest, SimpleSmt, ValuePath, Vec, Word,
4};
5
6#[cfg(test)]
7mod tests;
8
9#[derive(Debug, Default, Copy, Clone, Eq, PartialEq)]
10pub struct Node {
11 left: RpoDigest,
12 right: RpoDigest,
13}
14
15/// An in-memory data store for Merkle-lized data.
16///
17/// This is a in memory data store for Merkle trees, this store allows all the nodes of multiple
18/// trees to live as long as necessary and without duplication, this allows the implementation of
19/// space efficient persistent data structures.
20///
21/// Example usage:
22///
23/// ```rust
24/// # use miden_crypto::{ZERO, Felt, Word};
25/// # use miden_crypto::merkle::{NodeIndex, MerkleStore, MerkleTree};
26/// # use miden_crypto::hash::rpo::Rpo256;
27/// # const fn int_to_node(value: u64) -> Word {
28/// # [Felt::new(value), ZERO, ZERO, ZERO]
29/// # }
30/// # let A = int_to_node(1);
31/// # let B = int_to_node(2);
32/// # let C = int_to_node(3);
33/// # let D = int_to_node(4);
34/// # let E = int_to_node(5);
35/// # let F = int_to_node(6);
36/// # let G = int_to_node(7);
37/// # let H0 = int_to_node(8);
38/// # let H1 = int_to_node(9);
39/// # let T0 = MerkleTree::new([A, B, C, D, E, F, G, H0].to_vec()).expect("even number of leaves provided");
40/// # let T1 = MerkleTree::new([A, B, C, D, E, F, G, H1].to_vec()).expect("even number of leaves provided");
41/// # let ROOT0 = T0.root();
42/// # let ROOT1 = T1.root();
43/// let mut store = MerkleStore::new();
44///
45/// // the store is initialized with the SMT empty nodes
46/// assert_eq!(store.num_internal_nodes(), 64);
47///
48/// // populates the store with two merkle trees, common nodes are shared
49/// store.add_merkle_tree([A, B, C, D, E, F, G, H0]);
50/// store.add_merkle_tree([A, B, C, D, E, F, G, H1]);
51///
52/// // every leaf except the last are the same
53/// for i in 0..7 {
54/// let d0 = store.get_node(ROOT0, NodeIndex::new(3, i)).unwrap();
55/// let d1 = store.get_node(ROOT1, NodeIndex::new(3, i)).unwrap();
56/// assert_eq!(d0, d1, "Both trees have the same leaf at pos {i}");
57/// }
58///
59/// // The leafs A-B-C-D are the same for both trees, so are their 2 immediate parents
60/// for i in 0..4 {
61/// let d0 = store.get_path(ROOT0, NodeIndex::new(3, i)).unwrap();
62/// let d1 = store.get_path(ROOT1, NodeIndex::new(3, i)).unwrap();
63/// assert_eq!(d0.path[0..2], d1.path[0..2], "Both sub-trees are equal up to two levels");
64/// }
65///
66/// // Common internal nodes are shared, the two added trees have a total of 30, but the store has
67/// // only 10 new entries, corresponding to the 10 unique internal nodes of these trees.
68/// assert_eq!(store.num_internal_nodes() - 64, 10);
69/// ```
70#[derive(Debug, Clone, Eq, PartialEq)]
71pub struct MerkleStore {
72 nodes: BTreeMap<RpoDigest, Node>,
73}
74
75impl Default for MerkleStore {
76 fn default() -> Self {
77 Self::new()
78 }
79}
80
81impl MerkleStore {
82 // CONSTRUCTORS
83 // --------------------------------------------------------------------------------------------
84
85 /// Creates an empty `MerkleStore` instance.
86 pub fn new() -> MerkleStore {
87 // pre-populate the store with the empty hashes
88 let subtrees = EmptySubtreeRoots::empty_hashes(64);
89 let nodes = subtrees
90 .iter()
91 .copied()
92 .zip(subtrees.iter().skip(1).copied())
93 .map(|(child, parent)| {
94 (
95 parent,
96 Node {
97 left: child,
98 right: child,
99 },
100 )
101 })
102 .collect();
103
104 MerkleStore { nodes }
105 }
106
107 /// Appends the provided merkle tree represented by its `leaves` to the set.
108 pub fn with_merkle_tree<I>(mut self, leaves: I) -> Result<Self, MerkleError>
109 where
110 I: IntoIterator<Item = Word>,
111 {
112 self.add_merkle_tree(leaves)?;
113 Ok(self)
114 }
115
116 /// Appends the provided sparse merkle tree represented by its `entries` to the set.
117 pub fn with_sparse_merkle_tree<R, I>(mut self, entries: R) -> Result<Self, MerkleError>
118 where
119 R: IntoIterator<IntoIter = I>,
120 I: Iterator<Item = (u64, Word)> + ExactSizeIterator,
121 {
122 self.add_sparse_merkle_tree(entries)?;
123 Ok(self)
124 }
125
126 /// Appends the provided merkle path set.
127 pub fn with_merkle_path(
128 mut self,
129 index_value: u64,
130 node: Word,
131 path: MerklePath,
132 ) -> Result<Self, MerkleError> {
133 self.add_merkle_path(index_value, node, path)?;
134 Ok(self)
135 }
136
137 /// Appends the provided merkle path set.
138 pub fn with_merkle_paths<I>(mut self, paths: I) -> Result<Self, MerkleError>
139 where
140 I: IntoIterator<Item = (u64, Word, MerklePath)>,
141 {
142 self.add_merkle_paths(paths)?;
143 Ok(self)
144 }
145
146 // PUBLIC ACCESSORS
147 // --------------------------------------------------------------------------------------------
148
149 /// Return a count of the non-leaf nodes in the store.
150 pub fn num_internal_nodes(&self) -> usize {
151 self.nodes.len()
152 }
153
154 /// Returns the node at `index` rooted on the tree `root`.
155 ///
156 /// # Errors
157 ///
158 /// This method can return the following errors:
159 /// - `RootNotInStore` if the `root` is not present in the store.
160 /// - `NodeNotInStore` if a node needed to traverse from `root` to `index` is not present in the store.
161 pub fn get_node(&self, root: Word, index: NodeIndex) -> Result<Word, MerkleError> {
162 let mut hash: RpoDigest = root.into();
163
164 // corner case: check the root is in the store when called with index `NodeIndex::root()`
165 self.nodes
166 .get(&hash)
167 .ok_or(MerkleError::RootNotInStore(hash.into()))?;
168
169 for bit in index.bit_iterator().rev() {
170 let node = self
171 .nodes
172 .get(&hash)
173 .ok_or(MerkleError::NodeNotInStore(hash.into(), index))?;
174 hash = if bit { node.right } else { node.left }
175 }
176
177 Ok(hash.into())
178 }
179
180 /// Returns the node at the specified `index` and its opening to the `root`.
181 ///
182 /// The path starts at the sibling of the target leaf.
183 ///
184 /// # Errors
185 ///
186 /// This method can return the following errors:
187 /// - `RootNotInStore` if the `root` is not present in the store.
188 /// - `NodeNotInStore` if a node needed to traverse from `root` to `index` is not present in the store.
189 pub fn get_path(&self, root: Word, index: NodeIndex) -> Result<ValuePath, MerkleError> {
190 let mut hash: RpoDigest = root.into();
191 let mut path = Vec::with_capacity(index.depth().into());
192
193 // corner case: check the root is in the store when called with index `NodeIndex::root()`
194 self.nodes
195 .get(&hash)
196 .ok_or(MerkleError::RootNotInStore(hash.into()))?;
197
198 for bit in index.bit_iterator().rev() {
199 let node = self
200 .nodes
201 .get(&hash)
202 .ok_or(MerkleError::NodeNotInStore(hash.into(), index))?;
203
204 hash = if bit {
205 path.push(node.left.into());
206 node.right
207 } else {
208 path.push(node.right.into());
209 node.left
210 }
211 }
212
213 // the path is computed from root to leaf, so it must be reversed
214 path.reverse();
215
216 Ok(ValuePath {
217 value: hash.into(),
218 path: MerklePath::new(path),
219 })
220 }
221
222 // STATE MUTATORS
223 // --------------------------------------------------------------------------------------------
224
225 /// Adds all the nodes of a Merkle tree represented by `leaves`.
226 ///
227 /// This will instantiate a Merkle tree using `leaves` and include all the nodes into the
228 /// store.
229 ///
230 /// # Errors
231 ///
232 /// This method may return the following errors:
233 /// - `DepthTooSmall` if leaves is empty or contains only 1 element
234 /// - `NumLeavesNotPowerOfTwo` if the number of leaves is not a power-of-two
235 pub fn add_merkle_tree<I>(&mut self, leaves: I) -> Result<Word, MerkleError>
236 where
237 I: IntoIterator<Item = Word>,
238 {
239 let leaves: Vec<_> = leaves.into_iter().collect();
240 if leaves.len() < 2 {
241 return Err(MerkleError::DepthTooSmall(leaves.len() as u8));
242 }
243
244 let layers = leaves.len().ilog2();
245 let tree = MerkleTree::new(leaves)?;
246
247 let mut depth = 0;
248 let mut parent_offset = 1;
249 let mut child_offset = 2;
250 while depth < layers {
251 let layer_size = 1usize << depth;
252 for _ in 0..layer_size {
253 // merkle tree is using level form representation, so left and right siblings are
254 // next to each other
255 let left = tree.nodes[child_offset];
256 let right = tree.nodes[child_offset + 1];
257 self.nodes.insert(
258 tree.nodes[parent_offset].into(),
259 Node {
260 left: left.into(),
261 right: right.into(),
262 },
263 );
264 parent_offset += 1;
265 child_offset += 2;
266 }
267 depth += 1;
268 }
269
270 Ok(tree.nodes[1])
271 }
272
273 /// Adds all the nodes of a Sparse Merkle tree represented by `entries`.
274 ///
275 /// This will instantiate a Sparse Merkle tree using `entries` and include all the nodes into
276 /// the store.
277 ///
278 /// # Errors
279 ///
280 /// This will return `InvalidEntriesCount` if the length of `entries` is not `63`.
281 pub fn add_sparse_merkle_tree<R, I>(&mut self, entries: R) -> Result<Word, MerkleError>
282 where
283 R: IntoIterator<IntoIter = I>,
284 I: Iterator<Item = (u64, Word)> + ExactSizeIterator,
285 {
286 let smt = SimpleSmt::new(SimpleSmt::MAX_DEPTH)?.with_leaves(entries)?;
287 for branch in smt.store.branches.values() {
288 let parent = Rpo256::merge(&[branch.left, branch.right]);
289 self.nodes.insert(
290 parent,
291 Node {
292 left: branch.left,
293 right: branch.right,
294 },
295 );
296 }
297
298 Ok(smt.root())
299 }
300
301 /// Adds all the nodes of a Merkle path represented by `path`, opening to `node`. Returns the
302 /// new root.
303 ///
304 /// This will compute the sibling elements determined by the Merkle `path` and `node`, and
305 /// include all the nodes into the store.
306 pub fn add_merkle_path(
307 &mut self,
308 index_value: u64,
309 mut node: Word,
310 path: MerklePath,
311 ) -> Result<Word, MerkleError> {
312 let mut index = NodeIndex::new(self.nodes.len() as u8, index_value);
313
314 for sibling in path {
315 let (left, right) = match index.is_value_odd() {
316 true => (sibling, node),
317 false => (node, sibling),
318 };
319 let parent = Rpo256::merge(&[left.into(), right.into()]);
320 self.nodes.insert(
321 parent,
322 Node {
323 left: left.into(),
324 right: right.into(),
325 },
326 );
327
328 index.move_up();
329 node = parent.into();
330 }
331
332 Ok(node)
333 }
334
335 /// Adds all the nodes of multiple Merkle paths into the store.
336 ///
337 /// This will compute the sibling elements for each Merkle `path` and include all the nodes
338 /// into the store.
339 ///
340 /// For further reference, check [MerkleStore::add_merkle_path].
341 ///
342 /// # Errors
343 ///
344 /// Every path must resolve to the same root, otherwise this will return an `ConflictingRoots`
345 /// error.
346 pub fn add_merkle_paths<I>(&mut self, paths: I) -> Result<Word, MerkleError>
347 where
348 I: IntoIterator<Item = (u64, Word, MerklePath)>,
349 {
350 let paths: Vec<(u64, Word, MerklePath)> = paths.into_iter().collect();
351
352 let roots: BTreeSet<RpoDigest> = paths
353 .iter()
354 .map(|(index, node, path)| path.compute_root(*index, *node).into())
355 .collect();
356
357 if roots.len() != 1 {
358 return Err(MerkleError::ConflictingRoots(
359 roots.iter().map(|v| Word::from(*v)).collect(),
360 ));
361 }
362
363 for (index_value, node, path) in paths {
364 self.add_merkle_path(index_value, node, path)?;
365 }
366
367 Ok(roots.iter().next().unwrap().into())
368 }
369
370 /// Appends the provided [MerklePathSet] into the store.
371 ///
372 /// For further reference, check [MerkleStore::add_merkle_path].
373 pub fn add_merkle_path_set(&mut self, path_set: &MerklePathSet) -> Result<Word, MerkleError> {
374 let root = path_set.root();
375 for (index, path) in path_set.to_paths() {
376 self.add_merkle_path(index, path.value, path.path)?;
377 }
378 Ok(root)
379 }
380
381 /// Sets a node to `value`.
382 ///
383 /// # Errors
384 ///
385 /// This method can return the following errors:
386 /// - `RootNotInStore` if the `root` is not present in the store.
387 /// - `NodeNotInStore` if a node needed to traverse from `root` to `index` is not present in the store.
388 pub fn set_node(
389 &mut self,
390 mut root: Word,
391 index: NodeIndex,
392 value: Word,
393 ) -> Result<RootPath, MerkleError> {
394 let node = value;
395 let ValuePath { value, path } = self.get_path(root, index)?;
396
397 // performs the update only if the node value differs from the opening
398 if node != value {
399 root = self.add_merkle_path(index.value(), node, path.clone())?;
400 }
401
402 Ok(RootPath { root, path })
403 }
404
405 pub fn merge_roots(&mut self, root1: Word, root2: Word) -> Result<Word, MerkleError> {
406 let root1: RpoDigest = root1.into();
407 let root2: RpoDigest = root2.into();
408
409 if !self.nodes.contains_key(&root1) {
410 Err(MerkleError::NodeNotInStore(
411 root1.into(),
412 NodeIndex::new(0, 0),
413 ))
414 } else if !self.nodes.contains_key(&root1) {
415 Err(MerkleError::NodeNotInStore(
416 root2.into(),
417 NodeIndex::new(0, 0),
418 ))
419 } else {
420 let parent: Word = Rpo256::merge(&[root1, root2]).into();
421 self.nodes.insert(
422 parent.into(),
423 Node {
424 left: root1,
425 right: root2,
426 },
427 );
428
429 Ok(parent)
430 }
431 }
432}