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