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