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