ark-r1cs-std/r1cs-std/src/groups/curves/twisted_edwards/mod.rs
r1cs-std/src/groups/curves/twisted_edwards/mod.rsRaw
1use algebra::{
2 curves::{
3 twisted_edwards_extended::GroupAffine as TEAffine, MontgomeryModelParameters,
4 TEModelParameters,
5 },
6 BitIterator, Field, One, Zero,
7};
8
9use r1cs_core::{ConstraintSystem, SynthesisError};
10
11use crate::{prelude::*, Vec};
12
13use core::{borrow::Borrow, marker::PhantomData};
14
15#[derive(Derivative)]
16#[derivative(Debug, Clone)]
17#[derivative(Debug(bound = "P: TEModelParameters, ConstraintF: Field"))]
18#[must_use]
19pub struct MontgomeryAffineGadget<
20 P: TEModelParameters,
21 ConstraintF: Field,
22 F: FieldGadget<P::BaseField, ConstraintF>,
23> {
24 pub x: F,
25 pub y: F,
26 #[derivative(Debug = "ignore")]
27 _params: PhantomData<P>,
28 #[derivative(Debug = "ignore")]
29 _engine: PhantomData<ConstraintF>,
30}
31
32mod montgomery_affine_impl {
33 use super::*;
34 use crate::Assignment;
35 use algebra::{twisted_edwards_extended::GroupAffine, Field};
36 use core::ops::{AddAssign, MulAssign, SubAssign};
37
38 impl<P: TEModelParameters, ConstraintF: Field, F: FieldGadget<P::BaseField, ConstraintF>>
39 MontgomeryAffineGadget<P, ConstraintF, F>
40 {
41 pub fn new(x: F, y: F) -> Self {
42 Self {
43 x,
44 y,
45 _params: PhantomData,
46 _engine: PhantomData,
47 }
48 }
49
50 pub fn from_edwards_to_coords(
51 p: &TEAffine<P>,
52 ) -> Result<(P::BaseField, P::BaseField), SynthesisError> {
53 let montgomery_point: GroupAffine<P> = if p.y == P::BaseField::one() {
54 GroupAffine::zero()
55 } else if p.x == P::BaseField::zero() {
56 GroupAffine::new(P::BaseField::zero(), P::BaseField::zero())
57 } else {
58 let u =
59 (P::BaseField::one() + &p.y) * &(P::BaseField::one() - &p.y).inverse().unwrap();
60 let v = u * &p.x.inverse().unwrap();
61 GroupAffine::new(u, v)
62 };
63
64 Ok((montgomery_point.x, montgomery_point.y))
65 }
66
67 pub fn from_edwards<CS: ConstraintSystem<ConstraintF>>(
68 mut cs: CS,
69 p: &TEAffine<P>,
70 ) -> Result<Self, SynthesisError> {
71 let montgomery_coords = Self::from_edwards_to_coords(p)?;
72
73 let u = F::alloc(cs.ns(|| "u"), || Ok(montgomery_coords.0))?;
74
75 let v = F::alloc(cs.ns(|| "v"), || Ok(montgomery_coords.1))?;
76
77 Ok(Self::new(u, v))
78 }
79
80 pub fn into_edwards<CS: ConstraintSystem<ConstraintF>>(
81 &self,
82 mut cs: CS,
83 ) -> Result<AffineGadget<P, ConstraintF, F>, SynthesisError> {
84 // Compute u = x / y
85 let u = F::alloc(cs.ns(|| "u"), || {
86 let mut t0 = self.x.get_value().get()?;
87
88 match self.y.get_value().get()?.inverse() {
89 Some(invy) => {
90 t0.mul_assign(&invy);
91
92 Ok(t0)
93 },
94 None => Err(SynthesisError::DivisionByZero),
95 }
96 })?;
97
98 u.mul_equals(cs.ns(|| "u equals"), &self.y, &self.x)?;
99
100 let v = F::alloc(cs.ns(|| "v"), || {
101 let mut t0 = self.x.get_value().get()?;
102 let mut t1 = t0.clone();
103 t0.sub_assign(&P::BaseField::one());
104 t1.add_assign(&P::BaseField::one());
105
106 match t1.inverse() {
107 Some(t1) => {
108 t0.mul_assign(&t1);
109
110 Ok(t0)
111 },
112 None => Err(SynthesisError::DivisionByZero),
113 }
114 })?;
115
116 let xplusone = self
117 .x
118 .add_constant(cs.ns(|| "x plus one"), &P::BaseField::one())?;
119 let xminusone = self
120 .x
121 .sub_constant(cs.ns(|| "x minus one"), &P::BaseField::one())?;
122 v.mul_equals(cs.ns(|| "v equals"), &xplusone, &xminusone)?;
123
124 Ok(AffineGadget::new(u, v))
125 }
126
127 pub fn add<CS: ConstraintSystem<ConstraintF>>(
128 &self,
129 mut cs: CS,
130 other: &Self,
131 ) -> Result<Self, SynthesisError> {
132 let lambda = F::alloc(cs.ns(|| "lambda"), || {
133 let mut n = other.y.get_value().get()?;
134 n.sub_assign(&self.y.get_value().get()?);
135
136 let mut d = other.x.get_value().get()?;
137 d.sub_assign(&self.x.get_value().get()?);
138
139 match d.inverse() {
140 Some(d) => {
141 n.mul_assign(&d);
142 Ok(n)
143 },
144 None => Err(SynthesisError::DivisionByZero),
145 }
146 })?;
147 let lambda_n = other.y.sub(cs.ns(|| "other.y - self.y"), &self.y)?;
148 let lambda_d = other.x.sub(cs.ns(|| "other.x - self.x"), &self.x)?;
149 lambda_d.mul_equals(cs.ns(|| "lambda equals"), &lambda, &lambda_n)?;
150
151 // Compute x'' = B*lambda^2 - A - x - x'
152 let xprime = F::alloc(cs.ns(|| "xprime"), || {
153 Ok(
154 lambda.get_value().get()?.square() * &P::MontgomeryModelParameters::COEFF_B
155 - &P::MontgomeryModelParameters::COEFF_A
156 - &self.x.get_value().get()?
157 - &other.x.get_value().get()?,
158 )
159 })?;
160
161 let xprime_lc = self
162 .x
163 .add(cs.ns(|| "self.x + other.x"), &other.x)?
164 .add(cs.ns(|| "+ xprime"), &xprime)?
165 .add_constant(cs.ns(|| "+ A"), &P::MontgomeryModelParameters::COEFF_A)?;
166 // (lambda) * (lambda) = (A + x + x' + x'')
167 let lambda_b = lambda.mul_by_constant(
168 cs.ns(|| "lambda * b"),
169 &P::MontgomeryModelParameters::COEFF_B,
170 )?;
171 lambda_b.mul_equals(cs.ns(|| "xprime equals"), &lambda, &xprime_lc)?;
172
173 let yprime = F::alloc(cs.ns(|| "yprime"), || {
174 Ok(-(self.y.get_value().get()?
175 + &(lambda.get_value().get()?
176 * &(xprime.get_value().get()? - &self.x.get_value().get()?))))
177 })?;
178
179 let xres = self.x.sub(cs.ns(|| "xres"), &xprime)?;
180 let yres = self.y.add(cs.ns(|| "yres"), &yprime)?;
181 lambda.mul_equals(cs.ns(|| "yprime equals"), &xres, &yres)?;
182 Ok(MontgomeryAffineGadget::new(xprime, yprime))
183 }
184 }
185}
186
187#[derive(Derivative)]
188#[derivative(Debug, Clone)]
189#[derivative(Debug(bound = "P: TEModelParameters, ConstraintF: Field"))]
190#[must_use]
191pub struct AffineGadget<
192 P: TEModelParameters,
193 ConstraintF: Field,
194 F: FieldGadget<P::BaseField, ConstraintF>,
195> {
196 pub x: F,
197 pub y: F,
198 #[derivative(Debug = "ignore")]
199 _params: PhantomData<P>,
200 #[derivative(Debug = "ignore")]
201 _engine: PhantomData<ConstraintF>,
202}
203
204impl<P: TEModelParameters, ConstraintF: Field, F: FieldGadget<P::BaseField, ConstraintF>>
205 AffineGadget<P, ConstraintF, F>
206{
207 pub fn new(x: F, y: F) -> Self {
208 Self {
209 x,
210 y,
211 _params: PhantomData,
212 _engine: PhantomData,
213 }
214 }
215
216 pub fn alloc_without_check<FN, CS: ConstraintSystem<ConstraintF>>(
217 mut cs: CS,
218 value_gen: F,
219 ) -> Result<Self, SynthesisError>
220 where
221 F: FnOnce() -> Result<TEAffine<P>, SynthesisError>,
222 {
223 let (x, y) = match value_gen() {
224 Ok(fe) => (Ok(fe.x), Ok(fe.y)),
225 _ => (
226 Err(SynthesisError::AssignmentMissing),
227 Err(SynthesisError::AssignmentMissing),
228 ),
229 };
230
231 let x = F::alloc(&mut cs.ns(|| "x"), || x)?;
232 let y = F::alloc(&mut cs.ns(|| "y"), || y)?;
233
234 Ok(Self::new(x, y))
235 }
236}
237
238impl<P, ConstraintF, F> PartialEq for AffineGadget<P, ConstraintF, F>
239where
240 P: TEModelParameters,
241 ConstraintF: Field,
242 F: FieldGadget<P::BaseField, ConstraintF>,
243{
244 fn eq(&self, other: &Self) -> bool {
245 self.x == other.x && self.y == other.y
246 }
247}
248
249impl<P, ConstraintF, F> Eq for AffineGadget<P, ConstraintF, F>
250where
251 P: TEModelParameters,
252 ConstraintF: Field,
253 F: FieldGadget<P::BaseField, ConstraintF>,
254{
255}
256
257mod affine_impl {
258 use super::*;
259 use crate::Assignment;
260 use algebra::{curves::AffineCurve, Field, PrimeField};
261 use core::ops::Neg;
262
263 impl<P, ConstraintF, F> GroupGadget<TEAffine<P>, ConstraintF> for AffineGadget<P, ConstraintF, F>
264 where
265 P: TEModelParameters,
266 ConstraintF: Field,
267 F: FieldGadget<P::BaseField, ConstraintF>,
268 {
269 type Value = TEAffine<P>;
270 type Variable = (F::Variable, F::Variable);
271
272 #[inline]
273 fn get_value(&self) -> Option<Self::Value> {
274 match (self.x.get_value(), self.y.get_value()) {
275 (Some(x), Some(y)) => Some(TEAffine::new(x, y)),
276 (..) => None,
277 }
278 }
279
280 #[inline]
281 fn get_variable(&self) -> Self::Variable {
282 (self.x.get_variable(), self.y.get_variable())
283 }
284
285 #[inline]
286 fn zero<CS: ConstraintSystem<ConstraintF>>(mut cs: CS) -> Result<Self, SynthesisError> {
287 Ok(Self::new(
288 F::zero(cs.ns(|| "zero"))?,
289 F::one(cs.ns(|| "one"))?,
290 ))
291 }
292
293 /// Optimized constraints for checking Edwards point addition from ZCash
294 /// developers Daira Hopwood and Sean Bowe. Requires only 6 constraints
295 /// compared to 7 for the straightforward version we had earlier.
296 fn add<CS: ConstraintSystem<ConstraintF>>(
297 &self,
298 mut cs: CS,
299 other: &Self,
300 ) -> Result<Self, SynthesisError> {
301 let a = P::COEFF_A;
302 let d = P::COEFF_D;
303
304 // Compute U = (x1 + y1) * (x2 + y2)
305 let u1 = self
306 .x
307 .mul_by_constant(cs.ns(|| "-A * x1"), &a.neg())?
308 .add(cs.ns(|| "-A * x1 + y1"), &self.y)?;
309 let u2 = other.x.add(cs.ns(|| "x2 + y2"), &other.y)?;
310
311 let u = u1.mul(cs.ns(|| "(-A * x1 + y1) * (x2 + y2)"), &u2)?;
312
313 // Compute v0 = x1 * y2
314 let v0 = other.y.mul(&mut cs.ns(|| "v0"), &self.x)?;
315
316 // Compute v1 = x2 * y1
317 let v1 = other.x.mul(&mut cs.ns(|| "v1"), &self.y)?;
318
319 // Compute C = d*v0*v1
320 let v2 = v0
321 .mul(cs.ns(|| "v0 * v1"), &v1)?
322 .mul_by_constant(cs.ns(|| "D * v0 * v1"), &d)?;
323
324 // Compute x3 = (v0 + v1) / (1 + v2)
325 let x3 = F::alloc(&mut cs.ns(|| "x3"), || {
326 let t0 = v0.get_value().get()? + &v1.get_value().get()?;
327 let t1 = P::BaseField::one() + &v2.get_value().get()?;
328 Ok(t0 * &t1.inverse().get()?)
329 })?;
330
331 let one = P::BaseField::one();
332 let v2_plus_one = v2.add_constant(cs.ns(|| "v2 + 1"), &one)?;
333 let v0_plus_v1 = v0.add(cs.ns(|| "v0 + v1"), &v1)?;
334 x3.mul_equals(cs.ns(|| "check x3"), &v2_plus_one, &v0_plus_v1)?;
335
336 // Compute y3 = (U + a * v0 - v1) / (1 - v2)
337 let y3 = F::alloc(&mut cs.ns(|| "y3"), || {
338 let t0 =
339 u.get_value().get()? + &(a * &v0.get_value().get()?) - &v1.get_value().get()?;
340 let t1 = P::BaseField::one() - &v2.get_value().get()?;
341 Ok(t0 * &t1.inverse().get()?)
342 })?;
343
344 let one_minus_v2 = v2
345 .add_constant(cs.ns(|| "v2 - 1"), &(-one))?
346 .negate(cs.ns(|| "1 - v2"))?;
347 let a_v0 = v0.mul_by_constant(cs.ns(|| "a * v0"), &a)?;
348 let u_plus_a_v0_minus_v1 = u
349 .add(cs.ns(|| "u + a * v0"), &a_v0)?
350 .sub(cs.ns(|| "u + a * v0 - v1"), &v1)?;
351
352 y3.mul_equals(cs.ns(|| "check y3"), &one_minus_v2, &u_plus_a_v0_minus_v1)?;
353
354 Ok(Self::new(x3, y3))
355 }
356
357 fn add_constant<CS: ConstraintSystem<ConstraintF>>(
358 &self,
359 mut cs: CS,
360 other: &TEAffine<P>,
361 ) -> Result<Self, SynthesisError> {
362 let a = P::COEFF_A;
363 let d = P::COEFF_D;
364 let other_x = other.x;
365 let other_y = other.y;
366
367 // Compute U = (x1 + y1) * (x2 + y2)
368 let u1 = self
369 .x
370 .mul_by_constant(cs.ns(|| "-A * x1"), &a.neg())?
371 .add(cs.ns(|| "-A * x1 + y1"), &self.y)?;
372 let u2 = other_x + &other_y;
373
374 let u = u1.mul_by_constant(cs.ns(|| "(-A * x1 + y1) * (x2 + y2)"), &u2)?;
375
376 // Compute v0 = x1 * y2
377 let v0 = self.x.mul_by_constant(&mut cs.ns(|| "v0"), &other_y)?;
378
379 // Compute v1 = x2 * y1
380 let v1 = self.y.mul_by_constant(&mut cs.ns(|| "v1"), &other.x)?;
381
382 // Compute C = d*v0*v1
383 let v2 = v0
384 .mul(cs.ns(|| "v0 * v1"), &v1)?
385 .mul_by_constant(cs.ns(|| "D * v0 * v1"), &d)?;
386
387 // Compute x3 = (v0 + v1) / (1 + v2)
388 let x3 = F::alloc(&mut cs.ns(|| "x3"), || {
389 let t0 = v0.get_value().get()? + &v1.get_value().get()?;
390 let t1 = P::BaseField::one() + &v2.get_value().get()?;
391 Ok(t0 * &t1.inverse().get()?)
392 })?;
393
394 let one = P::BaseField::one();
395 let v2_plus_one = v2.add_constant(cs.ns(|| "v2 + 1"), &one)?;
396 let v0_plus_v1 = v0.add(cs.ns(|| "v0 + v1"), &v1)?;
397 x3.mul_equals(cs.ns(|| "check x3"), &v2_plus_one, &v0_plus_v1)?;
398
399 // Compute y3 = (U + a * v0 - v1) / (1 - v2)
400 let y3 = F::alloc(&mut cs.ns(|| "y3"), || {
401 let t0 =
402 u.get_value().get()? + &(a * &v0.get_value().get()?) - &v1.get_value().get()?;
403 let t1 = P::BaseField::one() - &v2.get_value().get()?;
404 Ok(t0 * &t1.inverse().get()?)
405 })?;
406
407 let one_minus_v2 = v2
408 .add_constant(cs.ns(|| "v2 - 1"), &(-one))?
409 .negate(cs.ns(|| "1 - v2"))?;
410 let a_v0 = v0.mul_by_constant(cs.ns(|| "a * v0"), &a)?;
411 let u_plus_a_v0_minus_v1 = u
412 .add(cs.ns(|| "u + a * v0"), &a_v0)?
413 .sub(cs.ns(|| "u + a * v0 - v1"), &v1)?;
414
415 y3.mul_equals(cs.ns(|| "check y3"), &one_minus_v2, &u_plus_a_v0_minus_v1)?;
416
417 Ok(Self::new(x3, y3))
418 }
419
420 fn double_in_place<CS: ConstraintSystem<ConstraintF>>(
421 &mut self,
422 mut cs: CS,
423 ) -> Result<(), SynthesisError> {
424 let a = P::COEFF_A;
425
426 // xy
427 let xy = self.x.mul(cs.ns(|| "x * y"), &self.y)?;
428 let x2 = self.x.square(cs.ns(|| "x * x"))?;
429 let y2 = self.y.square(cs.ns(|| "y * y"))?;
430
431 let a_x2 = x2.mul_by_constant(cs.ns(|| "a * x^2"), &a)?;
432
433 // Compute x3 = (2xy) / (ax^2 + y^2)
434 let x3 = F::alloc(&mut cs.ns(|| "x3"), || {
435 let t0 = xy.get_value().get()?.double();
436 let t1 = a * &x2.get_value().get()? + &y2.get_value().get()?;
437 Ok(t0 * &t1.inverse().get()?)
438 })?;
439
440 let a_x2_plus_y2 = a_x2.add(cs.ns(|| "v2 + 1"), &y2)?;
441 let two_xy = xy.double(cs.ns(|| "2xy"))?;
442 x3.mul_equals(cs.ns(|| "check x3"), &a_x2_plus_y2, &two_xy)?;
443
444 // Compute y3 = (y^2 - ax^2) / (2 - ax^2 - y^2)
445 let two = P::BaseField::one().double();
446 let y3 = F::alloc(&mut cs.ns(|| "y3"), || {
447 let a_x2 = a * &x2.get_value().get()?;
448 let t0 = y2.get_value().get()? - &a_x2;
449 let t1 = two - &a_x2 - &y2.get_value().get()?;
450 Ok(t0 * &t1.inverse().get()?)
451 })?;
452 let y2_minus_a_x2 = y2.sub(cs.ns(|| "y^2 - ax^2"), &a_x2)?;
453 let two_minus_ax2_minus_y2 = a_x2
454 .add(cs.ns(|| "ax2 + y2"), &y2)?
455 .negate(cs.ns(|| "-ax2 - y2"))?
456 .add_constant(cs.ns(|| "2 -ax2 - y2"), &two)?;
457
458 y3.mul_equals(
459 cs.ns(|| "check y3"),
460 &two_minus_ax2_minus_y2,
461 &y2_minus_a_x2,
462 )?;
463 self.x = x3;
464 self.y = y3;
465
466 Ok(())
467 }
468
469 fn negate<CS: ConstraintSystem<ConstraintF>>(
470 &self,
471 mut cs: CS,
472 ) -> Result<Self, SynthesisError> {
473 Ok(Self::new(
474 self.x.negate(cs.ns(|| "negate x"))?,
475 self.y.clone(),
476 ))
477 }
478
479 fn cost_of_add() -> usize {
480 4 + 2 * F::cost_of_mul()
481 }
482
483 fn cost_of_double() -> usize {
484 4 + F::cost_of_mul()
485 }
486 }
487
488 impl<P, ConstraintF, F> AllocGadget<TEAffine<P>, ConstraintF> for AffineGadget<P, ConstraintF, F>
489 where
490 P: TEModelParameters,
491 ConstraintF: Field,
492 F: FieldGadget<P::BaseField, ConstraintF>,
493 Self: GroupGadget<TEAffine<P>, ConstraintF>,
494 {
495 fn alloc<FN, T, CS: ConstraintSystem<ConstraintF>>(
496 mut cs: CS,
497 value_gen: FN,
498 ) -> Result<Self, SynthesisError>
499 where
500 FN: FnOnce() -> Result<T, SynthesisError>,
501 T: Borrow<TEAffine<P>>,
502 {
503 let (x, y) = match value_gen() {
504 Ok(ge) => {
505 let ge = *ge.borrow();
506 (Ok(ge.x), Ok(ge.y))
507 },
508 _ => (
509 Err(SynthesisError::AssignmentMissing),
510 Err(SynthesisError::AssignmentMissing),
511 ),
512 };
513
514 let d = P::COEFF_D;
515 let a = P::COEFF_A;
516
517 let x = F::alloc(&mut cs.ns(|| "x"), || x)?;
518 let y = F::alloc(&mut cs.ns(|| "y"), || y)?;
519
520 // Check that ax^2 + y^2 = 1 + dx^2y^2
521 // We do this by checking that ax^2 - 1 = y^2 * (dx^2 - 1)
522 let x2 = x.square(&mut cs.ns(|| "x^2"))?;
523 let y2 = y.square(&mut cs.ns(|| "y^2"))?;
524
525 let one = P::BaseField::one();
526 let d_x2_minus_one = x2
527 .mul_by_constant(cs.ns(|| "d * x^2"), &d)?
528 .add_constant(cs.ns(|| "d * x^2 - 1"), &one.neg())?;
529
530 let a_x2_minus_one = x2
531 .mul_by_constant(cs.ns(|| "a * x^2"), &a)?
532 .add_constant(cs.ns(|| "a * x^2 - 1"), &one.neg())?;
533
534 d_x2_minus_one.mul_equals(cs.ns(|| "on curve check"), &y2, &a_x2_minus_one)?;
535 Ok(Self::new(x, y))
536 }
537
538 fn alloc_checked<FN, T, CS: ConstraintSystem<ConstraintF>>(
539 mut cs: CS,
540 value_gen: FN,
541 ) -> Result<Self, SynthesisError>
542 where
543 FN: FnOnce() -> Result<T, SynthesisError>,
544 T: Borrow<TEAffine<P>>,
545 {
546 let cofactor_weight = BitIterator::new(P::COFACTOR).filter(|b| *b).count();
547 // If we multiply by r, we actually multiply by r - 2.
548 let r_minus_1 = (-P::ScalarField::one()).into_repr();
549 let r_weight = BitIterator::new(&r_minus_1).filter(|b| *b).count();
550
551 // We pick the most efficient method of performing the prime order check:
552 // If the cofactor has lower hamming weight than the scalar field's modulus,
553 // we first multiply by the inverse of the cofactor, and then, after allocating,
554 // multiply by the cofactor. This ensures the resulting point has no cofactors
555 //
556 // Else, we multiply by the scalar field's modulus and ensure that the result
557 // is zero.
558 if cofactor_weight < r_weight {
559 let ge = Self::alloc(cs.ns(|| "Alloc checked"), || {
560 value_gen().map(|ge| ge.borrow().mul_by_cofactor_inv())
561 })?;
562 let mut seen_one = false;
563 let mut result = Self::zero(cs.ns(|| "result"))?;
564 for (i, b) in BitIterator::new(P::COFACTOR).enumerate() {
565 let mut cs = cs.ns(|| format!("Iteration {}", i));
566
567 let old_seen_one = seen_one;
568 if seen_one {
569 result.double_in_place(cs.ns(|| "Double"))?;
570 } else {
571 seen_one = b;
572 }
573
574 if b {
575 result = if old_seen_one {
576 result.add(cs.ns(|| "Add"), &ge)?
577 } else {
578 ge.clone()
579 };
580 }
581 }
582 Ok(result)
583 } else {
584 let ge = Self::alloc(cs.ns(|| "Alloc checked"), value_gen)?;
585 let mut seen_one = false;
586 let mut result = Self::zero(cs.ns(|| "result"))?;
587 // Returns bits in big-endian order
588 for (i, b) in BitIterator::new(r_minus_1).enumerate() {
589 let mut cs = cs.ns(|| format!("Iteration {}", i));
590
591 let old_seen_one = seen_one;
592 if seen_one {
593 result.double_in_place(cs.ns(|| "Double"))?;
594 } else {
595 seen_one = b;
596 }
597
598 if b {
599 result = if old_seen_one {
600 result.add(cs.ns(|| "Add"), &ge)?
601 } else {
602 ge.clone()
603 };
604 }
605 }
606 let neg_ge = ge.negate(cs.ns(|| "Negate ge"))?;
607 neg_ge.enforce_equal(cs.ns(|| "Check equals"), &result)?;
608 Ok(ge)
609 }
610 }
611
612 fn alloc_input<FN, T, CS: ConstraintSystem<ConstraintF>>(
613 mut cs: CS,
614 value_gen: FN,
615 ) -> Result<Self, SynthesisError>
616 where
617 FN: FnOnce() -> Result<T, SynthesisError>,
618 T: Borrow<TEAffine<P>>,
619 {
620 let (x, y) = match value_gen() {
621 Ok(ge) => {
622 let ge = *ge.borrow();
623 (Ok(ge.x), Ok(ge.y))
624 },
625 _ => (
626 Err(SynthesisError::AssignmentMissing),
627 Err(SynthesisError::AssignmentMissing),
628 ),
629 };
630
631 let d = P::COEFF_D;
632 let a = P::COEFF_A;
633
634 let x = F::alloc_input(&mut cs.ns(|| "x"), || x)?;
635 let y = F::alloc_input(&mut cs.ns(|| "y"), || y)?;
636
637 // Check that ax^2 + y^2 = 1 + dx^2y^2
638 // We do this by checking that ax^2 - 1 = y^2 * (dx^2 - 1)
639 let x2 = x.square(&mut cs.ns(|| "x^2"))?;
640 let y2 = y.square(&mut cs.ns(|| "y^2"))?;
641
642 let one = P::BaseField::one();
643 let d_x2_minus_one = x2
644 .mul_by_constant(cs.ns(|| "d * x^2"), &d)?
645 .add_constant(cs.ns(|| "d * x^2 - 1"), &one.neg())?;
646
647 let a_x2_minus_one = x2
648 .mul_by_constant(cs.ns(|| "a * x^2"), &a)?
649 .add_constant(cs.ns(|| "a * x^2 - 1"), &one.neg())?;
650
651 d_x2_minus_one.mul_equals(cs.ns(|| "on curve check"), &y2, &a_x2_minus_one)?;
652 Ok(Self::new(x, y))
653 }
654 }
655}
656
657mod projective_impl {
658 use super::*;
659 use crate::{Assignment, Vec};
660 use algebra::{
661 curves::twisted_edwards_extended::GroupProjective as TEProjective, AffineCurve, Field,
662 PrimeField, ProjectiveCurve,
663 };
664 use core::ops::Neg;
665
666 impl<P, ConstraintF, F> GroupGadget<TEProjective<P>, ConstraintF>
667 for AffineGadget<P, ConstraintF, F>
668 where
669 P: TEModelParameters,
670 ConstraintF: Field,
671 F: FieldGadget<P::BaseField, ConstraintF>,
672 {
673 type Value = TEProjective<P>;
674 type Variable = (F::Variable, F::Variable);
675
676 #[inline]
677 fn get_value(&self) -> Option<Self::Value> {
678 match (self.x.get_value(), self.y.get_value()) {
679 (Some(x), Some(y)) => Some(TEAffine::new(x, y).into()),
680 (..) => None,
681 }
682 }
683
684 #[inline]
685 fn get_variable(&self) -> Self::Variable {
686 (self.x.get_variable(), self.y.get_variable())
687 }
688
689 #[inline]
690 fn zero<CS: ConstraintSystem<ConstraintF>>(mut cs: CS) -> Result<Self, SynthesisError> {
691 Ok(Self::new(
692 F::zero(cs.ns(|| "zero"))?,
693 F::one(cs.ns(|| "one"))?,
694 ))
695 }
696
697 /// Optimized constraints for checking Edwards point addition from ZCash
698 /// developers Daira Hopwood and Sean Bowe. Requires only 6 constraints
699 /// compared to 7 for the straightforward version we had earlier.
700 fn add<CS: ConstraintSystem<ConstraintF>>(
701 &self,
702 mut cs: CS,
703 other: &Self,
704 ) -> Result<Self, SynthesisError> {
705 let a = P::COEFF_A;
706 let d = P::COEFF_D;
707
708 // Compute U = (x1 + y1) * (x2 + y2)
709 let u1 = self
710 .x
711 .mul_by_constant(cs.ns(|| "-A * x1"), &a.neg())?
712 .add(cs.ns(|| "-A * x1 + y1"), &self.y)?;
713 let u2 = other.x.add(cs.ns(|| "x2 + y2"), &other.y)?;
714
715 let u = u1.mul(cs.ns(|| "(-A * x1 + y1) * (x2 + y2)"), &u2)?;
716
717 // Compute v0 = x1 * y2
718 let v0 = other.y.mul(&mut cs.ns(|| "v0"), &self.x)?;
719
720 // Compute v1 = x2 * y1
721 let v1 = other.x.mul(&mut cs.ns(|| "v1"), &self.y)?;
722
723 // Compute C = d*v0*v1
724 let v2 = v0
725 .mul(cs.ns(|| "v0 * v1"), &v1)?
726 .mul_by_constant(cs.ns(|| "D * v0 * v1"), &d)?;
727
728 // Compute x3 = (v0 + v1) / (1 + v2)
729 let x3 = F::alloc(&mut cs.ns(|| "x3"), || {
730 let t0 = v0.get_value().get()? + &v1.get_value().get()?;
731 let t1 = P::BaseField::one() + &v2.get_value().get()?;
732 Ok(t0 * &t1.inverse().get()?)
733 })?;
734
735 let one = P::BaseField::one();
736 let v2_plus_one = v2.add_constant(cs.ns(|| "v2 + 1"), &one)?;
737 let v0_plus_v1 = v0.add(cs.ns(|| "v0 + v1"), &v1)?;
738 x3.mul_equals(cs.ns(|| "check x3"), &v2_plus_one, &v0_plus_v1)?;
739
740 // Compute y3 = (U + a * v0 - v1) / (1 - v2)
741 let y3 = F::alloc(&mut cs.ns(|| "y3"), || {
742 let t0 =
743 u.get_value().get()? + &(a * &v0.get_value().get()?) - &v1.get_value().get()?;
744 let t1 = P::BaseField::one() - &v2.get_value().get()?;
745 Ok(t0 * &t1.inverse().get()?)
746 })?;
747
748 let one_minus_v2 = v2
749 .add_constant(cs.ns(|| "v2 - 1"), &(-one))?
750 .negate(cs.ns(|| "1 - v2"))?;
751 let a_v0 = v0.mul_by_constant(cs.ns(|| "a * v0"), &a)?;
752 let u_plus_a_v0_minus_v1 = u
753 .add(cs.ns(|| "u + a * v0"), &a_v0)?
754 .sub(cs.ns(|| "u + a * v0 - v1"), &v1)?;
755
756 y3.mul_equals(cs.ns(|| "check y3"), &one_minus_v2, &u_plus_a_v0_minus_v1)?;
757
758 Ok(Self::new(x3, y3))
759 }
760
761 fn add_constant<CS: ConstraintSystem<ConstraintF>>(
762 &self,
763 mut cs: CS,
764 other: &TEProjective<P>,
765 ) -> Result<Self, SynthesisError> {
766 let a = P::COEFF_A;
767 let d = P::COEFF_D;
768 let other = other.into_affine();
769 let other_x = other.x;
770 let other_y = other.y;
771
772 // Compute U = (x1 + y1) * (x2 + y2)
773 let u1 = self
774 .x
775 .mul_by_constant(cs.ns(|| "-A * x1"), &a.neg())?
776 .add(cs.ns(|| "-A * x1 + y1"), &self.y)?;
777 let u2 = other_x + &other_y;
778
779 let u = u1.mul_by_constant(cs.ns(|| "(-A * x1 + y1) * (x2 + y2)"), &u2)?;
780
781 // Compute v0 = x1 * y2
782 let v0 = self.x.mul_by_constant(&mut cs.ns(|| "v0"), &other_y)?;
783
784 // Compute v1 = x2 * y1
785 let v1 = self.y.mul_by_constant(&mut cs.ns(|| "v1"), &other.x)?;
786
787 // Compute C = d*v0*v1
788 let v2 = v0
789 .mul(cs.ns(|| "v0 * v1"), &v1)?
790 .mul_by_constant(cs.ns(|| "D * v0 * v1"), &d)?;
791
792 // Compute x3 = (v0 + v1) / (1 + v2)
793 let x3 = F::alloc(&mut cs.ns(|| "x3"), || {
794 let t0 = v0.get_value().get()? + &v1.get_value().get()?;
795 let t1 = P::BaseField::one() + &v2.get_value().get()?;
796 Ok(t0 * &t1.inverse().get()?)
797 })?;
798
799 let one = P::BaseField::one();
800 let v2_plus_one = v2.add_constant(cs.ns(|| "v2 + 1"), &one)?;
801 let v0_plus_v1 = v0.add(cs.ns(|| "v0 + v1"), &v1)?;
802 x3.mul_equals(cs.ns(|| "check x3"), &v2_plus_one, &v0_plus_v1)?;
803
804 // Compute y3 = (U + a * v0 - v1) / (1 - v2)
805 let y3 = F::alloc(&mut cs.ns(|| "y3"), || {
806 let t0 =
807 u.get_value().get()? + &(a * &v0.get_value().get()?) - &v1.get_value().get()?;
808 let t1 = P::BaseField::one() - &v2.get_value().get()?;
809 Ok(t0 * &t1.inverse().get()?)
810 })?;
811
812 let one_minus_v2 = v2
813 .add_constant(cs.ns(|| "v2 - 1"), &(-one))?
814 .negate(cs.ns(|| "1 - v2"))?;
815 let a_v0 = v0.mul_by_constant(cs.ns(|| "a * v0"), &a)?;
816 let u_plus_a_v0_minus_v1 = u
817 .add(cs.ns(|| "u + a * v0"), &a_v0)?
818 .sub(cs.ns(|| "u + a * v0 - v1"), &v1)?;
819
820 y3.mul_equals(cs.ns(|| "check y3"), &one_minus_v2, &u_plus_a_v0_minus_v1)?;
821
822 Ok(Self::new(x3, y3))
823 }
824
825 fn double_in_place<CS: ConstraintSystem<ConstraintF>>(
826 &mut self,
827 mut cs: CS,
828 ) -> Result<(), SynthesisError> {
829 let a = P::COEFF_A;
830
831 // xy
832 let xy = self.x.mul(cs.ns(|| "x * y"), &self.y)?;
833 let x2 = self.x.square(cs.ns(|| "x * x"))?;
834 let y2 = self.y.square(cs.ns(|| "y * y"))?;
835
836 let a_x2 = x2.mul_by_constant(cs.ns(|| "a * x^2"), &a)?;
837
838 // Compute x3 = (2xy) / (ax^2 + y^2)
839 let x3 = F::alloc(&mut cs.ns(|| "x3"), || {
840 let t0 = xy.get_value().get()?.double();
841 let t1 = a * &x2.get_value().get()? + &y2.get_value().get()?;
842 Ok(t0 * &t1.inverse().get()?)
843 })?;
844
845 let a_x2_plus_y2 = a_x2.add(cs.ns(|| "v2 + 1"), &y2)?;
846 let two_xy = xy.double(cs.ns(|| "2xy"))?;
847 x3.mul_equals(cs.ns(|| "check x3"), &a_x2_plus_y2, &two_xy)?;
848
849 // Compute y3 = (y^2 - ax^2) / (2 - ax^2 - y^2)
850 let two = P::BaseField::one().double();
851 let y3 = F::alloc(&mut cs.ns(|| "y3"), || {
852 let a_x2 = a * &x2.get_value().get()?;
853 let t0 = y2.get_value().get()? - &a_x2;
854 let t1 = two - &a_x2 - &y2.get_value().get()?;
855 Ok(t0 * &t1.inverse().get()?)
856 })?;
857 let y2_minus_a_x2 = y2.sub(cs.ns(|| "y^2 - ax^2"), &a_x2)?;
858 let two_minus_ax2_minus_y2 = a_x2
859 .add(cs.ns(|| "ax2 + y2"), &y2)?
860 .negate(cs.ns(|| "-ax2 - y2"))?
861 .add_constant(cs.ns(|| "2 -ax2 - y2"), &two)?;
862
863 y3.mul_equals(
864 cs.ns(|| "check y3"),
865 &two_minus_ax2_minus_y2,
866 &y2_minus_a_x2,
867 )?;
868 self.x = x3;
869 self.y = y3;
870
871 Ok(())
872 }
873
874 fn negate<CS: ConstraintSystem<ConstraintF>>(
875 &self,
876 mut cs: CS,
877 ) -> Result<Self, SynthesisError> {
878 Ok(Self::new(
879 self.x.negate(cs.ns(|| "negate x"))?,
880 self.y.clone(),
881 ))
882 }
883
884 fn precomputed_base_scalar_mul<'a, CS, I, B>(
885 &mut self,
886 mut cs: CS,
887 scalar_bits_with_base_powers: I,
888 ) -> Result<(), SynthesisError>
889 where
890 CS: ConstraintSystem<ConstraintF>,
891 I: Iterator<Item = (B, &'a TEProjective<P>)>,
892 B: Borrow<Boolean>,
893 {
894 let scalar_bits_with_base_powers: Vec<_> = scalar_bits_with_base_powers
895 .map(|(bit, base)| (bit.borrow().clone(), base.clone()))
896 .collect();
897 let zero = TEProjective::zero();
898 for (i, bits_base_powers) in scalar_bits_with_base_powers.chunks(2).enumerate() {
899 let mut cs = cs.ns(|| format!("Chunk {}", i));
900 if bits_base_powers.len() == 2 {
901 let bits = [bits_base_powers[0].0, bits_base_powers[1].0];
902 let base_powers = [bits_base_powers[0].1, bits_base_powers[1].1];
903
904 let mut table = [
905 zero,
906 base_powers[0],
907 base_powers[1],
908 base_powers[0] + &base_powers[1],
909 ];
910
911 TEProjective::batch_normalization(&mut table);
912 let x_s = [table[0].x, table[1].x, table[2].x, table[3].x];
913 let y_s = [table[0].y, table[1].y, table[2].y, table[3].y];
914
915 let x: F = F::two_bit_lookup(cs.ns(|| "Lookup x"), &bits, &x_s)?;
916 let y: F = F::two_bit_lookup(cs.ns(|| "Lookup y"), &bits, &y_s)?;
917 let adder: Self = Self::new(x, y);
918 *self = <Self as GroupGadget<TEProjective<P>, ConstraintF>>::add(
919 self,
920 &mut cs.ns(|| "Add"),
921 &adder,
922 )?;
923 } else if bits_base_powers.len() == 1 {
924 let bit = bits_base_powers[0].0;
925 let base_power = bits_base_powers[0].1;
926 let new_encoded =
927 self.add_constant(&mut cs.ns(|| "Add base power"), &base_power)?;
928 *self = Self::conditionally_select(
929 &mut cs.ns(|| "Conditional Select"),
930 &bit,
931 &new_encoded,
932 &self,
933 )?;
934 }
935 }
936
937 Ok(())
938 }
939
940 fn precomputed_base_3_bit_signed_digit_scalar_mul<'a, CS, I, J, B>(
941 mut cs: CS,
942 bases: &[B],
943 scalars: &[J],
944 ) -> Result<Self, SynthesisError>
945 where
946 CS: ConstraintSystem<ConstraintF>,
947 I: Borrow<[Boolean]>,
948 J: Borrow<[I]>,
949 B: Borrow<[TEProjective<P>]>,
950 {
951 const CHUNK_SIZE: usize = 3;
952 let mut edwards_result: Option<AffineGadget<P, ConstraintF, F>> = None;
953 let mut result: Option<MontgomeryAffineGadget<P, ConstraintF, F>> = None;
954
955 let mut process_segment_result =
956 |mut cs: r1cs_core::Namespace<_, _>,
957 result: &MontgomeryAffineGadget<P, ConstraintF, F>|
958 -> Result<(), SynthesisError> {
959 let segment_result = result.into_edwards(cs.ns(|| "segment result"))?;
960 match edwards_result {
961 None => {
962 edwards_result = Some(segment_result);
963 },
964 Some(ref mut edwards_result) => {
965 *edwards_result = GroupGadget::<TEAffine<P>, ConstraintF>::add(
966 &segment_result,
967 cs.ns(|| "edwards addition"),
968 edwards_result,
969 )?;
970 },
971 }
972
973 Ok(())
974 };
975
976 // Compute ∏(h_i^{m_i}) for all i.
977 for (segment_i, (segment_bits_chunks, segment_powers)) in
978 scalars.iter().zip(bases.iter()).enumerate()
979 {
980 for (i, (bits, base_power)) in segment_bits_chunks
981 .borrow()
982 .iter()
983 .zip(segment_powers.borrow().iter())
984 .enumerate()
985 {
986 let base_power = base_power.borrow();
987 let mut acc_power = *base_power;
988 let mut coords = vec![];
989 for _ in 0..4 {
990 coords.push(acc_power);
991 acc_power += base_power;
992 }
993
994 let bits = bits.borrow().to_bits(
995 &mut cs.ns(|| format!("Convert Scalar {}, {} to bits", segment_i, i)),
996 )?;
997 if bits.len() != CHUNK_SIZE {
998 return Err(SynthesisError::Unsatisfiable);
999 }
1000
1001 let coords = coords
1002 .iter()
1003 .map(|p| {
1004 let p = p.into_affine();
1005 MontgomeryAffineGadget::<P, ConstraintF, F>::from_edwards_to_coords(&p)
1006 .unwrap()
1007 })
1008 .collect::<Vec<_>>();
1009
1010 let x_coeffs = coords.iter().map(|p| p.0).collect::<Vec<_>>();
1011 let y_coeffs = coords.iter().map(|p| p.1).collect::<Vec<_>>();
1012
1013 let precomp = Boolean::and(
1014 cs.ns(|| format!("precomp in window {}, {}", segment_i, i)),
1015 &bits[0],
1016 &bits[1],
1017 )?;
1018
1019 let x = F::zero(cs.ns(|| format!("x in window {}, {}", segment_i, i)))?
1020 .conditionally_add_constant(
1021 cs.ns(|| format!("add bool 00 in window {}, {}", segment_i, i)),
1022 &Boolean::constant(true),
1023 x_coeffs[0],
1024 )?
1025 .conditionally_add_constant(
1026 cs.ns(|| format!("add bool 01 in window {}, {}", segment_i, i)),
1027 &bits[0],
1028 x_coeffs[1] - &x_coeffs[0],
1029 )?
1030 .conditionally_add_constant(
1031 cs.ns(|| format!("add bool 10 in window {}, {}", segment_i, i)),
1032 &bits[1],
1033 x_coeffs[2] - &x_coeffs[0],
1034 )?
1035 .conditionally_add_constant(
1036 cs.ns(|| format!("add bool 11 in window {}, {}", segment_i, i)),
1037 &precomp,
1038 x_coeffs[3] - &x_coeffs[2] - &x_coeffs[1] + &x_coeffs[0],
1039 )?;
1040
1041 let y = F::three_bit_cond_neg_lookup(
1042 cs.ns(|| format!("y lookup in window {}, {}", segment_i, i)),
1043 &bits,
1044 &precomp,
1045 &y_coeffs,
1046 )?;
1047
1048 let tmp = MontgomeryAffineGadget::new(x, y);
1049
1050 match result {
1051 None => {
1052 result = Some(tmp);
1053 },
1054 Some(ref mut result) => {
1055 *result = tmp.add(
1056 cs.ns(|| format!("addition of window {}, {}", segment_i, i)),
1057 result,
1058 )?;
1059 },
1060 }
1061 }
1062
1063 process_segment_result(
1064 cs.ns(|| format!("window {}", segment_i)),
1065 &result.unwrap(),
1066 )?;
1067 result = None;
1068 }
1069 if result.is_some() {
1070 process_segment_result(cs.ns(|| "leftover"), &result.unwrap())?;
1071 }
1072 Ok(edwards_result.unwrap())
1073 }
1074
1075 fn cost_of_add() -> usize {
1076 4 + 2 * F::cost_of_mul()
1077 }
1078
1079 fn cost_of_double() -> usize {
1080 4 + F::cost_of_mul()
1081 }
1082 }
1083
1084 impl<P, ConstraintF, F> AllocGadget<TEProjective<P>, ConstraintF>
1085 for AffineGadget<P, ConstraintF, F>
1086 where
1087 P: TEModelParameters,
1088 ConstraintF: Field,
1089 F: FieldGadget<P::BaseField, ConstraintF>,
1090 Self: GroupGadget<TEProjective<P>, ConstraintF>,
1091 {
1092 fn alloc<FN, T, CS: ConstraintSystem<ConstraintF>>(
1093 mut cs: CS,
1094 value_gen: FN,
1095 ) -> Result<Self, SynthesisError>
1096 where
1097 FN: FnOnce() -> Result<T, SynthesisError>,
1098 T: Borrow<TEProjective<P>>,
1099 {
1100 let (x, y) = match value_gen() {
1101 Ok(ge) => {
1102 let ge = ge.borrow().into_affine();
1103 (Ok(ge.x), Ok(ge.y))
1104 },
1105 _ => (
1106 Err(SynthesisError::AssignmentMissing),
1107 Err(SynthesisError::AssignmentMissing),
1108 ),
1109 };
1110
1111 let d = P::COEFF_D;
1112 let a = P::COEFF_A;
1113
1114 let x = F::alloc(&mut cs.ns(|| "x"), || x)?;
1115 let y = F::alloc(&mut cs.ns(|| "y"), || y)?;
1116
1117 // Check that ax^2 + y^2 = 1 + dx^2y^2
1118 // We do this by checking that ax^2 - 1 = y^2 * (dx^2 - 1)
1119 let x2 = x.square(&mut cs.ns(|| "x^2"))?;
1120 let y2 = y.square(&mut cs.ns(|| "y^2"))?;
1121
1122 let one = P::BaseField::one();
1123 let d_x2_minus_one = x2
1124 .mul_by_constant(cs.ns(|| "d * x^2"), &d)?
1125 .add_constant(cs.ns(|| "d * x^2 - 1"), &one.neg())?;
1126
1127 let a_x2_minus_one = x2
1128 .mul_by_constant(cs.ns(|| "a * x^2"), &a)?
1129 .add_constant(cs.ns(|| "a * x^2 - 1"), &one.neg())?;
1130
1131 d_x2_minus_one.mul_equals(cs.ns(|| "on curve check"), &y2, &a_x2_minus_one)?;
1132 Ok(Self::new(x, y))
1133 }
1134
1135 fn alloc_checked<FN, T, CS: ConstraintSystem<ConstraintF>>(
1136 mut cs: CS,
1137 value_gen: FN,
1138 ) -> Result<Self, SynthesisError>
1139 where
1140 FN: FnOnce() -> Result<T, SynthesisError>,
1141 T: Borrow<TEProjective<P>>,
1142 {
1143 let cofactor_weight = BitIterator::new(P::COFACTOR).filter(|b| *b).count();
1144 // If we multiply by r, we actually multiply by r - 2.
1145 let r_minus_1 = (-P::ScalarField::one()).into_repr();
1146 let r_weight = BitIterator::new(&r_minus_1).filter(|b| *b).count();
1147
1148 // We pick the most efficient method of performing the prime order check:
1149 // If the cofactor has lower hamming weight than the scalar field's modulus,
1150 // we first multiply by the inverse of the cofactor, and then, after allocating,
1151 // multiply by the cofactor. This ensures the resulting point has no cofactors
1152 //
1153 // Else, we multiply by the scalar field's modulus and ensure that the result
1154 // is zero.
1155 if cofactor_weight < r_weight {
1156 let ge = Self::alloc(cs.ns(|| "Alloc checked"), || {
1157 value_gen().map(|ge| {
1158 ge.borrow()
1159 .into_affine()
1160 .mul_by_cofactor_inv()
1161 .into_projective()
1162 })
1163 })?;
1164 let mut seen_one = false;
1165 let mut result = Self::zero(cs.ns(|| "result"))?;
1166 for (i, b) in BitIterator::new(P::COFACTOR).enumerate() {
1167 let mut cs = cs.ns(|| format!("Iteration {}", i));
1168
1169 let old_seen_one = seen_one;
1170 if seen_one {
1171 result.double_in_place(cs.ns(|| "Double"))?;
1172 } else {
1173 seen_one = b;
1174 }
1175
1176 if b {
1177 result = if old_seen_one {
1178 result.add(cs.ns(|| "Add"), &ge)?
1179 } else {
1180 ge.clone()
1181 };
1182 }
1183 }
1184 Ok(result)
1185 } else {
1186 let ge = Self::alloc(cs.ns(|| "Alloc checked"), value_gen)?;
1187 let mut seen_one = false;
1188 let mut result = Self::zero(cs.ns(|| "result"))?;
1189 // Returns bits in big-endian order
1190 for (i, b) in BitIterator::new(r_minus_1).enumerate() {
1191 let mut cs = cs.ns(|| format!("Iteration {}", i));
1192
1193 let old_seen_one = seen_one;
1194 if seen_one {
1195 result.double_in_place(cs.ns(|| "Double"))?;
1196 } else {
1197 seen_one = b;
1198 }
1199
1200 if b {
1201 result = if old_seen_one {
1202 result.add(cs.ns(|| "Add"), &ge)?
1203 } else {
1204 ge.clone()
1205 };
1206 }
1207 }
1208 let neg_ge = ge.negate(cs.ns(|| "Negate ge"))?;
1209 neg_ge.enforce_equal(cs.ns(|| "Check equals"), &result)?;
1210 Ok(ge)
1211 }
1212 }
1213
1214 fn alloc_input<FN, T, CS: ConstraintSystem<ConstraintF>>(
1215 mut cs: CS,
1216 value_gen: FN,
1217 ) -> Result<Self, SynthesisError>
1218 where
1219 FN: FnOnce() -> Result<T, SynthesisError>,
1220 T: Borrow<TEProjective<P>>,
1221 {
1222 let (x, y) = match value_gen() {
1223 Ok(ge) => {
1224 let ge = ge.borrow().into_affine();
1225 (Ok(ge.x), Ok(ge.y))
1226 },
1227 _ => (
1228 Err(SynthesisError::AssignmentMissing),
1229 Err(SynthesisError::AssignmentMissing),
1230 ),
1231 };
1232
1233 let d = P::COEFF_D;
1234 let a = P::COEFF_A;
1235
1236 let x = F::alloc_input(&mut cs.ns(|| "x"), || x)?;
1237 let y = F::alloc_input(&mut cs.ns(|| "y"), || y)?;
1238
1239 // Check that ax^2 + y^2 = 1 + dx^2y^2
1240 // We do this by checking that ax^2 - 1 = y^2 * (dx^2 - 1)
1241 let x2 = x.square(&mut cs.ns(|| "x^2"))?;
1242 let y2 = y.square(&mut cs.ns(|| "y^2"))?;
1243
1244 let one = P::BaseField::one();
1245 let d_x2_minus_one = x2
1246 .mul_by_constant(cs.ns(|| "d * x^2"), &d)?
1247 .add_constant(cs.ns(|| "d * x^2 - 1"), &one.neg())?;
1248
1249 let a_x2_minus_one = x2
1250 .mul_by_constant(cs.ns(|| "a * x^2"), &a)?
1251 .add_constant(cs.ns(|| "a * x^2 - 1"), &one.neg())?;
1252
1253 d_x2_minus_one.mul_equals(cs.ns(|| "on curve check"), &y2, &a_x2_minus_one)?;
1254 Ok(Self::new(x, y))
1255 }
1256 }
1257}
1258
1259impl<P, ConstraintF, F> CondSelectGadget<ConstraintF> for AffineGadget<P, ConstraintF, F>
1260where
1261 P: TEModelParameters,
1262 ConstraintF: Field,
1263 F: FieldGadget<P::BaseField, ConstraintF>,
1264{
1265 #[inline]
1266 fn conditionally_select<CS: ConstraintSystem<ConstraintF>>(
1267 mut cs: CS,
1268 cond: &Boolean,
1269 first: &Self,
1270 second: &Self,
1271 ) -> Result<Self, SynthesisError> {
1272 let x = F::conditionally_select(&mut cs.ns(|| "x"), cond, &first.x, &second.x)?;
1273 let y = F::conditionally_select(&mut cs.ns(|| "y"), cond, &first.y, &second.y)?;
1274
1275 Ok(Self::new(x, y))
1276 }
1277
1278 fn cost() -> usize {
1279 2 * <F as CondSelectGadget<ConstraintF>>::cost()
1280 }
1281}
1282
1283impl<P, ConstraintF, F> EqGadget<ConstraintF> for AffineGadget<P, ConstraintF, F>
1284where
1285 P: TEModelParameters,
1286 ConstraintF: Field,
1287 F: FieldGadget<P::BaseField, ConstraintF>,
1288{
1289}
1290
1291impl<P, ConstraintF, F> ConditionalEqGadget<ConstraintF> for AffineGadget<P, ConstraintF, F>
1292where
1293 P: TEModelParameters,
1294 ConstraintF: Field,
1295 F: FieldGadget<P::BaseField, ConstraintF>,
1296{
1297 #[inline]
1298 fn conditional_enforce_equal<CS: ConstraintSystem<ConstraintF>>(
1299 &self,
1300 mut cs: CS,
1301 other: &Self,
1302 condition: &Boolean,
1303 ) -> Result<(), SynthesisError> {
1304 self.x.conditional_enforce_equal(
1305 &mut cs.ns(|| "X Coordinate Conditional Equality"),
1306 &other.x,
1307 condition,
1308 )?;
1309 self.y.conditional_enforce_equal(
1310 &mut cs.ns(|| "Y Coordinate Conditional Equality"),
1311 &other.y,
1312 condition,
1313 )?;
1314 Ok(())
1315 }
1316
1317 fn cost() -> usize {
1318 2 * <F as ConditionalEqGadget<ConstraintF>>::cost()
1319 }
1320}
1321
1322impl<P, ConstraintF, F> NEqGadget<ConstraintF> for AffineGadget<P, ConstraintF, F>
1323where
1324 P: TEModelParameters,
1325 ConstraintF: Field,
1326 F: FieldGadget<P::BaseField, ConstraintF>,
1327{
1328 #[inline]
1329 fn enforce_not_equal<CS: ConstraintSystem<ConstraintF>>(
1330 &self,
1331 mut cs: CS,
1332 other: &Self,
1333 ) -> Result<(), SynthesisError> {
1334 self.x
1335 .enforce_not_equal(&mut cs.ns(|| "X Coordinate Inequality"), &other.x)?;
1336 self.y
1337 .enforce_not_equal(&mut cs.ns(|| "Y Coordinate Inequality"), &other.y)?;
1338 Ok(())
1339 }
1340
1341 fn cost() -> usize {
1342 2 * <F as NEqGadget<ConstraintF>>::cost()
1343 }
1344}
1345
1346impl<P, ConstraintF, F> ToBitsGadget<ConstraintF> for AffineGadget<P, ConstraintF, F>
1347where
1348 P: TEModelParameters,
1349 ConstraintF: Field,
1350 F: FieldGadget<P::BaseField, ConstraintF>,
1351{
1352 fn to_bits<CS: ConstraintSystem<ConstraintF>>(
1353 &self,
1354 mut cs: CS,
1355 ) -> Result<Vec<Boolean>, SynthesisError> {
1356 let mut x_bits = self.x.to_bits(cs.ns(|| "X Coordinate To Bits"))?;
1357 let y_bits = self.y.to_bits(cs.ns(|| "Y Coordinate To Bits"))?;
1358 x_bits.extend_from_slice(&y_bits);
1359 Ok(x_bits)
1360 }
1361
1362 fn to_bits_strict<CS: ConstraintSystem<ConstraintF>>(
1363 &self,
1364 mut cs: CS,
1365 ) -> Result<Vec<Boolean>, SynthesisError> {
1366 let mut x_bits = self.x.to_bits_strict(cs.ns(|| "X Coordinate To Bits"))?;
1367 let y_bits = self.y.to_bits_strict(cs.ns(|| "Y Coordinate To Bits"))?;
1368 x_bits.extend_from_slice(&y_bits);
1369
1370 Ok(x_bits)
1371 }
1372}
1373
1374impl<P, ConstraintF, F> ToBytesGadget<ConstraintF> for AffineGadget<P, ConstraintF, F>
1375where
1376 P: TEModelParameters,
1377 ConstraintF: Field,
1378 F: FieldGadget<P::BaseField, ConstraintF>,
1379{
1380 fn to_bytes<CS: ConstraintSystem<ConstraintF>>(
1381 &self,
1382 mut cs: CS,
1383 ) -> Result<Vec<UInt8>, SynthesisError> {
1384 let mut x_bytes = self.x.to_bytes(cs.ns(|| "x"))?;
1385 let y_bytes = self.y.to_bytes(cs.ns(|| "y"))?;
1386 x_bytes.extend_from_slice(&y_bytes);
1387 Ok(x_bytes)
1388 }
1389
1390 fn to_bytes_strict<CS: ConstraintSystem<ConstraintF>>(
1391 &self,
1392 mut cs: CS,
1393 ) -> Result<Vec<UInt8>, SynthesisError> {
1394 let mut x_bytes = self.x.to_bytes_strict(cs.ns(|| "x"))?;
1395 let y_bytes = self.y.to_bytes_strict(cs.ns(|| "y"))?;
1396 x_bytes.extend_from_slice(&y_bytes);
1397
1398 Ok(x_bytes)
1399 }
1400}
1401
1402#[cfg(test)]
1403#[allow(dead_code)]
1404pub(crate) fn test<ConstraintF, P, GG>()
1405where
1406 ConstraintF: Field,
1407 P: TEModelParameters,
1408 GG: GroupGadget<TEAffine<P>, ConstraintF, Value = TEAffine<P>>,
1409{
1410 use crate::{
1411 boolean::AllocatedBit, groups::test::group_test, prelude::*,
1412 test_constraint_system::TestConstraintSystem,
1413 };
1414 use algebra::{test_rng, Group, PrimeField, UniformRand};
1415 use rand::Rng;
1416
1417 group_test::<ConstraintF, TEAffine<P>, GG>();
1418
1419 let mut cs = TestConstraintSystem::new();
1420
1421 let a: TEAffine<P> = UniformRand::rand(&mut test_rng());
1422 let gadget_a = GG::alloc(&mut cs.ns(|| "a"), || Ok(a)).unwrap();
1423 // Check mul_bits
1424 let scalar: <TEAffine<P> as Group>::ScalarField = UniformRand::rand(&mut test_rng());
1425 let native_result = a.mul(&scalar);
1426
1427 let mut scalar: Vec<bool> = BitIterator::new(scalar.into_repr()).collect();
1428 // Get the scalar bits into little-endian form.
1429 scalar.reverse();
1430 let input = Vec::<Boolean>::alloc(cs.ns(|| "Input"), || Ok(scalar)).unwrap();
1431 let zero = GG::zero(cs.ns(|| "zero")).unwrap();
1432 let result = gadget_a
1433 .mul_bits(cs.ns(|| "mul_bits"), &zero, input.iter())
1434 .unwrap();
1435 let gadget_value = result.get_value().expect("Gadget_result failed");
1436 assert_eq!(native_result, gadget_value);
1437
1438 assert!(cs.is_satisfied());
1439
1440 // Test the cost of allocation, conditional selection, and point addition.
1441 let mut cs = TestConstraintSystem::new();
1442
1443 let bit = AllocatedBit::alloc(&mut cs.ns(|| "bool"), || Ok(true))
1444 .unwrap()
1445 .into();
1446
1447 let mut rng = test_rng();
1448 let a: TEAffine<P> = rng.gen();
1449 let b: TEAffine<P> = rng.gen();
1450 let gadget_a = GG::alloc(&mut cs.ns(|| "a"), || Ok(a)).unwrap();
1451 let gadget_b = GG::alloc(&mut cs.ns(|| "b"), || Ok(b)).unwrap();
1452 let alloc_cost = cs.num_constraints();
1453 let _ =
1454 GG::conditionally_select(&mut cs.ns(|| "cond_select"), &bit, &gadget_a, &gadget_b).unwrap();
1455 let cond_select_cost = cs.num_constraints() - alloc_cost;
1456
1457 let _ = gadget_a.add(&mut cs.ns(|| "ab"), &gadget_b).unwrap();
1458 let add_cost = cs.num_constraints() - cond_select_cost - alloc_cost;
1459 assert_eq!(cond_select_cost, <GG as CondSelectGadget<_>>::cost());
1460 assert_eq!(add_cost, GG::cost_of_add());
1461 assert!(cs.is_satisfied());
1462}