jf_relation/gadgets/ecc/emulated/
twisted_edwards.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//! Twisted Edwards curve point addition
8
9use crate::{
10    gadgets::{ecc::TEPoint, EmulatedVariable, EmulationConfig},
11    BoolVar, Circuit, CircuitError, PlonkCircuit,
12};
13use ark_ff::PrimeField;
14
15/// The variable represents an TE point in the emulated field.
16#[derive(Debug, Clone)]
17pub struct EmulatedTEPointVariable<E: PrimeField>(pub EmulatedVariable<E>, pub EmulatedVariable<E>);
18
19impl<F: PrimeField> PlonkCircuit<F> {
20    /// Return the witness point
21    pub fn emulated_te_point_witness<E: EmulationConfig<F>>(
22        &self,
23        point_var: &EmulatedTEPointVariable<E>,
24    ) -> Result<TEPoint<E>, CircuitError> {
25        let x = self.emulated_witness(&point_var.0)?;
26        let y = self.emulated_witness(&point_var.1)?;
27        Ok(TEPoint(x, y))
28    }
29
30    /// Add a new emulated EC point (as witness)
31    pub fn create_emulated_te_point_variable<E: EmulationConfig<F>>(
32        &mut self,
33        p: TEPoint<E>,
34    ) -> Result<EmulatedTEPointVariable<E>, CircuitError> {
35        let x = self.create_emulated_variable(p.0)?;
36        let y = self.create_emulated_variable(p.1)?;
37        Ok(EmulatedTEPointVariable(x, y))
38    }
39
40    /// Add a new constant emulated EC point
41    pub fn create_constant_emulated_te_point_variable<E: EmulationConfig<F>>(
42        &mut self,
43        p: TEPoint<E>,
44    ) -> Result<EmulatedTEPointVariable<E>, CircuitError> {
45        let x = self.create_constant_emulated_variable(p.0)?;
46        let y = self.create_constant_emulated_variable(p.1)?;
47        Ok(EmulatedTEPointVariable(x, y))
48    }
49
50    /// Add a new public emulated EC point
51    pub fn create_public_emulated_te_point_variable<E: EmulationConfig<F>>(
52        &mut self,
53        p: TEPoint<E>,
54    ) -> Result<EmulatedTEPointVariable<E>, CircuitError> {
55        let x = self.create_public_emulated_variable(p.0)?;
56        let y = self.create_public_emulated_variable(p.1)?;
57        Ok(EmulatedTEPointVariable(x, y))
58    }
59
60    /// Obtain an emulated point variable of the conditional selection from 2
61    /// emulated point variables. `b` is a boolean variable that indicates
62    /// selection of P_b from (P0, P1).
63    /// Return error if invalid input parameters are provided.
64    pub fn binary_emulated_te_point_vars_select<E: EmulationConfig<F>>(
65        &mut self,
66        b: BoolVar,
67        p0: &EmulatedTEPointVariable<E>,
68        p1: &EmulatedTEPointVariable<E>,
69    ) -> Result<EmulatedTEPointVariable<E>, CircuitError> {
70        let select_x = self.conditional_select_emulated(b, &p0.0, &p1.0)?;
71        let select_y = self.conditional_select_emulated(b, &p0.1, &p1.1)?;
72
73        Ok(EmulatedTEPointVariable::<E>(select_x, select_y))
74    }
75
76    /// Constrain two emulated point variables to be the same.
77    /// Return error if the input point variables are invalid.
78    pub fn enforce_emulated_te_point_equal<E: EmulationConfig<F>>(
79        &mut self,
80        p0: &EmulatedTEPointVariable<E>,
81        p1: &EmulatedTEPointVariable<E>,
82    ) -> Result<(), CircuitError> {
83        self.enforce_emulated_var_equal(&p0.0, &p1.0)?;
84        self.enforce_emulated_var_equal(&p0.1, &p1.1)?;
85        Ok(())
86    }
87
88    /// Obtain a bool variable representing whether two input emulated point
89    /// variables are equal. Return error if variables are invalid.
90    pub fn is_emulated_te_point_equal<E: EmulationConfig<F>>(
91        &mut self,
92        p0: &EmulatedTEPointVariable<E>,
93        p1: &EmulatedTEPointVariable<E>,
94    ) -> Result<BoolVar, CircuitError> {
95        let mut r0 = self.is_emulated_var_equal(&p0.0, &p1.0)?;
96        let r1 = self.is_emulated_var_equal(&p0.1, &p1.1)?;
97        r0.0 = self.mul(r0.0, r1.0)?;
98        Ok(r0)
99    }
100
101    /// Constrain variable `p2` to be the point addition of `p0` and
102    /// `p1` over an elliptic curve.
103    pub fn emulated_te_ecc_add_gate<E: EmulationConfig<F>>(
104        &mut self,
105        p0: &EmulatedTEPointVariable<E>,
106        p1: &EmulatedTEPointVariable<E>,
107        p2: &EmulatedTEPointVariable<E>,
108        d: E,
109    ) -> Result<(), CircuitError> {
110        let x0y1 = self.emulated_mul(&p0.0, &p1.1)?;
111        let x1y0 = self.emulated_mul(&p1.0, &p0.1)?;
112        let x0x1 = self.emulated_mul(&p0.0, &p1.0)?;
113        let y0y1 = self.emulated_mul(&p0.1, &p1.1)?;
114        let x0x1y0y1 = self.emulated_mul(&x0x1, &y0y1)?;
115        let dx0x1y0y1 = self.emulated_mul_constant(&x0x1y0y1, d)?;
116
117        // checking that x2 = x0y1 + x1y0 - dx0y0x1y1x2
118        // t1 = x0y1 + x1y0
119        let t1 = self.emulated_add(&x0y1, &x1y0)?;
120        // t2 = d x0 y0 x1 y1 x2
121        let t2 = self.emulated_mul(&dx0x1y0y1, &p2.0)?;
122        self.emulated_add_gate(&p2.0, &t2, &t1)?;
123
124        // checking that y2 = x0x1 + y0y1 + dx0y0x1y1y2
125        // t1 = x0x1 + y0y1
126        let t1 = self.emulated_add(&x0x1, &y0y1)?;
127        let t2 = self.emulated_mul(&dx0x1y0y1, &p2.1)?;
128        self.emulated_add_gate(&t1, &t2, &p2.1)
129    }
130
131    /// Obtain a variable to the point addition result of `a` + `b`
132    pub fn emulated_te_ecc_add<E: EmulationConfig<F>>(
133        &mut self,
134        p0: &EmulatedTEPointVariable<E>,
135        p1: &EmulatedTEPointVariable<E>,
136        d: E,
137    ) -> Result<EmulatedTEPointVariable<E>, CircuitError> {
138        let x0 = self.emulated_witness(&p0.0)?;
139        let y0 = self.emulated_witness(&p0.1)?;
140        let x1 = self.emulated_witness(&p1.0)?;
141        let y1 = self.emulated_witness(&p1.1)?;
142
143        let t1 = x0 * y1;
144        let t2 = x1 * y0;
145        let dx0x1y0y1 = d * t1 * t2;
146
147        let x2 = (t1 + t2) / (E::one() + dx0x1y0y1);
148        let y2 = (x0 * x1 + y0 * y1) / (E::one() - dx0x1y0y1);
149        let p2 = self.create_emulated_te_point_variable(TEPoint(x2, y2))?;
150        self.emulated_te_ecc_add_gate(p0, p1, &p2, d)?;
151        Ok(p2)
152    }
153}
154
155#[cfg(test)]
156mod tests {
157    use crate::{
158        gadgets::{
159            ecc::{conversion::*, TEPoint},
160            EmulationConfig,
161        },
162        Circuit, PlonkCircuit,
163    };
164    use ark_bls12_377::{g1::Config as Param377, Fq as Fq377};
165    use ark_bn254::Fr as Fr254;
166    use ark_ec::{
167        short_weierstrass::{Projective, SWCurveConfig},
168        CurveGroup, Group,
169    };
170    use ark_ff::{MontFp, PrimeField};
171    use ark_std::{UniformRand, Zero};
172
173    #[test]
174    fn test_emulated_te_point_addition() {
175        let d : Fq377 = MontFp!("122268283598675559488486339158635529096981886914877139579534153582033676785385790730042363341236035746924960903179");
176        test_emulated_te_point_addition_helper::<Fq377, Fr254, Param377>(d);
177    }
178
179    fn test_emulated_te_point_addition_helper<E, F, P>(d: E)
180    where
181        E: EmulationConfig<F> + SWToTEConParam,
182        F: PrimeField,
183        P: SWCurveConfig<BaseField = E>,
184    {
185        let mut rng = jf_utils::test_rng();
186        let neutral = Projective::<P>::zero().into_affine();
187        let p1 = Projective::<P>::rand(&mut rng).into_affine();
188        let p2 = Projective::<P>::rand(&mut rng).into_affine();
189        let expected: TEPoint<E> = (p1 + p2).into_affine().into();
190        let wrong_result: TEPoint<E> = (p1 + p2 + Projective::<P>::generator())
191            .into_affine()
192            .into();
193        let p1: TEPoint<E> = p1.into();
194        let p2: TEPoint<E> = p2.into();
195
196        let mut circuit = PlonkCircuit::<F>::new_turbo_plonk();
197
198        let var_p1 = circuit.create_emulated_te_point_variable(p1).unwrap();
199        let var_p2 = circuit.create_emulated_te_point_variable(p2).unwrap();
200        let var_result = circuit.emulated_te_ecc_add(&var_p1, &var_p2, d).unwrap();
201        assert_eq!(
202            circuit.emulated_te_point_witness(&var_result).unwrap(),
203            expected
204        );
205        let var_neutral = circuit
206            .create_emulated_te_point_variable(neutral.into())
207            .unwrap();
208        let var_neutral_result = circuit
209            .emulated_te_ecc_add(&var_p1, &var_neutral, d)
210            .unwrap();
211        assert_eq!(
212            circuit
213                .emulated_te_point_witness(&var_neutral_result)
214                .unwrap(),
215            p1
216        );
217        let var_neutral_result = circuit
218            .emulated_te_ecc_add(&var_neutral, &var_p1, d)
219            .unwrap();
220        assert_eq!(
221            circuit
222                .emulated_te_point_witness(&var_neutral_result)
223                .unwrap(),
224            p1
225        );
226        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
227
228        let var_wrong_result = circuit
229            .create_emulated_te_point_variable(wrong_result)
230            .unwrap();
231        circuit
232            .emulated_te_ecc_add_gate(&var_p1, &var_p2, &var_wrong_result, d)
233            .unwrap();
234        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
235    }
236
237    #[test]
238    fn test_emulated_point_select() {
239        test_emulated_point_select_helper::<Fq377, Fr254, Param377>();
240    }
241
242    fn test_emulated_point_select_helper<E, F, P>()
243    where
244        E: EmulationConfig<F> + SWToTEConParam,
245        F: PrimeField,
246        P: SWCurveConfig<BaseField = E>,
247    {
248        let mut rng = jf_utils::test_rng();
249        let p1 = Projective::<P>::rand(&mut rng).into_affine();
250        let p2 = Projective::<P>::rand(&mut rng).into_affine();
251
252        let mut circuit = PlonkCircuit::<F>::new_turbo_plonk();
253
254        let var_p1 = circuit
255            .create_emulated_te_point_variable(p1.into())
256            .unwrap();
257        let var_p2 = circuit
258            .create_emulated_te_point_variable(p2.into())
259            .unwrap();
260        let b = circuit.create_boolean_variable(true).unwrap();
261        let var_p3 = circuit
262            .binary_emulated_te_point_vars_select(b, &var_p1, &var_p2)
263            .unwrap();
264        assert_eq!(
265            circuit.emulated_te_point_witness(&var_p3).unwrap(),
266            p2.into()
267        );
268        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
269        *circuit.witness_mut(var_p3.0 .0[0]) = F::zero();
270        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
271    }
272
273    #[test]
274    fn test_enforce_emulated_point_eq() {
275        test_enforce_emulated_point_eq_helper::<Fq377, Fr254, Param377>();
276    }
277
278    fn test_enforce_emulated_point_eq_helper<E, F, P>()
279    where
280        E: EmulationConfig<F> + SWToTEConParam,
281        F: PrimeField,
282        P: SWCurveConfig<BaseField = E>,
283    {
284        let mut rng = jf_utils::test_rng();
285        let p1 = Projective::<P>::rand(&mut rng).into_affine();
286        let p2 = (p1 + Projective::<P>::generator()).into_affine();
287
288        let mut circuit = PlonkCircuit::<F>::new_turbo_plonk();
289
290        let var_p1 = circuit
291            .create_emulated_te_point_variable(p1.into())
292            .unwrap();
293        let var_p2 = circuit
294            .create_emulated_te_point_variable(p2.into())
295            .unwrap();
296        let var_p3 = circuit
297            .create_emulated_te_point_variable(p1.into())
298            .unwrap();
299        circuit
300            .enforce_emulated_te_point_equal(&var_p1, &var_p3)
301            .unwrap();
302        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
303        circuit
304            .enforce_emulated_te_point_equal(&var_p1, &var_p2)
305            .unwrap();
306        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
307    }
308}
jf_relation/gadgets/ecc/emulated/twisted_edwards.rs

jf_relation/gadgets/ecc/emulated/
twisted_edwards.rs
