miden-crypto/src/hash/rescue/rpo/tests.rs
src/hash/rescue/rpo/tests.rsRaw
1use alloc::{collections::BTreeSet, vec::Vec};
2
3use proptest::prelude::*;
4use rand_utils::rand_value;
5
6use super::{
7 super::{apply_inv_sbox, apply_sbox, ALPHA, INV_ALPHA},
8 Felt, FieldElement, Hasher, Rpo256, RpoDigest, StarkField, STATE_WIDTH, ZERO,
9};
10use crate::{
11 hash::rescue::{BINARY_CHUNK_SIZE, CAPACITY_RANGE, RATE_WIDTH},
12 Word, ONE,
13};
14
15#[test]
16fn test_sbox() {
17 let state = [Felt::new(rand_value()); STATE_WIDTH];
18
19 let mut expected = state;
20 expected.iter_mut().for_each(|v| *v = v.exp(ALPHA));
21
22 let mut actual = state;
23 apply_sbox(&mut actual);
24
25 assert_eq!(expected, actual);
26}
27
28#[test]
29fn test_inv_sbox() {
30 let state = [Felt::new(rand_value()); STATE_WIDTH];
31
32 let mut expected = state;
33 expected.iter_mut().for_each(|v| *v = v.exp(INV_ALPHA));
34
35 let mut actual = state;
36 apply_inv_sbox(&mut actual);
37
38 assert_eq!(expected, actual);
39}
40
41#[test]
42fn hash_elements_vs_merge() {
43 let elements = [Felt::new(rand_value()); 8];
44
45 let digests: [RpoDigest; 2] = [
46 RpoDigest::new(elements[..4].try_into().unwrap()),
47 RpoDigest::new(elements[4..].try_into().unwrap()),
48 ];
49
50 let m_result = Rpo256::merge(&digests);
51 let h_result = Rpo256::hash_elements(&elements);
52 assert_eq!(m_result, h_result);
53}
54
55#[test]
56fn merge_vs_merge_in_domain() {
57 let elements = [Felt::new(rand_value()); 8];
58
59 let digests: [RpoDigest; 2] = [
60 RpoDigest::new(elements[..4].try_into().unwrap()),
61 RpoDigest::new(elements[4..].try_into().unwrap()),
62 ];
63 let merge_result = Rpo256::merge(&digests);
64
65 // ------------- merge with domain = 0 -------------
66
67 // set domain to ZERO. This should not change the result.
68 let domain = ZERO;
69
70 let merge_in_domain_result = Rpo256::merge_in_domain(&digests, domain);
71 assert_eq!(merge_result, merge_in_domain_result);
72
73 // ------------- merge with domain = 1 -------------
74
75 // set domain to ONE. This should change the result.
76 let domain = ONE;
77
78 let merge_in_domain_result = Rpo256::merge_in_domain(&digests, domain);
79 assert_ne!(merge_result, merge_in_domain_result);
80}
81
82#[test]
83fn hash_elements_vs_merge_with_int() {
84 let tmp = [Felt::new(rand_value()); 4];
85 let seed = RpoDigest::new(tmp);
86
87 // ----- value fits into a field element ------------------------------------------------------
88 let val: Felt = Felt::new(rand_value());
89 let m_result = Rpo256::merge_with_int(seed, val.as_int());
90
91 let mut elements = seed.as_elements().to_vec();
92 elements.push(val);
93 let h_result = Rpo256::hash_elements(&elements);
94
95 assert_eq!(m_result, h_result);
96
97 // ----- value does not fit into a field element ----------------------------------------------
98 let val = Felt::MODULUS + 2;
99 let m_result = Rpo256::merge_with_int(seed, val);
100
101 let mut elements = seed.as_elements().to_vec();
102 elements.push(Felt::new(val));
103 elements.push(ONE);
104 let h_result = Rpo256::hash_elements(&elements);
105
106 assert_eq!(m_result, h_result);
107}
108
109#[test]
110fn hash_padding() {
111 // adding a zero bytes at the end of a byte string should result in a different hash
112 let r1 = Rpo256::hash(&[1_u8, 2, 3]);
113 let r2 = Rpo256::hash(&[1_u8, 2, 3, 0]);
114 assert_ne!(r1, r2);
115
116 // same as above but with bigger inputs
117 let r1 = Rpo256::hash(&[1_u8, 2, 3, 4, 5, 6]);
118 let r2 = Rpo256::hash(&[1_u8, 2, 3, 4, 5, 6, 0]);
119 assert_ne!(r1, r2);
120
121 // same as above but with input splitting over two elements
122 let r1 = Rpo256::hash(&[1_u8, 2, 3, 4, 5, 6, 7]);
123 let r2 = Rpo256::hash(&[1_u8, 2, 3, 4, 5, 6, 7, 0]);
124 assert_ne!(r1, r2);
125
126 // same as above but with multiple zeros
127 let r1 = Rpo256::hash(&[1_u8, 2, 3, 4, 5, 6, 7, 0, 0]);
128 let r2 = Rpo256::hash(&[1_u8, 2, 3, 4, 5, 6, 7, 0, 0, 0, 0]);
129 assert_ne!(r1, r2);
130}
131
132#[test]
133fn hash_padding_no_extra_permutation_call() {
134 use crate::hash::rescue::DIGEST_RANGE;
135
136 // Implementation
137 let num_bytes = BINARY_CHUNK_SIZE * RATE_WIDTH;
138 let mut buffer = vec![0_u8; num_bytes];
139 *buffer.last_mut().unwrap() = 97;
140 let r1 = Rpo256::hash(&buffer);
141
142 // Expected
143 let final_chunk = [0_u8, 0, 0, 0, 0, 0, 97, 1];
144 let mut state = [ZERO; STATE_WIDTH];
145 // padding when hashing bytes
146 state[CAPACITY_RANGE.start] = Felt::from(RATE_WIDTH as u8);
147 *state.last_mut().unwrap() = Felt::new(u64::from_le_bytes(final_chunk));
148 Rpo256::apply_permutation(&mut state);
149
150 assert_eq!(&r1[0..4], &state[DIGEST_RANGE]);
151}
152
153#[test]
154fn hash_elements_padding() {
155 let e1 = [Felt::new(rand_value()); 2];
156 let e2 = [e1[0], e1[1], ZERO];
157
158 let r1 = Rpo256::hash_elements(&e1);
159 let r2 = Rpo256::hash_elements(&e2);
160 assert_ne!(r1, r2);
161}
162
163#[test]
164fn hash_elements() {
165 let elements = [
166 ZERO,
167 ONE,
168 Felt::new(2),
169 Felt::new(3),
170 Felt::new(4),
171 Felt::new(5),
172 Felt::new(6),
173 Felt::new(7),
174 ];
175
176 let digests: [RpoDigest; 2] = [
177 RpoDigest::new(elements[..4].try_into().unwrap()),
178 RpoDigest::new(elements[4..8].try_into().unwrap()),
179 ];
180
181 let m_result = Rpo256::merge(&digests);
182 let h_result = Rpo256::hash_elements(&elements);
183 assert_eq!(m_result, h_result);
184}
185
186#[test]
187fn hash_empty() {
188 let elements: Vec<Felt> = vec![];
189
190 let zero_digest = RpoDigest::default();
191 let h_result = Rpo256::hash_elements(&elements);
192 assert_eq!(zero_digest, h_result);
193}
194
195#[test]
196fn hash_empty_bytes() {
197 let bytes: Vec<u8> = vec![];
198
199 let zero_digest = RpoDigest::default();
200 let h_result = Rpo256::hash(&bytes);
201 assert_eq!(zero_digest, h_result);
202}
203
204#[test]
205fn hash_test_vectors() {
206 let elements = [
207 ZERO,
208 ONE,
209 Felt::new(2),
210 Felt::new(3),
211 Felt::new(4),
212 Felt::new(5),
213 Felt::new(6),
214 Felt::new(7),
215 Felt::new(8),
216 Felt::new(9),
217 Felt::new(10),
218 Felt::new(11),
219 Felt::new(12),
220 Felt::new(13),
221 Felt::new(14),
222 Felt::new(15),
223 Felt::new(16),
224 Felt::new(17),
225 Felt::new(18),
226 ];
227
228 for i in 0..elements.len() {
229 let expected = RpoDigest::new(EXPECTED[i]);
230 let result = Rpo256::hash_elements(&elements[..(i + 1)]);
231 assert_eq!(result, expected);
232 }
233}
234
235#[test]
236fn sponge_bytes_with_remainder_length_wont_panic() {
237 // this test targets to assert that no panic will happen with the edge case of having an inputs
238 // with length that is not divisible by the used binary chunk size. 113 is a non-negligible
239 // input length that is prime; hence guaranteed to not be divisible by any choice of chunk
240 // size.
241 //
242 // this is a preliminary test to the fuzzy-stress of proptest.
243 Rpo256::hash(&[0; 113]);
244}
245
246#[test]
247fn sponge_collision_for_wrapped_field_element() {
248 let a = Rpo256::hash(&[0; 8]);
249 let b = Rpo256::hash(&Felt::MODULUS.to_le_bytes());
250 assert_ne!(a, b);
251}
252
253#[test]
254fn sponge_zeroes_collision() {
255 let mut zeroes = Vec::with_capacity(255);
256 let mut set = BTreeSet::new();
257 (0..255).for_each(|_| {
258 let hash = Rpo256::hash(&zeroes);
259 zeroes.push(0);
260 // panic if a collision was found
261 assert!(set.insert(hash));
262 });
263}
264
265proptest! {
266 #[test]
267 fn rpo256_wont_panic_with_arbitrary_input(ref bytes in any::<Vec<u8>>()) {
268 Rpo256::hash(bytes);
269 }
270}
271
272const EXPECTED: [Word; 19] = [
273 [
274 Felt::new(18126731724905382595),
275 Felt::new(7388557040857728717),
276 Felt::new(14290750514634285295),
277 Felt::new(7852282086160480146),
278 ],
279 [
280 Felt::new(10139303045932500183),
281 Felt::new(2293916558361785533),
282 Felt::new(15496361415980502047),
283 Felt::new(17904948502382283940),
284 ],
285 [
286 Felt::new(17457546260239634015),
287 Felt::new(803990662839494686),
288 Felt::new(10386005777401424878),
289 Felt::new(18168807883298448638),
290 ],
291 [
292 Felt::new(13072499238647455740),
293 Felt::new(10174350003422057273),
294 Felt::new(9201651627651151113),
295 Felt::new(6872461887313298746),
296 ],
297 [
298 Felt::new(2903803350580990546),
299 Felt::new(1838870750730563299),
300 Felt::new(4258619137315479708),
301 Felt::new(17334260395129062936),
302 ],
303 [
304 Felt::new(8571221005243425262),
305 Felt::new(3016595589318175865),
306 Felt::new(13933674291329928438),
307 Felt::new(678640375034313072),
308 ],
309 [
310 Felt::new(16314113978986502310),
311 Felt::new(14587622368743051587),
312 Felt::new(2808708361436818462),
313 Felt::new(10660517522478329440),
314 ],
315 [
316 Felt::new(2242391899857912644),
317 Felt::new(12689382052053305418),
318 Felt::new(235236990017815546),
319 Felt::new(5046143039268215739),
320 ],
321 [
322 Felt::new(5218076004221736204),
323 Felt::new(17169400568680971304),
324 Felt::new(8840075572473868990),
325 Felt::new(12382372614369863623),
326 ],
327 [
328 Felt::new(9783834557155203486),
329 Felt::new(12317263104955018849),
330 Felt::new(3933748931816109604),
331 Felt::new(1843043029836917214),
332 ],
333 [
334 Felt::new(14498234468286984551),
335 Felt::new(16837257669834682387),
336 Felt::new(6664141123711355107),
337 Felt::new(4590460158294697186),
338 ],
339 [
340 Felt::new(4661800562479916067),
341 Felt::new(11794407552792839953),
342 Felt::new(9037742258721863712),
343 Felt::new(6287820818064278819),
344 ],
345 [
346 Felt::new(7752693085194633729),
347 Felt::new(7379857372245835536),
348 Felt::new(9270229380648024178),
349 Felt::new(10638301488452560378),
350 ],
351 [
352 Felt::new(11542686762698783357),
353 Felt::new(15570714990728449027),
354 Felt::new(7518801014067819501),
355 Felt::new(12706437751337583515),
356 ],
357 [
358 Felt::new(9553923701032839042),
359 Felt::new(7281190920209838818),
360 Felt::new(2488477917448393955),
361 Felt::new(5088955350303368837),
362 ],
363 [
364 Felt::new(4935426252518736883),
365 Felt::new(12584230452580950419),
366 Felt::new(8762518969632303998),
367 Felt::new(18159875708229758073),
368 ],
369 [
370 Felt::new(12795429638314178838),
371 Felt::new(14360248269767567855),
372 Felt::new(3819563852436765058),
373 Felt::new(10859123583999067291),
374 ],
375 [
376 Felt::new(2695742617679420093),
377 Felt::new(9151515850666059759),
378 Felt::new(15855828029180595485),
379 Felt::new(17190029785471463210),
380 ],
381 [
382 Felt::new(13205273108219124830),
383 Felt::new(2524898486192849221),
384 Felt::new(14618764355375283547),
385 Felt::new(10615614265042186874),
386 ],
387];