Nova/src/gadgets/ecc_circuit.rs
src/gadgets/ecc_circuit.rsRaw
1#![allow(non_snake_case)]
2use crate::gadgets::utils::{
3 alloc_one, alloc_zero, conditionally_select, conditionally_select2, select_one_or, select_zero_or,
4};
5use bellperson::{
6 gadgets::{
7 boolean::{AllocatedBit, Boolean},
8 num::AllocatedNum,
9 Assignment,
10 },
11 ConstraintSystem, SynthesisError,
12};
13use ff::PrimeField;
14use rand::rngs::OsRng;
15
16#[derive(Clone)]
17pub struct AllocatedPoint<Fp>
18where
19 Fp: PrimeField,
20{
21 pub(crate) x: AllocatedNum<Fp>,
22 pub(crate) y: AllocatedNum<Fp>,
23 pub(crate) is_infinity: AllocatedNum<Fp>,
24}
25
26impl<Fp> AllocatedPoint<Fp>
27where
28 Fp: PrimeField,
29{
30 // Creates a new allocated point from allocated nums.
31 pub fn new(x: AllocatedNum<Fp>, y: AllocatedNum<Fp>, is_infinity: AllocatedNum<Fp>) -> Self {
32 Self { x, y, is_infinity }
33 }
34
35 // Check that is infinity is 0/1
36 #[allow(dead_code)]
37 pub fn check_is_infinity<CS: ConstraintSystem<Fp>>(
38 &self,
39 mut cs: CS,
40 ) -> Result<(), SynthesisError> {
41 // Check that is_infinity * ( 1 - is_infinity ) = 0
42 cs.enforce(
43 || "is_infinity is bit",
44 |lc| lc + self.is_infinity.get_variable(),
45 |lc| lc + CS::one() - self.is_infinity.get_variable(),
46 |lc| lc,
47 );
48 Ok(())
49 }
50
51 #[allow(dead_code)]
52 // Allocate a random point. Only used for testing
53 pub fn random_vartime<CS: ConstraintSystem<Fp>>(mut cs: CS) -> Result<Self, SynthesisError> {
54 loop {
55 let x = Fp::random(&mut OsRng);
56 let y = (x * x * x + Fp::one() + Fp::one() + Fp::one() + Fp::one() + Fp::one()).sqrt();
57 if y.is_some().unwrap_u8() == 1 {
58 let x_alloc = AllocatedNum::alloc(cs.namespace(|| "x"), || Ok(x))?;
59 let y_alloc = AllocatedNum::alloc(cs.namespace(|| "y"), || Ok(y.unwrap()))?;
60 let is_infinity = alloc_zero(cs.namespace(|| "Is Infinity"))?;
61 return Ok(Self::new(x_alloc, y_alloc, is_infinity));
62 }
63 }
64 }
65
66 // Make the point io
67 #[allow(dead_code)]
68 pub fn inputize<CS: ConstraintSystem<Fp>>(&self, mut cs: CS) -> Result<(), SynthesisError> {
69 let _ = self.x.inputize(cs.namespace(|| "Input point.x"));
70 let _ = self.y.inputize(cs.namespace(|| "Input point.y"));
71 let _ = self
72 .is_infinity
73 .inputize(cs.namespace(|| "Input point.is_infinity"));
74 Ok(())
75 }
76
77 // Adds other point to this point and returns the result
78 // Assumes that both other.is_infinity and this.is_infinty are bits
79 pub fn add<CS: ConstraintSystem<Fp>>(
80 &self,
81 mut cs: CS,
82 other: &AllocatedPoint<Fp>,
83 ) -> Result<Self, SynthesisError> {
84 // Allocate the boolean variables that check if either of the points is infinity
85
86 //************************************************************************/
87 // lambda = (other.y - self.y) * (other.x - self.x).invert().unwrap();
88 //************************************************************************/
89 // First compute (other.x - self.x).inverse()
90 // If either self or other are 1 then compute bogus values
91
92 // x_diff = other != inf && self != inf ? (other.x - self.x) : 1
93 let x_diff_actual = AllocatedNum::alloc(cs.namespace(|| "actual x diff"), || {
94 Ok(*other.x.get_value().get()? - *self.x.get_value().get()?)
95 })?;
96 cs.enforce(
97 || "actual x_diff is correct",
98 |lc| lc + other.x.get_variable() - self.x.get_variable(),
99 |lc| lc + CS::one(),
100 |lc| lc + x_diff_actual.get_variable(),
101 );
102
103 // Compute self.is_infinity OR other.is_infinity
104 let at_least_one_inf = AllocatedNum::alloc(cs.namespace(|| "at least one inf"), || {
105 Ok(*self.is_infinity.get_value().get()? * *other.is_infinity.get_value().get()?)
106 })?;
107 cs.enforce(
108 || "at least one inf = self.is_infinity * other.is_infinity",
109 |lc| lc + self.is_infinity.get_variable(),
110 |lc| lc + other.is_infinity.get_variable(),
111 |lc| lc + at_least_one_inf.get_variable(),
112 );
113
114 // x_diff = 1 if either self.is_infinity or other.is_infinity else x_diff_actual
115 let x_diff = select_one_or(
116 cs.namespace(|| "Compute x_diff"),
117 &x_diff_actual,
118 &at_least_one_inf,
119 )?;
120
121 let x_diff_inv = AllocatedNum::alloc(cs.namespace(|| "x diff inverse"), || {
122 if *at_least_one_inf.get_value().get()? == Fp::one() {
123 // Set to default
124 Ok(Fp::one())
125 } else {
126 // Set to the actual inverse
127 let inv = (*other.x.get_value().get()? - *self.x.get_value().get()?).invert();
128 if inv.is_some().unwrap_u8() == 1 {
129 Ok(inv.unwrap())
130 } else {
131 Err(SynthesisError::DivisionByZero)
132 }
133 }
134 })?;
135
136 cs.enforce(
137 || "Check inverse",
138 |lc| lc + x_diff.get_variable(),
139 |lc| lc + x_diff_inv.get_variable(),
140 |lc| lc + CS::one(),
141 );
142
143 let lambda = AllocatedNum::alloc(cs.namespace(|| "lambda"), || {
144 Ok(
145 (*other.y.get_value().get()? - *self.y.get_value().get()?)
146 * x_diff_inv.get_value().get()?,
147 )
148 })?;
149 cs.enforce(
150 || "Check that lambda is correct",
151 |lc| lc + other.y.get_variable() - self.y.get_variable(),
152 |lc| lc + x_diff_inv.get_variable(),
153 |lc| lc + lambda.get_variable(),
154 );
155
156 //************************************************************************/
157 // x = lambda * lambda - self.x - other.x;
158 //************************************************************************/
159 let x = AllocatedNum::alloc(cs.namespace(|| "x"), || {
160 Ok(
161 *lambda.get_value().get()? * lambda.get_value().get()?
162 - *self.x.get_value().get()?
163 - *other.x.get_value().get()?,
164 )
165 })?;
166 cs.enforce(
167 || "check that x is correct",
168 |lc| lc + lambda.get_variable(),
169 |lc| lc + lambda.get_variable(),
170 |lc| lc + x.get_variable() + self.x.get_variable() + other.x.get_variable(),
171 );
172
173 //************************************************************************/
174 // y = lambda * (self.x - x) - self.y;
175 //************************************************************************/
176 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
177 Ok(
178 *lambda.get_value().get()? * (*self.x.get_value().get()? - *x.get_value().get()?)
179 - *self.y.get_value().get()?,
180 )
181 })?;
182
183 cs.enforce(
184 || "Check that y is correct",
185 |lc| lc + lambda.get_variable(),
186 |lc| lc + self.x.get_variable() - x.get_variable(),
187 |lc| lc + y.get_variable() + self.y.get_variable(),
188 );
189
190 let is_infinity = AllocatedNum::alloc(cs.namespace(|| "is infinity"), || Ok(Fp::zero()))?;
191
192 //************************************************************************/
193 // We only return the computed x, y if neither of the points is infinity.
194 // if self.is_infinity return other.clone()
195 // elif other.is_infinity return self.clone()
196 // Otherwise return the computed points.
197 //************************************************************************/
198 // Now compute the output x
199 let inner_x = conditionally_select2(
200 cs.namespace(|| "final x: inner if"),
201 &self.x,
202 &x,
203 &other.is_infinity,
204 )?;
205 let final_x = conditionally_select2(
206 cs.namespace(|| "final x: outer if"),
207 &other.x,
208 &inner_x,
209 &self.is_infinity,
210 )?;
211
212 // The output y
213 let inner_y = conditionally_select2(
214 cs.namespace(|| "final y: inner if"),
215 &self.y,
216 &y,
217 &other.is_infinity,
218 )?;
219 let final_y = conditionally_select2(
220 cs.namespace(|| "final y: outer if"),
221 &other.y,
222 &inner_y,
223 &self.is_infinity,
224 )?;
225
226 // The output is_infinity
227 let inner_is_infinity = conditionally_select2(
228 cs.namespace(|| "final is infinity: inner if"),
229 &self.is_infinity,
230 &is_infinity,
231 &other.is_infinity,
232 )?;
233 let final_is_infinity = conditionally_select2(
234 cs.namespace(|| "final is infinity: outer if"),
235 &other.is_infinity,
236 &inner_is_infinity,
237 &self.is_infinity,
238 )?;
239 Ok(Self::new(final_x, final_y, final_is_infinity))
240 }
241
242 pub fn double<CS: ConstraintSystem<Fp>>(&self, mut cs: CS) -> Result<Self, SynthesisError> {
243 //*************************************************************/
244 // lambda = (Fp::one() + Fp::one() + Fp::one())
245 // * self.x
246 // * self.x
247 // * ((Fp::one() + Fp::one()) * self.y).invert().unwrap();
248 /*************************************************************/
249
250 // Compute tmp = (Fp::one() + Fp::one())* self.y ? self != inf : 1
251 let tmp_actual = AllocatedNum::alloc(cs.namespace(|| "tmp_actual"), || {
252 Ok(*self.y.get_value().get()? + *self.y.get_value().get()?)
253 })?;
254 cs.enforce(
255 || "check tmp_actual",
256 |lc| lc + CS::one() + CS::one(),
257 |lc| lc + self.y.get_variable(),
258 |lc| lc + tmp_actual.get_variable(),
259 );
260
261 let tmp = select_one_or(cs.namespace(|| "tmp"), &tmp_actual, &self.is_infinity)?;
262
263 // Compute inv = tmp.invert
264 let tmp_inv = AllocatedNum::alloc(cs.namespace(|| "tmp inverse"), || {
265 if *self.is_infinity.get_value().get()? == Fp::one() {
266 // Return default value 1
267 Ok(Fp::one())
268 } else {
269 // Return the actual inverse
270 let inv = (*tmp.get_value().get()?).invert();
271 if inv.is_some().unwrap_u8() == 1 {
272 Ok(inv.unwrap())
273 } else {
274 Err(SynthesisError::DivisionByZero)
275 }
276 }
277 })?;
278 cs.enforce(
279 || "Check inverse",
280 |lc| lc + tmp.get_variable(),
281 |lc| lc + tmp_inv.get_variable(),
282 |lc| lc + CS::one(),
283 );
284
285 // Now compute lambda as (Fp::one() + Fp::one + Fp::one()) * self.x * self.x * tmp_inv
286 let prod_1 = AllocatedNum::alloc(cs.namespace(|| "alloc prod 1"), || {
287 Ok(*tmp_inv.get_value().get()? * self.x.get_value().get()?)
288 })?;
289 cs.enforce(
290 || "Check prod 1",
291 |lc| lc + self.x.get_variable(),
292 |lc| lc + tmp_inv.get_variable(),
293 |lc| lc + prod_1.get_variable(),
294 );
295
296 let prod_2 = AllocatedNum::alloc(cs.namespace(|| "alloc prod 2"), || {
297 Ok(*prod_1.get_value().get()? * self.x.get_value().get()?)
298 })?;
299 cs.enforce(
300 || "Check prod 2",
301 |lc| lc + self.x.get_variable(),
302 |lc| lc + prod_1.get_variable(),
303 |lc| lc + prod_2.get_variable(),
304 );
305
306 let lambda = AllocatedNum::alloc(cs.namespace(|| "lambda"), || {
307 Ok(*prod_2.get_value().get()? * (Fp::one() + Fp::one() + Fp::one()))
308 })?;
309 cs.enforce(
310 || "Check lambda",
311 |lc| lc + CS::one() + CS::one() + CS::one(),
312 |lc| lc + prod_2.get_variable(),
313 |lc| lc + lambda.get_variable(),
314 );
315
316 /*************************************************************/
317 // x = lambda * lambda - self.x - self.x;
318 /*************************************************************/
319
320 let x = AllocatedNum::alloc(cs.namespace(|| "x"), || {
321 Ok(
322 ((*lambda.get_value().get()?) * (*lambda.get_value().get()?))
323 - *self.x.get_value().get()?
324 - self.x.get_value().get()?,
325 )
326 })?;
327 cs.enforce(
328 || "Check x",
329 |lc| lc + lambda.get_variable(),
330 |lc| lc + lambda.get_variable(),
331 |lc| lc + x.get_variable() + self.x.get_variable() + self.x.get_variable(),
332 );
333
334 /*************************************************************/
335 // y = lambda * (self.x - x) - self.y;
336 /*************************************************************/
337
338 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
339 Ok(
340 (*lambda.get_value().get()?) * (*self.x.get_value().get()? - x.get_value().get()?)
341 - self.y.get_value().get()?,
342 )
343 })?;
344 cs.enforce(
345 || "Check y",
346 |lc| lc + lambda.get_variable(),
347 |lc| lc + self.x.get_variable() - x.get_variable(),
348 |lc| lc + y.get_variable() + self.y.get_variable(),
349 );
350
351 /*************************************************************/
352 // Only return the computed x and y if the point is not infinity
353 /*************************************************************/
354
355 // x
356 let final_x = select_zero_or(cs.namespace(|| "final x"), &x, &self.is_infinity)?;
357
358 // y
359 let final_y = select_zero_or(cs.namespace(|| "final y"), &y, &self.is_infinity)?;
360
361 // is_infinity
362 let final_is_infinity = self.is_infinity.clone();
363
364 Ok(Self::new(final_x, final_y, final_is_infinity))
365 }
366
367 #[allow(dead_code)]
368 pub fn scalar_mul_mont<CS: ConstraintSystem<Fp>>(
369 &self,
370 mut cs: CS,
371 scalar: Vec<AllocatedBit>,
372 ) -> Result<Self, SynthesisError> {
373 /*************************************************************/
374 // Initialize RO = Self {
375 // x: Fp::zero(),
376 // y: Fp::zero(),
377 // is_infinity: true,
378 // _p: Default::default(),
379 //};
380 /*************************************************************/
381
382 let zero = alloc_zero(cs.namespace(|| "Allocate zero"))?;
383 let one = alloc_one(cs.namespace(|| "Allocate one"))?;
384 let mut R0 = Self::new(zero.clone(), zero, one);
385
386 /*************************************************************/
387 // Initialize R1 and the bits of the scalar
388 /*************************************************************/
389
390 let mut R1 = self.clone();
391
392 for i in (0..scalar.len()).rev() {
393 /*************************************************************/
394 //if bits[i] {
395 // R0 = R0.add(&R1);
396 // R1 = R1.double();
397 //} else {
398 // R0 = R0.double();
399 // R1 = R0.add(&R1);
400 //}
401 /*************************************************************/
402
403 let R0_and_R1 = R0.add(cs.namespace(|| format!("{}: R0 + R1", i)), &R1)?;
404 let R0_double = R0.double(cs.namespace(|| format!("{}: 2 * R0", i)))?;
405 let R1_double = R1.double(cs.namespace(|| format!("{}: 2 * R1", i)))?;
406
407 R0 = Self::conditionally_select(
408 cs.namespace(|| format!("{}: Update R0", i)),
409 &R0_and_R1,
410 &R0_double,
411 &Boolean::from(scalar[i].clone()),
412 )?;
413
414 R1 = Self::conditionally_select(
415 cs.namespace(|| format!("{}: Update R1", i)),
416 &R1_double,
417 &R0_and_R1,
418 &Boolean::from(scalar[i].clone()),
419 )?;
420 }
421 Ok(R0)
422 }
423
424 #[allow(dead_code)]
425 pub fn scalar_mul<CS: ConstraintSystem<Fp>>(
426 &self,
427 mut cs: CS,
428 scalar: Vec<AllocatedBit>,
429 ) -> Result<Self, SynthesisError> {
430 /*************************************************************/
431 // Initialize res = Self {
432 // x: Fp::zero(),
433 // y: Fp::zero(),
434 // is_infinity: true,
435 // _p: Default::default(),
436 //};
437 /*************************************************************/
438
439 let zero = alloc_zero(cs.namespace(|| "Allocate zero"))?;
440 let one = alloc_one(cs.namespace(|| "Allocate one"))?;
441 let mut res = Self::new(zero.clone(), zero, one);
442
443 for i in (0..scalar.len()).rev() {
444 /*************************************************************/
445 // res = res.double();
446 /*************************************************************/
447
448 res = res.double(cs.namespace(|| format!("{}: double", i)))?;
449
450 /*************************************************************/
451 // if scalar[i] {
452 // res = self.add(&res);
453 // }
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::new(x, y, is_infinity))
486 }
487}
488
489#[cfg(test)]
490mod tests {
491 use super::*;
492 use crate::bellperson::shape_cs::ShapeCS;
493 use crate::bellperson::solver::SatisfyingAssignment;
494 type G = pasta_curves::pallas::Point;
495 type Fp = pasta_curves::pallas::Scalar;
496 type Fq = pasta_curves::vesta::Scalar;
497 use crate::bellperson::r1cs::{NovaShape, NovaWitness};
498 use crate::gadgets::ecc::Point;
499 use ff::PrimeFieldBits;
500
501 fn synthesize_smul<Fp, Fq, CS>(mut cs: CS) -> (AllocatedPoint<Fp>, AllocatedPoint<Fp>, Fq)
502 where
503 Fp: PrimeField,
504 Fq: PrimeField + PrimeFieldBits,
505 CS: ConstraintSystem<Fp>,
506 {
507 let a = AllocatedPoint::<Fp>::random_vartime(cs.namespace(|| "a")).unwrap();
508 let _ = a.inputize(cs.namespace(|| "inputize a")).unwrap();
509 let s = Fq::random(&mut OsRng);
510 // Allocate random bits and only keep 128 bits
511 let bits: Vec<AllocatedBit> = s
512 .to_le_bits()
513 .into_iter()
514 .enumerate()
515 .map(|(i, bit)| AllocatedBit::alloc(cs.namespace(|| format!("bit {}", i)), Some(bit)))
516 .collect::<Result<Vec<AllocatedBit>, SynthesisError>>()
517 .unwrap();
518 let e = a.scalar_mul(cs.namespace(|| "Scalar Mul"), bits).unwrap();
519 let _ = e.inputize(cs.namespace(|| "inputize e")).unwrap();
520 (a, e, s)
521 }
522
523 #[test]
524 fn test_ecc_circuit_ops() {
525 // First create the shape
526 let mut cs: ShapeCS<G> = ShapeCS::new();
527 let _ = synthesize_smul::<Fp, Fq, _>(cs.namespace(|| "synthesize"));
528 println!("Number of constraints: {}", cs.num_constraints());
529 let shape = cs.r1cs_shape();
530 let gens = cs.r1cs_gens();
531
532 // Then the satisfying assignment
533 let mut cs: SatisfyingAssignment<G> = SatisfyingAssignment::new();
534 let (a, e, s) = synthesize_smul::<Fp, Fq, _>(cs.namespace(|| "synthesize"));
535 let (inst, witness) = cs.r1cs_instance_and_witness(&shape, &gens).unwrap();
536
537 let a_p: Point<Fp, Fq> = Point::new(
538 a.x.get_value().unwrap(),
539 a.y.get_value().unwrap(),
540 a.is_infinity.get_value().unwrap() == Fp::one(),
541 );
542 let e_p: Point<Fp, Fq> = Point::new(
543 e.x.get_value().unwrap(),
544 e.y.get_value().unwrap(),
545 e.is_infinity.get_value().unwrap() == Fp::one(),
546 );
547 let e_new = a_p.scalar_mul(&s);
548 assert!(e_p.x == e_new.x && e_p.y == e_new.y);
549 // Make sure that this is satisfiable
550 assert!(shape.is_sat(&gens, &inst, &witness).is_ok());
551 }
552}