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

ark_ec/models/bw6/
mod.rs
