1use alloc::vec::Vec;
  2use core::fmt::Debug;
  3use core::hash::{Hash, Hasher};
  4use core::ops::Neg;
  5
  6use plonky2::field::ops::Square;
  7use plonky2::field::types::{Field, PrimeField};
  8use serde::{Deserialize, Serialize};
  9
 10// To avoid implementation conflicts from associated types,
 11// see https://github.com/rust-lang/rust/issues/20400
 12pub struct CurveScalar<C: Curve>(pub <C as Curve>::ScalarField);
 13
 14/// A short Weierstrass curve.
 15pub trait Curve: 'static + Sync + Sized + Copy + Debug {
 16    type BaseField: PrimeField;
 17    type ScalarField: PrimeField;
 18
 19    const A: Self::BaseField;
 20    const B: Self::BaseField;
 21
 22    const GENERATOR_AFFINE: AffinePoint<Self>;
 23
 24    const GENERATOR_PROJECTIVE: ProjectivePoint<Self> = ProjectivePoint {
 25        x: Self::GENERATOR_AFFINE.x,
 26        y: Self::GENERATOR_AFFINE.y,
 27        z: Self::BaseField::ONE,
 28    };
 29
 30    fn convert(x: Self::ScalarField) -> CurveScalar<Self> {
 31        CurveScalar(x)
 32    }
 33
 34    fn is_safe_curve() -> bool {
 35        // Added additional check to prevent using vulnerabilties in case a discriminant is equal to 0.
 36        (Self::A.cube().double().double() + Self::B.square().triple().triple().triple())
 37            .is_nonzero()
 38    }
 39}
 40
 41/// A point on a short Weierstrass curve, represented in affine coordinates.
 42#[derive(Copy, Clone, Debug, Deserialize, Serialize)]
 43pub struct AffinePoint<C: Curve> {
 44    pub x: C::BaseField,
 45    pub y: C::BaseField,
 46    pub zero: bool,
 47}
 48
 49impl<C: Curve> AffinePoint<C> {
 50    pub const ZERO: Self = Self {
 51        x: C::BaseField::ZERO,
 52        y: C::BaseField::ZERO,
 53        zero: true,
 54    };
 55
 56    pub fn nonzero(x: C::BaseField, y: C::BaseField) -> Self {
 57        let point = Self { x, y, zero: false };
 58        debug_assert!(point.is_valid());
 59        point
 60    }
 61
 62    pub fn is_valid(&self) -> bool {
 63        let Self { x, y, zero } = *self;
 64        zero || y.square() == x.cube() + C::A * x + C::B
 65    }
 66
 67    pub fn to_projective(&self) -> ProjectivePoint<C> {
 68        let Self { x, y, zero } = *self;
 69        let z = if zero {
 70            C::BaseField::ZERO
 71        } else {
 72            C::BaseField::ONE
 73        };
 74
 75        ProjectivePoint { x, y, z }
 76    }
 77
 78    pub fn batch_to_projective(affine_points: &[Self]) -> Vec<ProjectivePoint<C>> {
 79        affine_points.iter().map(Self::to_projective).collect()
 80    }
 81
 82    #[must_use]
 83    pub fn double(&self) -> Self {
 84        let AffinePoint { x: x1, y: y1, zero } = *self;
 85
 86        if zero {
 87            return AffinePoint::ZERO;
 88        }
 89
 90        let double_y = y1.double();
 91        let inv_double_y = double_y.inverse(); // (2y)^(-1)
 92        let triple_xx = x1.square().triple(); // 3x^2
 93        let lambda = (triple_xx + C::A) * inv_double_y;
 94        let x3 = lambda.square() - self.x.double();
 95        let y3 = lambda * (x1 - x3) - y1;
 96
 97        Self {
 98            x: x3,
 99            y: y3,
100            zero: false,
101        }
102    }
103}
104
105impl<C: Curve> PartialEq for AffinePoint<C> {
106    fn eq(&self, other: &Self) -> bool {
107        let AffinePoint {
108            x: x1,
109            y: y1,
110            zero: zero1,
111        } = *self;
112        let AffinePoint {
113            x: x2,
114            y: y2,
115            zero: zero2,
116        } = *other;
117        if zero1 || zero2 {
118            return zero1 == zero2;
119        }
120        x1 == x2 && y1 == y2
121    }
122}
123
124impl<C: Curve> Eq for AffinePoint<C> {}
125
126impl<C: Curve> Hash for AffinePoint<C> {
127    fn hash<H: Hasher>(&self, state: &mut H) {
128        if self.zero {
129            self.zero.hash(state);
130        } else {
131            self.x.hash(state);
132            self.y.hash(state);
133        }
134    }
135}
136
137/// A point on a short Weierstrass curve, represented in projective coordinates.
138#[derive(Copy, Clone, Debug)]
139pub struct ProjectivePoint<C: Curve> {
140    pub x: C::BaseField,
141    pub y: C::BaseField,
142    pub z: C::BaseField,
143}
144
145impl<C: Curve> ProjectivePoint<C> {
146    pub const ZERO: Self = Self {
147        x: C::BaseField::ZERO,
148        y: C::BaseField::ONE,
149        z: C::BaseField::ZERO,
150    };
151
152    pub fn nonzero(x: C::BaseField, y: C::BaseField, z: C::BaseField) -> Self {
153        let point = Self { x, y, z };
154        debug_assert!(point.is_valid());
155        point
156    }
157
158    pub fn is_valid(&self) -> bool {
159        let Self { x, y, z } = *self;
160        z.is_zero() || y.square() * z == x.cube() + C::A * x * z.square() + C::B * z.cube()
161    }
162
163    pub fn to_affine(&self) -> AffinePoint<C> {
164        let Self { x, y, z } = *self;
165        if z == C::BaseField::ZERO {
166            AffinePoint::ZERO
167        } else {
168            let z_inv = z.inverse();
169            AffinePoint::nonzero(x * z_inv, y * z_inv)
170        }
171    }
172
173    pub fn batch_to_affine(proj_points: &[Self]) -> Vec<AffinePoint<C>> {
174        let n = proj_points.len();
175        let zs: Vec<C::BaseField> = proj_points.iter().map(|pp| pp.z).collect();
176        let z_invs = C::BaseField::batch_multiplicative_inverse(&zs);
177
178        let mut result = Vec::with_capacity(n);
179        for i in 0..n {
180            let Self { x, y, z } = proj_points[i];
181            result.push(if z == C::BaseField::ZERO {
182                AffinePoint::ZERO
183            } else {
184                let z_inv = z_invs[i];
185                AffinePoint::nonzero(x * z_inv, y * z_inv)
186            });
187        }
188        result
189    }
190
191    // From https://www.hyperelliptic.org/EFD/g1p/data/shortw/projective/doubling/dbl-2007-bl
192    #[must_use]
193    pub fn double(&self) -> Self {
194        let Self { x, y, z } = *self;
195        if z == C::BaseField::ZERO {
196            return ProjectivePoint::ZERO;
197        }
198
199        let xx = x.square();
200        let zz = z.square();
201        let mut w = xx.triple();
202        if C::A.is_nonzero() {
203            w += C::A * zz;
204        }
205        let s = y.double() * z;
206        let r = y * s;
207        let rr = r.square();
208        let b = (x + r).square() - (xx + rr);
209        let h = w.square() - b.double();
210        let x3 = h * s;
211        let y3 = w * (b - h) - rr.double();
212        let z3 = s.cube();
213        Self {
214            x: x3,
215            y: y3,
216            z: z3,
217        }
218    }
219
220    pub fn add_slices(a: &[Self], b: &[Self]) -> Vec<Self> {
221        assert_eq!(a.len(), b.len());
222        a.iter()
223            .zip(b.iter())
224            .map(|(&a_i, &b_i)| a_i + b_i)
225            .collect()
226    }
227
228    #[must_use]
229    pub fn neg(&self) -> Self {
230        Self {
231            x: self.x,
232            y: -self.y,
233            z: self.z,
234        }
235    }
236}
237
238impl<C: Curve> PartialEq for ProjectivePoint<C> {
239    fn eq(&self, other: &Self) -> bool {
240        let ProjectivePoint {
241            x: x1,
242            y: y1,
243            z: z1,
244        } = *self;
245        let ProjectivePoint {
246            x: x2,
247            y: y2,
248            z: z2,
249        } = *other;
250        if z1 == C::BaseField::ZERO || z2 == C::BaseField::ZERO {
251            return z1 == z2;
252        }
253
254        // We want to compare (x1/z1, y1/z1) == (x2/z2, y2/z2).
255        // But to avoid field division, it is better to compare (x1*z2, y1*z2) == (x2*z1, y2*z1).
256        x1 * z2 == x2 * z1 && y1 * z2 == y2 * z1
257    }
258}
259
260impl<C: Curve> Eq for ProjectivePoint<C> {}
261
262impl<C: Curve> Neg for AffinePoint<C> {
263    type Output = AffinePoint<C>;
264
265    fn neg(self) -> Self::Output {
266        let AffinePoint { x, y, zero } = self;
267        AffinePoint { x, y: -y, zero }
268    }
269}
270
271impl<C: Curve> Neg for ProjectivePoint<C> {
272    type Output = ProjectivePoint<C>;
273
274    fn neg(self) -> Self::Output {
275        let ProjectivePoint { x, y, z } = self;
276        ProjectivePoint { x, y: -y, z }
277    }
278}
279
280pub fn base_to_scalar<C: Curve>(x: C::BaseField) -> C::ScalarField {
281    C::ScalarField::from_noncanonical_biguint(x.to_canonical_biguint())
282}
283
284pub fn scalar_to_base<C: Curve>(x: C::ScalarField) -> C::BaseField {
285    C::BaseField::from_noncanonical_biguint(x.to_canonical_biguint())
286}