1use r1cs_core::SynthesisError;
  2
  3use super::PairingVar as PG;
  4
  5use crate::{
  6    fields::{fp::FpVar, fp12::Fp12Var, fp2::Fp2Var, FieldVar},
  7    groups::bls12::{G1AffineVar, G1PreparedVar, G1Var, G2PreparedVar, G2Var},
  8};
  9use algebra::{
 10    curves::bls12::{Bls12, Bls12Parameters, TwistType},
 11    fields::BitIteratorBE,
 12};
 13use core::marker::PhantomData;
 14
 15pub struct PairingVar<P: Bls12Parameters>(PhantomData<P>);
 16
 17type Fp2V<P> = Fp2Var<<P as Bls12Parameters>::Fp2Params>;
 18
 19impl<P: Bls12Parameters> PairingVar<P> {
 20    // Evaluate the line function at point p.
 21    fn ell(
 22        f: &mut Fp12Var<P::Fp12Params>,
 23        coeffs: &(Fp2V<P>, Fp2V<P>),
 24        p: &G1AffineVar<P>,
 25    ) -> Result<(), SynthesisError> {
 26        let zero = FpVar::<P::Fp>::zero();
 27
 28        match P::TWIST_TYPE {
 29            TwistType::M => {
 30                let c0 = coeffs.0.clone();
 31                let mut c1 = coeffs.1.clone();
 32                let c2 = Fp2V::<P>::new(p.y.clone(), zero);
 33
 34                c1.c0 = c1.c0 * &p.x;
 35                c1.c1 = c1.c1 * &p.x;
 36                *f = f.mul_by_014(&c0, &c1, &c2)?;
 37                Ok(())
 38            }
 39            TwistType::D => {
 40                let c0 = Fp2V::<P>::new(p.y.clone(), zero);
 41                let mut c1 = coeffs.0.clone();
 42                let c2 = coeffs.1.clone();
 43
 44                c1.c0 = c1.c0 * &p.x;
 45                c1.c1 = c1.c1 * &p.x;
 46                *f = f.mul_by_034(&c0, &c1, &c2)?;
 47                Ok(())
 48            }
 49        }
 50    }
 51
 52    fn exp_by_x(f: &Fp12Var<P::Fp12Params>) -> Result<Fp12Var<P::Fp12Params>, SynthesisError> {
 53        let mut result = f.optimized_cyclotomic_exp(P::X)?;
 54        if P::X_IS_NEGATIVE {
 55            result = result.unitary_inverse()?;
 56        }
 57        Ok(result)
 58    }
 59}
 60
 61impl<P: Bls12Parameters> PG<Bls12<P>, P::Fp> for PairingVar<P> {
 62    type G1Var = G1Var<P>;
 63    type G2Var = G2Var<P>;
 64    type G1PreparedVar = G1PreparedVar<P>;
 65    type G2PreparedVar = G2PreparedVar<P>;
 66    type GTVar = Fp12Var<P::Fp12Params>;
 67
 68    fn miller_loop(
 69        ps: &[Self::G1PreparedVar],
 70        qs: &[Self::G2PreparedVar],
 71    ) -> Result<Self::GTVar, SynthesisError> {
 72        let mut pairs = vec![];
 73        for (p, q) in ps.iter().zip(qs.iter()) {
 74            pairs.push((p, q.ell_coeffs.iter()));
 75        }
 76        let mut f = Self::GTVar::one();
 77
 78        for i in BitIteratorBE::new(P::X).skip(1) {
 79            f.square_in_place()?;
 80
 81            for &mut (p, ref mut coeffs) in pairs.iter_mut() {
 82                Self::ell(&mut f, coeffs.next().unwrap(), &p.0)?;
 83            }
 84
 85            if i {
 86                for &mut (p, ref mut coeffs) in pairs.iter_mut() {
 87                    Self::ell(&mut f, &coeffs.next().unwrap(), &p.0)?;
 88                }
 89            }
 90        }
 91
 92        if P::X_IS_NEGATIVE {
 93            f = f.unitary_inverse()?;
 94        }
 95
 96        Ok(f)
 97    }
 98
 99    fn final_exponentiation(f: &Self::GTVar) -> Result<Self::GTVar, SynthesisError> {
100        // Computing the final exponentation following
101        // https://eprint.iacr.org/2016/130.pdf.
102        // We don't use their "faster" formula because it is difficult to make
103        // it work for curves with odd `P::X`.
104        // Hence we implement the slower algorithm from Table 1 below.
105
106        let f1 = f.frobenius_map(6)?;
107
108        f.inverse().and_then(|mut f2| {
109            // f2 = f^(-1);
110            // r = f^(p^6 - 1)
111            let mut r = f1;
112            r *= &f2;
113
114            // f2 = f^(p^6 - 1)
115            f2 = r.clone();
116            // r = f^((p^6 - 1)(p^2))
117            r.frobenius_map_in_place(2)?;
118
119            // r = f^((p^6 - 1)(p^2) + (p^6 - 1))
120            // r = f^((p^6 - 1)(p^2 + 1))
121            r *= &f2;
122
123            // Hard part of the final exponentation is below:
124            // From https://eprint.iacr.org/2016/130.pdf, Table 1
125            let mut y0 = r.cyclotomic_square()?;
126            y0 = y0.unitary_inverse()?;
127
128            let mut y5 = Self::exp_by_x(&r)?;
129
130            let mut y1 = y5.cyclotomic_square()?;
131            let mut y3 = y0 * &y5;
132            y0 = Self::exp_by_x(&y3)?;
133            let y2 = Self::exp_by_x(&y0)?;
134            let mut y4 = Self::exp_by_x(&y2)?;
135            y4 *= &y1;
136            y1 = Self::exp_by_x(&y4)?;
137            y3 = y3.unitary_inverse()?;
138            y1 *= &y3;
139            y1 *= &r;
140            y3 = r.clone();
141            y3 = y3.unitary_inverse()?;
142            y0 *= &r;
143            y0.frobenius_map_in_place(3)?;
144            y4 *= &y3;
145            y4.frobenius_map_in_place(1)?;
146            y5 *= &y2;
147            y5.frobenius_map_in_place(2)?;
148            y5 *= &y0;
149            y5 *= &y4;
150            y5 *= &y1;
151            Ok(y5)
152        })
153    }
154
155    fn prepare_g1(p: &Self::G1Var) -> Result<Self::G1PreparedVar, SynthesisError> {
156        Self::G1PreparedVar::from_group_var(p)
157    }
158
159    fn prepare_g2(q: &Self::G2Var) -> Result<Self::G2PreparedVar, SynthesisError> {
160        Self::G2PreparedVar::from_group_var(q)
161    }
162}