jf_relation/gadgets/ultraplonk/
non_native_gates.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 non-native circuits that are mainly
8//! useful for rescue hash function.
9
10use super::mod_arith::{FpElem, FpElemVar};
11use crate::{Circuit, CircuitError, PlonkCircuit};
12use ark_ff::{BigInteger, PrimeField};
13use ark_std::{format, vec::Vec};
14
15impl<F: PrimeField> PlonkCircuit<F> {
16    /// generate a non-native circuit for the statement x^11 = y
17    ///
18    /// Input:
19    ///  - variable representation of x over a target field `T` whose order is
20    ///    less than F.
21    ///  - variable representation of x^11 over a same field
22    ///
23    /// Cost: 5 mod_mul + 2 equal gate
24    pub fn non_native_power_11_gate<T: PrimeField>(
25        &mut self,
26        x: &FpElemVar<F>,
27        x_to_11: &FpElemVar<F>,
28    ) -> Result<(), CircuitError> {
29        self.check_var_bound(x.components().0)?;
30        self.check_var_bound(x.components().1)?;
31        self.check_var_bound(x_to_11.components().0)?;
32        self.check_var_bound(x_to_11.components().1)?;
33
34        if T::MODULUS_BIT_SIZE >= F::MODULUS_BIT_SIZE {
35            return Err(CircuitError::NotSupported(format!(
36                "Target field size ({}) is greater than evaluation field size (P{})",
37                T::MODULUS_BIT_SIZE,
38                F::MODULUS_BIT_SIZE
39            )));
40        }
41
42        // x^11 = y
43        let y = self.non_native_power_11_gen::<T>(x)?;
44        self.enforce_equal(x_to_11.components().0, y.components().0)?;
45        self.enforce_equal(x_to_11.components().1, y.components().1)
46    }
47
48    /// generate a non-native circuit for the statement x^11 = y
49    ///
50    /// Input: variable representation of x over a target
51    /// field `T` whose order is less than F.
52    ///
53    /// Output: variable representation of x^11
54    ///
55    /// Cost: 5 mod_mul
56    pub fn non_native_power_11_gen<T: PrimeField>(
57        &mut self,
58        x: &FpElemVar<F>,
59    ) -> Result<FpElemVar<F>, CircuitError> {
60        // // checks already done by the caller
61        // if T::MODULUS_BIT_SIZE >= F::MODULUS_BIT_SIZE {
62        //     return Err(CircuitError::NotSupported(format!(
63        //         "Target field size ({}) is greater than evaluation field size (P{})",
64        //         T::MODULUS_BIT_SIZE,
65        //         F::MODULUS_BIT_SIZE
66        //     ))
67        //     .into());
68        // }
69
70        // convert T::MODULUS into an element in F
71        // Guaranteed without mod reduction since T::MODULUS_BIT_SIZE <
72        // F::MODULUS_BIT_SIZE
73        let t_modulus = F::from_le_bytes_mod_order(T::MODULUS.to_bytes_le().as_ref());
74
75        // convert t_modulus into FpElem
76        let m = x.param_m();
77        let two_power_m = Some(x.two_power_m());
78        let p = FpElem::new(&t_modulus, m, two_power_m)?;
79
80        // x^11 = y
81        let x2 = self.mod_mul(x, x, &p)?;
82        let x3 = self.mod_mul(&x2, x, &p)?;
83        let x4 = self.mod_mul(&x2, &x2, &p)?;
84        let x8 = self.mod_mul(&x4, &x4, &p)?;
85        self.mod_mul(&x3, &x8, &p)
86    }
87
88    /// generate a non-native circuit for the statement x^5 = y
89    ///
90    /// Input: variable representation of x over a target
91    /// field `T` whose order is less than F.
92    ///
93    /// Output: variable representation of x^5
94    ///
95    /// Cost: 3 mod_mul
96    pub fn non_native_power_5_gen<T: PrimeField>(
97        &mut self,
98        x: &FpElemVar<F>,
99    ) -> Result<FpElemVar<F>, CircuitError> {
100        // checks already done by the caller
101        if T::MODULUS_BIT_SIZE >= F::MODULUS_BIT_SIZE {
102            return Err(CircuitError::NotSupported(format!(
103                "Target field size ({}) is greater than evaluation field size (P{})",
104                T::MODULUS_BIT_SIZE,
105                F::MODULUS_BIT_SIZE
106            )));
107        }
108
109        // convert T::MODULUS into an element in F
110        // Guaranteed without mod reduction since T::MODULUS_BIT_SIZE <
111        // F::MODULUS_BIT_SIZE
112        let t_modulus = F::from_le_bytes_mod_order(T::MODULUS.to_bytes_le().as_ref());
113
114        // convert t_modulus into FpElem
115        let m = x.param_m();
116        let two_power_m = Some(x.two_power_m());
117        let p = FpElem::new(&t_modulus, m, two_power_m)?;
118
119        // x^5 = y
120        let x2 = self.mod_mul(x, x, &p)?;
121        let x3 = self.mod_mul(&x2, x, &p)?;
122        self.mod_mul(&x2, &x3, &p)
123    }
124
125    /// Input vector x and y, and a constant c,
126    /// generate a non-native circuit for the statement
127    ///     var_output = inner_product(x, y) + c
128    /// Input: variable representation of x, y, c over a target
129    /// field `T` whose order is less than F.
130    ///
131    /// Cost: 4 mod_mul_constant + 1 mod_add_internal
132    #[allow(clippy::many_single_char_names)]
133    pub fn non_native_linear_gen<T: PrimeField>(
134        &mut self,
135        x: &[FpElemVar<F>],
136        y: &[FpElem<F>],
137        c: &FpElem<F>,
138    ) -> Result<FpElemVar<F>, CircuitError> {
139        let m = c.param_m();
140        let two_power_m = Some(c.two_power_m());
141
142        // check the correctness of parameters
143        if T::MODULUS_BIT_SIZE >= F::MODULUS_BIT_SIZE {
144            return Err(CircuitError::NotSupported(format!(
145                "Target field size ({}) is greater than evaluation field size ({})",
146                T::MODULUS_BIT_SIZE,
147                F::MODULUS_BIT_SIZE
148            )));
149        }
150
151        if x.len() != y.len() {
152            return Err(CircuitError::ParameterError(format!(
153                "inputs x any y has different length ({} vs {})",
154                x.len(),
155                y.len()
156            )));
157        }
158        for e in x {
159            if m != e.param_m() {
160                return Err(CircuitError::ParameterError(format!(
161                    "inputs x any c has different m parameter ({} vs {})",
162                    e.param_m(),
163                    m
164                )));
165            }
166        }
167        for e in y {
168            if m != e.param_m() {
169                return Err(CircuitError::ParameterError(format!(
170                    "inputs y any c has different m parameter ({} vs {})",
171                    e.param_m(),
172                    m
173                )));
174            }
175        }
176
177        // convert T::MODULUS into an element in F
178        // Guaranteed without mod reduction since T::MODULUS_BIT_SIZE <
179        // F::MODULUS_BIT_SIZE
180        let t_modulus = F::from_le_bytes_mod_order(T::MODULUS.to_bytes_le().as_ref());
181
182        // convert t_modulus into FpElem
183        let p = FpElem::new(&t_modulus, m, two_power_m)?;
184
185        // generate the linear statement
186        // (\sum x[i] * y[i]) + c
187        let xiyi: Vec<FpElemVar<F>> = x
188            .iter()
189            .zip(y)
190            .map(|(xi, yi)| self.mod_mul_constant(xi, yi, &p))
191            .collect::<Result<Vec<FpElemVar<F>>, _>>()?;
192        let sum_xiyi = self.mod_add_vec(xiyi.as_ref(), &p)?;
193        self.mod_add_constant(&sum_xiyi, c, &p)
194    }
195}
196
197#[cfg(test)]
198mod test {
199    use super::*;
200    use crate::Variable;
201    use ark_bls12_377::Fq as Fq377;
202    use ark_ed_on_bls12_377::Fq as FqEd377;
203    use jf_utils::test_rng;
204
205    const RANGE_BIT_LEN_FOR_TEST: usize = 8;
206
207    #[test]
208    fn test_non_native_power_11_gen() -> Result<(), CircuitError> {
209        // use bls12-377 base field to prove rescue over jubjub377 base field
210        test_non_native_power_11_gen_helper::<FqEd377, Fq377>()
211    }
212
213    fn test_non_native_power_11_gen_helper<T: PrimeField, F: PrimeField>(
214    ) -> Result<(), CircuitError> {
215        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(RANGE_BIT_LEN_FOR_TEST);
216
217        let mut rng = test_rng();
218        let x_t = T::rand(&mut rng);
219        let y_t = x_t.pow([11]);
220        let x_p = F::from_le_bytes_mod_order(x_t.into_bigint().to_bytes_le().as_ref());
221        let y_p = F::from_le_bytes_mod_order(y_t.into_bigint().to_bytes_le().as_ref());
222
223        let m = (T::MODULUS_BIT_SIZE as usize / 2 / RANGE_BIT_LEN_FOR_TEST + 1)
224            * RANGE_BIT_LEN_FOR_TEST;
225
226        let x_var = circuit.create_variable(x_p)?;
227        let y_var = circuit.create_variable(y_p)?;
228
229        let x_split_vars = FpElemVar::new_unchecked(&mut circuit, x_var, m, None)?;
230        let x11_split_vars = circuit.non_native_power_11_gen::<T>(&x_split_vars)?;
231        let x11_var = x11_split_vars.convert_to_var(&mut circuit)?;
232
233        // good path
234        circuit.enforce_equal(x11_var, y_var)?;
235        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
236
237        // bad path: wrong witness should fail
238        let witness = circuit.witness(y_var)?;
239        *circuit.witness_mut(y_var) = F::rand(&mut rng);
240        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
241        *circuit.witness_mut(y_var) = witness;
242
243        // bad path: wrong value should fail
244        let y_wrong = F::rand(&mut rng);
245        let y_wrong_var = circuit.create_variable(y_wrong)?;
246        circuit.enforce_equal(x11_var, y_wrong_var)?;
247        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
248
249        Ok(())
250    }
251
252    #[test]
253    fn test_non_native_power_5_gen() -> Result<(), CircuitError> {
254        // use bls12-377 base field to prove rescue over jubjub377 base field
255        test_non_native_power_5_gen_helper::<FqEd377, Fq377>()
256    }
257
258    fn test_non_native_power_5_gen_helper<T: PrimeField, F: PrimeField>() -> Result<(), CircuitError>
259    {
260        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(RANGE_BIT_LEN_FOR_TEST);
261
262        let mut rng = test_rng();
263        let x_t = T::rand(&mut rng);
264        let y_t = x_t.pow([5]);
265        let x_p = F::from_le_bytes_mod_order(x_t.into_bigint().to_bytes_le().as_ref());
266        let y_p = F::from_le_bytes_mod_order(y_t.into_bigint().to_bytes_le().as_ref());
267
268        let m = (T::MODULUS_BIT_SIZE as usize / 2 / RANGE_BIT_LEN_FOR_TEST + 1)
269            * RANGE_BIT_LEN_FOR_TEST;
270
271        let x_var = circuit.create_variable(x_p)?;
272        let y_var = circuit.create_variable(y_p)?;
273
274        let x_split_vars = FpElemVar::new_unchecked(&mut circuit, x_var, m, None)?;
275        let x5_split_vars = circuit.non_native_power_5_gen::<T>(&x_split_vars)?;
276        let x5_var = x5_split_vars.convert_to_var(&mut circuit)?;
277
278        // good path
279        circuit.enforce_equal(x5_var, y_var)?;
280        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
281
282        // bad path: wrong witness should fail
283        let witness = circuit.witness(y_var)?;
284        *circuit.witness_mut(y_var) = F::rand(&mut rng);
285        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
286        *circuit.witness_mut(y_var) = witness;
287
288        // bad path: wrong value should fail
289        let y_wrong = F::rand(&mut rng);
290        let y_wrong_var = circuit.create_variable(y_wrong)?;
291        circuit.enforce_equal(x5_var, y_wrong_var)?;
292        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
293
294        Ok(())
295    }
296
297    #[test]
298    fn test_non_native_power_11_gate() -> Result<(), CircuitError> {
299        // use bls12-377 base field to prove rescue over bls scalar field
300        test_non_native_power_11_gate_helper::<FqEd377, Fq377>()
301    }
302
303    fn test_non_native_power_11_gate_helper<T: PrimeField, F: PrimeField>(
304    ) -> Result<(), CircuitError> {
305        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(RANGE_BIT_LEN_FOR_TEST);
306
307        let mut rng = test_rng();
308        let x_t = T::rand(&mut rng);
309        let y_t = x_t.pow([11]);
310        let x_p = F::from_le_bytes_mod_order(x_t.into_bigint().to_bytes_le().as_ref());
311        let y_p = F::from_le_bytes_mod_order(y_t.into_bigint().to_bytes_le().as_ref());
312
313        let m = (T::MODULUS_BIT_SIZE as usize / 2 / RANGE_BIT_LEN_FOR_TEST + 1)
314            * RANGE_BIT_LEN_FOR_TEST;
315
316        let x_var = circuit.create_variable(x_p)?;
317        let y_var = circuit.create_variable(y_p)?;
318
319        let x_split_vars = FpElemVar::new_unchecked(&mut circuit, x_var, m, None)?;
320        let y_split_vars =
321            FpElemVar::new_unchecked(&mut circuit, y_var, m, Some(x_split_vars.two_power_m()))?;
322
323        circuit.non_native_power_11_gate::<T>(&x_split_vars, &y_split_vars)?;
324
325        // good path
326        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
327
328        // bad path: wrong witness should fail
329        let witness = circuit.witness(y_var)?;
330        *circuit.witness_mut(y_var) = F::rand(&mut rng);
331        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
332        *circuit.witness_mut(y_var) = witness;
333
334        // bad path: wrong value should fail
335        let y_wrong = F::rand(&mut rng);
336        let y_wrong_var = circuit.create_variable(y_wrong)?;
337        let y_wrong_split_vars = FpElemVar::new_unchecked(
338            &mut circuit,
339            y_wrong_var,
340            m,
341            Some(x_split_vars.two_power_m()),
342        )?;
343        circuit.non_native_power_11_gate::<T>(&x_split_vars, &y_wrong_split_vars)?;
344        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
345
346        Ok(())
347    }
348
349    #[test]
350    fn test_non_native_linear_gate() -> Result<(), CircuitError> {
351        // use bls12-377 base field to prove rescue over jubjub377 base field
352        test_non_native_linear_gate_helper::<FqEd377, Fq377>()
353    }
354
355    fn test_non_native_linear_gate_helper<T: PrimeField, F: PrimeField>() -> Result<(), CircuitError>
356    {
357        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(RANGE_BIT_LEN_FOR_TEST);
358
359        let m = (T::MODULUS_BIT_SIZE as usize / 2 / RANGE_BIT_LEN_FOR_TEST + 1)
360            * RANGE_BIT_LEN_FOR_TEST;
361
362        let mut rng = test_rng();
363
364        let x_t: Vec<T> = (0..4).map(|_| T::rand(&mut rng)).collect();
365        let y_t: Vec<T> = (0..4).map(|_| T::rand(&mut rng)).collect();
366        let c_t = T::rand(&mut rng);
367        let mut res_t = c_t;
368        for (&xi, &yi) in x_t.iter().zip(y_t.iter()) {
369            res_t += xi * yi;
370        }
371        let res_p = F::from_le_bytes_mod_order(res_t.into_bigint().to_bytes_le().as_ref());
372
373        let x_p: Vec<F> = x_t
374            .iter()
375            .map(|x| F::from_le_bytes_mod_order(x.into_bigint().to_bytes_le().as_ref()))
376            .collect();
377        let y_p: Vec<F> = y_t
378            .iter()
379            .map(|y| F::from_le_bytes_mod_order(y.into_bigint().to_bytes_le().as_ref()))
380            .collect();
381        let c_p = F::from_le_bytes_mod_order(c_t.into_bigint().to_bytes_le().as_ref());
382
383        let x_vars: Vec<Variable> = x_p
384            .iter()
385            .map(|x| circuit.create_variable(*x))
386            .collect::<Result<Vec<Variable>, _>>()?;
387
388        let x_split_vars: Vec<FpElemVar<F>> = x_vars
389            .iter()
390            .map(|x| FpElemVar::new_unchecked(&mut circuit, *x, m, None))
391            .collect::<Result<Vec<FpElemVar<F>>, _>>()?;
392        let y_split: Vec<FpElem<F>> = y_p
393            .iter()
394            .map(|y| FpElem::new(y, m, Some(x_split_vars[0].two_power_m())))
395            .collect::<Result<Vec<FpElem<F>>, _>>()?;
396        let c_split = FpElem::new(&c_p, m, Some(x_split_vars[0].two_power_m()))?;
397
398        // check the result is correct
399        let res_split_var =
400            circuit.non_native_linear_gen::<T>(&x_split_vars, &y_split, &c_split)?;
401        let res_var = res_split_var.convert_to_var(&mut circuit)?;
402        assert_eq!(circuit.witness(res_var)?, res_p);
403
404        // good path: the circuit is satisfied
405        let res_var2 = circuit.create_variable(res_p)?;
406        circuit.enforce_equal(res_var, res_var2)?;
407        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
408
409        // bad path: wrong witness should fail
410        let witness = circuit.witness(x_vars[0])?;
411        *circuit.witness_mut(x_vars[0]) = F::rand(&mut rng);
412        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
413        *circuit.witness_mut(x_vars[0]) = witness;
414
415        // bad path: wrong value should fail
416        let res_var3 = F::rand(&mut rng);
417        let res_var3 = circuit.create_variable(res_var3)?;
418        circuit.enforce_equal(res_var, res_var3)?;
419        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
420
421        Ok(())
422    }
423}
jf_relation/gadgets/ultraplonk/non_native_gates.rs

jf_relation/gadgets/ultraplonk/
non_native_gates.rs
