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