snarkvm_curves/bls12_377/
g1.rs

1// Copyright (c) 2019-2025 Provable Inc.
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16use snarkvm_fields::{Field, One, PrimeField, Zero, field};
17use snarkvm_utilities::{
18    BigInteger,
19    BitIteratorBE,
20    biginteger::{BigInteger256, BigInteger384},
21};
22
23use crate::{
24    AffineCurve,
25    ProjectiveCurve,
26    bls12_377::{Fq, Fr},
27    templates::bls12::Bls12Parameters,
28    traits::{ModelParameters, ShortWeierstrassParameters},
29};
30
31use std::ops::Neg;
32
33#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
34pub struct Bls12_377G1Parameters;
35
36impl ModelParameters for Bls12_377G1Parameters {
37    type BaseField = Fq;
38    type ScalarField = Fr;
39}
40
41impl ShortWeierstrassParameters for Bls12_377G1Parameters {
42    /// AFFINE_GENERATOR_COEFFS = (G1_GENERATOR_X, G1_GENERATOR_Y)
43    const AFFINE_GENERATOR_COEFFS: (Self::BaseField, Self::BaseField) = (G1_GENERATOR_X, G1_GENERATOR_Y);
44    /// B1 = x^2 - 1
45    const B1: Fr = field!(
46        Fr,
47        BigInteger256([12574070832645531618, 10005695704657941814, 1564543351912391449, 657300228442948690])
48    );
49    /// B2 = x^2
50    const B2: Fr = field!(
51        Fr,
52        BigInteger256([2417046298041509844, 11783911742408086824, 14689097366802547462, 270119112518072728])
53    );
54    /// COFACTOR = (x - 1)^2 / 3  = 30631250834960419227450344600217059328
55    const COFACTOR: &'static [u64] = &[0x0, 0x170b5d4430000000];
56    /// COFACTOR_INV = COFACTOR^{-1} mod r
57    ///              = 5285428838741532253824584287042945485047145357130994810877
58    const COFACTOR_INV: Fr = field!(
59        Fr,
60        BigInteger256([2013239619100046060, 4201184776506987597, 2526766393982337036, 1114629510922847535,])
61    );
62    const PHI: Fq = field!(
63        Fq,
64        BigInteger384([
65            0xdacd106da5847973,
66            0xd8fe2454bac2a79a,
67            0x1ada4fd6fd832edc,
68            0xfb9868449d150908,
69            0xd63eb8aeea32285e,
70            0x167d6a36f873fd0,
71        ])
72    );
73    /// R128 = 2^128 - 1
74    const R128: Fr = field!(
75        Fr,
76        BigInteger256([13717662654766427599, 14709524173037165000, 15342848074630952979, 736762107895475646])
77    );
78    /// WEIERSTRASS_A = 0
79    const WEIERSTRASS_A: Fq = field!(Fq, BigInteger384([0x0, 0x0, 0x0, 0x0, 0x0, 0x0]));
80    /// WEIERSTRASS_B = 1
81    const WEIERSTRASS_B: Fq = field!(
82        Fq,
83        BigInteger384([
84            0x2cdffffffffff68,
85            0x51409f837fffffb1,
86            0x9f7db3a98a7d3ff2,
87            0x7b4e97b76e7c6305,
88            0x4cf495bf803c84e8,
89            0x8d6661e2fdf49a,
90        ])
91    );
92
93    #[inline(always)]
94    fn mul_by_a(_: &Self::BaseField) -> Self::BaseField {
95        Self::BaseField::zero()
96    }
97
98    fn is_in_correct_subgroup_assuming_on_curve(p: &super::G1Affine) -> bool {
99        let phi = |mut p: super::G1Affine| {
100            debug_assert!(Self::PHI.pow([3]).is_one());
101            p.x *= Self::PHI;
102            p
103        };
104        let x_square = Fr::from(super::Bls12_377Parameters::X[0]).square();
105        (phi(*p).mul_bits(BitIteratorBE::new_without_leading_zeros(x_square.to_bigint())).add_mixed(p)).is_zero()
106    }
107
108    fn glv_endomorphism(
109        mut p: crate::templates::short_weierstrass_jacobian::Affine<Self>,
110    ) -> crate::templates::short_weierstrass_jacobian::Affine<Self> {
111        p.x *= &Self::PHI;
112        p
113    }
114
115    fn mul_projective(
116        p: crate::templates::short_weierstrass_jacobian::Projective<Self>,
117        by: Self::ScalarField,
118    ) -> crate::templates::short_weierstrass_jacobian::Projective<Self> {
119        type ScalarBigInt = <Fr as PrimeField>::BigInteger;
120
121        /// The scalar multiplication window size.
122        const GLV_WINDOW_SIZE: usize = 4;
123
124        /// The table size, used for w-ary NAF recoding.
125        const TABLE_SIZE: i64 = 1 << (GLV_WINDOW_SIZE + 1);
126        const HALF_TABLE_SIZE: i64 = 1 << (GLV_WINDOW_SIZE);
127        const MASK_FOR_MOD_TABLE_SIZE: u64 = (TABLE_SIZE as u64) - 1;
128        /// The GLV table length.
129        const L: usize = 1 << (GLV_WINDOW_SIZE - 1);
130
131        let decomposition = by.decompose(&Self::Q1, &Self::Q2, Self::B1, Self::B2, Self::R128, &Self::HALF_R);
132
133        // Prepare tables.
134        let mut t_1 = Vec::with_capacity(L);
135        let double = crate::templates::short_weierstrass_jacobian::Affine::<Self>::from(p.double());
136        t_1.push(p);
137        for i in 1..L {
138            t_1.push(t_1[i - 1].add_mixed(&double));
139        }
140        let t_1 =
141            crate::templates::short_weierstrass_jacobian::Projective::<Self>::batch_normalization_into_affine(t_1);
142
143        let t_2 = t_1.iter().copied().map(Self::glv_endomorphism).collect::<Vec<_>>();
144
145        let mod_signed = |d| {
146            let d_mod_window_size = i64::try_from(d & MASK_FOR_MOD_TABLE_SIZE).unwrap();
147            if d_mod_window_size >= HALF_TABLE_SIZE { d_mod_window_size - TABLE_SIZE } else { d_mod_window_size }
148        };
149        let to_wnaf = |e: Self::ScalarField| -> Vec<i32> {
150            let mut naf = vec![];
151            let mut e = e.to_bigint();
152            while !e.is_zero() {
153                let next = if e.is_odd() {
154                    let naf_sign = mod_signed(e.as_ref()[0]);
155                    if naf_sign < 0 {
156                        e.add_nocarry(&ScalarBigInt::from(-naf_sign as u64));
157                    } else {
158                        e.sub_noborrow(&ScalarBigInt::from(naf_sign as u64));
159                    }
160                    naf_sign.try_into().unwrap()
161                } else {
162                    0
163                };
164                naf.push(next);
165                e.div2();
166            }
167
168            naf
169        };
170
171        let wnaf = |k1: Self::ScalarField, k2: Self::ScalarField, s1: bool, s2: bool| -> (Vec<i32>, Vec<i32>) {
172            let mut wnaf_1 = to_wnaf(k1);
173            let mut wnaf_2 = to_wnaf(k2);
174
175            if s1 {
176                wnaf_1.iter_mut().for_each(|e| *e = -*e);
177            }
178            if !s2 {
179                wnaf_2.iter_mut().for_each(|e| *e = -*e);
180            }
181
182            (wnaf_1, wnaf_2)
183        };
184
185        let naf_add = |table: &[crate::templates::short_weierstrass_jacobian::Affine<Self>],
186                       naf: i32,
187                       acc: &mut crate::templates::short_weierstrass_jacobian::Projective<Self>| {
188            if naf != 0 {
189                let mut p_1 = table[(naf.abs() >> 1) as usize];
190                if naf < 0 {
191                    p_1 = p_1.neg();
192                }
193                acc.add_assign_mixed(&p_1);
194            }
195        };
196
197        // Recode scalars.
198        let (naf_1, naf_2) = wnaf(decomposition.0, decomposition.1, decomposition.2, decomposition.3);
199        let max_len = naf_1.len().max(naf_2.len());
200        let mut acc = crate::templates::short_weierstrass_jacobian::Projective::<Self>::zero();
201        for i in (0..max_len).rev() {
202            if i < naf_1.len() {
203                naf_add(&t_1, naf_1[i], &mut acc)
204            }
205
206            if i < naf_2.len() {
207                naf_add(&t_2, naf_2[i], &mut acc)
208            }
209
210            if i != 0 {
211                acc.double_in_place();
212            }
213        }
214
215        acc
216    }
217}
218
219///
220/// G1_GENERATOR_X =
221/// 89363714989903307245735717098563574705733591463163614225748337416674727625843187853442697973404985688481508350822
222///
223/// See `snarkvm_algorithms::hash_to_curve::tests::bls12_377` for tests.
224///
225pub const G1_GENERATOR_X: Fq = field!(
226    Fq,
227    BigInteger384::new([
228        1171681672315280277,
229        6528257384425852712,
230        7514971432460253787,
231        2032708395764262463,
232        12876543207309632302,
233        107509843840671767
234    ])
235);
236
237///
238/// G1_GENERATOR_Y =
239/// 3702177272937190650578065972808860481433820514072818216637796320125658674906330993856598323293086021583822603349
240///
241/// See `snarkvm_algorithms::hash_to_curve::tests::bls12_377` for tests.
242///
243pub const G1_GENERATOR_Y: Fq = field!(
244    Fq,
245    BigInteger384::new([
246        13572190014569192121,
247        15344828677741220784,
248        17067903700058808083,
249        10342263224753415805,
250        1083990386877464092,
251        21335464879237822
252    ])
253);
254
255#[cfg(test)]
256mod tests {
257    use rand::Rng;
258    use snarkvm_fields::Field;
259    use snarkvm_utilities::{BitIteratorBE, TestRng, Uniform};
260
261    use crate::AffineCurve;
262
263    use super::{super::G1Affine, *};
264
265    #[test]
266    fn test_subgroup_membership() {
267        let rng = &mut TestRng::default();
268
269        for _ in 0..1000 {
270            let p = G1Affine::rand(rng);
271            assert!(Bls12_377G1Parameters::is_in_correct_subgroup_assuming_on_curve(&p));
272            let x = Fq::rand(rng);
273            let greatest = rng.r#gen();
274
275            if let Some(p) = G1Affine::from_x_coordinate(x, greatest) {
276                assert_eq!(
277                    Bls12_377G1Parameters::is_in_correct_subgroup_assuming_on_curve(&p),
278                    p.mul_bits(BitIteratorBE::new(Fr::characteristic())).is_zero(),
279                );
280            }
281        }
282    }
283}
snarkvm_curves/bls12_377/g1.rs

snarkvm_curves/bls12_377/
g1.rs
