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