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::{Projective, SWCurveConfig, SWFlags};
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 infinity: bool,
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.infinity {
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.infinity {
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: false,
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: false,
88        }
89    }
90
91    pub const fn identity() -> Self {
92        Self {
93            x: P::BaseField::ZERO,
94            y: P::BaseField::ZERO,
95            infinity: true,
96        }
97    }
98
99    /// Attempts to construct an affine point given an x-coordinate. The
100    /// point is not guaranteed to be in the prime order subgroup.
101    ///
102    /// If and only if `greatest` is set will the lexicographically
103    /// largest y-coordinate be selected.
104    #[allow(dead_code)]
105    pub fn get_point_from_x_unchecked(x: P::BaseField, greatest: bool) -> Option<Self> {
106        Self::get_ys_from_x_unchecked(x).map(|(smaller, larger)| {
107            if greatest {
108                Self::new_unchecked(x, larger)
109            } else {
110                Self::new_unchecked(x, smaller)
111            }
112        })
113    }
114
115    /// Returns the two possible y-coordinates corresponding to the given x-coordinate.
116    /// The corresponding points are not guaranteed to be in the prime-order subgroup,
117    /// but are guaranteed to be on the curve. That is, this method returns `None`
118    /// if the x-coordinate corresponds to a non-curve point.
119    ///
120    /// The results are sorted by lexicographical order.
121    /// This means that, if `P::BaseField: PrimeField`, the results are sorted as integers.
122    pub fn get_ys_from_x_unchecked(x: P::BaseField) -> Option<(P::BaseField, P::BaseField)> {
123        // Compute the curve equation x^3 + Ax + B.
124        // Since Rust does not optimise away additions with zero, we explicitly check
125        // for that case here, and avoid multiplication by `a` if possible.
126        let mut x3_plus_ax_plus_b = P::add_b(x.square() * x);
127        if !P::COEFF_A.is_zero() {
128            x3_plus_ax_plus_b += P::mul_by_a(x)
129        };
130        let y = x3_plus_ax_plus_b.sqrt()?;
131        let neg_y = -y;
132        match y < neg_y {
133            true => Some((y, neg_y)),
134            false => Some((neg_y, y)),
135        }
136    }
137
138    /// Checks if `self` is a valid point on the curve.
139    pub fn is_on_curve(&self) -> bool {
140        if !self.infinity {
141            // Rust does not optimise away addition with zero
142            let mut x3b = P::add_b(self.x.square() * self.x);
143            if !P::COEFF_A.is_zero() {
144                x3b += P::mul_by_a(self.x);
145            };
146            self.y.square() == x3b
147        } else {
148            true
149        }
150    }
151
152    pub fn to_flags(&self) -> SWFlags {
153        if self.infinity {
154            SWFlags::PointAtInfinity
155        } else if self.y <= -self.y {
156            SWFlags::YIsPositive
157        } else {
158            SWFlags::YIsNegative
159        }
160    }
161}
162
163impl<P: SWCurveConfig> Affine<P> {
164    /// Checks if `self` is in the subgroup having order that equaling that of
165    /// `P::ScalarField`.
166    // DISCUSS Maybe these function names are too verbose?
167    pub fn is_in_correct_subgroup_assuming_on_curve(&self) -> bool {
168        P::is_in_correct_subgroup_assuming_on_curve(self)
169    }
170}
171
172impl<P: SWCurveConfig> Zeroize for Affine<P> {
173    // The phantom data does not contain element-specific data
174    // and thus does not need to be zeroized.
175    fn zeroize(&mut self) {
176        self.x.zeroize();
177        self.y.zeroize();
178        self.infinity.zeroize();
179    }
180}
181
182impl<P: SWCurveConfig> Distribution<Affine<P>> for Standard {
183    /// Generates a uniformly random instance of the curve.
184    #[inline]
185    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Affine<P> {
186        loop {
187            let x = P::BaseField::rand(rng);
188            let greatest = rng.gen();
189
190            if let Some(p) = Affine::get_point_from_x_unchecked(x, greatest) {
191                return p.mul_by_cofactor();
192            }
193        }
194    }
195}
196
197impl<P: SWCurveConfig> AffineRepr for Affine<P> {
198    type Config = P;
199    type BaseField = P::BaseField;
200    type ScalarField = P::ScalarField;
201    type Group = Projective<P>;
202
203    fn xy(&self) -> Option<(Self::BaseField, Self::BaseField)> {
204        (!self.infinity).then(|| (self.x, self.y))
205    }
206
207    #[inline]
208    fn generator() -> Self {
209        P::GENERATOR
210    }
211
212    fn zero() -> Self {
213        Self {
214            x: P::BaseField::ZERO,
215            y: P::BaseField::ZERO,
216            infinity: true,
217        }
218    }
219
220    fn from_random_bytes(bytes: &[u8]) -> Option<Self> {
221        P::BaseField::from_random_bytes_with_flags::<SWFlags>(bytes).and_then(|(x, flags)| {
222            // if x is valid and is zero and only the infinity flag is set, then parse this
223            // point as infinity. For all other choices, get the original point.
224            if x.is_zero() && flags.is_infinity() {
225                Some(Self::identity())
226            } else if let Some(y_is_positive) = flags.is_positive() {
227                Self::get_point_from_x_unchecked(x, y_is_positive)
228                // Unwrap is safe because it's not zero.
229            } else {
230                None
231            }
232        })
233    }
234
235    fn mul_bigint(&self, by: impl AsRef<[u64]>) -> Self::Group {
236        P::mul_affine(self, by.as_ref())
237    }
238
239    /// Multiplies this element by the cofactor and output the
240    /// resulting projective element.
241    #[must_use]
242    fn mul_by_cofactor_to_group(&self) -> Self::Group {
243        P::mul_affine(self, Self::Config::COFACTOR)
244    }
245
246    /// Performs cofactor clearing.
247    /// The default method is simply to multiply by the cofactor.
248    /// Some curves can implement a more efficient algorithm.
249    fn clear_cofactor(&self) -> Self {
250        P::clear_cofactor(self)
251    }
252}
253
254impl<P: SWCurveConfig> Neg for Affine<P> {
255    type Output = Self;
256
257    /// If `self.is_zero()`, returns `self` (`== Self::zero()`).
258    /// Else, returns `(x, -y)`, where `self = (x, y)`.
259    #[inline]
260    fn neg(mut self) -> Self {
261        self.y.neg_in_place();
262        self
263    }
264}
265
266impl<P: SWCurveConfig, T: Borrow<Self>> Add<T> for Affine<P> {
267    type Output = Projective<P>;
268    fn add(self, other: T) -> Projective<P> {
269        // TODO implement more efficient formulae when z1 = z2 = 1.
270        let mut copy = self.into_group();
271        copy += other.borrow();
272        copy
273    }
274}
275
276impl<P: SWCurveConfig> Add<Projective<P>> for Affine<P> {
277    type Output = Projective<P>;
278    fn add(self, other: Projective<P>) -> Projective<P> {
279        other + self
280    }
281}
282
283impl<'a, P: SWCurveConfig> Add<&'a Projective<P>> for Affine<P> {
284    type Output = Projective<P>;
285    fn add(self, other: &'a Projective<P>) -> Projective<P> {
286        *other + self
287    }
288}
289
290impl<P: SWCurveConfig, T: Borrow<Self>> Sub<T> for Affine<P> {
291    type Output = Projective<P>;
292    fn sub(self, other: T) -> Projective<P> {
293        let mut copy = self.into_group();
294        copy -= other.borrow();
295        copy
296    }
297}
298
299impl<P: SWCurveConfig> Sub<Projective<P>> for Affine<P> {
300    type Output = Projective<P>;
301    fn sub(self, other: Projective<P>) -> Projective<P> {
302        self + (-other)
303    }
304}
305
306impl<'a, P: SWCurveConfig> Sub<&'a Projective<P>> for Affine<P> {
307    type Output = Projective<P>;
308    fn sub(self, other: &'a Projective<P>) -> Projective<P> {
309        self + (-*other)
310    }
311}
312
313impl<P: SWCurveConfig> Default for Affine<P> {
314    #[inline]
315    fn default() -> Self {
316        Self::identity()
317    }
318}
319
320impl<P: SWCurveConfig, T: Borrow<P::ScalarField>> Mul<T> for Affine<P> {
321    type Output = Projective<P>;
322
323    #[inline]
324    fn mul(self, other: T) -> Self::Output {
325        self.mul_bigint(other.borrow().into_bigint())
326    }
327}
328
329// The projective point X, Y, Z is represented in the affine
330// coordinates as X/Z^2, Y/Z^3.
331impl<P: SWCurveConfig> From<Projective<P>> for Affine<P> {
332    #[inline]
333    fn from(p: Projective<P>) -> Affine<P> {
334        if p.is_zero() {
335            Affine::identity()
336        } else if p.z.is_one() {
337            // If Z is one, the point is already normalized.
338            Affine::new_unchecked(p.x, p.y)
339        } else {
340            // Z is nonzero, so it must have an inverse in a field.
341            let zinv = p.z.inverse().unwrap();
342            let zinv_squared = zinv.square();
343
344            // X/Z^2
345            let x = p.x * &zinv_squared;
346
347            // Y/Z^3
348            let y = p.y * &(zinv_squared * &zinv);
349
350            Affine::new_unchecked(x, y)
351        }
352    }
353}
354
355impl<P: SWCurveConfig> CanonicalSerialize for Affine<P> {
356    #[inline]
357    fn serialize_with_mode<W: Write>(
358        &self,
359        writer: W,
360        compress: ark_serialize::Compress,
361    ) -> Result<(), SerializationError> {
362        P::serialize_with_mode(self, writer, compress)
363    }
364
365    #[inline]
366    fn serialized_size(&self, compress: Compress) -> usize {
367        P::serialized_size(compress)
368    }
369}
370
371impl<P: SWCurveConfig> Valid for Affine<P> {
372    fn check(&self) -> Result<(), SerializationError> {
373        if self.is_on_curve() && self.is_in_correct_subgroup_assuming_on_curve() {
374            Ok(())
375        } else {
376            Err(SerializationError::InvalidData)
377        }
378    }
379}
380
381impl<P: SWCurveConfig> CanonicalDeserialize for Affine<P> {
382    fn deserialize_with_mode<R: Read>(
383        reader: R,
384        compress: Compress,
385        validate: Validate,
386    ) -> Result<Self, SerializationError> {
387        P::deserialize_with_mode(reader, compress, validate)
388    }
389}
390
391impl<M: SWCurveConfig, ConstraintF: Field> ToConstraintField<ConstraintF> for Affine<M>
392where
393    M::BaseField: ToConstraintField<ConstraintF>,
394{
395    #[inline]
396    fn to_field_elements(&self) -> Option<Vec<ConstraintF>> {
397        let mut x = self.x.to_field_elements()?;
398        let y = self.y.to_field_elements()?;
399        let infinity = self.infinity.to_field_elements()?;
400        x.extend_from_slice(&y);
401        x.extend_from_slice(&infinity);
402        Some(x)
403    }
404}
ark_ec/models/short_weierstrass/affine.rs

ark_ec/models/short_weierstrass/
affine.rs
