miden-crypto/src/hash/rpo/tests.rs
src/hash/rpo/tests.rsRaw
1use super::{
2 Felt, FieldElement, Hasher, Rpo256, RpoDigest, StarkField, ALPHA, INV_ALPHA, ONE, STATE_WIDTH,
3 ZERO,
4};
5use crate::utils::collections::{BTreeSet, Vec};
6use core::convert::TryInto;
7use proptest::prelude::*;
8use rand_utils::rand_value;
9
10#[test]
11fn test_alphas() {
12 let e: Felt = Felt::new(rand_value());
13 let e_exp = e.exp(ALPHA);
14 assert_eq!(e, e_exp.exp(INV_ALPHA));
15}
16
17#[test]
18fn test_sbox() {
19 let state = [Felt::new(rand_value()); STATE_WIDTH];
20
21 let mut expected = state;
22 expected.iter_mut().for_each(|v| *v = v.exp(ALPHA));
23
24 let mut actual = state;
25 Rpo256::apply_sbox(&mut actual);
26
27 assert_eq!(expected, actual);
28}
29
30#[test]
31fn test_inv_sbox() {
32 let state = [Felt::new(rand_value()); STATE_WIDTH];
33
34 let mut expected = state;
35 expected.iter_mut().for_each(|v| *v = v.exp(INV_ALPHA));
36
37 let mut actual = state;
38 Rpo256::apply_inv_sbox(&mut actual);
39
40 assert_eq!(expected, actual);
41}
42
43#[test]
44fn hash_elements_vs_merge() {
45 let elements = [Felt::new(rand_value()); 8];
46
47 let digests: [RpoDigest; 2] = [
48 RpoDigest::new(elements[..4].try_into().unwrap()),
49 RpoDigest::new(elements[4..].try_into().unwrap()),
50 ];
51
52 let m_result = Rpo256::merge(&digests);
53 let h_result = Rpo256::hash_elements(&elements);
54 assert_eq!(m_result, h_result);
55}
56
57#[test]
58fn merge_vs_merge_in_domain() {
59 let elements = [Felt::new(rand_value()); 8];
60
61 let digests: [RpoDigest; 2] = [
62 RpoDigest::new(elements[..4].try_into().unwrap()),
63 RpoDigest::new(elements[4..].try_into().unwrap()),
64 ];
65 let merge_result = Rpo256::merge(&digests);
66
67 // ------------- merge with domain = 0 ----------------------------------------------------------
68
69 // set domain to ZERO. This should not change the result.
70 let domain = ZERO;
71
72 let merge_in_domain_result = Rpo256::merge_in_domain(&digests, domain);
73 assert_eq!(merge_result, merge_in_domain_result);
74
75 // ------------- merge with domain = 1 ----------------------------------------------------------
76
77 // set domain to ONE. This should change the result.
78 let domain = ONE;
79
80 let merge_in_domain_result = Rpo256::merge_in_domain(&digests, domain);
81 assert_ne!(merge_result, merge_in_domain_result);
82}
83
84#[test]
85fn hash_elements_vs_merge_with_int() {
86 let tmp = [Felt::new(rand_value()); 4];
87 let seed = RpoDigest::new(tmp);
88
89 // ----- value fits into a field element ------------------------------------------------------
90 let val: Felt = Felt::new(rand_value());
91 let m_result = Rpo256::merge_with_int(seed, val.as_int());
92
93 let mut elements = seed.as_elements().to_vec();
94 elements.push(val);
95 let h_result = Rpo256::hash_elements(&elements);
96
97 assert_eq!(m_result, h_result);
98
99 // ----- value does not fit into a field element ----------------------------------------------
100 let val = Felt::MODULUS + 2;
101 let m_result = Rpo256::merge_with_int(seed, val);
102
103 let mut elements = seed.as_elements().to_vec();
104 elements.push(Felt::new(val));
105 elements.push(Felt::new(1));
106 let h_result = Rpo256::hash_elements(&elements);
107
108 assert_eq!(m_result, h_result);
109}
110
111#[test]
112fn hash_padding() {
113 // adding a zero bytes at the end of a byte string should result in a different hash
114 let r1 = Rpo256::hash(&[1_u8, 2, 3]);
115 let r2 = Rpo256::hash(&[1_u8, 2, 3, 0]);
116 assert_ne!(r1, r2);
117
118 // same as above but with bigger inputs
119 let r1 = Rpo256::hash(&[1_u8, 2, 3, 4, 5, 6]);
120 let r2 = Rpo256::hash(&[1_u8, 2, 3, 4, 5, 6, 0]);
121 assert_ne!(r1, r2);
122
123 // same as above but with input splitting over two elements
124 let r1 = Rpo256::hash(&[1_u8, 2, 3, 4, 5, 6, 7]);
125 let r2 = Rpo256::hash(&[1_u8, 2, 3, 4, 5, 6, 7, 0]);
126 assert_ne!(r1, r2);
127
128 // same as above but with multiple zeros
129 let r1 = Rpo256::hash(&[1_u8, 2, 3, 4, 5, 6, 7, 0, 0]);
130 let r2 = Rpo256::hash(&[1_u8, 2, 3, 4, 5, 6, 7, 0, 0, 0, 0]);
131 assert_ne!(r1, r2);
132}
133
134#[test]
135fn hash_elements_padding() {
136 let e1 = [Felt::new(rand_value()); 2];
137 let e2 = [e1[0], e1[1], ZERO];
138
139 let r1 = Rpo256::hash_elements(&e1);
140 let r2 = Rpo256::hash_elements(&e2);
141 assert_ne!(r1, r2);
142}
143
144#[test]
145fn hash_elements() {
146 let elements = [
147 Felt::new(0),
148 Felt::new(1),
149 Felt::new(2),
150 Felt::new(3),
151 Felt::new(4),
152 Felt::new(5),
153 Felt::new(6),
154 Felt::new(7),
155 ];
156
157 let digests: [RpoDigest; 2] = [
158 RpoDigest::new(elements[..4].try_into().unwrap()),
159 RpoDigest::new(elements[4..8].try_into().unwrap()),
160 ];
161
162 let m_result = Rpo256::merge(&digests);
163 let h_result = Rpo256::hash_elements(&elements);
164 assert_eq!(m_result, h_result);
165}
166
167#[test]
168fn hash_test_vectors() {
169 let elements = [
170 Felt::new(0),
171 Felt::new(1),
172 Felt::new(2),
173 Felt::new(3),
174 Felt::new(4),
175 Felt::new(5),
176 Felt::new(6),
177 Felt::new(7),
178 Felt::new(8),
179 Felt::new(9),
180 Felt::new(10),
181 Felt::new(11),
182 Felt::new(12),
183 Felt::new(13),
184 Felt::new(14),
185 Felt::new(15),
186 Felt::new(16),
187 Felt::new(17),
188 Felt::new(18),
189 ];
190
191 for i in 0..elements.len() {
192 let expected = RpoDigest::new(EXPECTED[i]);
193 let result = Rpo256::hash_elements(&elements[..(i + 1)]);
194 assert_eq!(result, expected);
195 }
196}
197
198#[test]
199fn sponge_bytes_with_remainder_length_wont_panic() {
200 // this test targets to assert that no panic will happen with the edge case of having an inputs
201 // with length that is not divisible by the used binary chunk size. 113 is a non-negligible
202 // input length that is prime; hence guaranteed to not be divisible by any choice of chunk
203 // size.
204 //
205 // this is a preliminary test to the fuzzy-stress of proptest.
206 Rpo256::hash(&vec![0; 113]);
207}
208
209#[test]
210fn sponge_collision_for_wrapped_field_element() {
211 let a = Rpo256::hash(&[0; 8]);
212 let b = Rpo256::hash(&Felt::MODULUS.to_le_bytes());
213 assert_ne!(a, b);
214}
215
216#[test]
217fn sponge_zeroes_collision() {
218 let mut zeroes = Vec::with_capacity(255);
219 let mut set = BTreeSet::new();
220 (0..255).for_each(|_| {
221 let hash = Rpo256::hash(&zeroes);
222 zeroes.push(0);
223 // panic if a collision was found
224 assert!(set.insert(hash));
225 });
226}
227
228proptest! {
229 #[test]
230 fn rpo256_wont_panic_with_arbitrary_input(ref vec in any::<Vec<u8>>()) {
231 Rpo256::hash(&vec);
232 }
233}
234
235const EXPECTED: [[Felt; 4]; 19] = [
236 [
237 Felt::new(1502364727743950833),
238 Felt::new(5880949717274681448),
239 Felt::new(162790463902224431),
240 Felt::new(6901340476773664264),
241 ],
242 [
243 Felt::new(7478710183745780580),
244 Felt::new(3308077307559720969),
245 Felt::new(3383561985796182409),
246 Felt::new(17205078494700259815),
247 ],
248 [
249 Felt::new(17439912364295172999),
250 Felt::new(17979156346142712171),
251 Felt::new(8280795511427637894),
252 Felt::new(9349844417834368814),
253 ],
254 [
255 Felt::new(5105868198472766874),
256 Felt::new(13090564195691924742),
257 Felt::new(1058904296915798891),
258 Felt::new(18379501748825152268),
259 ],
260 [
261 Felt::new(9133662113608941286),
262 Felt::new(12096627591905525991),
263 Felt::new(14963426595993304047),
264 Felt::new(13290205840019973377),
265 ],
266 [
267 Felt::new(3134262397541159485),
268 Felt::new(10106105871979362399),
269 Felt::new(138768814855329459),
270 Felt::new(15044809212457404677),
271 ],
272 [
273 Felt::new(162696376578462826),
274 Felt::new(4991300494838863586),
275 Felt::new(660346084748120605),
276 Felt::new(13179389528641752698),
277 ],
278 [
279 Felt::new(2242391899857912644),
280 Felt::new(12689382052053305418),
281 Felt::new(235236990017815546),
282 Felt::new(5046143039268215739),
283 ],
284 [
285 Felt::new(9585630502158073976),
286 Felt::new(1310051013427303477),
287 Felt::new(7491921222636097758),
288 Felt::new(9417501558995216762),
289 ],
290 [
291 Felt::new(1994394001720334744),
292 Felt::new(10866209900885216467),
293 Felt::new(13836092831163031683),
294 Felt::new(10814636682252756697),
295 ],
296 [
297 Felt::new(17486854790732826405),
298 Felt::new(17376549265955727562),
299 Felt::new(2371059831956435003),
300 Felt::new(17585704935858006533),
301 ],
302 [
303 Felt::new(11368277489137713825),
304 Felt::new(3906270146963049287),
305 Felt::new(10236262408213059745),
306 Felt::new(78552867005814007),
307 ],
308 [
309 Felt::new(17899847381280262181),
310 Felt::new(14717912805498651446),
311 Felt::new(10769146203951775298),
312 Felt::new(2774289833490417856),
313 ],
314 [
315 Felt::new(3794717687462954368),
316 Felt::new(4386865643074822822),
317 Felt::new(8854162840275334305),
318 Felt::new(7129983987107225269),
319 ],
320 [
321 Felt::new(7244773535611633983),
322 Felt::new(19359923075859320),
323 Felt::new(10898655967774994333),
324 Felt::new(9319339563065736480),
325 ],
326 [
327 Felt::new(4935426252518736883),
328 Felt::new(12584230452580950419),
329 Felt::new(8762518969632303998),
330 Felt::new(18159875708229758073),
331 ],
332 [
333 Felt::new(14871230873837295931),
334 Felt::new(11225255908868362971),
335 Felt::new(18100987641405432308),
336 Felt::new(1559244340089644233),
337 ],
338 [
339 Felt::new(8348203744950016968),
340 Felt::new(4041411241960726733),
341 Felt::new(17584743399305468057),
342 Felt::new(16836952610803537051),
343 ],
344 [
345 Felt::new(16139797453633030050),
346 Felt::new(1090233424040889412),
347 Felt::new(10770255347785669036),
348 Felt::new(16982398877290254028),
349 ],
350];