Nova/src/gadgets/ecc.rs
src/gadgets/ecc.rsRaw
1//! This module implements various elliptic curve gadgets
2#![allow(non_snake_case)]
3use crate::{
4 gadgets::utils::{
5 alloc_num_equals, alloc_one, alloc_zero, conditionally_select, conditionally_select2,
6 select_num_or_one, select_num_or_zero, select_num_or_zero2, select_one_or_diff2,
7 select_one_or_num2, select_zero_or_num2,
8 },
9 traits::Group,
10};
11use bellperson::{
12 gadgets::{
13 boolean::{AllocatedBit, Boolean},
14 num::AllocatedNum,
15 Assignment,
16 },
17 ConstraintSystem, SynthesisError,
18};
19use ff::{Field, PrimeField};
20
21/// AllocatedPoint provides an elliptic curve abstraction inside a circuit.
22#[derive(Clone)]
23pub struct AllocatedPoint<G>
24where
25 G: Group,
26{
27 pub(crate) x: AllocatedNum<G::Base>,
28 pub(crate) y: AllocatedNum<G::Base>,
29 pub(crate) is_infinity: AllocatedNum<G::Base>,
30}
31
32impl<G> AllocatedPoint<G>
33where
34 G: Group,
35{
36 /// Allocates a new point on the curve using coordinates provided by `coords`.
37 /// If coords = None, it allocates the default infinity point
38 pub fn alloc<CS>(
39 mut cs: CS,
40 coords: Option<(G::Base, G::Base, bool)>,
41 ) -> Result<Self, SynthesisError>
42 where
43 CS: ConstraintSystem<G::Base>,
44 {
45 let x = AllocatedNum::alloc(cs.namespace(|| "x"), || {
46 Ok(coords.map_or(G::Base::ZERO, |c| c.0))
47 })?;
48 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
49 Ok(coords.map_or(G::Base::ZERO, |c| c.1))
50 })?;
51 let is_infinity = AllocatedNum::alloc(cs.namespace(|| "is_infinity"), || {
52 Ok(if coords.map_or(true, |c| c.2) {
53 G::Base::ONE
54 } else {
55 G::Base::ZERO
56 })
57 })?;
58 cs.enforce(
59 || "is_infinity is bit",
60 |lc| lc + is_infinity.get_variable(),
61 |lc| lc + CS::one() - is_infinity.get_variable(),
62 |lc| lc,
63 );
64
65 Ok(AllocatedPoint { x, y, is_infinity })
66 }
67
68 /// Allocates a default point on the curve.
69 pub fn default<CS>(mut cs: CS) -> Result<Self, SynthesisError>
70 where
71 CS: ConstraintSystem<G::Base>,
72 {
73 let zero = alloc_zero(cs.namespace(|| "zero"))?;
74 let one = alloc_one(cs.namespace(|| "one"))?;
75
76 Ok(AllocatedPoint {
77 x: zero.clone(),
78 y: zero,
79 is_infinity: one,
80 })
81 }
82
83 /// Returns coordinates associated with the point.
84 pub fn get_coordinates(
85 &self,
86 ) -> (
87 &AllocatedNum<G::Base>,
88 &AllocatedNum<G::Base>,
89 &AllocatedNum<G::Base>,
90 ) {
91 (&self.x, &self.y, &self.is_infinity)
92 }
93
94 /// Negates the provided point
95 pub fn negate<CS: ConstraintSystem<G::Base>>(&self, mut cs: CS) -> Result<Self, SynthesisError> {
96 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || Ok(-*self.y.get_value().get()?))?;
97
98 cs.enforce(
99 || "check y = - self.y",
100 |lc| lc + self.y.get_variable(),
101 |lc| lc + CS::one(),
102 |lc| lc - y.get_variable(),
103 );
104
105 Ok(Self {
106 x: self.x.clone(),
107 y,
108 is_infinity: self.is_infinity.clone(),
109 })
110 }
111
112 /// Add two points (may be equal)
113 pub fn add<CS: ConstraintSystem<G::Base>>(
114 &self,
115 mut cs: CS,
116 other: &AllocatedPoint<G>,
117 ) -> Result<Self, SynthesisError> {
118 // Compute boolean equal indicating if self = other
119
120 let equal_x = alloc_num_equals(
121 cs.namespace(|| "check self.x == other.x"),
122 &self.x,
123 &other.x,
124 )?;
125
126 let equal_y = alloc_num_equals(
127 cs.namespace(|| "check self.y == other.y"),
128 &self.y,
129 &other.y,
130 )?;
131
132 // Compute the result of the addition and the result of double self
133 let result_from_add = self.add_internal(cs.namespace(|| "add internal"), other, &equal_x)?;
134 let result_from_double = self.double(cs.namespace(|| "double"))?;
135
136 // Output:
137 // If (self == other) {
138 // return double(self)
139 // }else {
140 // if (self.x == other.x){
141 // return infinity [negation]
142 // } else {
143 // return add(self, other)
144 // }
145 // }
146 let result_for_equal_x = AllocatedPoint::select_point_or_infinity(
147 cs.namespace(|| "equal_y ? result_from_double : infinity"),
148 &result_from_double,
149 &Boolean::from(equal_y),
150 )?;
151
152 AllocatedPoint::conditionally_select(
153 cs.namespace(|| "equal ? result_from_double : result_from_add"),
154 &result_for_equal_x,
155 &result_from_add,
156 &Boolean::from(equal_x),
157 )
158 }
159
160 /// Adds other point to this point and returns the result. Assumes that the two points are
161 /// different and that both other.is_infinity and this.is_infinty are bits
162 pub fn add_internal<CS: ConstraintSystem<G::Base>>(
163 &self,
164 mut cs: CS,
165 other: &AllocatedPoint<G>,
166 equal_x: &AllocatedBit,
167 ) -> Result<Self, SynthesisError> {
168 //************************************************************************/
169 // lambda = (other.y - self.y) * (other.x - self.x).invert().unwrap();
170 //************************************************************************/
171 // First compute (other.x - self.x).inverse()
172 // If either self or other are the infinity point or self.x = other.x then compute bogus values
173 // Specifically,
174 // x_diff = self != inf && other != inf && self.x == other.x ? (other.x - self.x) : 1
175
176 // Compute self.is_infinity OR other.is_infinity =
177 // NOT(NOT(self.is_ifninity) AND NOT(other.is_infinity))
178 let at_least_one_inf = AllocatedNum::alloc(cs.namespace(|| "at least one inf"), || {
179 Ok(
180 G::Base::ONE
181 - (G::Base::ONE - *self.is_infinity.get_value().get()?)
182 * (G::Base::ONE - *other.is_infinity.get_value().get()?),
183 )
184 })?;
185 cs.enforce(
186 || "1 - at least one inf = (1-self.is_infinity) * (1-other.is_infinity)",
187 |lc| lc + CS::one() - self.is_infinity.get_variable(),
188 |lc| lc + CS::one() - other.is_infinity.get_variable(),
189 |lc| lc + CS::one() - at_least_one_inf.get_variable(),
190 );
191
192 // Now compute x_diff_is_actual = at_least_one_inf OR equal_x
193 let x_diff_is_actual =
194 AllocatedNum::alloc(cs.namespace(|| "allocate x_diff_is_actual"), || {
195 Ok(if *equal_x.get_value().get()? {
196 G::Base::ONE
197 } else {
198 *at_least_one_inf.get_value().get()?
199 })
200 })?;
201 cs.enforce(
202 || "1 - x_diff_is_actual = (1-equal_x) * (1-at_least_one_inf)",
203 |lc| lc + CS::one() - at_least_one_inf.get_variable(),
204 |lc| lc + CS::one() - equal_x.get_variable(),
205 |lc| lc + CS::one() - x_diff_is_actual.get_variable(),
206 );
207
208 // x_diff = 1 if either self.is_infinity or other.is_infinity or self.x = other.x else self.x -
209 // other.x
210 let x_diff = select_one_or_diff2(
211 cs.namespace(|| "Compute x_diff"),
212 &other.x,
213 &self.x,
214 &x_diff_is_actual,
215 )?;
216
217 let lambda = AllocatedNum::alloc(cs.namespace(|| "lambda"), || {
218 let x_diff_inv = if *x_diff_is_actual.get_value().get()? == G::Base::ONE {
219 // Set to default
220 G::Base::ONE
221 } else {
222 // Set to the actual inverse
223 (*other.x.get_value().get()? - *self.x.get_value().get()?)
224 .invert()
225 .unwrap()
226 };
227
228 Ok((*other.y.get_value().get()? - *self.y.get_value().get()?) * x_diff_inv)
229 })?;
230 cs.enforce(
231 || "Check that lambda is correct",
232 |lc| lc + lambda.get_variable(),
233 |lc| lc + x_diff.get_variable(),
234 |lc| lc + other.y.get_variable() - self.y.get_variable(),
235 );
236
237 //************************************************************************/
238 // x = lambda * lambda - self.x - other.x;
239 //************************************************************************/
240 let x = AllocatedNum::alloc(cs.namespace(|| "x"), || {
241 Ok(
242 *lambda.get_value().get()? * lambda.get_value().get()?
243 - *self.x.get_value().get()?
244 - *other.x.get_value().get()?,
245 )
246 })?;
247 cs.enforce(
248 || "check that x is correct",
249 |lc| lc + lambda.get_variable(),
250 |lc| lc + lambda.get_variable(),
251 |lc| lc + x.get_variable() + self.x.get_variable() + other.x.get_variable(),
252 );
253
254 //************************************************************************/
255 // y = lambda * (self.x - x) - self.y;
256 //************************************************************************/
257 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
258 Ok(
259 *lambda.get_value().get()? * (*self.x.get_value().get()? - *x.get_value().get()?)
260 - *self.y.get_value().get()?,
261 )
262 })?;
263
264 cs.enforce(
265 || "Check that y is correct",
266 |lc| lc + lambda.get_variable(),
267 |lc| lc + self.x.get_variable() - x.get_variable(),
268 |lc| lc + y.get_variable() + self.y.get_variable(),
269 );
270
271 //************************************************************************/
272 // We only return the computed x, y if neither of the points is infinity and self.x != other.y
273 // if self.is_infinity return other.clone()
274 // elif other.is_infinity return self.clone()
275 // elif self.x == other.x return infinity
276 // Otherwise return the computed points.
277 //************************************************************************/
278 // Now compute the output x
279
280 let x1 = conditionally_select2(
281 cs.namespace(|| "x1 = other.is_infinity ? self.x : x"),
282 &self.x,
283 &x,
284 &other.is_infinity,
285 )?;
286
287 let x = conditionally_select2(
288 cs.namespace(|| "x = self.is_infinity ? other.x : x1"),
289 &other.x,
290 &x1,
291 &self.is_infinity,
292 )?;
293
294 let y1 = conditionally_select2(
295 cs.namespace(|| "y1 = other.is_infinity ? self.y : y"),
296 &self.y,
297 &y,
298 &other.is_infinity,
299 )?;
300
301 let y = conditionally_select2(
302 cs.namespace(|| "y = self.is_infinity ? other.y : y1"),
303 &other.y,
304 &y1,
305 &self.is_infinity,
306 )?;
307
308 let is_infinity1 = select_num_or_zero2(
309 cs.namespace(|| "is_infinity1 = other.is_infinity ? self.is_infinity : 0"),
310 &self.is_infinity,
311 &other.is_infinity,
312 )?;
313
314 let is_infinity = conditionally_select2(
315 cs.namespace(|| "is_infinity = self.is_infinity ? other.is_infinity : is_infinity1"),
316 &other.is_infinity,
317 &is_infinity1,
318 &self.is_infinity,
319 )?;
320
321 Ok(Self { x, y, is_infinity })
322 }
323
324 /// Doubles the supplied point.
325 pub fn double<CS: ConstraintSystem<G::Base>>(&self, mut cs: CS) -> Result<Self, SynthesisError> {
326 //*************************************************************/
327 // lambda = (G::Base::from(3) * self.x * self.x + G::A())
328 // * (G::Base::from(2)) * self.y).invert().unwrap();
329 /*************************************************************/
330
331 // Compute tmp = (G::Base::ONE + G::Base::ONE)* self.y ? self != inf : 1
332 let tmp_actual = AllocatedNum::alloc(cs.namespace(|| "tmp_actual"), || {
333 Ok(*self.y.get_value().get()? + *self.y.get_value().get()?)
334 })?;
335 cs.enforce(
336 || "check tmp_actual",
337 |lc| lc + CS::one() + CS::one(),
338 |lc| lc + self.y.get_variable(),
339 |lc| lc + tmp_actual.get_variable(),
340 );
341
342 let tmp = select_one_or_num2(cs.namespace(|| "tmp"), &tmp_actual, &self.is_infinity)?;
343
344 // Now compute lambda as (G::Base::from(3) * self.x * self.x + G::A()) * tmp_inv
345
346 let prod_1 = AllocatedNum::alloc(cs.namespace(|| "alloc prod 1"), || {
347 Ok(G::Base::from(3) * self.x.get_value().get()? * self.x.get_value().get()?)
348 })?;
349 cs.enforce(
350 || "Check prod 1",
351 |lc| lc + (G::Base::from(3), self.x.get_variable()),
352 |lc| lc + self.x.get_variable(),
353 |lc| lc + prod_1.get_variable(),
354 );
355
356 let lambda = AllocatedNum::alloc(cs.namespace(|| "alloc lambda"), || {
357 let tmp_inv = if *self.is_infinity.get_value().get()? == G::Base::ONE {
358 // Return default value 1
359 G::Base::ONE
360 } else {
361 // Return the actual inverse
362 (*tmp.get_value().get()?).invert().unwrap()
363 };
364
365 Ok(tmp_inv * (*prod_1.get_value().get()? + G::get_curve_params().0))
366 })?;
367
368 cs.enforce(
369 || "Check lambda",
370 |lc| lc + tmp.get_variable(),
371 |lc| lc + lambda.get_variable(),
372 |lc| lc + prod_1.get_variable() + (G::get_curve_params().0, CS::one()),
373 );
374
375 /*************************************************************/
376 // x = lambda * lambda - self.x - self.x;
377 /*************************************************************/
378
379 let x = AllocatedNum::alloc(cs.namespace(|| "x"), || {
380 Ok(
381 ((*lambda.get_value().get()?) * (*lambda.get_value().get()?))
382 - *self.x.get_value().get()?
383 - self.x.get_value().get()?,
384 )
385 })?;
386 cs.enforce(
387 || "Check x",
388 |lc| lc + lambda.get_variable(),
389 |lc| lc + lambda.get_variable(),
390 |lc| lc + x.get_variable() + self.x.get_variable() + self.x.get_variable(),
391 );
392
393 /*************************************************************/
394 // y = lambda * (self.x - x) - self.y;
395 /*************************************************************/
396
397 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
398 Ok(
399 (*lambda.get_value().get()?) * (*self.x.get_value().get()? - x.get_value().get()?)
400 - self.y.get_value().get()?,
401 )
402 })?;
403 cs.enforce(
404 || "Check y",
405 |lc| lc + lambda.get_variable(),
406 |lc| lc + self.x.get_variable() - x.get_variable(),
407 |lc| lc + y.get_variable() + self.y.get_variable(),
408 );
409
410 /*************************************************************/
411 // Only return the computed x and y if the point is not infinity
412 /*************************************************************/
413
414 // x
415 let x = select_zero_or_num2(cs.namespace(|| "final x"), &x, &self.is_infinity)?;
416
417 // y
418 let y = select_zero_or_num2(cs.namespace(|| "final y"), &y, &self.is_infinity)?;
419
420 // is_infinity
421 let is_infinity = self.is_infinity.clone();
422
423 Ok(Self { x, y, is_infinity })
424 }
425
426 /// A gadget for scalar multiplication, optimized to use incomplete addition law.
427 /// The optimization here is analogous to https://github.com/arkworks-rs/r1cs-std/blob/6d64f379a27011b3629cf4c9cb38b7b7b695d5a0/src/groups/curves/short_weierstrass/mod.rs#L295,
428 /// except we use complete addition law over affine coordinates instead of projective coordinates for the tail bits
429 pub fn scalar_mul<CS: ConstraintSystem<G::Base>>(
430 &self,
431 mut cs: CS,
432 scalar_bits: &[AllocatedBit],
433 ) -> Result<Self, SynthesisError> {
434 let split_len = core::cmp::min(scalar_bits.len(), (G::Base::NUM_BITS - 2) as usize);
435 let (incomplete_bits, complete_bits) = scalar_bits.split_at(split_len);
436
437 // we convert AllocatedPoint into AllocatedPointNonInfinity; we deal with the case where self.is_infinity = 1 below
438 let mut p = AllocatedPointNonInfinity::from_allocated_point(self);
439
440 // we assume the first bit to be 1, so we must initialize acc to self and double it
441 // we remove this assumption below
442 let mut acc = p;
443 p = acc.double_incomplete(cs.namespace(|| "double"))?;
444
445 // perform the double-and-add loop to compute the scalar mul using incomplete addition law
446 for (i, bit) in incomplete_bits.iter().enumerate().skip(1) {
447 let temp = acc.add_incomplete(cs.namespace(|| format!("add {i}")), &p)?;
448 acc = AllocatedPointNonInfinity::conditionally_select(
449 cs.namespace(|| format!("acc_iteration_{i}")),
450 &temp,
451 &acc,
452 &Boolean::from(bit.clone()),
453 )?;
454
455 p = p.double_incomplete(cs.namespace(|| format!("double {i}")))?;
456 }
457
458 // convert back to AllocatedPoint
459 let res = {
460 // we set acc.is_infinity = self.is_infinity
461 let acc = acc.to_allocated_point(&self.is_infinity)?;
462
463 // we remove the initial slack if bits[0] is as not as assumed (i.e., it is not 1)
464 let acc_minus_initial = {
465 let neg = self.negate(cs.namespace(|| "negate"))?;
466 acc.add(cs.namespace(|| "res minus self"), &neg)
467 }?;
468
469 AllocatedPoint::conditionally_select(
470 cs.namespace(|| "remove slack if necessary"),
471 &acc,
472 &acc_minus_initial,
473 &Boolean::from(scalar_bits[0].clone()),
474 )?
475 };
476
477 // when self.is_infinity = 1, return the default point, else return res
478 // we already set res.is_infinity to be self.is_infinity, so we do not need to set it here
479 let default = Self::default(cs.namespace(|| "default"))?;
480 let x = conditionally_select2(
481 cs.namespace(|| "check if self.is_infinity is zero (x)"),
482 &default.x,
483 &res.x,
484 &self.is_infinity,
485 )?;
486
487 let y = conditionally_select2(
488 cs.namespace(|| "check if self.is_infinity is zero (y)"),
489 &default.y,
490 &res.y,
491 &self.is_infinity,
492 )?;
493
494 // we now perform the remaining scalar mul using complete addition law
495 let mut acc = AllocatedPoint {
496 x,
497 y,
498 is_infinity: res.is_infinity,
499 };
500 let mut p_complete = p.to_allocated_point(&self.is_infinity)?;
501
502 for (i, bit) in complete_bits.iter().enumerate() {
503 let temp = acc.add(cs.namespace(|| format!("add_complete {i}")), &p_complete)?;
504 acc = AllocatedPoint::conditionally_select(
505 cs.namespace(|| format!("acc_complete_iteration_{i}")),
506 &temp,
507 &acc,
508 &Boolean::from(bit.clone()),
509 )?;
510
511 p_complete = p_complete.double(cs.namespace(|| format!("double_complete {i}")))?;
512 }
513
514 Ok(acc)
515 }
516
517 /// If condition outputs a otherwise outputs b
518 pub fn conditionally_select<CS: ConstraintSystem<G::Base>>(
519 mut cs: CS,
520 a: &Self,
521 b: &Self,
522 condition: &Boolean,
523 ) -> Result<Self, SynthesisError> {
524 let x = conditionally_select(cs.namespace(|| "select x"), &a.x, &b.x, condition)?;
525
526 let y = conditionally_select(cs.namespace(|| "select y"), &a.y, &b.y, condition)?;
527
528 let is_infinity = conditionally_select(
529 cs.namespace(|| "select is_infinity"),
530 &a.is_infinity,
531 &b.is_infinity,
532 condition,
533 )?;
534
535 Ok(Self { x, y, is_infinity })
536 }
537
538 /// If condition outputs a otherwise infinity
539 pub fn select_point_or_infinity<CS: ConstraintSystem<G::Base>>(
540 mut cs: CS,
541 a: &Self,
542 condition: &Boolean,
543 ) -> Result<Self, SynthesisError> {
544 let x = select_num_or_zero(cs.namespace(|| "select x"), &a.x, condition)?;
545
546 let y = select_num_or_zero(cs.namespace(|| "select y"), &a.y, condition)?;
547
548 let is_infinity = select_num_or_one(
549 cs.namespace(|| "select is_infinity"),
550 &a.is_infinity,
551 condition,
552 )?;
553
554 Ok(Self { x, y, is_infinity })
555 }
556}
557
558#[derive(Clone)]
559/// AllocatedPoint but one that is guaranteed to be not infinity
560pub struct AllocatedPointNonInfinity<G>
561where
562 G: Group,
563{
564 x: AllocatedNum<G::Base>,
565 y: AllocatedNum<G::Base>,
566}
567
568impl<G> AllocatedPointNonInfinity<G>
569where
570 G: Group,
571{
572 /// Creates a new AllocatedPointNonInfinity from the specified coordinates
573 pub fn new(x: AllocatedNum<G::Base>, y: AllocatedNum<G::Base>) -> Self {
574 Self { x, y }
575 }
576
577 /// Allocates a new point on the curve using coordinates provided by `coords`.
578 pub fn alloc<CS>(mut cs: CS, coords: Option<(G::Base, G::Base)>) -> Result<Self, SynthesisError>
579 where
580 CS: ConstraintSystem<G::Base>,
581 {
582 let x = AllocatedNum::alloc(cs.namespace(|| "x"), || {
583 coords.map_or(Err(SynthesisError::AssignmentMissing), |c| Ok(c.0))
584 })?;
585 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
586 coords.map_or(Err(SynthesisError::AssignmentMissing), |c| Ok(c.1))
587 })?;
588
589 Ok(Self { x, y })
590 }
591
592 /// Turns an AllocatedPoint into an AllocatedPointNonInfinity (assumes it is not infinity)
593 pub fn from_allocated_point(p: &AllocatedPoint<G>) -> Self {
594 Self {
595 x: p.x.clone(),
596 y: p.y.clone(),
597 }
598 }
599
600 /// Returns an AllocatedPoint from an AllocatedPointNonInfinity
601 pub fn to_allocated_point(
602 &self,
603 is_infinity: &AllocatedNum<G::Base>,
604 ) -> Result<AllocatedPoint<G>, SynthesisError> {
605 Ok(AllocatedPoint {
606 x: self.x.clone(),
607 y: self.y.clone(),
608 is_infinity: is_infinity.clone(),
609 })
610 }
611
612 /// Returns coordinates associated with the point.
613 pub fn get_coordinates(&self) -> (&AllocatedNum<G::Base>, &AllocatedNum<G::Base>) {
614 (&self.x, &self.y)
615 }
616
617 /// Add two points assuming self != +/- other
618 pub fn add_incomplete<CS>(&self, mut cs: CS, other: &Self) -> Result<Self, SynthesisError>
619 where
620 CS: ConstraintSystem<G::Base>,
621 {
622 // allocate a free variable that an honest prover sets to lambda = (y2-y1)/(x2-x1)
623 let lambda = AllocatedNum::alloc(cs.namespace(|| "lambda"), || {
624 if *other.x.get_value().get()? == *self.x.get_value().get()? {
625 Ok(G::Base::ONE)
626 } else {
627 Ok(
628 (*other.y.get_value().get()? - *self.y.get_value().get()?)
629 * (*other.x.get_value().get()? - *self.x.get_value().get()?)
630 .invert()
631 .unwrap(),
632 )
633 }
634 })?;
635 cs.enforce(
636 || "Check that lambda is computed correctly",
637 |lc| lc + lambda.get_variable(),
638 |lc| lc + other.x.get_variable() - self.x.get_variable(),
639 |lc| lc + other.y.get_variable() - self.y.get_variable(),
640 );
641
642 //************************************************************************/
643 // x = lambda * lambda - self.x - other.x;
644 //************************************************************************/
645 let x = AllocatedNum::alloc(cs.namespace(|| "x"), || {
646 Ok(
647 *lambda.get_value().get()? * lambda.get_value().get()?
648 - *self.x.get_value().get()?
649 - *other.x.get_value().get()?,
650 )
651 })?;
652 cs.enforce(
653 || "check that x is correct",
654 |lc| lc + lambda.get_variable(),
655 |lc| lc + lambda.get_variable(),
656 |lc| lc + x.get_variable() + self.x.get_variable() + other.x.get_variable(),
657 );
658
659 //************************************************************************/
660 // y = lambda * (self.x - x) - self.y;
661 //************************************************************************/
662 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
663 Ok(
664 *lambda.get_value().get()? * (*self.x.get_value().get()? - *x.get_value().get()?)
665 - *self.y.get_value().get()?,
666 )
667 })?;
668
669 cs.enforce(
670 || "Check that y is correct",
671 |lc| lc + lambda.get_variable(),
672 |lc| lc + self.x.get_variable() - x.get_variable(),
673 |lc| lc + y.get_variable() + self.y.get_variable(),
674 );
675
676 Ok(Self { x, y })
677 }
678
679 /// doubles the point; since this is called with a point not at infinity, it is guaranteed to be not infinity
680 pub fn double_incomplete<CS>(&self, mut cs: CS) -> Result<Self, SynthesisError>
681 where
682 CS: ConstraintSystem<G::Base>,
683 {
684 // lambda = (3 x^2 + a) / 2 * y
685
686 let x_sq = self.x.square(cs.namespace(|| "x_sq"))?;
687
688 let lambda = AllocatedNum::alloc(cs.namespace(|| "lambda"), || {
689 let n = G::Base::from(3) * x_sq.get_value().get()? + G::get_curve_params().0;
690 let d = G::Base::from(2) * *self.y.get_value().get()?;
691 if d == G::Base::ZERO {
692 Ok(G::Base::ONE)
693 } else {
694 Ok(n * d.invert().unwrap())
695 }
696 })?;
697 cs.enforce(
698 || "Check that lambda is computed correctly",
699 |lc| lc + lambda.get_variable(),
700 |lc| lc + (G::Base::from(2), self.y.get_variable()),
701 |lc| lc + (G::Base::from(3), x_sq.get_variable()) + (G::get_curve_params().0, CS::one()),
702 );
703
704 let x = AllocatedNum::alloc(cs.namespace(|| "x"), || {
705 Ok(
706 *lambda.get_value().get()? * *lambda.get_value().get()?
707 - *self.x.get_value().get()?
708 - *self.x.get_value().get()?,
709 )
710 })?;
711
712 cs.enforce(
713 || "check that x is correct",
714 |lc| lc + lambda.get_variable(),
715 |lc| lc + lambda.get_variable(),
716 |lc| lc + x.get_variable() + (G::Base::from(2), self.x.get_variable()),
717 );
718
719 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
720 Ok(
721 *lambda.get_value().get()? * (*self.x.get_value().get()? - *x.get_value().get()?)
722 - *self.y.get_value().get()?,
723 )
724 })?;
725
726 cs.enforce(
727 || "Check that y is correct",
728 |lc| lc + lambda.get_variable(),
729 |lc| lc + self.x.get_variable() - x.get_variable(),
730 |lc| lc + y.get_variable() + self.y.get_variable(),
731 );
732
733 Ok(Self { x, y })
734 }
735
736 /// If condition outputs a otherwise outputs b
737 pub fn conditionally_select<CS: ConstraintSystem<G::Base>>(
738 mut cs: CS,
739 a: &Self,
740 b: &Self,
741 condition: &Boolean,
742 ) -> Result<Self, SynthesisError> {
743 let x = conditionally_select(cs.namespace(|| "select x"), &a.x, &b.x, condition)?;
744 let y = conditionally_select(cs.namespace(|| "select y"), &a.y, &b.y, condition)?;
745
746 Ok(Self { x, y })
747 }
748}
749
750#[cfg(test)]
751mod tests {
752 use super::*;
753 use crate::bellperson::{
754 r1cs::{NovaShape, NovaWitness},
755 {shape_cs::ShapeCS, solver::SatisfyingAssignment},
756 };
757 use crate::provider::bn256_grumpkin::{bn256, grumpkin};
758 use ff::{Field, PrimeFieldBits};
759 use pasta_curves::{arithmetic::CurveAffine, group::Curve, pallas, vesta};
760 use rand::rngs::OsRng;
761
762 #[derive(Debug, Clone)]
763 pub struct Point<G>
764 where
765 G: Group,
766 {
767 x: G::Base,
768 y: G::Base,
769 is_infinity: bool,
770 }
771
772 impl<G> Point<G>
773 where
774 G: Group,
775 {
776 pub fn new(x: G::Base, y: G::Base, is_infinity: bool) -> Self {
777 Self { x, y, is_infinity }
778 }
779
780 pub fn random_vartime() -> Self {
781 loop {
782 let x = G::Base::random(&mut OsRng);
783 let y = (x.square() * x + G::get_curve_params().1).sqrt();
784 if y.is_some().unwrap_u8() == 1 {
785 return Self {
786 x,
787 y: y.unwrap(),
788 is_infinity: false,
789 };
790 }
791 }
792 }
793
794 /// Add any two points
795 pub fn add(&self, other: &Point<G>) -> Self {
796 if self.x == other.x {
797 // If self == other then call double
798 if self.y == other.y {
799 self.double()
800 } else {
801 // if self.x == other.x and self.y != other.y then return infinity
802 Self {
803 x: G::Base::ZERO,
804 y: G::Base::ZERO,
805 is_infinity: true,
806 }
807 }
808 } else {
809 self.add_internal(other)
810 }
811 }
812
813 /// Add two different points
814 pub fn add_internal(&self, other: &Point<G>) -> Self {
815 if self.is_infinity {
816 return other.clone();
817 }
818
819 if other.is_infinity {
820 return self.clone();
821 }
822
823 let lambda = (other.y - self.y) * (other.x - self.x).invert().unwrap();
824 let x = lambda * lambda - self.x - other.x;
825 let y = lambda * (self.x - x) - self.y;
826 Self {
827 x,
828 y,
829 is_infinity: false,
830 }
831 }
832
833 pub fn double(&self) -> Self {
834 if self.is_infinity {
835 return Self {
836 x: G::Base::ZERO,
837 y: G::Base::ZERO,
838 is_infinity: true,
839 };
840 }
841
842 let lambda = G::Base::from(3)
843 * self.x
844 * self.x
845 * ((G::Base::ONE + G::Base::ONE) * self.y).invert().unwrap();
846 let x = lambda * lambda - self.x - self.x;
847 let y = lambda * (self.x - x) - self.y;
848 Self {
849 x,
850 y,
851 is_infinity: false,
852 }
853 }
854
855 pub fn scalar_mul(&self, scalar: &G::Scalar) -> Self {
856 let mut res = Self {
857 x: G::Base::ZERO,
858 y: G::Base::ZERO,
859 is_infinity: true,
860 };
861
862 let bits = scalar.to_le_bits();
863 for i in (0..bits.len()).rev() {
864 res = res.double();
865 if bits[i] {
866 res = self.add(&res);
867 }
868 }
869 res
870 }
871 }
872
873 // Allocate a random point. Only used for testing
874 pub fn alloc_random_point<G: Group, CS: ConstraintSystem<G::Base>>(
875 mut cs: CS,
876 ) -> Result<AllocatedPoint<G>, SynthesisError> {
877 // get a random point
878 let p = Point::<G>::random_vartime();
879 AllocatedPoint::alloc(cs.namespace(|| "alloc p"), Some((p.x, p.y, p.is_infinity)))
880 }
881
882 /// Make the point io
883 pub fn inputize_allocted_point<G: Group, CS: ConstraintSystem<G::Base>>(
884 p: &AllocatedPoint<G>,
885 mut cs: CS,
886 ) -> Result<(), SynthesisError> {
887 let _ = p.x.inputize(cs.namespace(|| "Input point.x"));
888 let _ = p.y.inputize(cs.namespace(|| "Input point.y"));
889 let _ = p
890 .is_infinity
891 .inputize(cs.namespace(|| "Input point.is_infinity"));
892 Ok(())
893 }
894
895 #[test]
896 fn test_ecc_ops() {
897 test_ecc_ops_with::<pallas::Affine, pallas::Point>();
898 test_ecc_ops_with::<vesta::Affine, vesta::Point>();
899
900 test_ecc_ops_with::<bn256::Affine, bn256::Point>();
901 test_ecc_ops_with::<grumpkin::Affine, grumpkin::Point>();
902 }
903
904 fn test_ecc_ops_with<C, G>()
905 where
906 C: CurveAffine<Base = G::Base, ScalarExt = G::Scalar>,
907 G: Group,
908 {
909 // perform some curve arithmetic
910 let a = Point::<G>::random_vartime();
911 let b = Point::<G>::random_vartime();
912 let c = a.add(&b);
913 let d = a.double();
914 let s = <G as Group>::Scalar::random(&mut OsRng);
915 let e = a.scalar_mul(&s);
916
917 // perform the same computation by translating to curve types
918 let a_curve = C::from_xy(
919 C::Base::from_repr(a.x.to_repr()).unwrap(),
920 C::Base::from_repr(a.y.to_repr()).unwrap(),
921 )
922 .unwrap();
923 let b_curve = C::from_xy(
924 C::Base::from_repr(b.x.to_repr()).unwrap(),
925 C::Base::from_repr(b.y.to_repr()).unwrap(),
926 )
927 .unwrap();
928 let c_curve = (a_curve + b_curve).to_affine();
929 let d_curve = (a_curve + a_curve).to_affine();
930 let e_curve = a_curve
931 .mul(C::Scalar::from_repr(s.to_repr()).unwrap())
932 .to_affine();
933
934 // transform c, d, and e into curve types
935 let c_curve_2 = C::from_xy(
936 C::Base::from_repr(c.x.to_repr()).unwrap(),
937 C::Base::from_repr(c.y.to_repr()).unwrap(),
938 )
939 .unwrap();
940 let d_curve_2 = C::from_xy(
941 C::Base::from_repr(d.x.to_repr()).unwrap(),
942 C::Base::from_repr(d.y.to_repr()).unwrap(),
943 )
944 .unwrap();
945 let e_curve_2 = C::from_xy(
946 C::Base::from_repr(e.x.to_repr()).unwrap(),
947 C::Base::from_repr(e.y.to_repr()).unwrap(),
948 )
949 .unwrap();
950
951 // check that we have the same outputs
952 assert_eq!(c_curve, c_curve_2);
953 assert_eq!(d_curve, d_curve_2);
954 assert_eq!(e_curve, e_curve_2);
955 }
956
957 fn synthesize_smul<G, CS>(mut cs: CS) -> (AllocatedPoint<G>, AllocatedPoint<G>, G::Scalar)
958 where
959 G: Group,
960 CS: ConstraintSystem<G::Base>,
961 {
962 let a = alloc_random_point(cs.namespace(|| "a")).unwrap();
963 inputize_allocted_point(&a, cs.namespace(|| "inputize a")).unwrap();
964
965 let s = G::Scalar::random(&mut OsRng);
966 // Allocate bits for s
967 let bits: Vec<AllocatedBit> = s
968 .to_le_bits()
969 .into_iter()
970 .enumerate()
971 .map(|(i, bit)| AllocatedBit::alloc(cs.namespace(|| format!("bit {i}")), Some(bit)))
972 .collect::<Result<Vec<AllocatedBit>, SynthesisError>>()
973 .unwrap();
974 let e = a.scalar_mul(cs.namespace(|| "Scalar Mul"), &bits).unwrap();
975 inputize_allocted_point(&e, cs.namespace(|| "inputize e")).unwrap();
976 (a, e, s)
977 }
978
979 #[test]
980 fn test_ecc_circuit_ops() {
981 test_ecc_circuit_ops_with::<pallas::Point, vesta::Point>();
982 test_ecc_circuit_ops_with::<vesta::Point, pallas::Point>();
983
984 test_ecc_circuit_ops_with::<bn256::Point, grumpkin::Point>();
985 test_ecc_circuit_ops_with::<grumpkin::Point, bn256::Point>();
986 }
987
988 fn test_ecc_circuit_ops_with<G1, G2>()
989 where
990 G1: Group<Base = <G2 as Group>::Scalar>,
991 G2: Group<Base = <G1 as Group>::Scalar>,
992 {
993 // First create the shape
994 let mut cs: ShapeCS<G2> = ShapeCS::new();
995 let _ = synthesize_smul::<G1, _>(cs.namespace(|| "synthesize"));
996 println!("Number of constraints: {}", cs.num_constraints());
997 let (shape, ck) = cs.r1cs_shape();
998
999 // Then the satisfying assignment
1000 let mut cs: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
1001 let (a, e, s) = synthesize_smul::<G1, _>(cs.namespace(|| "synthesize"));
1002 let (inst, witness) = cs.r1cs_instance_and_witness(&shape, &ck).unwrap();
1003
1004 let a_p: Point<G1> = Point::new(
1005 a.x.get_value().unwrap(),
1006 a.y.get_value().unwrap(),
1007 a.is_infinity.get_value().unwrap() == <G1 as Group>::Base::ONE,
1008 );
1009 let e_p: Point<G1> = Point::new(
1010 e.x.get_value().unwrap(),
1011 e.y.get_value().unwrap(),
1012 e.is_infinity.get_value().unwrap() == <G1 as Group>::Base::ONE,
1013 );
1014 let e_new = a_p.scalar_mul(&s);
1015 assert!(e_p.x == e_new.x && e_p.y == e_new.y);
1016 // Make sure that this is satisfiable
1017 assert!(shape.is_sat(&ck, &inst, &witness).is_ok());
1018 }
1019
1020 fn synthesize_add_equal<G, CS>(mut cs: CS) -> (AllocatedPoint<G>, AllocatedPoint<G>)
1021 where
1022 G: Group,
1023 CS: ConstraintSystem<G::Base>,
1024 {
1025 let a = alloc_random_point(cs.namespace(|| "a")).unwrap();
1026 inputize_allocted_point(&a, cs.namespace(|| "inputize a")).unwrap();
1027 let e = a.add(cs.namespace(|| "add a to a"), &a).unwrap();
1028 inputize_allocted_point(&e, cs.namespace(|| "inputize e")).unwrap();
1029 (a, e)
1030 }
1031
1032 #[test]
1033 fn test_ecc_circuit_add_equal() {
1034 test_ecc_circuit_add_equal_with::<pallas::Point, vesta::Point>();
1035 test_ecc_circuit_add_equal_with::<vesta::Point, pallas::Point>();
1036
1037 test_ecc_circuit_add_equal_with::<bn256::Point, grumpkin::Point>();
1038 test_ecc_circuit_add_equal_with::<grumpkin::Point, bn256::Point>();
1039 }
1040
1041 fn test_ecc_circuit_add_equal_with<G1, G2>()
1042 where
1043 G1: Group<Base = <G2 as Group>::Scalar>,
1044 G2: Group<Base = <G1 as Group>::Scalar>,
1045 {
1046 // First create the shape
1047 let mut cs: ShapeCS<G2> = ShapeCS::new();
1048 let _ = synthesize_add_equal::<G1, _>(cs.namespace(|| "synthesize add equal"));
1049 println!("Number of constraints: {}", cs.num_constraints());
1050 let (shape, ck) = cs.r1cs_shape();
1051
1052 // Then the satisfying assignment
1053 let mut cs: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
1054 let (a, e) = synthesize_add_equal::<G1, _>(cs.namespace(|| "synthesize add equal"));
1055 let (inst, witness) = cs.r1cs_instance_and_witness(&shape, &ck).unwrap();
1056 let a_p: Point<G1> = Point::new(
1057 a.x.get_value().unwrap(),
1058 a.y.get_value().unwrap(),
1059 a.is_infinity.get_value().unwrap() == <G1 as Group>::Base::ONE,
1060 );
1061 let e_p: Point<G1> = Point::new(
1062 e.x.get_value().unwrap(),
1063 e.y.get_value().unwrap(),
1064 e.is_infinity.get_value().unwrap() == <G1 as Group>::Base::ONE,
1065 );
1066 let e_new = a_p.add(&a_p);
1067 assert!(e_p.x == e_new.x && e_p.y == e_new.y);
1068 // Make sure that it is satisfiable
1069 assert!(shape.is_sat(&ck, &inst, &witness).is_ok());
1070 }
1071
1072 fn synthesize_add_negation<G, CS>(mut cs: CS) -> AllocatedPoint<G>
1073 where
1074 G: Group,
1075 CS: ConstraintSystem<G::Base>,
1076 {
1077 let a = alloc_random_point(cs.namespace(|| "a")).unwrap();
1078 inputize_allocted_point(&a, cs.namespace(|| "inputize a")).unwrap();
1079 let b = &mut a.clone();
1080 b.y = AllocatedNum::alloc(cs.namespace(|| "allocate negation of a"), || {
1081 Ok(G::Base::ZERO)
1082 })
1083 .unwrap();
1084 inputize_allocted_point(b, cs.namespace(|| "inputize b")).unwrap();
1085 let e = a.add(cs.namespace(|| "add a to b"), b).unwrap();
1086 e
1087 }
1088
1089 #[test]
1090 fn test_ecc_circuit_add_negation() {
1091 test_ecc_circuit_add_negation_with::<pallas::Point, vesta::Point>();
1092 test_ecc_circuit_add_negation_with::<vesta::Point, pallas::Point>();
1093
1094 test_ecc_circuit_add_negation_with::<bn256::Point, grumpkin::Point>();
1095 test_ecc_circuit_add_negation_with::<grumpkin::Point, bn256::Point>();
1096 }
1097
1098 fn test_ecc_circuit_add_negation_with<G1, G2>()
1099 where
1100 G1: Group<Base = <G2 as Group>::Scalar>,
1101 G2: Group<Base = <G1 as Group>::Scalar>,
1102 {
1103 // First create the shape
1104 let mut cs: ShapeCS<G2> = ShapeCS::new();
1105 let _ = synthesize_add_negation::<G1, _>(cs.namespace(|| "synthesize add equal"));
1106 println!("Number of constraints: {}", cs.num_constraints());
1107 let (shape, ck) = cs.r1cs_shape();
1108
1109 // Then the satisfying assignment
1110 let mut cs: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
1111 let e = synthesize_add_negation::<G1, _>(cs.namespace(|| "synthesize add negation"));
1112 let (inst, witness) = cs.r1cs_instance_and_witness(&shape, &ck).unwrap();
1113 let e_p: Point<G1> = Point::new(
1114 e.x.get_value().unwrap(),
1115 e.y.get_value().unwrap(),
1116 e.is_infinity.get_value().unwrap() == <G1 as Group>::Base::ONE,
1117 );
1118 assert!(e_p.is_infinity);
1119 // Make sure that it is satisfiable
1120 assert!(shape.is_sat(&ck, &inst, &witness).is_ok());
1121 }
1122}