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.clone();
443 p = p.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, EpAffine};
759 use rand::rngs::OsRng;
760 use std::ops::Mul;
761 type G1 = pasta_curves::pallas::Point;
762 type G2 = pasta_curves::vesta::Point;
763
764 #[derive(Debug, Clone)]
765 pub struct Point<G>
766 where
767 G: Group,
768 {
769 x: G::Base,
770 y: G::Base,
771 is_infinity: bool,
772 }
773
774 #[cfg(test)]
775 impl<G> Point<G>
776 where
777 G: Group,
778 {
779 pub fn new(x: G::Base, y: G::Base, is_infinity: bool) -> Self {
780 Self { x, y, is_infinity }
781 }
782
783 pub fn random_vartime() -> Self {
784 loop {
785 let x = G::Base::random(&mut OsRng);
786 let y = (x * x * x + G::Base::from(5)).sqrt();
787 if y.is_some().unwrap_u8() == 1 {
788 return Self {
789 x,
790 y: y.unwrap(),
791 is_infinity: false,
792 };
793 }
794 }
795 }
796
797 /// Add any two points
798 pub fn add(&self, other: &Point<G>) -> Self {
799 if self.x == other.x {
800 // If self == other then call double
801 if self.y == other.y {
802 self.double()
803 } else {
804 // if self.x == other.x and self.y != other.y then return infinity
805 Self {
806 x: G::Base::zero(),
807 y: G::Base::zero(),
808 is_infinity: true,
809 }
810 }
811 } else {
812 self.add_internal(other)
813 }
814 }
815
816 /// Add two different points
817 pub fn add_internal(&self, other: &Point<G>) -> Self {
818 if self.is_infinity {
819 return other.clone();
820 }
821
822 if other.is_infinity {
823 return self.clone();
824 }
825
826 let lambda = (other.y - self.y) * (other.x - self.x).invert().unwrap();
827 let x = lambda * lambda - self.x - other.x;
828 let y = lambda * (self.x - x) - self.y;
829 Self {
830 x,
831 y,
832 is_infinity: false,
833 }
834 }
835
836 pub fn double(&self) -> Self {
837 if self.is_infinity {
838 return Self {
839 x: G::Base::zero(),
840 y: G::Base::zero(),
841 is_infinity: true,
842 };
843 }
844
845 let lambda = G::Base::from(3)
846 * self.x
847 * self.x
848 * ((G::Base::one() + G::Base::one()) * self.y)
849 .invert()
850 .unwrap();
851 let x = lambda * lambda - self.x - self.x;
852 let y = lambda * (self.x - x) - self.y;
853 Self {
854 x,
855 y,
856 is_infinity: false,
857 }
858 }
859
860 pub fn scalar_mul(&self, scalar: &G::Scalar) -> Self {
861 let mut res = Self {
862 x: G::Base::zero(),
863 y: G::Base::zero(),
864 is_infinity: true,
865 };
866
867 let bits = scalar.to_le_bits();
868 for i in (0..bits.len()).rev() {
869 res = res.double();
870 if bits[i] {
871 res = self.add(&res);
872 }
873 }
874 res
875 }
876 }
877
878 // Allocate a random point. Only used for testing
879 pub fn alloc_random_point<G: Group, CS: ConstraintSystem<G::Base>>(
880 mut cs: CS,
881 ) -> Result<AllocatedPoint<G>, SynthesisError> {
882 // get a random point
883 let p = Point::<G>::random_vartime();
884 AllocatedPoint::alloc(cs.namespace(|| "alloc p"), Some((p.x, p.y, p.is_infinity)))
885 }
886
887 /// Make the point io
888 pub fn inputize_allocted_point<G: Group, CS: ConstraintSystem<G::Base>>(
889 p: &AllocatedPoint<G>,
890 mut cs: CS,
891 ) -> Result<(), SynthesisError> {
892 let _ = p.x.inputize(cs.namespace(|| "Input point.x"));
893 let _ = p.y.inputize(cs.namespace(|| "Input point.y"));
894 let _ = p
895 .is_infinity
896 .inputize(cs.namespace(|| "Input point.is_infinity"));
897 Ok(())
898 }
899
900 #[test]
901 fn test_ecc_ops() {
902 // perform some curve arithmetic
903 let a = Point::<G1>::random_vartime();
904 let b = Point::<G1>::random_vartime();
905 let c = a.add(&b);
906 let d = a.double();
907 let s = <G1 as Group>::Scalar::random(&mut OsRng);
908 let e = a.scalar_mul(&s);
909
910 // perform the same computation by translating to pasta_curve types
911 let a_pasta = EpAffine::from_xy(
912 pasta_curves::Fp::from_repr(a.x.to_repr()).unwrap(),
913 pasta_curves::Fp::from_repr(a.y.to_repr()).unwrap(),
914 )
915 .unwrap();
916 let b_pasta = EpAffine::from_xy(
917 pasta_curves::Fp::from_repr(b.x.to_repr()).unwrap(),
918 pasta_curves::Fp::from_repr(b.y.to_repr()).unwrap(),
919 )
920 .unwrap();
921 let c_pasta = (a_pasta + b_pasta).to_affine();
922 let d_pasta = (a_pasta + a_pasta).to_affine();
923 let e_pasta = a_pasta
924 .mul(pasta_curves::Fq::from_repr(s.to_repr()).unwrap())
925 .to_affine();
926
927 // transform c, d, and e into pasta_curve types
928 let c_pasta_2 = EpAffine::from_xy(
929 pasta_curves::Fp::from_repr(c.x.to_repr()).unwrap(),
930 pasta_curves::Fp::from_repr(c.y.to_repr()).unwrap(),
931 )
932 .unwrap();
933 let d_pasta_2 = EpAffine::from_xy(
934 pasta_curves::Fp::from_repr(d.x.to_repr()).unwrap(),
935 pasta_curves::Fp::from_repr(d.y.to_repr()).unwrap(),
936 )
937 .unwrap();
938 let e_pasta_2 = EpAffine::from_xy(
939 pasta_curves::Fp::from_repr(e.x.to_repr()).unwrap(),
940 pasta_curves::Fp::from_repr(e.y.to_repr()).unwrap(),
941 )
942 .unwrap();
943
944 // check that we have the same outputs
945 assert_eq!(c_pasta, c_pasta_2);
946 assert_eq!(d_pasta, d_pasta_2);
947 assert_eq!(e_pasta, e_pasta_2);
948 }
949
950 fn synthesize_smul<G, CS>(mut cs: CS) -> (AllocatedPoint<G>, AllocatedPoint<G>, G::Scalar)
951 where
952 G: Group,
953 CS: ConstraintSystem<G::Base>,
954 {
955 let a = alloc_random_point(cs.namespace(|| "a")).unwrap();
956 inputize_allocted_point(&a, cs.namespace(|| "inputize a")).unwrap();
957
958 let s = G::Scalar::random(&mut OsRng);
959 // Allocate bits for s
960 let bits: Vec<AllocatedBit> = s
961 .to_le_bits()
962 .into_iter()
963 .enumerate()
964 .map(|(i, bit)| AllocatedBit::alloc(cs.namespace(|| format!("bit {i}")), Some(bit)))
965 .collect::<Result<Vec<AllocatedBit>, SynthesisError>>()
966 .unwrap();
967 let e = a.scalar_mul(cs.namespace(|| "Scalar Mul"), bits).unwrap();
968 inputize_allocted_point(&e, cs.namespace(|| "inputize e")).unwrap();
969 (a, e, s)
970 }
971
972 #[test]
973 fn test_ecc_circuit_ops() {
974 // First create the shape
975 let mut cs: ShapeCS<G2> = ShapeCS::new();
976 let _ = synthesize_smul::<G1, _>(cs.namespace(|| "synthesize"));
977 println!("Number of constraints: {}", cs.num_constraints());
978 let (shape, ck) = cs.r1cs_shape();
979
980 // Then the satisfying assignment
981 let mut cs: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
982 let (a, e, s) = synthesize_smul::<G1, _>(cs.namespace(|| "synthesize"));
983 let (inst, witness) = cs.r1cs_instance_and_witness(&shape, &ck).unwrap();
984
985 let a_p: Point<G1> = Point::new(
986 a.x.get_value().unwrap(),
987 a.y.get_value().unwrap(),
988 a.is_infinity.get_value().unwrap() == <G1 as Group>::Base::one(),
989 );
990 let e_p: Point<G1> = Point::new(
991 e.x.get_value().unwrap(),
992 e.y.get_value().unwrap(),
993 e.is_infinity.get_value().unwrap() == <G1 as Group>::Base::one(),
994 );
995 let e_new = a_p.scalar_mul(&s);
996 assert!(e_p.x == e_new.x && e_p.y == e_new.y);
997 // Make sure that this is satisfiable
998 assert!(shape.is_sat(&ck, &inst, &witness).is_ok());
999 }
1000
1001 fn synthesize_add_equal<G, CS>(mut cs: CS) -> (AllocatedPoint<G>, AllocatedPoint<G>)
1002 where
1003 G: Group,
1004 CS: ConstraintSystem<G::Base>,
1005 {
1006 let a = alloc_random_point(cs.namespace(|| "a")).unwrap();
1007 inputize_allocted_point(&a, cs.namespace(|| "inputize a")).unwrap();
1008 let e = a.add(cs.namespace(|| "add a to a"), &a).unwrap();
1009 inputize_allocted_point(&e, cs.namespace(|| "inputize e")).unwrap();
1010 (a, e)
1011 }
1012
1013 #[test]
1014 fn test_ecc_circuit_add_equal() {
1015 // First create the shape
1016 let mut cs: ShapeCS<G2> = ShapeCS::new();
1017 let _ = synthesize_add_equal::<G1, _>(cs.namespace(|| "synthesize add equal"));
1018 println!("Number of constraints: {}", cs.num_constraints());
1019 let (shape, ck) = cs.r1cs_shape();
1020
1021 // Then the satisfying assignment
1022 let mut cs: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
1023 let (a, e) = synthesize_add_equal::<G1, _>(cs.namespace(|| "synthesize add equal"));
1024 let (inst, witness) = cs.r1cs_instance_and_witness(&shape, &ck).unwrap();
1025 let a_p: Point<G1> = Point::new(
1026 a.x.get_value().unwrap(),
1027 a.y.get_value().unwrap(),
1028 a.is_infinity.get_value().unwrap() == <G1 as Group>::Base::one(),
1029 );
1030 let e_p: Point<G1> = Point::new(
1031 e.x.get_value().unwrap(),
1032 e.y.get_value().unwrap(),
1033 e.is_infinity.get_value().unwrap() == <G1 as Group>::Base::one(),
1034 );
1035 let e_new = a_p.add(&a_p);
1036 assert!(e_p.x == e_new.x && e_p.y == e_new.y);
1037 // Make sure that it is satisfiable
1038 assert!(shape.is_sat(&ck, &inst, &witness).is_ok());
1039 }
1040
1041 fn synthesize_add_negation<G, CS>(mut cs: CS) -> AllocatedPoint<G>
1042 where
1043 G: Group,
1044 CS: ConstraintSystem<G::Base>,
1045 {
1046 let a = alloc_random_point(cs.namespace(|| "a")).unwrap();
1047 inputize_allocted_point(&a, cs.namespace(|| "inputize a")).unwrap();
1048 let mut b = a.clone();
1049 b.y = AllocatedNum::alloc(cs.namespace(|| "allocate negation of a"), || {
1050 Ok(G::Base::zero())
1051 })
1052 .unwrap();
1053 inputize_allocted_point(&b, cs.namespace(|| "inputize b")).unwrap();
1054 let e = a.add(cs.namespace(|| "add a to b"), &b).unwrap();
1055 e
1056 }
1057
1058 #[test]
1059 fn test_ecc_circuit_add_negation() {
1060 // First create the shape
1061 let mut cs: ShapeCS<G2> = ShapeCS::new();
1062 let _ = synthesize_add_negation::<G1, _>(cs.namespace(|| "synthesize add equal"));
1063 println!("Number of constraints: {}", cs.num_constraints());
1064 let (shape, ck) = cs.r1cs_shape();
1065
1066 // Then the satisfying assignment
1067 let mut cs: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
1068 let e = synthesize_add_negation::<G1, _>(cs.namespace(|| "synthesize add negation"));
1069 let (inst, witness) = cs.r1cs_instance_and_witness(&shape, &ck).unwrap();
1070 let e_p: Point<G1> = Point::new(
1071 e.x.get_value().unwrap(),
1072 e.y.get_value().unwrap(),
1073 e.is_infinity.get_value().unwrap() == <G1 as Group>::Base::one(),
1074 );
1075 assert!(e_p.is_infinity);
1076 // Make sure that it is satisfiable
1077 assert!(shape.is_sat(&ck, &inst, &witness).is_ok());
1078 }
1079}