ark_ec/models/double_odd/
group.rs

1use ark_serialize::{
2    CanonicalDeserialize, CanonicalSerialize, Compress, SerializationError, Valid, Validate,
3};
4use ark_std::{
5    borrow::Borrow,
6    fmt::{Debug, 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::Vec,
15    Zero,
16};
17use educe::Educe;
18
19use ark_ff::{fields::Field, AdditiveGroup, PrimeField, ToConstraintField, UniformRand};
20
21use zeroize::Zeroize;
22
23#[cfg(feature = "parallel")]
24use rayon::prelude::*;
25
26use super::{Affine, DOCurveConfig};
27use crate::{
28    scalar_mul::{variable_base::VariableBaseMSM, ScalarMul},
29    AffineRepr, CurveGroup, PrimeGroup,
30};
31
32/// Fractional coordinates as utilised in <https://doubleodd.group/doubleodd-jq.pdf>,
33/// but first defined in <https://www.sciencedirect.com/science/article/pii/S0020019007001433>.
34/// Affine point (e,u) is represented as (E:Z:U:T) such that:
35/// - Z != 0
36/// - e = E/Z
37/// - u = U/Z
38/// - u**2 / T/Z
39#[derive(Educe)]
40#[educe(Copy, Clone)]
41#[must_use]
42pub struct Projective<P: DOCurveConfig> {
43    /// `E / Z` projection of the affine `e`
44    pub e: P::BaseField,
45    /// Projective multiplicative inverse.
46    pub z: P::BaseField,
47    /// `U / Z` projection of the affine `u`
48    pub u: P::BaseField,
49    /// Additional formula for faster addition: `T = U^2/Z`
50    pub t: P::BaseField,
51}
52
53impl<P: DOCurveConfig> Display for Projective<P> {
54    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
55        write!(f, "{}", Affine::from(*self))
56    }
57}
58
59impl<P: DOCurveConfig> Debug for Projective<P> {
60    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
61        match self.is_zero() {
62            true => write!(f, "infinity"),
63            false => write!(f, "({}, {}, {}, {})", self.e, self.z, self.u, self.t),
64        }
65    }
66}
67
68impl<P: DOCurveConfig> Eq for Projective<P> {}
69impl<P: DOCurveConfig> PartialEq for Projective<P> {
70    fn eq(&self, other: &Self) -> bool {
71        if self.is_zero() {
72            return other.is_zero();
73        }
74        if other.is_zero() {
75            return false;
76        }
77        self.e * other.u == other.e * self.u
78    }
79}
80
81impl<P: DOCurveConfig> PartialEq<Affine<P>> for Projective<P> {
82    fn eq(&self, other: &Affine<P>) -> bool {
83        *self == other.into_group()
84    }
85}
86
87impl<P: DOCurveConfig> Hash for Projective<P> {
88    fn hash<H: Hasher>(&self, state: &mut H) {
89        self.into_affine().hash(state)
90    }
91}
92
93impl<P: DOCurveConfig> Distribution<Projective<P>> for Standard {
94    /// Generates a uniformly random instance of the curve.
95    #[inline]
96    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Projective<P> {
97        loop {
98            let u = P::BaseField::rand(rng);
99            let greatest = rng.gen();
100
101            if let Some(p) = Affine::get_point_from_u_unchecked(u, greatest) {
102                return p.into();
103            }
104        }
105    }
106}
107
108impl<P: DOCurveConfig> Default for Projective<P> {
109    #[inline]
110    fn default() -> Self {
111        Self::zero()
112    }
113}
114
115impl<P: DOCurveConfig> Projective<P> {
116    /// Constructs a new group element without checking whether the coordinates
117    /// specify a point in the subgroup.
118    pub const fn new_unchecked(
119        e: P::BaseField,
120        z: P::BaseField,
121        u: P::BaseField,
122        t: P::BaseField,
123    ) -> Self {
124        Self { e, z, u, t }
125    }
126
127    /// Constructs a new group element in a way while enforcing that points are in
128    /// the prime-order subgroup.
129    pub fn new(e: P::BaseField, z: P::BaseField, u: P::BaseField, t: P::BaseField) -> Self {
130        let p = Self::new_unchecked(e, z, u, t);
131        assert!(p.into_affine().is_on_curve(), "not_on_curve");
132        p
133    }
134}
135
136impl<P: DOCurveConfig> Zeroize for Projective<P> {
137    fn zeroize(&mut self) {
138        self.e.zeroize();
139        self.u.zeroize();
140        self.z.zeroize();
141        self.t.zeroize();
142    }
143}
144
145impl<P: DOCurveConfig> Zero for Projective<P> {
146    /// Returns one of the representants for the identity, namely the point-at-infinity `(1,1,0,0)`.
147    ///
148    /// The other representant `N=(-1,1,0,0)` of the identity could also be returned, but the
149    /// implementation of formulas only requires one representant.
150    #[inline]
151    fn zero() -> Self {
152        Self::new_unchecked(
153            P::BaseField::ONE,
154            P::BaseField::ONE,
155            P::BaseField::ZERO,
156            P::BaseField::ZERO,
157        )
158    }
159
160    #[inline]
161    // Zero has two representants: 'O = (X,X,0,0)`, and `O+N = (X,-X,0,0)`.
162    // These are the only two points with U=0, and is_zero assumes the point is correct,
163    // so E and Z don't need to be checked.
164    fn is_zero(&self) -> bool {
165        self.u == P::BaseField::ZERO
166    }
167}
168
169impl<P: DOCurveConfig> AdditiveGroup for Projective<P> {
170    type Scalar = P::ScalarField;
171
172    const ZERO: Self = Self::new_unchecked(
173        P::BaseField::ONE,
174        P::BaseField::ONE,
175        P::BaseField::ZERO,
176        P::BaseField::ZERO,
177    );
178
179    // Implements extended coordinates doubling as per the DO website:
180    // https://doubleodd.group/formulas-eu.html#extended-coordinates
181    // https://web.archive.org/web/20240718235643/https://doubleodd.group/formulas-eu.html#extended-coordinates
182    fn double_in_place(&mut self) -> &mut Self {
183        self.z = -P::get_c().double() * self.t.square(); // Self.z == -2cT^2
184        self.t = self.e;
185        self.e.square_in_place(); // Self.e == E^2
186        self.z += self.e; // Self.z == E^2 -2cT^2
187        self.z += (P::COEFF_A * self.u.square()).double(); // Self.z == W' == E^2 + 2aU^2 -2cT^2
188
189        self.t *= self.u;
190        self.t.double_in_place(); // Self.t == J'= 2EU
191
192        self.u = self.t; // Self.u == Self.t == J'
193        self.t.square_in_place(); // Self.t == T' = J'^2
194
195        self.u *= self.z; // U' = J' * W'
196        self.z.square_in_place(); // Self.z == W'^2
197
198        self.e.square_in_place(); // Self.e == X' == E^4
199        self.e.double_in_place(); // Self.e == 2X'
200        self.e += -self.z + (P::COEFF_A * self.t); // E' = 2X' - Z' + aT'
201
202        self
203    }
204}
205
206impl<P: DOCurveConfig> PrimeGroup for Projective<P> {
207    type ScalarField = P::ScalarField;
208
209    #[inline]
210    fn generator() -> Self {
211        Affine::generator().into()
212    }
213
214    #[inline]
215    fn mul_bigint(&self, other: impl AsRef<[u64]>) -> Self {
216        P::mul_projective(self, other.as_ref())
217    }
218}
219
220impl<P: DOCurveConfig> CurveGroup for Projective<P> {
221    type Config = P;
222    type BaseField = P::BaseField;
223    type Affine = Affine<P>;
224    type FullGroup = Affine<P>;
225
226    #[inline]
227    fn normalize_batch(v: &[Self]) -> Vec<Self::Affine> {
228        let mut z_s = v.iter().map(|g| g.z).collect::<Vec<_>>();
229        ark_ff::batch_inversion(&mut z_s);
230
231        // Perform affine transformations
232        ark_std::cfg_iter!(v)
233            .zip(z_s)
234            .map(|(g, z)| match g.is_zero() {
235                true => Affine::identity(),
236                false => {
237                    let e = g.e * z;
238                    let u = g.u * z;
239
240                    Affine::new_unchecked(e, u)
241                },
242            })
243            .collect()
244    }
245}
246
247impl<P: DOCurveConfig> Neg for Projective<P> {
248    type Output = Self;
249
250    #[inline]
251    fn neg(mut self) -> Self {
252        self.u = -self.u;
253        self
254    }
255}
256
257impl<P: DOCurveConfig, T: Borrow<Affine<P>>> AddAssign<T> for Projective<P> {
258    /// Using Algorithm 3 from <https://doubleodd.group/doubleodd-jq.pdf>,
259    /// simplified because the second point is affine
260    /// (n2 = Z1, n5 = Z1*T2 + T1).
261    fn add_assign(&mut self, other: T) {
262        let other = other.borrow();
263        let othert = other.u.square();
264        let n1 = self.e * other.e;
265        let n2 = self.z;
266        let n3 = self.u * other.u;
267        let n4 = self.t * othert;
268
269        let n5 = self.z * othert + self.t;
270        let n6 = (self.e + self.u) * (other.e + other.u) - n1 - n3;
271        let c = P::get_c();
272        let cn4 = c * n4;
273        let n7 = n2 - cn4;
274
275        let n3d = n3.double();
276
277        self.e = (n2 + cn4) * (n1 - P::COEFF_A * n3d) + c * n3d * n5;
278        self.z = n7.square();
279        self.t = n6.square();
280        self.u = n7 * n6;
281    }
282}
283
284impl<P: DOCurveConfig, T: Borrow<Affine<P>>> Add<T> for Projective<P> {
285    type Output = Self;
286    fn add(mut self, other: T) -> Self {
287        let other = other.borrow();
288        self += other;
289        self
290    }
291}
292
293impl<P: DOCurveConfig, T: Borrow<Affine<P>>> SubAssign<T> for Projective<P> {
294    fn sub_assign(&mut self, other: T) {
295        *self += -(*other.borrow());
296    }
297}
298
299impl<P: DOCurveConfig, T: Borrow<Affine<P>>> Sub<T> for Projective<P> {
300    type Output = Self;
301    fn sub(mut self, other: T) -> Self {
302        self -= other.borrow();
303        self
304    }
305}
306
307ark_ff::impl_additive_ops_from_ref!(Projective, DOCurveConfig);
308
309impl<'a, P: DOCurveConfig> Add<&'a Self> for Projective<P> {
310    type Output = Self;
311
312    #[inline]
313    fn add(mut self, other: &'a Self) -> Self {
314        self += other;
315        self
316    }
317}
318
319impl<'a, P: DOCurveConfig> AddAssign<&'a Self> for Projective<P> {
320    /// Using Algorithm 3 from <https://doubleodd.group/doubleodd-jq.pdf>.
321    fn add_assign(&mut self, other: &'a Self) {
322        if self.is_zero() {
323            *self = *other;
324            return;
325        }
326
327        if other.is_zero() {
328            return;
329        }
330
331        let n1 = self.e * other.e;
332        let n2 = self.z * other.z;
333        let n3 = self.u * other.u;
334        let n4 = self.t * other.t;
335
336        let n5 = (self.z + self.t) * (other.z + other.t) - n2 - n4;
337        self.t = (self.e + self.u) * (other.e + other.u) - n1 - n3;
338        let c = P::get_c();
339        let cn4 = c * n4;
340        self.z = n2 - cn4;
341
342        let n3d = n3.double();
343
344        self.e = (n2 + cn4) * (n1 - P::COEFF_A * n3d) + c * n3d * n5;
345        self.u = self.z * self.t;
346        self.z.square_in_place();
347        self.t.square_in_place();
348    }
349}
350
351impl<'a, P: DOCurveConfig> Sub<&'a Self> for Projective<P> {
352    type Output = Self;
353
354    #[inline]
355    fn sub(mut self, other: &'a Self) -> Self {
356        self -= other;
357        self
358    }
359}
360
361impl<'a, P: DOCurveConfig> SubAssign<&'a Self> for Projective<P> {
362    fn sub_assign(&mut self, other: &'a Self) {
363        *self += &(-(*other));
364    }
365}
366
367impl<P: DOCurveConfig, T: Borrow<P::ScalarField>> MulAssign<T> for Projective<P> {
368    fn mul_assign(&mut self, other: T) {
369        *self = self.mul_bigint(other.borrow().into_bigint())
370    }
371}
372
373impl<P: DOCurveConfig, T: Borrow<P::ScalarField>> Mul<T> for Projective<P> {
374    type Output = Self;
375
376    #[inline]
377    fn mul(mut self, other: T) -> Self {
378        self *= other;
379        self
380    }
381}
382
383impl<P: DOCurveConfig> From<Affine<P>> for Projective<P> {
384    #[inline]
385    fn from(p: Affine<P>) -> Self {
386        let u = p.u;
387        let e = p.e;
388        let z = P::BaseField::ONE;
389        let t = u.square();
390
391        Self::new_unchecked(e, z, u, t)
392    }
393}
394
395impl<P: DOCurveConfig> CanonicalSerialize for Projective<P> {
396    #[inline]
397    fn serialize_with_mode<W: Write>(
398        &self,
399        writer: W,
400        compress: Compress,
401    ) -> Result<(), SerializationError> {
402        let aff = Affine::<P>::from(*self);
403        P::serialize_with_mode(&aff, writer, compress)
404    }
405
406    #[inline]
407    fn serialized_size(&self, compress: Compress) -> usize {
408        P::serialized_size(compress)
409    }
410}
411
412impl<P: DOCurveConfig> Valid for Projective<P> {
413    fn check(&self) -> Result<(), SerializationError> {
414        self.into_affine().check()
415    }
416
417    fn batch_check<'a>(
418        batch: impl Iterator<Item = &'a Self> + Send,
419    ) -> Result<(), SerializationError>
420    where
421        Self: 'a,
422    {
423        let batch = batch.copied().collect::<Vec<_>>();
424        let batch = Self::normalize_batch(&batch);
425        Affine::batch_check(batch.iter())
426    }
427}
428
429impl<P: DOCurveConfig> CanonicalDeserialize for Projective<P> {
430    fn deserialize_with_mode<R: Read>(
431        reader: R,
432        compress: Compress,
433        validate: Validate,
434    ) -> Result<Self, SerializationError> {
435        let aff = P::deserialize_with_mode(reader, compress, validate)?;
436        Ok(aff.into())
437    }
438}
439
440impl<M: DOCurveConfig, ConstraintF: Field> ToConstraintField<ConstraintF> for Projective<M>
441where
442    M::BaseField: ToConstraintField<ConstraintF>,
443{
444    #[inline]
445    fn to_field_elements(&self) -> Option<Vec<ConstraintF>> {
446        Affine::from(*self).to_field_elements()
447    }
448}
449
450impl<P: DOCurveConfig> ScalarMul for Projective<P> {
451    type MulBase = Affine<P>;
452    const NEGATION_IS_CHEAP: bool = true;
453
454    fn batch_convert_to_mul_base(bases: &[Self]) -> Vec<Self::MulBase> {
455        Self::normalize_batch(bases)
456    }
457}
458
459impl<P: DOCurveConfig> VariableBaseMSM for Projective<P> {
460    type Bucket = Self;
461    const ZERO_BUCKET: Self = Self::ZERO;
462
463    fn msm(bases: &[Self::MulBase], bigints: &[Self::ScalarField]) -> Result<Self, usize> {
464        P::msm(bases, bigints)
465    }
466}
467
468impl<P: DOCurveConfig, T: Borrow<Affine<P>>> core::iter::Sum<T> for Projective<P> {
469    fn sum<I: Iterator<Item = T>>(iter: I) -> Self {
470        iter.fold(Self::zero(), |sum, x| sum + x.borrow())
471    }
472}
ark_ec/models/double_odd/group.rs

ark_ec/models/double_odd/
group.rs
