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