ark_r1cs_std/pairing/bls12/
mod.rs

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, Bls12Config, TwistType};
10use ark_ff::BitIteratorBE;
11use ark_std::marker::PhantomData;
12
13/// Specifies the constraints for computing a pairing in a BLS12 bilinear group.
14pub struct PairingVar<P: Bls12Config>(PhantomData<P>);
15
16type Fp2V<P> = Fp2Var<<P as Bls12Config>::Fp2Config>;
17
18impl<P: Bls12Config> PairingVar<P> {
19    // Evaluate the line function at point p.
20    #[tracing::instrument(target = "r1cs")]
21    fn ell(
22        f: &mut Fp12Var<P::Fp12Config>,
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 *= &p.x;
35                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 *= &p.x;
45                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::Fp12Config>) -> Result<Fp12Var<P::Fp12Config>, 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: Bls12Config> PG<Bls12<P>> 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::Fp12Config>;
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.unitary_inverse()?;
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}
ark_r1cs_std/pairing/bls12/mod.rs

ark_r1cs_std/pairing/bls12/
mod.rs
