miden-crypto/src/hash/rescue/mod.rs
src/hash/rescue/mod.rsRaw
1use super::{
2 CubeExtension, Digest, ElementHasher, Felt, FieldElement, Hasher, StarkField, ONE, ZERO,
3};
4use core::ops::Range;
5
6mod mds;
7use mds::{apply_mds, MDS};
8
9mod rpo;
10pub use rpo::{Rpo256, RpoDigest};
11
12mod rpx;
13pub use rpx::{Rpx256, RpxDigest};
14
15#[cfg(test)]
16mod tests;
17
18// CONSTANTS
19// ================================================================================================
20
21/// The number of rounds is set to 7. For the RPO hash functions all rounds are uniform. For the
22/// RPX hash function, there are 3 different types of rounds.
23const NUM_ROUNDS: usize = 7;
24
25/// Sponge state is set to 12 field elements or 96 bytes; 8 elements are reserved for rate and
26/// the remaining 4 elements are reserved for capacity.
27const STATE_WIDTH: usize = 12;
28
29/// The rate portion of the state is located in elements 4 through 11.
30const RATE_RANGE: Range<usize> = 4..12;
31const RATE_WIDTH: usize = RATE_RANGE.end - RATE_RANGE.start;
32
33const INPUT1_RANGE: Range<usize> = 4..8;
34const INPUT2_RANGE: Range<usize> = 8..12;
35
36/// The capacity portion of the state is located in elements 0, 1, 2, and 3.
37const CAPACITY_RANGE: Range<usize> = 0..4;
38
39/// The output of the hash function is a digest which consists of 4 field elements or 32 bytes.
40///
41/// The digest is returned from state elements 4, 5, 6, and 7 (the first four elements of the
42/// rate portion).
43const DIGEST_RANGE: Range<usize> = 4..8;
44const DIGEST_SIZE: usize = DIGEST_RANGE.end - DIGEST_RANGE.start;
45
46/// The number of bytes needed to encoded a digest
47const DIGEST_BYTES: usize = 32;
48
49/// The number of byte chunks defining a field element when hashing a sequence of bytes
50const BINARY_CHUNK_SIZE: usize = 7;
51
52/// S-Box and Inverse S-Box powers;
53///
54/// The constants are defined for tests only because the exponentiations in the code are unrolled
55/// for efficiency reasons.
56#[cfg(test)]
57const ALPHA: u64 = 7;
58#[cfg(test)]
59const INV_ALPHA: u64 = 10540996611094048183;
60
61// SBOX FUNCTION
62// ================================================================================================
63
64#[inline(always)]
65fn apply_sbox(state: &mut [Felt; STATE_WIDTH]) {
66 state[0] = state[0].exp7();
67 state[1] = state[1].exp7();
68 state[2] = state[2].exp7();
69 state[3] = state[3].exp7();
70 state[4] = state[4].exp7();
71 state[5] = state[5].exp7();
72 state[6] = state[6].exp7();
73 state[7] = state[7].exp7();
74 state[8] = state[8].exp7();
75 state[9] = state[9].exp7();
76 state[10] = state[10].exp7();
77 state[11] = state[11].exp7();
78}
79
80// INVERSE SBOX FUNCTION
81// ================================================================================================
82
83#[inline(always)]
84fn apply_inv_sbox(state: &mut [Felt; STATE_WIDTH]) {
85 // compute base^10540996611094048183 using 72 multiplications per array element
86 // 10540996611094048183 = b1001001001001001001001001001000110110110110110110110110110110111
87
88 // compute base^10
89 let mut t1 = *state;
90 t1.iter_mut().for_each(|t| *t = t.square());
91
92 // compute base^100
93 let mut t2 = t1;
94 t2.iter_mut().for_each(|t| *t = t.square());
95
96 // compute base^100100
97 let t3 = exp_acc::<Felt, STATE_WIDTH, 3>(t2, t2);
98
99 // compute base^100100100100
100 let t4 = exp_acc::<Felt, STATE_WIDTH, 6>(t3, t3);
101
102 // compute base^100100100100100100100100
103 let t5 = exp_acc::<Felt, STATE_WIDTH, 12>(t4, t4);
104
105 // compute base^100100100100100100100100100100
106 let t6 = exp_acc::<Felt, STATE_WIDTH, 6>(t5, t3);
107
108 // compute base^1001001001001001001001001001000100100100100100100100100100100
109 let t7 = exp_acc::<Felt, STATE_WIDTH, 31>(t6, t6);
110
111 // compute base^1001001001001001001001001001000110110110110110110110110110110111
112 for (i, s) in state.iter_mut().enumerate() {
113 let a = (t7[i].square() * t6[i]).square().square();
114 let b = t1[i] * t2[i] * *s;
115 *s = a * b;
116 }
117
118 #[inline(always)]
119 fn exp_acc<B: StarkField, const N: usize, const M: usize>(
120 base: [B; N],
121 tail: [B; N],
122 ) -> [B; N] {
123 let mut result = base;
124 for _ in 0..M {
125 result.iter_mut().for_each(|r| *r = r.square());
126 }
127 result.iter_mut().zip(tail).for_each(|(r, t)| *r *= t);
128 result
129 }
130}
131
132// OPTIMIZATIONS
133// ================================================================================================
134
135#[cfg(all(target_feature = "sve", feature = "sve"))]
136#[link(name = "rpo_sve", kind = "static")]
137extern "C" {
138 fn add_constants_and_apply_sbox(
139 state: *mut std::ffi::c_ulong,
140 constants: *const std::ffi::c_ulong,
141 ) -> bool;
142 fn add_constants_and_apply_inv_sbox(
143 state: *mut std::ffi::c_ulong,
144 constants: *const std::ffi::c_ulong,
145 ) -> bool;
146}
147
148#[inline(always)]
149#[cfg(all(target_feature = "sve", feature = "sve"))]
150fn optimized_add_constants_and_apply_sbox(
151 state: &mut [Felt; STATE_WIDTH],
152 ark: &[Felt; STATE_WIDTH],
153) -> bool {
154 unsafe {
155 add_constants_and_apply_sbox(state.as_mut_ptr() as *mut u64, ark.as_ptr() as *const u64)
156 }
157}
158
159#[inline(always)]
160#[cfg(not(all(target_feature = "sve", feature = "sve")))]
161fn optimized_add_constants_and_apply_sbox(
162 _state: &mut [Felt; STATE_WIDTH],
163 _ark: &[Felt; STATE_WIDTH],
164) -> bool {
165 false
166}
167
168#[inline(always)]
169#[cfg(all(target_feature = "sve", feature = "sve"))]
170fn optimized_add_constants_and_apply_inv_sbox(
171 state: &mut [Felt; STATE_WIDTH],
172 ark: &[Felt; STATE_WIDTH],
173) -> bool {
174 unsafe {
175 add_constants_and_apply_inv_sbox(state.as_mut_ptr() as *mut u64, ark.as_ptr() as *const u64)
176 }
177}
178
179#[inline(always)]
180#[cfg(not(all(target_feature = "sve", feature = "sve")))]
181fn optimized_add_constants_and_apply_inv_sbox(
182 _state: &mut [Felt; STATE_WIDTH],
183 _ark: &[Felt; STATE_WIDTH],
184) -> bool {
185 false
186}
187
188#[inline(always)]
189fn add_constants(state: &mut [Felt; STATE_WIDTH], ark: &[Felt; STATE_WIDTH]) {
190 state.iter_mut().zip(ark).for_each(|(s, &k)| *s += k);
191}
192
193// ROUND CONSTANTS
194// ================================================================================================
195
196/// Rescue round constants;
197/// computed as in [specifications](https://github.com/ASDiscreteMathematics/rpo)
198///
199/// The constants are broken up into two arrays ARK1 and ARK2; ARK1 contains the constants for the
200/// first half of RPO round, and ARK2 contains constants for the second half of RPO round.
201const ARK1: [[Felt; STATE_WIDTH]; NUM_ROUNDS] = [
202 [
203 Felt::new(5789762306288267392),
204 Felt::new(6522564764413701783),
205 Felt::new(17809893479458208203),
206 Felt::new(107145243989736508),
207 Felt::new(6388978042437517382),
208 Felt::new(15844067734406016715),
209 Felt::new(9975000513555218239),
210 Felt::new(3344984123768313364),
211 Felt::new(9959189626657347191),
212 Felt::new(12960773468763563665),
213 Felt::new(9602914297752488475),
214 Felt::new(16657542370200465908),
215 ],
216 [
217 Felt::new(12987190162843096997),
218 Felt::new(653957632802705281),
219 Felt::new(4441654670647621225),
220 Felt::new(4038207883745915761),
221 Felt::new(5613464648874830118),
222 Felt::new(13222989726778338773),
223 Felt::new(3037761201230264149),
224 Felt::new(16683759727265180203),
225 Felt::new(8337364536491240715),
226 Felt::new(3227397518293416448),
227 Felt::new(8110510111539674682),
228 Felt::new(2872078294163232137),
229 ],
230 [
231 Felt::new(18072785500942327487),
232 Felt::new(6200974112677013481),
233 Felt::new(17682092219085884187),
234 Felt::new(10599526828986756440),
235 Felt::new(975003873302957338),
236 Felt::new(8264241093196931281),
237 Felt::new(10065763900435475170),
238 Felt::new(2181131744534710197),
239 Felt::new(6317303992309418647),
240 Felt::new(1401440938888741532),
241 Felt::new(8884468225181997494),
242 Felt::new(13066900325715521532),
243 ],
244 [
245 Felt::new(5674685213610121970),
246 Felt::new(5759084860419474071),
247 Felt::new(13943282657648897737),
248 Felt::new(1352748651966375394),
249 Felt::new(17110913224029905221),
250 Felt::new(1003883795902368422),
251 Felt::new(4141870621881018291),
252 Felt::new(8121410972417424656),
253 Felt::new(14300518605864919529),
254 Felt::new(13712227150607670181),
255 Felt::new(17021852944633065291),
256 Felt::new(6252096473787587650),
257 ],
258 [
259 Felt::new(4887609836208846458),
260 Felt::new(3027115137917284492),
261 Felt::new(9595098600469470675),
262 Felt::new(10528569829048484079),
263 Felt::new(7864689113198939815),
264 Felt::new(17533723827845969040),
265 Felt::new(5781638039037710951),
266 Felt::new(17024078752430719006),
267 Felt::new(109659393484013511),
268 Felt::new(7158933660534805869),
269 Felt::new(2955076958026921730),
270 Felt::new(7433723648458773977),
271 ],
272 [
273 Felt::new(16308865189192447297),
274 Felt::new(11977192855656444890),
275 Felt::new(12532242556065780287),
276 Felt::new(14594890931430968898),
277 Felt::new(7291784239689209784),
278 Felt::new(5514718540551361949),
279 Felt::new(10025733853830934803),
280 Felt::new(7293794580341021693),
281 Felt::new(6728552937464861756),
282 Felt::new(6332385040983343262),
283 Felt::new(13277683694236792804),
284 Felt::new(2600778905124452676),
285 ],
286 [
287 Felt::new(7123075680859040534),
288 Felt::new(1034205548717903090),
289 Felt::new(7717824418247931797),
290 Felt::new(3019070937878604058),
291 Felt::new(11403792746066867460),
292 Felt::new(10280580802233112374),
293 Felt::new(337153209462421218),
294 Felt::new(13333398568519923717),
295 Felt::new(3596153696935337464),
296 Felt::new(8104208463525993784),
297 Felt::new(14345062289456085693),
298 Felt::new(17036731477169661256),
299 ],
300];
301
302const ARK2: [[Felt; STATE_WIDTH]; NUM_ROUNDS] = [
303 [
304 Felt::new(6077062762357204287),
305 Felt::new(15277620170502011191),
306 Felt::new(5358738125714196705),
307 Felt::new(14233283787297595718),
308 Felt::new(13792579614346651365),
309 Felt::new(11614812331536767105),
310 Felt::new(14871063686742261166),
311 Felt::new(10148237148793043499),
312 Felt::new(4457428952329675767),
313 Felt::new(15590786458219172475),
314 Felt::new(10063319113072092615),
315 Felt::new(14200078843431360086),
316 ],
317 [
318 Felt::new(6202948458916099932),
319 Felt::new(17690140365333231091),
320 Felt::new(3595001575307484651),
321 Felt::new(373995945117666487),
322 Felt::new(1235734395091296013),
323 Felt::new(14172757457833931602),
324 Felt::new(707573103686350224),
325 Felt::new(15453217512188187135),
326 Felt::new(219777875004506018),
327 Felt::new(17876696346199469008),
328 Felt::new(17731621626449383378),
329 Felt::new(2897136237748376248),
330 ],
331 [
332 Felt::new(8023374565629191455),
333 Felt::new(15013690343205953430),
334 Felt::new(4485500052507912973),
335 Felt::new(12489737547229155153),
336 Felt::new(9500452585969030576),
337 Felt::new(2054001340201038870),
338 Felt::new(12420704059284934186),
339 Felt::new(355990932618543755),
340 Felt::new(9071225051243523860),
341 Felt::new(12766199826003448536),
342 Felt::new(9045979173463556963),
343 Felt::new(12934431667190679898),
344 ],
345 [
346 Felt::new(18389244934624494276),
347 Felt::new(16731736864863925227),
348 Felt::new(4440209734760478192),
349 Felt::new(17208448209698888938),
350 Felt::new(8739495587021565984),
351 Felt::new(17000774922218161967),
352 Felt::new(13533282547195532087),
353 Felt::new(525402848358706231),
354 Felt::new(16987541523062161972),
355 Felt::new(5466806524462797102),
356 Felt::new(14512769585918244983),
357 Felt::new(10973956031244051118),
358 ],
359 [
360 Felt::new(6982293561042362913),
361 Felt::new(14065426295947720331),
362 Felt::new(16451845770444974180),
363 Felt::new(7139138592091306727),
364 Felt::new(9012006439959783127),
365 Felt::new(14619614108529063361),
366 Felt::new(1394813199588124371),
367 Felt::new(4635111139507788575),
368 Felt::new(16217473952264203365),
369 Felt::new(10782018226466330683),
370 Felt::new(6844229992533662050),
371 Felt::new(7446486531695178711),
372 ],
373 [
374 Felt::new(3736792340494631448),
375 Felt::new(577852220195055341),
376 Felt::new(6689998335515779805),
377 Felt::new(13886063479078013492),
378 Felt::new(14358505101923202168),
379 Felt::new(7744142531772274164),
380 Felt::new(16135070735728404443),
381 Felt::new(12290902521256031137),
382 Felt::new(12059913662657709804),
383 Felt::new(16456018495793751911),
384 Felt::new(4571485474751953524),
385 Felt::new(17200392109565783176),
386 ],
387 [
388 Felt::new(17130398059294018733),
389 Felt::new(519782857322261988),
390 Felt::new(9625384390925085478),
391 Felt::new(1664893052631119222),
392 Felt::new(7629576092524553570),
393 Felt::new(3485239601103661425),
394 Felt::new(9755891797164033838),
395 Felt::new(15218148195153269027),
396 Felt::new(16460604813734957368),
397 Felt::new(9643968136937729763),
398 Felt::new(3611348709641382851),
399 Felt::new(18256379591337759196),
400 ],
401];