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: &'static [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: &'static [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    #[allow(clippy::let_and_return)]
106    fn final_exponentiation(f: MillerLoopOutput<Bn<Self>>) -> Option<PairingOutput<Bn<Self>>> {
107        // Easy part: result = elt^((q^6-1)*(q^2+1)).
108        // Follows, e.g., Beuchat et al page 9, by computing result as follows:
109        //   elt^((q^6-1)*(q^2+1)) = (conj(elt) * elt^(-1))^(q^2+1)
110        let f = f.0;
111
112        // f1 = r.cyclotomic_inverse_in_place() = f^(p^6)
113        let mut f1 = f;
114        f1.cyclotomic_inverse_in_place();
115
116        f.inverse().map(|mut f2| {
117            // f2 = f^(-1);
118            // r = f^(p^6 - 1)
119            let mut r = f1 * &f2;
120
121            // f2 = f^(p^6 - 1)
122            f2 = r;
123            // r = f^((p^6 - 1)(p^2))
124            r.frobenius_map_in_place(2);
125
126            // r = f^((p^6 - 1)(p^2) + (p^6 - 1))
127            // r = f^((p^6 - 1)(p^2 + 1))
128            r *= &f2;
129
130            // Hard part follows Laura Fuentes-Castaneda et al. "Faster hashing to G2"
131            // by computing:
132            //
133            // result = elt^(q^3 * (12*z^3 + 6z^2 + 4z - 1) +
134            //               q^2 * (12*z^3 + 6z^2 + 6z) +
135            //               q   * (12*z^3 + 6z^2 + 4z) +
136            //               1   * (12*z^3 + 12z^2 + 6z + 1))
137            // which equals
138            //
139            // result = elt^( 2z * ( 6z^2 + 3z + 1 ) * (q^4 - q^2 + 1)/r ).
140
141            let y0 = Bn::<Self>::exp_by_neg_x(r);
142            let y1 = y0.cyclotomic_square();
143            let y2 = y1.cyclotomic_square();
144            let mut y3 = y2 * &y1;
145            let y4 = Bn::<Self>::exp_by_neg_x(y3);
146            let y5 = y4.cyclotomic_square();
147            let mut y6 = Bn::<Self>::exp_by_neg_x(y5);
148            y3.cyclotomic_inverse_in_place();
149            y6.cyclotomic_inverse_in_place();
150            let y7 = y6 * &y4;
151            let mut y8 = y7 * &y3;
152            let y9 = y8 * &y1;
153            let y10 = y8 * &y4;
154            let y11 = y10 * &r;
155            let mut y12 = y9;
156            y12.frobenius_map_in_place(1);
157            let y13 = y12 * &y11;
158            y8.frobenius_map_in_place(2);
159            let y14 = y8 * &y13;
160            r.cyclotomic_inverse_in_place();
161            let mut y15 = r * &y9;
162            y15.frobenius_map_in_place(3);
163            let y16 = y15 * &y14;
164
165            PairingOutput(y16)
166        })
167    }
168}
169
170pub mod g1;
171pub mod g2;
172
173pub use self::{
174    g1::{G1Affine, G1Prepared, G1Projective},
175    g2::{G2Affine, G2Prepared, G2Projective},
176};
177
178#[derive(Educe)]
179#[educe(Copy, Clone, PartialEq, Eq, Debug, Hash)]
180pub struct Bn<P: BnConfig>(PhantomData<fn() -> P>);
181
182impl<P: BnConfig> Bn<P> {
183    /// Evaluates the line function at point p.
184    fn ell(f: &mut Fp12<P::Fp12Config>, coeffs: &g2::EllCoeff<P>, p: &G1Affine<P>) {
185        let mut c0 = coeffs.0;
186        let mut c1 = coeffs.1;
187        let mut c2 = coeffs.2;
188
189        match P::TWIST_TYPE {
190            TwistType::M => {
191                c2.mul_assign_by_fp(&p.y);
192                c1.mul_assign_by_fp(&p.x);
193                f.mul_by_014(&c0, &c1, &c2);
194            },
195            TwistType::D => {
196                c0.mul_assign_by_fp(&p.y);
197                c1.mul_assign_by_fp(&p.x);
198                f.mul_by_034(&c0, &c1, &c2);
199            },
200        }
201    }
202
203    fn exp_by_neg_x(mut f: Fp12<P::Fp12Config>) -> Fp12<P::Fp12Config> {
204        f = f.cyclotomic_exp(P::X);
205        if !P::X_IS_NEGATIVE {
206            f.cyclotomic_inverse_in_place();
207        }
208        f
209    }
210}
211
212impl<P: BnConfig> Pairing for Bn<P> {
213    type BaseField = <P::G1Config as CurveConfig>::BaseField;
214    type ScalarField = <P::G1Config as CurveConfig>::ScalarField;
215    type G1 = G1Projective<P>;
216    type G1Affine = G1Affine<P>;
217    type G1Prepared = G1Prepared<P>;
218    type G2 = G2Projective<P>;
219    type G2Affine = G2Affine<P>;
220    type G2Prepared = G2Prepared<P>;
221    type TargetField = Fp12<P::Fp12Config>;
222
223    fn multi_miller_loop(
224        a: impl IntoIterator<Item = impl Into<Self::G1Prepared>>,
225        b: impl IntoIterator<Item = impl Into<Self::G2Prepared>>,
226    ) -> MillerLoopOutput<Self> {
227        P::multi_miller_loop(a, b)
228    }
229
230    fn final_exponentiation(f: MillerLoopOutput<Self>) -> Option<PairingOutput<Self>> {
231        P::final_exponentiation(f)
232    }
233}
ark_ec/models/bn/mod.rs

ark_ec/models/bn/
mod.rs
