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::{twisted_edwards_extended::GroupAffine as TEAffine, TEModelParameters},
3 BitIterator, Field
4};
5
6use r1cs_core::{ConstraintSystem, SynthesisError};
7
8use crate::prelude::*;
9
10use std::{borrow::Borrow, marker::PhantomData};
11
12pub mod edwards_bls12;
13pub mod edwards_sw6;
14pub mod jubjub;
15#[cfg(test)]
16mod test;
17
18#[derive(Derivative)]
19#[derivative(Debug, Clone)]
20#[derivative(Debug(bound = "P: TEModelParameters, ConstraintF: Field"))]
21#[must_use]
22pub struct AffineGadget<P: TEModelParameters, ConstraintF: Field, F: FieldGadget<P::BaseField, ConstraintF>> {
23 pub x: F,
24 pub y: F,
25 #[derivative(Debug = "ignore")]
26 _params: PhantomData<P>,
27 #[derivative(Debug = "ignore")]
28 _engine: PhantomData<ConstraintF>,
29}
30
31impl<P: TEModelParameters, ConstraintF: Field, F: FieldGadget<P::BaseField, ConstraintF>>
32 AffineGadget<P, ConstraintF, F>
33{
34 pub fn new(x: F, y: F) -> Self {
35 Self {
36 x,
37 y,
38 _params: PhantomData,
39 _engine: PhantomData,
40 }
41 }
42
43 pub fn alloc_without_check<FN, CS: ConstraintSystem<ConstraintF>>(
44 mut cs: CS,
45 value_gen: F,
46 ) -> Result<Self, SynthesisError>
47 where
48 F: FnOnce() -> Result<TEAffine<P>, SynthesisError>,
49 {
50 let (x, y) = match value_gen() {
51 Ok(fe) => (Ok(fe.x), Ok(fe.y)),
52 _ => (
53 Err(SynthesisError::AssignmentMissing),
54 Err(SynthesisError::AssignmentMissing),
55 ),
56 };
57
58 let x = F::alloc(&mut cs.ns(|| "x"), || x)?;
59 let y = F::alloc(&mut cs.ns(|| "y"), || y)?;
60
61 Ok(Self::new(x, y))
62 }
63}
64
65impl<P, ConstraintF, F> PartialEq for AffineGadget<P, ConstraintF, F>
66where
67 P: TEModelParameters,
68 ConstraintF: Field,
69 F: FieldGadget<P::BaseField, ConstraintF>,
70{
71 fn eq(&self, other: &Self) -> bool {
72 self.x == other.x && self.y == other.y
73 }
74}
75
76impl<P, ConstraintF, F> Eq for AffineGadget<P, ConstraintF, F>
77where
78 P: TEModelParameters,
79 ConstraintF: Field,
80 F: FieldGadget<P::BaseField, ConstraintF>,
81{
82}
83
84mod affine_impl {
85 use super::*;
86 use crate::Assignment;
87 use algebra::{curves::AffineCurve, Field, PrimeField};
88 use std::ops::Neg;
89
90 impl<P, ConstraintF, F> GroupGadget<TEAffine<P>, ConstraintF> for AffineGadget<P, ConstraintF, F>
91 where
92 P: TEModelParameters,
93 ConstraintF: Field,
94 F: FieldGadget<P::BaseField, ConstraintF>,
95 {
96 type Value = TEAffine<P>;
97 type Variable = (F::Variable, F::Variable);
98
99 #[inline]
100 fn get_value(&self) -> Option<Self::Value> {
101 match (self.x.get_value(), self.y.get_value()) {
102 (Some(x), Some(y)) => Some(TEAffine::new(x, y)),
103 (..) => None,
104 }
105 }
106
107 #[inline]
108 fn get_variable(&self) -> Self::Variable {
109 (self.x.get_variable(), self.y.get_variable())
110 }
111
112 #[inline]
113 fn zero<CS: ConstraintSystem<ConstraintF>>(mut cs: CS) -> Result<Self, SynthesisError> {
114 Ok(Self::new(
115 F::zero(cs.ns(|| "zero"))?,
116 F::one(cs.ns(|| "one"))?,
117 ))
118 }
119
120 /// Optimized constraints for checking Edwards point addition from ZCash
121 /// developers Daira Hopwood and Sean Bowe. Requires only 6 constraints
122 /// compared to 7 for the straightforward version we had earlier.
123 fn add<CS: ConstraintSystem<ConstraintF>>(
124 &self,
125 mut cs: CS,
126 other: &Self,
127 ) -> Result<Self, SynthesisError> {
128 let a = P::COEFF_A;
129 let d = P::COEFF_D;
130
131 // Compute U = (x1 + y1) * (x2 + y2)
132 let u1 = self
133 .x
134 .mul_by_constant(cs.ns(|| "-A * x1"), &a.neg())?
135 .add(cs.ns(|| "-A * x1 + y1"), &self.y)?;
136 let u2 = other.x.add(cs.ns(|| "x2 + y2"), &other.y)?;
137
138 let u = u1.mul(cs.ns(|| "(-A * x1 + y1) * (x2 + y2)"), &u2)?;
139
140 // Compute v0 = x1 * y2
141 let v0 = other.y.mul(&mut cs.ns(|| "v0"), &self.x)?;
142
143 // Compute v1 = x2 * y1
144 let v1 = other.x.mul(&mut cs.ns(|| "v1"), &self.y)?;
145
146 // Compute C = d*v0*v1
147 let v2 = v0
148 .mul(cs.ns(|| "v0 * v1"), &v1)?
149 .mul_by_constant(cs.ns(|| "D * v0 * v1"), &d)?;
150
151 // Compute x3 = (v0 + v1) / (1 + v2)
152 let x3 = F::alloc(&mut cs.ns(|| "x3"), || {
153 let t0 = v0.get_value().get()? + &v1.get_value().get()?;
154 let t1 = P::BaseField::one() + &v2.get_value().get()?;
155 Ok(t0 * &t1.inverse().get()?)
156 })?;
157
158 let one = P::BaseField::one();
159 let v2_plus_one = v2.add_constant(cs.ns(|| "v2 + 1"), &one)?;
160 let v0_plus_v1 = v0.add(cs.ns(|| "v0 + v1"), &v1)?;
161 x3.mul_equals(cs.ns(|| "check x3"), &v2_plus_one, &v0_plus_v1)?;
162
163 // Compute y3 = (U + a * v0 - v1) / (1 - v2)
164 let y3 = F::alloc(&mut cs.ns(|| "y3"), || {
165 let t0 =
166 u.get_value().get()? + &(a * &v0.get_value().get()?) - &v1.get_value().get()?;
167 let t1 = P::BaseField::one() - &v2.get_value().get()?;
168 Ok(t0 * &t1.inverse().get()?)
169 })?;
170
171 let one_minus_v2 = v2
172 .add_constant(cs.ns(|| "v2 - 1"), &(-one))?
173 .negate(cs.ns(|| "1 - v2"))?;
174 let a_v0 = v0.mul_by_constant(cs.ns(|| "a * v0"), &a)?;
175 let u_plus_a_v0_minus_v1 = u
176 .add(cs.ns(|| "u + a * v0"), &a_v0)?
177 .sub(cs.ns(|| "u + a * v0 - v1"), &v1)?;
178
179 y3.mul_equals(cs.ns(|| "check y3"), &one_minus_v2, &u_plus_a_v0_minus_v1)?;
180
181 Ok(Self::new(x3, y3))
182 }
183
184 fn add_constant<CS: ConstraintSystem<ConstraintF>>(
185 &self,
186 mut cs: CS,
187 other: &TEAffine<P>,
188 ) -> Result<Self, SynthesisError> {
189 let a = P::COEFF_A;
190 let d = P::COEFF_D;
191 let other_x = other.x;
192 let other_y = other.y;
193
194 // Compute U = (x1 + y1) * (x2 + y2)
195 let u1 = self
196 .x
197 .mul_by_constant(cs.ns(|| "-A * x1"), &a.neg())?
198 .add(cs.ns(|| "-A * x1 + y1"), &self.y)?;
199 let u2 = other_x + &other_y;
200
201 let u = u1.mul_by_constant(cs.ns(|| "(-A * x1 + y1) * (x2 + y2)"), &u2)?;
202
203 // Compute v0 = x1 * y2
204 let v0 = self.x.mul_by_constant(&mut cs.ns(|| "v0"), &other_y)?;
205
206 // Compute v1 = x2 * y1
207 let v1 = self.y.mul_by_constant(&mut cs.ns(|| "v1"), &other.x)?;
208
209 // Compute C = d*v0*v1
210 let v2 = v0
211 .mul(cs.ns(|| "v0 * v1"), &v1)?
212 .mul_by_constant(cs.ns(|| "D * v0 * v1"), &d)?;
213
214 // Compute x3 = (v0 + v1) / (1 + v2)
215 let x3 = F::alloc(&mut cs.ns(|| "x3"), || {
216 let t0 = v0.get_value().get()? + &v1.get_value().get()?;
217 let t1 = P::BaseField::one() + &v2.get_value().get()?;
218 Ok(t0 * &t1.inverse().get()?)
219 })?;
220
221 let one = P::BaseField::one();
222 let v2_plus_one = v2.add_constant(cs.ns(|| "v2 + 1"), &one)?;
223 let v0_plus_v1 = v0.add(cs.ns(|| "v0 + v1"), &v1)?;
224 x3.mul_equals(cs.ns(|| "check x3"), &v2_plus_one, &v0_plus_v1)?;
225
226 // Compute y3 = (U + a * v0 - v1) / (1 - v2)
227 let y3 = F::alloc(&mut cs.ns(|| "y3"), || {
228 let t0 =
229 u.get_value().get()? + &(a * &v0.get_value().get()?) - &v1.get_value().get()?;
230 let t1 = P::BaseField::one() - &v2.get_value().get()?;
231 Ok(t0 * &t1.inverse().get()?)
232 })?;
233
234 let one_minus_v2 = v2
235 .add_constant(cs.ns(|| "v2 - 1"), &(-one))?
236 .negate(cs.ns(|| "1 - v2"))?;
237 let a_v0 = v0.mul_by_constant(cs.ns(|| "a * v0"), &a)?;
238 let u_plus_a_v0_minus_v1 = u
239 .add(cs.ns(|| "u + a * v0"), &a_v0)?
240 .sub(cs.ns(|| "u + a * v0 - v1"), &v1)?;
241
242 y3.mul_equals(cs.ns(|| "check y3"), &one_minus_v2, &u_plus_a_v0_minus_v1)?;
243
244 Ok(Self::new(x3, y3))
245 }
246
247 fn double_in_place<CS: ConstraintSystem<ConstraintF>>(
248 &mut self,
249 mut cs: CS,
250 ) -> Result<(), SynthesisError> {
251 let a = P::COEFF_A;
252
253 // xy
254 let xy = self.x.mul(cs.ns(|| "x * y"), &self.y)?;
255 let x2 = self.x.square(cs.ns(|| "x * x"))?;
256 let y2 = self.y.square(cs.ns(|| "y * y"))?;
257
258 let a_x2 = x2.mul_by_constant(cs.ns(|| "a * x^2"), &a)?;
259
260 // Compute x3 = (2xy) / (ax^2 + y^2)
261 let x3 = F::alloc(&mut cs.ns(|| "x3"), || {
262 let t0 = xy.get_value().get()?.double();
263 let t1 = a * &x2.get_value().get()? + &y2.get_value().get()?;
264 Ok(t0 * &t1.inverse().get()?)
265 })?;
266
267 let a_x2_plus_y2 = a_x2.add(cs.ns(|| "v2 + 1"), &y2)?;
268 let two_xy = xy.double(cs.ns(|| "2xy"))?;
269 x3.mul_equals(cs.ns(|| "check x3"), &a_x2_plus_y2, &two_xy)?;
270
271 // Compute y3 = (y^2 - ax^2) / (2 - ax^2 - y^2)
272 let two = P::BaseField::one().double();
273 let y3 = F::alloc(&mut cs.ns(|| "y3"), || {
274 let a_x2 = a * &x2.get_value().get()?;
275 let t0 = y2.get_value().get()? - &a_x2;
276 let t1 = two - &a_x2 - &y2.get_value().get()?;
277 Ok(t0 * &t1.inverse().get()?)
278 })?;
279 let y2_minus_a_x2 = y2.sub(cs.ns(|| "y^2 - ax^2"), &a_x2)?;
280 let two_minus_ax2_minus_y2 = a_x2
281 .add(cs.ns(|| "ax2 + y2"), &y2)?
282 .negate(cs.ns(|| "-ax2 - y2"))?
283 .add_constant(cs.ns(|| "2 -ax2 - y2"), &two)?;
284
285 y3.mul_equals(
286 cs.ns(|| "check y3"),
287 &two_minus_ax2_minus_y2,
288 &y2_minus_a_x2,
289 )?;
290 self.x = x3;
291 self.y = y3;
292
293 Ok(())
294 }
295
296 fn negate<CS: ConstraintSystem<ConstraintF>>(&self, mut cs: CS) -> Result<Self, SynthesisError> {
297 Ok(Self::new(
298 self.x.negate(cs.ns(|| "negate x"))?,
299 self.y.clone(),
300 ))
301 }
302
303 fn cost_of_add() -> usize {
304 4 + 2 * F::cost_of_mul()
305 }
306
307 fn cost_of_double() -> usize {
308 4 + F::cost_of_mul()
309 }
310 }
311
312 impl<P, ConstraintF, F> AllocGadget<TEAffine<P>, ConstraintF> for AffineGadget<P, ConstraintF, F>
313 where
314 P: TEModelParameters,
315 ConstraintF: Field,
316 F: FieldGadget<P::BaseField, ConstraintF>,
317 Self: GroupGadget<TEAffine<P>, ConstraintF>,
318 {
319 fn alloc<FN, T, CS: ConstraintSystem<ConstraintF>>(
320 mut cs: CS,
321 value_gen: FN,
322 ) -> Result<Self, SynthesisError>
323 where
324 FN: FnOnce() -> Result<T, SynthesisError>,
325 T: Borrow<TEAffine<P>>,
326 {
327 let (x, y) = match value_gen() {
328 Ok(ge) => {
329 let ge = *ge.borrow();
330 (Ok(ge.x), Ok(ge.y))
331 },
332 _ => (
333 Err(SynthesisError::AssignmentMissing),
334 Err(SynthesisError::AssignmentMissing),
335 ),
336 };
337
338 let d = P::COEFF_D;
339 let a = P::COEFF_A;
340
341 let x = F::alloc(&mut cs.ns(|| "x"), || x)?;
342 let y = F::alloc(&mut cs.ns(|| "y"), || y)?;
343
344 // Check that ax^2 + y^2 = 1 + dx^2y^2
345 // We do this by checking that ax^2 - 1 = y^2 * (dx^2 - 1)
346 let x2 = x.square(&mut cs.ns(|| "x^2"))?;
347 let y2 = y.square(&mut cs.ns(|| "y^2"))?;
348
349 let one = P::BaseField::one();
350 let d_x2_minus_one = x2
351 .mul_by_constant(cs.ns(|| "d * x^2"), &d)?
352 .add_constant(cs.ns(|| "d * x^2 - 1"), &one.neg())?;
353
354 let a_x2_minus_one = x2
355 .mul_by_constant(cs.ns(|| "a * x^2"), &a)?
356 .add_constant(cs.ns(|| "a * x^2 - 1"), &one.neg())?;
357
358 d_x2_minus_one.mul_equals(cs.ns(|| "on curve check"), &y2, &a_x2_minus_one)?;
359 Ok(Self::new(x, y))
360 }
361
362 fn alloc_checked<FN, T, CS: ConstraintSystem<ConstraintF>>(
363 mut cs: CS,
364 value_gen: FN,
365 ) -> Result<Self, SynthesisError>
366 where
367 FN: FnOnce() -> Result<T, SynthesisError>,
368 T: Borrow<TEAffine<P>>,
369 {
370 let cofactor_weight = BitIterator::new(P::COFACTOR).filter(|b| *b).count();
371 // If we multiply by r, we actually multiply by r - 2.
372 let r_minus_1 = (-P::ScalarField::one()).into_repr();
373 let r_weight = BitIterator::new(&r_minus_1).filter(|b| *b).count();
374
375 // We pick the most efficient method of performing the prime order check:
376 // If the cofactor has lower hamming weight than the scalar field's modulus,
377 // we first multiply by the inverse of the cofactor, and then, after allocating,
378 // multiply by the cofactor. This ensures the resulting point has no cofactors
379 //
380 // Else, we multiply by the scalar field's modulus and ensure that the result
381 // is zero.
382 if cofactor_weight < r_weight {
383 let ge = Self::alloc(cs.ns(|| "Alloc checked"), || {
384 value_gen().map(|ge| ge.borrow().mul_by_cofactor_inv())
385 })?;
386 let mut seen_one = false;
387 let mut result = Self::zero(cs.ns(|| "result"))?;
388 for (i, b) in BitIterator::new(P::COFACTOR).enumerate() {
389 let mut cs = cs.ns(|| format!("Iteration {}", i));
390
391 let old_seen_one = seen_one;
392 if seen_one {
393 result.double_in_place(cs.ns(|| "Double"))?;
394 } else {
395 seen_one = b;
396 }
397
398 if b {
399 result = if old_seen_one {
400 result.add(cs.ns(|| "Add"), &ge)?
401 } else {
402 ge.clone()
403 };
404 }
405 }
406 Ok(result)
407 } else {
408 let ge = Self::alloc(cs.ns(|| "Alloc checked"), value_gen)?;
409 let mut seen_one = false;
410 let mut result = Self::zero(cs.ns(|| "result"))?;
411 // Returns bits in big-endian order
412 for (i, b) in BitIterator::new(r_minus_1).enumerate() {
413 let mut cs = cs.ns(|| format!("Iteration {}", i));
414
415 let old_seen_one = seen_one;
416 if seen_one {
417 result.double_in_place(cs.ns(|| "Double"))?;
418 } else {
419 seen_one = b;
420 }
421
422 if b {
423 result = if old_seen_one {
424 result.add(cs.ns(|| "Add"), &ge)?
425 } else {
426 ge.clone()
427 };
428 }
429 }
430 let neg_ge = ge.negate(cs.ns(|| "Negate ge"))?;
431 neg_ge.enforce_equal(cs.ns(|| "Check equals"), &result)?;
432 Ok(ge)
433 }
434 }
435
436 fn alloc_input<FN, T, CS: ConstraintSystem<ConstraintF>>(
437 mut cs: CS,
438 value_gen: FN,
439 ) -> Result<Self, SynthesisError>
440 where
441 FN: FnOnce() -> Result<T, SynthesisError>,
442 T: Borrow<TEAffine<P>>,
443 {
444 let (x, y) = match value_gen() {
445 Ok(ge) => {
446 let ge = *ge.borrow();
447 (Ok(ge.x), Ok(ge.y))
448 },
449 _ => (
450 Err(SynthesisError::AssignmentMissing),
451 Err(SynthesisError::AssignmentMissing),
452 ),
453 };
454
455 let d = P::COEFF_D;
456 let a = P::COEFF_A;
457
458 let x = F::alloc_input(&mut cs.ns(|| "x"), || x)?;
459 let y = F::alloc_input(&mut cs.ns(|| "y"), || y)?;
460
461 // Check that ax^2 + y^2 = 1 + dx^2y^2
462 // We do this by checking that ax^2 - 1 = y^2 * (dx^2 - 1)
463 let x2 = x.square(&mut cs.ns(|| "x^2"))?;
464 let y2 = y.square(&mut cs.ns(|| "y^2"))?;
465
466 let one = P::BaseField::one();
467 let d_x2_minus_one = x2
468 .mul_by_constant(cs.ns(|| "d * x^2"), &d)?
469 .add_constant(cs.ns(|| "d * x^2 - 1"), &one.neg())?;
470
471 let a_x2_minus_one = x2
472 .mul_by_constant(cs.ns(|| "a * x^2"), &a)?
473 .add_constant(cs.ns(|| "a * x^2 - 1"), &one.neg())?;
474
475 d_x2_minus_one.mul_equals(cs.ns(|| "on curve check"), &y2, &a_x2_minus_one)?;
476 Ok(Self::new(x, y))
477 }
478 }
479}
480
481mod projective_impl {
482 use super::*;
483 use crate::Assignment;
484 use algebra::{
485 curves::twisted_edwards_extended::GroupProjective as TEProjective, AffineCurve, Field,
486 PrimeField, ProjectiveCurve,
487 };
488 use std::ops::Neg;
489
490 impl<P, ConstraintF, F> GroupGadget<TEProjective<P>, ConstraintF> for AffineGadget<P, ConstraintF, F>
491 where
492 P: TEModelParameters,
493 ConstraintF: Field,
494 F: FieldGadget<P::BaseField, ConstraintF>,
495 {
496 type Value = TEProjective<P>;
497 type Variable = (F::Variable, F::Variable);
498
499 #[inline]
500 fn get_value(&self) -> Option<Self::Value> {
501 match (self.x.get_value(), self.y.get_value()) {
502 (Some(x), Some(y)) => Some(TEAffine::new(x, y).into()),
503 (..) => None,
504 }
505 }
506
507 #[inline]
508 fn get_variable(&self) -> Self::Variable {
509 (self.x.get_variable(), self.y.get_variable())
510 }
511
512 #[inline]
513 fn zero<CS: ConstraintSystem<ConstraintF>>(mut cs: CS) -> Result<Self, SynthesisError> {
514 Ok(Self::new(
515 F::zero(cs.ns(|| "zero"))?,
516 F::one(cs.ns(|| "one"))?,
517 ))
518 }
519
520 /// Optimized constraints for checking Edwards point addition from ZCash
521 /// developers Daira Hopwood and Sean Bowe. Requires only 6 constraints
522 /// compared to 7 for the straightforward version we had earlier.
523 fn add<CS: ConstraintSystem<ConstraintF>>(
524 &self,
525 mut cs: CS,
526 other: &Self,
527 ) -> Result<Self, SynthesisError> {
528 let a = P::COEFF_A;
529 let d = P::COEFF_D;
530
531 // Compute U = (x1 + y1) * (x2 + y2)
532 let u1 = self
533 .x
534 .mul_by_constant(cs.ns(|| "-A * x1"), &a.neg())?
535 .add(cs.ns(|| "-A * x1 + y1"), &self.y)?;
536 let u2 = other.x.add(cs.ns(|| "x2 + y2"), &other.y)?;
537
538 let u = u1.mul(cs.ns(|| "(-A * x1 + y1) * (x2 + y2)"), &u2)?;
539
540 // Compute v0 = x1 * y2
541 let v0 = other.y.mul(&mut cs.ns(|| "v0"), &self.x)?;
542
543 // Compute v1 = x2 * y1
544 let v1 = other.x.mul(&mut cs.ns(|| "v1"), &self.y)?;
545
546 // Compute C = d*v0*v1
547 let v2 = v0
548 .mul(cs.ns(|| "v0 * v1"), &v1)?
549 .mul_by_constant(cs.ns(|| "D * v0 * v1"), &d)?;
550
551 // Compute x3 = (v0 + v1) / (1 + v2)
552 let x3 = F::alloc(&mut cs.ns(|| "x3"), || {
553 let t0 = v0.get_value().get()? + &v1.get_value().get()?;
554 let t1 = P::BaseField::one() + &v2.get_value().get()?;
555 Ok(t0 * &t1.inverse().get()?)
556 })?;
557
558 let one = P::BaseField::one();
559 let v2_plus_one = v2.add_constant(cs.ns(|| "v2 + 1"), &one)?;
560 let v0_plus_v1 = v0.add(cs.ns(|| "v0 + v1"), &v1)?;
561 x3.mul_equals(cs.ns(|| "check x3"), &v2_plus_one, &v0_plus_v1)?;
562
563 // Compute y3 = (U + a * v0 - v1) / (1 - v2)
564 let y3 = F::alloc(&mut cs.ns(|| "y3"), || {
565 let t0 =
566 u.get_value().get()? + &(a * &v0.get_value().get()?) - &v1.get_value().get()?;
567 let t1 = P::BaseField::one() - &v2.get_value().get()?;
568 Ok(t0 * &t1.inverse().get()?)
569 })?;
570
571 let one_minus_v2 = v2
572 .add_constant(cs.ns(|| "v2 - 1"), &(-one))?
573 .negate(cs.ns(|| "1 - v2"))?;
574 let a_v0 = v0.mul_by_constant(cs.ns(|| "a * v0"), &a)?;
575 let u_plus_a_v0_minus_v1 = u
576 .add(cs.ns(|| "u + a * v0"), &a_v0)?
577 .sub(cs.ns(|| "u + a * v0 - v1"), &v1)?;
578
579 y3.mul_equals(cs.ns(|| "check y3"), &one_minus_v2, &u_plus_a_v0_minus_v1)?;
580
581 Ok(Self::new(x3, y3))
582 }
583
584 fn add_constant<CS: ConstraintSystem<ConstraintF>>(
585 &self,
586 mut cs: CS,
587 other: &TEProjective<P>,
588 ) -> Result<Self, SynthesisError> {
589 let a = P::COEFF_A;
590 let d = P::COEFF_D;
591 let other = other.into_affine();
592 let other_x = other.x;
593 let other_y = other.y;
594
595 // Compute U = (x1 + y1) * (x2 + y2)
596 let u1 = self
597 .x
598 .mul_by_constant(cs.ns(|| "-A * x1"), &a.neg())?
599 .add(cs.ns(|| "-A * x1 + y1"), &self.y)?;
600 let u2 = other_x + &other_y;
601
602 let u = u1.mul_by_constant(cs.ns(|| "(-A * x1 + y1) * (x2 + y2)"), &u2)?;
603
604 // Compute v0 = x1 * y2
605 let v0 = self.x.mul_by_constant(&mut cs.ns(|| "v0"), &other_y)?;
606
607 // Compute v1 = x2 * y1
608 let v1 = self.y.mul_by_constant(&mut cs.ns(|| "v1"), &other.x)?;
609
610 // Compute C = d*v0*v1
611 let v2 = v0
612 .mul(cs.ns(|| "v0 * v1"), &v1)?
613 .mul_by_constant(cs.ns(|| "D * v0 * v1"), &d)?;
614
615 // Compute x3 = (v0 + v1) / (1 + v2)
616 let x3 = F::alloc(&mut cs.ns(|| "x3"), || {
617 let t0 = v0.get_value().get()? + &v1.get_value().get()?;
618 let t1 = P::BaseField::one() + &v2.get_value().get()?;
619 Ok(t0 * &t1.inverse().get()?)
620 })?;
621
622 let one = P::BaseField::one();
623 let v2_plus_one = v2.add_constant(cs.ns(|| "v2 + 1"), &one)?;
624 let v0_plus_v1 = v0.add(cs.ns(|| "v0 + v1"), &v1)?;
625 x3.mul_equals(cs.ns(|| "check x3"), &v2_plus_one, &v0_plus_v1)?;
626
627 // Compute y3 = (U + a * v0 - v1) / (1 - v2)
628 let y3 = F::alloc(&mut cs.ns(|| "y3"), || {
629 let t0 =
630 u.get_value().get()? + &(a * &v0.get_value().get()?) - &v1.get_value().get()?;
631 let t1 = P::BaseField::one() - &v2.get_value().get()?;
632 Ok(t0 * &t1.inverse().get()?)
633 })?;
634
635 let one_minus_v2 = v2
636 .add_constant(cs.ns(|| "v2 - 1"), &(-one))?
637 .negate(cs.ns(|| "1 - v2"))?;
638 let a_v0 = v0.mul_by_constant(cs.ns(|| "a * v0"), &a)?;
639 let u_plus_a_v0_minus_v1 = u
640 .add(cs.ns(|| "u + a * v0"), &a_v0)?
641 .sub(cs.ns(|| "u + a * v0 - v1"), &v1)?;
642
643 y3.mul_equals(cs.ns(|| "check y3"), &one_minus_v2, &u_plus_a_v0_minus_v1)?;
644
645 Ok(Self::new(x3, y3))
646 }
647
648 fn double_in_place<CS: ConstraintSystem<ConstraintF>>(
649 &mut self,
650 mut cs: CS,
651 ) -> Result<(), SynthesisError> {
652 let a = P::COEFF_A;
653
654 // xy
655 let xy = self.x.mul(cs.ns(|| "x * y"), &self.y)?;
656 let x2 = self.x.square(cs.ns(|| "x * x"))?;
657 let y2 = self.y.square(cs.ns(|| "y * y"))?;
658
659 let a_x2 = x2.mul_by_constant(cs.ns(|| "a * x^2"), &a)?;
660
661 // Compute x3 = (2xy) / (ax^2 + y^2)
662 let x3 = F::alloc(&mut cs.ns(|| "x3"), || {
663 let t0 = xy.get_value().get()?.double();
664 let t1 = a * &x2.get_value().get()? + &y2.get_value().get()?;
665 Ok(t0 * &t1.inverse().get()?)
666 })?;
667
668 let a_x2_plus_y2 = a_x2.add(cs.ns(|| "v2 + 1"), &y2)?;
669 let two_xy = xy.double(cs.ns(|| "2xy"))?;
670 x3.mul_equals(cs.ns(|| "check x3"), &a_x2_plus_y2, &two_xy)?;
671
672 // Compute y3 = (y^2 - ax^2) / (2 - ax^2 - y^2)
673 let two = P::BaseField::one().double();
674 let y3 = F::alloc(&mut cs.ns(|| "y3"), || {
675 let a_x2 = a * &x2.get_value().get()?;
676 let t0 = y2.get_value().get()? - &a_x2;
677 let t1 = two - &a_x2 - &y2.get_value().get()?;
678 Ok(t0 * &t1.inverse().get()?)
679 })?;
680 let y2_minus_a_x2 = y2.sub(cs.ns(|| "y^2 - ax^2"), &a_x2)?;
681 let two_minus_ax2_minus_y2 = a_x2
682 .add(cs.ns(|| "ax2 + y2"), &y2)?
683 .negate(cs.ns(|| "-ax2 - y2"))?
684 .add_constant(cs.ns(|| "2 -ax2 - y2"), &two)?;
685
686 y3.mul_equals(
687 cs.ns(|| "check y3"),
688 &two_minus_ax2_minus_y2,
689 &y2_minus_a_x2,
690 )?;
691 self.x = x3;
692 self.y = y3;
693
694 Ok(())
695 }
696
697 fn negate<CS: ConstraintSystem<ConstraintF>>(&self, mut cs: CS) -> Result<Self, SynthesisError> {
698 Ok(Self::new(
699 self.x.negate(cs.ns(|| "negate x"))?,
700 self.y.clone(),
701 ))
702 }
703
704 fn precomputed_base_scalar_mul<'a, CS, I, B>(
705 &mut self,
706 mut cs: CS,
707 scalar_bits_with_base_powers: I,
708 ) -> Result<(), SynthesisError>
709 where
710 CS: ConstraintSystem<ConstraintF>,
711 I: Iterator<Item = (B, &'a TEProjective<P>)>,
712 B: Borrow<Boolean>,
713 {
714 let scalar_bits_with_base_powers: Vec<_> = scalar_bits_with_base_powers
715 .map(|(bit, base)| (bit.borrow().clone(), base.clone()))
716 .collect();
717 let zero = TEProjective::zero();
718 for (i, bits_base_powers) in scalar_bits_with_base_powers.chunks(2).enumerate() {
719 let mut cs = cs.ns(|| format!("Chunk {}", i));
720 if bits_base_powers.len() == 2 {
721 let bits = [bits_base_powers[0].0, bits_base_powers[1].0];
722 let base_powers = [bits_base_powers[0].1, bits_base_powers[1].1];
723
724 let mut table = [
725 zero,
726 base_powers[0],
727 base_powers[1],
728 base_powers[0] + &base_powers[1],
729 ];
730
731 TEProjective::batch_normalization(&mut table);
732 let x_s = [table[0].x, table[1].x, table[2].x, table[3].x];
733 let y_s = [table[0].y, table[1].y, table[2].y, table[3].y];
734
735 let x: F = F::two_bit_lookup(cs.ns(|| "Lookup x"), &bits, &x_s)?;
736 let y: F = F::two_bit_lookup(cs.ns(|| "Lookup y"), &bits, &y_s)?;
737 let adder: Self = Self::new(x, y);
738 *self = <Self as GroupGadget<TEProjective<P>, ConstraintF>>::add(
739 self,
740 &mut cs.ns(|| "Add"),
741 &adder,
742 )?;
743 } else if bits_base_powers.len() == 1 {
744 let bit = bits_base_powers[0].0;
745 let base_power = bits_base_powers[0].1;
746 let new_encoded =
747 self.add_constant(&mut cs.ns(|| "Add base power"), &base_power)?;
748 *self = Self::conditionally_select(
749 &mut cs.ns(|| "Conditional Select"),
750 &bit,
751 &new_encoded,
752 &self,
753 )?;
754 }
755 }
756
757 Ok(())
758 }
759
760 fn cost_of_add() -> usize {
761 4 + 2 * F::cost_of_mul()
762 }
763
764 fn cost_of_double() -> usize {
765 4 + F::cost_of_mul()
766 }
767 }
768
769 impl<P, ConstraintF, F> AllocGadget<TEProjective<P>, ConstraintF> for AffineGadget<P, ConstraintF, F>
770 where
771 P: TEModelParameters,
772 ConstraintF: Field,
773 F: FieldGadget<P::BaseField, ConstraintF>,
774 Self: GroupGadget<TEProjective<P>, ConstraintF>,
775 {
776 fn alloc<FN, T, CS: ConstraintSystem<ConstraintF>>(
777 mut cs: CS,
778 value_gen: FN,
779 ) -> Result<Self, SynthesisError>
780 where
781 FN: FnOnce() -> Result<T, SynthesisError>,
782 T: Borrow<TEProjective<P>>,
783 {
784 let (x, y) = match value_gen() {
785 Ok(ge) => {
786 let ge = ge.borrow().into_affine();
787 (Ok(ge.x), Ok(ge.y))
788 },
789 _ => (
790 Err(SynthesisError::AssignmentMissing),
791 Err(SynthesisError::AssignmentMissing),
792 ),
793 };
794
795 let d = P::COEFF_D;
796 let a = P::COEFF_A;
797
798 let x = F::alloc(&mut cs.ns(|| "x"), || x)?;
799 let y = F::alloc(&mut cs.ns(|| "y"), || y)?;
800
801 // Check that ax^2 + y^2 = 1 + dx^2y^2
802 // We do this by checking that ax^2 - 1 = y^2 * (dx^2 - 1)
803 let x2 = x.square(&mut cs.ns(|| "x^2"))?;
804 let y2 = y.square(&mut cs.ns(|| "y^2"))?;
805
806 let one = P::BaseField::one();
807 let d_x2_minus_one = x2
808 .mul_by_constant(cs.ns(|| "d * x^2"), &d)?
809 .add_constant(cs.ns(|| "d * x^2 - 1"), &one.neg())?;
810
811 let a_x2_minus_one = x2
812 .mul_by_constant(cs.ns(|| "a * x^2"), &a)?
813 .add_constant(cs.ns(|| "a * x^2 - 1"), &one.neg())?;
814
815 d_x2_minus_one.mul_equals(cs.ns(|| "on curve check"), &y2, &a_x2_minus_one)?;
816 Ok(Self::new(x, y))
817 }
818
819 fn alloc_checked<FN, T, CS: ConstraintSystem<ConstraintF>>(
820 mut cs: CS,
821 value_gen: FN,
822 ) -> Result<Self, SynthesisError>
823 where
824 FN: FnOnce() -> Result<T, SynthesisError>,
825 T: Borrow<TEProjective<P>>,
826 {
827 let cofactor_weight = BitIterator::new(P::COFACTOR).filter(|b| *b).count();
828 // If we multiply by r, we actually multiply by r - 2.
829 let r_minus_1 = (-P::ScalarField::one()).into_repr();
830 let r_weight = BitIterator::new(&r_minus_1).filter(|b| *b).count();
831
832 // We pick the most efficient method of performing the prime order check:
833 // If the cofactor has lower hamming weight than the scalar field's modulus,
834 // we first multiply by the inverse of the cofactor, and then, after allocating,
835 // multiply by the cofactor. This ensures the resulting point has no cofactors
836 //
837 // Else, we multiply by the scalar field's modulus and ensure that the result
838 // is zero.
839 if cofactor_weight < r_weight {
840 let ge = Self::alloc(cs.ns(|| "Alloc checked"), || {
841 value_gen().map(|ge| {
842 ge.borrow()
843 .into_affine()
844 .mul_by_cofactor_inv()
845 .into_projective()
846 })
847 })?;
848 let mut seen_one = false;
849 let mut result = Self::zero(cs.ns(|| "result"))?;
850 for (i, b) in BitIterator::new(P::COFACTOR).enumerate() {
851 let mut cs = cs.ns(|| format!("Iteration {}", i));
852
853 let old_seen_one = seen_one;
854 if seen_one {
855 result.double_in_place(cs.ns(|| "Double"))?;
856 } else {
857 seen_one = b;
858 }
859
860 if b {
861 result = if old_seen_one {
862 result.add(cs.ns(|| "Add"), &ge)?
863 } else {
864 ge.clone()
865 };
866 }
867 }
868 Ok(result)
869 } else {
870 let ge = Self::alloc(cs.ns(|| "Alloc checked"), value_gen)?;
871 let mut seen_one = false;
872 let mut result = Self::zero(cs.ns(|| "result"))?;
873 // Returns bits in big-endian order
874 for (i, b) in BitIterator::new(r_minus_1).enumerate() {
875 let mut cs = cs.ns(|| format!("Iteration {}", i));
876
877 let old_seen_one = seen_one;
878 if seen_one {
879 result.double_in_place(cs.ns(|| "Double"))?;
880 } else {
881 seen_one = b;
882 }
883
884 if b {
885 result = if old_seen_one {
886 result.add(cs.ns(|| "Add"), &ge)?
887 } else {
888 ge.clone()
889 };
890 }
891 }
892 let neg_ge = ge.negate(cs.ns(|| "Negate ge"))?;
893 neg_ge.enforce_equal(cs.ns(|| "Check equals"), &result)?;
894 Ok(ge)
895 }
896 }
897
898 fn alloc_input<FN, T, CS: ConstraintSystem<ConstraintF>>(
899 mut cs: CS,
900 value_gen: FN,
901 ) -> Result<Self, SynthesisError>
902 where
903 FN: FnOnce() -> Result<T, SynthesisError>,
904 T: Borrow<TEProjective<P>>,
905 {
906 let (x, y) = match value_gen() {
907 Ok(ge) => {
908 let ge = ge.borrow().into_affine();
909 (Ok(ge.x), Ok(ge.y))
910 },
911 _ => (
912 Err(SynthesisError::AssignmentMissing),
913 Err(SynthesisError::AssignmentMissing),
914 ),
915 };
916
917 let d = P::COEFF_D;
918 let a = P::COEFF_A;
919
920 let x = F::alloc_input(&mut cs.ns(|| "x"), || x)?;
921 let y = F::alloc_input(&mut cs.ns(|| "y"), || y)?;
922
923 // Check that ax^2 + y^2 = 1 + dx^2y^2
924 // We do this by checking that ax^2 - 1 = y^2 * (dx^2 - 1)
925 let x2 = x.square(&mut cs.ns(|| "x^2"))?;
926 let y2 = y.square(&mut cs.ns(|| "y^2"))?;
927
928 let one = P::BaseField::one();
929 let d_x2_minus_one = x2
930 .mul_by_constant(cs.ns(|| "d * x^2"), &d)?
931 .add_constant(cs.ns(|| "d * x^2 - 1"), &one.neg())?;
932
933 let a_x2_minus_one = x2
934 .mul_by_constant(cs.ns(|| "a * x^2"), &a)?
935 .add_constant(cs.ns(|| "a * x^2 - 1"), &one.neg())?;
936
937 d_x2_minus_one.mul_equals(cs.ns(|| "on curve check"), &y2, &a_x2_minus_one)?;
938 Ok(Self::new(x, y))
939 }
940 }
941}
942
943impl<P, ConstraintF, F> CondSelectGadget<ConstraintF> for AffineGadget<P, ConstraintF, F>
944where
945 P: TEModelParameters,
946 ConstraintF: Field,
947 F: FieldGadget<P::BaseField, ConstraintF>,
948{
949 #[inline]
950 fn conditionally_select<CS: ConstraintSystem<ConstraintF>>(
951 mut cs: CS,
952 cond: &Boolean,
953 first: &Self,
954 second: &Self,
955 ) -> Result<Self, SynthesisError> {
956 let x = F::conditionally_select(&mut cs.ns(|| "x"), cond, &first.x, &second.x)?;
957 let y = F::conditionally_select(&mut cs.ns(|| "y"), cond, &first.y, &second.y)?;
958
959 Ok(Self::new(x, y))
960 }
961
962 fn cost() -> usize {
963 2 * <F as CondSelectGadget<ConstraintF>>::cost()
964 }
965}
966
967impl<P, ConstraintF, F> EqGadget<ConstraintF> for AffineGadget<P, ConstraintF, F>
968where
969 P: TEModelParameters,
970 ConstraintF: Field,
971 F: FieldGadget<P::BaseField, ConstraintF>,
972{
973}
974
975impl<P, ConstraintF, F> ConditionalEqGadget<ConstraintF> for AffineGadget<P, ConstraintF, F>
976where
977 P: TEModelParameters,
978 ConstraintF: Field,
979 F: FieldGadget<P::BaseField, ConstraintF>,
980{
981 #[inline]
982 fn conditional_enforce_equal<CS: ConstraintSystem<ConstraintF>>(
983 &self,
984 mut cs: CS,
985 other: &Self,
986 condition: &Boolean,
987 ) -> Result<(), SynthesisError> {
988 self.x.conditional_enforce_equal(
989 &mut cs.ns(|| "X Coordinate Conditional Equality"),
990 &other.x,
991 condition,
992 )?;
993 self.y.conditional_enforce_equal(
994 &mut cs.ns(|| "Y Coordinate Conditional Equality"),
995 &other.y,
996 condition,
997 )?;
998 Ok(())
999 }
1000
1001 fn cost() -> usize {
1002 2 * <F as ConditionalEqGadget<ConstraintF>>::cost()
1003 }
1004}
1005
1006impl<P, ConstraintF, F> NEqGadget<ConstraintF> for AffineGadget<P, ConstraintF, F>
1007where
1008 P: TEModelParameters,
1009 ConstraintF: Field,
1010 F: FieldGadget<P::BaseField, ConstraintF>,
1011{
1012 #[inline]
1013 fn enforce_not_equal<CS: ConstraintSystem<ConstraintF>>(
1014 &self,
1015 mut cs: CS,
1016 other: &Self,
1017 ) -> Result<(), SynthesisError> {
1018 self.x
1019 .enforce_not_equal(&mut cs.ns(|| "X Coordinate Inequality"), &other.x)?;
1020 self.y
1021 .enforce_not_equal(&mut cs.ns(|| "Y Coordinate Inequality"), &other.y)?;
1022 Ok(())
1023 }
1024
1025 fn cost() -> usize {
1026 2 * <F as NEqGadget<ConstraintF>>::cost()
1027 }
1028}
1029
1030impl<P, ConstraintF, F> ToBitsGadget<ConstraintF> for AffineGadget<P, ConstraintF, F>
1031where
1032 P: TEModelParameters,
1033 ConstraintF: Field,
1034 F: FieldGadget<P::BaseField, ConstraintF>,
1035{
1036 fn to_bits<CS: ConstraintSystem<ConstraintF>>(&self, mut cs: CS) -> Result<Vec<Boolean>, SynthesisError> {
1037 let mut x_bits = self.x.to_bits(cs.ns(|| "X Coordinate To Bits"))?;
1038 let y_bits = self.y.to_bits(cs.ns(|| "Y Coordinate To Bits"))?;
1039 x_bits.extend_from_slice(&y_bits);
1040 Ok(x_bits)
1041 }
1042
1043 fn to_bits_strict<CS: ConstraintSystem<ConstraintF>>(
1044 &self,
1045 mut cs: CS,
1046 ) -> Result<Vec<Boolean>, SynthesisError> {
1047 let mut x_bits = self.x.to_bits_strict(cs.ns(|| "X Coordinate To Bits"))?;
1048 let y_bits = self.y.to_bits_strict(cs.ns(|| "Y Coordinate To Bits"))?;
1049 x_bits.extend_from_slice(&y_bits);
1050
1051 Ok(x_bits)
1052 }
1053}
1054
1055impl<P, ConstraintF, F> ToBytesGadget<ConstraintF> for AffineGadget<P, ConstraintF, F>
1056where
1057 P: TEModelParameters,
1058 ConstraintF: Field,
1059 F: FieldGadget<P::BaseField, ConstraintF>,
1060{
1061 fn to_bytes<CS: ConstraintSystem<ConstraintF>>(&self, mut cs: CS) -> Result<Vec<UInt8>, SynthesisError> {
1062 let mut x_bytes = self.x.to_bytes(cs.ns(|| "x"))?;
1063 let y_bytes = self.y.to_bytes(cs.ns(|| "y"))?;
1064 x_bytes.extend_from_slice(&y_bytes);
1065 Ok(x_bytes)
1066 }
1067
1068 fn to_bytes_strict<CS: ConstraintSystem<ConstraintF>>(
1069 &self,
1070 mut cs: CS,
1071 ) -> Result<Vec<UInt8>, SynthesisError> {
1072 let mut x_bytes = self.x.to_bytes_strict(cs.ns(|| "x"))?;
1073 let y_bytes = self.y.to_bytes_strict(cs.ns(|| "y"))?;
1074 x_bytes.extend_from_slice(&y_bytes);
1075
1076 Ok(x_bytes)
1077 }
1078}