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