ark_ec/models/short_weierstrass/
mod.rs

1use ark_serialize::{
2    CanonicalDeserialize, CanonicalDeserializeWithFlags, CanonicalSerialize,
3    CanonicalSerializeWithFlags, Compress, SerializationError, Valid, Validate,
4};
5use ark_std::{
6    hash::Hash,
7    io::{Read, Write},
8};
9
10use ark_ff::{fields::Field, AdditiveGroup};
11
12use crate::{
13    scalar_mul::{double_and_add, double_and_add_affine, variable_base::VariableBaseMSM},
14    AffineRepr,
15};
16use num_traits::Zero;
17
18mod affine;
19pub use affine::*;
20
21mod group;
22pub use group::*;
23
24mod bucket;
25pub use bucket::Bucket;
26
27mod serialization_flags;
28pub use serialization_flags::*;
29
30/// Constants and convenience functions that collectively define the [Short Weierstrass model](https://www.hyperelliptic.org/EFD/g1p/auto-shortw.html)
31/// of the curve.
32///
33/// In this model, the curve equation is `y² = x³ + a * x + b`, for constants `a` and `b`.
34pub trait SWCurveConfig: super::CurveConfig {
35    /// Coefficient `a` of the curve equation.
36    const COEFF_A: Self::BaseField;
37    /// Coefficient `b` of the curve equation.
38    const COEFF_B: Self::BaseField;
39    /// Generator of the prime-order subgroup.
40    const GENERATOR: Affine<Self>;
41
42    /// A type that is stored in `Affine<Self>` to indicate whether the point is at infinity.
43    type ZeroFlag: ZeroFlag<Self>;
44
45    /// Helper method for computing `elem * Self::COEFF_A`.
46    ///
47    /// The default implementation should be overridden only if
48    /// the product can be computed faster than standard field multiplication
49    /// (eg: via doubling if `COEFF_A == 2`, or if `COEFF_A.is_zero()`).
50    #[inline(always)]
51    fn mul_by_a(elem: Self::BaseField) -> Self::BaseField {
52        if Self::COEFF_A.is_zero() {
53            Self::BaseField::ZERO
54        } else {
55            elem * Self::COEFF_A
56        }
57    }
58
59    /// Helper method for computing `elem + Self::COEFF_B`.
60    ///
61    /// The default implementation should be overridden only if
62    /// the sum can be computed faster than standard field addition (eg: via
63    /// doubling).
64    #[inline(always)]
65    fn add_b(elem: Self::BaseField) -> Self::BaseField {
66        if Self::COEFF_B.is_zero() {
67            elem
68        } else {
69            elem + &Self::COEFF_B
70        }
71    }
72
73    /// Check if the provided curve point is in the prime-order subgroup.
74    ///
75    /// The default implementation multiplies `item` by the order `r` of the
76    /// prime-order subgroup, and checks if the result is zero. If the
77    /// curve's cofactor is one, this check automatically returns true.
78    /// Implementors can choose to override this default impl
79    /// if the given curve has faster methods
80    /// for performing this check (for example, via leveraging curve
81    /// isomorphisms).
82    fn is_in_correct_subgroup_assuming_on_curve(item: &Affine<Self>) -> bool {
83        if Self::cofactor_is_one() {
84            true
85        } else {
86            // Directly use `double_and_add_affine` to avoid incorrect zero results from
87            // custom `mul_affine` implementations that reduce scalars modulo the group order.
88            double_and_add_affine(item, Self::ScalarField::characteristic()).is_zero()
89        }
90    }
91
92    /// Performs cofactor clearing.
93    /// The default method is simply to multiply by the cofactor.
94    /// Some curves can implement a more efficient algorithm.
95    fn clear_cofactor(item: &Affine<Self>) -> Affine<Self> {
96        item.mul_by_cofactor()
97    }
98
99    /// Default implementation of group multiplication for projective
100    /// coordinates
101    fn mul_projective(base: &Projective<Self>, scalar: &[u64]) -> Projective<Self> {
102        double_and_add(base, scalar)
103    }
104
105    /// Default implementation of group multiplication for affine
106    /// coordinates.
107    fn mul_affine(base: &Affine<Self>, scalar: &[u64]) -> Projective<Self> {
108        double_and_add_affine(base, scalar)
109    }
110
111    /// Default implementation for multi scalar multiplication
112    fn msm(
113        bases: &[Affine<Self>],
114        scalars: &[Self::ScalarField],
115    ) -> Result<Projective<Self>, usize> {
116        (bases.len() == scalars.len())
117            .then(|| VariableBaseMSM::msm_unchecked(bases, scalars))
118            .ok_or_else(|| bases.len().min(scalars.len()))
119    }
120
121    /// If uncompressed, serializes both x and y coordinates as well as a bit for whether it is
122    /// infinity. If compressed, serializes x coordinate with two bits to encode whether y is
123    /// positive, negative, or infinity.
124    #[inline]
125    fn serialize_with_mode<W: Write>(
126        item: &Affine<Self>,
127        mut writer: W,
128        compress: ark_serialize::Compress,
129    ) -> Result<(), SerializationError> {
130        let (x, y, flags) = match item.is_zero() {
131            true => (
132                Self::BaseField::zero(),
133                Self::BaseField::zero(),
134                SWFlags::infinity(),
135            ),
136            false => (item.x, item.y, item.to_flags()),
137        };
138
139        match compress {
140            Compress::Yes => x.serialize_with_flags(writer, flags),
141            Compress::No => {
142                x.serialize_with_mode(&mut writer, compress)?;
143                y.serialize_with_flags(&mut writer, flags)
144            },
145        }
146    }
147
148    /// If `validate` is `Yes`, calls `check()` to make sure the element is valid.
149    fn deserialize_with_mode<R: Read>(
150        mut reader: R,
151        compress: Compress,
152        validate: Validate,
153    ) -> Result<Affine<Self>, SerializationError> {
154        let (x, y, flags) = match compress {
155            Compress::Yes => {
156                let (x, flags): (_, SWFlags) =
157                    CanonicalDeserializeWithFlags::deserialize_with_flags(reader)?;
158                match flags {
159                    SWFlags::PointAtInfinity => (
160                        Affine::<Self>::identity().x,
161                        Affine::<Self>::identity().y,
162                        flags,
163                    ),
164                    _ => {
165                        let is_positive = flags.is_positive().unwrap();
166                        let (y, neg_y) = Affine::<Self>::get_ys_from_x_unchecked(x)
167                            .ok_or(SerializationError::InvalidData)?;
168                        if is_positive {
169                            (x, y, flags)
170                        } else {
171                            (x, neg_y, flags)
172                        }
173                    },
174                }
175            },
176            Compress::No => {
177                let x: Self::BaseField =
178                    CanonicalDeserialize::deserialize_with_mode(&mut reader, compress, validate)?;
179                let (y, flags): (_, SWFlags) =
180                    CanonicalDeserializeWithFlags::deserialize_with_flags(&mut reader)?;
181                (x, y, flags)
182            },
183        };
184        if flags.is_infinity() {
185            Ok(Affine::identity())
186        } else {
187            let point = Affine::new_unchecked(x, y);
188            if validate == Validate::Yes {
189                point.check()?;
190            }
191            Ok(point)
192        }
193    }
194
195    #[inline]
196    fn serialized_size(compress: Compress) -> usize {
197        let zero = Self::BaseField::zero();
198        match compress {
199            Compress::Yes => zero.serialized_size_with_flags::<SWFlags>(),
200            Compress::No => zero.compressed_size() + zero.serialized_size_with_flags::<SWFlags>(),
201        }
202    }
203}
204
205pub trait ZeroFlag<C: SWCurveConfig>:
206    Hash + Ord + Eq + Copy + Sync + Send + Sized + 'static
207{
208    const IS_ZERO: Self;
209    const IS_NOT_ZERO: Self;
210    fn is_zero(point: &Affine<C>) -> bool;
211    fn zeroize(&mut self) {
212        *self = Self::IS_NOT_ZERO;
213    }
214}
215
216impl<C: SWCurveConfig<ZeroFlag = bool>> ZeroFlag<C> for bool {
217    const IS_ZERO: Self = true;
218    const IS_NOT_ZERO: Self = false;
219    fn is_zero(point: &Affine<C>) -> bool {
220        point.infinity
221    }
222}
223
224impl<C: SWCurveConfig> ZeroFlag<C> for () {
225    const IS_ZERO: Self = ();
226    const IS_NOT_ZERO: Self = ();
227    fn is_zero(point: &Affine<C>) -> bool {
228        point.x.is_zero() & point.y.is_zero()
229    }
230}
ark_ec/models/short_weierstrass/mod.rs

ark_ec/models/short_weierstrass/
mod.rs
