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