ark_bls12_377/curves/
g1.rs

1use ark_ec::{
2    bls12,
3    bls12::Bls12Config,
4    hashing::curve_maps::wb::{IsogenyMap, WBConfig},
5    models::{
6        short_weierstrass::{Affine as SWAffine, Projective as SWProjective, SWCurveConfig},
7        twisted_edwards::{
8            Affine as TEAffine, MontCurveConfig, Projective as TEProjective, TECurveConfig,
9        },
10    },
11    scalar_mul::glv::GLVConfig,
12    CurveConfig,
13};
14use ark_ff::{AdditiveGroup, BigInt, Field, MontFp, PrimeField, Zero};
15use ark_std::{ops::Neg, One};
16
17use super::g1_swu_iso::{SwuIsoConfig, ISOGENY_MAP_TO_G1};
18use crate::{Fq, Fr};
19
20pub type G1Affine = bls12::G1Affine<crate::Config>;
21pub type G1Projective = bls12::G1Projective<crate::Config>;
22
23#[derive(Clone, Default, PartialEq, Eq)]
24pub struct Config;
25
26impl CurveConfig for Config {
27    type BaseField = Fq;
28    type ScalarField = Fr;
29
30    /// COFACTOR = (x - 1)^2 / 3  = 30631250834960419227450344600217059328
31    const COFACTOR: &'static [u64] = &[0x0, 0x170b5d4430000000];
32
33    /// COFACTOR_INV = COFACTOR^{-1} mod r
34    /// = 5285428838741532253824584287042945485047145357130994810877
35    const COFACTOR_INV: Fr = MontFp!("5285428838741532253824584287042945485047145357130994810877");
36}
37
38impl SWCurveConfig for Config {
39    /// COEFF_A = 0
40    const COEFF_A: Fq = Fq::ZERO;
41
42    /// COEFF_B = 1
43    const COEFF_B: Fq = Fq::ONE;
44
45    /// AFFINE_GENERATOR_COEFFS = (G1_GENERATOR_X, G1_GENERATOR_Y)
46    const GENERATOR: G1SWAffine = G1SWAffine::new_unchecked(G1_GENERATOR_X, G1_GENERATOR_Y);
47
48    #[inline(always)]
49    fn mul_by_a(_: Self::BaseField) -> Self::BaseField {
50        Self::BaseField::zero()
51    }
52
53    #[inline]
54    fn mul_projective(p: &G1Projective, scalar: &[u64]) -> G1Projective {
55        let s = Self::ScalarField::from_sign_and_limbs(true, scalar);
56        GLVConfig::glv_mul_projective(*p, s)
57    }
58
59    #[inline]
60    fn clear_cofactor(p: &G1SWAffine) -> G1SWAffine {
61        // Using the effective cofactor.
62        //
63        // It is enough to multiply by (x - 1), instead of (x - 1)^2 / 3
64        let h_eff = x_minus_one().into_bigint();
65        <Config as SWCurveConfig>::mul_affine(p, h_eff.as_ref()).into()
66    }
67}
68
69impl GLVConfig for Config {
70    const ENDO_COEFFS: &'static[Self::BaseField] = &[
71        MontFp!("258664426012969093929703085429980814127835149614277183275038967946009968870203535512256352201271898244626862047231")
72    ];
73
74    const LAMBDA: Self::ScalarField =
75        MontFp!("8444461749428370424248824938781546531284005582649182570233710176290576793600");
76
77    const SCALAR_DECOMP_COEFFS: [(bool, <Self::ScalarField as PrimeField>::BigInt); 4] = [
78        (true, BigInt!("91893752504881257701523279626832445441")),
79        (true, BigInt!("1")),
80        (false, BigInt!("1")),
81        (true, BigInt!("91893752504881257701523279626832445440")),
82    ];
83
84    fn endomorphism(p: &SWProjective<Self>) -> SWProjective<Self> {
85        let mut res = (*p).clone();
86        res.x *= Self::ENDO_COEFFS[0];
87        res
88    }
89
90    fn endomorphism_affine(p: &SWAffine<Self>) -> SWAffine<Self> {
91        let mut res = (*p).clone();
92        res.x *= Self::ENDO_COEFFS[0];
93        res
94    }
95}
96
97fn x_minus_one() -> Fr {
98    const X: Fr = Fr::from_sign_and_limbs(!crate::Config::X_IS_NEGATIVE, crate::Config::X);
99    X - Fr::one()
100}
101
102pub type G1SWAffine = SWAffine<Config>;
103pub type G1TEAffine = TEAffine<Config>;
104pub type G1TEProjective = TEProjective<Config>;
105
106/// Bls12_377::G1 also has a twisted Edwards form.
107/// It can be obtained via the following script, implementing
108/// 1. SW -> Montgomery -> TE1 transformation: <https://en.wikipedia.org/wiki/Montgomery_curve>
109/// 2. TE1 -> TE2 normalization (enforcing `a = -1`)
110/// ``` sage
111/// # modulus
112/// p = 0x1ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c00000000001
113/// Fp = Zmod(p)
114///
115/// #####################################################
116/// # Weierstrass curve: y² = x³ + A * x + B
117/// #####################################################
118/// # curve y^2 = x^3 + 1
119/// WA = Fp(0)
120/// WB = Fp(1)
121///
122/// #####################################################
123/// # Montgomery curve: By² = x³ + A * x² + x
124/// #####################################################
125/// # root for x^3 + 1 = 0
126/// alpha = -1
127/// # s = 1 / (sqrt(3alpha^2 + a))
128/// s = 1/(Fp(3).sqrt())
129///
130/// # MA = 3 * alpha * s
131/// MA = Fp(228097355113300204138531148905234651262148041026195375645000724271212049151994375092458297304264351187709081232384)
132/// # MB = s
133/// MB = Fp(10189023633222963290707194929886294091415157242906428298294512798502806398782149227503530278436336312243746741931)
134///
135/// # #####################################################
136/// # # Twisted Edwards curve 1: a * x² + y² = 1 + d * x² * y²
137/// # #####################################################
138/// # We first convert to TE form obtaining a curve with a != -1, and then
139/// # apply a transformation to obtain a TE curve with a = -1.
140/// # a = (MA+2)/MB
141/// TE1a = Fp(61134141799337779744243169579317764548490943457438569789767076791016838392692895365021181670618017873462480451583)
142/// # b = (MA-2)/MB
143/// TE1d = Fp(197530284213631314266409564115575768987902569297476090750117185875703629955647927409947706468955342250977841006588)
144///
145/// # #####################################################
146/// # # Twisted Edwards curve 2: a * x² + y² = 1 + d * x² * y²
147/// # #####################################################
148/// # a = -1
149/// TE2a = Fp(-1)
150/// # b = -TE1d/TE1a
151/// TE2d = Fp(122268283598675559488486339158635529096981886914877139579534153582033676785385790730042363341236035746924960903179)
152/// ```
153impl TECurveConfig for Config {
154    /// COEFF_A = -1
155    const COEFF_A: Fq = MontFp!("-1");
156
157    /// COEFF_D = 122268283598675559488486339158635529096981886914877139579534153582033676785385790730042363341236035746924960903179 mod q
158    const COEFF_D: Fq = MontFp!("122268283598675559488486339158635529096981886914877139579534153582033676785385790730042363341236035746924960903179");
159
160    /// AFFINE_GENERATOR_COEFFS = (GENERATOR_X, GENERATOR_Y)
161    const GENERATOR: G1TEAffine = G1TEAffine::new_unchecked(TE_GENERATOR_X, TE_GENERATOR_Y);
162
163    type MontCurveConfig = Config;
164
165    /// Multiplication by `a` is multiply by `-1`.
166    #[inline(always)]
167    fn mul_by_a(elem: Self::BaseField) -> Self::BaseField {
168        elem.neg()
169    }
170}
171
172// BLS12-377::G1 also has a Montgomery form.
173// BLS12-377::G1 also has a twisted Edwards form.
174// It can be obtained via the following script, implementing
175// SW -> Montgomery transformation: <https://en.wikipedia.org/wiki/Montgomery_curve>
176// ``` sage
177// # modulus
178// p=0x1ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c00000000001
179// Fp=Zmod(p)
180//
181// #####################################################
182// # Weierstrass curve: y² = x³ + A * x + B
183// #####################################################
184// # curve y^2 = x^3 + 1
185// WA=Fp(0)
186// WB=Fp(1)
187//
188// #####################################################
189// # Montgomery curve: By² = x³ + A * x² + x
190// #####################################################
191// # root for x^3 + 1 = 0
192// alpha = -1
193// # s = 1 / (sqrt(3alpha^2 + a))
194// s = 1/(Fp(3).sqrt())
195//
196// # MA = 3 * alpha * s
197// MA=Fp(228097355113300204138531148905234651262148041026195375645000724271212049151994375092458297304264351187709081232384)
198// # MB = s
199// MB=Fp(10189023633222963290707194929886294091415157242906428298294512798502806398782149227503530278436336312243746741931)
200// ```
201impl MontCurveConfig for Config {
202    /// COEFF_A = 228097355113300204138531148905234651262148041026195375645000724271212049151994375092458297304264351187709081232384
203    const COEFF_A: Fq = MontFp!("228097355113300204138531148905234651262148041026195375645000724271212049151994375092458297304264351187709081232384");
204
205    /// COEFF_B = 10189023633222963290707194929886294091415157242906428298294512798502806398782149227503530278436336312243746741931
206    const COEFF_B: Fq = MontFp!("10189023633222963290707194929886294091415157242906428298294512798502806398782149227503530278436336312243746741931");
207
208    type TECurveConfig = Config;
209}
210
211/// G1_GENERATOR_X =
212/// 81937999373150964239938255573465948239988671502647976594219695644855304257327692006745978603320413799295628339695
213pub const G1_GENERATOR_X: Fq = MontFp!("81937999373150964239938255573465948239988671502647976594219695644855304257327692006745978603320413799295628339695");
214
215/// G1_GENERATOR_Y =
216/// 241266749859715473739788878240585681733927191168601896383759122102112907357779751001206799952863815012735208165030
217pub const G1_GENERATOR_Y: Fq = MontFp!("241266749859715473739788878240585681733927191168601896383759122102112907357779751001206799952863815012735208165030");
218
219impl WBConfig for Config {
220    type IsogenousCurve = SwuIsoConfig;
221
222    const ISOGENY_MAP: IsogenyMap<'static, Self::IsogenousCurve, Self> = ISOGENY_MAP_TO_G1;
223}
224
225// The generator for twisted Edward form is the same SW generator converted into
226// the normalized TE form (TE2).
227//``` sage
228// # following scripts in previous section
229// #####################################################
230// # Weierstrass curve generator
231// #####################################################
232// Wx = Fp(81937999373150964239938255573465948239988671502647976594219695644855304257327692006745978603320413799295628339695)
233// Wy = Fp(241266749859715473739788878240585681733927191168601896383759122102112907357779751001206799952863815012735208165030)
234//
235// assert(Wy^2 - Wx^3 - WA * Wx - WB == 0)
236//
237// #####################################################
238// # Montgomery curve generator
239// #####################################################
240// # x = s * (x - alpha)
241// Mx = Fp(251803586774461569862800610331871502335378228972505599912537082323947581271784390797244487924068052270360793200630)
242// # y = s * y
243// My = Fp(77739247071951651095607889637653357561348174979132042929587539214321586851215673796661346812932566642719051699820)
244//
245// assert(MB * My^2 == Mx^3+ MA * Mx^2 + Mx)
246//
247// # #####################################################
248// # # Twisted Edwards curve 1 generator
249// # #####################################################
250// # x = Mx/My
251// TE1x = Fp(82241236807150726090333472814441006963902378430536027612759193445733851062772474760677400112551677454953925168208)
252// # y = (Mx - 1)/(Mx+1)
253// TE1y = Fp(6177051365529633638563236407038680211609544222665285371549726196884440490905471891908272386851767077598415378235)
254//
255// assert( TE1a * TE1x^2 + TE1y^2 == 1 + TE1d * TE1x^2 * TE1y^2 )
256//
257//
258// # #####################################################
259// # # Twisted Edwards curve 2 generator
260// # #####################################################
261// beta = (-TE1a).sqrt()
262// # x = TE1x * sqrt(-TE1a)
263// TE2x = Fp(71222569531709137229370268896323705690285216175189308202338047559628438110820800641278662592954630774340654489393)
264// # y = TE1y
265// TE2y = Fp(6177051365529633638563236407038680211609544222665285371549726196884440490905471891908272386851767077598415378235)
266//
267// assert( TE2a * TE2x^2 + TE2y^2 == 1 + TE2d * TE2x^2 * TE2y^2 )
268// ```
269/// TE_GENERATOR_X =
270/// 71222569531709137229370268896323705690285216175189308202338047559628438110820800641278662592954630774340654489393
271pub const TE_GENERATOR_X: Fq = MontFp!("71222569531709137229370268896323705690285216175189308202338047559628438110820800641278662592954630774340654489393");
272
273/// TE_GENERATOR_Y =
274/// 6177051365529633638563236407038680211609544222665285371549726196884440490905471891908272386851767077598415378235
275pub const TE_GENERATOR_Y: Fq = MontFp!("6177051365529633638563236407038680211609544222665285371549726196884440490905471891908272386851767077598415378235");
276
277#[cfg(test)]
278mod test {
279
280    use super::*;
281    use crate::g1;
282    use ark_std::{rand::Rng, UniformRand};
283
284    fn sample_unchecked() -> SWAffine<g1::Config> {
285        let mut rng = ark_std::test_rng();
286        loop {
287            let x = Fq::rand(&mut rng);
288            let greatest = rng.gen();
289
290            if let Some(p) = SWAffine::get_point_from_x_unchecked(x, greatest) {
291                return p;
292            }
293        }
294    }
295
296    #[test]
297    fn test_cofactor_clearing() {
298        const SAMPLES: usize = 100;
299        for _ in 0..SAMPLES {
300            let p: SWAffine<g1::Config> = sample_unchecked();
301            let p = <Config as SWCurveConfig>::clear_cofactor(&p);
302            assert!(p.is_on_curve());
303            assert!(p.is_in_correct_subgroup_assuming_on_curve());
304        }
305    }
306}
ark_bls12_377/curves/g1.rs

ark_bls12_377/curves/
g1.rs
