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