1use algebra::{
  2    curves::mnt4::{
  3        g2::{AteAdditionCoefficients, AteDoubleCoefficients},
  4        G1Prepared, G2Prepared, MNT4Parameters,
  5    },
  6    Field,
  7};
  8use r1cs_core::{ConstraintSystem, SynthesisError};
  9
 10use crate::{
 11    fields::{fp::FpGadget, fp2::Fp2Gadget, FieldGadget},
 12    groups::curves::short_weierstrass::AffineGadget,
 13    pairing::mnt4::PairingGadget,
 14    prelude::*,
 15    Vec,
 16};
 17
 18pub type G1Gadget<P> = AffineGadget<
 19    <P as MNT4Parameters>::G1Parameters,
 20    <P as MNT4Parameters>::Fp,
 21    FpGadget<<P as MNT4Parameters>::Fp>,
 22>;
 23
 24pub type G2Gadget<P> =
 25    AffineGadget<<P as MNT4Parameters>::G2Parameters, <P as MNT4Parameters>::Fp, Fp2G<P>>;
 26
 27#[derive(Derivative)]
 28#[derivative(Clone(bound = "P: MNT4Parameters"), Debug(bound = "P: MNT4Parameters"))]
 29pub struct G1PreparedGadget<P: MNT4Parameters> {
 30    pub x: FpGadget<P::Fp>,
 31    pub y: FpGadget<P::Fp>,
 32    pub x_twist: Fp2Gadget<P::Fp2Params, P::Fp>,
 33    pub y_twist: Fp2Gadget<P::Fp2Params, P::Fp>,
 34}
 35
 36impl<P: MNT4Parameters> G1PreparedGadget<P> {
 37    pub fn get_value(&self) -> Option<G1Prepared<P>> {
 38        match (
 39            self.x.get_value(),
 40            self.y.get_value(),
 41            self.x_twist.get_value(),
 42            self.y_twist.get_value(),
 43        ) {
 44            (Some(x), Some(y), Some(x_twist), Some(y_twist)) => Some(G1Prepared {
 45                x,
 46                y,
 47                x_twist,
 48                y_twist,
 49            }),
 50            _ => None,
 51        }
 52    }
 53
 54    pub fn from_affine<CS: ConstraintSystem<P::Fp>>(
 55        mut cs: CS,
 56        q: &G1Gadget<P>,
 57    ) -> Result<Self, SynthesisError> {
 58        let x_twist = Fp2Gadget::new(
 59            q.x.mul_by_constant(cs.ns(|| "g1.x * twist.c0"), &P::TWIST.c0)?,
 60            q.x.mul_by_constant(cs.ns(|| "g1.x * twist.c1"), &P::TWIST.c1)?,
 61        );
 62        let y_twist = Fp2Gadget::new(
 63            q.y.mul_by_constant(cs.ns(|| "g1.y * twist.c0"), &P::TWIST.c0)?,
 64            q.y.mul_by_constant(cs.ns(|| "g1.y * twist.c1"), &P::TWIST.c1)?,
 65        );
 66        Ok(G1PreparedGadget {
 67            x: q.x.clone(),
 68            y: q.y.clone(),
 69            x_twist,
 70            y_twist,
 71        })
 72    }
 73}
 74
 75impl<P: MNT4Parameters> ToBytesGadget<P::Fp> for G1PreparedGadget<P> {
 76    #[inline]
 77    fn to_bytes<CS: ConstraintSystem<P::Fp>>(
 78        &self,
 79        mut cs: CS,
 80    ) -> Result<Vec<UInt8>, SynthesisError> {
 81        let mut x = self.x.to_bytes(&mut cs.ns(|| "x to bytes"))?;
 82        let mut y = self.y.to_bytes(&mut cs.ns(|| "y to bytes"))?;
 83        let mut x_twist = self.x_twist.to_bytes(&mut cs.ns(|| "x_twist to bytes"))?;
 84        let mut y_twist = self.y_twist.to_bytes(&mut cs.ns(|| "y_twist to bytes"))?;
 85
 86        x.append(&mut y);
 87        x.append(&mut x_twist);
 88        x.append(&mut y_twist);
 89        Ok(x)
 90    }
 91
 92    fn to_non_unique_bytes<CS: ConstraintSystem<P::Fp>>(
 93        &self,
 94        mut cs: CS,
 95    ) -> Result<Vec<UInt8>, SynthesisError> {
 96        let mut x = self.x.to_non_unique_bytes(&mut cs.ns(|| "x to bytes"))?;
 97        let mut y = self.y.to_non_unique_bytes(&mut cs.ns(|| "y to bytes"))?;
 98        let mut x_twist = self
 99            .x_twist
100            .to_non_unique_bytes(&mut cs.ns(|| "x_twist to bytes"))?;
101        let mut y_twist = self
102            .y_twist
103            .to_non_unique_bytes(&mut cs.ns(|| "y_twist to bytes"))?;
104
105        x.append(&mut y);
106        x.append(&mut x_twist);
107        x.append(&mut y_twist);
108        Ok(x)
109    }
110}
111
112type Fp2G<P> = Fp2Gadget<<P as MNT4Parameters>::Fp2Params, <P as MNT4Parameters>::Fp>;
113#[derive(Derivative)]
114#[derivative(Clone(bound = "P: MNT4Parameters"), Debug(bound = "P: MNT4Parameters"))]
115pub struct G2PreparedGadget<P: MNT4Parameters> {
116    pub x: Fp2Gadget<P::Fp2Params, P::Fp>,
117    pub y: Fp2Gadget<P::Fp2Params, P::Fp>,
118    pub x_over_twist: Fp2Gadget<P::Fp2Params, P::Fp>,
119    pub y_over_twist: Fp2Gadget<P::Fp2Params, P::Fp>,
120    pub double_coefficients: Vec<AteDoubleCoefficientsGadget<P>>,
121    pub addition_coefficients: Vec<AteAdditionCoefficientsGadget<P>>,
122}
123
124impl<P: MNT4Parameters> ToBytesGadget<P::Fp> for G2PreparedGadget<P> {
125    #[inline]
126    fn to_bytes<CS: ConstraintSystem<P::Fp>>(
127        &self,
128        mut cs: CS,
129    ) -> Result<Vec<UInt8>, SynthesisError> {
130        let mut x = self.x.to_bytes(&mut cs.ns(|| "x to bytes"))?;
131        let mut y = self.y.to_bytes(&mut cs.ns(|| "y to bytes"))?;
132        let mut x_over_twist = self
133            .x_over_twist
134            .to_bytes(&mut cs.ns(|| "x_over_twist to bytes"))?;
135        let mut y_over_twist = self
136            .y_over_twist
137            .to_bytes(&mut cs.ns(|| "y_over_twist to bytes"))?;
138
139        x.append(&mut y);
140        x.append(&mut x_over_twist);
141        x.append(&mut y_over_twist);
142
143        for (i, coeff) in self.double_coefficients.iter().enumerate() {
144            x.extend_from_slice(&coeff.to_bytes(cs.ns(|| format!("double_coefficients {}", i)))?);
145        }
146        for (i, coeff) in self.addition_coefficients.iter().enumerate() {
147            x.extend_from_slice(&coeff.to_bytes(cs.ns(|| format!("addition_coefficients {}", i)))?);
148        }
149        Ok(x)
150    }
151
152    fn to_non_unique_bytes<CS: ConstraintSystem<P::Fp>>(
153        &self,
154        mut cs: CS,
155    ) -> Result<Vec<UInt8>, SynthesisError> {
156        let mut x = self.x.to_non_unique_bytes(&mut cs.ns(|| "x to bytes"))?;
157        let mut y = self.y.to_non_unique_bytes(&mut cs.ns(|| "y to bytes"))?;
158        let mut x_over_twist = self
159            .x_over_twist
160            .to_non_unique_bytes(&mut cs.ns(|| "x_over_twist to bytes"))?;
161        let mut y_over_twist = self
162            .y_over_twist
163            .to_non_unique_bytes(&mut cs.ns(|| "y_over_twist to bytes"))?;
164
165        x.append(&mut y);
166        x.append(&mut x_over_twist);
167        x.append(&mut y_over_twist);
168
169        for (i, coeff) in self.double_coefficients.iter().enumerate() {
170            x.extend_from_slice(
171                &coeff.to_non_unique_bytes(cs.ns(|| format!("double_coefficients {}", i)))?,
172            );
173        }
174        for (i, coeff) in self.addition_coefficients.iter().enumerate() {
175            x.extend_from_slice(
176                &coeff.to_non_unique_bytes(cs.ns(|| format!("addition_coefficients {}", i)))?,
177            );
178        }
179        Ok(x)
180    }
181}
182
183impl<P: MNT4Parameters> G2PreparedGadget<P> {
184    pub fn get_value(&self) -> Option<G2Prepared<P>> {
185        match (
186            self.x.get_value(),
187            self.y.get_value(),
188            self.x_over_twist.get_value(),
189            self.y_over_twist.get_value(),
190            self.double_coefficients
191                .iter()
192                .map(|coeff| coeff.get_value())
193                .collect::<Option<Vec<AteDoubleCoefficients<P>>>>(),
194            self.addition_coefficients
195                .iter()
196                .map(|coeff| coeff.get_value())
197                .collect::<Option<Vec<AteAdditionCoefficients<P>>>>(),
198        ) {
199            (
200                Some(x),
201                Some(y),
202                Some(x_over_twist),
203                Some(y_over_twist),
204                Some(double_coefficients),
205                Some(addition_coefficients),
206            ) => Some(G2Prepared {
207                x,
208                y,
209                x_over_twist,
210                y_over_twist,
211                double_coefficients,
212                addition_coefficients,
213            }),
214            _ => None,
215        }
216    }
217
218    pub fn from_affine<CS: ConstraintSystem<P::Fp>>(
219        mut cs: CS,
220        q: &G2Gadget<P>,
221    ) -> Result<Self, SynthesisError> {
222        let twist_inv = P::TWIST.inverse().unwrap();
223
224        let mut g2p = G2PreparedGadget {
225            x: q.x.clone(),
226            y: q.y.clone(),
227            x_over_twist: q.x.mul_by_constant(cs.ns(|| "x over twist"), &twist_inv)?,
228            y_over_twist: q.y.mul_by_constant(cs.ns(|| "y over twist"), &twist_inv)?,
229            double_coefficients: vec![],
230            addition_coefficients: vec![],
231        };
232
233        let fp2_one = Fp2G::<P>::one(cs.ns(|| "one"))?;
234        let mut r = G2ProjectiveExtendedGadget {
235            x: q.x.clone(),
236            y: q.y.clone(),
237            z: fp2_one.clone(),
238            t: fp2_one,
239        };
240
241        for (idx, value) in P::ATE_LOOP_COUNT.iter().rev().enumerate() {
242            let mut tmp = *value;
243            let skip_extraneous_bits = 64 - value.leading_zeros();
244            let mut v = Vec::with_capacity(16);
245            for i in 0..64 {
246                if idx == 0 && (i == 0 || i >= skip_extraneous_bits) {
247                    continue;
248                }
249                v.push(tmp & 1 == 1);
250                tmp >>= 1;
251            }
252
253            let mut cs = cs.ns(|| format!("ate loop iteration {}", idx));
254
255            for (j, bit) in v.iter().rev().enumerate() {
256                let (r2, coeff) = PairingGadget::<P>::doubling_step_for_flipped_miller_loop(
257                    cs.ns(|| format!("doubling step {}", j)),
258                    &r,
259                )?;
260                g2p.double_coefficients.push(coeff);
261                r = r2;
262
263                if *bit {
264                    let (r2, coeff) =
265                        PairingGadget::<P>::mixed_addition_step_for_flipped_miller_loop(
266                            cs.ns(|| format!("mixed addition step {}", j)),
267                            &q.x,
268                            &q.y,
269                            &r,
270                        )?;
271                    g2p.addition_coefficients.push(coeff);
272                    r = r2;
273                }
274
275                tmp >>= 1;
276            }
277        }
278
279        if P::ATE_IS_LOOP_COUNT_NEG {
280            let rz_inv = r.z.inverse(cs.ns(|| "inverse r.z"))?;
281            let rz2_inv = rz_inv.square(cs.ns(|| "rz_inv^2"))?;
282            let rz3_inv = rz_inv.mul(cs.ns(|| "rz_inv * rz_inv^2"), &rz2_inv)?;
283
284            let minus_r_affine_x = r.x.mul(cs.ns(|| "r.x * rz2_inv"), &rz2_inv)?;
285            let minus_r_affine_y =
286                r.y.negate(cs.ns(|| "-r.y"))?
287                    .mul(cs.ns(|| "-r.y * rz3_inv"), &rz3_inv)?;
288
289            let add_result = PairingGadget::<P>::mixed_addition_step_for_flipped_miller_loop(
290                cs.ns(|| "mixed_addition step"),
291                &minus_r_affine_x,
292                &minus_r_affine_y,
293                &r,
294            )?;
295            g2p.addition_coefficients.push(add_result.1);
296        }
297
298        Ok(g2p)
299    }
300}
301
302#[derive(Derivative)]
303#[derivative(Clone(bound = "P: MNT4Parameters"), Debug(bound = "P: MNT4Parameters"))]
304pub struct AteDoubleCoefficientsGadget<P: MNT4Parameters> {
305    pub c_h: Fp2Gadget<P::Fp2Params, P::Fp>,
306    pub c_4c: Fp2Gadget<P::Fp2Params, P::Fp>,
307    pub c_j: Fp2Gadget<P::Fp2Params, P::Fp>,
308    pub c_l: Fp2Gadget<P::Fp2Params, P::Fp>,
309}
310
311impl<P: MNT4Parameters> ToBytesGadget<P::Fp> for AteDoubleCoefficientsGadget<P> {
312    #[inline]
313    fn to_bytes<CS: ConstraintSystem<P::Fp>>(
314        &self,
315        mut cs: CS,
316    ) -> Result<Vec<UInt8>, SynthesisError> {
317        let mut c_h = self.c_h.to_bytes(&mut cs.ns(|| "c_h to bytes"))?;
318        let mut c_4c = self.c_4c.to_bytes(&mut cs.ns(|| "c_4c to bytes"))?;
319        let mut c_j = self.c_j.to_bytes(&mut cs.ns(|| "c_j to bytes"))?;
320        let mut c_l = self.c_l.to_bytes(&mut cs.ns(|| "c_l to bytes"))?;
321
322        c_h.append(&mut c_4c);
323        c_h.append(&mut c_j);
324        c_h.append(&mut c_l);
325        Ok(c_h)
326    }
327
328    fn to_non_unique_bytes<CS: ConstraintSystem<P::Fp>>(
329        &self,
330        mut cs: CS,
331    ) -> Result<Vec<UInt8>, SynthesisError> {
332        let mut c_h = self
333            .c_h
334            .to_non_unique_bytes(&mut cs.ns(|| "c_h to bytes"))?;
335        let mut c_4c = self
336            .c_4c
337            .to_non_unique_bytes(&mut cs.ns(|| "c_4c to bytes"))?;
338        let mut c_j = self
339            .c_j
340            .to_non_unique_bytes(&mut cs.ns(|| "c_j to bytes"))?;
341        let mut c_l = self
342            .c_l
343            .to_non_unique_bytes(&mut cs.ns(|| "c_l to bytes"))?;
344
345        c_h.append(&mut c_4c);
346        c_h.append(&mut c_j);
347        c_h.append(&mut c_l);
348        Ok(c_h)
349    }
350}
351
352impl<P: MNT4Parameters> AteDoubleCoefficientsGadget<P> {
353    pub fn get_value(&self) -> Option<AteDoubleCoefficients<P>> {
354        match (
355            self.c_h.get_value(),
356            self.c_4c.get_value(),
357            self.c_j.get_value(),
358            self.c_l.get_value(),
359        ) {
360            (Some(c_h), Some(c_4c), Some(c_j), Some(c_l)) => Some(AteDoubleCoefficients {
361                c_h,
362                c_4c,
363                c_j,
364                c_l,
365            }),
366            _ => None,
367        }
368    }
369}
370
371#[derive(Derivative)]
372#[derivative(Clone(bound = "P: MNT4Parameters"), Debug(bound = "P: MNT4Parameters"))]
373pub struct AteAdditionCoefficientsGadget<P: MNT4Parameters> {
374    pub c_l1: Fp2Gadget<P::Fp2Params, P::Fp>,
375    pub c_rz: Fp2Gadget<P::Fp2Params, P::Fp>,
376}
377
378impl<P: MNT4Parameters> ToBytesGadget<P::Fp> for AteAdditionCoefficientsGadget<P> {
379    #[inline]
380    fn to_bytes<CS: ConstraintSystem<P::Fp>>(
381        &self,
382        mut cs: CS,
383    ) -> Result<Vec<UInt8>, SynthesisError> {
384        let mut c_l1 = self.c_l1.to_bytes(&mut cs.ns(|| "c_l1 to bytes"))?;
385        let mut c_rz = self.c_rz.to_bytes(&mut cs.ns(|| "c_rz to bytes"))?;
386
387        c_l1.append(&mut c_rz);
388        Ok(c_l1)
389    }
390
391    fn to_non_unique_bytes<CS: ConstraintSystem<P::Fp>>(
392        &self,
393        mut cs: CS,
394    ) -> Result<Vec<UInt8>, SynthesisError> {
395        let mut c_l1 = self
396            .c_l1
397            .to_non_unique_bytes(&mut cs.ns(|| "c_l1 to bytes"))?;
398        let mut c_rz = self
399            .c_rz
400            .to_non_unique_bytes(&mut cs.ns(|| "c_rz to bytes"))?;
401
402        c_l1.append(&mut c_rz);
403        Ok(c_l1)
404    }
405}
406
407impl<P: MNT4Parameters> AteAdditionCoefficientsGadget<P> {
408    pub fn get_value(&self) -> Option<AteAdditionCoefficients<P>> {
409        match (self.c_l1.get_value(), self.c_rz.get_value()) {
410            (Some(c_l1), Some(c_rz)) => Some(AteAdditionCoefficients { c_l1, c_rz }),
411            _ => None,
412        }
413    }
414}
415
416pub struct G2ProjectiveExtendedGadget<P: MNT4Parameters> {
417    pub x: Fp2Gadget<P::Fp2Params, P::Fp>,
418    pub y: Fp2Gadget<P::Fp2Params, P::Fp>,
419    pub z: Fp2Gadget<P::Fp2Params, P::Fp>,
420    pub t: Fp2Gadget<P::Fp2Params, P::Fp>,
421}