zksync_pairing/compact_bn256/
ec.rs

1macro_rules! curve_impl {
2    (
3        $name:expr,
4        $projective:ident,
5        $affine:ident,
6        $prepared:ident,
7        $basefield:ident,
8        $scalarfield:ident,
9        $uncompressed:ident,
10        $compressed:ident,
11        $pairing:ident
12    ) => {
13        #[derive(Copy, Clone, PartialEq, Eq, Debug, ::serde::Serialize, ::serde::Deserialize)]
14        pub struct $affine {
15            pub(crate) x: $basefield,
16            pub(crate) y: $basefield,
17        }
18
19        impl ::std::fmt::Display for $affine {
20            fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
21                if self.x.is_zero() && self.y.is_zero() {
22                    write!(f, "{}(Infinity)", $name)
23                } else {
24                    write!(f, "{}(x={}, y={})", $name, self.x, self.y)
25                }
26            }
27        }
28
29        #[derive(Copy, Clone, Debug, Eq)]
30        pub struct $projective {
31            pub(crate) x: $basefield,
32            pub(crate) y: $basefield,
33            pub(crate) z: $basefield,
34        }
35
36        impl ::std::fmt::Display for $projective {
37            fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
38                write!(f, "{}", self.into_affine())
39            }
40        }
41
42        impl PartialEq for $projective {
43            fn eq(&self, other: &$projective) -> bool {
44                if self.is_zero() {
45                    return other.is_zero();
46                }
47
48                if other.is_zero() {
49                    return false;
50                }
51
52                // The points (X, Y, Z) and (X', Y', Z')
53                // are equal when (X * Z^2) = (X' * Z'^2)
54                // and (Y * Z^3) = (Y' * Z'^3).
55
56                let mut z1 = self.z;
57                z1.square();
58                let mut z2 = other.z;
59                z2.square();
60
61                let mut tmp1 = self.x;
62                tmp1.mul_assign(&z2);
63
64                let mut tmp2 = other.x;
65                tmp2.mul_assign(&z1);
66
67                if tmp1 != tmp2 {
68                    return false;
69                }
70
71                z1.mul_assign(&self.z);
72                z2.mul_assign(&other.z);
73                z2.mul_assign(&self.y);
74                z1.mul_assign(&other.y);
75
76                if z1 != z2 {
77                    return false;
78                }
79
80                true
81            }
82        }
83
84        impl $affine {
85            fn mul_bits<S: AsRef<[u64]>>(&self, bits: BitIterator<S>) -> $projective {
86                let mut res = $projective::zero();
87                for i in bits {
88                    res.double();
89                    if i {
90                        res.add_assign_mixed(self)
91                    }
92                }
93                res
94            }
95
96            /// Attempts to construct an affine point given an x-coordinate. The
97            /// point is not guaranteed to be in the prime order subgroup.
98            ///
99            /// If and only if `greatest` is set will the lexicographically
100            /// largest y-coordinate be selected.
101            fn get_point_from_x(x: $basefield, greatest: bool) -> Option<$affine> {
102                // Compute x^3 + b
103                let mut x3b = x;
104                x3b.square();
105                x3b.mul_assign(&x);
106                x3b.add_assign(&$affine::get_coeff_b());
107
108                x3b.sqrt().map(|y| {
109                    let mut negy = y;
110                    negy.negate();
111
112                    $affine {
113                        x: x,
114                        y: if (y < negy) ^ greatest { y } else { negy },
115                    }
116                })
117            }
118
119            fn is_on_curve(&self) -> bool {
120                if self.is_zero() {
121                    true
122                } else {
123                    // Check that the point is on the curve
124                    let mut y2 = self.y;
125                    y2.square();
126
127                    let mut x3b = self.x;
128                    x3b.square();
129                    x3b.mul_assign(&self.x);
130                    x3b.add_assign(&Self::get_coeff_b());
131
132                    y2 == x3b
133                }
134            }
135        }
136
137        impl CurveAffine for $affine {
138            type Engine = Bn256;
139            type Scalar = $scalarfield;
140            type Base = $basefield;
141            type Prepared = $prepared;
142            type Projective = $projective;
143            type Uncompressed = $uncompressed;
144            type Compressed = $compressed;
145            type Pair = $pairing;
146            type PairingResult = Fq12;
147
148            fn zero() -> Self {
149                $affine {
150                    x: $basefield::zero(),
151                    y: $basefield::zero(),
152                }
153            }
154
155            fn one() -> Self {
156                Self::get_generator()
157            }
158
159            fn is_zero(&self) -> bool {
160                self.x.is_zero() && self.y.is_zero()
161            }
162
163            fn mul<S: Into<<Self::Scalar as PrimeField>::Repr>>(&self, by: S) -> $projective {
164                let bits = BitIterator::new(by.into());
165                self.mul_bits(bits)
166            }
167
168            fn negate(&mut self) {
169                if !self.is_zero() {
170                    self.y.negate();
171                }
172            }
173
174            fn prepare(&self) -> Self::Prepared {
175                $prepared::from_affine(*self)
176            }
177
178            fn pairing_with(&self, other: &Self::Pair) -> Self::PairingResult {
179                self.perform_pairing(other)
180            }
181
182            fn into_projective(&self) -> $projective {
183                (*self).into()
184            }
185
186            #[inline(always)]
187            fn as_xy(&self) -> (&Self::Base, &Self::Base) {
188                (&self.x, &self.y)
189            }
190
191            #[inline(always)]
192            fn into_xy_unchecked(self) -> (Self::Base, Self::Base) {
193                (self.x, self.y)
194            }
195
196            #[inline(always)]
197            fn from_xy_unchecked(x: Self::Base, y: Self::Base) -> Self {
198                Self { x: x, y: y }
199            }
200
201            fn from_xy_checked(x: Self::Base, y: Self::Base) -> Result<Self, GroupDecodingError> {
202                let affine = Self { x: x, y: y };
203
204                if !affine.is_on_curve() {
205                    Err(GroupDecodingError::NotOnCurve)
206                } else {
207                    Ok(affine)
208                }
209            }
210
211            fn a_coeff() -> Self::Base {
212                Self::Base::zero()
213            }
214
215            fn b_coeff() -> Self::Base {
216                $affine::get_coeff_b()
217            }
218        }
219
220        impl CurveProjective for $projective {
221            type Engine = Bn256;
222            type Scalar = $scalarfield;
223            type Base = $basefield;
224            type Affine = $affine;
225
226            // The point at infinity is always represented by
227            // Z = 0.
228            fn zero() -> Self {
229                $projective {
230                    x: $basefield::zero(),
231                    y: $basefield::one(),
232                    z: $basefield::zero(),
233                }
234            }
235
236            fn one() -> Self {
237                $affine::one().into()
238            }
239
240            // The point at infinity is always represented by
241            // Z = 0.
242            fn is_zero(&self) -> bool {
243                self.z.is_zero()
244            }
245
246            fn is_normalized(&self) -> bool {
247                self.is_zero() || self.z == $basefield::one()
248            }
249
250            fn batch_normalization(v: &mut [Self]) {
251                // Montgomery’s Trick and Fast Implementation of Masked AES
252                // Genelle, Prouff and Quisquater
253                // Section 3.2
254
255                // First pass: compute [a, ab, abc, ...]
256                let mut prod = Vec::with_capacity(v.len());
257                let mut tmp = $basefield::one();
258                for g in v
259                    .iter_mut()
260                    // Ignore normalized elements
261                    .filter(|g| !g.is_normalized())
262                {
263                    tmp.mul_assign(&g.z);
264                    prod.push(tmp);
265                }
266
267                // Invert `tmp`.
268                tmp = tmp.inverse().unwrap(); // Guaranteed to be nonzero.
269
270                // Second pass: iterate backwards to compute inverses
271                for (g, s) in v
272                    .iter_mut()
273                    // Backwards
274                    .rev()
275                    // Ignore normalized elements
276                    .filter(|g| !g.is_normalized())
277                    // Backwards, skip last element, fill in one for last term.
278                    .zip(prod.into_iter().rev().skip(1).chain(Some($basefield::one())))
279                {
280                    // tmp := tmp * g.z; g.z := tmp * s = 1/z
281                    let mut newtmp = tmp;
282                    newtmp.mul_assign(&g.z);
283                    g.z = tmp;
284                    g.z.mul_assign(&s);
285                    tmp = newtmp;
286                }
287
288                // Perform affine transformations
289                for g in v.iter_mut().filter(|g| !g.is_normalized()) {
290                    let mut z = g.z; // 1/z
291                    z.square(); // 1/z^2
292                    g.x.mul_assign(&z); // x/z^2
293                    z.mul_assign(&g.z); // 1/z^3
294                    g.y.mul_assign(&z); // y/z^3
295                    g.z = $basefield::one(); // z = 1
296                }
297            }
298
299            fn double(&mut self) {
300                if self.is_zero() {
301                    return;
302                }
303
304                // Other than the point at infinity, no points on E or E'
305                // can double to equal the point at infinity, as y=0 is
306                // never true for points on the curve.
307
308                // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l
309
310                // A = X1^2
311                let mut a = self.x;
312                a.square();
313
314                // B = Y1^2
315                let mut b = self.y;
316                b.square();
317
318                // C = B^2
319                let mut c = b;
320                c.square();
321
322                // D = 2*((X1+B)2-A-C)
323                let mut d = self.x;
324                d.add_assign(&b);
325                d.square();
326                d.sub_assign(&a);
327                d.sub_assign(&c);
328                d.double();
329
330                // E = 3*A
331                let mut e = a;
332                e.double();
333                e.add_assign(&a);
334
335                // F = E^2
336                let mut f = e;
337                f.square();
338
339                // Z3 = 2*Y1*Z1
340                self.z.mul_assign(&self.y);
341                self.z.double();
342
343                // X3 = F-2*D
344                self.x = f;
345                self.x.sub_assign(&d);
346                self.x.sub_assign(&d);
347
348                // Y3 = E*(D-X3)-8*C
349                self.y = d;
350                self.y.sub_assign(&self.x);
351                self.y.mul_assign(&e);
352                c.double();
353                c.double();
354                c.double();
355                self.y.sub_assign(&c);
356            }
357
358            fn add_assign(&mut self, other: &Self) {
359                if self.is_zero() {
360                    *self = *other;
361                    return;
362                }
363
364                if other.is_zero() {
365                    return;
366                }
367
368                // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-add-2007-bl
369
370                // Z1Z1 = Z1^2
371                let mut z1z1 = self.z;
372                z1z1.square();
373
374                // Z2Z2 = Z2^2
375                let mut z2z2 = other.z;
376                z2z2.square();
377
378                // U1 = X1*Z2Z2
379                let mut u1 = self.x;
380                u1.mul_assign(&z2z2);
381
382                // U2 = X2*Z1Z1
383                let mut u2 = other.x;
384                u2.mul_assign(&z1z1);
385
386                // S1 = Y1*Z2*Z2Z2
387                let mut s1 = self.y;
388                s1.mul_assign(&other.z);
389                s1.mul_assign(&z2z2);
390
391                // S2 = Y2*Z1*Z1Z1
392                let mut s2 = other.y;
393                s2.mul_assign(&self.z);
394                s2.mul_assign(&z1z1);
395
396                if u1 == u2 && s1 == s2 {
397                    // The two points are equal, so we double.
398                    self.double();
399                } else {
400                    // If we're adding -a and a together, self.z becomes zero as H becomes zero.
401
402                    if u1 == u2 {
403                        // The two points are equal, so we double.
404                        (*self) = Self::zero();
405                        return;
406                    }
407
408                    // H = U2-U1
409                    let mut h = u2;
410                    h.sub_assign(&u1);
411
412                    // I = (2*H)^2
413                    let mut i = h;
414                    i.double();
415                    i.square();
416
417                    // J = H*I
418                    let mut j = h;
419                    j.mul_assign(&i);
420
421                    // r = 2*(S2-S1)
422                    let mut r = s2;
423                    r.sub_assign(&s1);
424                    r.double();
425
426                    // V = U1*I
427                    let mut v = u1;
428                    v.mul_assign(&i);
429
430                    // X3 = r^2 - J - 2*V
431                    self.x = r;
432                    self.x.square();
433                    self.x.sub_assign(&j);
434                    self.x.sub_assign(&v);
435                    self.x.sub_assign(&v);
436
437                    // Y3 = r*(V - X3) - 2*S1*J
438                    self.y = v;
439                    self.y.sub_assign(&self.x);
440                    self.y.mul_assign(&r);
441                    s1.mul_assign(&j); // S1 = S1 * J * 2
442                    s1.double();
443                    self.y.sub_assign(&s1);
444
445                    // Z3 = ((Z1+Z2)^2 - Z1Z1 - Z2Z2)*H
446                    self.z.add_assign(&other.z);
447                    self.z.square();
448                    self.z.sub_assign(&z1z1);
449                    self.z.sub_assign(&z2z2);
450                    self.z.mul_assign(&h);
451                }
452            }
453
454            fn add_assign_mixed(&mut self, other: &Self::Affine) {
455                if other.is_zero() {
456                    return;
457                }
458
459                if self.is_zero() {
460                    self.x = other.x;
461                    self.y = other.y;
462                    self.z = $basefield::one();
463                    return;
464                }
465
466                // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-madd-2007-bl
467
468                // Z1Z1 = Z1^2
469                let mut z1z1 = self.z;
470                z1z1.square();
471
472                // U2 = X2*Z1Z1
473                let mut u2 = other.x;
474                u2.mul_assign(&z1z1);
475
476                // S2 = Y2*Z1*Z1Z1
477                let mut s2 = other.y;
478                s2.mul_assign(&self.z);
479                s2.mul_assign(&z1z1);
480
481                if self.x == u2 && self.y == s2 {
482                    // The two points are equal, so we double.
483                    self.double();
484                } else {
485                    // If we're adding -a and a together, self.z becomes zero as H becomes zero.
486
487                    // H = U2-X1
488                    let mut h = u2;
489                    h.sub_assign(&self.x);
490
491                    // HH = H^2
492                    let mut hh = h;
493                    hh.square();
494
495                    // I = 4*HH
496                    let mut i = hh;
497                    i.double();
498                    i.double();
499
500                    // J = H*I
501                    let mut j = h;
502                    j.mul_assign(&i);
503
504                    // r = 2*(S2-Y1)
505                    let mut r = s2;
506                    r.sub_assign(&self.y);
507                    r.double();
508
509                    // V = X1*I
510                    let mut v = self.x;
511                    v.mul_assign(&i);
512
513                    // X3 = r^2 - J - 2*V
514                    self.x = r;
515                    self.x.square();
516                    self.x.sub_assign(&j);
517                    self.x.sub_assign(&v);
518                    self.x.sub_assign(&v);
519
520                    // Y3 = r*(V-X3)-2*Y1*J
521                    j.mul_assign(&self.y); // J = 2*Y1*J
522                    j.double();
523                    self.y = v;
524                    self.y.sub_assign(&self.x);
525                    self.y.mul_assign(&r);
526                    self.y.sub_assign(&j);
527
528                    // Z3 = (Z1+H)^2-Z1Z1-HH
529                    self.z.add_assign(&h);
530                    self.z.square();
531                    self.z.sub_assign(&z1z1);
532                    self.z.sub_assign(&hh);
533                }
534            }
535
536            fn negate(&mut self) {
537                if !self.is_zero() {
538                    self.y.negate()
539                }
540            }
541
542            fn mul_assign<S: Into<<Self::Scalar as PrimeField>::Repr>>(&mut self, other: S) {
543                let mut res = Self::zero();
544
545                let mut found_one = false;
546
547                for i in BitIterator::new(other.into()) {
548                    if found_one {
549                        res.double();
550                    } else {
551                        found_one = i;
552                    }
553
554                    if i {
555                        res.add_assign(self);
556                    }
557                }
558
559                *self = res;
560            }
561
562            fn into_affine(&self) -> $affine {
563                (*self).into()
564            }
565
566            fn recommended_wnaf_for_scalar(scalar: <Self::Scalar as PrimeField>::Repr) -> usize {
567                Self::empirical_recommended_wnaf_for_scalar(scalar)
568            }
569
570            fn recommended_wnaf_for_num_scalars(num_scalars: usize) -> usize {
571                Self::empirical_recommended_wnaf_for_num_scalars(num_scalars)
572            }
573
574            fn as_xyz(&self) -> (&Self::Base, &Self::Base, &Self::Base) {
575                (&self.x, &self.y, &self.z)
576            }
577
578            fn into_xyz_unchecked(self) -> (Self::Base, Self::Base, Self::Base) {
579                (self.x, self.y, self.z)
580            }
581
582            fn from_xyz_unchecked(x: Self::Base, y: Self::Base, z: Self::Base) -> Self {
583                Self { x, y, z }
584            }
585
586            fn from_xyz_checked(_x: Self::Base, _y: Self::Base, _z: Self::Base) -> Result<Self, GroupDecodingError> {
587                unimplemented!("on curve check is not implemented for BLS12-381 projective")
588            }
589        }
590
591        // The affine point X, Y is represented in the jacobian
592        // coordinates with Z = 1.
593        impl From<$affine> for $projective {
594            fn from(p: $affine) -> $projective {
595                if p.is_zero() {
596                    $projective::zero()
597                } else {
598                    $projective {
599                        x: p.x,
600                        y: p.y,
601                        z: $basefield::one(),
602                    }
603                }
604            }
605        }
606
607        // The projective point X, Y, Z is represented in the affine
608        // coordinates as X/Z^2, Y/Z^3.
609        impl From<$projective> for $affine {
610            fn from(p: $projective) -> $affine {
611                if p.is_zero() {
612                    $affine::zero()
613                } else if p.z == $basefield::one() {
614                    // If Z is one, the point is already normalized.
615                    $affine { x: p.x, y: p.y }
616                } else {
617                    // Z is nonzero, so it must have an inverse in a field.
618                    let zinv = p.z.inverse().unwrap();
619                    let mut zinv_powered = zinv;
620                    zinv_powered.square();
621
622                    // X/Z^2
623                    let mut x = p.x;
624                    x.mul_assign(&zinv_powered);
625
626                    // Y/Z^3
627                    let mut y = p.y;
628                    zinv_powered.mul_assign(&zinv);
629                    y.mul_assign(&zinv_powered);
630
631                    $affine { x: x, y: y }
632                }
633            }
634        }
635    };
636}
637
638pub mod g1 {
639    use super::super::{Bn256, Fq, Fq12, FqRepr, Fr, FrRepr};
640    use super::g2::G2Affine;
641    use crate::{CurveAffine, CurveProjective, EncodedPoint, Engine, GroupDecodingError, RawEncodable};
642    use ff::{BitIterator, Field, PrimeField, PrimeFieldRepr, SqrtField};
643    use rand::{Rand, Rng};
644    use std::fmt;
645
646    curve_impl!("G1", G1, G1Affine, G1Prepared, Fq, Fr, G1Uncompressed, G1Compressed, G2Affine);
647
648    impl RawEncodable for G1Affine {
649        fn into_raw_uncompressed_le(&self) -> Self::Uncompressed {
650            let mut res = Self::Uncompressed::empty();
651            {
652                let mut writer = &mut res.0[..];
653
654                self.x.into_raw_repr().write_le(&mut writer).unwrap();
655                self.y.into_raw_repr().write_le(&mut writer).unwrap();
656            }
657
658            res
659        }
660
661        /// Creates a point from raw encoded coordinates without checking on curve
662        fn from_raw_uncompressed_le_unchecked(encoded: &Self::Uncompressed, _infinity: bool) -> Result<Self, GroupDecodingError> {
663            let copy = encoded.0;
664
665            if copy.iter().all(|b| *b == 0) {
666                return Ok(Self::zero());
667            }
668
669            let mut x = FqRepr([0; 4]);
670            let mut y = FqRepr([0; 4]);
671
672            {
673                let mut reader = &copy[..];
674                x.read_le(&mut reader).unwrap();
675                y.read_le(&mut reader).unwrap();
676            }
677
678            Ok(G1Affine {
679                x: Fq::from_raw_repr(x).map_err(|e| GroupDecodingError::CoordinateDecodingError("x coordinate", e))?,
680                y: Fq::from_raw_repr(y).map_err(|e| GroupDecodingError::CoordinateDecodingError("y coordinate", e))?,
681            })
682        }
683
684        fn from_raw_uncompressed_le(encoded: &Self::Uncompressed, _infinity: bool) -> Result<Self, GroupDecodingError> {
685            let affine = Self::from_raw_uncompressed_le_unchecked(&encoded, _infinity)?;
686
687            if !affine.is_on_curve() {
688                Err(GroupDecodingError::NotOnCurve)
689            } else {
690                Ok(affine)
691            }
692        }
693    }
694
695    #[derive(Copy, Clone)]
696    pub struct G1Uncompressed([u8; 64]);
697
698    impl Rand for G1 {
699        fn rand<R: Rng>(rng: &mut R) -> Self {
700            loop {
701                let x = rng.gen();
702                let greatest = rng.gen();
703
704                if let Some(p) = G1Affine::get_point_from_x(x, greatest) {
705                    if !p.is_zero() {
706                        if p.is_on_curve() {
707                            return p.into_projective();
708                        }
709                    }
710                }
711            }
712        }
713    }
714
715    impl Rand for G1Affine {
716        fn rand<R: Rng>(rng: &mut R) -> Self {
717            loop {
718                let x = rng.gen();
719                let greatest = rng.gen();
720
721                if let Some(p) = G1Affine::get_point_from_x(x, greatest) {
722                    if !p.is_zero() {
723                        if p.is_on_curve() {
724                            return p;
725                        }
726                    }
727                }
728            }
729        }
730    }
731
732    impl AsRef<[u8]> for G1Uncompressed {
733        fn as_ref(&self) -> &[u8] {
734            &self.0
735        }
736    }
737
738    impl AsMut<[u8]> for G1Uncompressed {
739        fn as_mut(&mut self) -> &mut [u8] {
740            &mut self.0
741        }
742    }
743
744    impl fmt::Debug for G1Uncompressed {
745        fn fmt(&self, formatter: &mut fmt::Formatter) -> Result<(), fmt::Error> {
746            self.0[..].fmt(formatter)
747        }
748    }
749
750    impl EncodedPoint for G1Uncompressed {
751        type Affine = G1Affine;
752
753        fn empty() -> Self {
754            G1Uncompressed([0; 64])
755        }
756        fn size() -> usize {
757            64
758        }
759        fn into_affine(&self) -> Result<G1Affine, GroupDecodingError> {
760            let affine = self.into_affine_unchecked()?;
761
762            if !affine.is_on_curve() {
763                Err(GroupDecodingError::NotOnCurve)
764            } else {
765                Ok(affine)
766            }
767        }
768        fn into_affine_unchecked(&self) -> Result<G1Affine, GroupDecodingError> {
769            // Create a copy of this representation.
770            let mut copy = self.0;
771
772            if copy[0] & (1 << 6) != 0 {
773                // This is the point at infinity, which means that if we mask away
774                // the first two bits, the entire representation should consist
775                // of zeroes.
776                copy[0] &= 0x3f;
777
778                if copy.iter().all(|b| *b == 0) {
779                    Ok(G1Affine::zero())
780                } else {
781                    Err(GroupDecodingError::UnexpectedInformation)
782                }
783            } else {
784                if copy[0] & (1 << 7) != 0 {
785                    // The bit indicating the y-coordinate should be lexicographically
786                    // largest is set, but this is an uncompressed element.
787                    return Err(GroupDecodingError::UnexpectedInformation);
788                }
789
790                // Unset the two most significant bits.
791                copy[0] &= 0x3f;
792
793                let mut x = FqRepr([0; 4]);
794                let mut y = FqRepr([0; 4]);
795
796                {
797                    let mut reader = &copy[..];
798
799                    x.read_be(&mut reader).unwrap();
800                    y.read_be(&mut reader).unwrap();
801                }
802
803                Ok(G1Affine {
804                    x: Fq::from_repr(x).map_err(|e| GroupDecodingError::CoordinateDecodingError("x coordinate", e))?,
805                    y: Fq::from_repr(y).map_err(|e| GroupDecodingError::CoordinateDecodingError("y coordinate", e))?,
806                })
807            }
808        }
809        fn from_affine(affine: G1Affine) -> Self {
810            let mut res = Self::empty();
811
812            if affine.is_zero() {
813                // Set the second-most significant bit to indicate this point
814                // is at infinity.
815                res.0[0] |= 1 << 6;
816            } else {
817                let mut writer = &mut res.0[..];
818
819                affine.x.into_repr().write_be(&mut writer).unwrap();
820                affine.y.into_repr().write_be(&mut writer).unwrap();
821            }
822
823            res
824        }
825    }
826
827    #[derive(Copy, Clone)]
828    pub struct G1Compressed([u8; 32]);
829
830    impl AsRef<[u8]> for G1Compressed {
831        fn as_ref(&self) -> &[u8] {
832            &self.0
833        }
834    }
835
836    impl AsMut<[u8]> for G1Compressed {
837        fn as_mut(&mut self) -> &mut [u8] {
838            &mut self.0
839        }
840    }
841
842    impl fmt::Debug for G1Compressed {
843        fn fmt(&self, formatter: &mut fmt::Formatter) -> Result<(), fmt::Error> {
844            self.0[..].fmt(formatter)
845        }
846    }
847
848    impl EncodedPoint for G1Compressed {
849        type Affine = G1Affine;
850
851        fn empty() -> Self {
852            G1Compressed([0; 32])
853        }
854        fn size() -> usize {
855            32
856        }
857        fn into_affine(&self) -> Result<G1Affine, GroupDecodingError> {
858            let affine = self.into_affine_unchecked()?;
859
860            // NB: Decompression guarantees that it is on the curve already.
861
862            Ok(affine)
863        }
864        fn into_affine_unchecked(&self) -> Result<G1Affine, GroupDecodingError> {
865            // Create a copy of this representation.
866            let mut copy = self.0;
867
868            if copy[0] & (1 << 6) != 0 {
869                // This is the point at infinity, which means that if we mask away
870                // the first two bits, the entire representation should consist
871                // of zeroes.
872                copy[0] &= 0x3f;
873
874                if copy.iter().all(|b| *b == 0) {
875                    Ok(G1Affine::zero())
876                } else {
877                    Err(GroupDecodingError::UnexpectedInformation)
878                }
879            } else {
880                // Determine if the intended y coordinate must be greater
881                // lexicographically.
882                let greatest = copy[0] & (1 << 7) != 0;
883
884                // Unset the two most significant bits.
885                copy[0] &= 0x3f;
886
887                let mut x = FqRepr([0; 4]);
888
889                {
890                    let mut reader = &copy[..];
891
892                    x.read_be(&mut reader).unwrap();
893                }
894
895                // Interpret as Fq element.
896                let x = Fq::from_repr(x).map_err(|e| GroupDecodingError::CoordinateDecodingError("x coordinate", e))?;
897
898                G1Affine::get_point_from_x(x, greatest).ok_or(GroupDecodingError::NotOnCurve)
899            }
900        }
901        fn from_affine(affine: G1Affine) -> Self {
902            let mut res = Self::empty();
903
904            if affine.is_zero() {
905                // Set the second-most significant bit to indicate this point
906                // is at infinity.
907                res.0[0] |= 1 << 6;
908            } else {
909                {
910                    let mut writer = &mut res.0[..];
911
912                    affine.x.into_repr().write_be(&mut writer).unwrap();
913                }
914
915                let mut negy = affine.y;
916                negy.negate();
917
918                // Set the third most significant bit if the correct y-coordinate
919                // is lexicographically largest.
920                if affine.y > negy {
921                    res.0[0] |= 1 << 7;
922                }
923            }
924
925            res
926        }
927    }
928
929    impl G1Affine {
930        // fn scale_by_cofactor(&self) -> G1 {
931        //     self.into_projective()
932        // }
933
934        fn get_generator() -> Self {
935            G1Affine {
936                x: super::super::fq::G1_GENERATOR_X,
937                y: super::super::fq::G1_GENERATOR_Y,
938            }
939        }
940
941        fn get_coeff_b() -> Fq {
942            super::super::fq::B_COEFF
943        }
944
945        fn perform_pairing(&self, other: &G2Affine) -> Fq12 {
946            super::super::Bn256::pairing(*self, *other)
947        }
948    }
949
950    impl G1 {
951        fn empirical_recommended_wnaf_for_scalar(scalar: FrRepr) -> usize {
952            let num_bits = scalar.num_bits() as usize;
953
954            if num_bits >= 130 {
955                4
956            } else if num_bits >= 34 {
957                3
958            } else {
959                2
960            }
961        }
962
963        fn empirical_recommended_wnaf_for_num_scalars(num_scalars: usize) -> usize {
964            const RECOMMENDATIONS: [usize; 12] = [1, 3, 7, 20, 43, 120, 273, 563, 1630, 3128, 7933, 62569];
965
966            let mut ret = 4;
967            for r in &RECOMMENDATIONS {
968                if num_scalars > *r {
969                    ret += 1;
970                } else {
971                    break;
972                }
973            }
974
975            ret
976        }
977    }
978
979    #[derive(Clone, Debug)]
980    pub struct G1Prepared(pub(crate) G1Affine);
981
982    impl G1Prepared {
983        pub fn is_zero(&self) -> bool {
984            self.0.is_zero()
985        }
986
987        pub fn from_affine(p: G1Affine) -> Self {
988            G1Prepared(p)
989        }
990    }
991
992    #[test]
993    fn g1_generator() {
994        use SqrtField;
995
996        let mut x = Fq::zero();
997        let mut i = 0;
998        loop {
999            // y^2 = x^3 + b
1000            let mut rhs = x;
1001            rhs.square();
1002            rhs.mul_assign(&x);
1003            rhs.add_assign(&G1Affine::get_coeff_b());
1004
1005            if let Some(y) = rhs.sqrt() {
1006                let yrepr = y.into_repr();
1007                let mut negy = y;
1008                negy.negate();
1009                let negyrepr = negy.into_repr();
1010
1011                let p = G1Affine {
1012                    x: x,
1013                    y: if yrepr < negyrepr { y } else { negy },
1014                };
1015
1016                let g1 = p.into_projective();
1017                if !g1.is_zero() {
1018                    assert_eq!(i, 1);
1019                    let g1 = G1Affine::from(g1);
1020
1021                    assert_eq!(g1, G1Affine::one());
1022                    break;
1023                }
1024            }
1025
1026            i += 1;
1027            x.add_assign(&Fq::one());
1028        }
1029    }
1030
1031    #[test]
1032
1033    fn test_base_point_addition_and_doubling() {
1034        let mut a = G1::one();
1035        print!("{}\n\n", a);
1036
1037        a.add_assign(&G1::one());
1038
1039        print!("{}\n\n", a);
1040    }
1041
1042    #[test]
1043    fn g1_curve_tests() {
1044        crate::tests::curve::curve_tests::<G1>();
1045        crate::tests::curve::random_transformation_tests::<G1>();
1046    }
1047}
1048
1049pub mod g2 {
1050    use super::super::{Bn256, Fq, Fq12, Fq2, FqRepr, Fr, FrRepr};
1051    use super::g1::G1Affine;
1052    use crate::{CurveAffine, CurveProjective, EncodedPoint, Engine, GroupDecodingError};
1053    use ff::{BitIterator, Field, PrimeField, PrimeFieldRepr, SqrtField};
1054    use rand::{Rand, Rng};
1055    use std::fmt;
1056
1057    curve_impl!("G2", G2, G2Affine, G2Prepared, Fq2, Fr, G2Uncompressed, G2Compressed, G1Affine);
1058
1059    impl Rand for G2 {
1060        fn rand<R: Rng>(rng: &mut R) -> Self {
1061            loop {
1062                let x = rng.gen();
1063                let greatest = rng.gen();
1064
1065                if let Some(p) = G2Affine::get_point_from_x(x, greatest) {
1066                    if !p.is_zero() {
1067                        if p.is_on_curve() {
1068                            return p.scale_by_cofactor();
1069                        }
1070                    }
1071                }
1072            }
1073        }
1074    }
1075
1076    impl Rand for G2Affine {
1077        fn rand<R: Rng>(rng: &mut R) -> Self {
1078            let r = G2::rand(rng);
1079            return r.into_affine();
1080        }
1081    }
1082
1083    #[derive(Copy, Clone)]
1084    pub struct G2Uncompressed([u8; 128]);
1085
1086    impl AsRef<[u8]> for G2Uncompressed {
1087        fn as_ref(&self) -> &[u8] {
1088            &self.0
1089        }
1090    }
1091
1092    impl AsMut<[u8]> for G2Uncompressed {
1093        fn as_mut(&mut self) -> &mut [u8] {
1094            &mut self.0
1095        }
1096    }
1097
1098    impl fmt::Debug for G2Uncompressed {
1099        fn fmt(&self, formatter: &mut fmt::Formatter) -> Result<(), fmt::Error> {
1100            self.0[..].fmt(formatter)
1101        }
1102    }
1103
1104    impl EncodedPoint for G2Uncompressed {
1105        type Affine = G2Affine;
1106
1107        fn empty() -> Self {
1108            G2Uncompressed([0; 128])
1109        }
1110        fn size() -> usize {
1111            128
1112        }
1113        fn into_affine(&self) -> Result<G2Affine, GroupDecodingError> {
1114            let affine = self.into_affine_unchecked()?;
1115
1116            if !affine.is_on_curve() {
1117                Err(GroupDecodingError::NotOnCurve)
1118            } else {
1119                Ok(affine)
1120            }
1121        }
1122        fn into_affine_unchecked(&self) -> Result<G2Affine, GroupDecodingError> {
1123            // Create a copy of this representation.
1124            let mut copy = self.0;
1125
1126            if copy[0] & (1 << 7) != 0 {
1127                // Distinguisher bit is set, but this should be uncompressed!
1128                return Err(GroupDecodingError::UnexpectedCompressionMode);
1129            }
1130
1131            if copy[0] & (1 << 6) != 0 {
1132                // This is the point at infinity, which means that if we mask away
1133                // the first two bits, the entire representation should consist
1134                // of zeroes.
1135                copy[0] &= 0x3f;
1136
1137                if copy.iter().all(|b| *b == 0) {
1138                    Ok(G2Affine::zero())
1139                } else {
1140                    Err(GroupDecodingError::UnexpectedInformation)
1141                }
1142            } else {
1143                // Unset the two most significant bits.
1144                copy[0] &= 0x3f;
1145
1146                let mut x_c0 = FqRepr([0; 4]);
1147                let mut x_c1 = FqRepr([0; 4]);
1148                let mut y_c0 = FqRepr([0; 4]);
1149                let mut y_c1 = FqRepr([0; 4]);
1150
1151                {
1152                    let mut reader = &copy[..];
1153
1154                    x_c1.read_be(&mut reader).unwrap();
1155                    x_c0.read_be(&mut reader).unwrap();
1156                    y_c1.read_be(&mut reader).unwrap();
1157                    y_c0.read_be(&mut reader).unwrap();
1158                }
1159
1160                Ok(G2Affine {
1161                    x: Fq2 {
1162                        c0: Fq::from_repr(x_c0).map_err(|e| GroupDecodingError::CoordinateDecodingError("x coordinate (c0)", e))?,
1163                        c1: Fq::from_repr(x_c1).map_err(|e| GroupDecodingError::CoordinateDecodingError("x coordinate (c1)", e))?,
1164                    },
1165                    y: Fq2 {
1166                        c0: Fq::from_repr(y_c0).map_err(|e| GroupDecodingError::CoordinateDecodingError("y coordinate (c0)", e))?,
1167                        c1: Fq::from_repr(y_c1).map_err(|e| GroupDecodingError::CoordinateDecodingError("y coordinate (c1)", e))?,
1168                    },
1169                })
1170            }
1171        }
1172        fn from_affine(affine: G2Affine) -> Self {
1173            let mut res = Self::empty();
1174
1175            if affine.is_zero() {
1176                // Set the second-most significant bit to indicate this point
1177                // is at infinity.
1178                res.0[0] |= 1 << 6;
1179            } else {
1180                let mut writer = &mut res.0[..];
1181
1182                affine.x.c1.into_repr().write_be(&mut writer).unwrap();
1183                affine.x.c0.into_repr().write_be(&mut writer).unwrap();
1184                affine.y.c1.into_repr().write_be(&mut writer).unwrap();
1185                affine.y.c0.into_repr().write_be(&mut writer).unwrap();
1186            }
1187
1188            res
1189        }
1190    }
1191
1192    #[derive(Copy, Clone)]
1193    pub struct G2Compressed([u8; 64]);
1194
1195    impl AsRef<[u8]> for G2Compressed {
1196        fn as_ref(&self) -> &[u8] {
1197            &self.0
1198        }
1199    }
1200
1201    impl AsMut<[u8]> for G2Compressed {
1202        fn as_mut(&mut self) -> &mut [u8] {
1203            &mut self.0
1204        }
1205    }
1206
1207    impl fmt::Debug for G2Compressed {
1208        fn fmt(&self, formatter: &mut fmt::Formatter) -> Result<(), fmt::Error> {
1209            self.0[..].fmt(formatter)
1210        }
1211    }
1212
1213    impl EncodedPoint for G2Compressed {
1214        type Affine = G2Affine;
1215
1216        fn empty() -> Self {
1217            G2Compressed([0; 64])
1218        }
1219        fn size() -> usize {
1220            64
1221        }
1222        fn into_affine(&self) -> Result<G2Affine, GroupDecodingError> {
1223            let affine = self.into_affine_unchecked()?;
1224
1225            // NB: Decompression guarantees that it is on the curve already.
1226
1227            Ok(affine)
1228        }
1229        fn into_affine_unchecked(&self) -> Result<G2Affine, GroupDecodingError> {
1230            // Create a copy of this representation.
1231            let mut copy = self.0;
1232
1233            if copy[0] & (1 << 6) != 0 {
1234                // This is the point at infinity, which means that if we mask away
1235                // the first two bits, the entire representation should consist
1236                // of zeroes.
1237                copy[0] &= 0x3f;
1238
1239                if copy.iter().all(|b| *b == 0) {
1240                    Ok(G2Affine::zero())
1241                } else {
1242                    Err(GroupDecodingError::UnexpectedInformation)
1243                }
1244            } else {
1245                // Determine if the intended y coordinate must be greater
1246                // lexicographically.
1247                let greatest = copy[0] & (1 << 7) != 0;
1248
1249                // Unset the two most significant bits.
1250                copy[0] &= 0x3f;
1251
1252                let mut x_c1 = FqRepr([0; 4]);
1253                let mut x_c0 = FqRepr([0; 4]);
1254
1255                {
1256                    let mut reader = &copy[..];
1257
1258                    x_c1.read_be(&mut reader).unwrap();
1259                    x_c0.read_be(&mut reader).unwrap();
1260                }
1261
1262                // Interpret as Fq element.
1263                let x = Fq2 {
1264                    c0: Fq::from_repr(x_c0).map_err(|e| GroupDecodingError::CoordinateDecodingError("x coordinate (c0)", e))?,
1265                    c1: Fq::from_repr(x_c1).map_err(|e| GroupDecodingError::CoordinateDecodingError("x coordinate (c1)", e))?,
1266                };
1267
1268                G2Affine::get_point_from_x(x, greatest).ok_or(GroupDecodingError::NotOnCurve)
1269            }
1270        }
1271        fn from_affine(affine: G2Affine) -> Self {
1272            let mut res = Self::empty();
1273
1274            if affine.is_zero() {
1275                // Set the second-most significant bit to indicate this point
1276                // is at infinity.
1277                res.0[0] |= 1 << 6;
1278            } else {
1279                {
1280                    let mut writer = &mut res.0[..];
1281
1282                    affine.x.c1.into_repr().write_be(&mut writer).unwrap();
1283                    affine.x.c0.into_repr().write_be(&mut writer).unwrap();
1284                }
1285
1286                let mut negy = affine.y;
1287                negy.negate();
1288
1289                // Set the third most significant bit if the correct y-coordinate
1290                // is lexicographically largest.
1291                if affine.y > negy {
1292                    res.0[0] |= 1 << 7;
1293                }
1294            }
1295
1296            res
1297        }
1298    }
1299
1300    impl G2Affine {
1301        fn scale_by_cofactor(&self) -> G2 {
1302            // G2 cofactor = 2p - n = 2q - r
1303            // 0x30644e72e131a029b85045b68181585e06ceecda572a2489345f2299c0f9fa8d
1304            let cofactor = BitIterator::new([0x345f2299c0f9fa8d, 0x06ceecda572a2489, 0xb85045b68181585e, 0x30644e72e131a029]);
1305            self.mul_bits(cofactor)
1306        }
1307
1308        fn get_generator() -> Self {
1309            G2Affine {
1310                x: Fq2 {
1311                    c0: super::super::fq::G2_GENERATOR_X_C0,
1312                    c1: super::super::fq::G2_GENERATOR_X_C1,
1313                },
1314                y: Fq2 {
1315                    c0: super::super::fq::G2_GENERATOR_Y_C0,
1316                    c1: super::super::fq::G2_GENERATOR_Y_C1,
1317                },
1318            }
1319        }
1320
1321        fn get_coeff_b() -> Fq2 {
1322            super::super::fq::B_COEFF_FQ2
1323            // Fq2 {
1324            //     c0: super::super::fq::B_COEFF,
1325            //     c1: super::super::fq::B_COEFF,
1326            // }
1327        }
1328
1329        fn perform_pairing(&self, other: &G1Affine) -> Fq12 {
1330            super::super::Bn256::pairing(*other, *self)
1331        }
1332    }
1333
1334    impl G2 {
1335        fn empirical_recommended_wnaf_for_scalar(scalar: FrRepr) -> usize {
1336            let num_bits = scalar.num_bits() as usize;
1337
1338            if num_bits >= 103 {
1339                4
1340            } else if num_bits >= 37 {
1341                3
1342            } else {
1343                2
1344            }
1345        }
1346
1347        fn empirical_recommended_wnaf_for_num_scalars(num_scalars: usize) -> usize {
1348            const RECOMMENDATIONS: [usize; 11] = [1, 3, 8, 20, 47, 126, 260, 826, 1501, 4555, 84071];
1349
1350            let mut ret = 4;
1351            for r in &RECOMMENDATIONS {
1352                if num_scalars > *r {
1353                    ret += 1;
1354                } else {
1355                    break;
1356                }
1357            }
1358
1359            ret
1360        }
1361    }
1362
1363    #[derive(Clone, Debug)]
1364    pub struct G2Prepared {
1365        pub(crate) coeffs: Vec<(Fq2, Fq2, Fq2)>,
1366        pub(crate) infinity: bool,
1367    }
1368
1369    // This generator does not take a random element in Fp2
1370    // and tries to increment it to be on a curve, but
1371    // generates a random scalar and multiplies predefined generator by it
1372
1373    #[test]
1374    fn g2_generator() {
1375        use SqrtField;
1376
1377        let mut x = Fq2::zero();
1378        loop {
1379            // y^2 = x^3 + b
1380            let mut rhs = x;
1381            rhs.square();
1382            rhs.mul_assign(&x);
1383            rhs.add_assign(&G2Affine::get_coeff_b());
1384
1385            if let Some(y) = rhs.sqrt() {
1386                let mut negy = y;
1387                negy.negate();
1388
1389                let p = G2Affine {
1390                    x: x,
1391                    y: if y < negy { y } else { negy },
1392                };
1393
1394                let g2 = p.into_projective();
1395                if !g2.is_zero() {
1396                    let _g2 = G2Affine::from(g2);
1397                    break;
1398                }
1399            }
1400
1401            x.add_assign(&Fq2::one());
1402        }
1403    }
1404
1405    #[test]
1406    fn test_generate_g2_in_subgroup() {
1407        use SqrtField;
1408
1409        let mut x = Fq2::zero();
1410        loop {
1411            // y^2 = x^3 + b
1412            let mut rhs = x;
1413            rhs.square();
1414            rhs.mul_assign(&x);
1415            rhs.add_assign(&G2Affine::get_coeff_b());
1416
1417            if let Some(y) = rhs.sqrt() {
1418                let mut negy = y;
1419                negy.negate();
1420
1421                let p = G2Affine {
1422                    x: x,
1423                    y: if y < negy { y } else { negy },
1424                };
1425
1426                let g2 = p.into_projective();
1427                let mut minus_one = Fr::one();
1428                minus_one.negate();
1429
1430                let mut expected_zero = p.mul(minus_one);
1431                expected_zero.add_assign(&g2);
1432
1433                if !expected_zero.is_zero() {
1434                    let p = expected_zero.into_affine();
1435                    let scaled_by_cofactor = p.scale_by_cofactor();
1436                    if scaled_by_cofactor.is_zero() {
1437                        let g2 = G2Affine::from(expected_zero);
1438                        println!("Invalid subgroup point = {}", g2);
1439                        return;
1440                    }
1441                }
1442            }
1443
1444            x.add_assign(&Fq2::one());
1445        }
1446    }
1447
1448    #[cfg(test)]
1449    use rand::{SeedableRng, XorShiftRng};
1450
1451    #[test]
1452    fn g2_generator_on_curve() {
1453        use SqrtField;
1454
1455        let gen = G2Affine::get_generator();
1456        let x = gen.x;
1457        // y^2 = x^3 + 3/xi
1458        let mut rhs = x;
1459        rhs.square();
1460        rhs.mul_assign(&x);
1461        rhs.add_assign(&G2Affine::get_coeff_b());
1462
1463        if let Some(y) = rhs.sqrt() {
1464            let mut negy = y;
1465            negy.negate();
1466
1467            let p = G2Affine {
1468                x: x,
1469                y: if y < negy { y } else { negy },
1470            };
1471
1472            assert_eq!(p.y, gen.y);
1473            assert_eq!(p, G2Affine::one());
1474            return;
1475        }
1476        panic!();
1477    }
1478
1479    #[test]
1480    #[ignore] // TODO(ignored-test): Timeout.
1481    fn g2_curve_tests() {
1482        crate::tests::curve::curve_tests::<G2>();
1483        crate::tests::curve::random_transformation_tests::<G2>();
1484    }
1485
1486    #[test]
1487
1488    fn test_b_coeff() {
1489        let b2 = G2Affine::get_coeff_b();
1490        print!("{}\n\n", b2);
1491    }
1492
1493    #[test]
1494
1495    fn test_base_point_addition_and_doubling() {
1496        let mut two = G2::one();
1497        two.add_assign(&G2::one());
1498
1499        let one = G2::one();
1500
1501        let mut three21 = two;
1502        three21.add_assign(&one);
1503
1504        let mut three12 = one;
1505        three12.add_assign(&two);
1506
1507        assert_eq!(three12, three21);
1508    }
1509
1510    #[test]
1511    fn test_addition_and_doubling() {
1512        let mut rng = XorShiftRng::from_seed([0x5dbe6259, 0x8d313d76, 0x3237db17, 0xe5bc0654]);
1513
1514        for _ in 0..1000 {
1515            let a = G2::rand(&mut rng);
1516            assert!(a.into_affine().is_on_curve());
1517            let b = G2::rand(&mut rng);
1518            let c = G2::rand(&mut rng);
1519            let a_affine = a.into_affine();
1520            let b_affine = b.into_affine();
1521            let c_affine = c.into_affine();
1522
1523            // a + a should equal the doubling
1524            {
1525                let mut aplusa = a;
1526                aplusa.add_assign(&a);
1527
1528                let mut aplusamixed = a;
1529                aplusamixed.add_assign_mixed(&a.into_affine());
1530
1531                let mut adouble = a;
1532                adouble.double();
1533
1534                assert_eq!(aplusa, adouble);
1535                assert_eq!(aplusamixed, adouble);
1536            }
1537
1538            let mut ab = a;
1539            ab.add_assign(&b);
1540
1541            let mut ba = b;
1542            ba.add_assign(&a);
1543
1544            assert_eq!(ab, ba, "Addition should not depend on order");
1545
1546            let mut tmp = vec![G2::zero(); 6];
1547
1548            // (a + b) + c
1549            tmp[0] = a;
1550            tmp[0].add_assign(&b);
1551            tmp[0].add_assign(&c);
1552
1553            // a + (b + c)
1554            tmp[1] = b;
1555            tmp[1].add_assign(&c);
1556            tmp[1].add_assign(&a);
1557
1558            // (a + c) + b
1559            tmp[2] = a;
1560            tmp[2].add_assign(&c);
1561            tmp[2].add_assign(&b);
1562
1563            // Mixed addition
1564
1565            // (a + b) + c
1566            tmp[3] = a_affine.into_projective();
1567            tmp[3].add_assign_mixed(&b_affine);
1568            tmp[3].add_assign_mixed(&c_affine);
1569
1570            // a + (b + c)
1571            tmp[4] = b_affine.into_projective();
1572            tmp[4].add_assign_mixed(&c_affine);
1573            tmp[4].add_assign_mixed(&a_affine);
1574
1575            // (a + c) + b
1576            tmp[5] = a_affine.into_projective();
1577            tmp[5].add_assign_mixed(&c_affine);
1578            tmp[5].add_assign_mixed(&b_affine);
1579
1580            // Comparisons
1581            for i in 0..6 {
1582                for j in 0..6 {
1583                    assert_eq!(tmp[i], tmp[j]);
1584                    assert_eq!(tmp[i].into_affine(), tmp[j].into_affine());
1585                }
1586
1587                assert!(tmp[i] != a);
1588                assert!(tmp[i] != b);
1589                assert!(tmp[i] != c);
1590
1591                assert!(a != tmp[i]);
1592                assert!(b != tmp[i]);
1593                assert!(c != tmp[i]);
1594            }
1595        }
1596    }
1597
1598    #[test]
1599    fn random_negation_tests() {
1600        let mut rng = XorShiftRng::from_seed([0x5dbe6259, 0x8d313d76, 0x3237db17, 0xe5bc0654]);
1601
1602        for _ in 0..1000 {
1603            // let r = G2::rand(&mut rng);
1604            // assert!(r.into_affine().is_on_curve());
1605
1606            let mut r = G2::one();
1607            let k = Fr::rand(&mut rng);
1608            r.mul_assign(k);
1609
1610            let s = Fr::rand(&mut rng);
1611            let mut sneg = s;
1612            sneg.negate();
1613
1614            let mut t1 = r;
1615            t1.mul_assign(s);
1616
1617            let mut t2 = r;
1618            t2.mul_assign(sneg);
1619
1620            let mut t3 = t1;
1621            t3.add_assign(&t2);
1622            assert!(t3.is_zero());
1623
1624            let mut t4 = t1;
1625            t4.add_assign_mixed(&t2.into_affine());
1626            assert!(t4.is_zero());
1627
1628            t1.negate();
1629            assert_eq!(t1, t2);
1630        }
1631    }
1632
1633    #[test]
1634    fn mul_by_order_tests() {
1635        let mut rng = XorShiftRng::from_seed([0x5dbe6259, 0x8d313d76, 0x3237db17, 0xe5bc0654]);
1636
1637        for _ in 0..1000 {
1638            // let r = G2::rand(&mut rng);
1639
1640            let mut r = G2::one();
1641            let k = Fr::rand(&mut rng);
1642            r.mul_assign(k);
1643
1644            let order = Fr::char();
1645
1646            let mut q = G2::one();
1647            q.mul_assign(order);
1648            assert!(q.is_zero());
1649
1650            r.mul_assign(order);
1651            assert!(r.is_zero());
1652
1653            let mut t = G2::rand(&mut rng);
1654            t.mul_assign(order);
1655            assert!(t.is_zero());
1656        }
1657    }
1658}
1659
1660pub use self::g1::*;
1661pub use self::g2::*;
zksync_pairing/compact_bn256/ec.rs

zksync_pairing/compact_bn256/
ec.rs
