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: Vec<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 ff::{Field, PrimeFieldBits};
758 use pasta_curves::{arithmetic::CurveAffine, group::Curve, pallas, vesta};
759 use rand::rngs::OsRng;
760
761 #[derive(Debug, Clone)]
762 pub struct Point<G>
763 where
764 G: Group,
765 {
766 x: G::Base,
767 y: G::Base,
768 is_infinity: bool,
769 }
770
771 #[cfg(test)]
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
901 fn test_ecc_ops_with<C, G>()
902 where
903 C: CurveAffine<Base = G::Base, ScalarExt = G::Scalar>,
904 G: Group,
905 {
906 // perform some curve arithmetic
907 let a = Point::<G>::random_vartime();
908 let b = Point::<G>::random_vartime();
909 let c = a.add(&b);
910 let d = a.double();
911 let s = <G as Group>::Scalar::random(&mut OsRng);
912 let e = a.scalar_mul(&s);
913
914 // perform the same computation by translating to curve types
915 let a_curve = C::from_xy(
916 C::Base::from_repr(a.x.to_repr()).unwrap(),
917 C::Base::from_repr(a.y.to_repr()).unwrap(),
918 )
919 .unwrap();
920 let b_curve = C::from_xy(
921 C::Base::from_repr(b.x.to_repr()).unwrap(),
922 C::Base::from_repr(b.y.to_repr()).unwrap(),
923 )
924 .unwrap();
925 let c_curve = (a_curve + b_curve).to_affine();
926 let d_curve = (a_curve + a_curve).to_affine();
927 let e_curve = a_curve
928 .mul(C::Scalar::from_repr(s.to_repr()).unwrap())
929 .to_affine();
930
931 // transform c, d, and e into curve types
932 let c_curve_2 = C::from_xy(
933 C::Base::from_repr(c.x.to_repr()).unwrap(),
934 C::Base::from_repr(c.y.to_repr()).unwrap(),
935 )
936 .unwrap();
937 let d_curve_2 = C::from_xy(
938 C::Base::from_repr(d.x.to_repr()).unwrap(),
939 C::Base::from_repr(d.y.to_repr()).unwrap(),
940 )
941 .unwrap();
942 let e_curve_2 = C::from_xy(
943 C::Base::from_repr(e.x.to_repr()).unwrap(),
944 C::Base::from_repr(e.y.to_repr()).unwrap(),
945 )
946 .unwrap();
947
948 // check that we have the same outputs
949 assert_eq!(c_curve, c_curve_2);
950 assert_eq!(d_curve, d_curve_2);
951 assert_eq!(e_curve, e_curve_2);
952 }
953
954 fn synthesize_smul<G, CS>(mut cs: CS) -> (AllocatedPoint<G>, AllocatedPoint<G>, G::Scalar)
955 where
956 G: Group,
957 CS: ConstraintSystem<G::Base>,
958 {
959 let a = alloc_random_point(cs.namespace(|| "a")).unwrap();
960 inputize_allocted_point(&a, cs.namespace(|| "inputize a")).unwrap();
961
962 let s = G::Scalar::random(&mut OsRng);
963 // Allocate bits for s
964 let bits: Vec<AllocatedBit> = s
965 .to_le_bits()
966 .into_iter()
967 .enumerate()
968 .map(|(i, bit)| AllocatedBit::alloc(cs.namespace(|| format!("bit {i}")), Some(bit)))
969 .collect::<Result<Vec<AllocatedBit>, SynthesisError>>()
970 .unwrap();
971 let e = a.scalar_mul(cs.namespace(|| "Scalar Mul"), bits).unwrap();
972 inputize_allocted_point(&e, cs.namespace(|| "inputize e")).unwrap();
973 (a, e, s)
974 }
975
976 #[test]
977 fn test_ecc_circuit_ops() {
978 test_ecc_circuit_ops_with::<pallas::Point, vesta::Point>();
979 test_ecc_circuit_ops_with::<vesta::Point, pallas::Point>();
980 }
981
982 fn test_ecc_circuit_ops_with<G1, G2>()
983 where
984 G1: Group<Base = <G2 as Group>::Scalar>,
985 G2: Group<Base = <G1 as Group>::Scalar>,
986 {
987 // First create the shape
988 let mut cs: ShapeCS<G2> = ShapeCS::new();
989 let _ = synthesize_smul::<G1, _>(cs.namespace(|| "synthesize"));
990 println!("Number of constraints: {}", cs.num_constraints());
991 let (shape, ck) = cs.r1cs_shape();
992
993 // Then the satisfying assignment
994 let mut cs: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
995 let (a, e, s) = synthesize_smul::<G1, _>(cs.namespace(|| "synthesize"));
996 let (inst, witness) = cs.r1cs_instance_and_witness(&shape, &ck).unwrap();
997
998 let a_p: Point<G1> = Point::new(
999 a.x.get_value().unwrap(),
1000 a.y.get_value().unwrap(),
1001 a.is_infinity.get_value().unwrap() == <G1 as Group>::Base::ONE,
1002 );
1003 let e_p: Point<G1> = Point::new(
1004 e.x.get_value().unwrap(),
1005 e.y.get_value().unwrap(),
1006 e.is_infinity.get_value().unwrap() == <G1 as Group>::Base::ONE,
1007 );
1008 let e_new = a_p.scalar_mul(&s);
1009 assert!(e_p.x == e_new.x && e_p.y == e_new.y);
1010 // Make sure that this is satisfiable
1011 assert!(shape.is_sat(&ck, &inst, &witness).is_ok());
1012 }
1013
1014 fn synthesize_add_equal<G, CS>(mut cs: CS) -> (AllocatedPoint<G>, AllocatedPoint<G>)
1015 where
1016 G: Group,
1017 CS: ConstraintSystem<G::Base>,
1018 {
1019 let a = alloc_random_point(cs.namespace(|| "a")).unwrap();
1020 inputize_allocted_point(&a, cs.namespace(|| "inputize a")).unwrap();
1021 let e = a.add(cs.namespace(|| "add a to a"), &a).unwrap();
1022 inputize_allocted_point(&e, cs.namespace(|| "inputize e")).unwrap();
1023 (a, e)
1024 }
1025
1026 #[test]
1027 fn test_ecc_circuit_add_equal() {
1028 test_ecc_circuit_add_equal_with::<pallas::Point, vesta::Point>();
1029 test_ecc_circuit_add_equal_with::<vesta::Point, pallas::Point>();
1030 }
1031
1032 fn test_ecc_circuit_add_equal_with<G1, G2>()
1033 where
1034 G1: Group<Base = <G2 as Group>::Scalar>,
1035 G2: Group<Base = <G1 as Group>::Scalar>,
1036 {
1037 // First create the shape
1038 let mut cs: ShapeCS<G2> = ShapeCS::new();
1039 let _ = synthesize_add_equal::<G1, _>(cs.namespace(|| "synthesize add equal"));
1040 println!("Number of constraints: {}", cs.num_constraints());
1041 let (shape, ck) = cs.r1cs_shape();
1042
1043 // Then the satisfying assignment
1044 let mut cs: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
1045 let (a, e) = synthesize_add_equal::<G1, _>(cs.namespace(|| "synthesize add equal"));
1046 let (inst, witness) = cs.r1cs_instance_and_witness(&shape, &ck).unwrap();
1047 let a_p: Point<G1> = Point::new(
1048 a.x.get_value().unwrap(),
1049 a.y.get_value().unwrap(),
1050 a.is_infinity.get_value().unwrap() == <G1 as Group>::Base::ONE,
1051 );
1052 let e_p: Point<G1> = Point::new(
1053 e.x.get_value().unwrap(),
1054 e.y.get_value().unwrap(),
1055 e.is_infinity.get_value().unwrap() == <G1 as Group>::Base::ONE,
1056 );
1057 let e_new = a_p.add(&a_p);
1058 assert!(e_p.x == e_new.x && e_p.y == e_new.y);
1059 // Make sure that it is satisfiable
1060 assert!(shape.is_sat(&ck, &inst, &witness).is_ok());
1061 }
1062
1063 fn synthesize_add_negation<G, CS>(mut cs: CS) -> AllocatedPoint<G>
1064 where
1065 G: Group,
1066 CS: ConstraintSystem<G::Base>,
1067 {
1068 let a = alloc_random_point(cs.namespace(|| "a")).unwrap();
1069 inputize_allocted_point(&a, cs.namespace(|| "inputize a")).unwrap();
1070 let mut b = &mut a.clone();
1071 b.y = AllocatedNum::alloc(cs.namespace(|| "allocate negation of a"), || {
1072 Ok(G::Base::ZERO)
1073 })
1074 .unwrap();
1075 inputize_allocted_point(b, cs.namespace(|| "inputize b")).unwrap();
1076 let e = a.add(cs.namespace(|| "add a to b"), b).unwrap();
1077 e
1078 }
1079
1080 #[test]
1081 fn test_ecc_circuit_add_negation() {
1082 test_ecc_circuit_add_negation_with::<pallas::Point, vesta::Point>();
1083 test_ecc_circuit_add_negation_with::<vesta::Point, pallas::Point>();
1084 }
1085
1086 fn test_ecc_circuit_add_negation_with<G1, G2>()
1087 where
1088 G1: Group<Base = <G2 as Group>::Scalar>,
1089 G2: Group<Base = <G1 as Group>::Scalar>,
1090 {
1091 // First create the shape
1092 let mut cs: ShapeCS<G2> = ShapeCS::new();
1093 let _ = synthesize_add_negation::<G1, _>(cs.namespace(|| "synthesize add equal"));
1094 println!("Number of constraints: {}", cs.num_constraints());
1095 let (shape, ck) = cs.r1cs_shape();
1096
1097 // Then the satisfying assignment
1098 let mut cs: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
1099 let e = synthesize_add_negation::<G1, _>(cs.namespace(|| "synthesize add negation"));
1100 let (inst, witness) = cs.r1cs_instance_and_witness(&shape, &ck).unwrap();
1101 let e_p: Point<G1> = Point::new(
1102 e.x.get_value().unwrap(),
1103 e.y.get_value().unwrap(),
1104 e.is_infinity.get_value().unwrap() == <G1 as Group>::Base::ONE,
1105 );
1106 assert!(e_p.is_infinity);
1107 // Make sure that it is satisfiable
1108 assert!(shape.is_sat(&ck, &inst, &witness).is_ok());
1109 }
1110}