ark_ec/models/bls12/
mod.rs

1use crate::{
2    models::{short_weierstrass::SWCurveConfig, CurveConfig},
3    pairing::{MillerLoopOutput, Pairing, PairingOutput},
4    AffineRepr,
5};
6use ark_ff::{
7    fields::{
8        fp12_2over3over2::{Fp12, Fp12Config},
9        fp2::Fp2Config,
10        fp6_3over2::Fp6Config,
11        Fp2,
12    },
13    BitIteratorBE, CyclotomicMultSubgroup, Field, PrimeField,
14};
15use ark_std::{cfg_chunks_mut, marker::PhantomData, vec::*};
16use educe::Educe;
17use num_traits::{One, Zero};
18
19#[cfg(feature = "parallel")]
20use rayon::prelude::*;
21
22/// A particular BLS12 group can have G2 being either a multiplicative or a
23/// divisive twist.
24pub enum TwistType {
25    M,
26    D,
27}
28
29pub trait Bls12Config: 'static + Sized {
30    /// Parameterizes the BLS12 family.
31    const X: &'static [u64];
32    /// Is `Self::X` negative?
33    const X_IS_NEGATIVE: bool;
34    /// What kind of twist is this?
35    const TWIST_TYPE: TwistType;
36
37    type Fp: PrimeField + Into<<Self::Fp as PrimeField>::BigInt>;
38    type Fp2Config: Fp2Config<Fp = Self::Fp>;
39    type Fp6Config: Fp6Config<Fp2Config = Self::Fp2Config>;
40    type Fp12Config: Fp12Config<Fp6Config = Self::Fp6Config>;
41    type G1Config: SWCurveConfig<BaseField = Self::Fp>;
42    type G2Config: SWCurveConfig<
43        BaseField = Fp2<Self::Fp2Config>,
44        ScalarField = <Self::G1Config as CurveConfig>::ScalarField,
45    >;
46
47    fn multi_miller_loop(
48        a: impl IntoIterator<Item = impl Into<G1Prepared<Self>>>,
49        b: impl IntoIterator<Item = impl Into<G2Prepared<Self>>>,
50    ) -> MillerLoopOutput<Bls12<Self>> {
51        use itertools::Itertools;
52
53        let mut pairs = a
54            .into_iter()
55            .zip_eq(b)
56            .filter_map(|(p, q)| {
57                let (p, q) = (p.into(), q.into());
58                match !p.is_zero() && !q.is_zero() {
59                    true => Some((p, q.ell_coeffs.into_iter())),
60                    false => None,
61                }
62            })
63            .collect::<Vec<_>>();
64
65        let mut f = cfg_chunks_mut!(pairs, 4)
66            .map(|pairs| {
67                let mut f = <Bls12<Self> as Pairing>::TargetField::one();
68                for i in BitIteratorBE::without_leading_zeros(Self::X).skip(1) {
69                    f.square_in_place();
70                    for (p, coeffs) in pairs.iter_mut() {
71                        Bls12::<Self>::ell(&mut f, &coeffs.next().unwrap(), &p.0);
72                    }
73                    if i {
74                        for (p, coeffs) in pairs.iter_mut() {
75                            Bls12::<Self>::ell(&mut f, &coeffs.next().unwrap(), &p.0);
76                        }
77                    }
78                }
79                f
80            })
81            .product::<<Bls12<Self> as Pairing>::TargetField>();
82
83        if Self::X_IS_NEGATIVE {
84            f.cyclotomic_inverse_in_place();
85        }
86        MillerLoopOutput(f)
87    }
88
89    fn final_exponentiation(
90        f: MillerLoopOutput<Bls12<Self>>,
91    ) -> Option<PairingOutput<Bls12<Self>>> {
92        // Computing the final exponentiation following
93        // https://eprint.iacr.org/2020/875
94        // Adapted from the implementation in https://github.com/ConsenSys/gurvy/pull/29
95
96        // f1 = r.cyclotomic_inverse_in_place() = f^(p^6)
97        let f = f.0;
98        let mut f1 = f;
99        f1.cyclotomic_inverse_in_place();
100
101        f.inverse().map(|mut f2| {
102            // f2 = f^(-1);
103            // r = f^(p^6 - 1)
104            let mut r = f1 * &f2;
105
106            // f2 = f^(p^6 - 1)
107            f2 = r;
108            // r = f^((p^6 - 1)(p^2))
109            r.frobenius_map_in_place(2);
110
111            // r = f^((p^6 - 1)(p^2) + (p^6 - 1))
112            // r = f^((p^6 - 1)(p^2 + 1))
113            r *= &f2;
114
115            // Hard part of the final exponentiation:
116            // t[0].CyclotomicSquare(&result)
117            let mut y0 = r.cyclotomic_square();
118            // t[1].Expt(&result)
119            let mut y1 = Fp12::zero();
120            Bls12::<Self>::exp_by_x(&r, &mut y1);
121            // t[2].InverseUnitary(&result)
122            let mut y2 = r;
123            y2.cyclotomic_inverse_in_place();
124            // t[1].Mul(&t[1], &t[2])
125            y1 *= &y2;
126            // t[2].Expt(&t[1])
127            Bls12::<Self>::exp_by_x(&y1, &mut y2);
128            // t[1].InverseUnitary(&t[1])
129            y1.cyclotomic_inverse_in_place();
130            // t[1].Mul(&t[1], &t[2])
131            y1 *= &y2;
132            // t[2].Expt(&t[1])
133            Bls12::<Self>::exp_by_x(&y1, &mut y2);
134            // t[1].Frobenius(&t[1])
135            y1.frobenius_map_in_place(1);
136            // t[1].Mul(&t[1], &t[2])
137            y1 *= &y2;
138            // result.Mul(&result, &t[0])
139            r *= &y0;
140            // t[0].Expt(&t[1])
141            Bls12::<Self>::exp_by_x(&y1, &mut y0);
142            // t[2].Expt(&t[0])
143            Bls12::<Self>::exp_by_x(&y0, &mut y2);
144            // t[0].FrobeniusSquare(&t[1])
145            y0 = y1;
146            y0.frobenius_map_in_place(2);
147            // t[1].InverseUnitary(&t[1])
148            y1.cyclotomic_inverse_in_place();
149            // t[1].Mul(&t[1], &t[2])
150            y1 *= &y2;
151            // t[1].Mul(&t[1], &t[0])
152            y1 *= &y0;
153            // result.Mul(&result, &t[1])
154            r *= &y1;
155            PairingOutput(r)
156        })
157    }
158}
159
160pub mod g1;
161pub mod g2;
162
163pub use self::{
164    g1::{G1Affine, G1Prepared, G1Projective},
165    g2::{G2Affine, G2Prepared, G2Projective},
166};
167
168#[derive(Educe)]
169#[educe(Copy, Clone, PartialEq, Eq, Debug, Hash)]
170pub struct Bls12<P: Bls12Config>(PhantomData<fn() -> P>);
171
172impl<P: Bls12Config> Bls12<P> {
173    // Evaluate the line function at point p.
174    fn ell(f: &mut Fp12<P::Fp12Config>, coeffs: &g2::EllCoeff<P>, p: &G1Affine<P>) {
175        let mut c0 = coeffs.0;
176        let mut c1 = coeffs.1;
177        let mut c2 = coeffs.2;
178        let (px, py) = p.xy().unwrap();
179
180        match P::TWIST_TYPE {
181            TwistType::M => {
182                c2.mul_assign_by_fp(&py);
183                c1.mul_assign_by_fp(&px);
184                f.mul_by_014(&c0, &c1, &c2);
185            },
186            TwistType::D => {
187                c0.mul_assign_by_fp(&py);
188                c1.mul_assign_by_fp(&px);
189                f.mul_by_034(&c0, &c1, &c2);
190            },
191        }
192    }
193
194    // Exponentiates `f` by `Self::X`, and stores the result in `result`.
195    fn exp_by_x(f: &Fp12<P::Fp12Config>, result: &mut Fp12<P::Fp12Config>) {
196        *result = f.cyclotomic_exp(P::X);
197        if P::X_IS_NEGATIVE {
198            result.cyclotomic_inverse_in_place();
199        }
200    }
201}
202
203impl<P: Bls12Config> Pairing for Bls12<P> {
204    type BaseField = <P::G1Config as CurveConfig>::BaseField;
205    type ScalarField = <P::G1Config as CurveConfig>::ScalarField;
206    type G1 = G1Projective<P>;
207    type G1Affine = G1Affine<P>;
208    type G1Prepared = G1Prepared<P>;
209    type G2 = G2Projective<P>;
210    type G2Affine = G2Affine<P>;
211    type G2Prepared = G2Prepared<P>;
212    type TargetField = Fp12<P::Fp12Config>;
213
214    fn multi_miller_loop(
215        a: impl IntoIterator<Item = impl Into<Self::G1Prepared>>,
216        b: impl IntoIterator<Item = impl Into<Self::G2Prepared>>,
217    ) -> MillerLoopOutput<Self> {
218        P::multi_miller_loop(a, b)
219    }
220
221    fn final_exponentiation(f: MillerLoopOutput<Self>) -> Option<PairingOutput<Self>> {
222        P::final_exponentiation(f)
223    }
224}
ark_ec/models/bls12/mod.rs

ark_ec/models/bls12/
mod.rs
