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