jf_rescue/
lib.rs

1// Copyright (c) 2022 Espresso Systems (espressosys.com)
2// This file is part of the Jellyfish library.
3
4// You should have received a copy of the MIT License
5// along with the Jellyfish library. If not, see <https://mit-license.org/>.
6
7//! This module implements Rescue hash function over the following fields
8//! - bls12_377 base field
9//! - ed_on_bls12_377 base field
10//! - ed_on_bls12_381 base field
11//! - ed_on_bn254 base field
12//!
13//! It also has place holders for
14//! - bls12_381 base field
15//! - bn254 base field
16//! - bw6_761 base field
17//!
18//! Those three place holders should never be used.
19
20#![cfg_attr(not(feature = "std"), no_std)]
21// Temporarily allow warning for nightly compilation with [`displaydoc`].
22#![allow(warnings)]
23#![deny(missing_docs)]
24#[cfg(test)]
25extern crate std;
26
27#[cfg(any(not(feature = "std"), target_has_atomic = "ptr"))]
28#[doc(hidden)]
29extern crate alloc;
30
31pub mod commitment;
32pub mod crhf;
33#[cfg(feature = "gadgets")]
34pub mod gadgets;
35pub mod permutation;
36pub mod prf;
37mod rescue_constants;
38
39use ark_ff::{PrimeField, Zero};
40use ark_std::{string::String, vec, vec::Vec};
41use displaydoc::Display;
42use spongefish::duplex_sponge::Unit;
43use zeroize::Zeroize;
44
45// re-export at the crate top level
46pub use permutation::RescueSponge;
47
48/// Rescue error type
49#[derive(Debug, Display, Eq, PartialEq)]
50pub enum RescueError {
51    /// Bad parameter in function call, {0}
52    ParameterError(String),
53}
54
55impl ark_std::error::Error for RescueError {}
56
57/// The state size of rescue hash.
58pub const STATE_SIZE: usize = 4;
59/// The rate of the sponge used in RescueCRHF.
60pub const CRHF_RATE: usize = 3;
61
62/// The # of rounds of rescue hash.
63// In the paper, to derive ROUND:
64//  sage: m = 4
65//  sage: for N in range (13):
66//  ....:     t = m*N*3+3+2
67//  ....:     b = m*N + 3
68//  ....:     sec = factorial(t)/factorial(b)/factorial(t-b)
69//  ....:     print (N, RR(log(sec^2,2)))
70//
71// for alpha = 5, (i.e., BLS12-381 and BN254)
72//      10 224.672644456021
73//      11 246.589942930803
74//      12 268.516687541633
75// set ROUND = 12, we have 134 bits security
76//
77// for alpha = 11, (i.e. BLS12-377) we have l1 =
78//      7 227.364142668101
79//      8 258.421493926570
80//      9 289.491120346551
81//      10 320.571247089962
82//      11 351.660410749737
83//      12 382.757409540148
84// The smallest possible round number will be max(10, l1), which
85// means round = 10 gives 160 bits security
86//
87// There is also the script from
88//  https://github.com/EspressoSystems/Marvellous
89//
90// For unknown reasons, for all alpha >=5, the ROUND number is taken as if alpha
91// = 5. This parameter choice does not seem to be optimal
92//
93//  if (self.alpha == 3):
94//      self.Nb = max(10, 2*ceil((1.0 * security_level + 2) / (4*m)))
95//  elif (self.alpha == 5):
96//      self.Nb = max(10, 2*ceil((1.0 * security_level + 3) / (5.5*m)))
97//  else :
98//      self.Nb = max(10, 2*ceil((1.0 * security_level + 3) / (5.5*m)))
99//  # where m = 4
100//
101// For conservative purpose, we are setting ROUNDS = 12 for now.
102// We may consider to use ROUNDS = 10 for BLS12-377 (alpha = 11) in futures.
103pub const ROUNDS: usize = 12;
104
105/// This trait defines constants that are used for rescue hash functions.
106pub trait RescueParameter: PrimeField + Unit {
107    /// parameter A, a.k.a., alpha
108    const A: u64;
109    /// parameter A^-1
110    const A_INV: &'static [u64];
111    /// MDS matrix
112    const MDS_LE: [[&'static [u8]; STATE_SIZE]; STATE_SIZE];
113    /// Initial vector.
114    const INIT_VEC_LE: [&'static [u8]; STATE_SIZE];
115    /// Injected keys for each round.
116    const KEY_INJECTION_LE: [[&'static [u8]; 4]; 2 * ROUNDS];
117    /// Permutation keys.
118    const PERMUTATION_ROUND_KEYS: [[&'static [u8]; 4]; 25];
119}
120
121#[derive(Clone, Debug, Eq, PartialEq, Copy, Default, Zeroize)]
122/// Data type for rescue prp inputs, keys and internal data
123pub struct RescueVector<F> {
124    pub(crate) vec: [F; STATE_SIZE],
125}
126
127// Public functions
128impl<F: PrimeField> RescueVector<F> {
129    /// zero vector
130    pub fn zero() -> RescueVector<F> {
131        RescueVector {
132            vec: [F::zero(); STATE_SIZE],
133        }
134    }
135
136    /// Return vector of the field elements
137    /// WARNING: may expose the internal state.
138    pub fn elems(&self) -> Vec<F> {
139        self.vec.to_vec()
140    }
141
142    /// Perform a linear transform of the vector.
143    /// Function needs to be public for circuits generation..
144    pub fn linear(&mut self, matrix: &RescueMatrix<F>, vector: &RescueVector<F>) {
145        let mut aux = matrix.mul_vec(self);
146        aux.add_assign(vector);
147        *self = aux
148    }
149}
150
151// Private functions
152impl<F: PrimeField> RescueVector<F> {
153    fn from_elems_le_bytes(e0: &[u8], e1: &[u8], e2: &[u8], e3: &[u8]) -> RescueVector<F> {
154        RescueVector {
155            vec: [
156                F::from_le_bytes_mod_order(e0),
157                F::from_le_bytes_mod_order(e1),
158                F::from_le_bytes_mod_order(e2),
159                F::from_le_bytes_mod_order(e3),
160            ],
161        }
162    }
163
164    fn pow(&mut self, exp: &[u64]) {
165        self.vec.iter_mut().for_each(|elem| {
166            *elem = elem.pow(exp);
167        });
168    }
169
170    fn add_assign(&mut self, vector: &RescueVector<F>) {
171        for (a, b) in self.vec.iter_mut().zip(vector.vec.iter()) {
172            a.add_assign(b);
173        }
174    }
175
176    fn add(&self, vector: &RescueVector<F>) -> RescueVector<F> {
177        let mut aux = *self;
178        aux.add_assign(vector);
179        aux
180    }
181
182    fn add_assign_elems(&mut self, elems: &[F]) {
183        self.vec
184            .iter_mut()
185            .zip(elems.iter())
186            .for_each(|(a, b)| a.add_assign(b));
187    }
188
189    fn dot_product(&self, vector: &RescueVector<F>) -> F {
190        let mut r = F::zero();
191        for (a, b) in self.vec.iter().zip(vector.vec.iter()) {
192            r.add_assign(&a.mul(b));
193        }
194        r
195    }
196}
197
198impl<F: RescueParameter> RescueVector<F> {
199    /// Helper function to compute f(M,x,c) = Mx^a + c.
200    /// Function needs to be public for circuits generation..
201    pub fn non_linear(&mut self, matrix: &RescueMatrix<F>, vector: &RescueVector<F>) {
202        let mut self_aux = *self;
203        self_aux.pow(&[F::A]);
204        let mut aux = matrix.mul_vec(&self_aux);
205        aux.add_assign(vector);
206        *self = aux;
207    }
208}
209
210impl<F: Copy> From<&[F]> for RescueVector<F> {
211    fn from(field_elems: &[F]) -> RescueVector<F> {
212        assert_eq!(field_elems.len(), STATE_SIZE);
213        RescueVector {
214            vec: [
215                field_elems[0],
216                field_elems[1],
217                field_elems[2],
218                field_elems[3],
219            ],
220        }
221    }
222}
223
224impl<F: Copy> From<&[F; STATE_SIZE]> for RescueVector<F> {
225    fn from(field_elems: &[F; STATE_SIZE]) -> RescueVector<F> {
226        RescueVector { vec: *field_elems }
227    }
228}
229
230/// A matrix that consists of `STATE_SIZE` number of rescue vectors.
231#[derive(Debug, Clone)]
232pub struct RescueMatrix<F> {
233    matrix: [RescueVector<F>; STATE_SIZE],
234}
235
236impl<F: PrimeField> From<&[RescueVector<F>; STATE_SIZE]> for RescueMatrix<F> {
237    fn from(vectors: &[RescueVector<F>; STATE_SIZE]) -> Self {
238        Self { matrix: *vectors }
239    }
240}
241
242impl<F: PrimeField> RescueMatrix<F> {
243    fn mul_vec(&self, vector: &RescueVector<F>) -> RescueVector<F> {
244        let mut result = [F::zero(); STATE_SIZE];
245        self.matrix
246            .iter()
247            .enumerate()
248            .for_each(|(i, row)| result[i] = row.dot_product(vector));
249        RescueVector { vec: result }
250    }
251
252    /// Accessing the i-th vector of the matrix.    
253    /// Function needs to be public for circuits generation..
254    /// WARNING: may expose the internal state.
255    pub fn vec(&self, i: usize) -> RescueVector<F> {
256        self.matrix[i]
257    }
258
259    /// Check if the matrix is empty.
260    pub fn is_empty(&self) -> bool {
261        self.matrix.is_empty()
262    }
263
264    /// Return the number of columns of the matrix.
265    pub fn len(&self) -> usize {
266        self.matrix.len()
267    }
268}
269
270// Rescue Pseudorandom Permutation (PRP) implementation for the BLS12_381 Scalar
271// field with 4 elements as key and input size. From the PRP it derives 3 hash
272// functions: 1. Sponge construction with arbitrary input and output length
273// 2. Sponge construction with input length multiple of the RATE (3) (no padding
274// needed) 3. 3 to 1 hashing (same construction as 1 and 2, but limiting the
275// input to 3 and output to 1
276//
277
278#[derive(Debug, Clone)]
279#[allow(clippy::upper_case_acronyms)]
280/// Rescue pseudo-random permutation (PRP) instance
281pub struct PRP<F> {
282    mds: RescueMatrix<F>,      // rescue permutation MDS matrix
283    init_vec: RescueVector<F>, // rescue permutation initial constants
284    key_injection: Vec<RescueVector<F>>, /* rescue permutation key injection constants to compute
285                                * round keys */
286}
287
288impl<F: RescueParameter> Default for PRP<F> {
289    fn default() -> Self {
290        let mut key_injection = Vec::with_capacity(2 * ROUNDS);
291        for bytes in F::KEY_INJECTION_LE.iter() {
292            key_injection.push(RescueVector::from_elems_le_bytes(
293                bytes[0], bytes[1], bytes[2], bytes[3],
294            ));
295        }
296        PRP {
297            mds: RescueMatrix::from(&[
298                RescueVector::from_elems_le_bytes(
299                    F::MDS_LE[0][0],
300                    F::MDS_LE[0][1],
301                    F::MDS_LE[0][2],
302                    F::MDS_LE[0][3],
303                ),
304                RescueVector::from_elems_le_bytes(
305                    F::MDS_LE[1][0],
306                    F::MDS_LE[1][1],
307                    F::MDS_LE[1][2],
308                    F::MDS_LE[1][3],
309                ),
310                RescueVector::from_elems_le_bytes(
311                    F::MDS_LE[2][0],
312                    F::MDS_LE[2][1],
313                    F::MDS_LE[2][2],
314                    F::MDS_LE[2][3],
315                ),
316                RescueVector::from_elems_le_bytes(
317                    F::MDS_LE[3][0],
318                    F::MDS_LE[3][1],
319                    F::MDS_LE[3][2],
320                    F::MDS_LE[3][3],
321                ),
322            ]),
323            init_vec: RescueVector::from_elems_le_bytes(
324                F::INIT_VEC_LE[0],
325                F::INIT_VEC_LE[1],
326                F::INIT_VEC_LE[2],
327                F::INIT_VEC_LE[3],
328            ),
329            key_injection,
330        }
331    }
332}
333
334impl<F: RescueParameter> PRP<F> {
335    /// Rescue pseudorandom permutation for Bls12381 scalars vectors of size 4
336    /// without key scheduled keys (scheduling occurs online)
337    pub fn prp(&self, key: &RescueVector<F>, input: &RescueVector<F>) -> RescueVector<F> {
338        let round_keys = self.key_schedule(key);
339        self.prp_with_round_keys(round_keys.as_slice(), input)
340    }
341
342    /// Rescue pseudorandom permutation for Bls12381 scalars vectors of size 4
343    /// using scheduled keys
344    pub fn prp_with_round_keys(
345        &self,
346        round_keys: &[RescueVector<F>],
347        input: &RescueVector<F>,
348    ) -> RescueVector<F> {
349        assert_eq!(round_keys.len(), 2 * ROUNDS + 1);
350        let mut perm_state = input.add(&round_keys[0]);
351        round_keys[1..].iter().enumerate().for_each(|(round, key)| {
352            if (round % 2).is_zero() {
353                perm_state.pow(F::A_INV);
354            } else {
355                perm_state.pow(&[F::A]);
356            }
357            perm_state.linear(&self.mds, key)
358        });
359        perm_state
360    }
361
362    /// Key scheduling for rescue based PRP for Bls12_381 scalars vector of size
363    /// 4
364    pub fn key_schedule(&self, key: &RescueVector<F>) -> Vec<RescueVector<F>> {
365        let mut aux = key.add(&self.init_vec);
366        let mut round_keys = vec![aux];
367        (0..2 * ROUNDS).for_each(|i| {
368            let exp = if (i % 2).is_zero() { F::A_INV } else { &[F::A] };
369            aux.pow(exp);
370            aux.linear(&self.mds, &self.key_injection[i]);
371            round_keys.push(aux);
372        });
373        round_keys
374    }
375
376    /// Return a pointer to the mds matrix.
377    /// Does not expose secret states.
378    #[inline]
379    pub fn mds_matrix_ref(&self) -> &RescueMatrix<F> {
380        &self.mds
381    }
382
383    /// Return a pointer to the key injection vectors.
384    /// Function needs to be public for circuits generation..
385    /// WARNING!!! May expose secret state if keys are supposed to be secret.
386    #[inline]
387    pub fn key_injection_vec_ref(&self) -> &[RescueVector<F>] {
388        &self.key_injection
389    }
390
391    /// Return a pointer to the initial vectors.
392    /// Does not expose secret states.
393    #[inline]
394    pub fn init_vec_ref(&self) -> &RescueVector<F> {
395        &self.init_vec
396    }
397}
398
399/// Instance of a unkeyed cryptographic permutation to be used for instantiation
400/// hashing, pseudo-random function, and other cryptographic primitives
401#[derive(Debug, Clone)]
402pub struct Permutation<F> {
403    rescue_prp: PRP<F>,
404    round_keys: Vec<RescueVector<F>>,
405}
406
407impl<F: RescueParameter> From<PRP<F>> for Permutation<F> {
408    fn from(rescue: PRP<F>) -> Self {
409        let mut keys: Vec<RescueVector<F>> = Vec::with_capacity(2 * ROUNDS + 1);
410        for key in F::PERMUTATION_ROUND_KEYS.iter() {
411            keys.push(RescueVector::from_elems_le_bytes(
412                key[0], key[1], key[2], key[3],
413            ))
414        }
415        Permutation {
416            rescue_prp: rescue,
417            round_keys: keys,
418        }
419    }
420}
421
422impl<F: RescueParameter> Default for Permutation<F> {
423    fn default() -> Self {
424        Permutation::from(PRP::default())
425    }
426}
427
428impl<F: RescueParameter> Permutation<F> {
429    /// Return a pointer to the round key.
430    /// Does not expose secret states.
431    #[inline]
432    pub fn round_keys_ref(&self) -> &[RescueVector<F>] {
433        self.round_keys.as_slice()
434    }
435
436    /// Return a pointer to the mds matrix.
437    /// Does not expose secret states.
438    #[inline]
439    pub fn mds_matrix_ref(&self) -> &RescueMatrix<F> {
440        self.rescue_prp.mds_matrix_ref()
441    }
442    /// Compute the permutation on RescueVector `input`
443    pub fn eval(&self, input: &RescueVector<F>) -> RescueVector<F> {
444        self.rescue_prp
445            .prp_with_round_keys(self.round_keys.as_slice(), input)
446    }
447}
448
449#[cfg(test)]
450mod test_prp {
451    use crate::{RescueVector, PRP};
452    use ark_bls12_377::Fq as Fq377;
453    use ark_bn254::Fq as Fq254;
454    use ark_ed_on_bls12_377::Fq as Fr377;
455    use ark_ed_on_bls12_381::Fq as Fr381;
456    use ark_ed_on_bn254::Fq as Fr254;
457
458    // hash output on vector [0, 0, 0, 0]
459    // this value is cross checked with sage script
460    // rescue761.Sponge([0,0,0,0], 4)
461    const OUTPUT761: [[u8; 48]; 4] = [
462        [
463            0x37, 0xBE, 0x12, 0x7E, 0xDF, 0x9C, 0xBF, 0xCE, 0x78, 0xE1, 0x4F, 0xEB, 0x69, 0xAC,
464            0x89, 0x53, 0xE7, 0xC4, 0x8D, 0x89, 0x90, 0x77, 0x64, 0x0D, 0xD0, 0x87, 0x42, 0xDD,
465            0x1F, 0x98, 0x30, 0xC8, 0x0F, 0x12, 0x6D, 0x7A, 0x49, 0xD3, 0x22, 0x2E, 0x12, 0xBA,
466            0x5B, 0x0E, 0x29, 0xB7, 0x2C, 0x01,
467        ],
468        [
469            0x68, 0xFE, 0x2E, 0x95, 0x57, 0xDA, 0x2E, 0x36, 0xEC, 0xC1, 0xC5, 0x8A, 0x19, 0x50,
470            0xD7, 0xBE, 0x11, 0x00, 0x3D, 0x5B, 0xAA, 0x8C, 0xF8, 0x45, 0x6F, 0xDC, 0xE4, 0x1F,
471            0xF0, 0x35, 0xC7, 0x62, 0x6A, 0xC2, 0x33, 0xE7, 0x98, 0x9F, 0x26, 0x2A, 0x6E, 0x89,
472            0xD5, 0x43, 0x21, 0xF8, 0x67, 0x01,
473        ],
474        [
475            0x84, 0xB4, 0x93, 0x04, 0x3B, 0x23, 0x3A, 0x1B, 0x43, 0xC3, 0x61, 0x61, 0x1B, 0xA0,
476            0x59, 0xFB, 0x2E, 0x88, 0x76, 0x62, 0x28, 0xBB, 0x32, 0x6F, 0x27, 0x1C, 0xA9, 0xCA,
477            0x60, 0xC1, 0xE0, 0x7A, 0x7D, 0x37, 0x2F, 0x95, 0x75, 0xDD, 0x37, 0x2A, 0x70, 0xD1,
478            0xE4, 0x55, 0xDB, 0x50, 0x2F, 0x00,
479        ],
480        [
481            0x4E, 0x01, 0x9E, 0x8A, 0x7F, 0x6F, 0x3B, 0xDE, 0x7F, 0xF5, 0x58, 0x0B, 0x1A, 0x34,
482            0x95, 0x8D, 0xBC, 0x94, 0x88, 0xD8, 0x5D, 0x25, 0x7A, 0xB0, 0xCC, 0x72, 0xFE, 0x36,
483            0xC3, 0x13, 0xCB, 0x1B, 0x7A, 0x69, 0xCF, 0xCC, 0xAB, 0x2B, 0x55, 0x11, 0x1E, 0xC5,
484            0x7C, 0xFC, 0x47, 0x7D, 0x9D, 0x01,
485        ],
486    ];
487
488    // hash output on vector [0, 0, 0, 0]
489    // this value is cross checked with sage script
490    // rescue381.Sponge([0,0,0,0], 4)
491    const OUTPUT381: [[u8; 32]; 4] = [
492        [
493            0x12, 0x53, 0x24, 0x66, 0x84, 0xA2, 0x4D, 0x2B, 0xC7, 0x28, 0x3E, 0x0F, 0x80, 0xDF,
494            0x1A, 0xC3, 0x5B, 0xA1, 0xA9, 0x5B, 0x46, 0x60, 0xBD, 0xED, 0xA6, 0xD1, 0x43, 0xB7,
495            0x60, 0xCA, 0x59, 0x0D,
496        ],
497        [
498            0x1B, 0xBE, 0xAB, 0x6C, 0xAB, 0x62, 0xB7, 0xAB, 0x19, 0xDF, 0xFF, 0x4D, 0x73, 0xB5,
499            0x78, 0x30, 0x72, 0xC0, 0xC6, 0xDA, 0x1F, 0x10, 0xAD, 0xD1, 0x28, 0x65, 0xB4, 0x94,
500            0x6F, 0xAC, 0xE5, 0x4B,
501        ],
502        [
503            0x07, 0x86, 0xBD, 0x9A, 0xB3, 0x35, 0x96, 0x22, 0xF0, 0xE5, 0xEA, 0xCC, 0x9C, 0x79,
504            0x89, 0x1F, 0x9D, 0x1D, 0x43, 0x44, 0xCC, 0xA9, 0x9A, 0xB0, 0x0E, 0xC0, 0x57, 0x6B,
505            0x07, 0xF8, 0x53, 0x06,
506        ],
507        [
508            0x9C, 0x23, 0x34, 0xB3, 0x0A, 0xCD, 0x94, 0x11, 0x49, 0xC0, 0x9D, 0x90, 0x7E, 0x7E,
509            0xC8, 0x51, 0x42, 0xD3, 0xCD, 0x5D, 0x05, 0x13, 0x31, 0x66, 0x4D, 0x36, 0x98, 0xCE,
510            0xAC, 0x44, 0x5C, 0x60,
511        ],
512    ];
513    // this value is cross checked with sage script
514    // rescue377.Sponge([0,0,0,0], 4)
515    const OUTPUT377: [[u8; 32]; 4] = [
516        [
517            0x65, 0xF2, 0xF2, 0x74, 0x15, 0x7A, 0x5A, 0xB5, 0xE0, 0x86, 0x46, 0x9D, 0xAE, 0x27,
518            0x29, 0xE0, 0x08, 0x39, 0x0D, 0xA6, 0x44, 0x5E, 0x20, 0x76, 0x23, 0x42, 0xDA, 0xF0,
519            0x49, 0xA3, 0x51, 0x02,
520        ],
521        [
522            0x67, 0xB5, 0x6A, 0xBA, 0x4B, 0xB8, 0x0F, 0xE2, 0xFC, 0x3D, 0x7E, 0xFC, 0x70, 0xCA,
523            0x3D, 0x1D, 0xAC, 0xDD, 0xEA, 0x62, 0x81, 0xD7, 0x08, 0x0B, 0x38, 0x5F, 0x0A, 0x68,
524            0xEC, 0xED, 0x53, 0x02,
525        ],
526        [
527            0x10, 0xC5, 0xA0, 0xA1, 0x8E, 0x8D, 0xBC, 0xAD, 0x99, 0xC3, 0xB4, 0xE9, 0x22, 0xC9,
528            0xB1, 0xCF, 0x35, 0x46, 0xE3, 0x52, 0x99, 0x5B, 0xBE, 0x6E, 0x08, 0xFF, 0x4B, 0x2F,
529            0xCE, 0xF0, 0xCB, 0x0A,
530        ],
531        [
532            0x33, 0xB0, 0xD0, 0x58, 0xE9, 0x25, 0x15, 0xB2, 0x8A, 0x9D, 0x16, 0x04, 0xEB, 0x26,
533            0xC4, 0x0E, 0x3F, 0xBF, 0xCF, 0x49, 0x20, 0xA8, 0x89, 0xE2, 0x16, 0x2D, 0x76, 0x19,
534            0xDF, 0x01, 0x02, 0x09,
535        ],
536    ];
537
538    // this value is cross checked with sage script
539    // rescue254.Sponge([0,0,0,0], 4)
540    const OUTPUT254: [[u8; 32]; 4] = [
541        [
542            0xDD, 0xE7, 0x55, 0x8E, 0x14, 0xF9, 0x4C, 0xEE, 0x9F, 0xCC, 0xB2, 0x02, 0xFC, 0x0E,
543            0x54, 0x21, 0xF2, 0xAA, 0xB8, 0x48, 0x05, 0xDB, 0x9B, 0x7A, 0xD2, 0x36, 0xA5, 0xF1,
544            0x49, 0x77, 0xB4, 0x17,
545        ],
546        [
547            0x43, 0x5F, 0x99, 0x3C, 0xB7, 0xB3, 0x84, 0x74, 0x4E, 0x80, 0x83, 0xFF, 0x73, 0x20,
548            0x07, 0xD9, 0x7B, 0xEC, 0x4B, 0x90, 0x48, 0x1D, 0xFD, 0x72, 0x4C, 0xF0, 0xA5, 0x7C,
549            0xDC, 0x68, 0xC0, 0x25,
550        ],
551        [
552            0x2C, 0x7B, 0x21, 0x09, 0x9D, 0x10, 0xE9, 0x5C, 0x36, 0x3E, 0x6D, 0x20, 0x28, 0xBB,
553            0xDB, 0x1E, 0xED, 0xF4, 0x22, 0x9B, 0x3A, 0xEE, 0x1E, 0x6F, 0x89, 0x13, 0x3D, 0x1E,
554            0x4C, 0xA0, 0xA6, 0x23,
555        ],
556        [
557            0x25, 0x9B, 0x47, 0xA2, 0x29, 0xFD, 0xC1, 0x08, 0xA9, 0xD1, 0x44, 0x71, 0x15, 0x8A,
558            0x5A, 0x1A, 0x55, 0x5B, 0x88, 0xAE, 0xD6, 0xF6, 0x57, 0xD3, 0x33, 0x07, 0xE1, 0x5B,
559            0x71, 0x5F, 0x12, 0x25,
560        ],
561    ];
562
563    // this value is cross checked with sage script
564    // rescue254.Sponge([0,0,0,0], 4)
565    const OUTPUTFQ254: [[u8; 32]; 4] = [
566        [
567            0xC9, 0xAC, 0x42, 0x08, 0x04, 0x18, 0xFC, 0x10, 0xA4, 0x41, 0xF4, 0xF9, 0x06, 0x2B,
568            0xE2, 0x87, 0xB7, 0x7A, 0xC4, 0x65, 0x8C, 0xE0, 0xE9, 0x78, 0xB0, 0x48, 0x39, 0xB6,
569            0x96, 0x9B, 0x60, 0x1B,
570        ],
571        [
572            0x00, 0xC2, 0xF9, 0x07, 0x54, 0x25, 0xF2, 0xC6, 0x75, 0x21, 0x01, 0x14, 0xF6, 0xD1,
573            0xAF, 0xE1, 0x0D, 0xD4, 0xFC, 0xEC, 0x15, 0xF3, 0x7D, 0x9A, 0x91, 0x26, 0x51, 0xDE,
574            0xC8, 0x8A, 0x19, 0x09,
575        ],
576        [
577            0x78, 0xDB, 0xB7, 0xEA, 0xD4, 0x35, 0x5E, 0xED, 0xAE, 0x14, 0xD6, 0xB1, 0xE8, 0x0D,
578            0xB4, 0xA7, 0x29, 0x9B, 0xBA, 0x6F, 0xBD, 0xA4, 0xEB, 0x52, 0x7D, 0xD5, 0x9B, 0x03,
579            0x17, 0x83, 0x06, 0x1D,
580        ],
581        [
582            0x72, 0xC6, 0xB8, 0xF9, 0x9E, 0xF3, 0xDA, 0x20, 0xED, 0x3D, 0xE4, 0x39, 0x87, 0x28,
583            0xE9, 0x25, 0x0D, 0x8D, 0x57, 0xCE, 0xEE, 0xCA, 0x35, 0xFB, 0x8E, 0x7E, 0xE3, 0x32,
584            0xDA, 0x03, 0x3F, 0x1B,
585        ],
586    ];
587
588    #[test]
589    fn test_rescue_perm_on_0_vec() {
590        test_rescue_perm_on_0_vec_fq254();
591        test_rescue_perm_on_0_vec_254();
592        test_rescue_perm_on_0_vec_377();
593        test_rescue_perm_on_0_vec_381();
594        test_rescue_perm_on_0_vec_761();
595    }
596
597    fn test_rescue_perm_on_0_vec_fq254() {
598        let rescue = PRP::<Fq254>::default();
599        let key = RescueVector::zero();
600        let input = RescueVector::zero();
601        let expected = RescueVector::from_elems_le_bytes(
602            &OUTPUTFQ254[0],
603            &OUTPUTFQ254[1],
604            &OUTPUTFQ254[2],
605            &OUTPUTFQ254[3],
606        );
607        let real_output = rescue.prp(&key, &input);
608        let round_keys = rescue.key_schedule(&key);
609
610        let real_output_with_round_keys = rescue.prp_with_round_keys(&round_keys, &input);
611        assert_eq!(real_output, real_output_with_round_keys);
612        assert_eq!(real_output, expected);
613    }
614
615    fn test_rescue_perm_on_0_vec_254() {
616        let rescue = PRP::<Fr254>::default();
617        let key = RescueVector::zero();
618        let input = RescueVector::zero();
619        let expected = RescueVector::from_elems_le_bytes(
620            &OUTPUT254[0],
621            &OUTPUT254[1],
622            &OUTPUT254[2],
623            &OUTPUT254[3],
624        );
625        let real_output = rescue.prp(&key, &input);
626        let round_keys = rescue.key_schedule(&key);
627        let real_output_with_round_keys = rescue.prp_with_round_keys(&round_keys, &input);
628        assert_eq!(real_output, real_output_with_round_keys);
629        assert_eq!(real_output, expected);
630    }
631
632    fn test_rescue_perm_on_0_vec_381() {
633        let rescue = PRP::<Fr381>::default();
634        let key = RescueVector::zero();
635        let input = RescueVector::zero();
636        let expected = RescueVector::from_elems_le_bytes(
637            &OUTPUT381[0],
638            &OUTPUT381[1],
639            &OUTPUT381[2],
640            &OUTPUT381[3],
641        );
642        let real_output = rescue.prp(&key, &input);
643        let round_keys = rescue.key_schedule(&key);
644        let real_output_with_round_keys = rescue.prp_with_round_keys(&round_keys, &input);
645
646        assert_eq!(real_output, real_output_with_round_keys);
647        assert_eq!(real_output, expected);
648    }
649
650    fn test_rescue_perm_on_0_vec_377() {
651        let rescue = PRP::<Fr377>::default();
652        let key = RescueVector::zero();
653        let input = RescueVector::zero();
654        let expected = RescueVector::from_elems_le_bytes(
655            &OUTPUT377[0],
656            &OUTPUT377[1],
657            &OUTPUT377[2],
658            &OUTPUT377[3],
659        );
660        let real_output = rescue.prp(&key, &input);
661        let round_keys = rescue.key_schedule(&key);
662        let real_output_with_round_keys = rescue.prp_with_round_keys(&round_keys, &input);
663        assert_eq!(real_output, real_output_with_round_keys);
664        assert_eq!(real_output, expected);
665    }
666
667    fn test_rescue_perm_on_0_vec_761() {
668        let rescue = PRP::<Fq377>::default();
669        let key = RescueVector::zero();
670        let input = RescueVector::zero();
671        let expected = RescueVector::from_elems_le_bytes(
672            &OUTPUT761[0],
673            &OUTPUT761[1],
674            &OUTPUT761[2],
675            &OUTPUT761[3],
676        );
677        let real_output = rescue.prp(&key, &input);
678        let round_keys = rescue.key_schedule(&key);
679        let real_output_with_round_keys = rescue.prp_with_round_keys(&round_keys, &input);
680        assert_eq!(real_output, real_output_with_round_keys);
681        assert_eq!(real_output, expected);
682    }
683
684    // printing vectors as hex bytes little endian
685    // use ark_ff::{BigInteger, PrimeField};
686    // use ark_std::{format, println, string::String, vec::Vec};
687    // #[test]
688    // fn print() {
689    //     let rescue_hash = PRP::<Fq254>::default();
690    //     println!("KeySchedule:");
691    //     let keys = rescue_hash.key_schedule(&RescueVector::zero());
692    //     println!("[");
693    //     for key in keys {
694    //         for elem in key.vec.iter() {
695    //             let str: Vec<String> = elem
696    //                 .into_bigint()
697    //                 .to_bytes_le()
698    //                 .iter()
699    //                 .map(|b| format!("0x{:02X},", b))
700    //                 .collect();
701    //             println!("&[{}],", str.join(" "));
702    //         }
703    //         println!("],[");
704    //     }
705    // }
706}
707
708#[cfg(test)]
709mod test_permutation {
710    use crate::{crhf::RescueCRHF, Permutation, RescueParameter, RescueVector, PRP};
711    use ark_bls12_377::Fq as Fq377;
712    use ark_bn254::Fq as Fq254;
713    use ark_ed_on_bls12_377::Fq as Fr377;
714    use ark_ed_on_bls12_381::Fq as Fr381;
715    use ark_ed_on_bn254::Fq as Fr254;
716    use ark_ff::PrimeField;
717    use ark_std::{vec, Zero};
718
719    #[test]
720    fn test_round_keys() {
721        test_round_keys_helper::<Fq254>();
722        test_round_keys_helper::<Fr254>();
723        test_round_keys_helper::<Fr377>();
724        test_round_keys_helper::<Fr381>();
725        test_round_keys_helper::<Fq377>();
726    }
727
728    fn test_round_keys_helper<F: RescueParameter>() {
729        let rescue_perm = PRP::<F>::default();
730        let rescue_hash = Permutation::default();
731        let zero = RescueVector::zero();
732        let keys2 = rescue_perm.key_schedule(&zero);
733
734        // // the following code is used to dump the key schedule to screen
735        // // in a sage friendly format
736        // for e in keys2.iter() {
737        //     for f in e.vec.iter() {
738        //         ark_std::println!("permutation_round_key.append({})",
739        // f.into_bigint());     }
740        // }
741        // assert!(false);
742
743        assert_eq!(rescue_hash.round_keys, keys2);
744    }
745
746    // hash output on vector [0, 0, 0, 0]
747    // this value is cross checked with sage script
748    // first three vectors of rescue761.Sponge([0,0,0,0], 4)
749    const OUTPUT761: [[u8; 48]; 3] = [
750        [
751            0x37, 0xBE, 0x12, 0x7E, 0xDF, 0x9C, 0xBF, 0xCE, 0x78, 0xE1, 0x4F, 0xEB, 0x69, 0xAC,
752            0x89, 0x53, 0xE7, 0xC4, 0x8D, 0x89, 0x90, 0x77, 0x64, 0x0D, 0xD0, 0x87, 0x42, 0xDD,
753            0x1F, 0x98, 0x30, 0xC8, 0x0F, 0x12, 0x6D, 0x7A, 0x49, 0xD3, 0x22, 0x2E, 0x12, 0xBA,
754            0x5B, 0x0E, 0x29, 0xB7, 0x2C, 0x01,
755        ],
756        [
757            0x68, 0xFE, 0x2E, 0x95, 0x57, 0xDA, 0x2E, 0x36, 0xEC, 0xC1, 0xC5, 0x8A, 0x19, 0x50,
758            0xD7, 0xBE, 0x11, 0x00, 0x3D, 0x5B, 0xAA, 0x8C, 0xF8, 0x45, 0x6F, 0xDC, 0xE4, 0x1F,
759            0xF0, 0x35, 0xC7, 0x62, 0x6A, 0xC2, 0x33, 0xE7, 0x98, 0x9F, 0x26, 0x2A, 0x6E, 0x89,
760            0xD5, 0x43, 0x21, 0xF8, 0x67, 0x01,
761        ],
762        [
763            0x84, 0xB4, 0x93, 0x04, 0x3B, 0x23, 0x3A, 0x1B, 0x43, 0xC3, 0x61, 0x61, 0x1B, 0xA0,
764            0x59, 0xFB, 0x2E, 0x88, 0x76, 0x62, 0x28, 0xBB, 0x32, 0x6F, 0x27, 0x1C, 0xA9, 0xCA,
765            0x60, 0xC1, 0xE0, 0x7A, 0x7D, 0x37, 0x2F, 0x95, 0x75, 0xDD, 0x37, 0x2A, 0x70, 0xD1,
766            0xE4, 0x55, 0xDB, 0x50, 0x2F, 0x00,
767        ],
768    ];
769
770    // hash output on vector [0, 0, 0, 0]
771    // this value is cross checked with sage script
772    // first three vectors of rescue254.Sponge([0,0,0,0], 4)
773    const OUTPUT254: [[u8; 32]; 3] = [
774        [
775            0xDD, 0xE7, 0x55, 0x8E, 0x14, 0xF9, 0x4C, 0xEE, 0x9F, 0xCC, 0xB2, 0x02, 0xFC, 0x0E,
776            0x54, 0x21, 0xF2, 0xAA, 0xB8, 0x48, 0x05, 0xDB, 0x9B, 0x7A, 0xD2, 0x36, 0xA5, 0xF1,
777            0x49, 0x77, 0xB4, 0x17,
778        ],
779        [
780            0x43, 0x5F, 0x99, 0x3C, 0xB7, 0xB3, 0x84, 0x74, 0x4E, 0x80, 0x83, 0xFF, 0x73, 0x20,
781            0x07, 0xD9, 0x7B, 0xEC, 0x4B, 0x90, 0x48, 0x1D, 0xFD, 0x72, 0x4C, 0xF0, 0xA5, 0x7C,
782            0xDC, 0x68, 0xC0, 0x25,
783        ],
784        [
785            0x2C, 0x7B, 0x21, 0x09, 0x9D, 0x10, 0xE9, 0x5C, 0x36, 0x3E, 0x6D, 0x20, 0x28, 0xBB,
786            0xDB, 0x1E, 0xED, 0xF4, 0x22, 0x9B, 0x3A, 0xEE, 0x1E, 0x6F, 0x89, 0x13, 0x3D, 0x1E,
787            0x4C, 0xA0, 0xA6, 0x23,
788        ],
789    ];
790    // hash output on vector [0, 0, 0, 0]
791    // this value is cross checked with sage script
792    // first three vectors of rescue377.Sponge([0,0,0,0], 4)
793    const OUTPUT377: [[u8; 32]; 3] = [
794        [
795            0x65, 0xF2, 0xF2, 0x74, 0x15, 0x7A, 0x5A, 0xB5, 0xE0, 0x86, 0x46, 0x9D, 0xAE, 0x27,
796            0x29, 0xE0, 0x08, 0x39, 0x0D, 0xA6, 0x44, 0x5E, 0x20, 0x76, 0x23, 0x42, 0xDA, 0xF0,
797            0x49, 0xA3, 0x51, 0x02,
798        ],
799        [
800            0x67, 0xB5, 0x6A, 0xBA, 0x4B, 0xB8, 0x0F, 0xE2, 0xFC, 0x3D, 0x7E, 0xFC, 0x70, 0xCA,
801            0x3D, 0x1D, 0xAC, 0xDD, 0xEA, 0x62, 0x81, 0xD7, 0x08, 0x0B, 0x38, 0x5F, 0x0A, 0x68,
802            0xEC, 0xED, 0x53, 0x02,
803        ],
804        [
805            0x10, 0xC5, 0xA0, 0xA1, 0x8E, 0x8D, 0xBC, 0xAD, 0x99, 0xC3, 0xB4, 0xE9, 0x22, 0xC9,
806            0xB1, 0xCF, 0x35, 0x46, 0xE3, 0x52, 0x99, 0x5B, 0xBE, 0x6E, 0x08, 0xFF, 0x4B, 0x2F,
807            0xCE, 0xF0, 0xCB, 0x0A,
808        ],
809    ];
810
811    // hash output on vector [0, 0, 0, 0]
812    // this value is cross checked with sage script
813    // first three vectors of rescue381.Sponge([0,0,0,0], 4)
814    const OUTPUT381: [[u8; 32]; 3] = [
815        [
816            0x12, 0x53, 0x24, 0x66, 0x84, 0xA2, 0x4D, 0x2B, 0xC7, 0x28, 0x3E, 0x0F, 0x80, 0xDF,
817            0x1A, 0xC3, 0x5B, 0xA1, 0xA9, 0x5B, 0x46, 0x60, 0xBD, 0xED, 0xA6, 0xD1, 0x43, 0xB7,
818            0x60, 0xCA, 0x59, 0x0D,
819        ],
820        [
821            0x1B, 0xBE, 0xAB, 0x6C, 0xAB, 0x62, 0xB7, 0xAB, 0x19, 0xDF, 0xFF, 0x4D, 0x73, 0xB5,
822            0x78, 0x30, 0x72, 0xC0, 0xC6, 0xDA, 0x1F, 0x10, 0xAD, 0xD1, 0x28, 0x65, 0xB4, 0x94,
823            0x6F, 0xAC, 0xE5, 0x4B,
824        ],
825        [
826            0x07, 0x86, 0xBD, 0x9A, 0xB3, 0x35, 0x96, 0x22, 0xF0, 0xE5, 0xEA, 0xCC, 0x9C, 0x79,
827            0x89, 0x1F, 0x9D, 0x1D, 0x43, 0x44, 0xCC, 0xA9, 0x9A, 0xB0, 0x0E, 0xC0, 0x57, 0x6B,
828            0x07, 0xF8, 0x53, 0x06,
829        ],
830    ];
831
832    // this value is cross checked with sage script
833    // rescue254.Sponge([0,0,0,0], 4)
834    const OUTPUTFQ254: [[u8; 32]; 4] = [
835        [
836            0xC9, 0xAC, 0x42, 0x08, 0x04, 0x18, 0xFC, 0x10, 0xA4, 0x41, 0xF4, 0xF9, 0x06, 0x2B,
837            0xE2, 0x87, 0xB7, 0x7A, 0xC4, 0x65, 0x8C, 0xE0, 0xE9, 0x78, 0xB0, 0x48, 0x39, 0xB6,
838            0x96, 0x9B, 0x60, 0x1B,
839        ],
840        [
841            0x00, 0xC2, 0xF9, 0x07, 0x54, 0x25, 0xF2, 0xC6, 0x75, 0x21, 0x01, 0x14, 0xF6, 0xD1,
842            0xAF, 0xE1, 0x0D, 0xD4, 0xFC, 0xEC, 0x15, 0xF3, 0x7D, 0x9A, 0x91, 0x26, 0x51, 0xDE,
843            0xC8, 0x8A, 0x19, 0x09,
844        ],
845        [
846            0x78, 0xDB, 0xB7, 0xEA, 0xD4, 0x35, 0x5E, 0xED, 0xAE, 0x14, 0xD6, 0xB1, 0xE8, 0x0D,
847            0xB4, 0xA7, 0x29, 0x9B, 0xBA, 0x6F, 0xBD, 0xA4, 0xEB, 0x52, 0x7D, 0xD5, 0x9B, 0x03,
848            0x17, 0x83, 0x06, 0x1D,
849        ],
850        [
851            0x72, 0xC6, 0xB8, 0xF9, 0x9E, 0xF3, 0xDA, 0x20, 0xED, 0x3D, 0xE4, 0x39, 0x87, 0x28,
852            0xE9, 0x25, 0x0D, 0x8D, 0x57, 0xCE, 0xEE, 0xCA, 0x35, 0xFB, 0x8E, 0x7E, 0xE3, 0x32,
853            0xDA, 0x03, 0x3F, 0x1B,
854        ],
855    ];
856
857    #[test]
858    fn test_sponge() {
859        test_sponge_helper::<Fq254>();
860        test_sponge_helper::<Fr254>();
861        test_sponge_helper::<Fr377>();
862        test_sponge_helper::<Fr381>();
863        test_sponge_helper::<Fq377>();
864    }
865
866    fn test_sponge_helper<F: RescueParameter>() {
867        let rescue_prp = PRP::default();
868        let mut prng = jf_utils::test_rng();
869        let e0 = F::rand(&mut prng);
870        let e1 = F::rand(&mut prng);
871        let e2 = F::rand(&mut prng);
872        let e3 = F::rand(&mut prng);
873        let e4 = F::rand(&mut prng);
874        let e5 = F::rand(&mut prng);
875
876        let input = [e0, e1, e2, e3, e4, e5];
877
878        let output = RescueCRHF::<F>::sponge_no_padding(&input, 1).unwrap()[0];
879
880        let zero = RescueVector::zero();
881        // First block: overwrite rate elements with input[0..3]
882        let mut state = RescueVector {
883            vec: [input[0], input[1], input[2], F::zero()],
884        };
885        state = rescue_prp.prp(&zero, &state);
886
887        // Second block: overwrite rate elements with input[3..6] (overwrite mode)
888        state.vec[0] = input[3];
889        state.vec[1] = input[4];
890        state.vec[2] = input[5];
891        state = rescue_prp.prp(&zero, &state);
892        assert_eq!(output, state.vec[0]);
893    }
894
895    #[test]
896    fn test_rescue_hash_on_0_vec() {
897        test_rescue_hash_on_0_vec_fq254();
898        test_rescue_hash_on_0_vec_254();
899        test_rescue_hash_on_0_vec_377();
900        test_rescue_hash_on_0_vec_381();
901        test_rescue_hash_on_0_vec_761()
902    }
903
904    fn test_rescue_hash_on_0_vec_fq254() {
905        let input = [Fq254::zero(); 3];
906        let expected = vec![
907            Fq254::from_le_bytes_mod_order(&OUTPUTFQ254[0]),
908            Fq254::from_le_bytes_mod_order(&OUTPUTFQ254[1]),
909            Fq254::from_le_bytes_mod_order(&OUTPUTFQ254[2]),
910        ];
911        let real_output = RescueCRHF::sponge_no_padding(&input, 3).unwrap();
912        assert_eq!(real_output, expected);
913    }
914
915    fn test_rescue_hash_on_0_vec_254() {
916        let input = [Fr254::zero(); 3];
917        let expected = vec![
918            Fr254::from_le_bytes_mod_order(&OUTPUT254[0]),
919            Fr254::from_le_bytes_mod_order(&OUTPUT254[1]),
920            Fr254::from_le_bytes_mod_order(&OUTPUT254[2]),
921        ];
922        let real_output = RescueCRHF::sponge_no_padding(&input, 3).unwrap();
923        assert_eq!(real_output, expected);
924    }
925
926    fn test_rescue_hash_on_0_vec_377() {
927        let input = [Fr377::zero(); 3];
928        let expected = vec![
929            Fr377::from_le_bytes_mod_order(&OUTPUT377[0]),
930            Fr377::from_le_bytes_mod_order(&OUTPUT377[1]),
931            Fr377::from_le_bytes_mod_order(&OUTPUT377[2]),
932        ];
933        let real_output = RescueCRHF::sponge_no_padding(&input, 3).unwrap();
934        assert_eq!(real_output, expected);
935    }
936
937    fn test_rescue_hash_on_0_vec_381() {
938        let input = [Fr381::zero(); 3];
939        let expected = vec![
940            Fr381::from_le_bytes_mod_order(&OUTPUT381[0]),
941            Fr381::from_le_bytes_mod_order(&OUTPUT381[1]),
942            Fr381::from_le_bytes_mod_order(&OUTPUT381[2]),
943        ];
944        let real_output = RescueCRHF::sponge_no_padding(&input, 3).unwrap();
945        assert_eq!(real_output, expected);
946    }
947
948    fn test_rescue_hash_on_0_vec_761() {
949        let input = [Fq377::zero(); 3];
950        let expected = vec![
951            Fq377::from_le_bytes_mod_order(&OUTPUT761[0]),
952            Fq377::from_le_bytes_mod_order(&OUTPUT761[1]),
953            Fq377::from_le_bytes_mod_order(&OUTPUT761[2]),
954        ];
955        let real_output = RescueCRHF::sponge_no_padding(&input, 3).unwrap();
956        assert_eq!(real_output, expected);
957    }
958}