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 lambda = AllocatedNum::alloc(cs.namespace(|| "lambda"), || {
218 let x_diff_inv = if *x_diff_is_actual.get_value().get()? == Fp::one() {
219 // Set to default
220 Fp::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<Fp>>(&self, mut cs: CS) -> Result<Self, SynthesisError> {
326 //*************************************************************/
327 // lambda = (Fp::one() + Fp::one() + Fp::one())
328 // * self.x
329 // * self.x
330 // * ((Fp::one() + Fp::one()) * self.y).invert().unwrap();
331 /*************************************************************/
332
333 // Compute tmp = (Fp::one() + Fp::one())* self.y ? self != inf : 1
334 let tmp_actual = AllocatedNum::alloc(cs.namespace(|| "tmp_actual"), || {
335 Ok(*self.y.get_value().get()? + *self.y.get_value().get()?)
336 })?;
337 cs.enforce(
338 || "check tmp_actual",
339 |lc| lc + CS::one() + CS::one(),
340 |lc| lc + self.y.get_variable(),
341 |lc| lc + tmp_actual.get_variable(),
342 );
343
344 let tmp = select_one_or_num2(cs.namespace(|| "tmp"), &tmp_actual, &self.is_infinity)?;
345
346 // Now compute lambda as (Fp::one() + Fp::one + Fp::one()) * self.x * self.x * tmp_inv
347 let prod_1 = AllocatedNum::alloc(cs.namespace(|| "alloc prod 1"), || {
348 let tmp_inv = if *self.is_infinity.get_value().get()? == Fp::one() {
349 // Return default value 1
350 Fp::one()
351 } else {
352 // Return the actual inverse
353 (*tmp.get_value().get()?).invert().unwrap()
354 };
355
356 Ok(tmp_inv * self.x.get_value().get()?)
357 })?;
358
359 cs.enforce(
360 || "Check prod 1",
361 |lc| lc + tmp.get_variable(),
362 |lc| lc + prod_1.get_variable(),
363 |lc| lc + self.x.get_variable(),
364 );
365
366 let prod_2 = AllocatedNum::alloc(cs.namespace(|| "alloc prod 2"), || {
367 Ok(*prod_1.get_value().get()? * self.x.get_value().get()?)
368 })?;
369 cs.enforce(
370 || "Check prod 2",
371 |lc| lc + self.x.get_variable(),
372 |lc| lc + prod_1.get_variable(),
373 |lc| lc + prod_2.get_variable(),
374 );
375
376 let lambda = AllocatedNum::alloc(cs.namespace(|| "lambda"), || {
377 Ok(*prod_2.get_value().get()? * (Fp::one() + Fp::one() + Fp::one()))
378 })?;
379 cs.enforce(
380 || "Check lambda",
381 |lc| lc + CS::one() + CS::one() + CS::one(),
382 |lc| lc + prod_2.get_variable(),
383 |lc| lc + lambda.get_variable(),
384 );
385
386 /*************************************************************/
387 // x = lambda * lambda - self.x - self.x;
388 /*************************************************************/
389
390 let x = AllocatedNum::alloc(cs.namespace(|| "x"), || {
391 Ok(
392 ((*lambda.get_value().get()?) * (*lambda.get_value().get()?))
393 - *self.x.get_value().get()?
394 - self.x.get_value().get()?,
395 )
396 })?;
397 cs.enforce(
398 || "Check x",
399 |lc| lc + lambda.get_variable(),
400 |lc| lc + lambda.get_variable(),
401 |lc| lc + x.get_variable() + self.x.get_variable() + self.x.get_variable(),
402 );
403
404 /*************************************************************/
405 // y = lambda * (self.x - x) - self.y;
406 /*************************************************************/
407
408 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
409 Ok(
410 (*lambda.get_value().get()?) * (*self.x.get_value().get()? - x.get_value().get()?)
411 - self.y.get_value().get()?,
412 )
413 })?;
414 cs.enforce(
415 || "Check y",
416 |lc| lc + lambda.get_variable(),
417 |lc| lc + self.x.get_variable() - x.get_variable(),
418 |lc| lc + y.get_variable() + self.y.get_variable(),
419 );
420
421 /*************************************************************/
422 // Only return the computed x and y if the point is not infinity
423 /*************************************************************/
424
425 // x
426 let x = select_zero_or_num2(cs.namespace(|| "final x"), &x, &self.is_infinity)?;
427
428 // y
429 let y = select_zero_or_num2(cs.namespace(|| "final y"), &y, &self.is_infinity)?;
430
431 // is_infinity
432 let is_infinity = self.is_infinity.clone();
433
434 Ok(Self { x, y, is_infinity })
435 }
436
437 /// A gadget for scalar multiplication.
438 pub fn scalar_mul<CS: ConstraintSystem<Fp>>(
439 &self,
440 mut cs: CS,
441 scalar: Vec<AllocatedBit>,
442 ) -> Result<Self, SynthesisError> {
443 let mut res = Self::default(cs.namespace(|| "res"))?;
444 for i in (0..scalar.len()).rev() {
445 /*************************************************************/
446 // res = res.double();
447 /*************************************************************/
448
449 res = res.double(cs.namespace(|| format!("{}: double", i)))?;
450
451 /*************************************************************/
452 // if scalar[i] {
453 // res = self.add(&res);
454 // }
455 /*************************************************************/
456 let self_and_res = self.add(cs.namespace(|| format!("{}: add", i)), &res)?;
457 res = Self::conditionally_select(
458 cs.namespace(|| format!("{}: Update res", i)),
459 &self_and_res,
460 &res,
461 &Boolean::from(scalar[i].clone()),
462 )?;
463 }
464 Ok(res)
465 }
466
467 /// If condition outputs a otherwise outputs b
468 pub fn conditionally_select<CS: ConstraintSystem<Fp>>(
469 mut cs: CS,
470 a: &Self,
471 b: &Self,
472 condition: &Boolean,
473 ) -> Result<Self, SynthesisError> {
474 let x = conditionally_select(cs.namespace(|| "select x"), &a.x, &b.x, condition)?;
475
476 let y = conditionally_select(cs.namespace(|| "select y"), &a.y, &b.y, condition)?;
477
478 let is_infinity = conditionally_select(
479 cs.namespace(|| "select is_infinity"),
480 &a.is_infinity,
481 &b.is_infinity,
482 condition,
483 )?;
484
485 Ok(Self { x, y, is_infinity })
486 }
487
488 /// If condition outputs a otherwise infinity
489 pub fn select_point_or_infinity<CS: ConstraintSystem<Fp>>(
490 mut cs: CS,
491 a: &Self,
492 condition: &Boolean,
493 ) -> Result<Self, SynthesisError> {
494 let x = select_num_or_zero(cs.namespace(|| "select x"), &a.x, condition)?;
495
496 let y = select_num_or_zero(cs.namespace(|| "select y"), &a.y, condition)?;
497
498 let is_infinity = select_num_or_one(
499 cs.namespace(|| "select is_infinity"),
500 &a.is_infinity,
501 condition,
502 )?;
503
504 Ok(Self { x, y, is_infinity })
505 }
506}
507
508#[cfg(test)]
509use ff::PrimeFieldBits;
510#[cfg(test)]
511use rand::rngs::OsRng;
512#[cfg(test)]
513use std::marker::PhantomData;
514
515#[cfg(test)]
516#[derive(Debug, Clone)]
517pub struct Point<Fp, Fq>
518where
519 Fp: PrimeField,
520 Fq: PrimeField + PrimeFieldBits,
521{
522 x: Fp,
523 y: Fp,
524 is_infinity: bool,
525 _p: PhantomData<Fq>,
526}
527
528#[cfg(test)]
529impl<Fp, Fq> Point<Fp, Fq>
530where
531 Fp: PrimeField,
532 Fq: PrimeField + PrimeFieldBits,
533{
534 pub fn new(x: Fp, y: Fp, is_infinity: bool) -> Self {
535 Self {
536 x,
537 y,
538 is_infinity,
539 _p: Default::default(),
540 }
541 }
542
543 pub fn random_vartime() -> Self {
544 loop {
545 let x = Fp::random(&mut OsRng);
546 let y = (x * x * x + Fp::one() + Fp::one() + Fp::one() + Fp::one() + Fp::one()).sqrt();
547 if y.is_some().unwrap_u8() == 1 {
548 return Self {
549 x,
550 y: y.unwrap(),
551 is_infinity: false,
552 _p: Default::default(),
553 };
554 }
555 }
556 }
557
558 /// Add any two points
559 pub fn add(&self, other: &Point<Fp, Fq>) -> Self {
560 if self.x == other.x {
561 // If self == other then call double
562 if self.y == other.y {
563 self.double()
564 } else {
565 // if self.x == other.x and self.y != other.y then return infinity
566 Self {
567 x: Fp::zero(),
568 y: Fp::zero(),
569 is_infinity: true,
570 _p: Default::default(),
571 }
572 }
573 } else {
574 self.add_internal(other)
575 }
576 }
577
578 /// Add two different points
579 pub fn add_internal(&self, other: &Point<Fp, Fq>) -> Self {
580 if self.is_infinity {
581 return other.clone();
582 }
583
584 if other.is_infinity {
585 return self.clone();
586 }
587
588 let lambda = (other.y - self.y) * (other.x - self.x).invert().unwrap();
589 let x = lambda * lambda - self.x - other.x;
590 let y = lambda * (self.x - x) - self.y;
591 Self {
592 x,
593 y,
594 is_infinity: false,
595 _p: Default::default(),
596 }
597 }
598
599 pub fn double(&self) -> Self {
600 if self.is_infinity {
601 return Self {
602 x: Fp::zero(),
603 y: Fp::zero(),
604 is_infinity: true,
605 _p: Default::default(),
606 };
607 }
608
609 let lambda = (Fp::one() + Fp::one() + Fp::one())
610 * self.x
611 * self.x
612 * ((Fp::one() + Fp::one()) * self.y).invert().unwrap();
613 let x = lambda * lambda - self.x - self.x;
614 let y = lambda * (self.x - x) - self.y;
615 Self {
616 x,
617 y,
618 is_infinity: false,
619 _p: Default::default(),
620 }
621 }
622
623 pub fn scalar_mul(&self, scalar: &Fq) -> Self {
624 let mut res = Self {
625 x: Fp::zero(),
626 y: Fp::zero(),
627 is_infinity: true,
628 _p: Default::default(),
629 };
630
631 let bits = scalar.to_le_bits();
632 for i in (0..bits.len()).rev() {
633 res = res.double();
634 if bits[i] {
635 res = self.add(&res);
636 }
637 }
638 res
639 }
640}
641
642#[cfg(test)]
643mod tests {
644 use super::*;
645
646 #[test]
647 fn test_ecc_ops() {
648 type Fp = pasta_curves::pallas::Base;
649 type Fq = pasta_curves::pallas::Scalar;
650
651 // perform some curve arithmetic
652 let a = Point::<Fp, Fq>::random_vartime();
653 let b = Point::<Fp, Fq>::random_vartime();
654 let c = a.add(&b);
655 let d = a.double();
656 let s = Fq::random(&mut OsRng);
657 let e = a.scalar_mul(&s);
658
659 // perform the same computation by translating to pasta_curve types
660 let a_pasta = EpAffine::from_xy(
661 pasta_curves::Fp::from_repr(a.x.to_repr()).unwrap(),
662 pasta_curves::Fp::from_repr(a.y.to_repr()).unwrap(),
663 )
664 .unwrap();
665 let b_pasta = EpAffine::from_xy(
666 pasta_curves::Fp::from_repr(b.x.to_repr()).unwrap(),
667 pasta_curves::Fp::from_repr(b.y.to_repr()).unwrap(),
668 )
669 .unwrap();
670 let c_pasta = (a_pasta + b_pasta).to_affine();
671 let d_pasta = (a_pasta + a_pasta).to_affine();
672 let e_pasta = a_pasta
673 .mul(pasta_curves::Fq::from_repr(s.to_repr()).unwrap())
674 .to_affine();
675
676 // transform c, d, and e into pasta_curve types
677 let c_pasta_2 = EpAffine::from_xy(
678 pasta_curves::Fp::from_repr(c.x.to_repr()).unwrap(),
679 pasta_curves::Fp::from_repr(c.y.to_repr()).unwrap(),
680 )
681 .unwrap();
682 let d_pasta_2 = EpAffine::from_xy(
683 pasta_curves::Fp::from_repr(d.x.to_repr()).unwrap(),
684 pasta_curves::Fp::from_repr(d.y.to_repr()).unwrap(),
685 )
686 .unwrap();
687 let e_pasta_2 = EpAffine::from_xy(
688 pasta_curves::Fp::from_repr(e.x.to_repr()).unwrap(),
689 pasta_curves::Fp::from_repr(e.y.to_repr()).unwrap(),
690 )
691 .unwrap();
692
693 // check that we have the same outputs
694 assert_eq!(c_pasta, c_pasta_2);
695 assert_eq!(d_pasta, d_pasta_2);
696 assert_eq!(e_pasta, e_pasta_2);
697 }
698
699 use crate::bellperson::{shape_cs::ShapeCS, solver::SatisfyingAssignment};
700 use ff::{Field, PrimeFieldBits};
701 use pasta_curves::{arithmetic::CurveAffine, group::Curve, EpAffine};
702 use std::ops::Mul;
703 type G = pasta_curves::pallas::Point;
704 type Fp = pasta_curves::pallas::Scalar;
705 type Fq = pasta_curves::vesta::Scalar;
706 use crate::bellperson::r1cs::{NovaShape, NovaWitness};
707
708 fn synthesize_smul<Fp, Fq, CS>(mut cs: CS) -> (AllocatedPoint<Fp>, AllocatedPoint<Fp>, Fq)
709 where
710 Fp: PrimeField,
711 Fq: PrimeField + PrimeFieldBits,
712 CS: ConstraintSystem<Fp>,
713 {
714 let a = AllocatedPoint::<Fp>::random_vartime(cs.namespace(|| "a")).unwrap();
715 a.inputize(cs.namespace(|| "inputize a")).unwrap();
716 let s = Fq::random(&mut OsRng);
717 // Allocate random bits and only keep 128 bits
718 let bits: Vec<AllocatedBit> = s
719 .to_le_bits()
720 .into_iter()
721 .enumerate()
722 .map(|(i, bit)| AllocatedBit::alloc(cs.namespace(|| format!("bit {}", i)), Some(bit)))
723 .collect::<Result<Vec<AllocatedBit>, SynthesisError>>()
724 .unwrap();
725 let e = a.scalar_mul(cs.namespace(|| "Scalar Mul"), bits).unwrap();
726 e.inputize(cs.namespace(|| "inputize e")).unwrap();
727 (a, e, s)
728 }
729
730 #[test]
731 fn test_ecc_circuit_ops() {
732 // First create the shape
733 let mut cs: ShapeCS<G> = ShapeCS::new();
734 let _ = synthesize_smul::<Fp, Fq, _>(cs.namespace(|| "synthesize"));
735 println!("Number of constraints: {}", cs.num_constraints());
736 let shape = cs.r1cs_shape();
737 let gens = cs.r1cs_gens();
738
739 // Then the satisfying assignment
740 let mut cs: SatisfyingAssignment<G> = SatisfyingAssignment::new();
741 let (a, e, s) = synthesize_smul::<Fp, Fq, _>(cs.namespace(|| "synthesize"));
742 let (inst, witness) = cs.r1cs_instance_and_witness(&shape, &gens).unwrap();
743
744 let a_p: Point<Fp, Fq> = Point::new(
745 a.x.get_value().unwrap(),
746 a.y.get_value().unwrap(),
747 a.is_infinity.get_value().unwrap() == Fp::one(),
748 );
749 let e_p: Point<Fp, Fq> = Point::new(
750 e.x.get_value().unwrap(),
751 e.y.get_value().unwrap(),
752 e.is_infinity.get_value().unwrap() == Fp::one(),
753 );
754 let e_new = a_p.scalar_mul(&s);
755 assert!(e_p.x == e_new.x && e_p.y == e_new.y);
756 // Make sure that this is satisfiable
757 assert!(shape.is_sat(&gens, &inst, &witness).is_ok());
758 }
759
760 fn synthesize_add_equal<Fp, Fq, CS>(mut cs: CS) -> (AllocatedPoint<Fp>, AllocatedPoint<Fp>)
761 where
762 Fp: PrimeField,
763 Fq: PrimeField + PrimeFieldBits,
764 CS: ConstraintSystem<Fp>,
765 {
766 let a = AllocatedPoint::<Fp>::random_vartime(cs.namespace(|| "a")).unwrap();
767 a.inputize(cs.namespace(|| "inputize a")).unwrap();
768 let e = a.add(cs.namespace(|| "add a to a"), &a).unwrap();
769 e.inputize(cs.namespace(|| "inputize e")).unwrap();
770 (a, e)
771 }
772
773 #[test]
774 fn test_ecc_circuit_add_equal() {
775 // First create the shape
776 let mut cs: ShapeCS<G> = ShapeCS::new();
777 let _ = synthesize_add_equal::<Fp, Fq, _>(cs.namespace(|| "synthesize add equal"));
778 println!("Number of constraints: {}", cs.num_constraints());
779 let shape = cs.r1cs_shape();
780 let gens = cs.r1cs_gens();
781
782 // Then the satisfying assignment
783 let mut cs: SatisfyingAssignment<G> = SatisfyingAssignment::new();
784 let (a, e) = synthesize_add_equal::<Fp, Fq, _>(cs.namespace(|| "synthesize add equal"));
785 let (inst, witness) = cs.r1cs_instance_and_witness(&shape, &gens).unwrap();
786 let a_p: Point<Fp, Fq> = Point::new(
787 a.x.get_value().unwrap(),
788 a.y.get_value().unwrap(),
789 a.is_infinity.get_value().unwrap() == Fp::one(),
790 );
791 let e_p: Point<Fp, Fq> = Point::new(
792 e.x.get_value().unwrap(),
793 e.y.get_value().unwrap(),
794 e.is_infinity.get_value().unwrap() == Fp::one(),
795 );
796 let e_new = a_p.add(&a_p);
797 assert!(e_p.x == e_new.x && e_p.y == e_new.y);
798 // Make sure that it is satisfiable
799 assert!(shape.is_sat(&gens, &inst, &witness).is_ok());
800 }
801
802 fn synthesize_add_negation<Fp, Fq, CS>(mut cs: CS) -> AllocatedPoint<Fp>
803 where
804 Fp: PrimeField,
805 Fq: PrimeField + PrimeFieldBits,
806 CS: ConstraintSystem<Fp>,
807 {
808 let a = AllocatedPoint::<Fp>::random_vartime(cs.namespace(|| "a")).unwrap();
809 a.inputize(cs.namespace(|| "inputize a")).unwrap();
810 let mut b = a.clone();
811 b.y =
812 AllocatedNum::alloc(cs.namespace(|| "allocate negation of a"), || Ok(Fp::zero())).unwrap();
813 b.inputize(cs.namespace(|| "inputize b")).unwrap();
814 let e = a.add(cs.namespace(|| "add a to b"), &b).unwrap();
815 e
816 }
817
818 #[test]
819 fn test_ecc_circuit_add_negation() {
820 // First create the shape
821 let mut cs: ShapeCS<G> = ShapeCS::new();
822 let _ = synthesize_add_negation::<Fp, Fq, _>(cs.namespace(|| "synthesize add equal"));
823 println!("Number of constraints: {}", cs.num_constraints());
824 let shape = cs.r1cs_shape();
825 let gens = cs.r1cs_gens();
826
827 // Then the satisfying assignment
828 let mut cs: SatisfyingAssignment<G> = SatisfyingAssignment::new();
829 let e = synthesize_add_negation::<Fp, Fq, _>(cs.namespace(|| "synthesize add negation"));
830 let (inst, witness) = cs.r1cs_instance_and_witness(&shape, &gens).unwrap();
831 let e_p: Point<Fp, Fq> = Point::new(
832 e.x.get_value().unwrap(),
833 e.y.get_value().unwrap(),
834 e.is_infinity.get_value().unwrap() == Fp::one(),
835 );
836 assert!(e_p.is_infinity);
837 // Make sure that it is satisfiable
838 assert!(shape.is_sat(&gens, &inst, &witness).is_ok());
839 }
840}