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