ark_ec/models/bw6/
mod.rs

1use crate::{
2    models::{short_weierstrass::SWCurveConfig, CurveConfig},
3    pairing::{MillerLoopOutput, Pairing, PairingOutput},
4};
5use ark_ff::{
6    fields::{
7        fp3::Fp3Config,
8        fp6_2over3::{Fp6, Fp6Config},
9        Field, PrimeField,
10    },
11    BitIteratorBE, CyclotomicMultSubgroup,
12};
13use ark_std::cfg_chunks_mut;
14use educe::Educe;
15use itertools::Itertools;
16use num_traits::One;
17
18use ark_std::{marker::PhantomData, vec::*};
19
20#[cfg(feature = "parallel")]
21use rayon::prelude::*;
22
23pub enum TwistType {
24    M,
25    D,
26}
27
28pub trait BW6Config: 'static + Eq + Sized {
29    const X: <Self::Fp as PrimeField>::BigInt;
30    const X_IS_NEGATIVE: bool;
31    // [X-1]/3 for X>0, and [(-X)+1]/3 otherwise
32    const X_MINUS_1_DIV_3: <Self::Fp as PrimeField>::BigInt;
33    const ATE_LOOP_COUNT_1: &[u64];
34    const ATE_LOOP_COUNT_1_IS_NEGATIVE: bool;
35    // X^2 - X - 1
36    const ATE_LOOP_COUNT_2: &[i8];
37    const ATE_LOOP_COUNT_2_IS_NEGATIVE: bool;
38    const TWIST_TYPE: TwistType;
39    const H_T: i64;
40    const H_Y: i64;
41    const T_MOD_R_IS_ZERO: bool;
42
43    type Fp: PrimeField + Into<<Self::Fp as PrimeField>::BigInt>;
44    type Fp3Config: Fp3Config<Fp = Self::Fp>;
45    type Fp6Config: Fp6Config<Fp3Config = Self::Fp3Config>;
46    type G1Config: SWCurveConfig<BaseField = Self::Fp>;
47    type G2Config: SWCurveConfig<
48        BaseField = Self::Fp,
49        ScalarField = <Self::G1Config as CurveConfig>::ScalarField,
50    >;
51
52    // Computes the exponent of an element of the cyclotomic subgroup,
53    // and inverses the result if necessary.
54    fn cyclotomic_exp_signed(
55        f: &Fp6<Self::Fp6Config>,
56        x: impl AsRef<[u64]>,
57        invert: bool,
58    ) -> Fp6<Self::Fp6Config> {
59        let mut f = f.cyclotomic_exp(x);
60        if invert {
61            f.cyclotomic_inverse_in_place();
62        }
63        f
64    }
65
66    // Computes the exponent of an element of the cyclotomic subgroup by the curve seed
67    fn exp_by_x(f: &Fp6<Self::Fp6Config>) -> Fp6<Self::Fp6Config> {
68        Self::cyclotomic_exp_signed(f, Self::X, Self::X_IS_NEGATIVE)
69    }
70
71    fn final_exponentiation_hard_part(f: &Fp6<Self::Fp6Config>) -> Fp6<Self::Fp6Config> {
72        BW6::<Self>::final_exponentiation_hard_part(f)
73    }
74
75    fn final_exponentiation(f: MillerLoopOutput<BW6<Self>>) -> Option<PairingOutput<BW6<Self>>> {
76        let easy_part = BW6::<Self>::final_exponentiation_easy_part(f.0);
77        Some(PairingOutput(Self::final_exponentiation_hard_part(
78            &easy_part,
79        )))
80    }
81
82    fn multi_miller_loop(
83        a: impl IntoIterator<Item = impl Into<G1Prepared<Self>>>,
84        b: impl IntoIterator<Item = impl Into<G2Prepared<Self>>>,
85    ) -> MillerLoopOutput<BW6<Self>> {
86        // Implements unoptimized version of the Miller loop for the optimal ate pairing.
87        // See formulas (4.15) and (4.17) from https://yelhousni.github.io/phd.pdf
88
89        let (mut pairs_1, mut pairs_2) = a
90            .into_iter()
91            .zip_eq(b)
92            .filter_map(|(p, q)| {
93                let (p, q): (G1Prepared<Self>, G2Prepared<Self>) = (p.into(), q.into());
94                match !p.is_zero() && !q.is_zero() {
95                    true => Some((
96                        (p, q.ell_coeffs_1.into_iter()),
97                        (p, q.ell_coeffs_2.into_iter()),
98                    )),
99                    false => None,
100                }
101            })
102            .unzip::<_, _, Vec<_>, Vec<_>>();
103
104        // compute f_u which we can later re-use for the 2nd loop
105        let mut f_u = cfg_chunks_mut!(pairs_1, 4)
106            .map(|pairs| {
107                let mut f = <BW6<Self> as Pairing>::TargetField::one();
108                for i in BitIteratorBE::without_leading_zeros(Self::ATE_LOOP_COUNT_1).skip(1) {
109                    f.square_in_place();
110                    for (p, coeffs) in pairs.iter_mut() {
111                        BW6::<Self>::ell(&mut f, &coeffs.next().unwrap(), &p.0);
112                    }
113                    if i {
114                        for (p, coeffs) in pairs.iter_mut() {
115                            BW6::<Self>::ell(&mut f, &coeffs.next().unwrap(), &p.0);
116                        }
117                    }
118                }
119                f
120            })
121            .product::<<BW6<Self> as Pairing>::TargetField>();
122
123        let f_u_inv;
124
125        if Self::ATE_LOOP_COUNT_1_IS_NEGATIVE {
126            f_u_inv = f_u;
127            f_u.cyclotomic_inverse_in_place();
128        } else {
129            f_u_inv = f_u.cyclotomic_inverse().unwrap();
130        }
131
132        // f_1(P) = f_(u+1)(P) = f_u(P) * l([u]q, q)(P)
133        let mut f_1 = cfg_chunks_mut!(pairs_1, 4)
134            .map(|pairs| {
135                pairs.iter_mut().fold(f_u, |mut f, (p, coeffs)| {
136                    BW6::<Self>::ell(&mut f, &coeffs.next().unwrap(), &p.0);
137                    f
138                })
139            })
140            .product::<<BW6<Self> as Pairing>::TargetField>();
141
142        let mut f_2 = cfg_chunks_mut!(pairs_2, 4)
143            .map(|pairs| {
144                let mut f = f_u;
145                for i in (1..Self::ATE_LOOP_COUNT_2.len()).rev() {
146                    f.square_in_place();
147
148                    for (p, ref mut coeffs) in pairs.iter_mut() {
149                        BW6::<Self>::ell(&mut f, &coeffs.next().unwrap(), &p.0);
150                    }
151
152                    let bit = Self::ATE_LOOP_COUNT_2[i - 1];
153                    if bit == 1 {
154                        f *= &f_u;
155                    } else if bit == -1 {
156                        f *= &f_u_inv;
157                    } else {
158                        continue;
159                    }
160                    for &mut (p, ref mut coeffs) in pairs.iter_mut() {
161                        BW6::<Self>::ell(&mut f, &coeffs.next().unwrap(), &p.0);
162                    }
163                }
164                f
165            })
166            .product::<<BW6<Self> as Pairing>::TargetField>();
167
168        if Self::ATE_LOOP_COUNT_2_IS_NEGATIVE {
169            f_2.cyclotomic_inverse_in_place();
170        }
171
172        if Self::T_MOD_R_IS_ZERO {
173            f_1.frobenius_map_in_place(1);
174        } else {
175            f_2.frobenius_map_in_place(1);
176        }
177
178        MillerLoopOutput(f_1 * &f_2)
179    }
180}
181
182pub mod g1;
183pub mod g2;
184
185pub use self::{
186    g1::{G1Affine, G1Prepared, G1Projective},
187    g2::{G2Affine, G2Prepared, G2Projective},
188};
189
190#[derive(Educe)]
191#[educe(Copy, Clone, PartialEq, Eq, Debug, Hash)]
192pub struct BW6<P: BW6Config>(PhantomData<fn() -> P>);
193
194impl<P: BW6Config> BW6<P> {
195    // Evaluate the line function at point p.
196    fn ell(f: &mut Fp6<P::Fp6Config>, coeffs: &(P::Fp, P::Fp, P::Fp), p: &G1Affine<P>) {
197        let mut c0 = coeffs.0;
198        let mut c1 = coeffs.1;
199        let mut c2 = coeffs.2;
200
201        match P::TWIST_TYPE {
202            TwistType::M => {
203                c2 *= &p.y;
204                c1 *= &p.x;
205                f.mul_by_014(&c0, &c1, &c2);
206            },
207            TwistType::D => {
208                c0 *= &p.y;
209                c1 *= &p.x;
210                f.mul_by_034(&c0, &c1, &c2);
211            },
212        }
213    }
214
215    fn exp_by_x_plus_1(f: &Fp6<P::Fp6Config>) -> Fp6<P::Fp6Config> {
216        P::exp_by_x(f) * f
217    }
218
219    fn exp_by_x_minus_1(f: &Fp6<P::Fp6Config>) -> Fp6<P::Fp6Config> {
220        P::exp_by_x(f) * &f.cyclotomic_inverse().unwrap()
221    }
222
223    fn exp_by_x_minus_1_div_3(f: &Fp6<P::Fp6Config>) -> Fp6<P::Fp6Config> {
224        P::cyclotomic_exp_signed(f, P::X_MINUS_1_DIV_3, P::X_IS_NEGATIVE)
225    }
226
227    // f^[(p^3-1)(p+1)]
228    fn final_exponentiation_easy_part(f: Fp6<P::Fp6Config>) -> Fp6<P::Fp6Config> {
229        // f^(-1)
230        let f_inv = f.inverse().unwrap();
231        // f^(p^3)
232        let f_p3 = {
233            let mut f = f;
234            f.conjugate_in_place();
235            f
236        };
237        // g := f^(p^3-1) = f^(p^3) * f^(-1)
238        let g = f_p3 * f_inv;
239        // g^p
240        let g_p = {
241            let mut g = g;
242            g.frobenius_map_in_place(1);
243            g
244        };
245        // g^(p+1) = g^p * g
246        g_p * &g
247    }
248
249    fn final_exponentiation_hard_part(f: &Fp6<P::Fp6Config>) -> Fp6<P::Fp6Config> {
250        // A = m**(u-1)
251        let a = Self::exp_by_x_minus_1(f);
252        // A = A**(u-1)
253        let a = Self::exp_by_x_minus_1(&a);
254
255        // Generic implementation of the hard part of the final exponentiation for the BW6 family.
256        // Computes (u+1)*Phi_k(p(u))/r(u)
257        if P::T_MOD_R_IS_ZERO {
258            // Algorithm 4.3 from https://yelhousni.github.io/phd.pdf
259            // Follows the implementation https://gitlab.inria.fr/zk-curves/snark-2-chains/-/blob/master/sage/pairing_bw6_bls12.py#L1036
260
261            // A = (m * A).conjugate() * m.frobenius()
262            let a = (f * &a).cyclotomic_inverse().unwrap() * f.frobenius_map(1);
263            // B = A**(u+1) * m
264            let b = Self::exp_by_x_plus_1(&a) * f;
265            // A = A**2 * A
266            let a = a.square() * &a;
267            // A = A.conjugate()
268            let a = a.cyclotomic_inverse().unwrap();
269            // C = B**((u-1)//3)
270            let c = Self::exp_by_x_minus_1_div_3(&b);
271            // D = C**(u-1)
272            let d = Self::exp_by_x_minus_1(&c);
273            // E = (D**(u-1))**(u-1) * D
274            let e = Self::exp_by_x_minus_1(&Self::exp_by_x_minus_1(&d)) * &d;
275            // F = (E**(u+1) * C).conjugate() * D
276            let f = (Self::exp_by_x_plus_1(&e) * &c)
277                .cyclotomic_inverse()
278                .unwrap()
279                * &d;
280            // G = ((F * D)**(u+1)).conjugate() * C * B
281            let g = Self::exp_by_x_plus_1(&(f * &d))
282                .cyclotomic_inverse()
283                .unwrap()
284                * &c
285                * &b;
286            // d2 = (ht**2+3*hy**2)//4
287            let d2 = ((P::H_T * P::H_T + 3 * P::H_Y * P::H_Y) / 4) as u64;
288            // d1 = (ht-hy)//2
289            let d1 = (P::H_T - P::H_Y) / 2;
290            // H = F**d1 * E
291            let h = P::cyclotomic_exp_signed(&f, [d1 as u64], d1 < 0) * &e;
292            // H = H**2 * H * B * G**d2
293            let h = h.square() * &h * &b * g.cyclotomic_exp([d2]);
294            // return A * H
295            a * &h
296        } else {
297            // Algorithm 4.4 from https://yelhousni.github.io/phd.pdf
298            // Follows the implementation https://gitlab.inria.fr/zk-curves/snark-2-chains/-/blob/master/sage/pairing_bw6_bls12.py#L969
299
300            // A = A * m.frobenius()
301            let a = a * f.frobenius_map(1);
302            // B = A**(u+1) * m.conjugate()
303            let b = Self::exp_by_x_plus_1(&a) * f.cyclotomic_inverse().unwrap();
304            // A = A**2 * A
305            let a = a.square() * &a;
306            // C = B**((u-1)//3)
307            let c = Self::exp_by_x_minus_1_div_3(&b);
308            // D = C**(u-1)
309            let d = Self::exp_by_x_minus_1(&c);
310            // E = (D**(u-1))**(u-1) * D
311            let e = Self::exp_by_x_minus_1(&Self::exp_by_x_minus_1(&d)) * &d;
312            // D = D.conjugate()
313            let d = d.cyclotomic_inverse().unwrap();
314            // Fc = D * B
315            let fc = d * &b;
316            // G = E**(u+1) * Fc
317            let g = Self::exp_by_x_plus_1(&e) * &fc;
318            // H = G * C
319            let h = g * &c;
320            // I = (G * D)**(u+1) * Fc.conjugate()
321            let i = Self::exp_by_x_plus_1(&(g * &d)) * fc.cyclotomic_inverse().unwrap();
322            // d2 = (ht**2+3*hy**2)//4
323            let d2 = ((P::H_T * P::H_T + 3 * P::H_Y * P::H_Y) / 4) as u64;
324            // d1 = (ht+hy)//2
325            let d1 = (P::H_T + P::H_Y) / 2;
326            // J = H**d1 * E
327            let j = P::cyclotomic_exp_signed(&h, [d1 as u64], d1 < 0) * &e;
328            // K = J**2 * J * B * I**d2
329            let k = j.square() * &j * &b * i.cyclotomic_exp([d2]);
330            // return A * K
331            a * &k
332        }
333    }
334}
335
336impl<P: BW6Config> Pairing for BW6<P> {
337    type BaseField = <P::G1Config as CurveConfig>::BaseField;
338    type ScalarField = <P::G1Config as CurveConfig>::ScalarField;
339    type G1 = G1Projective<P>;
340    type G1Affine = G1Affine<P>;
341    type G1Prepared = G1Prepared<P>;
342    type G2 = G2Projective<P>;
343    type G2Affine = G2Affine<P>;
344    type G2Prepared = G2Prepared<P>;
345    type TargetField = Fp6<P::Fp6Config>;
346
347    fn final_exponentiation(f: MillerLoopOutput<Self>) -> Option<PairingOutput<Self>> {
348        P::final_exponentiation(f)
349    }
350
351    fn multi_miller_loop(
352        a: impl IntoIterator<Item = impl Into<Self::G1Prepared>>,
353        b: impl IntoIterator<Item = impl Into<Self::G2Prepared>>,
354    ) -> MillerLoopOutput<Self> {
355        P::multi_miller_loop(a, b)
356    }
357}
ark_ec/models/bw6/mod.rs

ark_ec/models/bw6/
mod.rs
