ark_bls12_381/curves/
g2.rs

Help
1use ark_std::ops::Neg;
2
3use ark_ec::{
4    bls12,
5    bls12::Bls12Config,
6    hashing::curve_maps::wb::{IsogenyMap, WBConfig},
7    models::CurveConfig,
8    scalar_mul::glv::GLVConfig,
9    short_weierstrass::{Affine, Projective, SWCurveConfig},
10    AffineRepr, CurveGroup, PrimeGroup,
11};
12use ark_ff::{AdditiveGroup, BigInt, Field, MontFp, PrimeField, Zero};
13use ark_serialize::{Compress, SerializationError};
14
15use super::{
16    g2_swu_iso,
17    util::{serialize_fq, EncodingFlags, G2_SERIALIZED_SIZE},
18};
19use crate::{
20    util::{read_g2_compressed, read_g2_uncompressed},
21    *,
22};
23
24pub type G2Affine = bls12::G2Affine<crate::Config>;
25pub type G2Projective = bls12::G2Projective<crate::Config>;
26
27#[derive(Clone, Default, PartialEq, Eq)]
28pub struct Config;
29
30impl CurveConfig for Config {
31    type BaseField = Fq2;
32    type ScalarField = Fr;
33
34    /// COFACTOR = (x^8 - 4 x^7 + 5 x^6) - (4 x^4 + 6 x^3 - 4 x^2 - 4 x + 13) //
35    /// 9
36    /// = 305502333931268344200999753193121504214466019254188142667664032982267604182971884026507427359259977847832272839041616661285803823378372096355777062779109
37    #[rustfmt::skip]
38    const COFACTOR: &'static [u64] = &[
39        0xcf1c38e31c7238e5,
40        0x1616ec6e786f0c70,
41        0x21537e293a6691ae,
42        0xa628f1cb4d9e82ef,
43        0xa68a205b2e5a7ddf,
44        0xcd91de4547085aba,
45        0x91d50792876a202,
46        0x5d543a95414e7f1,
47    ];
48
49    /// COFACTOR_INV = COFACTOR^{-1} mod r
50    /// 26652489039290660355457965112010883481355318854675681319708643586776743290055
51    const COFACTOR_INV: Fr =
52        MontFp!("26652489039290660355457965112010883481355318854675681319708643586776743290055");
53}
54
55impl SWCurveConfig for Config {
56    /// COEFF_A = [0, 0]
57    const COEFF_A: Fq2 = Fq2::new(g1::Config::COEFF_A, g1::Config::COEFF_A);
58
59    /// COEFF_B = [4, 4]
60    const COEFF_B: Fq2 = Fq2::new(g1::Config::COEFF_B, g1::Config::COEFF_B);
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    fn is_in_correct_subgroup_assuming_on_curve(point: &G2Affine) -> bool {
71        // Algorithm from Section 4 of https://eprint.iacr.org/2021/1130.
72        //
73        // Checks that [p]P = [X]P
74
75        let mut x_times_point = point.mul_bigint(crate::Config::X);
76        if crate::Config::X_IS_NEGATIVE {
77            x_times_point = -x_times_point;
78        }
79
80        let p_times_point = p_power_endomorphism(point);
81
82        x_times_point.eq(&p_times_point)
83    }
84
85    #[inline]
86    fn clear_cofactor(p: &G2Affine) -> G2Affine {
87        // Based on Section 4.1 of https://eprint.iacr.org/2017/419.pdf
88        // [h(ψ)]P = [x^2 − x − 1]P + [x − 1]ψ(P) + (ψ^2)(2P)
89
90        // x = -15132376222941642752
91        // When multiplying, use -c1 instead, and then negate the result. That's much
92        // more efficient, since the scalar -c1 has less limbs and a much lower Hamming
93        // weight.
94        let x: &'static [u64] = crate::Config::X;
95        let p_projective = p.into_group();
96
97        // [x]P
98        let x_p = Config::mul_affine(p, &x).neg();
99        // ψ(P)
100        let psi_p = p_power_endomorphism(&p);
101        // (ψ^2)(2P)
102        let mut psi2_p2 = double_p_power_endomorphism(&p_projective.double());
103
104        // tmp = [x]P + ψ(P)
105        let mut tmp = x_p.clone();
106        tmp += &psi_p;
107
108        // tmp2 = [x^2]P + [x]ψ(P)
109        let mut tmp2: Projective<Config> = tmp;
110        tmp2 = tmp2.mul_bigint(x).neg();
111
112        // add up all the terms
113        psi2_p2 += tmp2;
114        psi2_p2 -= x_p;
115        psi2_p2 += &-psi_p;
116        (psi2_p2 - p_projective).into_affine()
117    }
118
119    fn deserialize_with_mode<R: ark_serialize::Read>(
120        mut reader: R,
121        compress: ark_serialize::Compress,
122        validate: ark_serialize::Validate,
123    ) -> Result<Affine<Self>, ark_serialize::SerializationError> {
124        let p = if compress == ark_serialize::Compress::Yes {
125            read_g2_compressed(&mut reader)?
126        } else {
127            read_g2_uncompressed(&mut reader)?
128        };
129
130        if validate == ark_serialize::Validate::Yes && !p.is_in_correct_subgroup_assuming_on_curve()
131        {
132            return Err(SerializationError::InvalidData);
133        }
134        Ok(p)
135    }
136
137    fn serialize_with_mode<W: ark_serialize::Write>(
138        item: &Affine<Self>,
139        mut writer: W,
140        compress: ark_serialize::Compress,
141    ) -> Result<(), SerializationError> {
142        let encoding = EncodingFlags {
143            is_compressed: compress == ark_serialize::Compress::Yes,
144            is_infinity: item.is_zero(),
145            is_lexographically_largest: item.y > -item.y,
146        };
147        let mut p = *item;
148        if encoding.is_infinity {
149            p = G2Affine::zero();
150        }
151
152        let mut x_bytes = [0u8; G2_SERIALIZED_SIZE];
153        let c1_bytes = serialize_fq(p.x.c1);
154        let c0_bytes = serialize_fq(p.x.c0);
155        x_bytes[0..48].copy_from_slice(&c1_bytes[..]);
156        x_bytes[48..96].copy_from_slice(&c0_bytes[..]);
157        if encoding.is_compressed {
158            let mut bytes: [u8; G2_SERIALIZED_SIZE] = x_bytes;
159
160            encoding.encode_flags(&mut bytes);
161            writer.write_all(&bytes)?;
162        } else {
163            let mut bytes = [0u8; 2 * G2_SERIALIZED_SIZE];
164
165            let mut y_bytes = [0u8; G2_SERIALIZED_SIZE];
166            let c1_bytes = serialize_fq(p.y.c1);
167            let c0_bytes = serialize_fq(p.y.c0);
168            y_bytes[0..48].copy_from_slice(&c1_bytes[..]);
169            y_bytes[48..96].copy_from_slice(&c0_bytes[..]);
170            bytes[0..G2_SERIALIZED_SIZE].copy_from_slice(&x_bytes);
171            bytes[G2_SERIALIZED_SIZE..].copy_from_slice(&y_bytes);
172
173            encoding.encode_flags(&mut bytes);
174            writer.write_all(&bytes)?;
175        };
176
177        Ok(())
178    }
179
180    fn serialized_size(compress: ark_serialize::Compress) -> usize {
181        if compress == Compress::Yes {
182            G2_SERIALIZED_SIZE
183        } else {
184            2 * G2_SERIALIZED_SIZE
185        }
186    }
187}
188
189impl GLVConfig for Config {
190    const ENDO_COEFFS: &'static[Self::BaseField] = &[
191        Fq2::new(
192            MontFp!("793479390729215512621379701633421447060886740281060493010456487427281649075476305620758731620350"),
193            Fq::ZERO
194        )
195    ];
196
197    const LAMBDA: Self::ScalarField = MontFp!("228988810152649578064853576960394133503");
198
199    const SCALAR_DECOMP_COEFFS: [(bool, <Self::ScalarField as PrimeField>::BigInt); 4] = [
200        (false, BigInt!("228988810152649578064853576960394133503")),
201        (true, BigInt!("1")),
202        (false, BigInt!("1")),
203        (false, BigInt!("228988810152649578064853576960394133504")),
204    ];
205
206    fn endomorphism(p: &Projective<Self>) -> Projective<Self> {
207        let mut res = (*p).clone();
208        res.x *= Self::ENDO_COEFFS[0];
209        res
210    }
211
212    fn endomorphism_affine(p: &Affine<Self>) -> Affine<Self> {
213        let mut res = (*p).clone();
214        res.x *= Self::ENDO_COEFFS[0];
215        res
216    }
217}
218
219pub const G2_GENERATOR_X: Fq2 = Fq2::new(G2_GENERATOR_X_C0, G2_GENERATOR_X_C1);
220pub const G2_GENERATOR_Y: Fq2 = Fq2::new(G2_GENERATOR_Y_C0, G2_GENERATOR_Y_C1);
221
222/// G2_GENERATOR_X_C0 =
223/// 352701069587466618187139116011060144890029952792775240219908644239793785735715026873347600343865175952761926303160
224pub const G2_GENERATOR_X_C0: Fq = MontFp!("352701069587466618187139116011060144890029952792775240219908644239793785735715026873347600343865175952761926303160");
225
226/// G2_GENERATOR_X_C1 =
227/// 3059144344244213709971259814753781636986470325476647558659373206291635324768958432433509563104347017837885763365758
228pub const G2_GENERATOR_X_C1: Fq = MontFp!("3059144344244213709971259814753781636986470325476647558659373206291635324768958432433509563104347017837885763365758");
229
230/// G2_GENERATOR_Y_C0 =
231/// 1985150602287291935568054521177171638300868978215655730859378665066344726373823718423869104263333984641494340347905
232pub const G2_GENERATOR_Y_C0: Fq = MontFp!("1985150602287291935568054521177171638300868978215655730859378665066344726373823718423869104263333984641494340347905");
233
234/// G2_GENERATOR_Y_C1 =
235/// 927553665492332455747201965776037880757740193453592970025027978793976877002675564980949289727957565575433344219582
236pub const G2_GENERATOR_Y_C1: Fq = MontFp!("927553665492332455747201965776037880757740193453592970025027978793976877002675564980949289727957565575433344219582");
237
238// PSI_X = 1/(u+1)^((p-1)/3)
239const P_POWER_ENDOMORPHISM_COEFF_0 : Fq2 = Fq2::new(
240    Fq::ZERO,
241    MontFp!(
242                "4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939437"
243    )
244);
245
246// PSI_Y = 1/(u+1)^((p-1)/2)
247const P_POWER_ENDOMORPHISM_COEFF_1: Fq2 = Fq2::new(
248    MontFp!(
249                "2973677408986561043442465346520108879172042883009249989176415018091420807192182638567116318576472649347015917690530"),
250    MontFp!(
251       "1028732146235106349975324479215795277384839936929757896155643118032610843298655225875571310552543014690878354869257")
252);
253
254// PSI_2_X = (u+1)^((1-p^2)/3)
255const DOUBLE_P_POWER_ENDOMORPHISM_COEFF_0: Fq2 = Fq2::new(
256    MontFp!("4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939436"),
257    Fq::ZERO
258);
259
260/// psi(P) is the untwist-Frobenius-twist endomorphism on E'(Fq2)
261fn p_power_endomorphism(p: &Affine<Config>) -> Affine<Config> {
262    // The p-power endomorphism for G2 is defined as follows:
263    // 1. Note that G2 is defined on curve E': y^2 = x^3 + 4(u+1).
264    //    To map a point (x, y) in E' to (s, t) in E,
265    //    set s = x / ((u+1) ^ (1/3)), t = y / ((u+1) ^ (1/2)),
266    //    because E: y^2 = x^3 + 4.
267    // 2. Apply the Frobenius endomorphism (s, t) => (s', t'),
268    //    another point on curve E, where s' = s^p, t' = t^p.
269    // 3. Map the point from E back to E'; that is,
270    //    set x' = s' * ((u+1) ^ (1/3)), y' = t' * ((u+1) ^ (1/2)).
271    //
272    // To sum up, it maps
273    // (x,y) -> (x^p / ((u+1)^((p-1)/3)), y^p / ((u+1)^((p-1)/2)))
274    // as implemented in the code as follows.
275
276    let mut res = *p;
277    res.x.frobenius_map_in_place(1);
278    res.y.frobenius_map_in_place(1);
279
280    let tmp_x = res.x.clone();
281    res.x.c0 = -P_POWER_ENDOMORPHISM_COEFF_0.c1 * &tmp_x.c1;
282    res.x.c1 = P_POWER_ENDOMORPHISM_COEFF_0.c1 * &tmp_x.c0;
283    res.y *= P_POWER_ENDOMORPHISM_COEFF_1;
284
285    res
286}
287
288/// For a p-power endomorphism psi(P), compute psi(psi(P))
289fn double_p_power_endomorphism(p: &Projective<Config>) -> Projective<Config> {
290    let mut res = *p;
291
292    res.x *= DOUBLE_P_POWER_ENDOMORPHISM_COEFF_0;
293    res.y = res.y.neg();
294
295    res
296}
297
298// Parameters from the [IETF draft v16, section E.3](https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-16.html#name-3-isogeny-map-for-bls12-381).
299impl WBConfig for Config {
300    type IsogenousCurve = g2_swu_iso::SwuIsoConfig;
301
302    const ISOGENY_MAP: IsogenyMap<'static, Self::IsogenousCurve, Self> =
303        g2_swu_iso::ISOGENY_MAP_TO_G2;
304}
305
306#[cfg(test)]
307mod test {
308
309    use super::*;
310    use ark_std::{rand::Rng, UniformRand};
311
312    fn sample_unchecked() -> Affine<g2::Config> {
313        let mut rng = ark_std::test_rng();
314        loop {
315            let x1 = Fq::rand(&mut rng);
316            let x2 = Fq::rand(&mut rng);
317            let greatest = rng.gen();
318            let x = Fq2::new(x1, x2);
319
320            if let Some(p) = Affine::get_point_from_x_unchecked(x, greatest) {
321                return p;
322            }
323        }
324    }
325
326    #[test]
327    fn test_psi_2() {
328        let p = sample_unchecked();
329        let psi_p = p_power_endomorphism(&p);
330        let psi2_p_composed = p_power_endomorphism(&psi_p);
331        let psi2_p_optimised = double_p_power_endomorphism(&p.into());
332
333        assert_eq!(psi2_p_composed, psi2_p_optimised);
334    }
335
336    #[test]
337    fn test_cofactor_clearing() {
338        // multiplying by h_eff and clearing the cofactor by the efficient
339        // endomorphism-based method should yield the same result.
340        let h_eff: &'static [u64] = &[
341            0xe8020005aaa95551,
342            0x59894c0adebbf6b4,
343            0xe954cbc06689f6a3,
344            0x2ec0ec69d7477c1a,
345            0x6d82bf015d1212b0,
346            0x329c2f178731db95,
347            0x9986ff031508ffe1,
348            0x88e2a8e9145ad768,
349            0x584c6a0ea91b3528,
350            0xbc69f08f2ee75b3,
351        ];
352
353        const SAMPLES: usize = 10;
354        for _ in 0..SAMPLES {
355            let p: Affine<g2::Config> = sample_unchecked();
356            let optimised = p.clear_cofactor();
357            let naive = g2::Config::mul_affine(&p, h_eff);
358            assert_eq!(optimised.into_group(), naive);
359            assert!(optimised.is_on_curve());
360            assert!(optimised.is_in_correct_subgroup_assuming_on_curve());
361        }
362    }
363}
ark_bls12_381/curves/g2.rs

ark_bls12_381/curves/
g2.rs
