plonky2-ecdsa/src/gadgets/curve.rs
src/gadgets/curve.rsRaw
1use alloc::vec;
2use alloc::vec::Vec;
3
4use plonky2::field::extension::Extendable;
5use plonky2::field::types::Sample;
6use plonky2::hash::hash_types::RichField;
7use plonky2::iop::target::BoolTarget;
8use plonky2::plonk::circuit_builder::CircuitBuilder;
9
10use crate::curve::curve_types::{AffinePoint, Curve, CurveScalar};
11use crate::gadgets::nonnative::{CircuitBuilderNonNative, NonNativeTarget};
12
13/// A Target representing an affine point on the curve `C`. We use incomplete arithmetic for efficiency,
14/// so we assume these points are not zero.
15#[derive(Clone, Debug)]
16pub struct AffinePointTarget<C: Curve> {
17 pub x: NonNativeTarget<C::BaseField>,
18 pub y: NonNativeTarget<C::BaseField>,
19}
20
21impl<C: Curve> AffinePointTarget<C> {
22 pub fn to_vec(&self) -> Vec<NonNativeTarget<C::BaseField>> {
23 vec![self.x.clone(), self.y.clone()]
24 }
25}
26
27pub trait CircuitBuilderCurve<F: RichField + Extendable<D>, const D: usize> {
28 fn constant_affine_point<C: Curve>(&mut self, point: AffinePoint<C>) -> AffinePointTarget<C>;
29
30 fn connect_affine_point<C: Curve>(
31 &mut self,
32 lhs: &AffinePointTarget<C>,
33 rhs: &AffinePointTarget<C>,
34 );
35
36 fn add_virtual_affine_point_target<C: Curve>(&mut self) -> AffinePointTarget<C>;
37
38 fn curve_assert_valid<C: Curve>(&mut self, p: &AffinePointTarget<C>);
39
40 fn curve_neg<C: Curve>(&mut self, p: &AffinePointTarget<C>) -> AffinePointTarget<C>;
41
42 fn curve_conditional_neg<C: Curve>(
43 &mut self,
44 p: &AffinePointTarget<C>,
45 b: BoolTarget,
46 ) -> AffinePointTarget<C>;
47
48 fn curve_double<C: Curve>(&mut self, p: &AffinePointTarget<C>) -> AffinePointTarget<C>;
49
50 fn curve_repeated_double<C: Curve>(
51 &mut self,
52 p: &AffinePointTarget<C>,
53 n: usize,
54 ) -> AffinePointTarget<C>;
55
56 /// Add two points, which are assumed to be non-equal.
57 fn curve_add<C: Curve>(
58 &mut self,
59 p1: &AffinePointTarget<C>,
60 p2: &AffinePointTarget<C>,
61 ) -> AffinePointTarget<C>;
62
63 fn curve_conditional_add<C: Curve>(
64 &mut self,
65 p1: &AffinePointTarget<C>,
66 p2: &AffinePointTarget<C>,
67 b: BoolTarget,
68 ) -> AffinePointTarget<C>;
69
70 fn curve_scalar_mul<C: Curve>(
71 &mut self,
72 p: &AffinePointTarget<C>,
73 n: &NonNativeTarget<C::ScalarField>,
74 ) -> AffinePointTarget<C>;
75}
76
77impl<F: RichField + Extendable<D>, const D: usize> CircuitBuilderCurve<F, D>
78 for CircuitBuilder<F, D>
79{
80 fn constant_affine_point<C: Curve>(&mut self, point: AffinePoint<C>) -> AffinePointTarget<C> {
81 debug_assert!(!point.zero);
82 AffinePointTarget {
83 x: self.constant_nonnative(point.x),
84 y: self.constant_nonnative(point.y),
85 }
86 }
87
88 fn connect_affine_point<C: Curve>(
89 &mut self,
90 lhs: &AffinePointTarget<C>,
91 rhs: &AffinePointTarget<C>,
92 ) {
93 self.connect_nonnative(&lhs.x, &rhs.x);
94 self.connect_nonnative(&lhs.y, &rhs.y);
95 }
96
97 fn add_virtual_affine_point_target<C: Curve>(&mut self) -> AffinePointTarget<C> {
98 let x = self.add_virtual_nonnative_target();
99 let y = self.add_virtual_nonnative_target();
100
101 AffinePointTarget { x, y }
102 }
103
104 fn curve_assert_valid<C: Curve>(&mut self, p: &AffinePointTarget<C>) {
105 let a = self.constant_nonnative(C::A);
106 let b = self.constant_nonnative(C::B);
107
108 let y_squared = self.mul_nonnative(&p.y, &p.y);
109 let x_squared = self.mul_nonnative(&p.x, &p.x);
110 let x_cubed = self.mul_nonnative(&x_squared, &p.x);
111 let a_x = self.mul_nonnative(&a, &p.x);
112 let a_x_plus_b = self.add_nonnative(&a_x, &b);
113 let rhs = self.add_nonnative(&x_cubed, &a_x_plus_b);
114
115 self.connect_nonnative(&y_squared, &rhs);
116 }
117
118 fn curve_neg<C: Curve>(&mut self, p: &AffinePointTarget<C>) -> AffinePointTarget<C> {
119 let neg_y = self.neg_nonnative(&p.y);
120 AffinePointTarget {
121 x: p.x.clone(),
122 y: neg_y,
123 }
124 }
125
126 fn curve_conditional_neg<C: Curve>(
127 &mut self,
128 p: &AffinePointTarget<C>,
129 b: BoolTarget,
130 ) -> AffinePointTarget<C> {
131 AffinePointTarget {
132 x: p.x.clone(),
133 y: self.nonnative_conditional_neg(&p.y, b),
134 }
135 }
136
137 fn curve_double<C: Curve>(&mut self, p: &AffinePointTarget<C>) -> AffinePointTarget<C> {
138 let AffinePointTarget { x, y } = p;
139 let double_y = self.add_nonnative(y, y);
140 let inv_double_y = self.inv_nonnative(&double_y);
141 let x_squared = self.mul_nonnative(x, x);
142 let double_x_squared = self.add_nonnative(&x_squared, &x_squared);
143 let triple_x_squared = self.add_nonnative(&double_x_squared, &x_squared);
144
145 let a = self.constant_nonnative(C::A);
146 let triple_xx_a = self.add_nonnative(&triple_x_squared, &a);
147 let lambda = self.mul_nonnative(&triple_xx_a, &inv_double_y);
148 let lambda_squared = self.mul_nonnative(&lambda, &lambda);
149 let x_double = self.add_nonnative(x, x);
150
151 let x3 = self.sub_nonnative(&lambda_squared, &x_double);
152
153 let x_diff = self.sub_nonnative(x, &x3);
154 let lambda_x_diff = self.mul_nonnative(&lambda, &x_diff);
155
156 let y3 = self.sub_nonnative(&lambda_x_diff, y);
157
158 AffinePointTarget { x: x3, y: y3 }
159 }
160
161 fn curve_repeated_double<C: Curve>(
162 &mut self,
163 p: &AffinePointTarget<C>,
164 n: usize,
165 ) -> AffinePointTarget<C> {
166 let mut result = p.clone();
167
168 for _ in 0..n {
169 result = self.curve_double(&result);
170 }
171
172 result
173 }
174
175 fn curve_add<C: Curve>(
176 &mut self,
177 p1: &AffinePointTarget<C>,
178 p2: &AffinePointTarget<C>,
179 ) -> AffinePointTarget<C> {
180 let AffinePointTarget { x: x1, y: y1 } = p1;
181 let AffinePointTarget { x: x2, y: y2 } = p2;
182
183 let u = self.sub_nonnative(y2, y1);
184 let v = self.sub_nonnative(x2, x1);
185 let v_inv = self.inv_nonnative(&v);
186 let s = self.mul_nonnative(&u, &v_inv);
187 let s_squared = self.mul_nonnative(&s, &s);
188 let x_sum = self.add_nonnative(x2, x1);
189 let x3 = self.sub_nonnative(&s_squared, &x_sum);
190 let x_diff = self.sub_nonnative(x1, &x3);
191 let prod = self.mul_nonnative(&s, &x_diff);
192 let y3 = self.sub_nonnative(&prod, y1);
193
194 AffinePointTarget { x: x3, y: y3 }
195 }
196
197 fn curve_conditional_add<C: Curve>(
198 &mut self,
199 p1: &AffinePointTarget<C>,
200 p2: &AffinePointTarget<C>,
201 b: BoolTarget,
202 ) -> AffinePointTarget<C> {
203 let not_b = self.not(b);
204 let sum = self.curve_add(p1, p2);
205 let x_if_true = self.mul_nonnative_by_bool(&sum.x, b);
206 let y_if_true = self.mul_nonnative_by_bool(&sum.y, b);
207 let x_if_false = self.mul_nonnative_by_bool(&p1.x, not_b);
208 let y_if_false = self.mul_nonnative_by_bool(&p1.y, not_b);
209
210 let x = self.add_nonnative(&x_if_true, &x_if_false);
211 let y = self.add_nonnative(&y_if_true, &y_if_false);
212
213 AffinePointTarget { x, y }
214 }
215
216 fn curve_scalar_mul<C: Curve>(
217 &mut self,
218 p: &AffinePointTarget<C>,
219 n: &NonNativeTarget<C::ScalarField>,
220 ) -> AffinePointTarget<C> {
221 let bits = self.split_nonnative_to_bits(n);
222
223 let rando = (CurveScalar(C::ScalarField::rand()) * C::GENERATOR_PROJECTIVE).to_affine();
224 let randot = self.constant_affine_point(rando);
225 // Result starts at `rando`, which is later subtracted, because we don't support arithmetic with the zero point.
226 let mut result = self.add_virtual_affine_point_target();
227 self.connect_affine_point(&randot, &result);
228
229 let mut two_i_times_p = self.add_virtual_affine_point_target();
230 self.connect_affine_point(p, &two_i_times_p);
231
232 for &bit in bits.iter() {
233 let not_bit = self.not(bit);
234
235 let result_plus_2_i_p = self.curve_add(&result, &two_i_times_p);
236
237 let new_x_if_bit = self.mul_nonnative_by_bool(&result_plus_2_i_p.x, bit);
238 let new_x_if_not_bit = self.mul_nonnative_by_bool(&result.x, not_bit);
239 let new_y_if_bit = self.mul_nonnative_by_bool(&result_plus_2_i_p.y, bit);
240 let new_y_if_not_bit = self.mul_nonnative_by_bool(&result.y, not_bit);
241
242 let new_x = self.add_nonnative(&new_x_if_bit, &new_x_if_not_bit);
243 let new_y = self.add_nonnative(&new_y_if_bit, &new_y_if_not_bit);
244
245 result = AffinePointTarget { x: new_x, y: new_y };
246
247 two_i_times_p = self.curve_double(&two_i_times_p);
248 }
249
250 // Subtract off result's intial value of `rando`.
251 let neg_r = self.curve_neg(&randot);
252 result = self.curve_add(&result, &neg_r);
253
254 result
255 }
256}
257
258#[cfg(test)]
259mod tests {
260 use core::ops::Neg;
261
262 use anyhow::Result;
263 use plonky2::field::secp256k1_base::Secp256K1Base;
264 use plonky2::field::secp256k1_scalar::Secp256K1Scalar;
265 use plonky2::field::types::{Field, Sample};
266 use plonky2::iop::witness::PartialWitness;
267 use plonky2::plonk::circuit_builder::CircuitBuilder;
268 use plonky2::plonk::circuit_data::CircuitConfig;
269 use plonky2::plonk::config::{GenericConfig, PoseidonGoldilocksConfig};
270
271 use crate::curve::curve_types::{AffinePoint, Curve, CurveScalar};
272 use crate::curve::secp256k1::Secp256K1;
273 use crate::gadgets::curve::CircuitBuilderCurve;
274 use crate::gadgets::nonnative::CircuitBuilderNonNative;
275
276 #[test]
277 fn test_curve_point_is_valid() -> Result<()> {
278 const D: usize = 2;
279 type C = PoseidonGoldilocksConfig;
280 type F = <C as GenericConfig<D>>::F;
281
282 let config = CircuitConfig::standard_ecc_config();
283
284 let pw = PartialWitness::new();
285 let mut builder = CircuitBuilder::<F, D>::new(config);
286
287 let g = Secp256K1::GENERATOR_AFFINE;
288 let g_target = builder.constant_affine_point(g);
289 let neg_g_target = builder.curve_neg(&g_target);
290
291 builder.curve_assert_valid(&g_target);
292 builder.curve_assert_valid(&neg_g_target);
293
294 let data = builder.build::<C>();
295 let proof = data.prove(pw).unwrap();
296
297 data.verify(proof)
298 }
299
300 #[test]
301 #[should_panic]
302 fn test_curve_point_is_not_valid() {
303 const D: usize = 2;
304 type C = PoseidonGoldilocksConfig;
305 type F = <C as GenericConfig<D>>::F;
306
307 let config = CircuitConfig::standard_ecc_config();
308
309 let pw = PartialWitness::new();
310 let mut builder = CircuitBuilder::<F, D>::new(config);
311
312 let g = Secp256K1::GENERATOR_AFFINE;
313 let not_g = AffinePoint::<Secp256K1> {
314 x: g.x,
315 y: g.y + Secp256K1Base::ONE,
316 zero: g.zero,
317 };
318 let not_g_target = builder.constant_affine_point(not_g);
319
320 builder.curve_assert_valid(¬_g_target);
321
322 let data = builder.build::<C>();
323 let proof = data.prove(pw).unwrap();
324
325 data.verify(proof).unwrap()
326 }
327
328 #[test]
329 fn test_curve_double() -> Result<()> {
330 const D: usize = 2;
331 type C = PoseidonGoldilocksConfig;
332 type F = <C as GenericConfig<D>>::F;
333
334 let config = CircuitConfig::standard_ecc_config();
335
336 let pw = PartialWitness::new();
337 let mut builder = CircuitBuilder::<F, D>::new(config);
338
339 let g = Secp256K1::GENERATOR_AFFINE;
340 let g_target = builder.constant_affine_point(g);
341 let neg_g_target = builder.curve_neg(&g_target);
342
343 let double_g = g.double();
344 let double_g_expected = builder.constant_affine_point(double_g);
345 builder.curve_assert_valid(&double_g_expected);
346
347 let double_neg_g = (-g).double();
348 let double_neg_g_expected = builder.constant_affine_point(double_neg_g);
349 builder.curve_assert_valid(&double_neg_g_expected);
350
351 let double_g_actual = builder.curve_double(&g_target);
352 let double_neg_g_actual = builder.curve_double(&neg_g_target);
353 builder.curve_assert_valid(&double_g_actual);
354 builder.curve_assert_valid(&double_neg_g_actual);
355
356 builder.connect_affine_point(&double_g_expected, &double_g_actual);
357 builder.connect_affine_point(&double_neg_g_expected, &double_neg_g_actual);
358
359 let data = builder.build::<C>();
360 let proof = data.prove(pw).unwrap();
361
362 data.verify(proof)
363 }
364
365 #[test]
366 fn test_curve_add() -> Result<()> {
367 const D: usize = 2;
368 type C = PoseidonGoldilocksConfig;
369 type F = <C as GenericConfig<D>>::F;
370
371 let config = CircuitConfig::standard_ecc_config();
372
373 let pw = PartialWitness::new();
374 let mut builder = CircuitBuilder::<F, D>::new(config);
375
376 let g = Secp256K1::GENERATOR_AFFINE;
377 let double_g = g.double();
378 let g_plus_2g = (g + double_g).to_affine();
379 let g_plus_2g_expected = builder.constant_affine_point(g_plus_2g);
380 builder.curve_assert_valid(&g_plus_2g_expected);
381
382 let g_target = builder.constant_affine_point(g);
383 let double_g_target = builder.curve_double(&g_target);
384 let g_plus_2g_actual = builder.curve_add(&g_target, &double_g_target);
385 builder.curve_assert_valid(&g_plus_2g_actual);
386
387 builder.connect_affine_point(&g_plus_2g_expected, &g_plus_2g_actual);
388
389 let data = builder.build::<C>();
390 let proof = data.prove(pw).unwrap();
391
392 data.verify(proof)
393 }
394
395 #[test]
396 fn test_curve_conditional_add() -> Result<()> {
397 const D: usize = 2;
398 type C = PoseidonGoldilocksConfig;
399 type F = <C as GenericConfig<D>>::F;
400
401 let config = CircuitConfig::standard_ecc_config();
402
403 let pw = PartialWitness::new();
404 let mut builder = CircuitBuilder::<F, D>::new(config);
405
406 let g = Secp256K1::GENERATOR_AFFINE;
407 let double_g = g.double();
408 let g_plus_2g = (g + double_g).to_affine();
409 let g_plus_2g_expected = builder.constant_affine_point(g_plus_2g);
410
411 let g_expected = builder.constant_affine_point(g);
412 let double_g_target = builder.curve_double(&g_expected);
413 let t = builder._true();
414 let f = builder._false();
415 let g_plus_2g_actual = builder.curve_conditional_add(&g_expected, &double_g_target, t);
416 let g_actual = builder.curve_conditional_add(&g_expected, &double_g_target, f);
417
418 builder.connect_affine_point(&g_plus_2g_expected, &g_plus_2g_actual);
419 builder.connect_affine_point(&g_expected, &g_actual);
420
421 let data = builder.build::<C>();
422 let proof = data.prove(pw).unwrap();
423
424 data.verify(proof)
425 }
426
427 #[test]
428 #[ignore]
429 fn test_curve_mul() -> Result<()> {
430 const D: usize = 2;
431 type C = PoseidonGoldilocksConfig;
432 type F = <C as GenericConfig<D>>::F;
433
434 let config = CircuitConfig::standard_ecc_config();
435
436 let pw = PartialWitness::new();
437 let mut builder = CircuitBuilder::<F, D>::new(config);
438
439 let g = Secp256K1::GENERATOR_PROJECTIVE.to_affine();
440 let five = Secp256K1Scalar::from_canonical_usize(5);
441 let neg_five = five.neg();
442 let neg_five_scalar = CurveScalar::<Secp256K1>(neg_five);
443 let neg_five_g = (neg_five_scalar * g.to_projective()).to_affine();
444 let neg_five_g_expected = builder.constant_affine_point(neg_five_g);
445 builder.curve_assert_valid(&neg_five_g_expected);
446
447 let g_target = builder.constant_affine_point(g);
448 let neg_five_target = builder.constant_nonnative(neg_five);
449 let neg_five_g_actual = builder.curve_scalar_mul(&g_target, &neg_five_target);
450 builder.curve_assert_valid(&neg_five_g_actual);
451
452 builder.connect_affine_point(&neg_five_g_expected, &neg_five_g_actual);
453
454 let data = builder.build::<C>();
455 let proof = data.prove(pw).unwrap();
456
457 data.verify(proof)
458 }
459
460 #[test]
461 #[ignore]
462 fn test_curve_random() -> Result<()> {
463 const D: usize = 2;
464 type C = PoseidonGoldilocksConfig;
465 type F = <C as GenericConfig<D>>::F;
466
467 let config = CircuitConfig::standard_ecc_config();
468
469 let pw = PartialWitness::new();
470 let mut builder = CircuitBuilder::<F, D>::new(config);
471
472 let rando =
473 (CurveScalar(Secp256K1Scalar::rand()) * Secp256K1::GENERATOR_PROJECTIVE).to_affine();
474 let randot = builder.constant_affine_point(rando);
475
476 let two_target = builder.constant_nonnative(Secp256K1Scalar::TWO);
477 let randot_doubled = builder.curve_double(&randot);
478 let randot_times_two = builder.curve_scalar_mul(&randot, &two_target);
479 builder.connect_affine_point(&randot_doubled, &randot_times_two);
480
481 let data = builder.build::<C>();
482 let proof = data.prove(pw).unwrap();
483
484 data.verify(proof)
485 }
486}