airbender_crypto/bls12_381/curves/
g1.rs

1use ark_ec::{
2    bls12,
3    bls12::Bls12Config,
4    hashing::curve_maps::wb::{IsogenyMap, WBConfig},
5    models::CurveConfig,
6    scalar_mul::glv::GLVConfig,
7    short_weierstrass::{Affine, SWCurveConfig},
8    AffineRepr, PrimeGroup,
9};
10use ark_ff::{AdditiveGroup, One, PrimeField, Zero};
11use ruint::aliases::U512;
12
13#[cfg(any(
14    all(target_arch = "riscv32", feature = "bigint_ops"),
15    test,
16    feature = "proving"
17))]
18use crate::ark_ff_delegation::{BigIntMacro as BigInt, MontFp};
19#[cfg(not(any(
20    all(target_arch = "riscv32", feature = "bigint_ops"),
21    test,
22    feature = "proving"
23)))]
24use ark_ff::{BigInt, MontFp};
25use ark_serialize::{Compress, SerializationError};
26use core::ops::Neg;
27
28use super::g1_swu_iso;
29use crate::{
30    bls12_381::{
31        util::{
32            read_g1_compressed, read_g1_uncompressed, serialize_fq, EncodingFlags,
33            G1_SERIALIZED_SIZE,
34        },
35        Fq, Fr,
36    },
37    glv_decomposition::GLVConfigNoAllocator,
38};
39
40pub type G1Affine = bls12::G1Affine<crate::bls12_381::curves::Config>;
41pub type G1Projective = bls12::G1Projective<crate::bls12_381::curves::Config>;
42
43#[derive(Clone, Default, PartialEq, Eq)]
44pub struct Config;
45
46impl CurveConfig for Config {
47    type BaseField = Fq;
48    type ScalarField = Fr;
49
50    /// COFACTOR = (x - 1)^2 / 3  = 76329603384216526031706109802092473003
51    const COFACTOR: &'static [u64] = &[0x8c00aaab0000aaab, 0x396c8c005555e156];
52
53    /// COFACTOR_INV = COFACTOR^{-1} mod r
54    /// = 52435875175126190458656871551744051925719901746859129887267498875565241663483
55    const COFACTOR_INV: Fr =
56        MontFp!("52435875175126190458656871551744051925719901746859129887267498875565241663483");
57}
58
59impl SWCurveConfig for Config {
60    /// COEFF_A = 0
61    const COEFF_A: Fq = Fq::ZERO;
62
63    /// COEFF_B = 4
64    const COEFF_B: Fq = MontFp!("4");
65
66    /// AFFINE_GENERATOR_COEFFS = (G1_GENERATOR_X, G1_GENERATOR_Y)
67    const GENERATOR: G1Affine = G1Affine::new_unchecked(G1_GENERATOR_X, G1_GENERATOR_Y);
68
69    #[inline(always)]
70    fn mul_by_a(_: Self::BaseField) -> Self::BaseField {
71        Self::BaseField::zero()
72    }
73
74    #[inline]
75    fn mul_projective(p: &G1Projective, scalar: &[u64]) -> G1Projective {
76        let s = Self::ScalarField::from_sign_and_limbs(true, scalar);
77        GLVConfig::glv_mul_projective(*p, s)
78    }
79
80    #[inline]
81    fn mul_affine(base: &Affine<Self>, scalar: &[u64]) -> G1Projective {
82        Self::mul_projective(&base.into_group(), scalar)
83    }
84
85    #[inline]
86    fn is_in_correct_subgroup_assuming_on_curve(p: &G1Affine) -> bool {
87        // Algorithm from Section 6 of https://eprint.iacr.org/2021/1130.
88        //
89        // Check that endomorphism_p(P) == -[X^2]P
90
91        // An early-out optimization described in Section 6.
92        // If uP == P but P != point of infinity, then the point is not in the right
93        // subgroup.
94        let x_times_p = p.mul_bigint(crate::bls12_381::curves::Config::X);
95        if x_times_p.eq(p) && !p.infinity {
96            return false;
97        }
98
99        let minus_x_squared_times_p = x_times_p
100            .mul_bigint(crate::bls12_381::curves::Config::X)
101            .neg();
102        let endomorphism_p = endomorphism(p);
103        minus_x_squared_times_p.eq(&endomorphism_p)
104    }
105
106    #[inline]
107    fn clear_cofactor(p: &G1Affine) -> G1Affine {
108        // Using the effective cofactor, as explained in
109        // Section 5 of https://eprint.iacr.org/2019/403.pdf.
110        //
111        // It is enough to multiply by (1 - x), instead of (x - 1)^2 / 3
112        let h_eff = one_minus_x().into_bigint();
113        Config::mul_affine(&p, h_eff.as_ref()).into()
114    }
115
116    fn deserialize_with_mode<R: ark_serialize::Read>(
117        mut reader: R,
118        compress: ark_serialize::Compress,
119        validate: ark_serialize::Validate,
120    ) -> Result<Affine<Self>, ark_serialize::SerializationError> {
121        let p = if compress == ark_serialize::Compress::Yes {
122            read_g1_compressed(&mut reader)?
123        } else {
124            read_g1_uncompressed(&mut reader)?
125        };
126
127        if validate == ark_serialize::Validate::Yes && !p.is_in_correct_subgroup_assuming_on_curve()
128        {
129            return Err(SerializationError::InvalidData);
130        }
131        Ok(p)
132    }
133
134    fn serialize_with_mode<W: ark_serialize::Write>(
135        item: &Affine<Self>,
136        mut writer: W,
137        compress: ark_serialize::Compress,
138    ) -> Result<(), SerializationError> {
139        let encoding = EncodingFlags {
140            is_compressed: compress == ark_serialize::Compress::Yes,
141            is_infinity: item.is_zero(),
142            is_lexographically_largest: item.y > -item.y,
143        };
144        let mut p = *item;
145        if encoding.is_infinity {
146            p = G1Affine::zero();
147        }
148        // need to access the field struct `x` directly, otherwise we get None from xy()
149        // method
150        let x_bytes = serialize_fq(p.x);
151        if encoding.is_compressed {
152            let mut bytes: [u8; G1_SERIALIZED_SIZE] = x_bytes;
153
154            encoding.encode_flags(&mut bytes);
155            writer.write_all(&bytes)?;
156        } else {
157            let mut bytes = [0u8; 2 * G1_SERIALIZED_SIZE];
158            bytes[0..G1_SERIALIZED_SIZE].copy_from_slice(&x_bytes[..]);
159            bytes[G1_SERIALIZED_SIZE..].copy_from_slice(&serialize_fq(p.y)[..]);
160
161            encoding.encode_flags(&mut bytes);
162            writer.write_all(&bytes)?;
163        };
164
165        Ok(())
166    }
167
168    fn serialized_size(compress: Compress) -> usize {
169        if compress == Compress::Yes {
170            G1_SERIALIZED_SIZE
171        } else {
172            G1_SERIALIZED_SIZE * 2
173        }
174    }
175}
176
177impl GLVConfig for Config {
178    const ENDO_COEFFS: &'static[Self::BaseField] = &[
179        MontFp!("793479390729215512621379701633421447060886740281060493010456487427281649075476305620758731620350")
180    ];
181
182    const LAMBDA: Self::ScalarField =
183        MontFp!("52435875175126190479447740508185965837461563690374988244538805122978187051009");
184
185    const SCALAR_DECOMP_COEFFS: [(bool, <Self::ScalarField as PrimeField>::BigInt); 4] = [
186        (true, BigInt!("228988810152649578064853576960394133504")),
187        (true, BigInt!("1")),
188        (false, BigInt!("1")),
189        (true, BigInt!("228988810152649578064853576960394133503")),
190    ];
191
192    fn endomorphism(p: &G1Projective) -> G1Projective {
193        let mut res = (*p).clone();
194        res.x *= Self::ENDO_COEFFS[0];
195        res
196    }
197
198    fn endomorphism_affine(p: &Affine<Self>) -> Affine<Self> {
199        let mut res = (*p).clone();
200        res.x *= Self::ENDO_COEFFS[0];
201        res
202    }
203
204    fn scalar_decomposition(
205        k: Self::ScalarField,
206    ) -> ((bool, Self::ScalarField), (bool, Self::ScalarField)) {
207        Self::scalar_decomposition_no_allocator(k)
208    }
209}
210
211impl GLVConfigNoAllocator for Config {
212    const BETA_1: (bool, U512) = (
213        true,
214        U512::from_limbs([
215            2263426366270003411,
216            10926721885838854917,
217            11648686701815784454,
218            238326537624862759,
219            7203196592358157870,
220            8965520006802549469,
221            1,
222            0,
223        ]),
224    );
225
226    const BETA_2: (bool, U512) = (
227        false,
228        U512::from_limbs([
229            4788304978035696531,
230            7279011843745230193,
231            4086414915577876179,
232            3841734232051169148,
233            2,
234            0,
235            0,
236            0,
237        ]),
238    );
239}
240
241fn one_minus_x() -> Fr {
242    const X: Fr = Fr::from_sign_and_limbs(
243        !crate::bls12_381::curves::Config::X_IS_NEGATIVE,
244        crate::bls12_381::curves::Config::X,
245    );
246    Fr::one() - X
247}
248
249// 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).
250impl WBConfig for Config {
251    type IsogenousCurve = g1_swu_iso::SwuIsoConfig;
252
253    const ISOGENY_MAP: IsogenyMap<'static, Self::IsogenousCurve, Self> =
254        g1_swu_iso::ISOGENY_MAP_TO_G1;
255}
256
257/// G1_GENERATOR_X =
258/// 3685416753713387016781088315183077757961620795782546409894578378688607592378376318836054947676345821548104185464507
259pub const G1_GENERATOR_X: Fq = MontFp!("3685416753713387016781088315183077757961620795782546409894578378688607592378376318836054947676345821548104185464507");
260
261/// G1_GENERATOR_Y =
262/// 1339506544944476473020471379941921221584933875938349620426543736416511423956333506472724655353366534992391756441569
263pub const G1_GENERATOR_Y: Fq = MontFp!("1339506544944476473020471379941921221584933875938349620426543736416511423956333506472724655353366534992391756441569");
264
265/// BETA is a non-trivial cubic root of unity in Fq.
266pub const BETA: Fq = MontFp!("793479390729215512621379701633421447060886740281060493010456487427281649075476305620758731620350");
267
268pub fn endomorphism(p: &Affine<Config>) -> Affine<Config> {
269    // Endomorphism of the points on the curve.
270    // endomorphism_p(x,y) = (BETA * x, y)
271    // where BETA is a non-trivial cubic root of unity in Fq.
272    let mut res = (*p).clone();
273    res.x *= BETA;
274    res
275}
276
277#[cfg(test)]
278mod tests {
279    use super::GLVConfigNoAllocator;
280    use super::{Config, CurveConfig, GLVConfig, PrimeField};
281    use proptest::{prop_assert_eq, proptest};
282    type ScalarField = <Config as CurveConfig>::ScalarField;
283
284    #[test]
285    fn compare_scalar_decomposition() {
286        proptest!(|(bytes: [u8; 32])| {
287            let k = ScalarField::from_be_bytes_mod_order(&bytes);
288
289            let (k1, k2) = Config::scalar_decomposition(k.clone());
290            let (k1_ref, k2_ref) = Config::scalar_decomposition_ref(k);
291
292            prop_assert_eq!(k1, k1_ref);
293            prop_assert_eq!(k2, k2_ref);
294        })
295    }
296
297    #[test]
298    fn test_betas() {
299        use ark_std::ops::Neg;
300        use num_bigint::{BigInt, BigUint, Sign};
301        use num_integer::Integer;
302        use ruint::aliases::U512;
303
304        let coeff_bigints: [BigInt; 4] = Config::SCALAR_DECOMP_COEFFS.map(|x| {
305            BigInt::from_biguint(x.0.then_some(Sign::Plus).unwrap_or(Sign::Minus), x.1.into())
306        });
307
308        let [_, n12, _, n22] = coeff_bigints;
309
310        let n = 512u64;
311        let r = BigInt::from(<<Config as CurveConfig>::ScalarField>::MODULUS);
312
313        let beta_1_ref = (n22 << n).div_rem(&r).0;
314
315        let sign = Config::BETA_1
316            .0
317            .then_some(Sign::Plus)
318            .unwrap_or(Sign::Minus);
319        let data = BigUint::from_bytes_be(&Config::BETA_1.1.to_be_bytes::<{ U512::BYTES }>());
320        let beta_1 = BigInt::from_biguint(sign, data);
321        assert_eq!(beta_1, beta_1_ref);
322
323        let beta_2_ref = ((n12 << n).neg()).div_rem(&r).0;
324
325        let sign = Config::BETA_2
326            .0
327            .then_some(Sign::Plus)
328            .unwrap_or(Sign::Minus);
329        let data = BigUint::from_bytes_be(&Config::BETA_2.1.to_be_bytes::<{ U512::BYTES }>());
330        let beta_2 = BigInt::from_biguint(sign, data);
331        assert_eq!(beta_2, beta_2_ref);
332    }
333}
airbender_crypto/bls12_381/curves/g1.rs

airbender_crypto/bls12_381/curves/
g1.rs
