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