miden-crypto/src/merkle/tiered_smt/tests.rs
src/merkle/tiered_smt/tests.rsRaw
1use super::{
2 super::{super::ONE, Felt, MerkleStore, WORD_SIZE},
3 get_remaining_path, EmptySubtreeRoots, NodeIndex, Rpo256, RpoDigest, TieredSmt, Word,
4};
5
6#[test]
7fn tsmt_insert_one() {
8 let mut smt = TieredSmt::new();
9 let mut store = MerkleStore::default();
10
11 let raw = 0b_01101001_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
12 let key = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)]);
13 let value = [ONE; WORD_SIZE];
14
15 // since the tree is empty, the first node will be inserted at depth 16 and the index will be
16 // 16 most significant bits of the key
17 let index = NodeIndex::make(16, raw >> 48);
18 let leaf_node = compute_leaf_node(key, value, 16);
19 let tree_root = store.set_node(smt.root().into(), index, leaf_node.into()).unwrap().root;
20
21 smt.insert(key, value).unwrap();
22
23 assert_eq!(smt.root(), tree_root.into());
24
25 // make sure the value was inserted, and the node is at the expected index
26 assert_eq!(smt.get_value(key).unwrap(), value);
27 assert_eq!(smt.get_node(index).unwrap(), leaf_node);
28
29 // make sure the paths we get from the store and the tree match
30 let expected_path = store.get_path(tree_root, index).unwrap();
31 assert_eq!(smt.get_path(index).unwrap(), expected_path.path);
32}
33
34#[test]
35fn tsmt_insert_two() {
36 let mut smt = TieredSmt::new();
37 let mut store = MerkleStore::default();
38
39 // --- insert the first value ---------------------------------------------
40 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
41 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
42 let val_a = [ONE; WORD_SIZE];
43 smt.insert(key_a, val_a).unwrap();
44
45 // --- insert the second value --------------------------------------------
46 // the key for this value has the same 16-bit prefix as the key for the first value,
47 // thus, on insertions, both values should be pushed to depth 32 tier
48 let raw_b = 0b_10101010_10101010_10011111_11111111_10010110_10010011_11100000_00000000_u64;
49 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
50 let val_b = [Felt::new(2); WORD_SIZE];
51 smt.insert(key_b, val_b).unwrap();
52
53 // --- build Merkle store with equivalent data ----------------------------
54 let mut tree_root = get_init_root();
55 let index_a = NodeIndex::make(32, raw_a >> 32);
56 let leaf_node_a = compute_leaf_node(key_a, val_a, 32);
57 tree_root = store.set_node(tree_root, index_a, leaf_node_a.into()).unwrap().root;
58
59 let index_b = NodeIndex::make(32, raw_b >> 32);
60 let leaf_node_b = compute_leaf_node(key_b, val_b, 32);
61 tree_root = store.set_node(tree_root, index_b, leaf_node_b.into()).unwrap().root;
62
63 // --- verify that data is consistent between store and tree --------------
64
65 assert_eq!(smt.root(), tree_root.into());
66
67 assert_eq!(smt.get_value(key_a).unwrap(), val_a);
68 assert_eq!(smt.get_node(index_a).unwrap(), leaf_node_a);
69 let expected_path = store.get_path(tree_root, index_a).unwrap().path;
70 assert_eq!(smt.get_path(index_a).unwrap(), expected_path);
71
72 assert_eq!(smt.get_value(key_b).unwrap(), val_b);
73 assert_eq!(smt.get_node(index_b).unwrap(), leaf_node_b);
74 let expected_path = store.get_path(tree_root, index_b).unwrap().path;
75 assert_eq!(smt.get_path(index_b).unwrap(), expected_path);
76}
77
78#[test]
79fn tsmt_insert_three() {
80 let mut smt = TieredSmt::new();
81 let mut store = MerkleStore::default();
82
83 // --- insert the first value ---------------------------------------------
84 let raw_a = 0b_10101010_10101010_00011111_11111111_10010110_10010011_11100000_00000000_u64;
85 let key_a = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_a)]);
86 let val_a = [ONE; WORD_SIZE];
87 smt.insert(key_a, val_a).unwrap();
88
89 // --- insert the second value --------------------------------------------
90 // the key for this value has the same 16-bit prefix as the key for the first value,
91 // thus, on insertions, both values should be pushed to depth 32 tier
92 let raw_b = 0b_10101010_10101010_10011111_11111111_10010110_10010011_11100000_00000000_u64;
93 let key_b = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_b)]);
94 let val_b = [Felt::new(2); WORD_SIZE];
95 smt.insert(key_b, val_b).unwrap();
96
97 // --- insert the third value ---------------------------------------------
98 // the key for this value has the same 16-bit prefix as the keys for the first two,
99 // values; thus, on insertions, it will be inserted into depth 32 tier, but will not
100 // affect locations of the other two values
101 let raw_c = 0b_10101010_10101010_11011111_11111111_10010110_10010011_11100000_00000000_u64;
102 let key_c = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw_c)]);
103 let val_c = [Felt::new(3); WORD_SIZE];
104 smt.insert(key_c, val_c).unwrap();
105
106 // --- build Merkle store with equivalent data ----------------------------
107 let mut tree_root = get_init_root();
108 let index_a = NodeIndex::make(32, raw_a >> 32);
109 let leaf_node_a = compute_leaf_node(key_a, val_a, 32);
110 tree_root = store.set_node(tree_root, index_a, leaf_node_a.into()).unwrap().root;
111
112 let index_b = NodeIndex::make(32, raw_b >> 32);
113 let leaf_node_b = compute_leaf_node(key_b, val_b, 32);
114 tree_root = store.set_node(tree_root, index_b, leaf_node_b.into()).unwrap().root;
115
116 let index_c = NodeIndex::make(32, raw_c >> 32);
117 let leaf_node_c = compute_leaf_node(key_c, val_c, 32);
118 tree_root = store.set_node(tree_root, index_c, leaf_node_c.into()).unwrap().root;
119
120 // --- verify that data is consistent between store and tree --------------
121
122 assert_eq!(smt.root(), tree_root.into());
123
124 assert_eq!(smt.get_value(key_a).unwrap(), val_a);
125 assert_eq!(smt.get_node(index_a).unwrap(), leaf_node_a);
126 let expected_path = store.get_path(tree_root, index_a).unwrap().path;
127 assert_eq!(smt.get_path(index_a).unwrap(), expected_path);
128
129 assert_eq!(smt.get_value(key_b).unwrap(), val_b);
130 assert_eq!(smt.get_node(index_b).unwrap(), leaf_node_b);
131 let expected_path = store.get_path(tree_root, index_b).unwrap().path;
132 assert_eq!(smt.get_path(index_b).unwrap(), expected_path);
133
134 assert_eq!(smt.get_value(key_c).unwrap(), val_c);
135 assert_eq!(smt.get_node(index_c).unwrap(), leaf_node_c);
136 let expected_path = store.get_path(tree_root, index_c).unwrap().path;
137 assert_eq!(smt.get_path(index_c).unwrap(), expected_path);
138}
139
140#[test]
141fn tsmt_update() {
142 let mut smt = TieredSmt::new();
143 let mut store = MerkleStore::default();
144
145 // --- insert a value into the tree ---------------------------------------
146 let raw = 0b_01101001_01101100_00011111_11111111_10010110_10010011_11100000_00000000_u64;
147 let key = RpoDigest::from([ONE, ONE, ONE, Felt::new(raw)]);
148 let value_a = [ONE; WORD_SIZE];
149 smt.insert(key, value_a).unwrap();
150
151 // --- update value ---------------------------------------
152 let value_b = [Felt::new(2); WORD_SIZE];
153 smt.insert(key, value_b).unwrap();
154
155 // --- verify consistency -------------------------------------------------
156 let mut tree_root = get_init_root();
157 let index = NodeIndex::make(16, raw >> 48);
158 let leaf_node = compute_leaf_node(key, value_b, 16);
159 tree_root = store.set_node(tree_root, index, leaf_node.into()).unwrap().root;
160
161 assert_eq!(smt.root(), tree_root.into());
162
163 assert_eq!(smt.get_value(key).unwrap(), value_b);
164 assert_eq!(smt.get_node(index).unwrap(), leaf_node);
165 let expected_path = store.get_path(tree_root, index).unwrap().path;
166 assert_eq!(smt.get_path(index).unwrap(), expected_path);
167}
168
169// HELPER FUNCTIONS
170// ================================================================================================
171
172fn get_init_root() -> Word {
173 EmptySubtreeRoots::empty_hashes(64)[0].into()
174}
175
176fn compute_leaf_node(key: RpoDigest, value: Word, depth: u8) -> RpoDigest {
177 let remaining_path = get_remaining_path(key, depth as u32);
178 Rpo256::merge_in_domain(&[remaining_path, value.into()], depth.into())
179}