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