sp1_lib/ecdsa/
projective.rs

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

sp1_lib/ecdsa/
projective.rs
