ark_bls12_377/curves/
g2.rs

1use ark_ec::{
2    bls12,
3    bls12::Bls12Config,
4    hashing::curve_maps::wb::{IsogenyMap, WBConfig},
5    scalar_mul::glv::GLVConfig,
6    short_weierstrass::{Affine, Projective, SWCurveConfig},
7    AffineRepr, CurveConfig, CurveGroup, PrimeGroup,
8};
9
10use ark_ff::{AdditiveGroup, BigInt, Field, MontFp, PrimeField, Zero};
11use ark_std::ops::Neg;
12
13use crate::*;
14
15use super::g2_swu_iso::{SwuIsoConfig, ISOGENY_MAP_TO_G2};
16
17pub type G2Affine = bls12::G2Affine<crate::Config>;
18pub type G2Projective = bls12::G2Projective<crate::Config>;
19
20#[derive(Clone, Default, PartialEq, Eq)]
21pub struct Config;
22
23impl CurveConfig for Config {
24    type BaseField = Fq2;
25    type ScalarField = Fr;
26
27    /// COFACTOR =
28    /// 7923214915284317143930293550643874566881017850177945424769256759165301436616933228209277966774092486467289478618404761412630691835764674559376407658497
29    #[rustfmt::skip]
30    const COFACTOR: &'static [u64] = &[
31        0x0000000000000001,
32        0x452217cc90000000,
33        0xa0f3622fba094800,
34        0xd693e8c36676bd09,
35        0x8c505634fae2e189,
36        0xfbb36b00e1dcc40c,
37        0xddd88d99a6f6a829,
38        0x26ba558ae9562a,
39    ];
40
41    /// COFACTOR_INV = COFACTOR^{-1} mod r
42    /// = 6764900296503390671038341982857278410319949526107311149686707033187604810669
43    const COFACTOR_INV: Fr =
44        MontFp!("6764900296503390671038341982857278410319949526107311149686707033187604810669");
45}
46
47impl SWCurveConfig for Config {
48    /// COEFF_A = [0, 0]
49    const COEFF_A: Fq2 = Fq2::new(g1::Config::COEFF_A, g1::Config::COEFF_A);
50
51    // As per https://eprint.iacr.org/2012/072.pdf,
52    // this curve has b' = b/i, where b is the COEFF_B of G1, and x^6 -i is
53    // the irreducible poly used to extend from Fp2 to Fp12.
54    // In our case, i = u (App A.3, T_6).
55    /// COEFF_B = [0,
56    /// 155198655607781456406391640216936120121836107652948796323930557600032281009004493664981332883744016074664192874906]
57    const COEFF_B: Fq2 = Fq2::new(
58        Fq::ZERO,
59        MontFp!("155198655607781456406391640216936120121836107652948796323930557600032281009004493664981332883744016074664192874906"),
60    );
61
62    /// AFFINE_GENERATOR_COEFFS = (G2_GENERATOR_X, G2_GENERATOR_Y)
63    const GENERATOR: G2Affine = G2Affine::new_unchecked(G2_GENERATOR_X, G2_GENERATOR_Y);
64
65    #[inline(always)]
66    fn mul_by_a(_: Self::BaseField) -> Self::BaseField {
67        Self::BaseField::zero()
68    }
69
70    #[inline]
71    fn clear_cofactor(p: &G2Affine) -> G2Affine {
72        // Based on Section 4.1 of https://eprint.iacr.org/2017/419.pdf
73        // [h(ψ)]P = [x^2 − x − 1]P + [x − 1]ψ(P) + (ψ^2)(2P)
74
75        let x: &'static [u64] = crate::Config::X;
76        let p_projective = p.into_group();
77
78        // [x]P
79        let x_p = Config::mul_affine(p, x);
80        // ψ(P)
81        let psi_p = p_power_endomorphism(p);
82        // (ψ^2)(2P)
83        let mut psi2_p2 = double_p_power_endomorphism(&p_projective.double());
84
85        // tmp = [x]P + ψ(P)
86        let mut tmp = x_p;
87        tmp += &psi_p;
88
89        // tmp2 = [x^2]P + [x]ψ(P)
90        let mut tmp2: Projective<Config> = tmp;
91        tmp2 = tmp2.mul_bigint(x);
92
93        // add up all the terms
94        psi2_p2 += tmp2;
95        psi2_p2 -= x_p;
96        psi2_p2 += &-psi_p;
97        (psi2_p2 - p_projective).into_affine()
98    }
99}
100
101impl GLVConfig for Config {
102    const ENDO_COEFFS: &'static[Self::BaseField] = &[
103        Fq2::new(
104            MontFp!("258664426012969093929703085429980814127835149614277183275038967946009968870203535512256352201271898244626862047231"),
105            Fq::ZERO
106        )
107    ];
108
109    const LAMBDA: Self::ScalarField = MontFp!("91893752504881257701523279626832445440");
110
111    const SCALAR_DECOMP_COEFFS: [(bool, <Self::ScalarField as PrimeField>::BigInt); 4] = [
112        (false, BigInt!("91893752504881257701523279626832445440")),
113        (true, BigInt!("1")),
114        (false, BigInt!("1")),
115        (false, BigInt!("91893752504881257701523279626832445441")),
116    ];
117
118    fn endomorphism(p: &Projective<Self>) -> Projective<Self> {
119        let mut res = (*p).clone();
120        res.x *= Self::ENDO_COEFFS[0];
121        res
122    }
123
124    fn endomorphism_affine(p: &Affine<Self>) -> Affine<Self> {
125        let mut res = (*p).clone();
126        res.x *= Self::ENDO_COEFFS[0];
127        res
128    }
129}
130
131pub const G2_GENERATOR_X: Fq2 = Fq2::new(G2_GENERATOR_X_C0, G2_GENERATOR_X_C1);
132pub const G2_GENERATOR_Y: Fq2 = Fq2::new(G2_GENERATOR_Y_C0, G2_GENERATOR_Y_C1);
133
134/// G2_GENERATOR_X_C0 =
135/// 233578398248691099356572568220835526895379068987715365179118596935057653620464273615301663571204657964920925606294
136pub const G2_GENERATOR_X_C0: Fq = MontFp!("233578398248691099356572568220835526895379068987715365179118596935057653620464273615301663571204657964920925606294");
137
138/// G2_GENERATOR_X_C1 =
139/// 140913150380207355837477652521042157274541796891053068589147167627541651775299824604154852141315666357241556069118
140pub const G2_GENERATOR_X_C1: Fq = MontFp!("140913150380207355837477652521042157274541796891053068589147167627541651775299824604154852141315666357241556069118");
141
142/// G2_GENERATOR_Y_C0 =
143/// 63160294768292073209381361943935198908131692476676907196754037919244929611450776219210369229519898517858833747423
144pub const G2_GENERATOR_Y_C0: Fq = MontFp!("63160294768292073209381361943935198908131692476676907196754037919244929611450776219210369229519898517858833747423");
145
146/// G2_GENERATOR_Y_C1 =
147/// 149157405641012693445398062341192467754805999074082136895788947234480009303640899064710353187729182149407503257491
148pub const G2_GENERATOR_Y_C1: Fq = MontFp!("149157405641012693445398062341192467754805999074082136895788947234480009303640899064710353187729182149407503257491");
149
150// PSI_X = u^((p-1)/3)
151const P_POWER_ENDOMORPHISM_COEFF_0 : Fq2 = Fq2::new(
152    MontFp!(
153        "80949648264912719408558363140637477264845294720710499478137287262712535938301461879813459410946"
154    ),
155    Fq::ZERO,
156);
157
158// PSI_Y = u^((p-1)/2)
159const P_POWER_ENDOMORPHISM_COEFF_1: Fq2 = Fq2::new(
160    MontFp!(
161        "216465761340224619389371505802605247630151569547285782856803747159100223055385581585702401816380679166954762214499"),
162        Fq::ZERO,
163    );
164
165// PSI_2_X = u^((p^2 - 1)/3)
166const DOUBLE_P_POWER_ENDOMORPHISM_COEFF_0: Fq2 = Fq2::new(
167        MontFp!("80949648264912719408558363140637477264845294720710499478137287262712535938301461879813459410945"),
168        Fq::ZERO
169    );
170
171/// psi(x,y) is the untwist-Frobenius-twist endomorhism on E'(Fq2)
172fn p_power_endomorphism(p: &Affine<Config>) -> Affine<Config> {
173    // The p-power endomorphism for G2 is defined as follows:
174    // 1. Note that G2 is defined on curve E': y^2 = x^3 + 1/u.
175    //    To map a point (x, y) in E' to (s, t) in E,
176    //    one set s = x * (u ^ (1/3)), t = y * (u ^ (1/2)),
177    //    because E: y^2 = x^3 + 1.
178    // 2. Apply the Frobenius endomorphism (s, t) => (s', t'),
179    //    another point on curve E, where s' = s^p, t' = t^p.
180    // 3. Map the point from E back to E'; that is,
181    //    one set x' = s' / ((u) ^ (1/3)), y' = t' / ((u) ^ (1/2)).
182    //
183    // To sum up, it maps
184    // (x,y) -> (x^p * (u ^ ((p-1)/3)), y^p * (u ^ ((p-1)/2)))
185    // as implemented in the code as follows.
186
187    let mut res = *p;
188    res.x.frobenius_map_in_place(1);
189    res.y.frobenius_map_in_place(1);
190
191    res.x *= P_POWER_ENDOMORPHISM_COEFF_0;
192    res.y *= P_POWER_ENDOMORPHISM_COEFF_1;
193
194    res
195}
196
197/// For a p-power endomorphism psi(P), compute psi(psi(P))
198fn double_p_power_endomorphism(p: &Projective<Config>) -> Projective<Config> {
199    // p_power_endomorphism(&p_power_endomorphism(&p.into_affine())).into()
200    let mut res = *p;
201
202    res.x *= DOUBLE_P_POWER_ENDOMORPHISM_COEFF_0;
203    // u^((p^2 - 1)/2) == -1
204    res.y = res.y.neg();
205
206    res
207}
208
209impl WBConfig for Config {
210    type IsogenousCurve = SwuIsoConfig;
211
212    const ISOGENY_MAP: IsogenyMap<'static, Self::IsogenousCurve, Self> = ISOGENY_MAP_TO_G2;
213}
214
215#[cfg(test)]
216mod test {
217
218    use super::*;
219    use ark_std::{rand::Rng, UniformRand};
220
221    fn sample_unchecked() -> Affine<g2::Config> {
222        let mut rng = ark_std::test_rng();
223        loop {
224            let x1 = Fq::rand(&mut rng);
225            let x2 = Fq::rand(&mut rng);
226            let greatest = rng.gen();
227            let x = Fq2::new(x1, x2);
228
229            if let Some(p) = Affine::get_point_from_x_unchecked(x, greatest) {
230                return p;
231            }
232        }
233    }
234
235    #[test]
236    fn test_psi_2() {
237        let p = sample_unchecked();
238        let psi_p = p_power_endomorphism(&p);
239        let psi2_p_composed = p_power_endomorphism(&psi_p);
240        let psi2_p_optimised = double_p_power_endomorphism(&p.into());
241
242        assert_eq!(psi2_p_composed, psi2_p_optimised);
243    }
244
245    #[test]
246    fn test_cofactor_clearing() {
247        let h_eff = &[
248            0x1e34800000000000,
249            0xcf664765b0000003,
250            0x8e8e73ad8a538800,
251            0x78ba279637388559,
252            0xb85860aaaad29276,
253            0xf7ee7c4b03103b45,
254            0x8f6ade35a5c7d769,
255            0xa951764c46f4edd2,
256            0x53648d3d9502abfb,
257            0x1f60243677e306,
258        ];
259        const SAMPLES: usize = 10;
260        for _ in 0..SAMPLES {
261            let p: Affine<g2::Config> = sample_unchecked();
262            let optimised = p.clear_cofactor();
263            let naive = g2::Config::mul_affine(&p, h_eff);
264            assert_eq!(optimised.into_group(), naive);
265            assert!(optimised.is_on_curve());
266            assert!(optimised.is_in_correct_subgroup_assuming_on_curve());
267        }
268    }
269}
ark_bls12_377/curves/g2.rs

ark_bls12_377/curves/
g2.rs
