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