ark_ec/models/bn/
mod.rs

1use crate::{
2    models::{short_weierstrass::SWCurveConfig, CurveConfig},
3    pairing::{MillerLoopOutput, Pairing, PairingOutput},
4};
5use ark_ff::{
6    fields::{
7        fp12_2over3over2::{Fp12, Fp12Config},
8        fp2::Fp2Config,
9        fp6_3over2::Fp6Config,
10        Field, Fp2, PrimeField,
11    },
12    CyclotomicMultSubgroup,
13};
14use ark_std::{cfg_chunks_mut, marker::PhantomData, vec::*};
15use educe::Educe;
16use itertools::Itertools;
17use num_traits::One;
18
19#[cfg(feature = "parallel")]
20use rayon::prelude::*;
21
22pub enum TwistType {
23    M,
24    D,
25}
26
27pub trait BnConfig: 'static + Sized {
28    /// The absolute value of the BN curve parameter `X`
29    /// (as in `q = 36 X^4 + 36 X^3 + 24 X^2 + 6 X + 1`).
30    const X: &[u64];
31
32    /// Whether or not `X` is negative.
33    const X_IS_NEGATIVE: bool;
34
35    /// The absolute value of `6X + 2`.
36    const ATE_LOOP_COUNT: &[i8];
37
38    const TWIST_TYPE: TwistType;
39    const TWIST_MUL_BY_Q_X: Fp2<Self::Fp2Config>;
40    const TWIST_MUL_BY_Q_Y: Fp2<Self::Fp2Config>;
41    type Fp: PrimeField + Into<<Self::Fp as PrimeField>::BigInt>;
42    type Fp2Config: Fp2Config<Fp = Self::Fp>;
43    type Fp6Config: Fp6Config<Fp2Config = Self::Fp2Config>;
44    type Fp12Config: Fp12Config<Fp6Config = Self::Fp6Config>;
45    type G1Config: SWCurveConfig<BaseField = Self::Fp>;
46    type G2Config: SWCurveConfig<
47        BaseField = Fp2<Self::Fp2Config>,
48        ScalarField = <Self::G1Config as CurveConfig>::ScalarField,
49    >;
50
51    fn multi_miller_loop(
52        a: impl IntoIterator<Item = impl Into<G1Prepared<Self>>>,
53        b: impl IntoIterator<Item = impl Into<G2Prepared<Self>>>,
54    ) -> MillerLoopOutput<Bn<Self>> {
55        let mut pairs = a
56            .into_iter()
57            .zip_eq(b)
58            .filter_map(|(p, q)| {
59                let (p, q) = (p.into(), q.into());
60                match !p.is_zero() && !q.is_zero() {
61                    true => Some((p, q.ell_coeffs.into_iter())),
62                    false => None,
63                }
64            })
65            .collect::<Vec<_>>();
66
67        let mut f = cfg_chunks_mut!(pairs, 4)
68            .map(|pairs| {
69                let mut f = <Bn<Self> as Pairing>::TargetField::one();
70                for i in (1..Self::ATE_LOOP_COUNT.len()).rev() {
71                    if i != Self::ATE_LOOP_COUNT.len() - 1 {
72                        f.square_in_place();
73                    }
74
75                    for (p, coeffs) in pairs.iter_mut() {
76                        Bn::<Self>::ell(&mut f, &coeffs.next().unwrap(), &p.0);
77                    }
78
79                    let bit = Self::ATE_LOOP_COUNT[i - 1];
80                    if bit == 1 || bit == -1 {
81                        for (p, coeffs) in pairs.iter_mut() {
82                            Bn::<Self>::ell(&mut f, &coeffs.next().unwrap(), &p.0);
83                        }
84                    }
85                }
86                f
87            })
88            .product::<<Bn<Self> as Pairing>::TargetField>();
89
90        if Self::X_IS_NEGATIVE {
91            f.cyclotomic_inverse_in_place();
92        }
93
94        for (p, coeffs) in &mut pairs {
95            Bn::<Self>::ell(&mut f, &coeffs.next().unwrap(), &p.0);
96        }
97
98        for (p, coeffs) in &mut pairs {
99            Bn::<Self>::ell(&mut f, &coeffs.next().unwrap(), &p.0);
100        }
101
102        MillerLoopOutput(f)
103    }
104
105    fn final_exponentiation(f: MillerLoopOutput<Bn<Self>>) -> Option<PairingOutput<Bn<Self>>> {
106        // Easy part: result = elt^((q^6-1)*(q^2+1)).
107        // Follows, e.g., Beuchat et al page 9, by computing result as follows:
108        //   elt^((q^6-1)*(q^2+1)) = (conj(elt) * elt^(-1))^(q^2+1)
109        let f = f.0;
110
111        // f1 = r.cyclotomic_inverse_in_place() = f^(p^6)
112        let mut f1 = f;
113        f1.cyclotomic_inverse_in_place();
114
115        f.inverse().map(|mut f2| {
116            // f2 = f^(-1);
117            // r = f^(p^6 - 1)
118            let mut r = f1 * &f2;
119
120            // f2 = f^(p^6 - 1)
121            f2 = r;
122            // r = f^((p^6 - 1)(p^2))
123            r.frobenius_map_in_place(2);
124
125            // r = f^((p^6 - 1)(p^2) + (p^6 - 1))
126            // r = f^((p^6 - 1)(p^2 + 1))
127            r *= &f2;
128
129            // Hard part follows Laura Fuentes-Castaneda et al. "Faster hashing to G2"
130            // by computing:
131            //
132            // result = elt^(q^3 * (12*z^3 + 6z^2 + 4z - 1) +
133            //               q^2 * (12*z^3 + 6z^2 + 6z) +
134            //               q   * (12*z^3 + 6z^2 + 4z) +
135            //               1   * (12*z^3 + 12z^2 + 6z + 1))
136            // which equals
137            //
138            // result = elt^( 2z * ( 6z^2 + 3z + 1 ) * (q^4 - q^2 + 1)/r ).
139
140            let y0 = Bn::<Self>::exp_by_neg_x(r);
141            let y1 = y0.cyclotomic_square();
142            let y2 = y1.cyclotomic_square();
143            let mut y3 = y2 * &y1;
144            let y4 = Bn::<Self>::exp_by_neg_x(y3);
145            let y5 = y4.cyclotomic_square();
146            let mut y6 = Bn::<Self>::exp_by_neg_x(y5);
147            y3.cyclotomic_inverse_in_place();
148            y6.cyclotomic_inverse_in_place();
149            let y7 = y6 * &y4;
150            let mut y8 = y7 * &y3;
151            let y9 = y8 * &y1;
152            let y10 = y8 * &y4;
153            let y11 = y10 * &r;
154            let mut y12 = y9;
155            y12.frobenius_map_in_place(1);
156            let y13 = y12 * &y11;
157            y8.frobenius_map_in_place(2);
158            let y14 = y8 * &y13;
159            r.cyclotomic_inverse_in_place();
160            let mut y15 = r * &y9;
161            y15.frobenius_map_in_place(3);
162            let y16 = y15 * &y14;
163
164            PairingOutput(y16)
165        })
166    }
167}
168
169pub mod g1;
170pub mod g2;
171
172pub use self::{
173    g1::{G1Affine, G1Prepared, G1Projective},
174    g2::{G2Affine, G2Prepared, G2Projective},
175};
176
177#[derive(Educe)]
178#[educe(Copy, Clone, PartialEq, Eq, Debug, Hash)]
179pub struct Bn<P: BnConfig>(PhantomData<fn() -> P>);
180
181impl<P: BnConfig> Bn<P> {
182    /// Evaluates the line function at point p.
183    fn ell(f: &mut Fp12<P::Fp12Config>, coeffs: &g2::EllCoeff<P>, p: &G1Affine<P>) {
184        let mut c0 = coeffs.0;
185        let mut c1 = coeffs.1;
186        let mut c2 = coeffs.2;
187
188        match P::TWIST_TYPE {
189            TwistType::M => {
190                c2.mul_assign_by_fp(&p.y);
191                c1.mul_assign_by_fp(&p.x);
192                f.mul_by_014(&c0, &c1, &c2);
193            },
194            TwistType::D => {
195                c0.mul_assign_by_fp(&p.y);
196                c1.mul_assign_by_fp(&p.x);
197                f.mul_by_034(&c0, &c1, &c2);
198            },
199        }
200    }
201
202    fn exp_by_neg_x(mut f: Fp12<P::Fp12Config>) -> Fp12<P::Fp12Config> {
203        f = f.cyclotomic_exp(P::X);
204        if !P::X_IS_NEGATIVE {
205            f.cyclotomic_inverse_in_place();
206        }
207        f
208    }
209}
210
211impl<P: BnConfig> Pairing for Bn<P> {
212    type BaseField = <P::G1Config as CurveConfig>::BaseField;
213    type ScalarField = <P::G1Config as CurveConfig>::ScalarField;
214    type G1 = G1Projective<P>;
215    type G1Affine = G1Affine<P>;
216    type G1Prepared = G1Prepared<P>;
217    type G2 = G2Projective<P>;
218    type G2Affine = G2Affine<P>;
219    type G2Prepared = G2Prepared<P>;
220    type TargetField = Fp12<P::Fp12Config>;
221
222    fn multi_miller_loop(
223        a: impl IntoIterator<Item = impl Into<Self::G1Prepared>>,
224        b: impl IntoIterator<Item = impl Into<Self::G2Prepared>>,
225    ) -> MillerLoopOutput<Self> {
226        P::multi_miller_loop(a, b)
227    }
228
229    fn final_exponentiation(f: MillerLoopOutput<Self>) -> Option<PairingOutput<Self>> {
230        P::final_exponentiation(f)
231    }
232}
ark_ec/models/bn/mod.rs

ark_ec/models/bn/
mod.rs
