plonky2-ecdsa/src/curve/curve_summation.rs
src/curve/curve_summation.rsRaw
1use alloc::vec;
2use alloc::vec::Vec;
3use core::iter::Sum;
4
5use plonky2::field::ops::Square;
6use plonky2::field::types::Field;
7
8use crate::curve::curve_types::{AffinePoint, Curve, ProjectivePoint};
9
10impl<C: Curve> Sum<AffinePoint<C>> for ProjectivePoint<C> {
11 fn sum<I: Iterator<Item = AffinePoint<C>>>(iter: I) -> ProjectivePoint<C> {
12 let points: Vec<_> = iter.collect();
13 affine_summation_best(points)
14 }
15}
16
17impl<C: Curve> Sum for ProjectivePoint<C> {
18 fn sum<I: Iterator<Item = ProjectivePoint<C>>>(iter: I) -> ProjectivePoint<C> {
19 iter.fold(ProjectivePoint::ZERO, |acc, x| acc + x)
20 }
21}
22
23pub fn affine_summation_best<C: Curve>(summation: Vec<AffinePoint<C>>) -> ProjectivePoint<C> {
24 let result = affine_multisummation_best(vec![summation]);
25 debug_assert_eq!(result.len(), 1);
26 result[0]
27}
28
29pub fn affine_multisummation_best<C: Curve>(
30 summations: Vec<Vec<AffinePoint<C>>>,
31) -> Vec<ProjectivePoint<C>> {
32 let pairwise_sums: usize = summations.iter().map(|summation| summation.len() / 2).sum();
33
34 // This threshold is chosen based on data from the summation benchmarks.
35 if pairwise_sums < 70 {
36 affine_multisummation_pairwise(summations)
37 } else {
38 affine_multisummation_batch_inversion(summations)
39 }
40}
41
42/// Adds each pair of points using an affine + affine = projective formula, then adds up the
43/// intermediate sums using a projective formula.
44pub fn affine_multisummation_pairwise<C: Curve>(
45 summations: Vec<Vec<AffinePoint<C>>>,
46) -> Vec<ProjectivePoint<C>> {
47 summations
48 .into_iter()
49 .map(affine_summation_pairwise)
50 .collect()
51}
52
53/// Adds each pair of points using an affine + affine = projective formula, then adds up the
54/// intermediate sums using a projective formula.
55pub fn affine_summation_pairwise<C: Curve>(points: Vec<AffinePoint<C>>) -> ProjectivePoint<C> {
56 let mut reduced_points: Vec<ProjectivePoint<C>> = Vec::new();
57 for chunk in points.chunks(2) {
58 match chunk.len() {
59 1 => reduced_points.push(chunk[0].to_projective()),
60 2 => reduced_points.push(chunk[0] + chunk[1]),
61 _ => panic!(),
62 }
63 }
64 // TODO: Avoid copying (deref)
65 reduced_points
66 .iter()
67 .fold(ProjectivePoint::ZERO, |sum, x| sum + *x)
68}
69
70/// Computes several summations of affine points by applying an affine group law, except that the
71/// divisions are batched via Montgomery's trick.
72pub fn affine_summation_batch_inversion<C: Curve>(
73 summation: Vec<AffinePoint<C>>,
74) -> ProjectivePoint<C> {
75 let result = affine_multisummation_batch_inversion(vec![summation]);
76 debug_assert_eq!(result.len(), 1);
77 result[0]
78}
79
80/// Computes several summations of affine points by applying an affine group law, except that the
81/// divisions are batched via Montgomery's trick.
82pub fn affine_multisummation_batch_inversion<C: Curve>(
83 summations: Vec<Vec<AffinePoint<C>>>,
84) -> Vec<ProjectivePoint<C>> {
85 let mut elements_to_invert = Vec::new();
86
87 // For each pair of points, (x1, y1) and (x2, y2), that we're going to add later, we want to
88 // invert either y (if the points are equal) or x1 - x2 (otherwise). We will use these later.
89 for summation in &summations {
90 let n = summation.len();
91 // The special case for n=0 is to avoid underflow.
92 let range_end = if n == 0 { 0 } else { n - 1 };
93
94 for i in (0..range_end).step_by(2) {
95 let p1 = summation[i];
96 let p2 = summation[i + 1];
97 let AffinePoint {
98 x: x1,
99 y: y1,
100 zero: zero1,
101 } = p1;
102 let AffinePoint {
103 x: x2,
104 y: _y2,
105 zero: zero2,
106 } = p2;
107
108 if zero1 || zero2 || p1 == -p2 {
109 // These are trivial cases where we won't need any inverse.
110 } else if p1 == p2 {
111 elements_to_invert.push(y1.double());
112 } else {
113 elements_to_invert.push(x1 - x2);
114 }
115 }
116 }
117
118 let inverses: Vec<C::BaseField> =
119 C::BaseField::batch_multiplicative_inverse(&elements_to_invert);
120
121 let mut all_reduced_points = Vec::with_capacity(summations.len());
122 let mut inverse_index = 0;
123 for summation in summations {
124 let n = summation.len();
125 let mut reduced_points = Vec::with_capacity((n + 1) / 2);
126
127 // The special case for n=0 is to avoid underflow.
128 let range_end = if n == 0 { 0 } else { n - 1 };
129
130 for i in (0..range_end).step_by(2) {
131 let p1 = summation[i];
132 let p2 = summation[i + 1];
133 let AffinePoint {
134 x: x1,
135 y: y1,
136 zero: zero1,
137 } = p1;
138 let AffinePoint {
139 x: x2,
140 y: y2,
141 zero: zero2,
142 } = p2;
143
144 let sum = if zero1 {
145 p2
146 } else if zero2 {
147 p1
148 } else if p1 == -p2 {
149 AffinePoint::ZERO
150 } else {
151 // It's a non-trivial case where we need one of the inverses we computed earlier.
152 let inverse = inverses[inverse_index];
153 inverse_index += 1;
154
155 if p1 == p2 {
156 // This is the doubling case.
157 let mut numerator = x1.square().triple();
158 if C::A.is_nonzero() {
159 numerator += C::A;
160 }
161 let quotient = numerator * inverse;
162 let x3 = quotient.square() - x1.double();
163 let y3 = quotient * (x1 - x3) - y1;
164 AffinePoint::nonzero(x3, y3)
165 } else {
166 // This is the general case. We use the incomplete addition formulas 4.3 and 4.4.
167 let quotient = (y1 - y2) * inverse;
168 let x3 = quotient.square() - x1 - x2;
169 let y3 = quotient * (x1 - x3) - y1;
170 AffinePoint::nonzero(x3, y3)
171 }
172 };
173 reduced_points.push(sum);
174 }
175
176 // If n is odd, the last point was not part of a pair.
177 if n % 2 == 1 {
178 reduced_points.push(summation[n - 1]);
179 }
180
181 all_reduced_points.push(reduced_points);
182 }
183
184 // We should have consumed all of the inverses from the batch computation.
185 debug_assert_eq!(inverse_index, inverses.len());
186
187 // Recurse with our smaller set of points.
188 affine_multisummation_best(all_reduced_points)
189}
190
191#[cfg(test)]
192mod tests {
193 use super::*;
194 use crate::curve::secp256k1::Secp256K1;
195
196 #[test]
197 fn test_pairwise_affine_summation() {
198 let g_affine = Secp256K1::GENERATOR_AFFINE;
199 let g2_affine = (g_affine + g_affine).to_affine();
200 let g3_affine = (g_affine + g_affine + g_affine).to_affine();
201 let g2_proj = g2_affine.to_projective();
202 let g3_proj = g3_affine.to_projective();
203 assert_eq!(
204 affine_summation_pairwise::<Secp256K1>(vec![g_affine, g_affine]),
205 g2_proj
206 );
207 assert_eq!(
208 affine_summation_pairwise::<Secp256K1>(vec![g_affine, g2_affine]),
209 g3_proj
210 );
211 assert_eq!(
212 affine_summation_pairwise::<Secp256K1>(vec![g_affine, g_affine, g_affine]),
213 g3_proj
214 );
215 assert_eq!(
216 affine_summation_pairwise::<Secp256K1>(vec![]),
217 ProjectivePoint::ZERO
218 );
219 }
220
221 #[test]
222 fn test_pairwise_affine_summation_batch_inversion() {
223 let g = Secp256K1::GENERATOR_AFFINE;
224 let g_proj = g.to_projective();
225 assert_eq!(
226 affine_summation_batch_inversion::<Secp256K1>(vec![g, g]),
227 g_proj + g_proj
228 );
229 assert_eq!(
230 affine_summation_batch_inversion::<Secp256K1>(vec![g, g, g]),
231 g_proj + g_proj + g_proj
232 );
233 assert_eq!(
234 affine_summation_batch_inversion::<Secp256K1>(vec![]),
235 ProjectivePoint::ZERO
236 );
237 }
238}