1use ark_std::ops::Neg;
  2
  3use ark_ec::{
  4    bls12,
  5    bls12::Bls12Parameters,
  6    models::CurveConfig,
  7    short_weierstrass::{Affine, Projective, SWCurveConfig},
  8    AffineRepr, CurveGroup, Group,
  9};
 10use ark_ff::{Field, MontFp, Zero};
 11use ark_serialize::{Compress, SerializationError};
 12
 13use super::util::{serialize_fq, EncodingFlags, G2_SERIALIZED_SIZE};
 14use crate::{
 15    util::{read_g2_compressed, read_g2_uncompressed},
 16    *,
 17};
 18
 19pub type G2Affine = bls12::G2Affine<crate::Parameters>;
 20pub type G2Projective = bls12::G2Projective<crate::Parameters>;
 21
 22#[derive(Clone, Default, PartialEq, Eq)]
 23pub struct Parameters;
 24
 25impl CurveConfig for Parameters {
 26    type BaseField = Fq2;
 27    type ScalarField = Fr;
 28
 29    /// COFACTOR = (x^8 - 4 x^7 + 5 x^6) - (4 x^4 + 6 x^3 - 4 x^2 - 4 x + 13) //
 30    /// 9
 31    /// = 305502333931268344200999753193121504214466019254188142667664032982267604182971884026507427359259977847832272839041616661285803823378372096355777062779109
 32    #[rustfmt::skip]
 33    const COFACTOR: &'static [u64] = &[
 34        0xcf1c38e31c7238e5,
 35        0x1616ec6e786f0c70,
 36        0x21537e293a6691ae,
 37        0xa628f1cb4d9e82ef,
 38        0xa68a205b2e5a7ddf,
 39        0xcd91de4547085aba,
 40        0x91d50792876a202,
 41        0x5d543a95414e7f1,
 42    ];
 43
 44    /// COFACTOR_INV = COFACTOR^{-1} mod r
 45    /// 26652489039290660355457965112010883481355318854675681319708643586776743290055
 46    const COFACTOR_INV: Fr =
 47        MontFp!("26652489039290660355457965112010883481355318854675681319708643586776743290055");
 48}
 49
 50impl SWCurveConfig for Parameters {
 51    /// COEFF_A = [0, 0]
 52    const COEFF_A: Fq2 = Fq2::new(g1::Parameters::COEFF_A, g1::Parameters::COEFF_A);
 53
 54    /// COEFF_B = [4, 4]
 55    const COEFF_B: Fq2 = Fq2::new(g1::Parameters::COEFF_B, g1::Parameters::COEFF_B);
 56
 57    /// AFFINE_GENERATOR_COEFFS = (G2_GENERATOR_X, G2_GENERATOR_Y)
 58    const GENERATOR: G2Affine = G2Affine::new_unchecked(G2_GENERATOR_X, G2_GENERATOR_Y);
 59
 60    #[inline(always)]
 61    fn mul_by_a(_: Self::BaseField) -> Self::BaseField {
 62        Self::BaseField::zero()
 63    }
 64
 65    fn is_in_correct_subgroup_assuming_on_curve(point: &G2Affine) -> bool {
 66        // Algorithm from Section 4 of https://eprint.iacr.org/2021/1130.
 67        //
 68        // Checks that [p]P = [X]P
 69
 70        let mut x_times_point = point.mul_bigint(crate::Parameters::X);
 71        if crate::Parameters::X_IS_NEGATIVE {
 72            x_times_point = -x_times_point;
 73        }
 74
 75        let p_times_point = p_power_endomorphism(point);
 76
 77        x_times_point.eq(&p_times_point)
 78    }
 79
 80    #[inline]
 81    fn clear_cofactor(p: &G2Affine) -> G2Affine {
 82        // Based on Section 4.1 of https://eprint.iacr.org/2017/419.pdf
 83        // [h(ψ)]P = [x^2 − x − 1]P + [x − 1]ψ(P) + (ψ^2)(2P)
 84
 85        // x = -15132376222941642752
 86        // When multiplying, use -c1 instead, and then negate the result. That's much
 87        // more efficient, since the scalar -c1 has less limbs and a much lower Hamming
 88        // weight.
 89        let x: &'static [u64] = crate::Parameters::X;
 90        let p_projective = p.into_group();
 91
 92        // [x]P
 93        let x_p = Parameters::mul_affine(p, &x).neg();
 94        // ψ(P)
 95        let psi_p = p_power_endomorphism(&p);
 96        // (ψ^2)(2P)
 97        let mut psi2_p2 = double_p_power_endomorphism(&p_projective.double());
 98
 99        // tmp = [x]P + ψ(P)
100        let mut tmp = x_p.clone();
101        tmp += &psi_p;
102
103        // tmp2 = [x^2]P + [x]ψ(P)
104        let mut tmp2: Projective<Parameters> = tmp;
105        tmp2 = tmp2.mul_bigint(x).neg();
106
107        // add up all the terms
108        psi2_p2 += tmp2;
109        psi2_p2 -= x_p;
110        psi2_p2 += &-psi_p;
111        (psi2_p2 - p_projective).into_affine()
112    }
113
114    fn deserialize_with_mode<R: ark_serialize::Read>(
115        mut reader: R,
116        compress: ark_serialize::Compress,
117        validate: ark_serialize::Validate,
118    ) -> Result<Affine<Self>, ark_serialize::SerializationError> {
119        let p = if compress == ark_serialize::Compress::Yes {
120            read_g2_compressed(&mut reader)?
121        } else {
122            read_g2_uncompressed(&mut reader)?
123        };
124
125        if validate == ark_serialize::Validate::Yes && !p.is_in_correct_subgroup_assuming_on_curve()
126        {
127            return Err(SerializationError::InvalidData);
128        }
129        Ok(p)
130    }
131
132    fn serialize_with_mode<W: ark_serialize::Write>(
133        item: &Affine<Self>,
134        mut writer: W,
135        compress: ark_serialize::Compress,
136    ) -> Result<(), SerializationError> {
137        let encoding = EncodingFlags {
138            is_compressed: compress == ark_serialize::Compress::Yes,
139            is_infinity: item.is_zero(),
140            is_lexographically_largest: item.y > -item.y,
141        };
142        let mut p = *item;
143        if encoding.is_infinity {
144            p = G2Affine::zero();
145        }
146
147        let mut x_bytes = [0u8; G2_SERIALIZED_SIZE];
148        let c1_bytes = serialize_fq(p.x.c1);
149        let c0_bytes = serialize_fq(p.x.c0);
150        x_bytes[0..48].copy_from_slice(&c1_bytes[..]);
151        x_bytes[48..96].copy_from_slice(&c0_bytes[..]);
152        if encoding.is_compressed {
153            let mut bytes: [u8; G2_SERIALIZED_SIZE] = x_bytes;
154
155            encoding.encode_flags(&mut bytes);
156            writer.write_all(&bytes)?;
157        } else {
158            let mut bytes = [0u8; 2 * G2_SERIALIZED_SIZE];
159
160            let mut y_bytes = [0u8; G2_SERIALIZED_SIZE];
161            let c1_bytes = serialize_fq(p.y.c1);
162            let c0_bytes = serialize_fq(p.y.c0);
163            y_bytes[0..48].copy_from_slice(&c1_bytes[..]);
164            y_bytes[48..96].copy_from_slice(&c0_bytes[..]);
165            bytes[0..G2_SERIALIZED_SIZE].copy_from_slice(&x_bytes);
166            bytes[G2_SERIALIZED_SIZE..].copy_from_slice(&y_bytes);
167
168            encoding.encode_flags(&mut bytes);
169            writer.write_all(&bytes)?;
170        };
171
172        Ok(())
173    }
174
175    fn serialized_size(compress: ark_serialize::Compress) -> usize {
176        if compress == Compress::Yes {
177            G2_SERIALIZED_SIZE
178        } else {
179            2 * G2_SERIALIZED_SIZE
180        }
181    }
182}
183
184pub const G2_GENERATOR_X: Fq2 = Fq2::new(G2_GENERATOR_X_C0, G2_GENERATOR_X_C1);
185pub const G2_GENERATOR_Y: Fq2 = Fq2::new(G2_GENERATOR_Y_C0, G2_GENERATOR_Y_C1);
186
187/// G2_GENERATOR_X_C0 =
188/// 352701069587466618187139116011060144890029952792775240219908644239793785735715026873347600343865175952761926303160
189pub const G2_GENERATOR_X_C0: Fq = MontFp!("352701069587466618187139116011060144890029952792775240219908644239793785735715026873347600343865175952761926303160");
190
191/// G2_GENERATOR_X_C1 =
192/// 3059144344244213709971259814753781636986470325476647558659373206291635324768958432433509563104347017837885763365758
193pub const G2_GENERATOR_X_C1: Fq = MontFp!("3059144344244213709971259814753781636986470325476647558659373206291635324768958432433509563104347017837885763365758");
194
195/// G2_GENERATOR_Y_C0 =
196/// 1985150602287291935568054521177171638300868978215655730859378665066344726373823718423869104263333984641494340347905
197pub const G2_GENERATOR_Y_C0: Fq = MontFp!("1985150602287291935568054521177171638300868978215655730859378665066344726373823718423869104263333984641494340347905");
198
199/// G2_GENERATOR_Y_C1 =
200/// 927553665492332455747201965776037880757740193453592970025027978793976877002675564980949289727957565575433344219582
201pub const G2_GENERATOR_Y_C1: Fq = MontFp!("927553665492332455747201965776037880757740193453592970025027978793976877002675564980949289727957565575433344219582");
202
203// psi(x,y) = (x**p * PSI_X, y**p * PSI_Y) is the Frobenius composed
204// with the quadratic twist and its inverse
205
206// PSI_X = 1/(u+1)^((p-1)/3)
207pub const P_POWER_ENDOMORPHISM_COEFF_0 : Fq2 = Fq2::new(
208    Fq::ZERO,
209    MontFp!(
210                "4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939437"
211    )
212);
213
214// PSI_Y = 1/(u+1)^((p-1)/2)
215pub const P_POWER_ENDOMORPHISM_COEFF_1: Fq2 = Fq2::new(
216    MontFp!(
217                "2973677408986561043442465346520108879172042883009249989176415018091420807192182638567116318576472649347015917690530"),
218    MontFp!(
219                "1028732146235106349975324479215795277384839936929757896155643118032610843298655225875571310552543014690878354869257")
220);
221
222pub const DOUBLE_P_POWER_ENDOMORPHISM: Fq2 = Fq2::new(
223    MontFp!("4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939436"),
224    Fq::ZERO
225);
226
227pub fn p_power_endomorphism(p: &Affine<Parameters>) -> Affine<Parameters> {
228    // The p-power endomorphism for G2 is defined as follows:
229    // 1. Note that G2 is defined on curve E': y^2 = x^3 + 4(u+1).
230    //    To map a point (x, y) in E' to (s, t) in E,
231    //    one set s = x / ((u+1) ^ (1/3)), t = y / ((u+1) ^ (1/2)),
232    //    because E: y^2 = x^3 + 4.
233    // 2. Apply the Frobenius endomorphism (s, t) => (s', t'),
234    //    another point on curve E, where s' = s^p, t' = t^p.
235    // 3. Map the point from E back to E'; that is,
236    //    one set x' = s' * ((u+1) ^ (1/3)), y' = t' * ((u+1) ^ (1/2)).
237    //
238    // To sum up, it maps
239    // (x,y) -> (x^p / ((u+1)^((p-1)/3)), y^p / ((u+1)^((p-1)/2)))
240    // as implemented in the code as follows.
241
242    let mut res = *p;
243    res.x.frobenius_map(1);
244    res.y.frobenius_map(1);
245
246    let tmp_x = res.x.clone();
247    res.x.c0 = -P_POWER_ENDOMORPHISM_COEFF_0.c1 * &tmp_x.c1;
248    res.x.c1 = P_POWER_ENDOMORPHISM_COEFF_0.c1 * &tmp_x.c0;
249    res.y *= P_POWER_ENDOMORPHISM_COEFF_1;
250
251    res
252}
253
254/// For a p-power endomorphism psi(P), compute psi(psi(P))
255pub fn double_p_power_endomorphism(p: &Projective<Parameters>) -> Projective<Parameters> {
256    let mut res = *p;
257
258    res.x *= DOUBLE_P_POWER_ENDOMORPHISM;
259    res.y = res.y.neg();
260
261    res
262}
263
264#[cfg(test)]
265mod test {
266
267    use super::*;
268    use ark_std::UniformRand;
269
270    #[test]
271    fn test_cofactor_clearing() {
272        // multiplying by h_eff and clearing the cofactor by the efficient
273        // endomorphism-based method should yield the same result.
274        let h_eff: &'static [u64] = &[
275            0xe8020005aaa95551,
276            0x59894c0adebbf6b4,
277            0xe954cbc06689f6a3,
278            0x2ec0ec69d7477c1a,
279            0x6d82bf015d1212b0,
280            0x329c2f178731db95,
281            0x9986ff031508ffe1,
282            0x88e2a8e9145ad768,
283            0x584c6a0ea91b3528,
284            0xbc69f08f2ee75b3,
285        ];
286
287        let mut rng = ark_std::test_rng();
288        const SAMPLES: usize = 10;
289        for _ in 0..SAMPLES {
290            let p = Affine::<g2::Parameters>::rand(&mut rng);
291            let optimised = p.clear_cofactor().into_group();
292            let naive = g2::Parameters::mul_affine(&p, h_eff);
293            assert_eq!(optimised, naive);
294        }
295    }
296}