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

sp1_lib/ecdsa/
projective.rs
