sp1_lib/ecdsa/
projective.rs

1//! Implementation of the SP1 accelerated projective point. The projective point wraps the affine point.
2//!
3//! This type is mainly used in the `ecdsa-core` algorithms.
4//!
5//! Note: When performing curve operations, accelerated crates for SP1 use affine arithmetic instead of projective arithmetic for performance.
6
7use super::{AffinePoint, ECDSACurve, SP1AffinePointTrait};
8
9use elliptic_curve::{
10    group::{cofactor::CofactorGroup, prime::PrimeGroup},
11    ops::MulByGenerator,
12    sec1::{CompressedPoint, ModulusSize},
13    CurveArithmetic, FieldBytes,
14};
15
16use elliptic_curve::{
17    ff::{Field, PrimeField},
18    group::{Curve, Group, GroupEncoding},
19    ops::LinearCombination,
20    rand_core::RngCore,
21    subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption},
22    zeroize::DefaultIsZeroes,
23};
24
25use std::iter::Sum;
26use std::ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign};
27
28use std::borrow::Borrow;
29
30/// The SP1 accelerated projective point.
31#[derive(Clone, Copy, Debug)]
32pub struct ProjectivePoint<C: ECDSACurve> {
33    /// The inner affine point.
34    ///
35    /// SP1 uses affine arithmetic for all operations.
36    pub inner: AffinePoint<C>,
37}
38
39impl<C: ECDSACurve> ProjectivePoint<C> {
40    pub fn identity() -> Self {
41        ProjectivePoint { inner: AffinePoint::<C>::identity() }
42    }
43
44    /// Convert the projective point to an affine point.
45    pub fn to_affine(self) -> AffinePoint<C> {
46        self.inner
47    }
48
49    fn to_zkvm_point(self) -> C::SP1AffinePoint {
50        self.inner.inner
51    }
52
53    fn as_zkvm_point(&self) -> &C::SP1AffinePoint {
54        &self.inner.inner
55    }
56
57    fn as_mut_zkvm_point(&mut self) -> &mut C::SP1AffinePoint {
58        &mut self.inner.inner
59    }
60
61    /// Check if the point is the identity point.
62    pub fn is_identity(&self) -> Choice {
63        self.inner.is_identity()
64    }
65
66    fn from_zkvm_point(p: C::SP1AffinePoint) -> Self {
67        Self { inner: AffinePoint { inner: p } }
68    }
69}
70
71impl<C: ECDSACurve> From<AffinePoint<C>> for ProjectivePoint<C> {
72    fn from(p: AffinePoint<C>) -> Self {
73        ProjectivePoint { inner: p }
74    }
75}
76
77impl<C: ECDSACurve> From<&AffinePoint<C>> for ProjectivePoint<C> {
78    fn from(p: &AffinePoint<C>) -> Self {
79        ProjectivePoint { inner: *p }
80    }
81}
82
83impl<C: ECDSACurve> From<ProjectivePoint<C>> for AffinePoint<C> {
84    fn from(p: ProjectivePoint<C>) -> Self {
85        p.inner
86    }
87}
88
89impl<C: ECDSACurve> From<&ProjectivePoint<C>> for AffinePoint<C> {
90    fn from(p: &ProjectivePoint<C>) -> Self {
91        p.inner
92    }
93}
94
95impl<C: ECDSACurve> Group for ProjectivePoint<C> {
96    type Scalar = <C as CurveArithmetic>::Scalar;
97
98    fn identity() -> Self {
99        Self::identity()
100    }
101
102    fn random(rng: impl RngCore) -> Self {
103        ProjectivePoint::<C>::generator() * Self::Scalar::random(rng)
104    }
105
106    fn double(&self) -> Self {
107        *self + self
108    }
109
110    fn generator() -> Self {
111        Self { inner: AffinePoint::<C>::generator() }
112    }
113
114    fn is_identity(&self) -> Choice {
115        self.inner.is_identity()
116    }
117}
118
119impl<C: ECDSACurve> Curve for ProjectivePoint<C> {
120    type AffineRepr = AffinePoint<C>;
121
122    fn to_affine(&self) -> Self::AffineRepr {
123        self.inner
124    }
125}
126
127impl<C: ECDSACurve> MulByGenerator for ProjectivePoint<C> {}
128
129impl<C: ECDSACurve> LinearCombination for ProjectivePoint<C> {
130    fn lincomb(x: &Self, k: &Self::Scalar, y: &Self, l: &Self::Scalar) -> Self {
131        let x = x.to_zkvm_point();
132        let y = y.to_zkvm_point();
133
134        let a_bits_le = be_bytes_to_le_bits(k.to_repr().as_ref());
135        let b_bits_le = be_bytes_to_le_bits(l.to_repr().as_ref());
136
137        let sp1_point =
138            C::SP1AffinePoint::multi_scalar_multiplication(&a_bits_le, x, &b_bits_le, y);
139
140        Self::from_zkvm_point(sp1_point)
141    }
142}
143
144// Implementation of scalar multiplication for the projective point.
145
146impl<C: ECDSACurve, T: Borrow<C::Scalar>> Mul<T> for ProjectivePoint<C> {
147    type Output = ProjectivePoint<C>;
148
149    fn mul(mut self, rhs: T) -> Self::Output {
150        let sp1_point = self.as_mut_zkvm_point();
151        sp1_point.mul_assign(&be_bytes_to_le_words(rhs.borrow().to_repr()));
152
153        self
154    }
155}
156
157impl<C: ECDSACurve, T: Borrow<C::Scalar>> MulAssign<T> for ProjectivePoint<C> {
158    fn mul_assign(&mut self, rhs: T) {
159        self.as_mut_zkvm_point().mul_assign(&be_bytes_to_le_words(rhs.borrow().to_repr()));
160    }
161}
162
163// Implementation of projective arithmetic.
164
165impl<C: ECDSACurve> Neg for ProjectivePoint<C> {
166    type Output = ProjectivePoint<C>;
167
168    fn neg(self) -> Self::Output {
169        if self.is_identity().into() {
170            return self;
171        }
172
173        let point = self.to_affine();
174        let (x, y) = point.field_elements();
175
176        AffinePoint::<C>::from_field_elements_unchecked(x, y.neg()).into()
177    }
178}
179
180impl<C: ECDSACurve> Add<ProjectivePoint<C>> for ProjectivePoint<C> {
181    type Output = ProjectivePoint<C>;
182
183    fn add(mut self, rhs: ProjectivePoint<C>) -> Self::Output {
184        self.as_mut_zkvm_point().add_assign(rhs.as_zkvm_point());
185
186        self
187    }
188}
189
190impl<C: ECDSACurve> Add<&ProjectivePoint<C>> for ProjectivePoint<C> {
191    type Output = ProjectivePoint<C>;
192
193    fn add(mut self, rhs: &ProjectivePoint<C>) -> Self::Output {
194        self.as_mut_zkvm_point().add_assign(rhs.as_zkvm_point());
195
196        self
197    }
198}
199
200impl<C: ECDSACurve> Sub<ProjectivePoint<C>> for ProjectivePoint<C> {
201    type Output = ProjectivePoint<C>;
202
203    #[allow(clippy::suspicious_arithmetic_impl)]
204    fn sub(self, rhs: ProjectivePoint<C>) -> Self::Output {
205        self + rhs.neg()
206    }
207}
208
209impl<C: ECDSACurve> Sub<&ProjectivePoint<C>> for ProjectivePoint<C> {
210    type Output = ProjectivePoint<C>;
211
212    #[allow(clippy::suspicious_arithmetic_impl)]
213    fn sub(self, rhs: &ProjectivePoint<C>) -> Self::Output {
214        self + (*rhs).neg()
215    }
216}
217
218impl<C: ECDSACurve> Sum<ProjectivePoint<C>> for ProjectivePoint<C> {
219    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
220        iter.fold(Self::identity(), |a, b| a + b)
221    }
222}
223
224impl<'a, C: ECDSACurve> Sum<&'a ProjectivePoint<C>> for ProjectivePoint<C> {
225    fn sum<I: Iterator<Item = &'a ProjectivePoint<C>>>(iter: I) -> Self {
226        iter.cloned().sum()
227    }
228}
229
230impl<C: ECDSACurve> AddAssign<ProjectivePoint<C>> for ProjectivePoint<C> {
231    fn add_assign(&mut self, rhs: ProjectivePoint<C>) {
232        self.as_mut_zkvm_point().add_assign(rhs.as_zkvm_point());
233    }
234}
235
236impl<C: ECDSACurve> AddAssign<&ProjectivePoint<C>> for ProjectivePoint<C> {
237    fn add_assign(&mut self, rhs: &ProjectivePoint<C>) {
238        self.as_mut_zkvm_point().add_assign(rhs.as_zkvm_point());
239    }
240}
241
242impl<C: ECDSACurve> SubAssign<ProjectivePoint<C>> for ProjectivePoint<C> {
243    fn sub_assign(&mut self, rhs: ProjectivePoint<C>) {
244        self.as_mut_zkvm_point().add_assign(rhs.neg().as_zkvm_point());
245    }
246}
247
248impl<C: ECDSACurve> SubAssign<&ProjectivePoint<C>> for ProjectivePoint<C> {
249    fn sub_assign(&mut self, rhs: &ProjectivePoint<C>) {
250        self.as_mut_zkvm_point().add_assign(rhs.neg().as_zkvm_point());
251    }
252}
253
254impl<C: ECDSACurve> Default for ProjectivePoint<C> {
255    fn default() -> Self {
256        Self::identity()
257    }
258}
259
260// Implementation of mixed arithmetic.
261
262impl<C: ECDSACurve> Add<AffinePoint<C>> for ProjectivePoint<C> {
263    type Output = ProjectivePoint<C>;
264
265    fn add(self, rhs: AffinePoint<C>) -> Self::Output {
266        self + ProjectivePoint { inner: rhs }
267    }
268}
269
270impl<C: ECDSACurve> Add<&AffinePoint<C>> for ProjectivePoint<C> {
271    type Output = ProjectivePoint<C>;
272
273    fn add(self, rhs: &AffinePoint<C>) -> Self::Output {
274        self + ProjectivePoint { inner: *rhs }
275    }
276}
277
278impl<C: ECDSACurve> AddAssign<AffinePoint<C>> for ProjectivePoint<C> {
279    fn add_assign(&mut self, rhs: AffinePoint<C>) {
280        self.as_mut_zkvm_point().add_assign(&rhs.inner);
281    }
282}
283
284impl<C: ECDSACurve> AddAssign<&AffinePoint<C>> for ProjectivePoint<C> {
285    fn add_assign(&mut self, rhs: &AffinePoint<C>) {
286        self.as_mut_zkvm_point().add_assign(&rhs.inner);
287    }
288}
289
290impl<C: ECDSACurve> Sub<AffinePoint<C>> for ProjectivePoint<C> {
291    type Output = ProjectivePoint<C>;
292
293    fn sub(self, rhs: AffinePoint<C>) -> Self::Output {
294        self - ProjectivePoint { inner: rhs }
295    }
296}
297
298impl<C: ECDSACurve> Sub<&AffinePoint<C>> for ProjectivePoint<C> {
299    type Output = ProjectivePoint<C>;
300
301    fn sub(self, rhs: &AffinePoint<C>) -> Self::Output {
302        self - ProjectivePoint { inner: *rhs }
303    }
304}
305
306impl<C: ECDSACurve> SubAssign<AffinePoint<C>> for ProjectivePoint<C> {
307    fn sub_assign(&mut self, rhs: AffinePoint<C>) {
308        let projective = ProjectivePoint { inner: rhs }.neg();
309
310        self.as_mut_zkvm_point().add_assign(projective.as_zkvm_point());
311    }
312}
313
314impl<C: ECDSACurve> SubAssign<&AffinePoint<C>> for ProjectivePoint<C> {
315    fn sub_assign(&mut self, rhs: &AffinePoint<C>) {
316        let projective = ProjectivePoint { inner: *rhs }.neg();
317
318        self.as_mut_zkvm_point().add_assign(projective.as_zkvm_point());
319    }
320}
321
322impl<C: ECDSACurve> DefaultIsZeroes for ProjectivePoint<C> {}
323
324impl<C: ECDSACurve> ConditionallySelectable for ProjectivePoint<C> {
325    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
326        Self { inner: AffinePoint::conditional_select(&a.inner, &b.inner, choice) }
327    }
328}
329
330impl<C: ECDSACurve> ConstantTimeEq for ProjectivePoint<C> {
331    fn ct_eq(&self, other: &Self) -> Choice {
332        self.inner.ct_eq(&other.inner)
333    }
334}
335
336impl<C: ECDSACurve> PartialEq for ProjectivePoint<C> {
337    fn eq(&self, other: &Self) -> bool {
338        self.ct_eq(other).into()
339    }
340}
341
342impl<C: ECDSACurve> Eq for ProjectivePoint<C> {}
343
344impl<C: ECDSACurve> GroupEncoding for ProjectivePoint<C>
345where
346    FieldBytes<C>: Copy,
347    C::FieldBytesSize: ModulusSize,
348    CompressedPoint<C>: Copy,
349{
350    type Repr = CompressedPoint<C>;
351
352    fn from_bytes(bytes: &Self::Repr) -> CtOption<Self> {
353        <AffinePoint<C> as GroupEncoding>::from_bytes(bytes).map(Into::into)
354    }
355
356    fn from_bytes_unchecked(bytes: &Self::Repr) -> CtOption<Self> {
357        // No unchecked conversion possible for compressed points.
358        Self::from_bytes(bytes)
359    }
360
361    fn to_bytes(&self) -> Self::Repr {
362        self.inner.to_bytes()
363    }
364}
365
366impl<C: ECDSACurve> PrimeGroup for ProjectivePoint<C>
367where
368    FieldBytes<C>: Copy,
369    C::FieldBytesSize: ModulusSize,
370    CompressedPoint<C>: Copy,
371{
372}
373
374/// The scalar field has prime order, so the cofactor is 1.
375impl<C: ECDSACurve> CofactorGroup for ProjectivePoint<C>
376where
377    FieldBytes<C>: Copy,
378    C::FieldBytesSize: ModulusSize,
379    CompressedPoint<C>: Copy,
380{
381    type Subgroup = Self;
382
383    fn clear_cofactor(&self) -> Self {
384        *self
385    }
386
387    fn into_subgroup(self) -> CtOption<Self> {
388        CtOption::new(self, Choice::from(1))
389    }
390
391    fn is_torsion_free(&self) -> Choice {
392        Choice::from(1)
393    }
394}
395
396#[inline]
397fn be_bytes_to_le_words<T: AsMut<[u8]>>(mut bytes: T) -> [u32; 8] {
398    let bytes = bytes.as_mut();
399    bytes.reverse();
400
401    let mut iter = bytes.chunks(4).map(|b| u32::from_le_bytes(b.try_into().unwrap()));
402    core::array::from_fn(|_| iter.next().unwrap())
403}
404
405/// Convert big-endian bytes with the most significant bit first to little-endian bytes with the least significant bit first.
406/// Panics: If the bytes have len > 32.
407#[inline]
408fn be_bytes_to_le_bits(be_bytes: &[u8]) -> [bool; 256] {
409    let mut bits = [false; 256];
410    // Reverse the byte order to little-endian.
411    for (i, &byte) in be_bytes.iter().rev().enumerate() {
412        for j in 0..8 {
413            // Flip the bit order so the least significant bit is now the first bit of the chunk.
414            bits[i * 8 + j] = ((byte >> j) & 1) == 1;
415        }
416    }
417    bits
418}
sp1_lib/ecdsa/projective.rs

sp1_lib/ecdsa/
projective.rs
