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