1use r1cs_core::{ConstraintSystem, SynthesisError};
  2
  3use super::PairingGadget as PG;
  4
  5use crate::{
  6    fields::{fp::FpGadget, fp12::Fp12Gadget, fp2::Fp2Gadget, FieldGadget},
  7    groups::bls12::{G1Gadget, G1PreparedGadget, G2Gadget, G2PreparedGadget},
  8};
  9use algebra::{
 10    curves::{
 11        bls12::{
 12            Bls12, Bls12Parameters, G1Affine, G1Prepared, G1Projective, G2Affine, G2Prepared,
 13            G2Projective, TwistType,
 14        },
 15        models::ModelParameters,
 16        PairingCurve,
 17    },
 18    fields::{fp12_2over3over2::Fp12, BitIterator},
 19};
 20use std::marker::PhantomData;
 21
 22pub mod bls12_377;
 23
 24pub struct PairingGadget<P: Bls12Parameters>(PhantomData<P>);
 25
 26type Fp2G<P> = Fp2Gadget<<P as Bls12Parameters>::Fp2Params, <P as Bls12Parameters>::Fp>;
 27
 28impl<P: Bls12Parameters> PairingGadget<P> {
 29    // Evaluate the line function at point p.
 30    fn ell<CS: ConstraintSystem<P::Fp>>(
 31        mut cs: CS,
 32        f: &mut Fp12Gadget<P::Fp12Params, P::Fp>,
 33        coeffs: &(Fp2G<P>, Fp2G<P>),
 34        p: &G1Gadget<P>,
 35    ) -> Result<(), SynthesisError> {
 36        let zero = FpGadget::<P::Fp>::zero(cs.ns(|| "fpg zero"))?;
 37
 38        match P::TWIST_TYPE {
 39            TwistType::M => {
 40                let c0 = coeffs.0.clone();
 41                let mut c1 = coeffs.1.clone();
 42                let c2 = Fp2G::<P>::new(p.y.clone(), zero.clone());
 43
 44                c1.c0 = c1.c0.mul(cs.ns(|| "mul c1.c0"), &p.x)?;
 45                c1.c1 = c1.c1.mul(cs.ns(|| "mul c1.c1"), &p.x)?;
 46                *f = f.mul_by_014(cs.ns(|| "sparse mul f"), &c0, &c1, &c2)?;
 47                Ok(())
 48            },
 49            TwistType::D => {
 50                let c0 = Fp2G::<P>::new(p.y.clone(), zero.clone());
 51                let mut c1 = coeffs.0.clone();
 52                let c2 = coeffs.1.clone();
 53
 54                c1.c0 = c1.c0.mul(cs.ns(|| "mul c1.c0"), &p.x)?;
 55                c1.c1 = c1.c1.mul(cs.ns(|| "mul c1.c1"), &p.x)?;
 56                *f = f.mul_by_034(cs.ns(|| "sparse mul f"), &c0, &c1, &c2)?;
 57                Ok(())
 58            },
 59        }
 60    }
 61
 62    fn exp_by_x<CS: ConstraintSystem<P::Fp>>(
 63        mut cs: CS,
 64        f: &Fp12Gadget<P::Fp12Params, P::Fp>,
 65    ) -> Result<Fp12Gadget<P::Fp12Params, P::Fp>, SynthesisError> {
 66        let mut result = f.cyclotomic_exp(cs.ns(|| "exp_by_x"), P::X)?;
 67        if P::X_IS_NEGATIVE {
 68            result.conjugate_in_place(cs.ns(|| "conjugate"))?;
 69        }
 70        Ok(result)
 71    }
 72}
 73
 74impl<P: Bls12Parameters> PG<Bls12<P>, P::Fp> for PairingGadget<P>
 75where
 76    G1Affine<P>: PairingCurve<
 77        BaseField = <P::G1Parameters as ModelParameters>::BaseField,
 78        ScalarField = <P::G1Parameters as ModelParameters>::ScalarField,
 79        Projective = G1Projective<P>,
 80        PairWith = G2Affine<P>,
 81        Prepared = G1Prepared<P>,
 82        PairingResult = Fp12<P::Fp12Params>,
 83    >,
 84    G2Affine<P>: PairingCurve<
 85        BaseField = <P::G2Parameters as ModelParameters>::BaseField,
 86        ScalarField = <P::G1Parameters as ModelParameters>::ScalarField,
 87        Projective = G2Projective<P>,
 88        PairWith = G1Affine<P>,
 89        Prepared = G2Prepared<P>,
 90        PairingResult = Fp12<P::Fp12Params>,
 91    >,
 92{
 93    type G1Gadget = G1Gadget<P>;
 94    type G2Gadget = G2Gadget<P>;
 95    type G1PreparedGadget = G1PreparedGadget<P>;
 96    type G2PreparedGadget = G2PreparedGadget<P>;
 97    type GTGadget = Fp12Gadget<P::Fp12Params, P::Fp>;
 98
 99    fn miller_loop<CS: ConstraintSystem<P::Fp>>(
100        mut cs: CS,
101        ps: &[Self::G1PreparedGadget],
102        qs: &[Self::G2PreparedGadget],
103    ) -> Result<Self::GTGadget, SynthesisError> {
104        let mut pairs = vec![];
105        for (p, q) in ps.iter().zip(qs.iter()) {
106            pairs.push((p, q.ell_coeffs.iter()));
107        }
108        let mut f = Self::GTGadget::one(cs.ns(|| "one"))?;
109
110        for (j, i) in BitIterator::new(P::X).skip(1).enumerate() {
111            let mut cs = cs.ns(|| format!("Iteration {}", j));
112            f.square_in_place(cs.ns(|| "square"))?;
113
114            for (k, &mut (p, ref mut coeffs)) in pairs.iter_mut().enumerate() {
115                let cs = cs.ns(|| format!("Double input {}", k));
116                Self::ell(cs, &mut f, coeffs.next().unwrap(), &p.0)?;
117            }
118
119            if i {
120                for (k, &mut (p, ref mut coeffs)) in pairs.iter_mut().enumerate() {
121                    let cs = cs.ns(|| format!("Addition input {}", k));
122                    Self::ell(cs, &mut f, &coeffs.next().unwrap(), &p.0)?;
123                }
124            }
125        }
126
127        if P::X_IS_NEGATIVE {
128            f.conjugate_in_place(cs.ns(|| "f conjugate"))?;
129        }
130
131        Ok(f)
132    }
133
134    fn final_exponentiation<CS: ConstraintSystem<P::Fp>>(
135        mut cs: CS,
136        f: &Self::GTGadget,
137    ) -> Result<Self::GTGadget, SynthesisError> {
138        // Computing the final exponentation following
139        // https://eprint.iacr.org/2016/130.pdf.
140        // We don't use their "faster" formula because it is difficult to make
141        // it work for curves with odd `P::X`.
142        // Hence we implement the slower algorithm from Table 1 below.
143
144        let f1 = f.frobenius_map(cs.ns(|| "frobmap 1"), 6)?;
145
146        f.inverse(cs.ns(|| "inverse 1")).and_then(|mut f2| {
147            // f2 = f^(-1);
148            // r = f^(p^6 - 1)
149            let mut r = f1;
150            r.mul_in_place(cs.ns(|| "r = f1 * f2"), &f2)?;
151
152            // f2 = f^(p^6 - 1)
153            f2 = r.clone();
154            // r = f^((p^6 - 1)(p^2))
155            r.frobenius_map_in_place(cs.ns(|| "frobenius map 2"), 2)?;
156
157            // r = f^((p^6 - 1)(p^2) + (p^6 - 1))
158            // r = f^((p^6 - 1)(p^2 + 1))
159            r.mul_in_place(cs.ns(|| "mul 0"), &f2)?;
160
161            // Hard part of the final exponentation is below:
162            // From https://eprint.iacr.org/2016/130.pdf, Table 1
163            let mut y0 = r.cyclotomic_square(cs.ns(|| "cyclotomic_sq 1"))?;
164            y0.conjugate_in_place(&mut cs.ns(|| "conjugate 2"))?;
165
166            let mut y5 = Self::exp_by_x(&mut cs.ns(|| "exp_by_x 1"), &r)?;
167
168            let mut y1 = y5.cyclotomic_square(&mut cs.ns(|| "square 1"))?;
169            let mut y3 = y0.mul(&mut cs.ns(|| "mul 1"), &y5)?;
170            y0 = Self::exp_by_x(cs.ns(|| "exp_by_x 2"), &y3)?;
171            let y2 = Self::exp_by_x(cs.ns(|| "exp_by_x 3"), &y0)?;
172            let mut y4 = Self::exp_by_x(cs.ns(|| "exp_by_x 4"), &y2)?;
173            y4.mul_in_place(cs.ns(|| "mul 2"), &y1)?;
174            y1 = Self::exp_by_x(cs.ns(|| "exp_by_x 5"), &y4)?;
175            y3.conjugate_in_place(cs.ns(|| "conjugate 3"))?;
176            y1.mul_in_place(cs.ns(|| "mul 3"), &y3)?;
177            y1.mul_in_place(cs.ns(|| "mul 4"), &r)?;
178            y3 = r.clone();
179            y3.conjugate_in_place(cs.ns(|| "conjugate 4"))?;
180            y0.mul_in_place(cs.ns(|| "mul 5"), &r)?;
181            y0.frobenius_map_in_place(cs.ns(|| "frobmap 3"), 3)?;
182            y4.mul_in_place(cs.ns(|| "mul 6"), &y3)?;
183            y4.frobenius_map_in_place(cs.ns(|| "frobmap 4"), 1)?;
184            y5.mul_in_place(cs.ns(|| "mul 7"), &y2)?;
185            y5.frobenius_map_in_place(cs.ns(|| "frobmap 5"), 2)?;
186            y5.mul_in_place(cs.ns(|| "mul 8"), &y0)?;
187            y5.mul_in_place(cs.ns(|| "mul 9"), &y4)?;
188            y5.mul_in_place(cs.ns(|| "mul 10"), &y1)?;
189            Ok(y5)
190        })
191    }
192
193    fn prepare_g1<CS: ConstraintSystem<P::Fp>>(
194        cs: CS,
195        p: &Self::G1Gadget,
196    ) -> Result<Self::G1PreparedGadget, SynthesisError> {
197        Self::G1PreparedGadget::from_affine(cs, p)
198    }
199
200    fn prepare_g2<CS: ConstraintSystem<P::Fp>>(
201        cs: CS,
202        q: &Self::G2Gadget,
203    ) -> Result<Self::G2PreparedGadget, SynthesisError> {
204        Self::G2PreparedGadget::from_affine(cs, q)
205    }
206}