ark_ec/models/twisted_edwards/
mod.rs

1use ark_serialize::{
2    CanonicalDeserialize, CanonicalDeserializeWithFlags, CanonicalSerialize,
3    CanonicalSerializeWithFlags, Compress, SerializationError, Valid, Validate,
4};
5use ark_std::io::{Read, Write};
6
7use crate::{scalar_mul::variable_base::VariableBaseMSM, AffineRepr};
8use num_traits::Zero;
9
10use ark_ff::{fields::Field, AdditiveGroup};
11
12mod affine;
13pub use affine::*;
14
15mod group;
16pub use group::*;
17
18mod serialization_flags;
19pub use serialization_flags::*;
20
21/// Constants and convenience functions that collectively define the [Twisted Edwards model](https://www.hyperelliptic.org/EFD/g1p/auto-twisted.html)
22/// of the curve. In this model, the curve equation is
23/// `a * x² + y² = 1 + d * x² * y²`, for constants `a` and `d`.
24pub trait TECurveConfig: super::CurveConfig {
25    /// Coefficient `a` of the curve equation.
26    const COEFF_A: Self::BaseField;
27    /// Coefficient `d` of the curve equation.
28    const COEFF_D: Self::BaseField;
29    /// Generator of the prime-order subgroup.
30    const GENERATOR: Affine<Self>;
31
32    /// Model parameters for the Montgomery curve that is birationally
33    /// equivalent to this curve.
34    type MontCurveConfig: MontCurveConfig<BaseField = Self::BaseField>;
35
36    /// Helper method for computing `elem * Self::COEFF_A`.
37    ///
38    /// The default implementation should be overridden only if
39    /// the product can be computed faster than standard field multiplication
40    /// (eg: via doubling if `COEFF_A == 2`, or if `COEFF_A.is_zero()`).
41    #[inline(always)]
42    fn mul_by_a(elem: Self::BaseField) -> Self::BaseField {
43        elem * Self::COEFF_A
44    }
45
46    /// Checks that the current point is in the prime order subgroup given
47    /// the point on the curve.
48    fn is_in_correct_subgroup_assuming_on_curve(item: &Affine<Self>) -> bool {
49        Self::mul_affine(item, Self::ScalarField::characteristic()).is_zero()
50    }
51
52    /// Performs cofactor clearing.
53    /// The default method is simply to multiply by the cofactor.
54    /// For some curve families though, it is sufficient to multiply
55    /// by a smaller scalar.
56    fn clear_cofactor(item: &Affine<Self>) -> Affine<Self> {
57        item.mul_by_cofactor()
58    }
59
60    /// Default implementation of group multiplication for projective
61    /// coordinates
62    fn mul_projective(base: &Projective<Self>, scalar: &[u64]) -> Projective<Self> {
63        let mut res = Projective::<Self>::zero();
64        for b in ark_ff::BitIteratorBE::without_leading_zeros(scalar) {
65            res.double_in_place();
66            if b {
67                res += base;
68            }
69        }
70
71        res
72    }
73
74    /// Default implementation of group multiplication for affine
75    /// coordinates
76    fn mul_affine(base: &Affine<Self>, scalar: &[u64]) -> Projective<Self> {
77        let mut res = Projective::<Self>::zero();
78        for b in ark_ff::BitIteratorBE::without_leading_zeros(scalar) {
79            res.double_in_place();
80            if b {
81                res += base
82            }
83        }
84
85        res
86    }
87
88    /// Default implementation for multi scalar multiplication
89    fn msm(
90        bases: &[Affine<Self>],
91        scalars: &[Self::ScalarField],
92    ) -> Result<Projective<Self>, usize> {
93        (bases.len() == scalars.len())
94            .then(|| VariableBaseMSM::msm_unchecked(bases, scalars))
95            .ok_or(bases.len().min(scalars.len()))
96    }
97
98    /// If uncompressed, serializes both x and y coordinates.
99    /// If compressed, serializes y coordinate with a bit to encode whether x is positive.
100    #[inline]
101    fn serialize_with_mode<W: Write>(
102        item: &Affine<Self>,
103        mut writer: W,
104        compress: ark_serialize::Compress,
105    ) -> Result<(), SerializationError> {
106        let flags = TEFlags::from_x_coordinate(item.x);
107        match compress {
108            Compress::Yes => item.y.serialize_with_flags(writer, flags),
109            Compress::No => {
110                item.x.serialize_uncompressed(&mut writer)?;
111                item.y.serialize_uncompressed(&mut writer)
112            },
113        }
114    }
115
116    /// If `validate` is `Yes`, calls `check()` to make sure the element is valid.
117    ///
118    /// Uses `Affine::get_xs_from_y_unchecked()` for the compressed version.
119    fn deserialize_with_mode<R: Read>(
120        mut reader: R,
121        compress: Compress,
122        validate: Validate,
123    ) -> Result<Affine<Self>, SerializationError> {
124        let (x, y) = match compress {
125            Compress::Yes => {
126                let (y, flags): (_, TEFlags) =
127                    CanonicalDeserializeWithFlags::deserialize_with_flags(reader)?;
128                let (x, neg_x) = Affine::<Self>::get_xs_from_y_unchecked(y)
129                    .ok_or(SerializationError::InvalidData)?;
130                if flags.is_negative() {
131                    (neg_x, y)
132                } else {
133                    (x, y)
134                }
135            },
136            Compress::No => {
137                let x: Self::BaseField =
138                    CanonicalDeserialize::deserialize_uncompressed(&mut reader)?;
139                let y: Self::BaseField =
140                    CanonicalDeserialize::deserialize_uncompressed(&mut reader)?;
141                (x, y)
142            },
143        };
144        let point = Affine::<Self>::new_unchecked(x, y);
145        if let Validate::Yes = validate {
146            point.check()?;
147        }
148        Ok(point)
149    }
150
151    #[inline]
152    fn serialized_size(compress: Compress) -> usize {
153        let zero = Self::BaseField::zero();
154        match compress {
155            Compress::Yes => zero.serialized_size_with_flags::<TEFlags>(),
156            Compress::No => zero.uncompressed_size() + zero.uncompressed_size(),
157        }
158    }
159}
160
161/// Constants and convenience functions that collectively define the [Montgomery model](https://www.hyperelliptic.org/EFD/g1p/auto-montgom.html)
162/// of the curve. In this model, the curve equation is
163/// `b * y² = x³ + a * x² + x`, for constants `a` and `b`.
164pub trait MontCurveConfig: super::CurveConfig {
165    /// Coefficient `a` of the curve equation.
166    const COEFF_A: Self::BaseField;
167    /// Coefficient `b` of the curve equation.
168    const COEFF_B: Self::BaseField;
169
170    /// Model parameters for the Twisted Edwards curve that is birationally
171    /// equivalent to this curve.
172    type TECurveConfig: TECurveConfig<BaseField = Self::BaseField>;
173}
174
175//////////////////////////////////////////////////////////////////////////////
ark_ec/models/twisted_edwards/mod.rs

ark_ec/models/twisted_edwards/
mod.rs
