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