sp1_lib/utils.rs
1pub trait AffinePoint<const N: usize>: Clone + Sized {
2 /// The generator.
3 #[deprecated = "This const will have the `Self` type in the next major version."]
4 const GENERATOR: [u32; N];
5
6 const GENERATOR_T: Self;
7
8 /// Creates a new [`AffinePoint`] from the given limbs.
9 fn new(limbs: [u32; N]) -> Self;
10
11 /// Creates a new [`AffinePoint`] that corresponds to the identity point.
12 fn identity() -> Self;
13
14 /// Returns a reference to the limbs.
15 fn limbs_ref(&self) -> &[u32; N];
16
17 /// Returns a mutable reference to the limbs. If the point is the infinity point, this will
18 /// panic.
19 fn limbs_mut(&mut self) -> &mut [u32; N];
20
21 fn is_identity(&self) -> bool;
22
23 /// Creates a new [`AffinePoint`] from the given x and y coordinates.
24 ///
25 /// The bytes are the concatenated little endian representations of the coordinates.
26 fn from(x: &[u8], y: &[u8]) -> Self {
27 debug_assert!(x.len() == N * 2);
28 debug_assert!(y.len() == N * 2);
29
30 let mut limbs = [0u32; N];
31 let x = bytes_to_words_le(x);
32 let y = bytes_to_words_le(y);
33
34 debug_assert!(x.len() == N / 2);
35 debug_assert!(y.len() == N / 2);
36
37 limbs[..(N / 2)].copy_from_slice(&x);
38 limbs[(N / 2)..].copy_from_slice(&y);
39 Self::new(limbs)
40 }
41
42 /// Creates a new [`AffinePoint`] from the given bytes in little endian.
43 fn from_le_bytes(bytes: &[u8]) -> Self {
44 let limbs = bytes_to_words_le(bytes);
45 debug_assert!(limbs.len() == N);
46 Self::new(limbs.try_into().unwrap())
47 }
48
49 /// Creates a new [`AffinePoint`] from the given bytes in big endian.
50 fn to_le_bytes(&self) -> Vec<u8> {
51 let le_bytes = words_to_bytes_le(self.limbs_ref());
52 debug_assert!(le_bytes.len() == N * 4);
53 le_bytes
54 }
55
56 /// Adds the given [`AffinePoint`] to `self`.
57 fn add_assign(&mut self, other: &Self);
58
59 /// Adds the given [`AffinePoint`] to `self`. Can be optionally overridden to use a different
60 /// implementation of addition in multi-scalar multiplication, which is used in secp256k1
61 /// recovery.
62 fn complete_add_assign(&mut self, other: &Self) {
63 self.add_assign(other);
64 }
65
66 /// Doubles `self`.
67 fn double(&mut self);
68
69 /// Multiplies `self` by the given scalar.
70 fn mul_assign(&mut self, scalar: &[u32]) {
71 debug_assert!(scalar.len() == N / 2);
72
73 let mut res: Self = Self::identity();
74 let mut temp = self.clone();
75
76 for &words in scalar.iter() {
77 for i in 0..32 {
78 if (words >> i) & 1 == 1 {
79 res.complete_add_assign(&temp);
80 }
81 temp.double();
82 }
83 }
84
85 *self = res;
86 }
87
88 /// Performs multi-scalar multiplication (MSM) on slices of bit vectors and points. Note:
89 /// a_bits_le and b_bits_le should be in little endian order.
90 fn multi_scalar_multiplication(
91 a_bits_le: &[bool],
92 a: Self,
93 b_bits_le: &[bool],
94 b: Self,
95 ) -> Self {
96 // The length of the bit vectors must be the same.
97 debug_assert!(a_bits_le.len() == b_bits_le.len());
98
99 let mut res: Self = Self::identity();
100 let mut temp_a = a.clone();
101 let mut temp_b = b.clone();
102 for (a_bit, b_bit) in a_bits_le.iter().zip(b_bits_le.iter()) {
103 if *a_bit {
104 res.complete_add_assign(&temp_a);
105 }
106 if *b_bit {
107 res.complete_add_assign(&temp_b);
108 }
109 temp_a.double();
110 temp_b.double();
111 }
112 res
113 }
114}
115
116/// Errors that can occur during scalar multiplication of an [`AffinePoint`].
117#[derive(Debug)]
118pub enum MulAssignError {
119 ScalarIsZero,
120}
121
122/// Converts a slice of words to a byte array in little endian.
123pub fn words_to_bytes_le(words: &[u32]) -> Vec<u8> {
124 words.iter().flat_map(|word| word.to_le_bytes().to_vec()).collect::<Vec<_>>()
125}
126
127/// Converts a byte array in little endian to a slice of words.
128pub fn bytes_to_words_le(bytes: &[u8]) -> Vec<u32> {
129 bytes
130 .chunks_exact(4)
131 .map(|chunk| u32::from_le_bytes(chunk.try_into().unwrap()))
132 .collect::<Vec<_>>()
133}
134
135#[derive(Copy, Clone, Debug)]
136/// A representation of a point on a Weierstrass curve.
137pub enum WeierstrassPoint<const N: usize> {
138 Infinity,
139 Affine([u32; N]),
140}
141
142/// A trait for affine points on Weierstrass curves.
143pub trait WeierstrassAffinePoint<const N: usize>: AffinePoint<N> {
144 /// The infinity point representation of the Weierstrass curve. Typically an enum variant.
145 fn infinity() -> Self;
146
147 /// Returns true if the point is the infinity point.
148 fn is_infinity(&self) -> bool;
149
150 /// Performs the complete addition of two [`AffinePoint`]'s on a Weierstrass curve.
151 /// For an addition of two points P1 and P2, the cases are:
152 /// 1. P1 is infinity
153 /// 2. P2 is infinity
154 /// 3. P1 equals P2
155 /// 4. P1 is the negation of P2
156 /// 5. Default addition.
157 ///
158 /// Implements the complete addition cases according to the
159 /// [Zcash complete addition spec](https://zcash.github.io/halo2/design/gadgets/ecc/addition.html#complete-addition).
160 fn weierstrass_add_assign(&mut self, other: &Self) {
161 // Case 1: p1 is infinity.
162 if self.is_infinity() {
163 *self = other.clone();
164 return;
165 }
166
167 // Case 2: p2 is infinity.
168 if other.is_infinity() {
169 return;
170 }
171
172 // Once it's known the points are not infinity, their limbs can be safely used.
173 let p1 = self.limbs_mut();
174 let p2 = other.limbs_ref();
175
176 // Case 3: p1 equals p2.
177 if p1 == p2 {
178 self.double();
179 return;
180 }
181
182 // Case 4: p1 is the negation of p2.
183 // Note: If p1 and p2 are valid elliptic curve points, and p1.x == p2.x, that means that
184 // either p1.y == p2.y or p1.y + p2.y == p. Because we are past Case 4, we know that p1.y !=
185 // p2.y, so we can just check if p1.x == p2.x. Therefore, this implicitly checks that
186 // p1.x == p2.x AND p1.y + p2.y == p without modular negation.
187 if p1[..N / 2] == p2[..N / 2] {
188 *self = Self::infinity();
189 return;
190 }
191
192 // Case 5: Default addition.
193 self.add_assign(other);
194 }
195}