ark_ec/models/mnt4/
mod.rs

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

ark_ec/models/mnt4/
mod.rs
