ark_ec/models/mnt6/
mod.rs

1use crate::{
2    models::{short_weierstrass::SWCurveConfig, CurveConfig},
3    pairing::{MillerLoopOutput, Pairing, PairingOutput},
4};
5use ark_ff::{
6    fp3::{Fp3, Fp3Config},
7    fp6_2over3::{Fp6, Fp6Config},
8    AdditiveGroup, CyclotomicMultSubgroup, Field, PrimeField,
9};
10use educe::Educe;
11use itertools::Itertools;
12use num_traits::{One, Zero};
13
14use ark_std::{marker::PhantomData, vec::*};
15
16#[cfg(feature = "parallel")]
17use rayon::prelude::*;
18
19pub mod g1;
20pub mod g2;
21
22use self::g2::{AteAdditionCoefficients, AteDoubleCoefficients, G2ProjectiveExtended};
23pub use self::{
24    g1::{G1Affine, G1Prepared, G1Projective},
25    g2::{G2Affine, G2Prepared, G2Projective},
26};
27
28pub type GT<P> = Fp6<P>;
29
30pub trait MNT6Config: 'static + Sized {
31    const TWIST: Fp3<Self::Fp3Config>;
32    const TWIST_COEFF_A: Fp3<Self::Fp3Config>;
33    const ATE_LOOP_COUNT: &'static [i8];
34    const ATE_IS_LOOP_COUNT_NEG: bool;
35    const FINAL_EXPONENT_LAST_CHUNK_1: <Self::Fp as PrimeField>::BigInt;
36    const FINAL_EXPONENT_LAST_CHUNK_W0_IS_NEG: bool;
37    const FINAL_EXPONENT_LAST_CHUNK_ABS_OF_W0: <Self::Fp as PrimeField>::BigInt;
38    type Fp: PrimeField + Into<<Self::Fp as PrimeField>::BigInt>;
39    type Fr: PrimeField + Into<<Self::Fr as PrimeField>::BigInt>;
40    type Fp3Config: Fp3Config<Fp = Self::Fp>;
41    type Fp6Config: Fp6Config<Fp3Config = Self::Fp3Config>;
42    type G1Config: SWCurveConfig<BaseField = Self::Fp, ScalarField = Self::Fr>;
43    type G2Config: SWCurveConfig<
44        BaseField = Fp3<Self::Fp3Config>,
45        ScalarField = <Self::G1Config as CurveConfig>::ScalarField,
46    >;
47
48    fn multi_miller_loop(
49        a: impl IntoIterator<Item = impl Into<G1Prepared<Self>>>,
50        b: impl IntoIterator<Item = impl Into<G2Prepared<Self>>>,
51    ) -> MillerLoopOutput<MNT6<Self>> {
52        let pairs = a
53            .into_iter()
54            .zip_eq(b)
55            .map(|(a, b)| (a.into(), b.into()))
56            .collect::<Vec<_>>();
57        let result = ark_std::cfg_into_iter!(pairs)
58            .map(|(a, b)| MNT6::<Self>::ate_miller_loop(&a, &b))
59            .product();
60        MillerLoopOutput(result)
61    }
62
63    fn final_exponentiation(f: MillerLoopOutput<MNT6<Self>>) -> Option<PairingOutput<MNT6<Self>>> {
64        let value = f.0;
65        let value_inv = value.inverse()?;
66        let value_to_first_chunk =
67            MNT6::<Self>::final_exponentiation_first_chunk(&value, &value_inv);
68        let value_inv_to_first_chunk =
69            MNT6::<Self>::final_exponentiation_first_chunk(&value_inv, &value);
70        let result = MNT6::<Self>::final_exponentiation_last_chunk(
71            &value_to_first_chunk,
72            &value_inv_to_first_chunk,
73        );
74        Some(PairingOutput(result))
75    }
76}
77
78#[derive(Educe)]
79#[educe(Copy, Clone, PartialEq, Eq, Debug, Hash)]
80pub struct MNT6<P: MNT6Config>(PhantomData<fn() -> P>);
81
82impl<P: MNT6Config> MNT6<P> {
83    fn doubling_for_flipped_miller_loop(
84        r: &G2ProjectiveExtended<P>,
85    ) -> (G2ProjectiveExtended<P>, AteDoubleCoefficients<P>) {
86        let a = r.t.square();
87        let b = r.x.square();
88        let c = r.y.square();
89        let d = c.square();
90        let e = (r.x + &c).square() - &b - &d;
91        let f = (b + &b + &b) + &(P::TWIST_COEFF_A * &a);
92        let g = f.square();
93
94        let d_eight = d.double().double().double();
95
96        let e2 = e.double();
97        let x = g - &e2.double();
98        let y = -d_eight + &(f * &(e2 - &x));
99        let z = (r.y + &r.z).square() - &c - &r.z.square();
100        let t = z.square();
101
102        let r2 = G2ProjectiveExtended { x, y, z, t };
103        let coeff = AteDoubleCoefficients {
104            c_h: (r2.z + &r.t).square() - &r2.t - &a,
105            c_4c: c + &c + &c + &c,
106            c_j: (f + &r.t).square() - &g - &a,
107            c_l: (f + &r.x).square() - &g - &b,
108        };
109
110        (r2, coeff)
111    }
112
113    fn mixed_addition_for_flipper_miller_loop(
114        x: &Fp3<P::Fp3Config>,
115        y: &Fp3<P::Fp3Config>,
116        r: &G2ProjectiveExtended<P>,
117    ) -> (G2ProjectiveExtended<P>, AteAdditionCoefficients<P>) {
118        let a = y.square();
119        let b = r.t * x;
120        let d = ((r.z + y).square() - &a - &r.t) * &r.t;
121        let h = b - &r.x;
122        let i = h.square();
123        let e = i + &i + &i + &i;
124        let j = h * &e;
125        let v = r.x * &e;
126        let ry2 = r.y.double();
127        let l1 = d - &ry2;
128
129        let x = l1.square() - &j - &(v + &v);
130        let y = l1 * &(v - &x) - &(j * &ry2);
131        let z = (r.z + &h).square() - &r.t - &i;
132        let t = z.square();
133
134        let r2 = G2ProjectiveExtended { x, y, z, t };
135        let coeff = AteAdditionCoefficients { c_l1: l1, c_rz: z };
136
137        (r2, coeff)
138    }
139
140    pub fn ate_miller_loop(p: &G1Prepared<P>, q: &G2Prepared<P>) -> Fp6<P::Fp6Config> {
141        let l1_coeff = Fp3::new(p.x, P::Fp::zero(), P::Fp::zero()) - &q.x_over_twist;
142
143        let mut f = <Fp6<P::Fp6Config>>::one();
144
145        let mut add_idx: usize = 0;
146
147        // code below gets executed for all bits (EXCEPT the MSB itself) of
148        // mnt6_param_p (skipping leading zeros) in MSB to LSB order
149        let y_over_twist_neg = -q.y_over_twist;
150        assert_eq!(P::ATE_LOOP_COUNT.len() - 1, q.double_coefficients.len());
151        for (bit, dc) in P::ATE_LOOP_COUNT.iter().skip(1).zip(&q.double_coefficients) {
152            let g_rr_at_p = Fp6::new(
153                dc.c_l - &dc.c_4c - &(dc.c_j * &p.x_twist),
154                dc.c_h * &p.y_twist,
155            );
156
157            f = f.square() * &g_rr_at_p;
158
159            // Compute l_{R,Q}(P) if bit == 1, and l_{R,-Q}(P) if bit == -1
160            let g_rq_at_p = if *bit == 1 {
161                let ac = &q.addition_coefficients[add_idx];
162                add_idx += 1;
163
164                Fp6::new(
165                    ac.c_rz * &p.y_twist,
166                    -(q.y_over_twist * &ac.c_rz + &(l1_coeff * &ac.c_l1)),
167                )
168            } else if *bit == -1 {
169                let ac = &q.addition_coefficients[add_idx];
170                add_idx += 1;
171                Fp6::new(
172                    ac.c_rz * &p.y_twist,
173                    -(y_over_twist_neg * &ac.c_rz + &(l1_coeff * &ac.c_l1)),
174                )
175            } else if *bit == 0 {
176                continue;
177            } else {
178                unreachable!();
179            };
180            f *= &g_rq_at_p;
181        }
182
183        if P::ATE_IS_LOOP_COUNT_NEG {
184            let ac = &q.addition_coefficients[add_idx];
185
186            let g_rnegr_at_p = Fp6::new(
187                ac.c_rz * &p.y_twist,
188                -(q.y_over_twist * &ac.c_rz + &(l1_coeff * &ac.c_l1)),
189            );
190            f = (f * &g_rnegr_at_p).inverse().unwrap();
191        }
192
193        f
194    }
195
196    fn final_exponentiation_first_chunk(
197        elt: &Fp6<P::Fp6Config>,
198        elt_inv: &Fp6<P::Fp6Config>,
199    ) -> Fp6<P::Fp6Config> {
200        // (q^3-1)*(q+1)
201
202        // elt_q3 = elt^(q^3)
203        let mut elt_q3 = *elt;
204        elt_q3.cyclotomic_inverse_in_place();
205        // elt_q3_over_elt = elt^(q^3-1)
206        let elt_q3_over_elt = elt_q3 * elt_inv;
207        // alpha = elt^((q^3-1) * q)
208        let mut alpha = elt_q3_over_elt;
209        alpha.frobenius_map_in_place(1);
210        // beta = elt^((q^3-1)*(q+1)
211        alpha * &elt_q3_over_elt
212    }
213
214    fn final_exponentiation_last_chunk(
215        elt: &Fp6<P::Fp6Config>,
216        elt_inv: &Fp6<P::Fp6Config>,
217    ) -> Fp6<P::Fp6Config> {
218        let elt_clone = *elt;
219        let elt_inv_clone = *elt_inv;
220
221        let mut elt_q = *elt;
222        elt_q.frobenius_map_in_place(1);
223
224        let w1_part = elt_q.cyclotomic_exp(P::FINAL_EXPONENT_LAST_CHUNK_1);
225        let w0_part = if P::FINAL_EXPONENT_LAST_CHUNK_W0_IS_NEG {
226            elt_inv_clone.cyclotomic_exp(P::FINAL_EXPONENT_LAST_CHUNK_ABS_OF_W0)
227        } else {
228            elt_clone.cyclotomic_exp(P::FINAL_EXPONENT_LAST_CHUNK_ABS_OF_W0)
229        };
230
231        w1_part * &w0_part
232    }
233}
234
235impl<P: MNT6Config> Pairing for MNT6<P> {
236    type BaseField = <P::G1Config as CurveConfig>::BaseField;
237    type ScalarField = <P::G1Config as CurveConfig>::ScalarField;
238    type G1 = G1Projective<P>;
239    type G1Affine = G1Affine<P>;
240    type G1Prepared = G1Prepared<P>;
241    type G2 = G2Projective<P>;
242    type G2Affine = G2Affine<P>;
243    type G2Prepared = G2Prepared<P>;
244    type TargetField = Fp6<P::Fp6Config>;
245
246    fn multi_miller_loop(
247        a: impl IntoIterator<Item = impl Into<Self::G1Prepared>>,
248        b: impl IntoIterator<Item = impl Into<Self::G2Prepared>>,
249    ) -> MillerLoopOutput<Self> {
250        P::multi_miller_loop(a, b)
251    }
252
253    fn final_exponentiation(f: MillerLoopOutput<Self>) -> Option<PairingOutput<Self>> {
254        P::final_exponentiation(f)
255    }
256}
ark_ec/models/mnt6/mod.rs

ark_ec/models/mnt6/
mod.rs
