ark-curves-cherry-picked/bls12_381/src/curves/g1.rs
bls12_381/src/curves/g1.rsRaw
1use ark_ec::{
2 bls12,
3 bls12::Bls12Config,
4 hashing::curve_maps::wb::{IsogenyMap, WBConfig},
5 models::CurveConfig,
6 short_weierstrass::{Affine, SWCurveConfig},
7 AffineRepr, PrimeGroup,
8};
9use ark_ff::{AdditiveGroup, MontFp, PrimeField, Zero};
10use ark_serialize::{Compress, SerializationError};
11use ark_std::{ops::Neg, One};
12
13use super::g1_swu_iso;
14use crate::{
15 util::{
16 read_g1_compressed, read_g1_uncompressed, serialize_fq, EncodingFlags, G1_SERIALIZED_SIZE,
17 },
18 Fq, Fr,
19};
20
21pub type G1Affine = bls12::G1Affine<crate::Config>;
22pub type G1Projective = bls12::G1Projective<crate::Config>;
23
24#[derive(Clone, Default, PartialEq, Eq)]
25pub struct Config;
26
27impl CurveConfig for Config {
28 type BaseField = Fq;
29 type ScalarField = Fr;
30
31 /// COFACTOR = (x - 1)^2 / 3 = 76329603384216526031706109802092473003
32 const COFACTOR: &'static [u64] = &[0x8c00aaab0000aaab, 0x396c8c005555e156];
33
34 /// COFACTOR_INV = COFACTOR^{-1} mod r
35 /// = 52435875175126190458656871551744051925719901746859129887267498875565241663483
36 const COFACTOR_INV: Fr =
37 MontFp!("52435875175126190458656871551744051925719901746859129887267498875565241663483");
38}
39
40impl SWCurveConfig for Config {
41 /// COEFF_A = 0
42 const COEFF_A: Fq = Fq::ZERO;
43
44 /// COEFF_B = 4
45 const COEFF_B: Fq = MontFp!("4");
46
47 /// AFFINE_GENERATOR_COEFFS = (G1_GENERATOR_X, G1_GENERATOR_Y)
48 const GENERATOR: G1Affine = G1Affine::new_unchecked(G1_GENERATOR_X, G1_GENERATOR_Y);
49
50 #[inline(always)]
51 fn mul_by_a(_: Self::BaseField) -> Self::BaseField {
52 Self::BaseField::zero()
53 }
54
55 #[inline]
56 fn is_in_correct_subgroup_assuming_on_curve(p: &G1Affine) -> bool {
57 // Algorithm from Section 6 of https://eprint.iacr.org/2021/1130.
58 //
59 // Check that endomorphism_p(P) == -[X^2]P
60
61 // An early-out optimization described in Section 6.
62 // If uP == P but P != point of infinity, then the point is not in the right
63 // subgroup.
64 let x_times_p = p.mul_bigint(crate::Config::X);
65 if x_times_p.eq(p) && !p.infinity {
66 return false;
67 }
68
69 let minus_x_squared_times_p = x_times_p.mul_bigint(crate::Config::X).neg();
70 let endomorphism_p = endomorphism(p);
71 minus_x_squared_times_p.eq(&endomorphism_p)
72 }
73
74 #[inline]
75 fn clear_cofactor(p: &G1Affine) -> G1Affine {
76 // Using the effective cofactor, as explained in
77 // Section 5 of https://eprint.iacr.org/2019/403.pdf.
78 //
79 // It is enough to multiply by (1 - x), instead of (x - 1)^2 / 3
80 let h_eff = one_minus_x().into_bigint();
81 Config::mul_affine(&p, h_eff.as_ref()).into()
82 }
83
84 fn deserialize_with_mode<R: ark_serialize::Read>(
85 mut reader: R,
86 compress: ark_serialize::Compress,
87 validate: ark_serialize::Validate,
88 ) -> Result<Affine<Self>, ark_serialize::SerializationError> {
89 let p = if compress == ark_serialize::Compress::Yes {
90 read_g1_compressed(&mut reader)?
91 } else {
92 read_g1_uncompressed(&mut reader)?
93 };
94
95 if validate == ark_serialize::Validate::Yes && !p.is_in_correct_subgroup_assuming_on_curve()
96 {
97 return Err(SerializationError::InvalidData);
98 }
99 Ok(p)
100 }
101
102 fn serialize_with_mode<W: ark_serialize::Write>(
103 item: &Affine<Self>,
104 mut writer: W,
105 compress: ark_serialize::Compress,
106 ) -> Result<(), SerializationError> {
107 let encoding = EncodingFlags {
108 is_compressed: compress == ark_serialize::Compress::Yes,
109 is_infinity: item.is_zero(),
110 is_lexographically_largest: item.y > -item.y,
111 };
112 let mut p = *item;
113 if encoding.is_infinity {
114 p = G1Affine::zero();
115 }
116 // need to access the field struct `x` directly, otherwise we get None from xy()
117 // method
118 let x_bytes = serialize_fq(p.x);
119 if encoding.is_compressed {
120 let mut bytes: [u8; G1_SERIALIZED_SIZE] = x_bytes;
121
122 encoding.encode_flags(&mut bytes);
123 writer.write_all(&bytes)?;
124 } else {
125 let mut bytes = [0u8; 2 * G1_SERIALIZED_SIZE];
126 bytes[0..G1_SERIALIZED_SIZE].copy_from_slice(&x_bytes[..]);
127 bytes[G1_SERIALIZED_SIZE..].copy_from_slice(&serialize_fq(p.y)[..]);
128
129 encoding.encode_flags(&mut bytes);
130 writer.write_all(&bytes)?;
131 };
132
133 Ok(())
134 }
135
136 fn serialized_size(compress: Compress) -> usize {
137 if compress == Compress::Yes {
138 G1_SERIALIZED_SIZE
139 } else {
140 G1_SERIALIZED_SIZE * 2
141 }
142 }
143}
144
145fn one_minus_x() -> Fr {
146 const X: Fr = Fr::from_sign_and_limbs(!crate::Config::X_IS_NEGATIVE, crate::Config::X);
147 Fr::one() - X
148}
149
150// Parameters from the [IETF draft v16, section E.2](https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-16.html#name-11-isogeny-map-for-bls12-381).
151impl WBConfig for Config {
152 type IsogenousCurve = g1_swu_iso::SwuIsoConfig;
153
154 const ISOGENY_MAP: IsogenyMap<'static, Self::IsogenousCurve, Self> =
155 g1_swu_iso::ISOGENY_MAP_TO_G1;
156}
157
158/// G1_GENERATOR_X =
159/// 3685416753713387016781088315183077757961620795782546409894578378688607592378376318836054947676345821548104185464507
160pub const G1_GENERATOR_X: Fq = MontFp!("3685416753713387016781088315183077757961620795782546409894578378688607592378376318836054947676345821548104185464507");
161
162/// G1_GENERATOR_Y =
163/// 1339506544944476473020471379941921221584933875938349620426543736416511423956333506472724655353366534992391756441569
164pub const G1_GENERATOR_Y: Fq = MontFp!("1339506544944476473020471379941921221584933875938349620426543736416511423956333506472724655353366534992391756441569");
165
166/// BETA is a non-trivial cubic root of unity in Fq.
167pub const BETA: Fq = MontFp!("793479390729215512621379701633421447060886740281060493010456487427281649075476305620758731620350");
168
169pub fn endomorphism(p: &Affine<Config>) -> Affine<Config> {
170 // Endomorphism of the points on the curve.
171 // endomorphism_p(x,y) = (BETA * x, y)
172 // where BETA is a non-trivial cubic root of unity in Fq.
173 let mut res = (*p).clone();
174 res.x *= BETA;
175 res
176}
177
178#[cfg(test)]
179mod test {
180
181 use super::*;
182 use crate::g1;
183 use ark_serialize::CanonicalDeserialize;
184 use ark_std::{rand::Rng, UniformRand};
185
186 fn sample_unchecked() -> Affine<g1::Config> {
187 let mut rng = ark_std::test_rng();
188 loop {
189 let x = Fq::rand(&mut rng);
190 let greatest = rng.gen();
191
192 if let Some(p) = Affine::get_point_from_x_unchecked(x, greatest) {
193 return p;
194 }
195 }
196 }
197
198 #[test]
199 fn test_cofactor_clearing() {
200 const SAMPLES: usize = 100;
201 for _ in 0..SAMPLES {
202 let p: Affine<g1::Config> = sample_unchecked();
203 let p = p.clear_cofactor();
204 assert!(p.is_on_curve());
205 assert!(p.is_in_correct_subgroup_assuming_on_curve());
206 }
207 }
208
209 #[test]
210 fn non_canonical_identity_point() {
211 let non_canonical_hex = "c01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
212 let non_canonical_bytes = hex::decode(non_canonical_hex).unwrap();
213 assert_eq!(non_canonical_bytes.len(), 48);
214
215 let maybe_affine_point: Result<G1Affine, ark_serialize::SerializationError> =
216 CanonicalDeserialize::deserialize_compressed(&non_canonical_bytes[..]);
217
218 assert!(maybe_affine_point.is_err());
219
220 let non_canonical_hex_uncompressed = "c00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001";
221 let non_canonical_bytes = hex::decode(non_canonical_hex_uncompressed).unwrap();
222 assert_eq!(non_canonical_bytes.len(), 96);
223
224 let maybe_affine_point: Result<G1Affine, ark_serialize::SerializationError> =
225 CanonicalDeserialize::deserialize_uncompressed(&non_canonical_bytes[..]);
226
227 assert!(maybe_affine_point.is_err())
228 }
229
230 #[test]
231 fn bad_flag_combination() {
232 // See https://github.com/zkcrypto/pairing/tree/fa8103764a07bd273927447d434de18aace252d3/src/bls12_381#serialization
233 // - Bit 1 is compressed/uncompressed
234 // - Bit 2 is infinity
235 // - Bit 3 is lexicographical order for compressed point deserialization
236 // Hence `0b1110` ("e" in hex) or `0b0110` ("6" in hex") are both nonsensical.
237
238 // uncompressed, but lexicographically largest flag is set
239 let non_canonical_hex = "600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
240 let non_canonical_bytes = hex::decode(non_canonical_hex).unwrap();
241 assert_eq!(non_canonical_bytes.len(), 48);
242
243 let maybe_affine_point: Result<G1Affine, ark_serialize::SerializationError> =
244 CanonicalDeserialize::deserialize_compressed(&non_canonical_bytes[..]);
245
246 assert!(maybe_affine_point.is_err());
247
248 // compressed, but infinity flag is set and lexicographically largest flag is
249 // set
250 let non_canonical_hex_2 = "e00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
251
252 let non_canonical_bytes = hex::decode(non_canonical_hex_2).unwrap();
253 assert_eq!(non_canonical_bytes.len(), 48);
254
255 let maybe_affine_point: Result<G1Affine, ark_serialize::SerializationError> =
256 CanonicalDeserialize::deserialize_compressed(&non_canonical_bytes[..]);
257 assert!(maybe_affine_point.is_err());
258 }
259}