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