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