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