Nova/src/gadgets/ecc.rs
src/gadgets/ecc.rsRaw
1//! This module implements various elliptic curve gadgets
2#![allow(non_snake_case)]
3use crate::gadgets::utils::{
4 alloc_num_equals, alloc_one, alloc_zero, conditionally_select, conditionally_select2,
5 select_num_or_one, select_num_or_zero, select_num_or_zero2, select_one_or_diff2,
6 select_one_or_num2, select_zero_or_num2,
7};
8use bellperson::{
9 gadgets::{
10 boolean::{AllocatedBit, Boolean},
11 num::AllocatedNum,
12 Assignment,
13 },
14 ConstraintSystem, SynthesisError,
15};
16use ff::PrimeField;
17
18/// AllocatedPoint provides an elliptic curve abstraction inside a circuit.
19#[derive(Clone)]
20pub struct AllocatedPoint<Fp>
21where
22 Fp: PrimeField,
23{
24 pub(crate) x: AllocatedNum<Fp>,
25 pub(crate) y: AllocatedNum<Fp>,
26 pub(crate) is_infinity: AllocatedNum<Fp>,
27}
28
29impl<Fp> AllocatedPoint<Fp>
30where
31 Fp: PrimeField,
32{
33 /// Allocates a new point on the curve using coordinates provided by `coords`.
34 /// If coords = None, it allocates the default infinity point
35 pub fn alloc<CS>(mut cs: CS, coords: Option<(Fp, Fp, bool)>) -> Result<Self, SynthesisError>
36 where
37 CS: ConstraintSystem<Fp>,
38 {
39 let x = AllocatedNum::alloc(cs.namespace(|| "x"), || {
40 Ok(coords.map_or(Fp::zero(), |c| c.0))
41 })?;
42 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
43 Ok(coords.map_or(Fp::zero(), |c| c.1))
44 })?;
45 let is_infinity = AllocatedNum::alloc(cs.namespace(|| "is_infinity"), || {
46 Ok(if coords.map_or(true, |c| c.2) {
47 Fp::one()
48 } else {
49 Fp::zero()
50 })
51 })?;
52 cs.enforce(
53 || "is_infinity is bit",
54 |lc| lc + is_infinity.get_variable(),
55 |lc| lc + CS::one() - is_infinity.get_variable(),
56 |lc| lc,
57 );
58
59 Ok(AllocatedPoint { x, y, is_infinity })
60 }
61
62 /// Allocates a default point on the curve.
63 pub fn default<CS>(mut cs: CS) -> Result<Self, SynthesisError>
64 where
65 CS: ConstraintSystem<Fp>,
66 {
67 let zero = alloc_zero(cs.namespace(|| "zero"))?;
68 let one = alloc_one(cs.namespace(|| "one"))?;
69
70 Ok(AllocatedPoint {
71 x: zero.clone(),
72 y: zero,
73 is_infinity: one,
74 })
75 }
76
77 /// Returns coordinates associated with the point.
78 pub fn get_coordinates(&self) -> (&AllocatedNum<Fp>, &AllocatedNum<Fp>, &AllocatedNum<Fp>) {
79 (&self.x, &self.y, &self.is_infinity)
80 }
81
82 // Allocate a random point. Only used for testing
83 #[cfg(test)]
84 pub fn random_vartime<CS: ConstraintSystem<Fp>>(mut cs: CS) -> Result<Self, SynthesisError> {
85 loop {
86 let x = Fp::random(&mut OsRng);
87 let y = (x * x * x + Fp::one() + Fp::one() + Fp::one() + Fp::one() + Fp::one()).sqrt();
88 if y.is_some().unwrap_u8() == 1 {
89 let x_alloc = AllocatedNum::alloc(cs.namespace(|| "x"), || Ok(x))?;
90 let y_alloc = AllocatedNum::alloc(cs.namespace(|| "y"), || Ok(y.unwrap()))?;
91 let is_infinity = alloc_zero(cs.namespace(|| "Is Infinity"))?;
92 return Ok(Self {
93 x: x_alloc,
94 y: y_alloc,
95 is_infinity,
96 });
97 }
98 }
99 }
100
101 /// Make the point io
102 #[cfg(test)]
103 pub fn inputize<CS: ConstraintSystem<Fp>>(&self, mut cs: CS) -> Result<(), SynthesisError> {
104 let _ = self.x.inputize(cs.namespace(|| "Input point.x"));
105 let _ = self.y.inputize(cs.namespace(|| "Input point.y"));
106 let _ = self
107 .is_infinity
108 .inputize(cs.namespace(|| "Input point.is_infinity"));
109 Ok(())
110 }
111
112 /// Add two points (may be equal)
113 pub fn add<CS: ConstraintSystem<Fp>>(
114 &self,
115 mut cs: CS,
116 other: &AllocatedPoint<Fp>,
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<Fp>>(
163 &self,
164 mut cs: CS,
165 other: &AllocatedPoint<Fp>,
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 Fp::one()
181 - (Fp::one() - *self.is_infinity.get_value().get()?)
182 * (Fp::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 Fp::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 x_diff_inv = AllocatedNum::alloc(cs.namespace(|| "x diff inverse"), || {
218 if *x_diff_is_actual.get_value().get()? == Fp::one() {
219 // Set to default
220 Ok(Fp::one())
221 } else {
222 // Set to the actual inverse
223 let inv = (*other.x.get_value().get()? - *self.x.get_value().get()?).invert();
224 if inv.is_some().unwrap_u8() == 1 {
225 Ok(inv.unwrap())
226 } else {
227 Err(SynthesisError::DivisionByZero)
228 }
229 }
230 })?;
231
232 cs.enforce(
233 || "Check inverse",
234 |lc| lc + x_diff.get_variable(),
235 |lc| lc + x_diff_inv.get_variable(),
236 |lc| lc + CS::one(),
237 );
238
239 let lambda = AllocatedNum::alloc(cs.namespace(|| "lambda"), || {
240 Ok(
241 (*other.y.get_value().get()? - *self.y.get_value().get()?)
242 * x_diff_inv.get_value().get()?,
243 )
244 })?;
245 cs.enforce(
246 || "Check that lambda is correct",
247 |lc| lc + other.y.get_variable() - self.y.get_variable(),
248 |lc| lc + x_diff_inv.get_variable(),
249 |lc| lc + lambda.get_variable(),
250 );
251
252 //************************************************************************/
253 // x = lambda * lambda - self.x - other.x;
254 //************************************************************************/
255 let x = AllocatedNum::alloc(cs.namespace(|| "x"), || {
256 Ok(
257 *lambda.get_value().get()? * lambda.get_value().get()?
258 - *self.x.get_value().get()?
259 - *other.x.get_value().get()?,
260 )
261 })?;
262 cs.enforce(
263 || "check that x is correct",
264 |lc| lc + lambda.get_variable(),
265 |lc| lc + lambda.get_variable(),
266 |lc| lc + x.get_variable() + self.x.get_variable() + other.x.get_variable(),
267 );
268
269 //************************************************************************/
270 // y = lambda * (self.x - x) - self.y;
271 //************************************************************************/
272 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
273 Ok(
274 *lambda.get_value().get()? * (*self.x.get_value().get()? - *x.get_value().get()?)
275 - *self.y.get_value().get()?,
276 )
277 })?;
278
279 cs.enforce(
280 || "Check that y is correct",
281 |lc| lc + lambda.get_variable(),
282 |lc| lc + self.x.get_variable() - x.get_variable(),
283 |lc| lc + y.get_variable() + self.y.get_variable(),
284 );
285
286 //************************************************************************/
287 // We only return the computed x, y if neither of the points is infinity and self.x != other.y
288 // if self.is_infinity return other.clone()
289 // elif other.is_infinity return self.clone()
290 // elif self.x == other.x return infinity
291 // Otherwise return the computed points.
292 //************************************************************************/
293 // Now compute the output x
294
295 let x1 = conditionally_select2(
296 cs.namespace(|| "x1 = other.is_infinity ? self.x : x"),
297 &self.x,
298 &x,
299 &other.is_infinity,
300 )?;
301
302 let x = conditionally_select2(
303 cs.namespace(|| "x = self.is_infinity ? other.x : x1"),
304 &other.x,
305 &x1,
306 &self.is_infinity,
307 )?;
308
309 let y1 = conditionally_select2(
310 cs.namespace(|| "y1 = other.is_infinity ? self.y : y"),
311 &self.y,
312 &y,
313 &other.is_infinity,
314 )?;
315
316 let y = conditionally_select2(
317 cs.namespace(|| "y = self.is_infinity ? other.y : y1"),
318 &other.y,
319 &y1,
320 &self.is_infinity,
321 )?;
322
323 let is_infinity1 = select_num_or_zero2(
324 cs.namespace(|| "is_infinity1 = other.is_infinity ? self.is_infinity : 0"),
325 &self.is_infinity,
326 &other.is_infinity,
327 )?;
328
329 let is_infinity = conditionally_select2(
330 cs.namespace(|| "is_infinity = self.is_infinity ? other.is_infinity : is_infinity1"),
331 &other.is_infinity,
332 &is_infinity1,
333 &self.is_infinity,
334 )?;
335
336 Ok(Self { x, y, is_infinity })
337 }
338
339 /// Doubles the supplied point.
340 pub fn double<CS: ConstraintSystem<Fp>>(&self, mut cs: CS) -> Result<Self, SynthesisError> {
341 //*************************************************************/
342 // lambda = (Fp::one() + Fp::one() + Fp::one())
343 // * self.x
344 // * self.x
345 // * ((Fp::one() + Fp::one()) * self.y).invert().unwrap();
346 /*************************************************************/
347
348 // Compute tmp = (Fp::one() + Fp::one())* self.y ? self != inf : 1
349 let tmp_actual = AllocatedNum::alloc(cs.namespace(|| "tmp_actual"), || {
350 Ok(*self.y.get_value().get()? + *self.y.get_value().get()?)
351 })?;
352 cs.enforce(
353 || "check tmp_actual",
354 |lc| lc + CS::one() + CS::one(),
355 |lc| lc + self.y.get_variable(),
356 |lc| lc + tmp_actual.get_variable(),
357 );
358
359 let tmp = select_one_or_num2(cs.namespace(|| "tmp"), &tmp_actual, &self.is_infinity)?;
360
361 // Compute inv = tmp.invert
362 let tmp_inv = AllocatedNum::alloc(cs.namespace(|| "tmp inverse"), || {
363 if *self.is_infinity.get_value().get()? == Fp::one() {
364 // Return default value 1
365 Ok(Fp::one())
366 } else {
367 // Return the actual inverse
368 let inv = (*tmp.get_value().get()?).invert();
369 if inv.is_some().unwrap_u8() == 1 {
370 Ok(inv.unwrap())
371 } else {
372 Err(SynthesisError::DivisionByZero)
373 }
374 }
375 })?;
376 cs.enforce(
377 || "Check inverse",
378 |lc| lc + tmp.get_variable(),
379 |lc| lc + tmp_inv.get_variable(),
380 |lc| lc + CS::one(),
381 );
382
383 // Now compute lambda as (Fp::one() + Fp::one + Fp::one()) * self.x * self.x * tmp_inv
384 let prod_1 = AllocatedNum::alloc(cs.namespace(|| "alloc prod 1"), || {
385 Ok(*tmp_inv.get_value().get()? * self.x.get_value().get()?)
386 })?;
387 cs.enforce(
388 || "Check prod 1",
389 |lc| lc + self.x.get_variable(),
390 |lc| lc + tmp_inv.get_variable(),
391 |lc| lc + prod_1.get_variable(),
392 );
393
394 let prod_2 = AllocatedNum::alloc(cs.namespace(|| "alloc prod 2"), || {
395 Ok(*prod_1.get_value().get()? * self.x.get_value().get()?)
396 })?;
397 cs.enforce(
398 || "Check prod 2",
399 |lc| lc + self.x.get_variable(),
400 |lc| lc + prod_1.get_variable(),
401 |lc| lc + prod_2.get_variable(),
402 );
403
404 let lambda = AllocatedNum::alloc(cs.namespace(|| "lambda"), || {
405 Ok(*prod_2.get_value().get()? * (Fp::one() + Fp::one() + Fp::one()))
406 })?;
407 cs.enforce(
408 || "Check lambda",
409 |lc| lc + CS::one() + CS::one() + CS::one(),
410 |lc| lc + prod_2.get_variable(),
411 |lc| lc + lambda.get_variable(),
412 );
413
414 /*************************************************************/
415 // x = lambda * lambda - self.x - self.x;
416 /*************************************************************/
417
418 let x = AllocatedNum::alloc(cs.namespace(|| "x"), || {
419 Ok(
420 ((*lambda.get_value().get()?) * (*lambda.get_value().get()?))
421 - *self.x.get_value().get()?
422 - self.x.get_value().get()?,
423 )
424 })?;
425 cs.enforce(
426 || "Check x",
427 |lc| lc + lambda.get_variable(),
428 |lc| lc + lambda.get_variable(),
429 |lc| lc + x.get_variable() + self.x.get_variable() + self.x.get_variable(),
430 );
431
432 /*************************************************************/
433 // y = lambda * (self.x - x) - self.y;
434 /*************************************************************/
435
436 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
437 Ok(
438 (*lambda.get_value().get()?) * (*self.x.get_value().get()? - x.get_value().get()?)
439 - self.y.get_value().get()?,
440 )
441 })?;
442 cs.enforce(
443 || "Check y",
444 |lc| lc + lambda.get_variable(),
445 |lc| lc + self.x.get_variable() - x.get_variable(),
446 |lc| lc + y.get_variable() + self.y.get_variable(),
447 );
448
449 /*************************************************************/
450 // Only return the computed x and y if the point is not infinity
451 /*************************************************************/
452
453 // x
454 let x = select_zero_or_num2(cs.namespace(|| "final x"), &x, &self.is_infinity)?;
455
456 // y
457 let y = select_zero_or_num2(cs.namespace(|| "final y"), &y, &self.is_infinity)?;
458
459 // is_infinity
460 let is_infinity = self.is_infinity.clone();
461
462 Ok(Self { x, y, is_infinity })
463 }
464
465 /// A gadget for scalar multiplication.
466 pub fn scalar_mul<CS: ConstraintSystem<Fp>>(
467 &self,
468 mut cs: CS,
469 scalar: Vec<AllocatedBit>,
470 ) -> Result<Self, SynthesisError> {
471 let mut res = Self::default(cs.namespace(|| "res"))?;
472 for i in (0..scalar.len()).rev() {
473 /*************************************************************/
474 // res = res.double();
475 /*************************************************************/
476
477 res = res.double(cs.namespace(|| format!("{}: double", i)))?;
478
479 /*************************************************************/
480 // if scalar[i] {
481 // res = self.add(&res);
482 // }
483 /*************************************************************/
484 let self_and_res = self.add(cs.namespace(|| format!("{}: add", i)), &res)?;
485 res = Self::conditionally_select(
486 cs.namespace(|| format!("{}: Update res", i)),
487 &self_and_res,
488 &res,
489 &Boolean::from(scalar[i].clone()),
490 )?;
491 }
492 Ok(res)
493 }
494
495 /// If condition outputs a otherwise outputs b
496 pub fn conditionally_select<CS: ConstraintSystem<Fp>>(
497 mut cs: CS,
498 a: &Self,
499 b: &Self,
500 condition: &Boolean,
501 ) -> Result<Self, SynthesisError> {
502 let x = conditionally_select(cs.namespace(|| "select x"), &a.x, &b.x, condition)?;
503
504 let y = conditionally_select(cs.namespace(|| "select y"), &a.y, &b.y, condition)?;
505
506 let is_infinity = conditionally_select(
507 cs.namespace(|| "select is_infinity"),
508 &a.is_infinity,
509 &b.is_infinity,
510 condition,
511 )?;
512
513 Ok(Self { x, y, is_infinity })
514 }
515
516 /// If condition outputs a otherwise infinity
517 pub fn select_point_or_infinity<CS: ConstraintSystem<Fp>>(
518 mut cs: CS,
519 a: &Self,
520 condition: &Boolean,
521 ) -> Result<Self, SynthesisError> {
522 let x = select_num_or_zero(cs.namespace(|| "select x"), &a.x, condition)?;
523
524 let y = select_num_or_zero(cs.namespace(|| "select y"), &a.y, condition)?;
525
526 let is_infinity = select_num_or_one(
527 cs.namespace(|| "select is_infinity"),
528 &a.is_infinity,
529 condition,
530 )?;
531
532 Ok(Self { x, y, is_infinity })
533 }
534}
535
536#[cfg(test)]
537use ff::PrimeFieldBits;
538#[cfg(test)]
539use rand::rngs::OsRng;
540#[cfg(test)]
541use std::marker::PhantomData;
542
543#[cfg(test)]
544#[derive(Debug, Clone)]
545pub struct Point<Fp, Fq>
546where
547 Fp: PrimeField,
548 Fq: PrimeField + PrimeFieldBits,
549{
550 x: Fp,
551 y: Fp,
552 is_infinity: bool,
553 _p: PhantomData<Fq>,
554}
555
556#[cfg(test)]
557impl<Fp, Fq> Point<Fp, Fq>
558where
559 Fp: PrimeField,
560 Fq: PrimeField + PrimeFieldBits,
561{
562 pub fn new(x: Fp, y: Fp, is_infinity: bool) -> Self {
563 Self {
564 x,
565 y,
566 is_infinity,
567 _p: Default::default(),
568 }
569 }
570
571 pub fn random_vartime() -> Self {
572 loop {
573 let x = Fp::random(&mut OsRng);
574 let y = (x * x * x + Fp::one() + Fp::one() + Fp::one() + Fp::one() + Fp::one()).sqrt();
575 if y.is_some().unwrap_u8() == 1 {
576 return Self {
577 x,
578 y: y.unwrap(),
579 is_infinity: false,
580 _p: Default::default(),
581 };
582 }
583 }
584 }
585
586 /// Add any two points
587 pub fn add(&self, other: &Point<Fp, Fq>) -> Self {
588 if self.x == other.x {
589 // If self == other then call double
590 if self.y == other.y {
591 self.double()
592 } else {
593 // if self.x == other.x and self.y != other.y then return infinity
594 Self {
595 x: Fp::zero(),
596 y: Fp::zero(),
597 is_infinity: true,
598 _p: Default::default(),
599 }
600 }
601 } else {
602 self.add_internal(other)
603 }
604 }
605
606 /// Add two different points
607 pub fn add_internal(&self, other: &Point<Fp, Fq>) -> Self {
608 if self.is_infinity {
609 return other.clone();
610 }
611
612 if other.is_infinity {
613 return self.clone();
614 }
615
616 let lambda = (other.y - self.y) * (other.x - self.x).invert().unwrap();
617 let x = lambda * lambda - self.x - other.x;
618 let y = lambda * (self.x - x) - self.y;
619 Self {
620 x,
621 y,
622 is_infinity: false,
623 _p: Default::default(),
624 }
625 }
626
627 pub fn double(&self) -> Self {
628 if self.is_infinity {
629 return Self {
630 x: Fp::zero(),
631 y: Fp::zero(),
632 is_infinity: true,
633 _p: Default::default(),
634 };
635 }
636
637 let lambda = (Fp::one() + Fp::one() + Fp::one())
638 * self.x
639 * self.x
640 * ((Fp::one() + Fp::one()) * self.y).invert().unwrap();
641 let x = lambda * lambda - self.x - self.x;
642 let y = lambda * (self.x - x) - self.y;
643 Self {
644 x,
645 y,
646 is_infinity: false,
647 _p: Default::default(),
648 }
649 }
650
651 pub fn scalar_mul(&self, scalar: &Fq) -> Self {
652 let mut res = Self {
653 x: Fp::zero(),
654 y: Fp::zero(),
655 is_infinity: true,
656 _p: Default::default(),
657 };
658
659 let bits = scalar.to_le_bits();
660 for i in (0..bits.len()).rev() {
661 res = res.double();
662 if bits[i] {
663 res = self.add(&res);
664 }
665 }
666 res
667 }
668}
669
670#[cfg(test)]
671mod tests {
672 use super::*;
673
674 #[test]
675 fn test_ecc_ops() {
676 type Fp = pasta_curves::pallas::Base;
677 type Fq = pasta_curves::pallas::Scalar;
678
679 // perform some curve arithmetic
680 let a = Point::<Fp, Fq>::random_vartime();
681 let b = Point::<Fp, Fq>::random_vartime();
682 let c = a.add(&b);
683 let d = a.double();
684 let s = Fq::random(&mut OsRng);
685 let e = a.scalar_mul(&s);
686
687 // perform the same computation by translating to pasta_curve types
688 let a_pasta = EpAffine::from_xy(
689 pasta_curves::Fp::from_repr(a.x.to_repr()).unwrap(),
690 pasta_curves::Fp::from_repr(a.y.to_repr()).unwrap(),
691 )
692 .unwrap();
693 let b_pasta = EpAffine::from_xy(
694 pasta_curves::Fp::from_repr(b.x.to_repr()).unwrap(),
695 pasta_curves::Fp::from_repr(b.y.to_repr()).unwrap(),
696 )
697 .unwrap();
698 let c_pasta = (a_pasta + b_pasta).to_affine();
699 let d_pasta = (a_pasta + a_pasta).to_affine();
700 let e_pasta = a_pasta
701 .mul(pasta_curves::Fq::from_repr(s.to_repr()).unwrap())
702 .to_affine();
703
704 // transform c, d, and e into pasta_curve types
705 let c_pasta_2 = EpAffine::from_xy(
706 pasta_curves::Fp::from_repr(c.x.to_repr()).unwrap(),
707 pasta_curves::Fp::from_repr(c.y.to_repr()).unwrap(),
708 )
709 .unwrap();
710 let d_pasta_2 = EpAffine::from_xy(
711 pasta_curves::Fp::from_repr(d.x.to_repr()).unwrap(),
712 pasta_curves::Fp::from_repr(d.y.to_repr()).unwrap(),
713 )
714 .unwrap();
715 let e_pasta_2 = EpAffine::from_xy(
716 pasta_curves::Fp::from_repr(e.x.to_repr()).unwrap(),
717 pasta_curves::Fp::from_repr(e.y.to_repr()).unwrap(),
718 )
719 .unwrap();
720
721 // check that we have the same outputs
722 assert_eq!(c_pasta, c_pasta_2);
723 assert_eq!(d_pasta, d_pasta_2);
724 assert_eq!(e_pasta, e_pasta_2);
725 }
726
727 use crate::bellperson::{shape_cs::ShapeCS, solver::SatisfyingAssignment};
728 use ff::{Field, PrimeFieldBits};
729 use pasta_curves::{arithmetic::CurveAffine, group::Curve, EpAffine};
730 use std::ops::Mul;
731 type G = pasta_curves::pallas::Point;
732 type Fp = pasta_curves::pallas::Scalar;
733 type Fq = pasta_curves::vesta::Scalar;
734 use crate::bellperson::r1cs::{NovaShape, NovaWitness};
735
736 fn synthesize_smul<Fp, Fq, CS>(mut cs: CS) -> (AllocatedPoint<Fp>, AllocatedPoint<Fp>, Fq)
737 where
738 Fp: PrimeField,
739 Fq: PrimeField + PrimeFieldBits,
740 CS: ConstraintSystem<Fp>,
741 {
742 let a = AllocatedPoint::<Fp>::random_vartime(cs.namespace(|| "a")).unwrap();
743 let _ = a.inputize(cs.namespace(|| "inputize a")).unwrap();
744 let s = Fq::random(&mut OsRng);
745 // Allocate random bits and only keep 128 bits
746 let bits: Vec<AllocatedBit> = s
747 .to_le_bits()
748 .into_iter()
749 .enumerate()
750 .map(|(i, bit)| AllocatedBit::alloc(cs.namespace(|| format!("bit {}", i)), Some(bit)))
751 .collect::<Result<Vec<AllocatedBit>, SynthesisError>>()
752 .unwrap();
753 let e = a.scalar_mul(cs.namespace(|| "Scalar Mul"), bits).unwrap();
754 let _ = e.inputize(cs.namespace(|| "inputize e")).unwrap();
755 (a, e, s)
756 }
757
758 #[test]
759 fn test_ecc_circuit_ops() {
760 // First create the shape
761 let mut cs: ShapeCS<G> = ShapeCS::new();
762 let _ = synthesize_smul::<Fp, Fq, _>(cs.namespace(|| "synthesize"));
763 println!("Number of constraints: {}", cs.num_constraints());
764 let shape = cs.r1cs_shape();
765 let gens = cs.r1cs_gens();
766
767 // Then the satisfying assignment
768 let mut cs: SatisfyingAssignment<G> = SatisfyingAssignment::new();
769 let (a, e, s) = synthesize_smul::<Fp, Fq, _>(cs.namespace(|| "synthesize"));
770 let (inst, witness) = cs.r1cs_instance_and_witness(&shape, &gens).unwrap();
771
772 let a_p: Point<Fp, Fq> = Point::new(
773 a.x.get_value().unwrap(),
774 a.y.get_value().unwrap(),
775 a.is_infinity.get_value().unwrap() == Fp::one(),
776 );
777 let e_p: Point<Fp, Fq> = Point::new(
778 e.x.get_value().unwrap(),
779 e.y.get_value().unwrap(),
780 e.is_infinity.get_value().unwrap() == Fp::one(),
781 );
782 let e_new = a_p.scalar_mul(&s);
783 assert!(e_p.x == e_new.x && e_p.y == e_new.y);
784 // Make sure that this is satisfiable
785 assert!(shape.is_sat(&gens, &inst, &witness).is_ok());
786 }
787
788 fn synthesize_add_equal<Fp, Fq, CS>(mut cs: CS) -> (AllocatedPoint<Fp>, AllocatedPoint<Fp>)
789 where
790 Fp: PrimeField,
791 Fq: PrimeField + PrimeFieldBits,
792 CS: ConstraintSystem<Fp>,
793 {
794 let a = AllocatedPoint::<Fp>::random_vartime(cs.namespace(|| "a")).unwrap();
795 let _ = a.inputize(cs.namespace(|| "inputize a")).unwrap();
796 let e = a.add(cs.namespace(|| "add a to a"), &a).unwrap();
797 let _ = e.inputize(cs.namespace(|| "inputize e")).unwrap();
798 (a, e)
799 }
800
801 #[test]
802 fn test_ecc_circuit_add_equal() {
803 // First create the shape
804 let mut cs: ShapeCS<G> = ShapeCS::new();
805 let _ = synthesize_add_equal::<Fp, Fq, _>(cs.namespace(|| "synthesize add equal"));
806 println!("Number of constraints: {}", cs.num_constraints());
807 let shape = cs.r1cs_shape();
808 let gens = cs.r1cs_gens();
809
810 // Then the satisfying assignment
811 let mut cs: SatisfyingAssignment<G> = SatisfyingAssignment::new();
812 let (a, e) = synthesize_add_equal::<Fp, Fq, _>(cs.namespace(|| "synthesize add equal"));
813 let (inst, witness) = cs.r1cs_instance_and_witness(&shape, &gens).unwrap();
814 let a_p: Point<Fp, Fq> = Point::new(
815 a.x.get_value().unwrap(),
816 a.y.get_value().unwrap(),
817 a.is_infinity.get_value().unwrap() == Fp::one(),
818 );
819 let e_p: Point<Fp, Fq> = Point::new(
820 e.x.get_value().unwrap(),
821 e.y.get_value().unwrap(),
822 e.is_infinity.get_value().unwrap() == Fp::one(),
823 );
824 let e_new = a_p.add(&a_p);
825 assert!(e_p.x == e_new.x && e_p.y == e_new.y);
826 // Make sure that it is satisfiable
827 assert!(shape.is_sat(&gens, &inst, &witness).is_ok());
828 }
829
830 fn synthesize_add_negation<Fp, Fq, CS>(mut cs: CS) -> AllocatedPoint<Fp>
831 where
832 Fp: PrimeField,
833 Fq: PrimeField + PrimeFieldBits,
834 CS: ConstraintSystem<Fp>,
835 {
836 let a = AllocatedPoint::<Fp>::random_vartime(cs.namespace(|| "a")).unwrap();
837 let _ = a.inputize(cs.namespace(|| "inputize a")).unwrap();
838 let mut b = a.clone();
839 b.y =
840 AllocatedNum::alloc(cs.namespace(|| "allocate negation of a"), || Ok(Fp::zero())).unwrap();
841 let _ = b.inputize(cs.namespace(|| "inputize b")).unwrap();
842 let e = a.add(cs.namespace(|| "add a to b"), &b).unwrap();
843 e
844 }
845
846 #[test]
847 fn test_ecc_circuit_add_negation() {
848 // First create the shape
849 let mut cs: ShapeCS<G> = ShapeCS::new();
850 let _ = synthesize_add_negation::<Fp, Fq, _>(cs.namespace(|| "synthesize add equal"));
851 println!("Number of constraints: {}", cs.num_constraints());
852 let shape = cs.r1cs_shape();
853 let gens = cs.r1cs_gens();
854
855 // Then the satisfying assignment
856 let mut cs: SatisfyingAssignment<G> = SatisfyingAssignment::new();
857 let e = synthesize_add_negation::<Fp, Fq, _>(cs.namespace(|| "synthesize add negation"));
858 let (inst, witness) = cs.r1cs_instance_and_witness(&shape, &gens).unwrap();
859 let e_p: Point<Fp, Fq> = Point::new(
860 e.x.get_value().unwrap(),
861 e.y.get_value().unwrap(),
862 e.is_infinity.get_value().unwrap() == Fp::one(),
863 );
864 assert!(e_p.is_infinity);
865 // Make sure that it is satisfiable
866 assert!(shape.is_sat(&gens, &inst, &witness).is_ok());
867 }
868}