ark_ec/models/twisted_edwards/
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};
15use educe::Educe;
16use num_traits::{One, Zero};
17use zeroize::Zeroize;
18
19use ark_ff::{fields::Field, AdditiveGroup, PrimeField, ToConstraintField, UniformRand};
20
21use super::{Projective, TECurveConfig, TEFlags};
22use crate::AffineRepr;
23
24/// Affine coordinates for a point on a twisted Edwards curve, over the
25/// base field `P::BaseField`.
26#[derive(Educe)]
27#[educe(Copy, Clone, PartialEq, Eq, Hash)]
28#[must_use]
29pub struct Affine<P: TECurveConfig> {
30    /// X coordinate of the point represented as a field element
31    pub x: P::BaseField,
32    /// Y coordinate of the point represented as a field element
33    pub y: P::BaseField,
34}
35
36impl<P: TECurveConfig> Display for Affine<P> {
37    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
38        match self.is_zero() {
39            true => write!(f, "infinity"),
40            false => write!(f, "({}, {})", self.x, self.y),
41        }
42    }
43}
44
45impl<P: TECurveConfig> Debug 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: TECurveConfig> PartialEq<Projective<P>> for Affine<P> {
55    fn eq(&self, other: &Projective<P>) -> bool {
56        self.into_group() == *other
57    }
58}
59
60impl<P: TECurveConfig> Affine<P> {
61    /// Construct a new group element without checking whether the coordinates
62    /// specify a point in the subgroup.
63    pub const fn new_unchecked(x: P::BaseField, y: P::BaseField) -> Self {
64        Self { x, y }
65    }
66
67    /// Construct a new group element in a way while enforcing that points are in
68    /// the prime-order subgroup.
69    pub fn new(x: P::BaseField, y: P::BaseField) -> Self {
70        let p = Self::new_unchecked(x, y);
71        assert!(p.is_on_curve());
72        assert!(p.is_in_correct_subgroup_assuming_on_curve());
73        p
74    }
75
76    /// Construct the identity of the group
77    pub const fn zero() -> Self {
78        Self::new_unchecked(P::BaseField::ZERO, P::BaseField::ONE)
79    }
80
81    /// Is this point the identity?
82    pub fn is_zero(&self) -> bool {
83        self.x.is_zero() && self.y.is_one()
84    }
85
86    /// Attempts to construct an affine point given an y-coordinate. The
87    /// point is not guaranteed to be in the prime order subgroup.
88    ///
89    /// If and only if `greatest` is set will the lexicographically
90    /// largest x-coordinate be selected.
91    ///
92    /// a * X^2 + Y^2 = 1 + d * X^2 * Y^2
93    /// a * X^2 - d * X^2 * Y^2 = 1 - Y^2
94    /// X^2 * (a - d * Y^2) = 1 - Y^2
95    /// X^2 = (1 - Y^2) / (a - d * Y^2)
96    #[allow(dead_code)]
97    pub fn get_point_from_y_unchecked(y: P::BaseField, greatest: bool) -> Option<Self> {
98        Self::get_xs_from_y_unchecked(y).map(|(x, neg_x)| {
99            if greatest {
100                Self::new_unchecked(neg_x, y)
101            } else {
102                Self::new_unchecked(x, y)
103            }
104        })
105    }
106
107    /// Attempts to recover the x-coordinate given an y-coordinate. The
108    /// resulting point is not guaranteed to be in the prime order subgroup.
109    ///
110    /// If and only if `greatest` is set will the lexicographically
111    /// largest x-coordinate be selected.
112    ///
113    /// a * X^2 + Y^2 = 1 + d * X^2 * Y^2
114    /// a * X^2 - d * X^2 * Y^2 = 1 - Y^2
115    /// X^2 * (a - d * Y^2) = 1 - Y^2
116    /// X^2 = (1 - Y^2) / (a - d * Y^2)
117    #[allow(dead_code)]
118    pub fn get_xs_from_y_unchecked(y: P::BaseField) -> Option<(P::BaseField, P::BaseField)> {
119        let y2 = y.square();
120
121        let numerator = P::BaseField::one() - y2;
122        let denominator = P::COEFF_A - (y2 * P::COEFF_D);
123
124        denominator
125            .inverse()
126            .map(|denom| denom * &numerator)
127            .and_then(|x2| x2.sqrt())
128            .map(|x| {
129                let neg_x = -x;
130                if x <= neg_x {
131                    (x, neg_x)
132                } else {
133                    (neg_x, x)
134                }
135            })
136    }
137
138    /// Checks that the current point is on the elliptic curve.
139    pub fn is_on_curve(&self) -> bool {
140        let x2 = self.x.square();
141        let y2 = self.y.square();
142
143        let lhs = y2 + P::mul_by_a(x2);
144        let rhs = P::BaseField::one() + &(P::COEFF_D * &(x2 * &y2));
145
146        lhs == rhs
147    }
148}
149
150impl<P: TECurveConfig> Affine<P> {
151    /// Checks if `self` is in the subgroup having order equaling that of
152    /// `P::ScalarField` given it is on the curve.
153    pub fn is_in_correct_subgroup_assuming_on_curve(&self) -> bool {
154        P::is_in_correct_subgroup_assuming_on_curve(self)
155    }
156}
157
158impl<P: TECurveConfig> AffineRepr for Affine<P> {
159    type Config = P;
160    type BaseField = P::BaseField;
161    type ScalarField = P::ScalarField;
162    type Group = Projective<P>;
163
164    fn xy(&self) -> Option<(Self::BaseField, Self::BaseField)> {
165        (!self.is_zero()).then(|| (self.x, self.y))
166    }
167
168    fn generator() -> Self {
169        P::GENERATOR
170    }
171
172    fn zero() -> Self {
173        Self::new_unchecked(P::BaseField::ZERO, P::BaseField::ONE)
174    }
175
176    fn from_random_bytes(bytes: &[u8]) -> Option<Self> {
177        P::BaseField::from_random_bytes_with_flags::<TEFlags>(bytes)
178            .and_then(|(y, flags)| Self::get_point_from_y_unchecked(y, flags.is_negative()))
179    }
180
181    fn mul_bigint(&self, by: impl AsRef<[u64]>) -> Self::Group {
182        P::mul_affine(self, by.as_ref())
183    }
184
185    /// Multiplies this element by the cofactor and output the
186    /// resulting projective element.
187    #[must_use]
188    fn mul_by_cofactor_to_group(&self) -> Self::Group {
189        P::mul_affine(self, Self::Config::COFACTOR)
190    }
191
192    /// Performs cofactor clearing.
193    /// The default method is simply to multiply by the cofactor.
194    /// Some curves can implement a more efficient algorithm.
195    fn clear_cofactor(&self) -> Self {
196        P::clear_cofactor(self)
197    }
198}
199
200impl<P: TECurveConfig> Zeroize for Affine<P> {
201    // The phantom data does not contain element-specific data
202    // and thus does not need to be zeroized.
203    fn zeroize(&mut self) {
204        self.x.zeroize();
205        self.y.zeroize();
206    }
207}
208
209impl<P: TECurveConfig> Neg for Affine<P> {
210    type Output = Self;
211
212    fn neg(self) -> Self {
213        Self::new_unchecked(-self.x, self.y)
214    }
215}
216
217impl<P: TECurveConfig, T: Borrow<Self>> Add<T> for Affine<P> {
218    type Output = Projective<P>;
219    fn add(self, other: T) -> Self::Output {
220        let mut copy = self.into_group();
221        copy += other.borrow();
222        copy
223    }
224}
225
226impl<P: TECurveConfig> Add<Projective<P>> for Affine<P> {
227    type Output = Projective<P>;
228    fn add(self, other: Projective<P>) -> Projective<P> {
229        other + self
230    }
231}
232
233impl<'a, P: TECurveConfig> Add<&'a Projective<P>> for Affine<P> {
234    type Output = Projective<P>;
235    fn add(self, other: &'a Projective<P>) -> Projective<P> {
236        *other + self
237    }
238}
239
240impl<P: TECurveConfig, T: Borrow<Self>> Sub<T> for Affine<P> {
241    type Output = Projective<P>;
242    fn sub(self, other: T) -> Self::Output {
243        let mut copy = self.into_group();
244        copy -= other.borrow();
245        copy
246    }
247}
248
249impl<P: TECurveConfig> Sub<Projective<P>> for Affine<P> {
250    type Output = Projective<P>;
251    fn sub(self, other: Projective<P>) -> Projective<P> {
252        self + (-other)
253    }
254}
255
256impl<'a, P: TECurveConfig> Sub<&'a Projective<P>> for Affine<P> {
257    type Output = Projective<P>;
258    fn sub(self, other: &'a Projective<P>) -> Projective<P> {
259        self + (-*other)
260    }
261}
262
263impl<P: TECurveConfig> Default for Affine<P> {
264    #[inline]
265    fn default() -> Self {
266        Self::zero()
267    }
268}
269
270impl<P: TECurveConfig> Distribution<Affine<P>> for Standard {
271    /// Generates a uniformly random instance of the curve.
272    #[inline]
273    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Affine<P> {
274        loop {
275            let y = P::BaseField::rand(rng);
276            let greatest = rng.gen();
277
278            if let Some(p) = Affine::get_point_from_y_unchecked(y, greatest) {
279                return p.mul_by_cofactor();
280            }
281        }
282    }
283}
284
285impl<P: TECurveConfig, T: Borrow<P::ScalarField>> Mul<T> for Affine<P> {
286    type Output = Projective<P>;
287
288    #[inline]
289    fn mul(self, other: T) -> Self::Output {
290        self.mul_bigint(other.borrow().into_bigint())
291    }
292}
293
294// The projective point X, Y, T, Z is represented in the affine
295// coordinates as X/Z, Y/Z.
296impl<P: TECurveConfig> From<Projective<P>> for Affine<P> {
297    fn from(p: Projective<P>) -> Affine<P> {
298        if p.is_zero() {
299            Affine::zero()
300        } else if p.z.is_one() {
301            // If Z is one, the point is already normalized.
302            Affine::new_unchecked(p.x, p.y)
303        } else {
304            // Z is nonzero, so it must have an inverse in a field.
305            let z_inv = p.z.inverse().unwrap();
306            let x = p.x * &z_inv;
307            let y = p.y * &z_inv;
308            Affine::new_unchecked(x, y)
309        }
310    }
311}
312impl<P: TECurveConfig> CanonicalSerialize for Affine<P> {
313    #[inline]
314    fn serialize_with_mode<W: Write>(
315        &self,
316        writer: W,
317        compress: ark_serialize::Compress,
318    ) -> Result<(), SerializationError> {
319        P::serialize_with_mode(self, writer, compress)
320    }
321
322    #[inline]
323    fn serialized_size(&self, compress: Compress) -> usize {
324        P::serialized_size(compress)
325    }
326}
327
328impl<P: TECurveConfig> Valid for Affine<P> {
329    fn check(&self) -> Result<(), SerializationError> {
330        if self.is_on_curve() && self.is_in_correct_subgroup_assuming_on_curve() {
331            Ok(())
332        } else {
333            Err(SerializationError::InvalidData)
334        }
335    }
336}
337
338impl<P: TECurveConfig> CanonicalDeserialize for Affine<P> {
339    fn deserialize_with_mode<R: Read>(
340        reader: R,
341        compress: Compress,
342        validate: Validate,
343    ) -> Result<Self, SerializationError> {
344        P::deserialize_with_mode(reader, compress, validate)
345    }
346}
347
348impl<M: TECurveConfig, ConstraintF: Field> ToConstraintField<ConstraintF> for Affine<M>
349where
350    M::BaseField: ToConstraintField<ConstraintF>,
351{
352    #[inline]
353    fn to_field_elements(&self) -> Option<Vec<ConstraintF>> {
354        let mut x_fe = self.x.to_field_elements()?;
355        let y_fe = self.y.to_field_elements()?;
356        x_fe.extend_from_slice(&y_fe);
357        Some(x_fe)
358    }
359}
ark_ec/models/twisted_edwards/affine.rs

ark_ec/models/twisted_edwards/
affine.rs
