miden-crypto/src/hash/rpo/mod.rs
src/hash/rpo/mod.rsRaw
1use super::{ElementHasher, HashFn};
2use crate::{Felt, FieldElement, StarkField, ONE, ZERO};
3use core::{convert::TryInto, ops::Range};
4
5mod digest;
6pub use digest::RpoDigest256;
7
8mod mds_freq;
9use mds_freq::mds_multiply_freq;
10
11#[cfg(test)]
12mod tests;
13
14// CONSTANTS
15// ================================================================================================
16
17/// Sponge state is set to 12 field elements or 96 bytes; 8 elements are reserved for rate and
18/// the remaining 4 elements are reserved for capacity.
19const STATE_WIDTH: usize = 12;
20
21/// The rate portion of the state is located in elements 4 through 11.
22const RATE_RANGE: Range<usize> = 4..12;
23const RATE_WIDTH: usize = RATE_RANGE.end - RATE_RANGE.start;
24
25const INPUT1_RANGE: Range<usize> = 4..8;
26const INPUT2_RANGE: Range<usize> = 8..12;
27
28/// The capacity portion of the state is located in elements 0, 1, 2, and 3.
29const CAPACITY_RANGE: Range<usize> = 0..4;
30
31/// The output of the hash function is a digest which consists of 4 field elements or 32 bytes.
32///
33/// The digest is returned from state elements 4, 5, 6, and 7 (the first four elements of the
34/// rate portion).
35const DIGEST_RANGE: Range<usize> = 4..8;
36const DIGEST_SIZE: usize = DIGEST_RANGE.end - DIGEST_RANGE.start;
37
38/// The number of rounds is set to 7 to target 128-bit security level
39const NUM_ROUNDS: usize = 7;
40
41/// The number of byte chunks defining a field element when hashing a sequence of bytes
42const BINARY_CHUNK_SIZE: usize = 7;
43
44/// S-Box and Inverse S-Box powers;
45///
46/// The constants are defined for tests only because the exponentiations in the code are unrolled
47/// for efficiency reasons.
48#[cfg(test)]
49const ALPHA: u64 = 7;
50#[cfg(test)]
51const INV_ALPHA: u64 = 10540996611094048183;
52
53// HASHER IMPLEMENTATION
54// ================================================================================================
55
56/// Implementation of [Hasher] trait for Rescue Prime Optimized (Rpo256) hash function with 256-bit output.
57///
58/// The hash function is implemented according to the Rescue Prime Optimized
59/// [specifications](https://github.com/ASDiscreteMathematics/rpo)
60///
61/// The parameters used to instantiate the function are:
62/// * Field: 64-bit prime field with modulus 2^64 - 2^32 + 1.
63/// * State width: 12 field elements.
64/// * Capacity size: 4 field elements.
65/// * Number of founds: 7.
66/// * S-Box degree: 7.
67///
68/// The above parameters target 128-bit security level. The digest consists of four field elements
69/// and it can be serialized into 32 bytes (256 bits).
70///
71/// ## Hash output consistency
72/// Functions [hash_elements()](Rpo256::hash_elements), [merge()](Rpo256::merge), and
73/// [merge_with_int()](Rpo256::merge_with_int) are internally consistent. That is, computing
74/// a hash for the same set of elements using these functions will always produce the same
75/// result. For example, merging two digests using [merge()](Rpo256::merge) will produce the
76/// same result as hashing 8 elements which make up these digests using
77/// [hash_elements()](Rpo256::hash_elements) function.
78///
79/// However, [hash()](Rpo256::hash) function is not consistent with functions mentioned above.
80/// For example, if we take two field elements, serialize them to bytes and hash them using
81/// [hash()](Rpo256::hash), the result will differ from the result obtained by hashing these
82/// elements directly using [hash_elements()](Rpo256::hash_elements) function. The reason for
83/// this difference is that [hash()](Rpo256::hash) function needs to be able to handle
84/// arbitrary binary strings, which may or may not encode valid field elements - and thus,
85/// deserialization procedure used by this function is different from the procedure used to
86/// deserialize valid field elements.
87///
88/// Thus, if the underlying data consists of valid field elements, it might make more sense
89/// to deserialize them into field elements and then hash them using
90/// [hash_elements()](Rpo256::hash_elements) function rather then hashing the serialized bytes
91/// using [hash()](Rpo256::hash) function.
92pub struct Rpo256();
93
94impl HashFn for Rpo256 {
95 type Digest = RpoDigest256;
96
97 fn hash(bytes: &[u8]) -> Self::Digest {
98 // compute the number of elements required to represent the string; we will be processing
99 // the string in BINARY_CHUNK_SIZE-byte chunks, thus the number of elements will be equal
100 // to the number of such chunks (including a potential partial chunk at the end).
101 let num_elements = if bytes.len() % BINARY_CHUNK_SIZE == 0 {
102 bytes.len() / BINARY_CHUNK_SIZE
103 } else {
104 bytes.len() / BINARY_CHUNK_SIZE + 1
105 };
106
107 // initialize state to all zeros, except for the first element of the capacity part, which
108 // is set to the number of elements to be hashed. this is done so that adding zero elements
109 // at the end of the list always results in a different hash.
110 let mut state = [ZERO; STATE_WIDTH];
111 state[CAPACITY_RANGE.start] = Felt::new(num_elements as u64);
112
113 // break the string into BINARY_CHUNK_SIZE-byte chunks, convert each chunk into a field
114 // element, and absorb the element into the rate portion of the state. we use
115 // BINARY_CHUNK_SIZE-byte chunks because every BINARY_CHUNK_SIZE-byte chunk is guaranteed
116 // to map to some field element.
117 let mut i = 0;
118 let mut buf = [0_u8; 8];
119 for chunk in bytes.chunks(BINARY_CHUNK_SIZE) {
120 if i < num_elements - 1 {
121 buf[..BINARY_CHUNK_SIZE].copy_from_slice(chunk);
122 } else {
123 // if we are dealing with the last chunk, it may be smaller than BINARY_CHUNK_SIZE
124 // bytes long, so we need to handle it slightly differently. We also append a byte
125 // with value 1 to the end of the string; this pads the string in such a way that
126 // adding trailing zeros results in different hash
127 let chunk_len = chunk.len();
128 buf = [0_u8; 8];
129 buf[..chunk_len].copy_from_slice(chunk);
130 buf[chunk_len] = 1;
131 }
132
133 // convert the bytes into a field element and absorb it into the rate portion of the
134 // state; if the rate is filled up, apply the Rescue permutation and start absorbing
135 // again from zero index.
136 state[RATE_RANGE.start + i] = Felt::new(u64::from_le_bytes(buf));
137 i += 1;
138 if i % RATE_WIDTH == 0 {
139 Self::apply_permutation(&mut state);
140 i = 0;
141 }
142 }
143
144 // if we absorbed some elements but didn't apply a permutation to them (would happen when
145 // the number of elements is not a multiple of RATE_WIDTH), apply the RPO permutation.
146 // we don't need to apply any extra padding because we injected total number of elements
147 // in the input list into the capacity portion of the state during initialization.
148 if i > 0 {
149 Self::apply_permutation(&mut state);
150 }
151
152 // return the first 4 elements of the state as hash result
153 RpoDigest256::new(state[DIGEST_RANGE].try_into().unwrap())
154 }
155
156 fn merge(values: &[Self::Digest; 2]) -> Self::Digest {
157 // initialize the state by copying the digest elements into the rate portion of the state
158 // (8 total elements), and set the capacity elements to 0.
159 let mut state = [ZERO; STATE_WIDTH];
160 let it = Self::Digest::digests_as_elements(values.iter());
161 for (i, v) in it.enumerate() {
162 state[RATE_RANGE.start + i] = *v;
163 }
164
165 // apply the RPO permutation and return the first four elements of the state
166 Self::apply_permutation(&mut state);
167 RpoDigest256::new(state[DIGEST_RANGE].try_into().unwrap())
168 }
169
170 fn merge_with_int(seed: Self::Digest, value: u64) -> Self::Digest {
171 // initialize the state as follows:
172 // - seed is copied into the first 4 elements of the rate portion of the state.
173 // - if the value fits into a single field element, copy it into the fifth rate element
174 // and set the sixth rate element to 1.
175 // - if the value doesn't fit into a single field element, split it into two field
176 // elements, copy them into rate elements 5 and 6, and set the seventh rate element
177 // to 1.
178 // - set the first capacity element to 1
179 let mut state = [ZERO; STATE_WIDTH];
180 state[INPUT1_RANGE].copy_from_slice(seed.as_elements());
181 state[INPUT2_RANGE.start] = Felt::new(value);
182 if value < Felt::MODULUS {
183 state[INPUT2_RANGE.start + 1] = ONE;
184 } else {
185 state[INPUT2_RANGE.start + 1] = Felt::new(value / Felt::MODULUS);
186 state[INPUT2_RANGE.start + 2] = ONE;
187 }
188
189 // common padding for both cases
190 state[CAPACITY_RANGE.start] = ONE;
191
192 // apply the RPO permutation and return the first four elements of the state
193 Self::apply_permutation(&mut state);
194 RpoDigest256::new(state[DIGEST_RANGE].try_into().unwrap())
195 }
196}
197
198impl ElementHasher for Rpo256 {
199 type BaseField = Felt;
200
201 fn hash_elements<E: FieldElement<BaseField = Self::BaseField>>(elements: &[E]) -> Self::Digest {
202 // convert the elements into a list of base field elements
203 let elements = E::as_base_elements(elements);
204
205 // initialize state to all zeros, except for the first element of the capacity part, which
206 // is set to 1 if the number of elements is not a multiple of RATE_WIDTH.
207 let mut state = [ZERO; STATE_WIDTH];
208 if elements.len() % RATE_WIDTH != 0 {
209 state[CAPACITY_RANGE.start] = ONE;
210 }
211
212 // absorb elements into the state one by one until the rate portion of the state is filled
213 // up; then apply the Rescue permutation and start absorbing again; repeat until all
214 // elements have been absorbed
215 let mut i = 0;
216 for &element in elements.iter() {
217 state[RATE_RANGE.start + i] = element;
218 i += 1;
219 if i % RATE_WIDTH == 0 {
220 Self::apply_permutation(&mut state);
221 i = 0;
222 }
223 }
224
225 // if we absorbed some elements but didn't apply a permutation to them (would happen when
226 // the number of elements is not a multiple of RATE_WIDTH), apply the RPO permutation after
227 // padding by appending a 1 followed by as many 0 as necessary to make the input length a
228 // multiple of the RATE_WIDTH.
229 if i > 0 {
230 state[RATE_RANGE.start + i] = ONE;
231 i += 1;
232 while i != RATE_WIDTH {
233 state[RATE_RANGE.start + i] = ZERO;
234 i += 1;
235 }
236 Self::apply_permutation(&mut state);
237 }
238
239 // return the first 4 elements of the state as hash result
240 RpoDigest256::new(state[DIGEST_RANGE].try_into().unwrap())
241 }
242}
243
244// HASH FUNCTION IMPLEMENTATION
245// ================================================================================================
246
247impl Rpo256 {
248 // RESCUE PERMUTATION
249 // --------------------------------------------------------------------------------------------
250
251 /// Applies RPO permutation to the provided state.
252 pub fn apply_permutation(state: &mut [Felt; STATE_WIDTH]) {
253 for i in 0..NUM_ROUNDS {
254 Self::apply_round(state, i);
255 }
256 }
257
258 /// RPO round function.
259 #[inline(always)]
260 pub fn apply_round(state: &mut [Felt; STATE_WIDTH], round: usize) {
261 // apply first half of RPO round
262 Self::apply_mds(state);
263 Self::add_constants(state, &ARK1[round]);
264 Self::apply_sbox(state);
265
266 // apply second half of RPO round
267 Self::apply_mds(state);
268 Self::add_constants(state, &ARK2[round]);
269 Self::apply_inv_sbox(state);
270 }
271
272 // HELPER FUNCTIONS
273 // --------------------------------------------------------------------------------------------
274
275 #[inline(always)]
276 fn apply_mds(state: &mut [Felt; STATE_WIDTH]) {
277 let mut result = [ZERO; STATE_WIDTH];
278
279 // Using the linearity of the operations we can split the state into a low||high decomposition
280 // and operate on each with no overflow and then combine/reduce the result to a field element.
281 // The no overflow is guaranteed by the fact that the MDS matrix is a small powers of two in
282 // frequency domain.
283 let mut state_l = [0u64; STATE_WIDTH];
284 let mut state_h = [0u64; STATE_WIDTH];
285
286 for r in 0..STATE_WIDTH {
287 let s = state[r].inner();
288 state_h[r] = s >> 32;
289 state_l[r] = (s as u32) as u64;
290 }
291
292 let state_h = mds_multiply_freq(state_h);
293 let state_l = mds_multiply_freq(state_l);
294
295 for r in 0..STATE_WIDTH {
296 let s = state_l[r] as u128 + ((state_h[r] as u128) << 32);
297 let s_hi = (s >> 64) as u64;
298 let s_lo = s as u64;
299 let z = (s_hi << 32) - s_hi;
300 let (res, over) = s_lo.overflowing_add(z);
301
302 result[r] = Felt::from_mont(res.wrapping_add(0u32.wrapping_sub(over as u32) as u64));
303 }
304 *state = result;
305 }
306
307 #[inline(always)]
308 fn add_constants(state: &mut [Felt; STATE_WIDTH], ark: &[Felt; STATE_WIDTH]) {
309 state.iter_mut().zip(ark).for_each(|(s, &k)| *s += k);
310 }
311
312 #[inline(always)]
313 fn apply_sbox(state: &mut [Felt; STATE_WIDTH]) {
314 state[0] = state[0].exp7();
315 state[1] = state[1].exp7();
316 state[2] = state[2].exp7();
317 state[3] = state[3].exp7();
318 state[4] = state[4].exp7();
319 state[5] = state[5].exp7();
320 state[6] = state[6].exp7();
321 state[7] = state[7].exp7();
322 state[8] = state[8].exp7();
323 state[9] = state[9].exp7();
324 state[10] = state[10].exp7();
325 state[11] = state[11].exp7();
326 }
327
328 #[inline(always)]
329 fn apply_inv_sbox(state: &mut [Felt; STATE_WIDTH]) {
330 // compute base^10540996611094048183 using 72 multiplications per array element
331 // 10540996611094048183 = b1001001001001001001001001001000110110110110110110110110110110111
332
333 // compute base^10
334 let mut t1 = *state;
335 t1.iter_mut().for_each(|t| *t = t.square());
336
337 // compute base^100
338 let mut t2 = t1;
339 t2.iter_mut().for_each(|t| *t = t.square());
340
341 // compute base^100100
342 let t3 = Self::exp_acc::<Felt, STATE_WIDTH, 3>(t2, t2);
343
344 // compute base^100100100100
345 let t4 = Self::exp_acc::<Felt, STATE_WIDTH, 6>(t3, t3);
346
347 // compute base^100100100100100100100100
348 let t5 = Self::exp_acc::<Felt, STATE_WIDTH, 12>(t4, t4);
349
350 // compute base^100100100100100100100100100100
351 let t6 = Self::exp_acc::<Felt, STATE_WIDTH, 6>(t5, t3);
352
353 // compute base^1001001001001001001001001001000100100100100100100100100100100
354 let t7 = Self::exp_acc::<Felt, STATE_WIDTH, 31>(t6, t6);
355
356 // compute base^1001001001001001001001001001000110110110110110110110110110110111
357 for (i, s) in state.iter_mut().enumerate() {
358 let a = (t7[i].square() * t6[i]).square().square();
359 let b = t1[i] * t2[i] * *s;
360 *s = a * b;
361 }
362 }
363
364 #[inline(always)]
365 fn exp_acc<B: StarkField, const N: usize, const M: usize>(
366 base: [B; N],
367 tail: [B; N],
368 ) -> [B; N] {
369 let mut result = base;
370 for _ in 0..M {
371 result.iter_mut().for_each(|r| *r = r.square());
372 }
373 result.iter_mut().zip(tail).for_each(|(r, t)| *r *= t);
374 result
375 }
376}
377
378// MDS
379// ================================================================================================
380/// RPO MDS matrix
381pub const MDS: [[Felt; STATE_WIDTH]; STATE_WIDTH] = [
382 [
383 Felt::new(7),
384 Felt::new(23),
385 Felt::new(8),
386 Felt::new(26),
387 Felt::new(13),
388 Felt::new(10),
389 Felt::new(9),
390 Felt::new(7),
391 Felt::new(6),
392 Felt::new(22),
393 Felt::new(21),
394 Felt::new(8),
395 ],
396 [
397 Felt::new(8),
398 Felt::new(7),
399 Felt::new(23),
400 Felt::new(8),
401 Felt::new(26),
402 Felt::new(13),
403 Felt::new(10),
404 Felt::new(9),
405 Felt::new(7),
406 Felt::new(6),
407 Felt::new(22),
408 Felt::new(21),
409 ],
410 [
411 Felt::new(21),
412 Felt::new(8),
413 Felt::new(7),
414 Felt::new(23),
415 Felt::new(8),
416 Felt::new(26),
417 Felt::new(13),
418 Felt::new(10),
419 Felt::new(9),
420 Felt::new(7),
421 Felt::new(6),
422 Felt::new(22),
423 ],
424 [
425 Felt::new(22),
426 Felt::new(21),
427 Felt::new(8),
428 Felt::new(7),
429 Felt::new(23),
430 Felt::new(8),
431 Felt::new(26),
432 Felt::new(13),
433 Felt::new(10),
434 Felt::new(9),
435 Felt::new(7),
436 Felt::new(6),
437 ],
438 [
439 Felt::new(6),
440 Felt::new(22),
441 Felt::new(21),
442 Felt::new(8),
443 Felt::new(7),
444 Felt::new(23),
445 Felt::new(8),
446 Felt::new(26),
447 Felt::new(13),
448 Felt::new(10),
449 Felt::new(9),
450 Felt::new(7),
451 ],
452 [
453 Felt::new(7),
454 Felt::new(6),
455 Felt::new(22),
456 Felt::new(21),
457 Felt::new(8),
458 Felt::new(7),
459 Felt::new(23),
460 Felt::new(8),
461 Felt::new(26),
462 Felt::new(13),
463 Felt::new(10),
464 Felt::new(9),
465 ],
466 [
467 Felt::new(9),
468 Felt::new(7),
469 Felt::new(6),
470 Felt::new(22),
471 Felt::new(21),
472 Felt::new(8),
473 Felt::new(7),
474 Felt::new(23),
475 Felt::new(8),
476 Felt::new(26),
477 Felt::new(13),
478 Felt::new(10),
479 ],
480 [
481 Felt::new(10),
482 Felt::new(9),
483 Felt::new(7),
484 Felt::new(6),
485 Felt::new(22),
486 Felt::new(21),
487 Felt::new(8),
488 Felt::new(7),
489 Felt::new(23),
490 Felt::new(8),
491 Felt::new(26),
492 Felt::new(13),
493 ],
494 [
495 Felt::new(13),
496 Felt::new(10),
497 Felt::new(9),
498 Felt::new(7),
499 Felt::new(6),
500 Felt::new(22),
501 Felt::new(21),
502 Felt::new(8),
503 Felt::new(7),
504 Felt::new(23),
505 Felt::new(8),
506 Felt::new(26),
507 ],
508 [
509 Felt::new(26),
510 Felt::new(13),
511 Felt::new(10),
512 Felt::new(9),
513 Felt::new(7),
514 Felt::new(6),
515 Felt::new(22),
516 Felt::new(21),
517 Felt::new(8),
518 Felt::new(7),
519 Felt::new(23),
520 Felt::new(8),
521 ],
522 [
523 Felt::new(8),
524 Felt::new(26),
525 Felt::new(13),
526 Felt::new(10),
527 Felt::new(9),
528 Felt::new(7),
529 Felt::new(6),
530 Felt::new(22),
531 Felt::new(21),
532 Felt::new(8),
533 Felt::new(7),
534 Felt::new(23),
535 ],
536 [
537 Felt::new(23),
538 Felt::new(8),
539 Felt::new(26),
540 Felt::new(13),
541 Felt::new(10),
542 Felt::new(9),
543 Felt::new(7),
544 Felt::new(6),
545 Felt::new(22),
546 Felt::new(21),
547 Felt::new(8),
548 Felt::new(7),
549 ],
550];
551
552/// RPO Inverse MDS matrix
553pub const INV_MDS: [[Felt; STATE_WIDTH]; STATE_WIDTH] = [
554 [
555 Felt::new(14868391535953158196),
556 Felt::new(13278298489594233127),
557 Felt::new(389999932707070822),
558 Felt::new(9782021734907796003),
559 Felt::new(4829905704463175582),
560 Felt::new(7567822018949214430),
561 Felt::new(14205019324568680367),
562 Felt::new(15489674211196160593),
563 Felt::new(17636013826542227504),
564 Felt::new(16254215311946436093),
565 Felt::new(3641486184877122796),
566 Felt::new(11069068059762973582),
567 ],
568 [
569 Felt::new(11069068059762973582),
570 Felt::new(14868391535953158196),
571 Felt::new(13278298489594233127),
572 Felt::new(389999932707070822),
573 Felt::new(9782021734907796003),
574 Felt::new(4829905704463175582),
575 Felt::new(7567822018949214430),
576 Felt::new(14205019324568680367),
577 Felt::new(15489674211196160593),
578 Felt::new(17636013826542227504),
579 Felt::new(16254215311946436093),
580 Felt::new(3641486184877122796),
581 ],
582 [
583 Felt::new(3641486184877122796),
584 Felt::new(11069068059762973582),
585 Felt::new(14868391535953158196),
586 Felt::new(13278298489594233127),
587 Felt::new(389999932707070822),
588 Felt::new(9782021734907796003),
589 Felt::new(4829905704463175582),
590 Felt::new(7567822018949214430),
591 Felt::new(14205019324568680367),
592 Felt::new(15489674211196160593),
593 Felt::new(17636013826542227504),
594 Felt::new(16254215311946436093),
595 ],
596 [
597 Felt::new(16254215311946436093),
598 Felt::new(3641486184877122796),
599 Felt::new(11069068059762973582),
600 Felt::new(14868391535953158196),
601 Felt::new(13278298489594233127),
602 Felt::new(389999932707070822),
603 Felt::new(9782021734907796003),
604 Felt::new(4829905704463175582),
605 Felt::new(7567822018949214430),
606 Felt::new(14205019324568680367),
607 Felt::new(15489674211196160593),
608 Felt::new(17636013826542227504),
609 ],
610 [
611 Felt::new(17636013826542227504),
612 Felt::new(16254215311946436093),
613 Felt::new(3641486184877122796),
614 Felt::new(11069068059762973582),
615 Felt::new(14868391535953158196),
616 Felt::new(13278298489594233127),
617 Felt::new(389999932707070822),
618 Felt::new(9782021734907796003),
619 Felt::new(4829905704463175582),
620 Felt::new(7567822018949214430),
621 Felt::new(14205019324568680367),
622 Felt::new(15489674211196160593),
623 ],
624 [
625 Felt::new(15489674211196160593),
626 Felt::new(17636013826542227504),
627 Felt::new(16254215311946436093),
628 Felt::new(3641486184877122796),
629 Felt::new(11069068059762973582),
630 Felt::new(14868391535953158196),
631 Felt::new(13278298489594233127),
632 Felt::new(389999932707070822),
633 Felt::new(9782021734907796003),
634 Felt::new(4829905704463175582),
635 Felt::new(7567822018949214430),
636 Felt::new(14205019324568680367),
637 ],
638 [
639 Felt::new(14205019324568680367),
640 Felt::new(15489674211196160593),
641 Felt::new(17636013826542227504),
642 Felt::new(16254215311946436093),
643 Felt::new(3641486184877122796),
644 Felt::new(11069068059762973582),
645 Felt::new(14868391535953158196),
646 Felt::new(13278298489594233127),
647 Felt::new(389999932707070822),
648 Felt::new(9782021734907796003),
649 Felt::new(4829905704463175582),
650 Felt::new(7567822018949214430),
651 ],
652 [
653 Felt::new(7567822018949214430),
654 Felt::new(14205019324568680367),
655 Felt::new(15489674211196160593),
656 Felt::new(17636013826542227504),
657 Felt::new(16254215311946436093),
658 Felt::new(3641486184877122796),
659 Felt::new(11069068059762973582),
660 Felt::new(14868391535953158196),
661 Felt::new(13278298489594233127),
662 Felt::new(389999932707070822),
663 Felt::new(9782021734907796003),
664 Felt::new(4829905704463175582),
665 ],
666 [
667 Felt::new(4829905704463175582),
668 Felt::new(7567822018949214430),
669 Felt::new(14205019324568680367),
670 Felt::new(15489674211196160593),
671 Felt::new(17636013826542227504),
672 Felt::new(16254215311946436093),
673 Felt::new(3641486184877122796),
674 Felt::new(11069068059762973582),
675 Felt::new(14868391535953158196),
676 Felt::new(13278298489594233127),
677 Felt::new(389999932707070822),
678 Felt::new(9782021734907796003),
679 ],
680 [
681 Felt::new(9782021734907796003),
682 Felt::new(4829905704463175582),
683 Felt::new(7567822018949214430),
684 Felt::new(14205019324568680367),
685 Felt::new(15489674211196160593),
686 Felt::new(17636013826542227504),
687 Felt::new(16254215311946436093),
688 Felt::new(3641486184877122796),
689 Felt::new(11069068059762973582),
690 Felt::new(14868391535953158196),
691 Felt::new(13278298489594233127),
692 Felt::new(389999932707070822),
693 ],
694 [
695 Felt::new(389999932707070822),
696 Felt::new(9782021734907796003),
697 Felt::new(4829905704463175582),
698 Felt::new(7567822018949214430),
699 Felt::new(14205019324568680367),
700 Felt::new(15489674211196160593),
701 Felt::new(17636013826542227504),
702 Felt::new(16254215311946436093),
703 Felt::new(3641486184877122796),
704 Felt::new(11069068059762973582),
705 Felt::new(14868391535953158196),
706 Felt::new(13278298489594233127),
707 ],
708 [
709 Felt::new(13278298489594233127),
710 Felt::new(389999932707070822),
711 Felt::new(9782021734907796003),
712 Felt::new(4829905704463175582),
713 Felt::new(7567822018949214430),
714 Felt::new(14205019324568680367),
715 Felt::new(15489674211196160593),
716 Felt::new(17636013826542227504),
717 Felt::new(16254215311946436093),
718 Felt::new(3641486184877122796),
719 Felt::new(11069068059762973582),
720 Felt::new(14868391535953158196),
721 ],
722];
723
724// ROUND CONSTANTS
725// ================================================================================================
726
727/// Rescue round constants;
728/// computed as in [specifications](https://github.com/ASDiscreteMathematics/rpo)
729///
730/// The constants are broken up into two arrays ARK1 and ARK2; ARK1 contains the constants for the
731/// first half of RPO round, and ARK2 contains constants for the second half of RPO round.
732const ARK1: [[Felt; STATE_WIDTH]; NUM_ROUNDS] = [
733 [
734 Felt::new(5789762306288267392),
735 Felt::new(6522564764413701783),
736 Felt::new(17809893479458208203),
737 Felt::new(107145243989736508),
738 Felt::new(6388978042437517382),
739 Felt::new(15844067734406016715),
740 Felt::new(9975000513555218239),
741 Felt::new(3344984123768313364),
742 Felt::new(9959189626657347191),
743 Felt::new(12960773468763563665),
744 Felt::new(9602914297752488475),
745 Felt::new(16657542370200465908),
746 ],
747 [
748 Felt::new(12987190162843096997),
749 Felt::new(653957632802705281),
750 Felt::new(4441654670647621225),
751 Felt::new(4038207883745915761),
752 Felt::new(5613464648874830118),
753 Felt::new(13222989726778338773),
754 Felt::new(3037761201230264149),
755 Felt::new(16683759727265180203),
756 Felt::new(8337364536491240715),
757 Felt::new(3227397518293416448),
758 Felt::new(8110510111539674682),
759 Felt::new(2872078294163232137),
760 ],
761 [
762 Felt::new(18072785500942327487),
763 Felt::new(6200974112677013481),
764 Felt::new(17682092219085884187),
765 Felt::new(10599526828986756440),
766 Felt::new(975003873302957338),
767 Felt::new(8264241093196931281),
768 Felt::new(10065763900435475170),
769 Felt::new(2181131744534710197),
770 Felt::new(6317303992309418647),
771 Felt::new(1401440938888741532),
772 Felt::new(8884468225181997494),
773 Felt::new(13066900325715521532),
774 ],
775 [
776 Felt::new(5674685213610121970),
777 Felt::new(5759084860419474071),
778 Felt::new(13943282657648897737),
779 Felt::new(1352748651966375394),
780 Felt::new(17110913224029905221),
781 Felt::new(1003883795902368422),
782 Felt::new(4141870621881018291),
783 Felt::new(8121410972417424656),
784 Felt::new(14300518605864919529),
785 Felt::new(13712227150607670181),
786 Felt::new(17021852944633065291),
787 Felt::new(6252096473787587650),
788 ],
789 [
790 Felt::new(4887609836208846458),
791 Felt::new(3027115137917284492),
792 Felt::new(9595098600469470675),
793 Felt::new(10528569829048484079),
794 Felt::new(7864689113198939815),
795 Felt::new(17533723827845969040),
796 Felt::new(5781638039037710951),
797 Felt::new(17024078752430719006),
798 Felt::new(109659393484013511),
799 Felt::new(7158933660534805869),
800 Felt::new(2955076958026921730),
801 Felt::new(7433723648458773977),
802 ],
803 [
804 Felt::new(16308865189192447297),
805 Felt::new(11977192855656444890),
806 Felt::new(12532242556065780287),
807 Felt::new(14594890931430968898),
808 Felt::new(7291784239689209784),
809 Felt::new(5514718540551361949),
810 Felt::new(10025733853830934803),
811 Felt::new(7293794580341021693),
812 Felt::new(6728552937464861756),
813 Felt::new(6332385040983343262),
814 Felt::new(13277683694236792804),
815 Felt::new(2600778905124452676),
816 ],
817 [
818 Felt::new(7123075680859040534),
819 Felt::new(1034205548717903090),
820 Felt::new(7717824418247931797),
821 Felt::new(3019070937878604058),
822 Felt::new(11403792746066867460),
823 Felt::new(10280580802233112374),
824 Felt::new(337153209462421218),
825 Felt::new(13333398568519923717),
826 Felt::new(3596153696935337464),
827 Felt::new(8104208463525993784),
828 Felt::new(14345062289456085693),
829 Felt::new(17036731477169661256),
830 ],
831];
832
833const ARK2: [[Felt; STATE_WIDTH]; NUM_ROUNDS] = [
834 [
835 Felt::new(6077062762357204287),
836 Felt::new(15277620170502011191),
837 Felt::new(5358738125714196705),
838 Felt::new(14233283787297595718),
839 Felt::new(13792579614346651365),
840 Felt::new(11614812331536767105),
841 Felt::new(14871063686742261166),
842 Felt::new(10148237148793043499),
843 Felt::new(4457428952329675767),
844 Felt::new(15590786458219172475),
845 Felt::new(10063319113072092615),
846 Felt::new(14200078843431360086),
847 ],
848 [
849 Felt::new(6202948458916099932),
850 Felt::new(17690140365333231091),
851 Felt::new(3595001575307484651),
852 Felt::new(373995945117666487),
853 Felt::new(1235734395091296013),
854 Felt::new(14172757457833931602),
855 Felt::new(707573103686350224),
856 Felt::new(15453217512188187135),
857 Felt::new(219777875004506018),
858 Felt::new(17876696346199469008),
859 Felt::new(17731621626449383378),
860 Felt::new(2897136237748376248),
861 ],
862 [
863 Felt::new(8023374565629191455),
864 Felt::new(15013690343205953430),
865 Felt::new(4485500052507912973),
866 Felt::new(12489737547229155153),
867 Felt::new(9500452585969030576),
868 Felt::new(2054001340201038870),
869 Felt::new(12420704059284934186),
870 Felt::new(355990932618543755),
871 Felt::new(9071225051243523860),
872 Felt::new(12766199826003448536),
873 Felt::new(9045979173463556963),
874 Felt::new(12934431667190679898),
875 ],
876 [
877 Felt::new(18389244934624494276),
878 Felt::new(16731736864863925227),
879 Felt::new(4440209734760478192),
880 Felt::new(17208448209698888938),
881 Felt::new(8739495587021565984),
882 Felt::new(17000774922218161967),
883 Felt::new(13533282547195532087),
884 Felt::new(525402848358706231),
885 Felt::new(16987541523062161972),
886 Felt::new(5466806524462797102),
887 Felt::new(14512769585918244983),
888 Felt::new(10973956031244051118),
889 ],
890 [
891 Felt::new(6982293561042362913),
892 Felt::new(14065426295947720331),
893 Felt::new(16451845770444974180),
894 Felt::new(7139138592091306727),
895 Felt::new(9012006439959783127),
896 Felt::new(14619614108529063361),
897 Felt::new(1394813199588124371),
898 Felt::new(4635111139507788575),
899 Felt::new(16217473952264203365),
900 Felt::new(10782018226466330683),
901 Felt::new(6844229992533662050),
902 Felt::new(7446486531695178711),
903 ],
904 [
905 Felt::new(3736792340494631448),
906 Felt::new(577852220195055341),
907 Felt::new(6689998335515779805),
908 Felt::new(13886063479078013492),
909 Felt::new(14358505101923202168),
910 Felt::new(7744142531772274164),
911 Felt::new(16135070735728404443),
912 Felt::new(12290902521256031137),
913 Felt::new(12059913662657709804),
914 Felt::new(16456018495793751911),
915 Felt::new(4571485474751953524),
916 Felt::new(17200392109565783176),
917 ],
918 [
919 Felt::new(17130398059294018733),
920 Felt::new(519782857322261988),
921 Felt::new(9625384390925085478),
922 Felt::new(1664893052631119222),
923 Felt::new(7629576092524553570),
924 Felt::new(3485239601103661425),
925 Felt::new(9755891797164033838),
926 Felt::new(15218148195153269027),
927 Felt::new(16460604813734957368),
928 Felt::new(9643968136937729763),
929 Felt::new(3611348709641382851),
930 Felt::new(18256379591337759196),
931 ],
932];