ark_bls12_381_ext/curves/
g2.rs

1use ark_bls12_381::{fq2::Fq2, g2::Config as ArkConfig, Fq};
2use ark_ec::AdditiveGroup;
3use ark_ff::{Field, MontFp};
4use ark_models_ext::{
5    bls12, bls12::Bls12Config, short_weierstrass::SWCurveConfig, AffineRepr, CurveConfig,
6    CurveGroup, PrimeGroup,
7};
8use ark_serialize::{Compress, SerializationError, Validate};
9use ark_std::{
10    io::{Read, Write},
11    marker::PhantomData,
12    ops::Neg,
13};
14
15use crate::{
16    util::{
17        read_g2_compressed, read_g2_uncompressed, serialize_fq, EncodingFlags, G2_SERIALIZED_SIZE,
18    },
19    CurveHooks,
20};
21
22pub use ark_bls12_381::g2::{
23    G2_GENERATOR_X, G2_GENERATOR_X_C0, G2_GENERATOR_X_C1, G2_GENERATOR_Y, G2_GENERATOR_Y_C0,
24    G2_GENERATOR_Y_C1,
25};
26
27// PSI_X = 1/(u+1)^((p-1)/3)
28const P_POWER_ENDOMORPHISM_COEFF_0 : Fq2 = Fq2::new(
29    Fq::ZERO,
30    MontFp!("4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939437")
31);
32
33// PSI_Y = 1/(u+1)^((p-1)/2)
34const P_POWER_ENDOMORPHISM_COEFF_1: Fq2 = Fq2::new(
35    MontFp!("2973677408986561043442465346520108879172042883009249989176415018091420807192182638567116318576472649347015917690530"),
36    MontFp!("1028732146235106349975324479215795277384839936929757896155643118032610843298655225875571310552543014690878354869257")
37);
38
39// PSI_2_X = (u+1)^((1-p^2)/3)
40const DOUBLE_P_POWER_ENDOMORPHISM_COEFF_0: Fq2 = Fq2::new(
41    MontFp!("4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939436"),
42    Fq::ZERO
43);
44
45pub type G2Affine<H> = bls12::G2Affine<crate::Config<H>>;
46pub type G2Projective<H> = bls12::G2Projective<crate::Config<H>>;
47
48#[derive(Clone, Copy)]
49pub struct Config<H: CurveHooks>(PhantomData<fn() -> H>);
50
51impl<H: CurveHooks> CurveConfig for Config<H> {
52    const COFACTOR: &'static [u64] = <ArkConfig as CurveConfig>::COFACTOR;
53    const COFACTOR_INV: Self::ScalarField = <ArkConfig as CurveConfig>::COFACTOR_INV;
54
55    type BaseField = <ArkConfig as CurveConfig>::BaseField;
56    type ScalarField = <ArkConfig as CurveConfig>::ScalarField;
57}
58
59impl<H: CurveHooks> SWCurveConfig for Config<H> {
60    const COEFF_A: Self::BaseField = <ArkConfig as SWCurveConfig>::COEFF_A;
61    const COEFF_B: Self::BaseField = <ArkConfig as SWCurveConfig>::COEFF_B;
62
63    const GENERATOR: G2Affine<H> = G2Affine::<H>::new_unchecked(G2_GENERATOR_X, G2_GENERATOR_Y);
64
65    /// Multi scalar multiplication jumping into the user-defined `msm_g2` hook.
66    #[inline(always)]
67    fn msm(bases: &[G2Affine<H>], scalars: &[Self::ScalarField]) -> Result<G2Projective<H>, usize> {
68        if bases.len() != scalars.len() {
69            return Err(bases.len().min(scalars.len()));
70        }
71        Ok(H::msm_g2(bases, scalars))
72    }
73
74    /// Projective multiplication jumping into the user-defined `mul_projective_g2` hook.
75    #[inline(always)]
76    fn mul_projective(base: &G2Projective<H>, scalar: &[u64]) -> G2Projective<H> {
77        H::mul_projective_g2(base, scalar)
78    }
79
80    /// Affine multiplication jumping into the user-defined `mul_projective_g2` hook.
81    #[inline(always)]
82    fn mul_affine(base: &G2Affine<H>, scalar: &[u64]) -> G2Projective<H> {
83        Self::mul_projective(&(*base).into(), scalar)
84    }
85
86    #[inline(always)]
87    fn mul_by_a(elem: Self::BaseField) -> Self::BaseField {
88        <ArkConfig as SWCurveConfig>::mul_by_a(elem)
89    }
90
91    // Verbatim copy of upstream implementation.
92    //
93    // Can't call it directly because of different `Affine` configuration.
94    #[inline(always)]
95    fn is_in_correct_subgroup_assuming_on_curve(point: &G2Affine<H>) -> bool {
96        let mut x_times_point = point.mul_bigint(crate::Config::<H>::X);
97        if crate::Config::<H>::X_IS_NEGATIVE {
98            x_times_point = -x_times_point;
99        }
100
101        let p_times_point = p_power_endomorphism(point);
102
103        x_times_point.eq(&p_times_point)
104    }
105
106    // Verbatim copy of upstream implementation.
107    //
108    // Can't call it directly because of different `Affine` configuration.
109    #[inline]
110    fn clear_cofactor(p: &G2Affine<H>) -> G2Affine<H> {
111        // Based on Section 4.1 of https://eprint.iacr.org/2017/419.pdf
112        // [h(ψ)]P = [x^2 − x − 1]P + [x − 1]ψ(P) + (ψ^2)(2P)
113
114        // x = -15132376222941642752
115        // When multiplying, use -c1 instead, and then negate the result. That's much
116        // more efficient, since the scalar -c1 has less limbs and a much lower Hamming
117        // weight.
118        let x: &'static [u64] = crate::Config::<H>::X;
119        let p_projective = p.into_group();
120
121        // [x]P
122        let x_p = Config::mul_affine(p, x).neg();
123        // ψ(P)
124        let psi_p = p_power_endomorphism(p);
125        // (ψ^2)(2P)
126        let mut psi2_p2 = double_p_power_endomorphism(&p_projective.double());
127
128        // tmp = [x]P + ψ(P)
129        let mut tmp = x_p;
130        tmp += &psi_p;
131
132        // tmp2 = [x^2]P + [x]ψ(P)
133        let mut tmp2: G2Projective<H> = tmp;
134        tmp2 = tmp2.mul_bigint(x).neg();
135
136        // add up all the terms
137        psi2_p2 += tmp2;
138        psi2_p2 -= x_p;
139        psi2_p2 += &-psi_p;
140        (psi2_p2 - p_projective).into_affine()
141    }
142
143    // Verbatim copy of upstream implementation.
144    //
145    // Can't call it directly because of different `Affine` configuration.
146    fn deserialize_with_mode<R: Read>(
147        mut reader: R,
148        compress: Compress,
149        validate: Validate,
150    ) -> Result<G2Affine<H>, SerializationError> {
151        let p = if compress == Compress::Yes {
152            read_g2_compressed(&mut reader)?
153        } else {
154            read_g2_uncompressed(&mut reader)?
155        };
156
157        if validate == Validate::Yes && !p.is_in_correct_subgroup_assuming_on_curve() {
158            return Err(SerializationError::InvalidData);
159        }
160        Ok(p)
161    }
162
163    // Verbatim copy of upstream implementation.
164    //
165    // Can't call it directly because of different `Affine` configuration.
166    fn serialize_with_mode<W: Write>(
167        item: &G2Affine<H>,
168        mut writer: W,
169        compress: Compress,
170    ) -> Result<(), SerializationError> {
171        let encoding = EncodingFlags {
172            is_compressed: compress == Compress::Yes,
173            is_infinity: item.is_zero(),
174            is_lexographically_largest: item.y > -item.y,
175        };
176        let mut p = *item;
177        if encoding.is_infinity {
178            p = G2Affine::<H>::zero();
179        }
180
181        let mut x_bytes = [0u8; G2_SERIALIZED_SIZE];
182        let c1_bytes = serialize_fq(p.x.c1);
183        let c0_bytes = serialize_fq(p.x.c0);
184        x_bytes[0..48].copy_from_slice(&c1_bytes[..]);
185        x_bytes[48..96].copy_from_slice(&c0_bytes[..]);
186        if encoding.is_compressed {
187            let mut bytes: [u8; G2_SERIALIZED_SIZE] = x_bytes;
188
189            encoding.encode_flags(&mut bytes);
190            writer.write_all(&bytes)?;
191        } else {
192            let mut bytes = [0u8; 2 * G2_SERIALIZED_SIZE];
193
194            let mut y_bytes = [0u8; G2_SERIALIZED_SIZE];
195            let c1_bytes = serialize_fq(p.y.c1);
196            let c0_bytes = serialize_fq(p.y.c0);
197            y_bytes[0..48].copy_from_slice(&c1_bytes[..]);
198            y_bytes[48..96].copy_from_slice(&c0_bytes[..]);
199            bytes[0..G2_SERIALIZED_SIZE].copy_from_slice(&x_bytes);
200            bytes[G2_SERIALIZED_SIZE..].copy_from_slice(&y_bytes);
201
202            encoding.encode_flags(&mut bytes);
203            writer.write_all(&bytes)?;
204        };
205
206        Ok(())
207    }
208
209    // Verbatim copy of upstream implementation.
210    //
211    // Can't call it directly because of different `Affine` configuration.
212    fn serialized_size(compress: Compress) -> usize {
213        <ArkConfig as SWCurveConfig>::serialized_size(compress)
214    }
215}
216
217/// psi(P) is the untwist-Frobenius-twist endomorhism on E'(Fq2)
218fn p_power_endomorphism<H: CurveHooks>(p: &G2Affine<H>) -> G2Affine<H> {
219    // The p-power endomorphism for G2 is defined as follows:
220    // 1. Note that G2 is defined on curve E': y^2 = x^3 + 4(u+1).
221    //    To map a point (x, y) in E' to (s, t) in E,
222    //    set s = x / ((u+1) ^ (1/3)), t = y / ((u+1) ^ (1/2)),
223    //    because E: y^2 = x^3 + 4.
224    // 2. Apply theFrobenius endomorphism (s, t) => (s', t'),
225    //    another point on curve E, where s' = s^p, t' = t^p.
226    // 3. Map the point From E back to E'; that is,
227    //    set x' = s' * ((u+1) ^ (1/3)), y' = t' * ((u+1) ^ (1/2)).
228    //
229    // To sum up, it maps
230    // (x,y) -> (x^p / ((u+1)^((p-1)/3)), y^p / ((u+1)^((p-1)/2)))
231    // as implemented in the code as follows.
232
233    let mut res = *p;
234    res.x.frobenius_map_in_place(1);
235    res.y.frobenius_map_in_place(1);
236
237    let tmp_x = res.x;
238    res.x.c0 = -P_POWER_ENDOMORPHISM_COEFF_0.c1 * tmp_x.c1;
239    res.x.c1 = P_POWER_ENDOMORPHISM_COEFF_0.c1 * tmp_x.c0;
240    res.y *= P_POWER_ENDOMORPHISM_COEFF_1;
241
242    res
243}
244
245/// For a p-power endomorphism psi(P), compute psi(psi(P))
246fn double_p_power_endomorphism<H: CurveHooks>(p: &G2Projective<H>) -> G2Projective<H> {
247    let mut res = *p;
248
249    res.x *= DOUBLE_P_POWER_ENDOMORPHISM_COEFF_0;
250    res.y = res.y.neg();
251
252    res
253}
ark_bls12_381_ext/curves/g2.rs

ark_bls12_381_ext/curves/
g2.rs
