openzeppelin_crypto/curve/sw/
projective.rs

1//! Projective coordinates for a point on a Short Weierstrass curve
2//! ([Homogeneous coordinates]).
3//!
4//! [Homogeneous coordinates]: https://en.wikipedia.org/wiki/Homogeneous_coordinates
5
6use alloc::vec::Vec;
7use core::{
8    borrow::Borrow,
9    fmt::{Debug, Display, Formatter},
10    hash::{Hash, Hasher},
11    ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
12};
13
14use educe::Educe;
15use num_traits::{One, Zero};
16use zeroize::Zeroize;
17
18use super::{Affine, SWCurveConfig};
19use crate::{
20    bits::BitIteratorBE,
21    curve::{batch_inversion, AffineRepr, CurveGroup, PrimeGroup},
22    field::{group::AdditiveGroup, prime::PrimeField, Field},
23    impl_additive_ops_from_ref,
24};
25
26/// Jacobian coordinates for a point on an elliptic curve in short Weierstrass
27/// form, over the base field `P::BaseField`. This struct implements arithmetic
28/// via the Jacobian formulae.
29#[derive(Educe)]
30#[educe(Copy, Clone)]
31#[must_use]
32pub struct Projective<P: SWCurveConfig> {
33    /// `X / Z` projection of the affine `X`
34    pub x: P::BaseField,
35    /// `Y / Z` projection of the affine `Y`
36    pub y: P::BaseField,
37    /// Projective multiplicative inverse. Will be `0` only at infinity.
38    pub z: P::BaseField,
39}
40
41impl<P: SWCurveConfig> Display for Projective<P> {
42    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
43        write!(f, "{}", Affine::from(*self))
44    }
45}
46
47impl<P: SWCurveConfig> Debug for Projective<P> {
48    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
49        if self.is_zero() {
50            write!(f, "infinity")
51        } else {
52            write!(f, "({}, {}, {})", self.x, self.y, self.z)
53        }
54    }
55}
56
57impl<P: SWCurveConfig> Eq for Projective<P> {}
58impl<P: SWCurveConfig> PartialEq for Projective<P> {
59    fn eq(&self, other: &Self) -> bool {
60        if self.is_zero() {
61            return other.is_zero();
62        }
63
64        if other.is_zero() {
65            return false;
66        }
67
68        // The points (X, Y, Z) and (X', Y', Z')
69        // are equal when (X * Z'^2) = (X' * Z^2)
70        // and (Y * Z'^3) = (Y' * Z^3).
71        let z1z1 = self.z.square();
72        let z2z2 = other.z.square();
73
74        if self.x * z2z2 == other.x * z1z1 {
75            self.y * (z2z2 * other.z) == other.y * (z1z1 * self.z)
76        } else {
77            false
78        }
79    }
80}
81
82impl<P: SWCurveConfig> PartialEq<Affine<P>> for Projective<P> {
83    fn eq(&self, other: &Affine<P>) -> bool {
84        self == &other.into_group()
85    }
86}
87
88impl<P: SWCurveConfig> Hash for Projective<P> {
89    fn hash<H: Hasher>(&self, state: &mut H) {
90        self.into_affine().hash(state);
91    }
92}
93
94impl<P: SWCurveConfig> Default for Projective<P> {
95    #[inline]
96    fn default() -> Self {
97        Self::zero()
98    }
99}
100
101impl<P: SWCurveConfig> Projective<P> {
102    /// Constructs a new group element without checking whether the coordinates
103    /// specify a point in the subgroup.
104    pub const fn new_unchecked(
105        x: P::BaseField,
106        y: P::BaseField,
107        z: P::BaseField,
108    ) -> Self {
109        Self { x, y, z }
110    }
111
112    /// Constructs a new group element in a way while enforcing that points are
113    /// in the prime-order subgroup.
114    ///
115    /// # Panics
116    ///
117    /// * If point is not on curve.
118    /// * If point is not in the prime-order subgroup.
119    pub fn new(x: P::BaseField, y: P::BaseField, z: P::BaseField) -> Self {
120        let p = Self::new_unchecked(x, y, z).into_affine();
121        assert!(p.is_on_curve());
122        assert!(p.is_in_prime_order_subgroup());
123        p.into()
124    }
125}
126
127impl<P: SWCurveConfig> Zeroize for Projective<P> {
128    fn zeroize(&mut self) {
129        self.x.zeroize();
130        self.y.zeroize();
131        self.z.zeroize();
132    }
133}
134
135impl<P: SWCurveConfig> Zero for Projective<P> {
136    /// Returns the point at infinity, which always has Z = 0.
137    #[inline]
138    fn zero() -> Self {
139        Self::new_unchecked(
140            P::BaseField::one(),
141            P::BaseField::one(),
142            P::BaseField::zero(),
143        )
144    }
145
146    /// Checks whether `self.z.is_zero()`.
147    #[inline]
148    fn is_zero(&self) -> bool {
149        self.z == P::BaseField::ZERO
150    }
151}
152
153impl<P: SWCurveConfig> AdditiveGroup for Projective<P> {
154    type Scalar = P::ScalarField;
155
156    const ZERO: Self = Self::new_unchecked(
157        P::BaseField::ONE,
158        P::BaseField::ONE,
159        P::BaseField::ZERO,
160    );
161
162    /// Sets `self = 2 * self`. Note that Jacobian formulae are incomplete, and
163    /// so doubling cannot be computed as `self + self`. Instead, this
164    /// implementation uses the following specialized doubling formulae:
165    ///
166    /// * [`P::A` is zero](http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l)
167    /// * [`P::A` is not zero](https://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-2007-bl)
168    fn double_in_place(&mut self) -> &mut Self {
169        if self.is_zero() {
170            return self;
171        }
172
173        if P::COEFF_A == P::BaseField::ZERO {
174            // A = X1^2
175            let mut a = self.x;
176            a.square_in_place();
177
178            // B = Y1^2
179            let mut b = self.y;
180            b.square_in_place();
181
182            // C = B^2
183            let mut c = b;
184            c.square_in_place();
185
186            // D = 2*((X1+B)^2-A-C)
187            //   = 2 * (X1 + Y1^2)^2 - A - C
188            //   = 2 * 2 * X1 * Y1^2
189            let d = if [1, 2].contains(&P::BaseField::extension_degree()) {
190                let mut d = self.x;
191                d *= &b;
192                d.double_in_place().double_in_place();
193                d
194            } else {
195                let mut d = self.x;
196                d += &b;
197                d.square_in_place();
198                d -= a;
199                d -= c;
200                d.double_in_place();
201                d
202            };
203
204            // E = 3*A
205            let e = a + a.double_in_place();
206
207            // Z3 = 2*Y1*Z1
208            self.z *= &self.y;
209            self.z.double_in_place();
210
211            // F = E^2
212            // X3 = F-2*D
213            self.x = e;
214            self.x.square_in_place();
215            self.x -= &d.double();
216
217            // Y3 = E*(D-X3)-8*C
218            self.y = d;
219            self.y -= &self.x;
220            self.y *= &e;
221            self.y -= c.double_in_place().double_in_place().double_in_place();
222            self
223        } else {
224            // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l
225            // XX = X1^2
226            let xx = self.x.square();
227
228            // YY = Y1^2
229            let yy = self.y.square();
230
231            // YYYY = YY^2
232            let mut yyyy = yy;
233            yyyy.square_in_place();
234
235            // ZZ = Z1^2
236            let mut zz = self.z;
237            zz.square_in_place();
238
239            // S = 2*((X1+YY)^2-XX-YYYY)
240            let s = ((self.x + yy).square() - xx - yyyy).double();
241
242            // M = 3*XX+a*ZZ^2
243            let mut m = xx;
244            m.double_in_place();
245            m += &xx;
246            m += &P::mul_by_a(zz.square());
247
248            // T = M^2-2*S
249            // X3 = T
250            self.x = m;
251            self.x.square_in_place();
252            self.x -= s.double();
253
254            // Z3 = (Y1+Z1)^2-YY-ZZ
255            // Can be calculated as Z3 = 2*Y1*Z1, and this is faster.
256            self.z *= self.y;
257            self.z.double_in_place();
258
259            // Y3 = M*(S-X3)-8*YYYY
260            self.y = s;
261            self.y -= &self.x;
262            self.y *= &m;
263            self.y -=
264                yyyy.double_in_place().double_in_place().double_in_place();
265
266            self
267        }
268    }
269}
270
271impl<P: SWCurveConfig> PrimeGroup for Projective<P> {
272    type ScalarField = P::ScalarField;
273
274    #[inline]
275    fn generator() -> Self {
276        Affine::generator().into()
277    }
278
279    #[inline]
280    fn mul_bigint(&self, other: impl BitIteratorBE) -> Self {
281        P::mul_projective(self, other)
282    }
283}
284
285impl<P: SWCurveConfig> CurveGroup for Projective<P> {
286    type Affine = Affine<P>;
287    type BaseField = P::BaseField;
288    type Config = P;
289    type FullGroup = Affine<P>;
290
291    /// Normalizes a slice of projective elements so that
292    /// conversion to affine is inexpensive.
293    ///
294    /// In more detail, this method converts a curve point in Jacobian
295    /// coordinates (x, y, z) into an equivalent representation (x/z^2,
296    /// y/z^3, 1).
297    ///
298    /// For `N = v.len()`, this costs 1 inversion + 6N field multiplications + N
299    /// field squarings.
300    ///
301    /// (Where batch inversion comprises 3N field multiplications + 1 inversion
302    /// of these operations)
303    #[inline]
304    fn normalize_batch(v: &[Self]) -> Vec<Self::Affine> {
305        let mut z_s = v.iter().map(|g| g.z).collect::<Vec<_>>();
306
307        batch_inversion(&mut z_s);
308
309        // Perform affine transformations.
310        v.iter()
311            .zip(z_s)
312            .map(|(g, z)| {
313                if g.is_zero() {
314                    Affine::identity()
315                } else {
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
408                // latter is slower.
409                self.z *= &h;
410                self.z.double_in_place();
411            }
412        }
413    }
414}
415
416impl<P: SWCurveConfig, T: Borrow<Affine<P>>> Add<T> for Projective<P> {
417    type Output = Self;
418
419    fn add(mut self, other: T) -> Self {
420        let other = other.borrow();
421        self += other;
422        self
423    }
424}
425
426impl<P: SWCurveConfig, T: Borrow<Affine<P>>> SubAssign<T> for Projective<P> {
427    fn sub_assign(&mut self, other: T) {
428        *self += -(*other.borrow());
429    }
430}
431
432impl<P: SWCurveConfig, T: Borrow<Affine<P>>> Sub<T> for Projective<P> {
433    type Output = Self;
434
435    fn sub(mut self, other: T) -> Self {
436        self -= other.borrow();
437        self
438    }
439}
440
441impl_additive_ops_from_ref!(Projective, SWCurveConfig);
442
443impl<'a, P: SWCurveConfig> Add<&'a Self> for Projective<P> {
444    type Output = Self;
445
446    #[inline]
447    fn add(mut self, other: &'a Self) -> Self {
448        self += other;
449        self
450    }
451}
452
453impl<'a, P: SWCurveConfig> AddAssign<&'a Self> for Projective<P> {
454    fn add_assign(&mut self, other: &'a Self) {
455        if self.is_zero() {
456            *self = *other;
457            return;
458        }
459
460        if other.is_zero() {
461            return;
462        }
463
464        // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-add-2007-bl
465        // Works for all curves.
466
467        // Z1Z1 = Z1^2
468        let z1z1 = self.z.square();
469
470        // Z2Z2 = Z2^2
471        let z2z2 = other.z.square();
472
473        // U1 = X1*Z2Z2
474        let mut u1 = self.x;
475        u1 *= &z2z2;
476
477        // U2 = X2*Z1Z1
478        let mut u2 = other.x;
479        u2 *= &z1z1;
480
481        // S1 = Y1*Z2*Z2Z2
482        let mut s1 = self.y;
483        s1 *= &other.z;
484        s1 *= &z2z2;
485
486        // S2 = Y2*Z1*Z1Z1
487        let mut s2 = other.y;
488        s2 *= &self.z;
489        s2 *= &z1z1;
490
491        if u1 == u2 {
492            if s1 == s2 {
493                // The two points are equal, so we double.
494                self.double_in_place();
495            } else {
496                // a + (-a) = 0
497                *self = Self::zero();
498            }
499        } else {
500            // H = U2-U1
501            let mut h = u2;
502            h -= &u1;
503
504            // I = (2*H)^2
505            let mut i = h;
506            i.double_in_place().square_in_place();
507
508            // J = -H*I
509            let mut j = h;
510            j.neg_in_place();
511            j *= &i;
512
513            // r = 2*(S2-S1)
514            let mut r = s2;
515            r -= &s1;
516            r.double_in_place();
517
518            // V = U1*I
519            let mut v = u1;
520            v *= &i;
521
522            // X3 = r^2 + J - 2*V
523            self.x = r;
524            self.x.square_in_place();
525            self.x += &j;
526            self.x -= &(v.double());
527
528            // Y3 = r*(V - X3) + 2*S1*J
529            v -= &self.x;
530            self.y = s1;
531            self.y.double_in_place();
532            self.y = P::BaseField::sum_of_products(&[r, self.y], &[v, j]);
533
534            // Z3 = ((Z1+Z2)^2 - Z1Z1 - Z2Z2)*H
535            // This is equal to Z3 = 2 * Z1 * Z2 * H, and computing it this way
536            // is faster.
537            self.z *= other.z;
538            self.z.double_in_place();
539            self.z *= &h;
540        }
541    }
542}
543
544impl<'a, P: SWCurveConfig> Sub<&'a Self> for Projective<P> {
545    type Output = Self;
546
547    #[inline]
548    fn sub(mut self, other: &'a Self) -> Self {
549        self -= other;
550        self
551    }
552}
553
554impl<'a, P: SWCurveConfig> SubAssign<&'a Self> for Projective<P> {
555    fn sub_assign(&mut self, other: &'a Self) {
556        *self += &(-(*other));
557    }
558}
559
560impl<P: SWCurveConfig, T: Borrow<P::ScalarField>> MulAssign<T>
561    for Projective<P>
562{
563    fn mul_assign(&mut self, other: T) {
564        *self = self.mul_bigint(other.borrow().into_bigint());
565    }
566}
567
568impl<P: SWCurveConfig, T: Borrow<P::ScalarField>> Mul<T> for Projective<P> {
569    type Output = Self;
570
571    #[inline]
572    fn mul(mut self, other: T) -> Self {
573        self *= other;
574        self
575    }
576}
577
578// The affine point X, Y is represented in the Jacobian
579// coordinates with Z = 1.
580impl<P: SWCurveConfig> From<Affine<P>> for Projective<P> {
581    #[inline]
582    fn from(p: Affine<P>) -> Projective<P> {
583        p.xy().map_or(Projective::zero(), |(x, y)| Self {
584            x,
585            y,
586            z: P::BaseField::one(),
587        })
588    }
589}
590
591impl<P: SWCurveConfig, T: Borrow<Affine<P>>> core::iter::Sum<T>
592    for Projective<P>
593{
594    fn sum<I: Iterator<Item = T>>(iter: I) -> Self {
595        iter.fold(Projective::zero(), |sum, x| sum + x.borrow())
596    }
597}
openzeppelin_crypto/curve/sw/projective.rs

openzeppelin_crypto/curve/sw/
projective.rs
