zkhash/gmimc/
gmimc.rs

Help
1use crate::merkle_tree::merkle_tree_fp::MerkleTreeHash;
2
3use std::sync::Arc;
4
5use ark_ff::PrimeField;
6
7use super::gmimc_params::GmimcParams;
8
9#[derive(Clone, Debug)]
10pub struct Gmimc<S: PrimeField> {
11    pub(crate) params: Arc<GmimcParams<S>>,
12}
13
14impl<S: PrimeField> Gmimc<S> {
15    pub fn new(params: &Arc<GmimcParams<S>>) -> Self {
16        Gmimc {
17            params: Arc::clone(params),
18        }
19    }
20
21    pub fn get_t(&self) -> usize {
22        self.params.t
23    }
24
25    fn sbox(&self, state_0: &S, round: usize) -> S {
26        let mut input = *state_0;
27        input.add_assign(&self.params.round_constants[round]);
28
29        let mut input2 = input.to_owned();
30        input2.square_in_place();
31        match self.params.d {
32            3 => {
33                let mut out = input2;
34                out.mul_assign(&input);
35                out
36            }
37            5 => {
38                let mut out = input2;
39                out.square_in_place();
40                out.mul_assign(&input);
41                out
42            }
43            7 => {
44                let mut out = input2;
45                out.square_in_place();
46                out.mul_assign(&input2);
47                out.mul_assign(&input);
48                out
49            }
50            _ => {
51                panic!();
52            }
53        }
54    }
55
56    fn round(&self, state: &mut [S], round: usize) {
57        let power = self.sbox(&state[0], round);
58        state.iter_mut().skip(1).for_each(|f| f.add_assign(&power));
59    }
60
61    pub fn permutation(&self, input: &[S]) -> Vec<S> {
62        let t = self.params.t;
63        // not opt is faster for small t
64        if t < 8 {
65            return self.permutation_not_opt(input);
66        }
67
68        assert_eq!(t, input.len());
69        let mut current_state = input.to_owned();
70        let mut acc = S::zero();
71        let mut acc_queue = vec![S::zero(); t - 1];
72        for r in 0..self.params.rounds - 1 {
73            let power = self.sbox(&current_state[0], r);
74            acc_queue.rotate_right(1);
75            acc.sub_assign(&acc_queue[0]);
76            acc_queue[0] = power;
77            acc.add_assign(&power);
78
79            current_state.rotate_right(1);
80            current_state[0].add_assign(&acc);
81        }
82
83        // finally without rotation
84        let power = self.sbox(&current_state[0], self.params.rounds - 1);
85        acc_queue.rotate_right(1);
86        acc.sub_assign(&acc_queue[0]);
87        acc_queue[0] = power;
88        acc.add_assign(&power);
89        current_state[t - 1].add_assign(&acc);
90
91        // final adds
92        for el in current_state.iter_mut().skip(1).take(t - 2).rev() {
93            acc_queue.rotate_right(1);
94            acc.sub_assign(&acc_queue[0]);
95            el.add_assign(&acc);
96        }
97
98        current_state
99    }
100
101    pub fn permutation_not_opt(&self, input: &[S]) -> Vec<S> {
102        assert_eq!(self.params.t, input.len());
103        let mut current_state = input.to_owned();
104        for r in 0..self.params.rounds - 1 {
105            self.round(&mut current_state, r);
106            current_state.rotate_right(1);
107        }
108
109        // finally without rotation
110        self.round(&mut current_state, self.params.rounds - 1);
111
112        current_state
113    }
114}
115
116impl<F: PrimeField> MerkleTreeHash<F> for Gmimc<F> {
117    fn compress(&self, input: &[&F]) -> F {
118        self.permutation(&[input[0].to_owned(), input[1].to_owned(), F::zero()])[0]
119    }
120}
121
122#[cfg(test)]
123mod gmimc_tests_bls12 {
124    use super::*;
125    use crate::gmimc::gmimc_instance_bls12::GMIMC_BLS_3_PARAMS;
126    use crate::fields::{bls12::FpBLS12, utils::random_scalar};
127
128    type Scalar = FpBLS12;
129
130    static TESTRUNS: usize = 5;
131
132    #[test]
133    fn consistent_perm() {
134        let gmimc = Gmimc::new(&GMIMC_BLS_3_PARAMS);
135        let t = gmimc.params.t;
136        for _ in 0..TESTRUNS {
137            let input1: Vec<Scalar> = (0..t).map(|_| random_scalar()).collect();
138
139            let mut input2: Vec<Scalar>;
140            loop {
141                input2 = (0..t).map(|_| random_scalar()).collect();
142                if input1 != input2 {
143                    break;
144                }
145            }
146
147            let perm1 = gmimc.permutation(&input1);
148            let perm2 = gmimc.permutation(&input1);
149            let perm3 = gmimc.permutation(&input2);
150            assert_eq!(perm1, perm2);
151            assert_ne!(perm1, perm3);
152        }
153    }
154
155    #[test]
156    fn opt_equals_not_opt() {
157        let gmimc = Gmimc::new(&GMIMC_BLS_3_PARAMS);
158        let t = gmimc.params.t;
159        for _ in 0..TESTRUNS {
160            let input: Vec<Scalar> = (0..t).map(|_| random_scalar()).collect();
161
162            let perm1 = gmimc.permutation(&input);
163            let perm2 = gmimc.permutation_not_opt(&input);
164            assert_eq!(perm1, perm2);
165        }
166    }
167}
168
169#[cfg(test)]
170mod gmimc_tests_bn256 {
171    use super::*;
172    use crate::gmimc::gmimc_instance_bn256::GMIMC_BN_3_PARAMS;
173    use crate::fields::{bn256::FpBN256, utils::random_scalar};
174
175    type Scalar = FpBN256;
176
177    static TESTRUNS: usize = 5;
178
179    #[test]
180    fn consistent_perm() {
181        let gmimc = Gmimc::new(&GMIMC_BN_3_PARAMS);
182        let t = gmimc.params.t;
183        for _ in 0..TESTRUNS {
184            let input1: Vec<Scalar> = (0..t).map(|_| random_scalar()).collect();
185
186            let mut input2: Vec<Scalar>;
187            loop {
188                input2 = (0..t).map(|_| random_scalar()).collect();
189                if input1 != input2 {
190                    break;
191                }
192            }
193
194            let perm1 = gmimc.permutation(&input1);
195            let perm2 = gmimc.permutation(&input1);
196            let perm3 = gmimc.permutation(&input2);
197            assert_eq!(perm1, perm2);
198            assert_ne!(perm1, perm3);
199        }
200    }
201
202    #[test]
203    fn opt_equals_not_opt() {
204        let gmimc = Gmimc::new(&GMIMC_BN_3_PARAMS);
205        let t = gmimc.params.t;
206        for _ in 0..TESTRUNS {
207            let input: Vec<Scalar> = (0..t).map(|_| random_scalar()).collect();
208
209            let perm1 = gmimc.permutation(&input);
210            let perm2 = gmimc.permutation_not_opt(&input);
211            assert_eq!(perm1, perm2);
212        }
213    }
214}
215
216#[cfg(test)]
217mod gmimc_tests_goldilocks {
218    use super::*;
219    use crate::fields::{goldilocks::FpGoldiLocks, utils::random_scalar};
220    use crate::gmimc::gmimc_instance_goldilocks::{
221        GMIMC_GOLDILOCKS_8_PARAMS,
222        GMIMC_GOLDILOCKS_12_PARAMS,
223        GMIMC_GOLDILOCKS_16_PARAMS,
224        GMIMC_GOLDILOCKS_20_PARAMS,
225    };
226
227    type Scalar = FpGoldiLocks;
228
229    static TESTRUNS: usize = 5;
230
231    #[test]
232    fn consistent_perm() {
233        let instances = vec![
234            Gmimc::new(&GMIMC_GOLDILOCKS_8_PARAMS),
235            Gmimc::new(&GMIMC_GOLDILOCKS_12_PARAMS),
236            Gmimc::new(&GMIMC_GOLDILOCKS_16_PARAMS),
237            Gmimc::new(&GMIMC_GOLDILOCKS_20_PARAMS),
238        ];
239        for instance in instances {
240            let t = instance.params.t;
241            for _ in 0..TESTRUNS {
242                let input1: Vec<Scalar> = (0..t).map(|_| random_scalar()).collect();
243
244                let mut input2: Vec<Scalar>;
245                loop {
246                    input2 = (0..t).map(|_| random_scalar()).collect();
247                    if input1 != input2 {
248                        break;
249                    }
250                }
251
252                let perm1 = instance.permutation(&input1);
253                let perm2 = instance.permutation(&input1);
254                let perm3 = instance.permutation(&input2);
255                assert_eq!(perm1, perm2);
256                assert_ne!(perm1, perm3);
257            }
258        }
259    }
260
261    #[test]
262    fn opt_equals_not_opt() {
263        let instances = vec![
264            Gmimc::new(&GMIMC_GOLDILOCKS_8_PARAMS),
265            Gmimc::new(&GMIMC_GOLDILOCKS_12_PARAMS),
266            Gmimc::new(&GMIMC_GOLDILOCKS_16_PARAMS),
267            Gmimc::new(&GMIMC_GOLDILOCKS_20_PARAMS),
268        ];
269        for instance in instances {
270            let t = instance.params.t;
271            for _ in 0..TESTRUNS {
272                let input: Vec<Scalar> = (0..t).map(|_| random_scalar()).collect();
273
274                let perm1 = instance.permutation(&input);
275                let perm2 = instance.permutation_not_opt(&input);
276                assert_eq!(perm1, perm2);
277            }
278        }
279    }
280}
281
282#[cfg(test)]
283mod gmimc_tests_babybear {
284    use super::*;
285    use crate::gmimc::gmimc_instance_babybear::GMIMC_BABYBEAR_16_PARAMS;
286    use crate::gmimc::gmimc_instance_babybear::GMIMC_BABYBEAR_24_PARAMS;
287    use crate::fields::{babybear::FpBabyBear, utils::random_scalar};
288
289    type Scalar = FpBabyBear;
290
291    static TESTRUNS: usize = 5;
292
293    #[test]
294    fn consistent_perm() {
295        let instances = vec![
296            Gmimc::new(&GMIMC_BABYBEAR_16_PARAMS),
297            Gmimc::new(&GMIMC_BABYBEAR_24_PARAMS),
298        ];
299        for instance in instances {
300            let t = instance.params.t;
301            for _ in 0..TESTRUNS {
302                let input1: Vec<Scalar> = (0..t).map(|_| random_scalar()).collect();
303
304                let mut input2: Vec<Scalar>;
305                loop {
306                    input2 = (0..t).map(|_| random_scalar()).collect();
307                    if input1 != input2 {
308                        break;
309                    }
310                }
311
312                let perm1 = instance.permutation(&input1);
313                let perm2 = instance.permutation(&input1);
314                let perm3 = instance.permutation(&input2);
315                assert_eq!(perm1, perm2);
316                assert_ne!(perm1, perm3);
317            }
318        }
319    }
320
321    #[test]
322    fn opt_equals_not_opt() {
323        let instances = vec![
324            Gmimc::new(&GMIMC_BABYBEAR_16_PARAMS),
325            Gmimc::new(&GMIMC_BABYBEAR_24_PARAMS),
326        ];
327        for instance in instances {
328            let t = instance.params.t;
329            for _ in 0..TESTRUNS {
330                let input: Vec<Scalar> = (0..t).map(|_| random_scalar()).collect();
331
332                let perm1 = instance.permutation(&input);
333                let perm2 = instance.permutation_not_opt(&input);
334                assert_eq!(perm1, perm2);
335            }
336        }
337    }
338}
zkhash/gmimc/gmimc.rs

zkhash/gmimc/
gmimc.rs
