ark_ec/models/short_weierstrass/
group.rs

1use super::{Affine, SWCurveConfig};
2use crate::{
3    scalar_mul::{variable_base::VariableBaseMSM, ScalarMul},
4    AffineRepr, CurveGroup, PrimeGroup,
5};
6use ark_ff::{fields::Field, AdditiveGroup, PrimeField, ToConstraintField, UniformRand};
7use ark_serialize::{
8    CanonicalDeserialize, CanonicalSerialize, Compress, SerializationError, Valid, Validate,
9};
10use ark_std::{
11    borrow::Borrow,
12    fmt::{Debug, Display, Formatter, Result as FmtResult},
13    hash::{Hash, Hasher},
14    io::{Read, Write},
15    ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
16    rand::{
17        distributions::{Distribution, Standard},
18        Rng,
19    },
20    vec::*,
21    One, Zero,
22};
23use educe::Educe;
24#[cfg(feature = "parallel")]
25use rayon::prelude::*;
26use zeroize::Zeroize;
27
28/// Jacobian coordinates for a point on an elliptic curve in short Weierstrass
29/// form, over the base field `P::BaseField`. This struct implements arithmetic
30/// via the Jacobian formulae
31#[derive(Educe)]
32#[educe(Copy, Clone)]
33#[must_use]
34pub struct Projective<P: SWCurveConfig> {
35    /// `X / Z` projection of the affine `X`
36    pub x: P::BaseField,
37    /// `Y / Z` projection of the affine `Y`
38    pub y: P::BaseField,
39    /// Projective multiplicative inverse. Will be `0` only at infinity.
40    pub z: P::BaseField,
41}
42
43impl<P: SWCurveConfig> Display for Projective<P> {
44    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
45        write!(f, "{}", Affine::from(*self))
46    }
47}
48
49impl<P: SWCurveConfig> Debug for Projective<P> {
50    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
51        match self.is_zero() {
52            true => write!(f, "infinity"),
53            false => write!(f, "({}, {}, {})", self.x, self.y, self.z),
54        }
55    }
56}
57
58impl<P: SWCurveConfig> Eq for Projective<P> {}
59impl<P: SWCurveConfig> PartialEq for Projective<P> {
60    fn eq(&self, other: &Self) -> bool {
61        if self.is_zero() {
62            return other.is_zero();
63        }
64
65        if other.is_zero() {
66            return false;
67        }
68
69        // The points (X, Y, Z) and (X', Y', Z')
70        // are equal when (X * Z^2) = (X' * Z'^2)
71        // and (Y * Z^3) = (Y' * Z'^3).
72        let z1z1 = self.z.square();
73        let z2z2 = other.z.square();
74
75        if self.x * &z2z2 != other.x * &z1z1 {
76            false
77        } else {
78            self.y * &(z2z2 * &other.z) == other.y * &(z1z1 * &self.z)
79        }
80    }
81}
82
83impl<P: SWCurveConfig> PartialEq<Affine<P>> for Projective<P> {
84    fn eq(&self, other: &Affine<P>) -> bool {
85        *self == other.into_group()
86    }
87}
88
89impl<P: SWCurveConfig> Hash for Projective<P> {
90    fn hash<H: Hasher>(&self, state: &mut H) {
91        self.into_affine().hash(state)
92    }
93}
94
95impl<P: SWCurveConfig> Distribution<Projective<P>> for Standard {
96    /// Generates a uniformly random instance of the curve.
97    #[inline]
98    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Projective<P> {
99        loop {
100            let x = P::BaseField::rand(rng);
101            let greatest = rng.gen();
102
103            if let Some(p) = Affine::get_point_from_x_unchecked(x, greatest) {
104                return p.mul_by_cofactor_to_group();
105            }
106        }
107    }
108}
109
110impl<P: SWCurveConfig> Default for Projective<P> {
111    #[inline]
112    fn default() -> Self {
113        Self::zero()
114    }
115}
116
117impl<P: SWCurveConfig> Projective<P> {
118    /// Constructs a new group element without checking whether the coordinates
119    /// specify a point in the subgroup.
120    pub const fn new_unchecked(x: P::BaseField, y: P::BaseField, z: P::BaseField) -> Self {
121        Self { x, y, z }
122    }
123
124    /// Constructs a new group element in a way while enforcing that points are in
125    /// the prime-order subgroup.
126    pub fn new(x: P::BaseField, y: P::BaseField, z: P::BaseField) -> Self {
127        let p = Self::new_unchecked(x, y, z).into_affine();
128        assert!(p.is_on_curve());
129        assert!(p.is_in_correct_subgroup_assuming_on_curve());
130        p.into()
131    }
132}
133
134impl<P: SWCurveConfig> Zeroize for Projective<P> {
135    fn zeroize(&mut self) {
136        self.x.zeroize();
137        self.y.zeroize();
138        self.z.zeroize();
139    }
140}
141
142impl<P: SWCurveConfig> Zero for Projective<P> {
143    /// Returns the point at infinity, which always has Z = 0.
144    #[inline]
145    fn zero() -> Self {
146        Self::new_unchecked(
147            P::BaseField::one(),
148            P::BaseField::one(),
149            P::BaseField::zero(),
150        )
151    }
152
153    /// Checks whether `self.z.is_zero()`.
154    #[inline]
155    fn is_zero(&self) -> bool {
156        self.z == P::BaseField::ZERO
157    }
158}
159
160impl<P: SWCurveConfig> AdditiveGroup for Projective<P> {
161    type Scalar = P::ScalarField;
162
163    const ZERO: Self =
164        Self::new_unchecked(P::BaseField::ONE, P::BaseField::ONE, P::BaseField::ZERO);
165
166    /// Sets `self = 2 * self`. Note that Jacobian formulae are incomplete, and
167    /// so doubling cannot be computed as `self + self`. Instead, this
168    /// implementation uses the following specialized doubling formulae:
169    /// * [`P::A` is zero](http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l)
170    /// * [`P::A` is not zero](https://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-2007-bl)
171    fn double_in_place(&mut self) -> &mut Self {
172        if self.is_zero() {
173            return self;
174        }
175
176        if P::COEFF_A == P::BaseField::ZERO {
177            // A = X1^2
178            let mut a = self.x;
179            a.square_in_place();
180
181            // B = Y1^2
182            let mut b = self.y;
183            b.square_in_place();
184
185            // C = B^2
186            let mut c = b;
187            c.square_in_place();
188
189            // D = 2*((X1+B)^2-A-C)
190            //   = 2 * (X1 + Y1^2)^2 - A - C
191            //   = 2 * 2 * X1 * Y1^2
192            let d = if [1, 2].contains(&P::BaseField::extension_degree()) {
193                let mut d = self.x;
194                d *= &b;
195                d.double_in_place().double_in_place();
196                d
197            } else {
198                let mut d = self.x;
199                d += &b;
200                d.square_in_place();
201                d -= a;
202                d -= c;
203                d.double_in_place();
204                d
205            };
206
207            // E = 3*A
208            let e = a + &*a.double_in_place();
209
210            // Z3 = 2*Y1*Z1
211            self.z *= &self.y;
212            self.z.double_in_place();
213
214            // F = E^2
215            // X3 = F-2*D
216            self.x = e;
217            self.x.square_in_place();
218            self.x -= &d.double();
219
220            // Y3 = E*(D-X3)-8*C
221            self.y = d;
222            self.y -= &self.x;
223            self.y *= &e;
224            self.y -= c.double_in_place().double_in_place().double_in_place();
225            self
226        } else {
227            // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l
228            // XX = X1^2
229            let xx = self.x.square();
230
231            // YY = Y1^2
232            let yy = self.y.square();
233
234            // YYYY = YY^2
235            let mut yyyy = yy;
236            yyyy.square_in_place();
237
238            // ZZ = Z1^2
239            let mut zz = self.z;
240            zz.square_in_place();
241
242            // S = 2*((X1+YY)^2-XX-YYYY)
243            let s = ((self.x + &yy).square() - &xx - &yyyy).double();
244
245            // M = 3*XX+a*ZZ^2
246            let mut m = xx;
247            m.double_in_place();
248            m += &xx;
249            m += &P::mul_by_a(zz.square());
250
251            // T = M^2-2*S
252            // X3 = T
253            self.x = m;
254            self.x.square_in_place();
255            self.x -= s.double();
256
257            // Z3 = (Y1+Z1)^2-YY-ZZ
258            // Can be calculated as Z3 = 2*Y1*Z1, and this is faster.
259            self.z *= self.y;
260            self.z.double_in_place();
261
262            // Y3 = M*(S-X3)-8*YYYY
263            self.y = s;
264            self.y -= &self.x;
265            self.y *= &m;
266            self.y -= yyyy.double_in_place().double_in_place().double_in_place();
267
268            self
269        }
270    }
271}
272
273impl<P: SWCurveConfig> PrimeGroup for Projective<P> {
274    type ScalarField = P::ScalarField;
275
276    #[inline]
277    fn generator() -> Self {
278        Affine::generator().into()
279    }
280
281    #[inline]
282    fn mul_bigint(&self, other: impl AsRef<[u64]>) -> Self {
283        P::mul_projective(self, other.as_ref())
284    }
285}
286
287impl<P: SWCurveConfig> CurveGroup for Projective<P> {
288    type Config = P;
289    type BaseField = P::BaseField;
290    type Affine = Affine<P>;
291    type FullGroup = Affine<P>;
292
293    /// Normalizes a slice of projective elements so that
294    /// conversion to affine is cheap.
295    ///
296    /// In more detail, this method converts a curve point in Jacobian
297    /// coordinates (x, y, z) into an equivalent representation (x/z^2,
298    /// y/z^3, 1).
299    ///
300    /// For `N = v.len()`, this costs 1 inversion + 6N field multiplications + N
301    /// field squarings.
302    ///
303    /// (Where batch inversion comprises 3N field multiplications + 1 inversion
304    /// of these operations)
305    #[inline]
306    fn normalize_batch(v: &[Self]) -> Vec<Self::Affine> {
307        let mut z_s = v.iter().map(|g| g.z).collect::<Vec<_>>();
308        ark_ff::batch_inversion(&mut z_s);
309
310        // Perform affine transformations
311        ark_std::cfg_iter!(v)
312            .zip(z_s)
313            .map(|(g, z)| match g.is_zero() {
314                true => Affine::identity(),
315                false => {
316                    let z2 = z.square();
317                    let x = g.x * z2;
318                    let y = g.y * z2 * z;
319                    Affine::new_unchecked(x, y)
320                },
321            })
322            .collect()
323    }
324}
325
326impl<P: SWCurveConfig> Neg for Projective<P> {
327    type Output = Self;
328
329    #[inline]
330    fn neg(mut self) -> Self {
331        self.y = -self.y;
332        self
333    }
334}
335
336impl<P: SWCurveConfig, T: Borrow<Affine<P>>> AddAssign<T> for Projective<P> {
337    /// Using <http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-madd-2007-bl>
338    fn add_assign(&mut self, other: T) {
339        let other = other.borrow();
340        if let Some((other_x, other_y)) = other.xy() {
341            if self.is_zero() {
342                self.x = other_x;
343                self.y = other_y;
344                self.z = P::BaseField::one();
345                return;
346            }
347
348            // Z1Z1 = Z1^2
349            let mut z1z1 = self.z;
350            z1z1.square_in_place();
351
352            // U2 = X2*Z1Z1
353            let mut u2 = other_x;
354            u2 *= &z1z1;
355
356            // S2 = Y2*Z1*Z1Z1
357            let mut s2 = self.z;
358            s2 *= &other_y;
359            s2 *= &z1z1;
360
361            if self.x == u2 {
362                if self.y == s2 {
363                    // The two points are equal, so we double.
364                    self.double_in_place();
365                } else {
366                    // a + (-a) = 0
367                    *self = Self::zero()
368                }
369            } else {
370                // H = U2-X1
371                let mut h = u2;
372                h -= &self.x;
373
374                // HH = H^2
375                let mut hh = h;
376                hh.square_in_place();
377
378                // I = 4*HH
379                let mut i = hh;
380                i.double_in_place().double_in_place();
381
382                // J = -H*I
383                let mut j = h;
384                j.neg_in_place();
385                j *= &i;
386
387                // r = 2*(S2-Y1)
388                let mut r = s2;
389                r -= &self.y;
390                r.double_in_place();
391
392                // V = X1*I
393                let mut v = self.x;
394                v *= &i;
395
396                // X3 = r^2 + J - 2*V
397                self.x = r.square();
398                self.x += &j;
399                self.x -= &v.double();
400
401                // Y3 = r*(V-X3) + 2*Y1*J
402                v -= &self.x;
403                self.y.double_in_place();
404                self.y = P::BaseField::sum_of_products(&[r, self.y], &[v, j]);
405
406                // Z3 = 2 * Z1 * H;
407                // Can alternatively be computed as (Z1+H)^2-Z1Z1-HH, but the latter is slower.
408                self.z *= &h;
409                self.z.double_in_place();
410            }
411        }
412    }
413}
414
415impl<P: SWCurveConfig, T: Borrow<Affine<P>>> Add<T> for Projective<P> {
416    type Output = Self;
417    fn add(mut self, other: T) -> Self {
418        let other = other.borrow();
419        self += other;
420        self
421    }
422}
423
424impl<P: SWCurveConfig, T: Borrow<Affine<P>>> SubAssign<T> for Projective<P> {
425    fn sub_assign(&mut self, other: T) {
426        *self += -(*other.borrow());
427    }
428}
429
430impl<P: SWCurveConfig, T: Borrow<Affine<P>>> Sub<T> for Projective<P> {
431    type Output = Self;
432    fn sub(mut self, other: T) -> Self {
433        self -= other.borrow();
434        self
435    }
436}
437
438ark_ff::impl_additive_ops_from_ref!(Projective, SWCurveConfig);
439
440impl<'a, P: SWCurveConfig> Add<&'a Self> for Projective<P> {
441    type Output = Self;
442
443    #[inline]
444    fn add(mut self, other: &'a Self) -> Self {
445        self += other;
446        self
447    }
448}
449
450impl<'a, P: SWCurveConfig> AddAssign<&'a Self> for Projective<P> {
451    fn add_assign(&mut self, other: &'a Self) {
452        if self.is_zero() {
453            *self = *other;
454            return;
455        }
456
457        if other.is_zero() {
458            return;
459        }
460
461        // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-add-2007-bl
462        // Works for all curves.
463
464        // Z1Z1 = Z1^2
465        let z1z1 = self.z.square();
466
467        // Z2Z2 = Z2^2
468        let z2z2 = other.z.square();
469
470        // U1 = X1*Z2Z2
471        let mut u1 = self.x;
472        u1 *= &z2z2;
473
474        // U2 = X2*Z1Z1
475        let mut u2 = other.x;
476        u2 *= &z1z1;
477
478        // S1 = Y1*Z2*Z2Z2
479        let mut s1 = self.y;
480        s1 *= &other.z;
481        s1 *= &z2z2;
482
483        // S2 = Y2*Z1*Z1Z1
484        let mut s2 = other.y;
485        s2 *= &self.z;
486        s2 *= &z1z1;
487
488        if u1 == u2 {
489            if s1 == s2 {
490                // The two points are equal, so we double.
491                self.double_in_place();
492            } else {
493                // a + (-a) = 0
494                *self = Self::zero();
495            }
496        } else {
497            // H = U2-U1
498            let mut h = u2;
499            h -= &u1;
500
501            // I = (2*H)^2
502            let mut i = h;
503            i.double_in_place().square_in_place();
504
505            // J = -H*I
506            let mut j = h;
507            j.neg_in_place();
508            j *= &i;
509
510            // r = 2*(S2-S1)
511            let mut r = s2;
512            r -= &s1;
513            r.double_in_place();
514
515            // V = U1*I
516            let mut v = u1;
517            v *= &i;
518
519            // X3 = r^2 + J - 2*V
520            self.x = r;
521            self.x.square_in_place();
522            self.x += &j;
523            self.x -= &(v.double());
524
525            // Y3 = r*(V - X3) + 2*S1*J
526            v -= &self.x;
527            self.y = s1;
528            self.y.double_in_place();
529            self.y = P::BaseField::sum_of_products(&[r, self.y], &[v, j]);
530
531            // Z3 = ((Z1+Z2)^2 - Z1Z1 - Z2Z2)*H
532            // This is equal to Z3 = 2 * Z1 * Z2 * H, and computing it this way is faster.
533            self.z *= other.z;
534            self.z.double_in_place();
535            self.z *= &h;
536        }
537    }
538}
539
540impl<'a, P: SWCurveConfig> Sub<&'a Self> for Projective<P> {
541    type Output = Self;
542
543    #[inline]
544    fn sub(mut self, other: &'a Self) -> Self {
545        self -= other;
546        self
547    }
548}
549
550impl<'a, P: SWCurveConfig> SubAssign<&'a Self> for Projective<P> {
551    fn sub_assign(&mut self, other: &'a Self) {
552        *self += &(-(*other));
553    }
554}
555
556impl<P: SWCurveConfig, T: Borrow<P::ScalarField>> MulAssign<T> for Projective<P> {
557    fn mul_assign(&mut self, other: T) {
558        *self = self.mul_bigint(other.borrow().into_bigint())
559    }
560}
561
562impl<P: SWCurveConfig, T: Borrow<P::ScalarField>> Mul<T> for Projective<P> {
563    type Output = Self;
564
565    #[inline]
566    fn mul(mut self, other: T) -> Self {
567        self *= other;
568        self
569    }
570}
571
572// The affine point X, Y is represented in the Jacobian
573// coordinates with Z = 1.
574impl<P: SWCurveConfig> From<Affine<P>> for Projective<P> {
575    #[inline]
576    fn from(p: Affine<P>) -> Projective<P> {
577        p.xy().map_or(Projective::zero(), |(x, y)| Self {
578            x,
579            y,
580            z: P::BaseField::one(),
581        })
582    }
583}
584
585impl<P: SWCurveConfig> CanonicalSerialize for Projective<P> {
586    #[inline]
587    fn serialize_with_mode<W: Write>(
588        &self,
589        writer: W,
590        compress: Compress,
591    ) -> Result<(), SerializationError> {
592        let aff = Affine::<P>::from(*self);
593        P::serialize_with_mode(&aff, writer, compress)
594    }
595
596    #[inline]
597    fn serialized_size(&self, compress: Compress) -> usize {
598        P::serialized_size(compress)
599    }
600}
601
602impl<P: SWCurveConfig> Valid for Projective<P> {
603    fn check(&self) -> Result<(), SerializationError> {
604        self.into_affine().check()
605    }
606
607    fn batch_check<'a>(
608        batch: impl Iterator<Item = &'a Self> + Send,
609    ) -> Result<(), SerializationError>
610    where
611        Self: 'a,
612    {
613        let batch = batch.copied().collect::<Vec<_>>();
614        let batch = Self::normalize_batch(&batch);
615        Affine::batch_check(batch.iter())
616    }
617}
618
619impl<P: SWCurveConfig> CanonicalDeserialize for Projective<P> {
620    fn deserialize_with_mode<R: Read>(
621        reader: R,
622        compress: Compress,
623        validate: Validate,
624    ) -> Result<Self, SerializationError> {
625        let aff = P::deserialize_with_mode(reader, compress, validate)?;
626        Ok(aff.into())
627    }
628}
629
630impl<M: SWCurveConfig, ConstraintF: Field> ToConstraintField<ConstraintF> for Projective<M>
631where
632    M::BaseField: ToConstraintField<ConstraintF>,
633{
634    #[inline]
635    fn to_field_elements(&self) -> Option<Vec<ConstraintF>> {
636        Affine::from(*self).to_field_elements()
637    }
638}
639
640impl<P: SWCurveConfig> ScalarMul for Projective<P> {
641    type MulBase = Affine<P>;
642    const NEGATION_IS_CHEAP: bool = true;
643
644    fn batch_convert_to_mul_base(bases: &[Self]) -> Vec<Self::MulBase> {
645        Self::normalize_batch(bases)
646    }
647}
648
649impl<P: SWCurveConfig> VariableBaseMSM for Projective<P> {
650    fn msm(bases: &[Self::MulBase], bigints: &[Self::ScalarField]) -> Result<Self, usize> {
651        P::msm(bases, bigints)
652    }
653}
654
655impl<P: SWCurveConfig, T: Borrow<Affine<P>>> core::iter::Sum<T> for Projective<P> {
656    fn sum<I: Iterator<Item = T>>(iter: I) -> Self {
657        iter.fold(Projective::zero(), |sum, x| sum + x.borrow())
658    }
659}
ark_ec/models/short_weierstrass/group.rs

ark_ec/models/short_weierstrass/
group.rs
