ark_ec/models/short_weierstrass/
affine.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    io::{Read, Write},
8    ops::{Add, Mul, Neg, Sub},
9    rand::{
10        distributions::{Distribution, Standard},
11        Rng,
12    },
13    vec::*,
14    One, Zero,
15};
16
17use ark_ff::{fields::Field, AdditiveGroup, PrimeField, ToConstraintField, UniformRand};
18
19use educe::Educe;
20use zeroize::Zeroize;
21
22use super::{bucket::Bucket, Projective, SWCurveConfig, SWFlags, ZeroFlag};
23use crate::AffineRepr;
24
25/// Affine coordinates for a point on an elliptic curve in short Weierstrass
26/// form, over the base field `P::BaseField`.
27#[derive(Educe)]
28#[educe(Copy, Clone, PartialEq, Eq, Hash)]
29#[must_use]
30pub struct Affine<P: SWCurveConfig> {
31    #[doc(hidden)]
32    pub x: P::BaseField,
33    #[doc(hidden)]
34    pub y: P::BaseField,
35    #[doc(hidden)]
36    pub(super) infinity: P::ZeroFlag,
37}
38
39impl<P: SWCurveConfig> PartialEq<Projective<P>> for Affine<P> {
40    fn eq(&self, other: &Projective<P>) -> bool {
41        self.into_group() == *other
42    }
43}
44
45impl<P: SWCurveConfig> Display for Affine<P> {
46    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
47        match self.is_zero() {
48            true => write!(f, "infinity"),
49            false => write!(f, "({}, {})", self.x, self.y),
50        }
51    }
52}
53
54impl<P: SWCurveConfig> Debug for Affine<P> {
55    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
56        match self.is_zero() {
57            true => write!(f, "infinity"),
58            false => write!(f, "({}, {})", self.x, self.y),
59        }
60    }
61}
62
63impl<P: SWCurveConfig> Affine<P> {
64    /// Constructs a group element from x and y coordinates.
65    /// Performs checks to ensure that the point is on the curve and is in the right subgroup.
66    pub fn new(x: P::BaseField, y: P::BaseField) -> Self {
67        let point = Self {
68            x,
69            y,
70            infinity: P::ZeroFlag::IS_NOT_ZERO,
71        };
72        assert!(point.is_on_curve());
73        assert!(point.is_in_correct_subgroup_assuming_on_curve());
74        point
75    }
76
77    /// Constructs a group element from x and y coordinates.
78    ///
79    /// # Warning
80    ///
81    /// Does *not* perform any checks to ensure the point is in the curve or
82    /// is in the right subgroup.
83    pub const fn new_unchecked(x: P::BaseField, y: P::BaseField) -> Self {
84        Self {
85            x,
86            y,
87            infinity: P::ZeroFlag::IS_NOT_ZERO,
88        }
89    }
90
91    pub const fn identity() -> Self {
92        // Setting these to zero is *load-bearing* and important.
93        // These are the values that represent the identity element
94        // when `P::ZeroFlag` is `()`.
95        //
96        // We cannot ask `P::ZeroFlag` to provide the zero values
97        // via a `const fn` because constant functions in traits
98        // are not yet supported in Rust.
99        Self {
100            x: P::BaseField::ZERO,
101            y: P::BaseField::ZERO,
102            infinity: P::ZeroFlag::IS_ZERO,
103        }
104    }
105
106    /// Attempts to construct an affine point given an x-coordinate. The
107    /// point is not guaranteed to be in the prime order subgroup.
108    ///
109    /// If and only if `greatest` is set will the lexicographically
110    /// largest y-coordinate be selected.
111    #[allow(dead_code)]
112    pub fn get_point_from_x_unchecked(x: P::BaseField, greatest: bool) -> Option<Self> {
113        Self::get_ys_from_x_unchecked(x).map(|(smaller, larger)| {
114            if greatest {
115                Self::new_unchecked(x, larger)
116            } else {
117                Self::new_unchecked(x, smaller)
118            }
119        })
120    }
121
122    /// Returns the two possible y-coordinates corresponding to the given x-coordinate.
123    /// The corresponding points are not guaranteed to be in the prime-order subgroup,
124    /// but are guaranteed to be on the curve. That is, this method returns `None`
125    /// if the x-coordinate corresponds to a non-curve point.
126    ///
127    /// The results are sorted by lexicographical order.
128    /// This means that, if `P::BaseField: PrimeField`, the results are sorted as integers.
129    pub fn get_ys_from_x_unchecked(x: P::BaseField) -> Option<(P::BaseField, P::BaseField)> {
130        // Compute the curve equation x^3 + Ax + B.
131        // Since Rust does not optimise away additions with zero, we explicitly check
132        // for that case here, and avoid multiplication by `a` if possible.
133        let mut x3_plus_ax_plus_b = P::add_b(x.square() * x);
134        if !P::COEFF_A.is_zero() {
135            x3_plus_ax_plus_b += P::mul_by_a(x)
136        };
137        let y = x3_plus_ax_plus_b.sqrt()?;
138        let neg_y = -y;
139        match y < neg_y {
140            true => Some((y, neg_y)),
141            false => Some((neg_y, y)),
142        }
143    }
144
145    /// Checks if `self` is a valid point on the curve.
146    pub fn is_on_curve(&self) -> bool {
147        if self.is_zero() {
148            true
149        } else {
150            // Rust does not optimise away addition with zero
151            let mut x3b = P::add_b(self.x.square() * self.x);
152            if !P::COEFF_A.is_zero() {
153                x3b += P::mul_by_a(self.x);
154            };
155            self.y.square() == x3b
156        }
157    }
158
159    pub fn to_flags(&self) -> SWFlags {
160        if self.is_zero() {
161            SWFlags::PointAtInfinity
162        } else if self.y <= -self.y {
163            SWFlags::YIsPositive
164        } else {
165            SWFlags::YIsNegative
166        }
167    }
168
169    pub fn double_to_bucket(&self) -> Bucket<P> {
170        if self.is_zero() {
171            Bucket::ZERO
172        } else {
173            // https://www.hyperelliptic.org/EFD/g1p/auto-shortw-xyzz.html#doubling-mdbl-2008-s-1
174            // U = 2*Y1
175            let u = self.y.double();
176            // V = U^2
177            let v = u.square();
178            // W = U*V
179            let w = u * &v;
180            // S = X1*V
181            let s = self.x * &v;
182            // M = 3*X1^2+a
183            let mut m = self.x.square();
184            m += m.double();
185            if !P::COEFF_A.is_zero() {
186                m += P::COEFF_A;
187            }
188            // X3 = M^2-2*S
189            let x = m.square() - s.double();
190            // Y3 = M*(S-X3)-W*Y1
191            let y = m * (s - x) - w * self.y;
192            Bucket {
193                x,
194                y,
195                // ZZ3 = V
196                zz: v,
197                // ZZZ3 = W
198                zzz: w,
199            }
200        }
201    }
202}
203
204impl<P: SWCurveConfig> Affine<P> {
205    /// Checks if `self` is in the subgroup having order that equaling that of
206    /// `P::ScalarField`.
207    // DISCUSS Maybe these function names are too verbose?
208    pub fn is_in_correct_subgroup_assuming_on_curve(&self) -> bool {
209        P::is_in_correct_subgroup_assuming_on_curve(self)
210    }
211}
212
213impl<P: SWCurveConfig> Zeroize for Affine<P> {
214    // The phantom data does not contain element-specific data
215    // and thus does not need to be zeroized.
216    fn zeroize(&mut self) {
217        self.x.zeroize();
218        self.y.zeroize();
219        self.infinity.zeroize();
220    }
221}
222
223impl<P: SWCurveConfig> Distribution<Affine<P>> for Standard {
224    /// Generates a uniformly random instance of the curve.
225    #[inline]
226    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Affine<P> {
227        loop {
228            let x = P::BaseField::rand(rng);
229            let greatest = rng.gen();
230
231            if let Some(p) = Affine::get_point_from_x_unchecked(x, greatest) {
232                return p.mul_by_cofactor();
233            }
234        }
235    }
236}
237
238impl<P: SWCurveConfig> AffineRepr for Affine<P> {
239    type Config = P;
240    type BaseField = P::BaseField;
241    type ScalarField = P::ScalarField;
242    type Group = Projective<P>;
243
244    const GENERATOR: Self = P::GENERATOR;
245    const ZERO: Self = Self::identity();
246
247    fn xy(&self) -> Option<(Self::BaseField, Self::BaseField)> {
248        (!self.is_zero()).then(|| (self.x, self.y))
249    }
250
251    #[inline]
252    fn generator() -> Self {
253        Self::GENERATOR
254    }
255
256    fn zero() -> Self {
257        Self::ZERO
258    }
259
260    fn is_zero(&self) -> bool {
261        P::ZeroFlag::is_zero(self)
262    }
263
264    fn from_random_bytes(bytes: &[u8]) -> Option<Self> {
265        P::BaseField::from_random_bytes_with_flags::<SWFlags>(bytes).and_then(|(x, flags)| {
266            // if x is valid and is zero and only the infinity flag is set, then parse this
267            // point as infinity. For all other choices, get the original point.
268            if x.is_zero() && flags.is_infinity() {
269                Some(Self::identity())
270            } else if let Some(y_is_positive) = flags.is_positive() {
271                Self::get_point_from_x_unchecked(x, y_is_positive)
272                // Unwrap is safe because it's not zero.
273            } else {
274                None
275            }
276        })
277    }
278
279    fn mul_bigint(&self, by: impl AsRef<[u64]>) -> Self::Group {
280        P::mul_affine(self, by.as_ref())
281    }
282
283    /// Multiplies this element by the cofactor and output the
284    /// resulting projective element.
285    fn mul_by_cofactor_to_group(&self) -> Self::Group {
286        P::mul_affine(self, Self::Config::COFACTOR)
287    }
288
289    /// Performs cofactor clearing.
290    /// The default method is simply to multiply by the cofactor.
291    /// Some curves can implement a more efficient algorithm.
292    fn clear_cofactor(&self) -> Self {
293        P::clear_cofactor(self)
294    }
295}
296
297impl<P: SWCurveConfig> Neg for Affine<P> {
298    type Output = Self;
299
300    /// If `self.is_zero()`, returns `self` (`== Self::zero()`).
301    /// Else, returns `(x, -y)`, where `self = (x, y)`.
302    #[inline]
303    fn neg(mut self) -> Self {
304        self.y.neg_in_place();
305        self
306    }
307}
308
309impl<P: SWCurveConfig, T: Borrow<Self>> Add<T> for Affine<P> {
310    type Output = Projective<P>;
311    fn add(self, other: T) -> Projective<P> {
312        // TODO implement more efficient formulae when z1 = z2 = 1.
313        let mut copy = self.into_group();
314        copy += other.borrow();
315        copy
316    }
317}
318
319impl<P: SWCurveConfig> Add<Projective<P>> for Affine<P> {
320    type Output = Projective<P>;
321    fn add(self, other: Projective<P>) -> Projective<P> {
322        other + self
323    }
324}
325
326impl<'a, P: SWCurveConfig> Add<&'a Projective<P>> for Affine<P> {
327    type Output = Projective<P>;
328    fn add(self, other: &'a Projective<P>) -> Projective<P> {
329        *other + self
330    }
331}
332
333impl<P: SWCurveConfig, T: Borrow<Self>> Sub<T> for Affine<P> {
334    type Output = Projective<P>;
335    fn sub(self, other: T) -> Projective<P> {
336        let mut copy = self.into_group();
337        copy -= other.borrow();
338        copy
339    }
340}
341
342impl<P: SWCurveConfig> Sub<Projective<P>> for Affine<P> {
343    type Output = Projective<P>;
344    fn sub(self, other: Projective<P>) -> Projective<P> {
345        self + (-other)
346    }
347}
348
349impl<'a, P: SWCurveConfig> Sub<&'a Projective<P>> for Affine<P> {
350    type Output = Projective<P>;
351    fn sub(self, other: &'a Projective<P>) -> Projective<P> {
352        self + (-*other)
353    }
354}
355
356impl<P: SWCurveConfig> Default for Affine<P> {
357    #[inline]
358    fn default() -> Self {
359        Self::identity()
360    }
361}
362
363impl<P: SWCurveConfig, T: Borrow<P::ScalarField>> Mul<T> for Affine<P> {
364    type Output = Projective<P>;
365
366    #[inline]
367    fn mul(self, other: T) -> Self::Output {
368        self.mul_bigint(other.borrow().into_bigint())
369    }
370}
371
372// The projective point X, Y, Z is represented in the affine
373// coordinates as X/Z^2, Y/Z^3.
374impl<P: SWCurveConfig> From<Projective<P>> for Affine<P> {
375    #[inline]
376    fn from(p: Projective<P>) -> Self {
377        if p.is_zero() {
378            Self::identity()
379        } else if p.z.is_one() {
380            // If Z is one, the point is already normalized.
381            Self::new_unchecked(p.x, p.y)
382        } else {
383            // Z is nonzero, so it must have an inverse in a field.
384            let zinv = p.z.inverse().unwrap();
385            let zinv_squared = zinv.square();
386
387            // X/Z^2
388            let x = p.x * &zinv_squared;
389
390            // Y/Z^3
391            let y = p.y * &(zinv_squared * &zinv);
392
393            Self::new_unchecked(x, y)
394        }
395    }
396}
397
398impl<P: SWCurveConfig> CanonicalSerialize for Affine<P> {
399    #[inline]
400    fn serialize_with_mode<W: Write>(
401        &self,
402        writer: W,
403        compress: ark_serialize::Compress,
404    ) -> Result<(), SerializationError> {
405        P::serialize_with_mode(self, writer, compress)
406    }
407
408    #[inline]
409    fn serialized_size(&self, compress: Compress) -> usize {
410        P::serialized_size(compress)
411    }
412}
413
414impl<P: SWCurveConfig> Valid for Affine<P> {
415    fn check(&self) -> Result<(), SerializationError> {
416        if self.is_on_curve() && self.is_in_correct_subgroup_assuming_on_curve() {
417            Ok(())
418        } else {
419            Err(SerializationError::InvalidData)
420        }
421    }
422}
423
424impl<P: SWCurveConfig> CanonicalDeserialize for Affine<P> {
425    fn deserialize_with_mode<R: Read>(
426        reader: R,
427        compress: Compress,
428        validate: Validate,
429    ) -> Result<Self, SerializationError> {
430        P::deserialize_with_mode(reader, compress, validate)
431    }
432}
433
434impl<M: SWCurveConfig, ConstraintF: Field> ToConstraintField<ConstraintF> for Affine<M>
435where
436    M::BaseField: ToConstraintField<ConstraintF>,
437{
438    #[inline]
439    fn to_field_elements(&self) -> Option<Vec<ConstraintF>> {
440        let mut x = self.x.to_field_elements()?;
441        let y = self.y.to_field_elements()?;
442        let infinity = self.is_zero().to_field_elements()?;
443        x.extend_from_slice(&y);
444        x.extend_from_slice(&infinity);
445        Some(x)
446    }
447}
ark_ec/models/short_weierstrass/affine.rs

ark_ec/models/short_weierstrass/
affine.rs
