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