miden-crypto/src/merkle/simple_smt/tests.rs
src/merkle/simple_smt/tests.rsRaw
1use super::{
2 super::{InnerNodeInfo, MerkleError, MerkleTree, RpoDigest, SimpleSmt},
3 NodeIndex, Rpo256, Vec,
4};
5use crate::{
6 merkle::{empty_roots::EMPTY_WORD, int_to_leaf},
7 Word,
8};
9
10// TEST DATA
11// ================================================================================================
12
13const KEYS4: [u64; 4] = [0, 1, 2, 3];
14const KEYS8: [u64; 8] = [0, 1, 2, 3, 4, 5, 6, 7];
15
16const VALUES4: [Word; 4] = [int_to_leaf(1), int_to_leaf(2), int_to_leaf(3), int_to_leaf(4)];
17
18const VALUES8: [Word; 8] = [
19 int_to_leaf(1),
20 int_to_leaf(2),
21 int_to_leaf(3),
22 int_to_leaf(4),
23 int_to_leaf(5),
24 int_to_leaf(6),
25 int_to_leaf(7),
26 int_to_leaf(8),
27];
28
29const ZERO_VALUES8: [Word; 8] = [int_to_leaf(0); 8];
30
31// TESTS
32// ================================================================================================
33
34#[test]
35fn build_empty_tree() {
36 // tree of depth 3
37 let smt = SimpleSmt::new(3).unwrap();
38 let mt = MerkleTree::new(ZERO_VALUES8.to_vec()).unwrap();
39 assert_eq!(mt.root(), smt.root().into());
40}
41
42#[test]
43fn build_sparse_tree() {
44 let mut smt = SimpleSmt::new(3).unwrap();
45 let mut values = ZERO_VALUES8.to_vec();
46
47 // insert single value
48 let key = 6;
49 let new_node = int_to_leaf(7);
50 values[key as usize] = new_node;
51 let old_value = smt.update_leaf(key, new_node).expect("Failed to update leaf");
52 let mt2 = MerkleTree::new(values.clone()).unwrap();
53 assert_eq!(mt2.root(), smt.root().into());
54 assert_eq!(
55 mt2.get_path(NodeIndex::make(3, 6)).unwrap(),
56 smt.get_path(NodeIndex::make(3, 6)).unwrap()
57 );
58 assert_eq!(old_value, EMPTY_WORD);
59
60 // insert second value at distinct leaf branch
61 let key = 2;
62 let new_node = int_to_leaf(3);
63 values[key as usize] = new_node;
64 let old_value = smt.update_leaf(key, new_node).expect("Failed to update leaf");
65 let mt3 = MerkleTree::new(values).unwrap();
66 assert_eq!(mt3.root(), smt.root().into());
67 assert_eq!(
68 mt3.get_path(NodeIndex::make(3, 2)).unwrap(),
69 smt.get_path(NodeIndex::make(3, 2)).unwrap()
70 );
71 assert_eq!(old_value, EMPTY_WORD);
72}
73
74#[test]
75fn test_depth2_tree() {
76 let tree = SimpleSmt::with_leaves(2, KEYS4.into_iter().zip(VALUES4.into_iter())).unwrap();
77
78 // check internal structure
79 let (root, node2, node3) = compute_internal_nodes();
80 assert_eq!(root, tree.root());
81 assert_eq!(node2, tree.get_node(NodeIndex::make(1, 0)).unwrap());
82 assert_eq!(node3, tree.get_node(NodeIndex::make(1, 1)).unwrap());
83
84 // check get_node()
85 assert_eq!(VALUES4[0], *tree.get_node(NodeIndex::make(2, 0)).unwrap());
86 assert_eq!(VALUES4[1], *tree.get_node(NodeIndex::make(2, 1)).unwrap());
87 assert_eq!(VALUES4[2], *tree.get_node(NodeIndex::make(2, 2)).unwrap());
88 assert_eq!(VALUES4[3], *tree.get_node(NodeIndex::make(2, 3)).unwrap());
89
90 // check get_path(): depth 2
91 assert_eq!(vec![VALUES4[1].into(), node3], *tree.get_path(NodeIndex::make(2, 0)).unwrap());
92 assert_eq!(vec![VALUES4[0].into(), node3], *tree.get_path(NodeIndex::make(2, 1)).unwrap());
93 assert_eq!(vec![VALUES4[3].into(), node2], *tree.get_path(NodeIndex::make(2, 2)).unwrap());
94 assert_eq!(vec![VALUES4[2].into(), node2], *tree.get_path(NodeIndex::make(2, 3)).unwrap());
95
96 // check get_path(): depth 1
97 assert_eq!(vec![node3], *tree.get_path(NodeIndex::make(1, 0)).unwrap());
98 assert_eq!(vec![node2], *tree.get_path(NodeIndex::make(1, 1)).unwrap());
99}
100
101#[test]
102fn test_inner_node_iterator() -> Result<(), MerkleError> {
103 let tree = SimpleSmt::with_leaves(2, KEYS4.into_iter().zip(VALUES4.into_iter())).unwrap();
104
105 // check depth 2
106 assert_eq!(VALUES4[0], *tree.get_node(NodeIndex::make(2, 0)).unwrap());
107 assert_eq!(VALUES4[1], *tree.get_node(NodeIndex::make(2, 1)).unwrap());
108 assert_eq!(VALUES4[2], *tree.get_node(NodeIndex::make(2, 2)).unwrap());
109 assert_eq!(VALUES4[3], *tree.get_node(NodeIndex::make(2, 3)).unwrap());
110
111 // get parent nodes
112 let root = tree.root();
113 let l1n0 = tree.get_node(NodeIndex::make(1, 0))?;
114 let l1n1 = tree.get_node(NodeIndex::make(1, 1))?;
115 let l2n0 = tree.get_node(NodeIndex::make(2, 0))?;
116 let l2n1 = tree.get_node(NodeIndex::make(2, 1))?;
117 let l2n2 = tree.get_node(NodeIndex::make(2, 2))?;
118 let l2n3 = tree.get_node(NodeIndex::make(2, 3))?;
119
120 let nodes: Vec<InnerNodeInfo> = tree.inner_nodes().collect();
121 let expected = vec![
122 InnerNodeInfo {
123 value: root.into(),
124 left: l1n0.into(),
125 right: l1n1.into(),
126 },
127 InnerNodeInfo {
128 value: l1n0.into(),
129 left: l2n0.into(),
130 right: l2n1.into(),
131 },
132 InnerNodeInfo {
133 value: l1n1.into(),
134 left: l2n2.into(),
135 right: l2n3.into(),
136 },
137 ];
138 assert_eq!(nodes, expected);
139
140 Ok(())
141}
142
143#[test]
144fn update_leaf() {
145 let mut tree = SimpleSmt::with_leaves(3, KEYS8.into_iter().zip(VALUES8.into_iter())).unwrap();
146
147 // update one value
148 let key = 3;
149 let new_node = int_to_leaf(9);
150 let mut expected_values = VALUES8.to_vec();
151 expected_values[key] = new_node;
152 let expected_tree = MerkleTree::new(expected_values.clone()).unwrap();
153
154 let old_leaf = tree.update_leaf(key as u64, new_node).unwrap();
155 assert_eq!(expected_tree.root(), tree.root);
156 assert_eq!(old_leaf, VALUES8[key]);
157
158 // update another value
159 let key = 6;
160 let new_node = int_to_leaf(10);
161 expected_values[key] = new_node;
162 let expected_tree = MerkleTree::new(expected_values.clone()).unwrap();
163
164 let old_leaf = tree.update_leaf(key as u64, new_node).unwrap();
165 assert_eq!(expected_tree.root(), tree.root);
166 assert_eq!(old_leaf, VALUES8[key]);
167}
168
169#[test]
170fn small_tree_opening_is_consistent() {
171 // ____k____
172 // / \
173 // _i_ _j_
174 // / \ / \
175 // e f g h
176 // / \ / \ / \ / \
177 // a b 0 0 c 0 0 d
178
179 let z = EMPTY_WORD;
180
181 let a = Word::from(Rpo256::merge(&[z.into(); 2]));
182 let b = Word::from(Rpo256::merge(&[a.into(); 2]));
183 let c = Word::from(Rpo256::merge(&[b.into(); 2]));
184 let d = Word::from(Rpo256::merge(&[c.into(); 2]));
185
186 let e = RpoDigest::from(Rpo256::merge(&[a.into(), b.into()]));
187 let f = RpoDigest::from(Rpo256::merge(&[z.into(), z.into()]));
188 let g = RpoDigest::from(Rpo256::merge(&[c.into(), z.into()]));
189 let h = RpoDigest::from(Rpo256::merge(&[z.into(), d.into()]));
190
191 let i = RpoDigest::from(Rpo256::merge(&[e.into(), f.into()]));
192 let j = RpoDigest::from(Rpo256::merge(&[g.into(), h.into()]));
193
194 let k = RpoDigest::from(Rpo256::merge(&[i.into(), j.into()]));
195
196 let depth = 3;
197 let entries = vec![(0, a), (1, b), (4, c), (7, d)];
198 let tree = SimpleSmt::with_leaves(depth, entries).unwrap();
199
200 assert_eq!(tree.root(), RpoDigest::from(k));
201
202 let cases: Vec<(u8, u64, Vec<RpoDigest>)> = vec![
203 (3, 0, vec![b.into(), f, j]),
204 (3, 1, vec![a.into(), f, j]),
205 (3, 4, vec![z.into(), h, i]),
206 (3, 7, vec![z.into(), g, i]),
207 (2, 0, vec![f, j]),
208 (2, 1, vec![e, j]),
209 (2, 2, vec![h, i]),
210 (2, 3, vec![g, i]),
211 (1, 0, vec![j]),
212 (1, 1, vec![i]),
213 ];
214
215 for (depth, key, path) in cases {
216 let opening = tree.get_path(NodeIndex::make(depth, key)).unwrap();
217
218 assert_eq!(path, *opening);
219 }
220}
221
222#[test]
223fn fail_on_duplicates() {
224 let entries = [(1_u64, int_to_leaf(1)), (5, int_to_leaf(2)), (1_u64, int_to_leaf(3))];
225 let smt = SimpleSmt::with_leaves(64, entries);
226 assert!(smt.is_err());
227
228 let entries = [(1_u64, int_to_leaf(0)), (5, int_to_leaf(2)), (1_u64, int_to_leaf(0))];
229 let smt = SimpleSmt::with_leaves(64, entries);
230 assert!(smt.is_err());
231
232 let entries = [(1_u64, int_to_leaf(0)), (5, int_to_leaf(2)), (1_u64, int_to_leaf(1))];
233 let smt = SimpleSmt::with_leaves(64, entries);
234 assert!(smt.is_err());
235
236 let entries = [(1_u64, int_to_leaf(1)), (5, int_to_leaf(2)), (1_u64, int_to_leaf(0))];
237 let smt = SimpleSmt::with_leaves(64, entries);
238 assert!(smt.is_err());
239}
240
241#[test]
242fn with_no_duplicates_empty_node() {
243 let entries = [(1_u64, int_to_leaf(0)), (5, int_to_leaf(2))];
244 let smt = SimpleSmt::with_leaves(64, entries);
245 assert!(smt.is_ok());
246}
247
248// HELPER FUNCTIONS
249// --------------------------------------------------------------------------------------------
250
251fn compute_internal_nodes() -> (RpoDigest, RpoDigest, RpoDigest) {
252 let node2 = Rpo256::hash_elements(
253 &[VALUES4[0], VALUES4[1]]
254 .iter()
255 .map(|digest| *digest)
256 .collect::<Vec<Word>>()
257 .concat(),
258 );
259 let node3 = Rpo256::hash_elements(
260 &[VALUES4[2], VALUES4[3]]
261 .iter()
262 .map(|digest| *digest)
263 .collect::<Vec<Word>>()
264 .concat(),
265 );
266 let root = Rpo256::merge(&[node2, node3]);
267
268 (root.into(), node2.into(), node3.into())
269}