ark_ec/models/twisted_edwards/
group.rs

1use ark_serialize::{
2    CanonicalDeserialize, CanonicalSerialize, Compress, SerializationError, Valid, Validate,
3};
4use ark_std::{
5    borrow::Borrow,
6    fmt::{Display, Formatter, Result as FmtResult},
7    hash::{Hash, Hasher},
8    io::{Read, Write},
9    ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
10    rand::{
11        distributions::{Distribution, Standard},
12        Rng,
13    },
14    vec::*,
15    One, Zero,
16};
17
18use ark_ff::{fields::Field, AdditiveGroup, PrimeField, ToConstraintField, UniformRand};
19
20use educe::Educe;
21use zeroize::Zeroize;
22
23#[cfg(feature = "parallel")]
24use rayon::prelude::*;
25
26use super::{Affine, MontCurveConfig, TECurveConfig};
27use crate::{
28    scalar_mul::{variable_base::VariableBaseMSM, ScalarMul},
29    AffineRepr, CurveGroup, PrimeGroup,
30};
31
32/// `Projective` implements Extended Twisted Edwards Coordinates
33/// as described in [\[HKCD08\]](https://eprint.iacr.org/2008/522.pdf).
34///
35/// This implementation uses the unified addition formulae from that paper (see
36/// Section 3.1).
37#[derive(Educe)]
38#[educe(Copy, Clone, Eq(bound(P: TECurveConfig)), Debug)]
39#[must_use]
40pub struct Projective<P: TECurveConfig> {
41    pub x: P::BaseField,
42    pub y: P::BaseField,
43    pub t: P::BaseField,
44    pub z: P::BaseField,
45}
46
47impl<P: TECurveConfig> PartialEq<Affine<P>> for Projective<P> {
48    fn eq(&self, other: &Affine<P>) -> bool {
49        *self == other.into_group()
50    }
51}
52
53impl<P: TECurveConfig> Display for Projective<P> {
54    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
55        write!(f, "{}", Affine::from(*self))
56    }
57}
58
59impl<P: TECurveConfig> 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        // x1/z1 == x2/z2  <==> x1 * z2 == x2 * z1
70        (self.x * &other.z) == (other.x * &self.z) && (self.y * &other.z) == (other.y * &self.z)
71    }
72}
73
74impl<P: TECurveConfig> Hash for Projective<P> {
75    fn hash<H: Hasher>(&self, state: &mut H) {
76        self.into_affine().hash(state)
77    }
78}
79
80impl<P: TECurveConfig> Distribution<Projective<P>> for Standard {
81    /// Generates a uniformly random instance of the curve.
82    #[inline]
83    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Projective<P> {
84        loop {
85            let y = P::BaseField::rand(rng);
86            let greatest = rng.gen();
87
88            if let Some(p) = Affine::get_point_from_y_unchecked(y, greatest) {
89                return p.mul_by_cofactor_to_group();
90            }
91        }
92    }
93}
94
95impl<P: TECurveConfig> Default for Projective<P> {
96    #[inline]
97    fn default() -> Self {
98        Self::zero()
99    }
100}
101
102impl<P: TECurveConfig> Projective<P> {
103    /// Construct a new group element without checking whether the coordinates
104    /// specify a point in the subgroup.
105    pub const fn new_unchecked(
106        x: P::BaseField,
107        y: P::BaseField,
108        t: P::BaseField,
109        z: P::BaseField,
110    ) -> Self {
111        Self { x, y, t, z }
112    }
113
114    /// Construct a new group element in a way while enforcing that points are in
115    /// the prime-order subgroup.
116    pub fn new(x: P::BaseField, y: P::BaseField, t: P::BaseField, z: P::BaseField) -> Self {
117        let p = Self::new_unchecked(x, y, t, z).into_affine();
118        assert!(p.is_on_curve());
119        assert!(p.is_in_correct_subgroup_assuming_on_curve());
120        p.into()
121    }
122}
123impl<P: TECurveConfig> Zeroize for Projective<P> {
124    // The phantom data does not contain element-specific data
125    // and thus does not need to be zeroized.
126    fn zeroize(&mut self) {
127        self.x.zeroize();
128        self.y.zeroize();
129        self.t.zeroize();
130        self.z.zeroize();
131    }
132}
133
134impl<P: TECurveConfig> Zero for Projective<P> {
135    fn zero() -> Self {
136        Self::new_unchecked(
137            P::BaseField::zero(),
138            P::BaseField::one(),
139            P::BaseField::zero(),
140            P::BaseField::one(),
141        )
142    }
143
144    fn is_zero(&self) -> bool {
145        self.x.is_zero() && self.y == self.z && !self.y.is_zero() && self.t.is_zero()
146    }
147}
148
149impl<P: TECurveConfig> AdditiveGroup for Projective<P> {
150    type Scalar = P::ScalarField;
151
152    const ZERO: Self = Self::new_unchecked(
153        P::BaseField::ZERO,
154        P::BaseField::ONE,
155        P::BaseField::ZERO,
156        P::BaseField::ONE,
157    );
158
159    fn double_in_place(&mut self) -> &mut Self {
160        // See "Twisted Edwards Curves Revisited"
161        // Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson
162        // 3.3 Doubling in E^e
163        // Source: https://www.hyperelliptic.org/EFD/g1p/data/twisted/extended/doubling/dbl-2008-hwcd
164
165        // A = X1^2
166        let a = self.x.square();
167        // B = Y1^2
168        let b = self.y.square();
169        // C = 2 * Z1^2
170        let c = self.z.square().double();
171        // D = a * A
172        let d = P::mul_by_a(a);
173        // E = (X1 + Y1)^2 - A - B
174        let e = (self.x + &self.y).square() - &a - &b;
175        // G = D + B
176        let g = d + &b;
177        // F = G - C
178        let f = g - &c;
179        // H = D - B
180        let h = d - &b;
181        // X3 = E * F
182        self.x = e * &f;
183        // Y3 = G * H
184        self.y = g * &h;
185        // T3 = E * H
186        self.t = e * &h;
187        // Z3 = F * G
188        self.z = f * &g;
189
190        self
191    }
192}
193
194impl<P: TECurveConfig> PrimeGroup for Projective<P> {
195    type ScalarField = P::ScalarField;
196
197    fn generator() -> Self {
198        Affine::generator().into()
199    }
200
201    #[inline]
202    fn mul_bigint(&self, other: impl AsRef<[u64]>) -> Self {
203        P::mul_projective(self, other.as_ref())
204    }
205}
206
207impl<P: TECurveConfig> CurveGroup for Projective<P> {
208    type Config = P;
209    type BaseField = P::BaseField;
210    type Affine = Affine<P>;
211    type FullGroup = Affine<P>;
212
213    fn normalize_batch(v: &[Self]) -> Vec<Self::Affine> {
214        // A projective curve element (x, y, t, z) is normalized
215        // to its affine representation, by the conversion
216        // (x, y, t, z) -> (x/z, y/z, t/z, 1)
217        // Batch normalizing N twisted edwards curve elements costs:
218        //     1 inversion + 6N field multiplications
219        // (batch inversion requires 3N multiplications + 1 inversion)
220        let mut z_s = v.iter().map(|g| g.z).collect::<Vec<_>>();
221        ark_ff::batch_inversion(&mut z_s);
222
223        // Perform affine transformations
224        ark_std::cfg_iter!(v)
225            .zip(z_s)
226            .map(|(g, z)| match g.is_zero() {
227                true => Affine::zero(),
228                false => {
229                    let x = g.x * &z;
230                    let y = g.y * &z;
231                    Affine::new_unchecked(x, y)
232                },
233            })
234            .collect()
235    }
236}
237
238impl<P: TECurveConfig> Neg for Projective<P> {
239    type Output = Self;
240    fn neg(mut self) -> Self {
241        self.x = -self.x;
242        self.t = -self.t;
243        self
244    }
245}
246
247impl<P: TECurveConfig, T: Borrow<Affine<P>>> AddAssign<T> for Projective<P> {
248    fn add_assign(&mut self, other: T) {
249        let other = other.borrow();
250        // See "Twisted Edwards Curves Revisited"
251        // Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson
252        // 3.1 Unified Addition in E^e
253        // Source: https://www.hyperelliptic.org/EFD/g1p/data/twisted/extended/addition/madd-2008-hwcd
254
255        // A = X1*X2
256        let a = self.x * &other.x;
257        // B = Y1*Y2
258        let b = self.y * &other.y;
259        // C = T1*d*T2
260        let c = P::COEFF_D * &self.t * &other.x * &other.y;
261
262        // D = Z1
263        let d = self.z;
264        // E = (X1+Y1)*(X2+Y2)-A-B
265        let e = (self.x + &self.y) * &(other.x + &other.y) - &a - &b;
266        // F = D-C
267        let f = d - &c;
268        // G = D+C
269        let g = d + &c;
270        // H = B-a*A
271        let h = b - &P::mul_by_a(a);
272        // X3 = E*F
273        self.x = e * &f;
274        // Y3 = G*H
275        self.y = g * &h;
276        // T3 = E*H
277        self.t = e * &h;
278        // Z3 = F*G
279        self.z = f * &g;
280    }
281}
282
283impl<P: TECurveConfig, T: Borrow<Affine<P>>> Add<T> for Projective<P> {
284    type Output = Self;
285    fn add(mut self, other: T) -> Self {
286        let other = other.borrow();
287        self += other;
288        self
289    }
290}
291
292impl<P: TECurveConfig, T: Borrow<Affine<P>>> SubAssign<T> for Projective<P> {
293    fn sub_assign(&mut self, other: T) {
294        *self += -(*other.borrow());
295    }
296}
297
298impl<P: TECurveConfig, T: Borrow<Affine<P>>> Sub<T> for Projective<P> {
299    type Output = Self;
300    fn sub(mut self, other: T) -> Self {
301        self -= other.borrow();
302        self
303    }
304}
305ark_ff::impl_additive_ops_from_ref!(Projective, TECurveConfig);
306
307impl<'a, P: TECurveConfig> Add<&'a Self> for Projective<P> {
308    type Output = Self;
309    fn add(mut self, other: &'a Self) -> Self {
310        self += other;
311        self
312    }
313}
314
315impl<'a, P: TECurveConfig> Sub<&'a Self> for Projective<P> {
316    type Output = Self;
317    fn sub(mut self, other: &'a Self) -> Self {
318        self -= other;
319        self
320    }
321}
322
323impl<'a, P: TECurveConfig> AddAssign<&'a Self> for Projective<P> {
324    fn add_assign(&mut self, other: &'a Self) {
325        // See "Twisted Edwards Curves Revisited" (https://eprint.iacr.org/2008/522.pdf)
326        // by Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson
327        // 3.1 Unified Addition in E^e
328
329        // A = x1 * x2
330        let a = self.x * &other.x;
331
332        // B = y1 * y2
333        let b = self.y * &other.y;
334
335        // C = d * t1 * t2
336        let c = P::COEFF_D * &self.t * &other.t;
337
338        // D = z1 * z2
339        let d = self.z * &other.z;
340
341        // H = B - aA
342        let h = b - &P::mul_by_a(a);
343
344        // E = (x1 + y1) * (x2 + y2) - A - B
345        let e = (self.x + &self.y) * &(other.x + &other.y) - &a - &b;
346
347        // F = D - C
348        let f = d - &c;
349
350        // G = D + C
351        let g = d + &c;
352
353        // x3 = E * F
354        self.x = e * &f;
355
356        // y3 = G * H
357        self.y = g * &h;
358
359        // t3 = E * H
360        self.t = e * &h;
361
362        // z3 = F * G
363        self.z = f * &g;
364    }
365}
366
367impl<'a, P: TECurveConfig> SubAssign<&'a Self> for Projective<P> {
368    fn sub_assign(&mut self, other: &'a Self) {
369        *self += -(*other);
370    }
371}
372
373impl<P: TECurveConfig, T: Borrow<P::ScalarField>> MulAssign<T> for Projective<P> {
374    fn mul_assign(&mut self, other: T) {
375        *self = self.mul_bigint(other.borrow().into_bigint())
376    }
377}
378
379impl<P: TECurveConfig, T: Borrow<P::ScalarField>> Mul<T> for Projective<P> {
380    type Output = Self;
381
382    #[inline]
383    fn mul(mut self, other: T) -> Self {
384        self *= other;
385        self
386    }
387}
388
389impl<P: TECurveConfig, T: Borrow<Affine<P>>> ark_std::iter::Sum<T> for Projective<P> {
390    fn sum<I>(iter: I) -> Self
391    where
392        I: Iterator<Item = T>,
393    {
394        iter.fold(Self::zero(), |acc, x| acc + x.borrow())
395    }
396}
397
398// The affine point (X, Y) is represented in the Extended Projective coordinates
399// with Z = 1.
400impl<P: TECurveConfig> From<Affine<P>> for Projective<P> {
401    fn from(p: Affine<P>) -> Projective<P> {
402        Self::new_unchecked(p.x, p.y, p.x * &p.y, P::BaseField::one())
403    }
404}
405
406#[derive(Educe)]
407#[educe(Copy, Clone, PartialEq, Eq, Debug, Hash)]
408pub struct MontgomeryAffine<P: MontCurveConfig> {
409    pub x: P::BaseField,
410    pub y: P::BaseField,
411}
412
413impl<P: MontCurveConfig> Display for MontgomeryAffine<P> {
414    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
415        write!(f, "MontgomeryAffine(x={}, y={})", self.x, self.y)
416    }
417}
418
419impl<P: MontCurveConfig> MontgomeryAffine<P> {
420    pub fn new(x: P::BaseField, y: P::BaseField) -> Self {
421        Self { x, y }
422    }
423}
424
425impl<P: TECurveConfig> CanonicalSerialize for Projective<P> {
426    #[allow(unused_qualifications)]
427    #[inline]
428    fn serialize_with_mode<W: Write>(
429        &self,
430        writer: W,
431        compress: Compress,
432    ) -> Result<(), SerializationError> {
433        let aff = Affine::<P>::from(*self);
434        P::serialize_with_mode(&aff, writer, compress)
435    }
436
437    #[inline]
438    fn serialized_size(&self, compress: Compress) -> usize {
439        P::serialized_size(compress)
440    }
441}
442
443impl<P: TECurveConfig> Valid for Projective<P> {
444    fn check(&self) -> Result<(), SerializationError> {
445        self.into_affine().check()
446    }
447
448    fn batch_check<'a>(
449        batch: impl Iterator<Item = &'a Self> + Send,
450    ) -> Result<(), SerializationError>
451    where
452        Self: 'a,
453    {
454        let batch = batch.copied().collect::<Vec<_>>();
455        let batch = Self::normalize_batch(&batch);
456        Affine::batch_check(batch.iter())
457    }
458}
459
460impl<P: TECurveConfig> CanonicalDeserialize for Projective<P> {
461    #[allow(unused_qualifications)]
462    fn deserialize_with_mode<R: Read>(
463        reader: R,
464        compress: Compress,
465        validate: Validate,
466    ) -> Result<Self, SerializationError> {
467        let aff = P::deserialize_with_mode(reader, compress, validate)?;
468        Ok(aff.into())
469    }
470}
471
472impl<M: TECurveConfig, ConstraintF: Field> ToConstraintField<ConstraintF> for Projective<M>
473where
474    M::BaseField: ToConstraintField<ConstraintF>,
475{
476    #[inline]
477    fn to_field_elements(&self) -> Option<Vec<ConstraintF>> {
478        Affine::from(*self).to_field_elements()
479    }
480}
481
482impl<P: TECurveConfig> ScalarMul for Projective<P> {
483    type MulBase = Affine<P>;
484    const NEGATION_IS_CHEAP: bool = true;
485
486    fn batch_convert_to_mul_base(bases: &[Self]) -> Vec<Self::MulBase> {
487        Self::normalize_batch(bases)
488    }
489}
490
491impl<P: TECurveConfig> VariableBaseMSM for Projective<P> {
492    fn msm(bases: &[Self::MulBase], bigints: &[Self::ScalarField]) -> Result<Self, usize> {
493        P::msm(bases, bigints)
494    }
495}
ark_ec/models/twisted_edwards/group.rs

ark_ec/models/twisted_edwards/
group.rs
