ark_ec/models/double_odd/
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::Vec,
14};
15
16use ark_ff::{fields::Field, AdditiveGroup, One, PrimeField, ToConstraintField, UniformRand};
17
18use educe::Educe;
19use zeroize::Zeroize;
20
21use super::{DOCurveConfig, Projective};
22use crate::{AffineRepr, CurveGroup};
23
24/// Affine coordinates for a point on an elliptic curve in double-odd
25/// form, over the base field `P::BaseField`.
26///
27/// Instead of using the (x,y)-coordinate system of the original double-odd paper (<https://doubleodd.group/doubleodd.pdf>),
28/// the (e,u)-coordinate system from the follow-up paper (<https://doubleodd.group/doubleodd-jq.pdf>) was implemented.
29/// This coordinate system allows for the new curve equation `e**2 = (a-4*b)*u**4 - 2a*u**2 + 1`,
30/// which is of the Jacobi quartic form, allowing for faster addition/doubling formulae.
31/// Additionally, these coordinates allow for more efficient en/decoding.
32/// - In general: `P = (e,u) = (u**2*(x - b/x),x/y)`
33/// - `P` and `P+N` are representants of the same group element.
34/// - `P+N = (-e,-u)`, `-P = (e,-u)`, and `-P+N = (-e,u)`
35/// - The group neutral is represented by the point at infinity `O = (1,0)` and `N = O+N = (-1,0)`
36#[derive(Educe)]
37#[educe(Copy, Clone, Hash)]
38#[must_use]
39pub struct Affine<P: DOCurveConfig> {
40    #[doc(hidden)]
41    pub e: P::BaseField,
42    #[doc(hidden)]
43    pub u: P::BaseField,
44}
45
46impl<P: DOCurveConfig> Eq for Affine<P> {}
47impl<P: DOCurveConfig> PartialEq for Affine<P> {
48    fn eq(&self, other: &Self) -> bool {
49        if self.is_zero() {
50            return other.is_zero();
51        }
52        if other.is_zero() {
53            return false;
54        }
55        (self.e == other.e && self.u == other.u) || (self.e == -other.e && self.u == -other.u)
56    }
57}
58
59impl<P: DOCurveConfig> PartialEq<Projective<P>> for Affine<P> {
60    fn eq(&self, other: &Projective<P>) -> bool {
61        self.into_group() == *other
62    }
63}
64
65impl<P: DOCurveConfig> Display for Affine<P> {
66    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
67        write!(f, "({}, {})", self.e, self.u)
68    }
69}
70
71impl<P: DOCurveConfig> Debug for Affine<P> {
72    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
73        write!(f, "({}, {})", self.e, self.u)
74    }
75}
76
77impl<P: DOCurveConfig> Affine<P> {
78    pub fn new(e: P::BaseField, u: P::BaseField) -> Self {
79        let point = Self { e, u };
80        assert!(point.is_on_curve());
81        point
82    }
83
84    pub const fn new_unchecked(e: P::BaseField, u: P::BaseField) -> Self {
85        Self { e, u }
86    }
87
88    /// Returns one of the representants for the identity, namely the point-at-infinity `(1,0)`.
89    ///
90    /// The other representant `N=(-1,0)` of the identity could also be returned, but the
91    /// implementation of formulas only requires one representant.
92    pub const fn identity() -> Self {
93        Self {
94            e: P::BaseField::ONE,
95            u: P::BaseField::ZERO,
96        }
97    }
98
99    #[allow(dead_code)]
100    pub fn get_point_from_u_unchecked(u: P::BaseField, greatest: bool) -> Option<Self> {
101        Self::get_es_from_u_unchecked(u).map(|(smaller, larger)| {
102            if greatest {
103                Self::new_unchecked(larger, u)
104            } else {
105                Self::new_unchecked(smaller, u)
106            }
107        })
108    }
109
110    pub fn get_e_from_u(u: P::BaseField) -> Option<P::BaseField> {
111        // Compute e from the curve equation `e**2 = (a-4*b)*u**4 - 2a*u**2 + 1'
112        (P::get_c() * u.square().square() - (P::COEFF_A * u.square()).double() + P::BaseField::ONE)
113            .sqrt()
114    }
115
116    pub fn get_es_from_u_unchecked(u: P::BaseField) -> Option<(P::BaseField, P::BaseField)> {
117        let e = Self::get_e_from_u(u)?;
118        let neg_e = -e;
119        match e < neg_e {
120            true => Some((e, neg_e)),
121            false => Some((neg_e, e)),
122        }
123    }
124
125    /// Checks if `self` is a valid point on the curve,
126    /// using the curve equation `e**2 = (a-4*b)*u**4 - 2a*u**2 + 1`
127    pub fn is_on_curve(&self) -> bool {
128        let e_squared = P::get_c() * self.u.square().square()
129            - (P::COEFF_A * self.u.square()).double()
130            + P::BaseField::ONE;
131        self.e.square() == e_squared
132    }
133}
134
135impl<P: DOCurveConfig> Zeroize for Affine<P> {
136    fn zeroize(&mut self) {
137        self.e.zeroize();
138        self.u.zeroize();
139    }
140}
141
142impl<P: DOCurveConfig> Distribution<Affine<P>> for Standard {
143    /// Generates a uniformly random point in the prime-order subgroup.
144    #[inline]
145    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Affine<P> {
146        loop {
147            let u = P::BaseField::rand(rng);
148            let greatest = rng.gen();
149
150            if let Some(p) = Affine::get_point_from_u_unchecked(u, greatest) {
151                return p;
152            }
153        }
154    }
155}
156
157impl<P: DOCurveConfig> AffineRepr for Affine<P> {
158    type Config = P;
159    type BaseField = P::BaseField;
160    type ScalarField = P::ScalarField;
161    type Group = Projective<P>;
162
163    const GENERATOR: Self = P::GENERATOR;
164    const ZERO: Self = Self::identity();
165
166    fn xy(&self) -> Option<(Self::BaseField, Self::BaseField)> {
167        Some((self.e, self.u))
168    }
169
170    #[inline]
171    fn generator() -> Self {
172        Self::GENERATOR
173    }
174
175    fn zero() -> Self {
176        Self::ZERO
177    }
178
179    // Zero has two representants: 'O = (1,0)`, and `O+N = (-1,0)`.
180    // These are the only two points with u=0, and is_zero assumes the point is correct,
181    // so e doesn't need to be checked.
182    #[inline]
183    fn is_zero(&self) -> bool {
184        self.u == P::BaseField::ZERO
185    }
186
187    fn from_random_bytes(bytes: &[u8]) -> Option<Self> {
188        P::BaseField::from_random_bytes(bytes)
189            .and_then(|u| Self::get_point_from_u_unchecked(u, true))
190    }
191
192    fn mul_bigint(&self, by: impl AsRef<[u64]>) -> Self::Group {
193        P::mul_affine(self, by.as_ref())
194    }
195
196    /// Multiplies this element by the cofactor and output the
197    /// resulting projective element.
198    fn mul_by_cofactor_to_group(&self) -> Self::Group {
199        P::mul_affine(self, Self::Config::COFACTOR)
200    }
201
202    /// Performs cofactor clearing.
203    /// The default method is simply to multiply by the cofactor.
204    /// Some curves can implement a more efficient algorithm.
205    fn clear_cofactor(&self) -> Self {
206        P::mul_affine(self, Self::Config::COFACTOR).into_affine()
207    }
208}
209
210impl<P: DOCurveConfig> Neg for Affine<P> {
211    type Output = Self;
212
213    #[inline]
214    fn neg(mut self) -> Self {
215        self.u.neg_in_place();
216        self
217    }
218}
219
220impl<P: DOCurveConfig, T: Borrow<Self>> Add<T> for Affine<P> {
221    type Output = Projective<P>;
222    /// Using Algorithm 3 from <https://doubleodd.group/doubleodd-jq.pdf>,
223    /// simplified because both points are affine
224    /// (n2 = 1, n5 = T1 + T2).
225    fn add(self, other: T) -> Projective<P> {
226        let mut copy = self.into_group();
227        let other = other.borrow();
228        let othert = other.u.square();
229        let n1 = copy.e * other.e;
230        let n3 = copy.u * other.u;
231        let n4 = copy.t * othert;
232
233        let n5 = othert + copy.t;
234        let n6 = (copy.e + copy.u) * (other.e + other.u) - n1 - n3;
235        let cn4 = P::get_c() * n4;
236        let n7 = P::BaseField::ONE - cn4;
237
238        let n3d = n3.double();
239
240        copy.e = (P::BaseField::ONE + cn4) * (n1 - P::COEFF_A * n3d) + P::get_c() * n3d * n5;
241        copy.z = n7.square();
242        copy.t = n6.square();
243        copy.u = n7 * n6;
244
245        copy
246    }
247}
248
249impl<P: DOCurveConfig> Add<Projective<P>> for Affine<P> {
250    type Output = Projective<P>;
251    fn add(self, other: Projective<P>) -> Projective<P> {
252        other + self
253    }
254}
255
256impl<'a, P: DOCurveConfig> Add<&'a Projective<P>> for Affine<P> {
257    type Output = Projective<P>;
258    fn add(self, other: &'a Projective<P>) -> Projective<P> {
259        *other + self
260    }
261}
262
263impl<P: DOCurveConfig, T: Borrow<Self>> Sub<T> for Affine<P> {
264    type Output = Projective<P>;
265    fn sub(self, other: T) -> Projective<P> {
266        let mut copy = self.into_group();
267        copy -= other.borrow();
268        copy
269    }
270}
271
272impl<P: DOCurveConfig> Sub<Projective<P>> for Affine<P> {
273    type Output = Projective<P>;
274    fn sub(self, other: Projective<P>) -> Projective<P> {
275        self + (-other)
276    }
277}
278
279impl<'a, P: DOCurveConfig> Sub<&'a Projective<P>> for Affine<P> {
280    type Output = Projective<P>;
281    fn sub(self, other: &'a Projective<P>) -> Projective<P> {
282        self + (-*other)
283    }
284}
285
286impl<P: DOCurveConfig> Default for Affine<P> {
287    #[inline]
288    fn default() -> Self {
289        Self::identity()
290    }
291}
292
293impl<P: DOCurveConfig, T: Borrow<P::ScalarField>> Mul<T> for Affine<P> {
294    type Output = Projective<P>;
295
296    #[inline]
297    fn mul(self, other: T) -> Self::Output {
298        self.mul_bigint(other.borrow().into_bigint())
299    }
300}
301
302// The projective point E, Z, U, T is represented in the affine
303// coordinates as (e, u) by E/Z, U/Z
304impl<P: DOCurveConfig> From<Projective<P>> for Affine<P> {
305    #[inline]
306    fn from(p: Projective<P>) -> Self {
307        use ark_std::Zero;
308
309        if p.is_zero() {
310            Self::identity()
311        } else if p.z.is_one() {
312            Self::new_unchecked(p.e, p.u)
313        } else {
314            let z_i = p.z.inverse().unwrap();
315
316            let u = p.u * &z_i;
317            let e = p.e * &z_i;
318
319            Self::new_unchecked(e, u)
320        }
321    }
322}
323
324impl<P: DOCurveConfig> CanonicalSerialize for Affine<P> {
325    #[inline]
326    fn serialize_with_mode<W: Write>(
327        &self,
328        writer: W,
329        compress: ark_serialize::Compress,
330    ) -> Result<(), SerializationError> {
331        P::serialize_with_mode(self, writer, compress)
332    }
333
334    #[inline]
335    fn serialized_size(&self, compress: Compress) -> usize {
336        P::serialized_size(compress)
337    }
338}
339
340impl<P: DOCurveConfig> Valid for Affine<P> {
341    fn check(&self) -> Result<(), SerializationError> {
342        if self.is_on_curve() {
343            Ok(())
344        } else {
345            Err(SerializationError::InvalidData)
346        }
347    }
348}
349
350impl<P: DOCurveConfig> CanonicalDeserialize for Affine<P> {
351    fn deserialize_with_mode<R: Read>(
352        reader: R,
353        compress: Compress,
354        validate: Validate,
355    ) -> Result<Self, SerializationError> {
356        P::deserialize_with_mode(reader, compress, validate)
357    }
358}
359
360impl<M: DOCurveConfig, ConstraintF: Field> ToConstraintField<ConstraintF> for Affine<M>
361where
362    M::BaseField: ToConstraintField<ConstraintF>,
363{
364    #[inline]
365    fn to_field_elements(&self) -> Option<Vec<ConstraintF>> {
366        let mut e = self.e.to_field_elements()?;
367        let u = self.u.to_field_elements()?;
368        e.extend_from_slice(&u);
369        Some(e)
370    }
371}
ark_ec/models/double_odd/affine.rs

ark_ec/models/double_odd/
affine.rs
