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, GroupProjective as TEProjective},
4 AffineCurve, MontgomeryModelParameters, ProjectiveCurve, TEModelParameters,
5 },
6 BigInteger, BitIterator, Field, One, PrimeField, Zero,
7};
8
9use r1cs_core::{ConstraintSystemRef, Namespace, SynthesisError};
10
11use crate::{prelude::*, Vec};
12
13use core::{borrow::Borrow, marker::PhantomData};
14
15#[derive(Derivative)]
16#[derivative(Debug, Clone)]
17#[must_use]
18pub struct MontgomeryAffineVar<
19 P: TEModelParameters,
20 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
21> where
22 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
23{
24 pub x: F,
25 pub y: F,
26 #[derivative(Debug = "ignore")]
27 _params: PhantomData<P>,
28}
29
30mod montgomery_affine_impl {
31 use super::*;
32 use algebra::{twisted_edwards_extended::GroupAffine, Field};
33 use core::ops::Add;
34
35 impl<P, F> R1CSVar<<P::BaseField as Field>::BasePrimeField> for MontgomeryAffineVar<P, F>
36 where
37 P: TEModelParameters,
38 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
39 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
40 {
41 type Value = (P::BaseField, P::BaseField);
42
43 fn cs(&self) -> Option<ConstraintSystemRef<<P::BaseField as Field>::BasePrimeField>> {
44 self.x.cs().or(self.y.cs())
45 }
46
47 fn value(&self) -> Result<Self::Value, SynthesisError> {
48 let x = self.x.value()?;
49 let y = self.y.value()?;
50 Ok((x, y))
51 }
52 }
53
54 impl<
55 P: TEModelParameters,
56 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
57 > MontgomeryAffineVar<P, F>
58 where
59 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
60 {
61 pub fn new(x: F, y: F) -> Self {
62 Self {
63 x,
64 y,
65 _params: PhantomData,
66 }
67 }
68
69 pub fn from_edwards_to_coords(
70 p: &TEAffine<P>,
71 ) -> Result<(P::BaseField, P::BaseField), SynthesisError> {
72 let montgomery_point: GroupAffine<P> = if p.y == P::BaseField::one() {
73 GroupAffine::zero()
74 } else if p.x == P::BaseField::zero() {
75 GroupAffine::new(P::BaseField::zero(), P::BaseField::zero())
76 } else {
77 let u =
78 (P::BaseField::one() + &p.y) * &(P::BaseField::one() - &p.y).inverse().unwrap();
79 let v = u * &p.x.inverse().unwrap();
80 GroupAffine::new(u, v)
81 };
82
83 Ok((montgomery_point.x, montgomery_point.y))
84 }
85
86 pub fn new_witness_from_edwards(
87 cs: ConstraintSystemRef<<P::BaseField as Field>::BasePrimeField>,
88 p: &TEAffine<P>,
89 ) -> Result<Self, SynthesisError> {
90 let montgomery_coords = Self::from_edwards_to_coords(p)?;
91 let u = F::new_witness(cs.ns("u"), || Ok(montgomery_coords.0))?;
92 let v = F::new_witness(cs.ns("v"), || Ok(montgomery_coords.1))?;
93 Ok(Self::new(u, v))
94 }
95
96 pub fn into_edwards(&self) -> Result<AffineVar<P, F>, SynthesisError> {
97 let cs = self.cs().unwrap_or(ConstraintSystemRef::None);
98 // Compute u = x / y
99 let u = F::new_witness(cs.ns("u"), || {
100 let y_inv = self
101 .y
102 .value()?
103 .inverse()
104 .ok_or(SynthesisError::DivisionByZero)?;
105 Ok(self.x.value()? * &y_inv)
106 })?;
107
108 u.mul_equals(&self.y, &self.x)?;
109
110 let v = F::new_witness(cs.ns("v"), || {
111 let mut t0 = self.x.value()?;
112 let mut t1 = t0;
113 t0 -= &P::BaseField::one();
114 t1 += &P::BaseField::one();
115
116 Ok(t0 * &t1.inverse().ok_or(SynthesisError::DivisionByZero)?)
117 })?;
118
119 let xplusone = &self.x + P::BaseField::one();
120 let xminusone = &self.x - P::BaseField::one();
121 v.mul_equals(&xplusone, &xminusone)?;
122
123 Ok(AffineVar::new(u, v))
124 }
125 }
126
127 impl<'a, P, F> Add<&'a MontgomeryAffineVar<P, F>> for MontgomeryAffineVar<P, F>
128 where
129 P: TEModelParameters,
130 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
131 for<'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
132 {
133 type Output = MontgomeryAffineVar<P, F>;
134 fn add(self, other: &'a Self) -> Self::Output {
135 let cs = [&self, other].cs();
136 let mode = if cs.is_none() || matches!(cs, Some(ConstraintSystemRef::None)) {
137 AllocationMode::Constant
138 } else {
139 AllocationMode::Witness
140 };
141 let cs = cs.unwrap_or(ConstraintSystemRef::None);
142
143 let coeff_b = P::MontgomeryModelParameters::COEFF_B;
144 let coeff_a = P::MontgomeryModelParameters::COEFF_A;
145
146 let lambda = F::new_variable(
147 cs.ns("lambda"),
148 || {
149 let n = other.y.value()? - &self.y.value()?;
150 let d = other.x.value()? - &self.x.value()?;
151 Ok(n * &d.inverse().ok_or(SynthesisError::DivisionByZero)?)
152 },
153 mode,
154 )
155 .unwrap();
156 let lambda_n = &other.y - &self.y;
157 let lambda_d = &other.x - &self.x;
158 lambda_d.mul_equals(&lambda, &lambda_n).unwrap();
159
160 // Compute x'' = B*lambda^2 - A - x - x'
161 let xprime = F::new_variable(
162 cs.ns("xprime"),
163 || {
164 Ok(lambda.value()?.square() * &coeff_b
165 - &coeff_a
166 - &self.x.value()?
167 - &other.x.value()?)
168 },
169 mode,
170 )
171 .unwrap();
172
173 let xprime_lc = &self.x + &other.x + &xprime + coeff_a;
174 // (lambda) * (lambda) = (A + x + x' + x'')
175 let lambda_b = &lambda * coeff_b;
176 lambda_b.mul_equals(&lambda, &xprime_lc).unwrap();
177
178 let yprime = F::new_variable(
179 cs.ns("yprime"),
180 || {
181 Ok(-(self.y.value()?
182 + &(lambda.value()? * &(xprime.value()? - &self.x.value()?))))
183 },
184 mode,
185 )
186 .unwrap();
187
188 let xres = &self.x - &xprime;
189 let yres = &self.y + &yprime;
190 lambda.mul_equals(&xres, &yres).unwrap();
191 MontgomeryAffineVar::new(xprime, yprime)
192 }
193 }
194}
195
196#[derive(Derivative)]
197#[derivative(Debug, Clone)]
198#[must_use]
199pub struct AffineVar<
200 P: TEModelParameters,
201 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
202> where
203 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
204{
205 pub x: F,
206 pub y: F,
207 #[derivative(Debug = "ignore")]
208 _params: PhantomData<P>,
209}
210
211impl<P: TEModelParameters, F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>>
212 AffineVar<P, F>
213where
214 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
215{
216 pub fn new(x: F, y: F) -> Self {
217 Self {
218 x,
219 y,
220 _params: PhantomData,
221 }
222 }
223
224 /// Allocates a new variable without performing an on-curve check, which is
225 /// useful if the variable is known to be on the curve (eg., if the point
226 /// is a constant or is a public input).
227 pub fn new_variable_omit_on_curve_check<T: Into<TEAffine<P>>>(
228 cs: impl Into<Namespace<<P::BaseField as Field>::BasePrimeField>>,
229 f: impl FnOnce() -> Result<T, SynthesisError>,
230 mode: AllocationMode,
231 ) -> Result<Self, SynthesisError> {
232 let ns = cs.into();
233 let cs = ns.cs();
234
235 let (x, y) = match f() {
236 Ok(ge) => {
237 let ge: TEAffine<P> = ge.into();
238 (Ok(ge.x), Ok(ge.y))
239 }
240 _ => (
241 Err(SynthesisError::AssignmentMissing),
242 Err(SynthesisError::AssignmentMissing),
243 ),
244 };
245
246 let x = F::new_variable(cs.ns("x"), || x, mode)?;
247 let y = F::new_variable(cs.ns("y"), || y, mode)?;
248
249 Ok(Self::new(x, y))
250 }
251}
252
253impl<P, F> R1CSVar<<P::BaseField as Field>::BasePrimeField> for AffineVar<P, F>
254where
255 P: TEModelParameters,
256 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
257 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
258{
259 type Value = TEProjective<P>;
260
261 fn cs(&self) -> Option<ConstraintSystemRef<<P::BaseField as Field>::BasePrimeField>> {
262 self.x.cs().or(self.y.cs())
263 }
264
265 #[inline]
266 fn value(&self) -> Result<TEProjective<P>, SynthesisError> {
267 let (x, y) = (self.x.value()?, self.y.value()?);
268 let result = TEAffine::new(x, y);
269 Ok(result.into())
270 }
271}
272
273impl<P, F> CurveVar<TEProjective<P>, <P::BaseField as Field>::BasePrimeField> for AffineVar<P, F>
274where
275 P: TEModelParameters,
276 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>
277 + TwoBitLookupGadget<<P::BaseField as Field>::BasePrimeField, TableConstant = P::BaseField>
278 + ThreeBitCondNegLookupGadget<
279 <P::BaseField as Field>::BasePrimeField,
280 TableConstant = P::BaseField,
281 >,
282 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
283{
284 fn constant(g: TEProjective<P>) -> Self {
285 let cs = ConstraintSystemRef::None;
286 Self::new_variable_omit_on_curve_check(cs, || Ok(g), AllocationMode::Constant).unwrap()
287 }
288
289 fn zero() -> Self {
290 Self::new(F::zero(), F::one())
291 }
292
293 fn is_zero(&self) -> Result<Boolean<<P::BaseField as Field>::BasePrimeField>, SynthesisError> {
294 self.x.is_zero()?.and(&self.x.is_one()?)
295 }
296
297 fn new_variable_omit_prime_order_check(
298 cs: impl Into<Namespace<<P::BaseField as Field>::BasePrimeField>>,
299 f: impl FnOnce() -> Result<TEProjective<P>, SynthesisError>,
300 mode: AllocationMode,
301 ) -> Result<Self, SynthesisError> {
302 let ns = cs.into();
303 let cs = ns.cs();
304
305 let g = Self::new_variable_omit_on_curve_check(cs, f, mode)?;
306
307 if mode != AllocationMode::Constant {
308 let d = P::COEFF_D;
309 let a = P::COEFF_A;
310 // Check that ax^2 + y^2 = 1 + dx^2y^2
311 // We do this by checking that ax^2 - 1 = y^2 * (dx^2 - 1)
312 let x2 = g.x.square()?;
313 let y2 = g.y.square()?;
314
315 let one = P::BaseField::one();
316 let d_x2_minus_one = &x2 * d - one;
317 let a_x2_minus_one = &x2 * a - one;
318
319 d_x2_minus_one.mul_equals(&y2, &a_x2_minus_one)?;
320 }
321 Ok(g)
322 }
323
324 /// Enforce that `self` is in the prime-order subgroup.
325 ///
326 /// Does so by multiplying by the prime order, and checking that the result
327 /// is unchanged.
328 fn enforce_prime_order(&self) -> Result<(), SynthesisError> {
329 let r_minus_1 = (-P::ScalarField::one()).into_repr();
330
331 let mut seen_one = false;
332 let mut result = Self::zero();
333 for b in BitIterator::new(r_minus_1) {
334 let old_seen_one = seen_one;
335 if seen_one {
336 result.double_in_place()?;
337 } else {
338 seen_one = b;
339 }
340
341 if b {
342 result = if old_seen_one {
343 result + self
344 } else {
345 self.clone()
346 };
347 }
348 }
349 self.negate()?.enforce_equal(&result)?;
350 Ok(())
351 }
352
353 #[inline]
354 fn double_in_place(&mut self) -> Result<(), SynthesisError> {
355 if let Some(cs) = self.cs() {
356 let a = P::COEFF_A;
357
358 // xy
359 let xy = &self.x * &self.y;
360 let x2 = self.x.square()?;
361 let y2 = self.y.square()?;
362
363 let a_x2 = &x2 * a;
364
365 // Compute x3 = (2xy) / (ax^2 + y^2)
366 let x3 = F::new_witness(cs.ns("x3"), || {
367 let t0 = xy.value()?.double();
368 let t1 = a * &x2.value()? + &y2.value()?;
369 Ok(t0 * &t1.inverse().ok_or(SynthesisError::DivisionByZero)?)
370 })?;
371
372 let a_x2_plus_y2 = &a_x2 + &y2;
373 let two_xy = xy.double()?;
374 x3.mul_equals(&a_x2_plus_y2, &two_xy)?;
375
376 // Compute y3 = (y^2 - ax^2) / (2 - ax^2 - y^2)
377 let two = P::BaseField::one().double();
378 let y3 = F::new_witness(cs.ns("y3"), || {
379 let a_x2 = a * &x2.value()?;
380 let t0 = y2.value()? - &a_x2;
381 let t1 = two - &a_x2 - &y2.value()?;
382 Ok(t0 * &t1.inverse().ok_or(SynthesisError::DivisionByZero)?)
383 })?;
384 let y2_minus_a_x2 = &y2 - &a_x2;
385 let two_minus_ax2_minus_y2 = (&a_x2 + &y2).negate()? + two;
386
387 y3.mul_equals(&two_minus_ax2_minus_y2, &y2_minus_a_x2)?;
388 self.x = x3;
389 self.y = y3;
390 } else {
391 let value = self.value()?;
392 *self = Self::constant(value.double());
393 }
394 Ok(())
395 }
396
397 fn negate(&self) -> Result<Self, SynthesisError> {
398 Ok(Self::new(self.x.negate()?, self.y.clone()))
399 }
400
401 fn precomputed_base_scalar_mul<'a, I, B>(
402 &mut self,
403 scalar_bits_with_base_powers: I,
404 ) -> Result<(), SynthesisError>
405 where
406 I: Iterator<Item = (B, &'a TEProjective<P>)>,
407 B: Borrow<Boolean<<P::BaseField as Field>::BasePrimeField>>,
408 {
409 let scalar_bits_with_base_powers = scalar_bits_with_base_powers
410 .map(|(bit, base)| (bit.borrow().clone(), (*base).into()))
411 .collect::<Vec<(_, TEProjective<P>)>>();
412 let zero = TEProjective::zero();
413 for bits_base_powers in scalar_bits_with_base_powers.chunks(2) {
414 if bits_base_powers.len() == 2 {
415 let bits = [bits_base_powers[0].0.clone(), bits_base_powers[1].0.clone()];
416 let base_powers = [&bits_base_powers[0].1, &bits_base_powers[1].1];
417
418 let mut table = [
419 zero,
420 *base_powers[0],
421 *base_powers[1],
422 *base_powers[0] + base_powers[1],
423 ];
424
425 TEProjective::batch_normalization(&mut table);
426 let x_s = [table[0].x, table[1].x, table[2].x, table[3].x];
427 let y_s = [table[0].y, table[1].y, table[2].y, table[3].y];
428
429 let x = F::two_bit_lookup(&bits, &x_s)?;
430 let y = F::two_bit_lookup(&bits, &y_s)?;
431 *self += Self::new(x, y);
432 } else if bits_base_powers.len() == 1 {
433 let bit = bits_base_powers[0].0.clone();
434 let base_power = bits_base_powers[0].1;
435 let new_encoded = &*self + base_power;
436 *self = bit.select(&new_encoded, &self)?;
437 }
438 }
439
440 Ok(())
441 }
442
443 fn precomputed_base_3_bit_signed_digit_scalar_mul<'a, I, J, B>(
444 bases: &[B],
445 scalars: &[J],
446 ) -> Result<Self, SynthesisError>
447 where
448 I: Borrow<[Boolean<<P::BaseField as Field>::BasePrimeField>]>,
449 J: Borrow<[I]>,
450 B: Borrow<[TEProjective<P>]>,
451 {
452 const CHUNK_SIZE: usize = 3;
453 let mut ed_result: Option<AffineVar<P, F>> = None;
454 let mut result: Option<MontgomeryAffineVar<P, F>> = None;
455
456 let mut process_segment_result = |result: &MontgomeryAffineVar<P, F>| {
457 let sgmt_result = result.into_edwards()?;
458 ed_result = match ed_result.as_ref() {
459 None => Some(sgmt_result),
460 Some(r) => Some(sgmt_result + r),
461 };
462 Ok::<(), SynthesisError>(())
463 };
464
465 // Compute ∏(h_i^{m_i}) for all i.
466 for (segment_bits_chunks, segment_powers) in scalars.iter().zip(bases) {
467 for (bits, base_power) in segment_bits_chunks
468 .borrow()
469 .iter()
470 .zip(segment_powers.borrow())
471 {
472 let base_power = base_power.borrow();
473 let mut acc_power = *base_power;
474 let mut coords = vec![];
475 for _ in 0..4 {
476 coords.push(acc_power);
477 acc_power += base_power;
478 }
479
480 let bits = bits.borrow().to_bits()?;
481 if bits.len() != CHUNK_SIZE {
482 return Err(SynthesisError::Unsatisfiable);
483 }
484
485 let coords = coords
486 .iter()
487 .map(|p| MontgomeryAffineVar::from_edwards_to_coords(&p.into_affine()))
488 .collect::<Result<Vec<_>, _>>()?;
489
490 let x_coeffs = coords.iter().map(|p| p.0).collect::<Vec<_>>();
491 let y_coeffs = coords.iter().map(|p| p.1).collect::<Vec<_>>();
492
493 let precomp = bits[0].and(&bits[1])?;
494
495 let x = F::zero()
496 + x_coeffs[0]
497 + F::from(bits[0].clone()) * (x_coeffs[1] - &x_coeffs[0])
498 + F::from(bits[1].clone()) * (x_coeffs[2] - &x_coeffs[0])
499 + F::from(precomp.clone())
500 * (x_coeffs[3] - &x_coeffs[2] - &x_coeffs[1] + &x_coeffs[0]);
501
502 let y = F::three_bit_cond_neg_lookup(&bits, &precomp, &y_coeffs)?;
503
504 let tmp = MontgomeryAffineVar::new(x, y);
505 result = match result.as_ref() {
506 None => Some(tmp),
507 Some(r) => Some(tmp + r),
508 };
509 }
510
511 process_segment_result(&result.unwrap())?;
512 result = None;
513 }
514 if result.is_some() {
515 process_segment_result(&result.unwrap())?;
516 }
517 Ok(ed_result.unwrap())
518 }
519}
520
521impl<P, F> AllocVar<TEProjective<P>, <P::BaseField as Field>::BasePrimeField> for AffineVar<P, F>
522where
523 P: TEModelParameters,
524 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>
525 + TwoBitLookupGadget<<P::BaseField as Field>::BasePrimeField, TableConstant = P::BaseField>
526 + ThreeBitCondNegLookupGadget<
527 <P::BaseField as Field>::BasePrimeField,
528 TableConstant = P::BaseField,
529 >,
530 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
531{
532 fn new_variable<Point: Borrow<TEProjective<P>>>(
533 cs: impl Into<Namespace<<P::BaseField as Field>::BasePrimeField>>,
534 f: impl FnOnce() -> Result<Point, SynthesisError>,
535 mode: AllocationMode,
536 ) -> Result<Self, SynthesisError> {
537 let ns = cs.into();
538 let cs = ns.cs();
539 let f = || Ok(*f()?.borrow());
540 match mode {
541 AllocationMode::Constant => Self::new_variable_omit_prime_order_check(cs, f, mode),
542 AllocationMode::Input => Self::new_variable_omit_prime_order_check(cs, f, mode),
543 AllocationMode::Witness => {
544 // if cofactor.is_even():
545 // divide until you've removed all even factors
546 // else:
547 // just directly use double and add.
548 let mut power_of_2: u32 = 0;
549 let mut cofactor = P::COFACTOR.to_vec();
550 while cofactor[0] % 2 == 0 {
551 div2(&mut cofactor);
552 power_of_2 += 1;
553 }
554
555 let cofactor_weight = BitIterator::new(cofactor.as_slice()).filter(|b| *b).count();
556 let modulus_minus_1 = (-P::ScalarField::one()).into_repr(); // r - 1
557 let modulus_minus_1_weight =
558 BitIterator::new(modulus_minus_1).filter(|b| *b).count();
559
560 // We pick the most efficient method of performing the prime order check:
561 // If the cofactor has lower hamming weight than the scalar field's modulus,
562 // we first multiply by the inverse of the cofactor, and then, after allocating,
563 // multiply by the cofactor. This ensures the resulting point has no cofactors
564 //
565 // Else, we multiply by the scalar field's modulus and ensure that the result
566 // equals the identity.
567
568 let (mut ge, iter) = if cofactor_weight < modulus_minus_1_weight {
569 let ge = Self::new_variable_omit_prime_order_check(
570 cs.ns("Witness without subgroup check with cofactor mul"),
571 || f().map(|g| g.borrow().into_affine().mul_by_cofactor_inv().into()),
572 mode,
573 )?;
574 (ge, BitIterator::new(cofactor.as_slice()))
575 } else {
576 let ge = Self::new_variable_omit_prime_order_check(
577 cs.ns("Witness without subgroup check with `r` check"),
578 || {
579 f().map(|g| {
580 let g = g.into_affine();
581 let mut power_of_two = P::ScalarField::one().into_repr();
582 power_of_two.muln(power_of_2);
583 let power_of_two_inv =
584 P::ScalarField::from(power_of_two).inverse().unwrap();
585 g.mul(power_of_two_inv)
586 })
587 },
588 mode,
589 )?;
590
591 (ge, BitIterator::new(modulus_minus_1.as_ref()))
592 };
593 // Remove the even part of the cofactor
594 for _ in 0..power_of_2 {
595 ge.double_in_place()?;
596 }
597
598 let mut seen_one = false;
599 let mut result = Self::zero();
600 for b in iter {
601 let old_seen_one = seen_one;
602 if seen_one {
603 result.double_in_place()?;
604 } else {
605 seen_one = b;
606 }
607
608 if b {
609 result = if old_seen_one {
610 result + &ge
611 } else {
612 ge.clone()
613 };
614 }
615 }
616 if cofactor_weight < modulus_minus_1_weight {
617 Ok(result)
618 } else {
619 ge.enforce_equal(&ge)?;
620 Ok(ge)
621 }
622 }
623 }
624 }
625}
626
627impl<P, F> AllocVar<TEAffine<P>, <P::BaseField as Field>::BasePrimeField> for AffineVar<P, F>
628where
629 P: TEModelParameters,
630 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>
631 + TwoBitLookupGadget<<P::BaseField as Field>::BasePrimeField, TableConstant = P::BaseField>
632 + ThreeBitCondNegLookupGadget<
633 <P::BaseField as Field>::BasePrimeField,
634 TableConstant = P::BaseField,
635 >,
636 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
637{
638 fn new_variable<Point: Borrow<TEAffine<P>>>(
639 cs: impl Into<Namespace<<P::BaseField as Field>::BasePrimeField>>,
640 f: impl FnOnce() -> Result<Point, SynthesisError>,
641 mode: AllocationMode,
642 ) -> Result<Self, SynthesisError> {
643 Self::new_variable(cs, || f().map(|b| b.borrow().into_projective()), mode)
644 }
645}
646
647#[inline]
648fn div2(limbs: &mut [u64]) {
649 let mut t = 0;
650 for i in limbs.iter_mut().rev() {
651 let t2 = *i << 63;
652 *i >>= 1;
653 *i |= t;
654 t = t2;
655 }
656}
657
658impl_bounded_ops!(
659 AffineVar<P, F>,
660 TEProjective<P>,
661 Add,
662 add,
663 AddAssign,
664 add_assign,
665 |this: &'a AffineVar<P, F>, other: &'a AffineVar<P, F>| {
666 if let Some(cs) = [this, other].cs() {
667 let a = P::COEFF_A;
668 let d = P::COEFF_D;
669
670 // Compute U = (x1 + y1) * (x2 + y2)
671 let u1 = (&this.x * -a) + &this.y;
672 let u2 = &other.x + &other.y;
673
674 let u = u1 * &u2;
675
676 // Compute v0 = x1 * y2
677 let v0 = &other.y * &this.x;
678
679 // Compute v1 = x2 * y1
680 let v1 = &other.x * &this.y;
681
682 // Compute C = d*v0*v1
683 let v2 = &v0 * &v1 * d;
684
685 // Compute x3 = (v0 + v1) / (1 + v2)
686 let x3 = F::new_witness(cs.ns("x3"), || {
687 let t0 = v0.value()? + &v1.value()?;
688 let t1 = P::BaseField::one() + &v2.value()?;
689 Ok(t0 * &t1.inverse().ok_or(SynthesisError::DivisionByZero)?)
690 }).unwrap();
691
692 let v2_plus_one = &v2 + P::BaseField::one();
693 let v0_plus_v1 = &v0 + &v1;
694 x3.mul_equals(&v2_plus_one, &v0_plus_v1).unwrap();
695
696 // Compute y3 = (U + a * v0 - v1) / (1 - v2)
697 let y3 = F::new_witness(cs.ns("y3"), || {
698 let t0 = u.value()? + &(a * &v0.value()?) - &v1.value()?;
699 let t1 = P::BaseField::one() - &v2.value()?;
700 Ok(t0 * &t1.inverse().ok_or(SynthesisError::DivisionByZero)?)
701 }).unwrap();
702
703 let one_minus_v2 = (&v2 - P::BaseField::one()).negate().unwrap();
704 let a_v0 = &v0 * a;
705 let u_plus_a_v0_minus_v1 = &u + &a_v0 - &v1;
706
707 y3.mul_equals(&one_minus_v2, &u_plus_a_v0_minus_v1).unwrap();
708
709 AffineVar::new(x3, y3)
710 } else {
711 assert!(this.is_constant() && other.is_constant());
712 AffineVar::constant(this.value().unwrap() + &other.value().unwrap())
713 }
714 },
715 |this: &'a AffineVar<P, F>, other: TEProjective<P>| this + AffineVar::constant(other),
716 (
717 F :FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>
718 + TwoBitLookupGadget<<P::BaseField as Field>::BasePrimeField, TableConstant = P::BaseField>
719 + ThreeBitCondNegLookupGadget<<P::BaseField as Field>::BasePrimeField, TableConstant = P::BaseField>,
720 P: TEModelParameters,
721 ),
722 for <'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
723);
724
725impl_bounded_ops!(
726 AffineVar<P, F>,
727 TEProjective<P>,
728 Sub,
729 sub,
730 SubAssign,
731 sub_assign,
732 |this: &'a AffineVar<P, F>, other: &'a AffineVar<P, F>| this + other.negate().unwrap(),
733 |this: &'a AffineVar<P, F>, other: TEProjective<P>| this - AffineVar::constant(other),
734 (
735 F :FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>
736 + TwoBitLookupGadget<<P::BaseField as Field>::BasePrimeField, TableConstant = P::BaseField>
737 + ThreeBitCondNegLookupGadget<<P::BaseField as Field>::BasePrimeField, TableConstant = P::BaseField>,
738 P: TEModelParameters,
739 ),
740 for <'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>
741);
742
743impl<'a, P, F> GroupOpsBounds<'a, TEProjective<P>, AffineVar<P, F>> for AffineVar<P, F>
744where
745 P: TEModelParameters,
746 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>
747 + TwoBitLookupGadget<<P::BaseField as Field>::BasePrimeField, TableConstant = P::BaseField>
748 + ThreeBitCondNegLookupGadget<
749 <P::BaseField as Field>::BasePrimeField,
750 TableConstant = P::BaseField,
751 >,
752 for<'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
753{
754}
755
756impl<'a, P, F> GroupOpsBounds<'a, TEProjective<P>, AffineVar<P, F>> for &'a AffineVar<P, F>
757where
758 P: TEModelParameters,
759 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>
760 + TwoBitLookupGadget<<P::BaseField as Field>::BasePrimeField, TableConstant = P::BaseField>
761 + ThreeBitCondNegLookupGadget<
762 <P::BaseField as Field>::BasePrimeField,
763 TableConstant = P::BaseField,
764 >,
765 for<'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
766{
767}
768
769impl<P, F> CondSelectGadget<<P::BaseField as Field>::BasePrimeField> for AffineVar<P, F>
770where
771 P: TEModelParameters,
772 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
773 for<'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
774{
775 #[inline]
776 fn conditionally_select(
777 cond: &Boolean<<P::BaseField as Field>::BasePrimeField>,
778 true_value: &Self,
779 false_value: &Self,
780 ) -> Result<Self, SynthesisError> {
781 let x = cond.select(&true_value.x, &false_value.x)?;
782 let y = cond.select(&true_value.y, &false_value.y)?;
783
784 Ok(Self::new(x, y))
785 }
786}
787
788impl<P, F> EqGadget<<P::BaseField as Field>::BasePrimeField> for AffineVar<P, F>
789where
790 P: TEModelParameters,
791 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
792 for<'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
793{
794 fn is_eq(
795 &self,
796 other: &Self,
797 ) -> Result<Boolean<<P::BaseField as Field>::BasePrimeField>, SynthesisError> {
798 let x_equal = self.x.is_eq(&other.x)?;
799 let y_equal = self.y.is_eq(&other.y)?;
800 x_equal.and(&y_equal)
801 }
802
803 #[inline]
804 fn conditional_enforce_equal(
805 &self,
806 other: &Self,
807 condition: &Boolean<<P::BaseField as Field>::BasePrimeField>,
808 ) -> Result<(), SynthesisError> {
809 self.x.conditional_enforce_equal(&other.x, condition)?;
810 self.y.conditional_enforce_equal(&other.y, condition)?;
811 Ok(())
812 }
813
814 #[inline]
815 fn conditional_enforce_not_equal(
816 &self,
817 other: &Self,
818 condition: &Boolean<<P::BaseField as Field>::BasePrimeField>,
819 ) -> Result<(), SynthesisError> {
820 self.is_eq(other)?
821 .and(condition)?
822 .enforce_equal(&Boolean::Constant(false))
823 }
824}
825
826impl<P, F> ToBitsGadget<<P::BaseField as Field>::BasePrimeField> for AffineVar<P, F>
827where
828 P: TEModelParameters,
829 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
830 for<'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
831{
832 fn to_bits(
833 &self,
834 ) -> Result<Vec<Boolean<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
835 let mut x_bits = self.x.to_bits()?;
836 let y_bits = self.y.to_bits()?;
837 x_bits.extend_from_slice(&y_bits);
838 Ok(x_bits)
839 }
840
841 fn to_non_unique_bits(
842 &self,
843 ) -> Result<Vec<Boolean<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
844 let mut x_bits = self.x.to_non_unique_bits()?;
845 let y_bits = self.y.to_non_unique_bits()?;
846 x_bits.extend_from_slice(&y_bits);
847
848 Ok(x_bits)
849 }
850}
851
852impl<P, F> ToBytesGadget<<P::BaseField as Field>::BasePrimeField> for AffineVar<P, F>
853where
854 P: TEModelParameters,
855 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
856 for<'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
857{
858 fn to_bytes(
859 &self,
860 ) -> Result<Vec<UInt8<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
861 let mut x_bytes = self.x.to_bytes()?;
862 let y_bytes = self.y.to_bytes()?;
863 x_bytes.extend_from_slice(&y_bytes);
864 Ok(x_bytes)
865 }
866
867 fn to_non_unique_bytes(
868 &self,
869 ) -> Result<Vec<UInt8<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
870 let mut x_bytes = self.x.to_non_unique_bytes()?;
871 let y_bytes = self.y.to_non_unique_bytes()?;
872 x_bytes.extend_from_slice(&y_bytes);
873
874 Ok(x_bytes)
875 }
876}
877
878#[cfg(test)]
879#[allow(dead_code)]
880pub(crate) fn test<P, GG>() -> Result<(), SynthesisError>
881where
882 P: TEModelParameters,
883 GG: CurveVar<TEProjective<P>, <P::BaseField as Field>::BasePrimeField>,
884 for<'a> &'a GG: GroupOpsBounds<'a, TEProjective<P>, GG>,
885{
886 use crate::prelude::*;
887 use algebra::{test_rng, Group, UniformRand};
888 use r1cs_core::ConstraintSystem;
889
890 crate::groups::test::group_test::<TEProjective<P>, _, GG>()?;
891
892 let mut rng = test_rng();
893
894 let cs = ConstraintSystem::<<P::BaseField as Field>::BasePrimeField>::new_ref();
895
896 let a = TEProjective::<P>::rand(&mut rng);
897 let b = TEProjective::<P>::rand(&mut rng);
898 let a_affine = a.into_affine();
899 let b_affine = b.into_affine();
900
901 println!("Allocating things");
902 let ns = cs.ns("allocating variables");
903 println!("{:?}", cs.current_namespace());
904 let mut gadget_a = GG::new_witness(cs.ns("a"), || Ok(a))?;
905 let gadget_b = GG::new_witness(cs.ns("b"), || Ok(b))?;
906 println!("{:?}", cs.current_namespace());
907 ns.leave_namespace();
908 println!("Done Allocating things");
909 assert_eq!(gadget_a.value()?.into_affine().x, a_affine.x);
910 assert_eq!(gadget_a.value()?.into_affine().y, a_affine.y);
911 assert_eq!(gadget_b.value()?.into_affine().x, b_affine.x);
912 assert_eq!(gadget_b.value()?.into_affine().y, b_affine.y);
913 assert_eq!(cs.which_is_unsatisfied(), None);
914
915 println!("Checking addition");
916 // Check addition
917 let ab = a + &b;
918 let ab_affine = ab.into_affine();
919 let gadget_ab = &gadget_a + &gadget_b;
920 let gadget_ba = &gadget_b + &gadget_a;
921 gadget_ba.enforce_equal(&gadget_ab)?;
922
923 let ab_val = gadget_ab.value()?.into_affine();
924 assert_eq!(ab_val, ab_affine, "Result of addition is unequal");
925 assert!(cs.is_satisfied().unwrap());
926 println!("Done checking addition");
927
928 println!("Checking doubling");
929 // Check doubling
930 let aa = Group::double(&a);
931 let aa_affine = aa.into_affine();
932 gadget_a.double_in_place()?;
933 let aa_val = gadget_a.value()?.into_affine();
934 assert_eq!(
935 aa_val, aa_affine,
936 "Gadget and native values are unequal after double."
937 );
938 assert!(cs.is_satisfied().unwrap());
939 println!("Done checking doubling");
940
941 println!("Checking mul_bits");
942 // Check mul_bits
943 let scalar = P::ScalarField::rand(&mut rng);
944 let native_result = AffineCurve::mul(&aa.into_affine(), scalar);
945 let native_result = native_result.into_affine();
946
947 let mut scalar: Vec<bool> = BitIterator::new(scalar.into_repr()).collect();
948 // Get the scalar bits into little-endian form.
949 scalar.reverse();
950 let input: Vec<Boolean<_>> = Vec::new_witness(cs.ns("bits"), || Ok(scalar)).unwrap();
951 let result = gadget_a.mul_bits(input.iter())?;
952 let result_val = result.value()?.into_affine();
953 assert_eq!(
954 result_val, native_result,
955 "gadget & native values are diff. after scalar mul"
956 );
957 assert!(cs.is_satisfied().unwrap());
958 println!("Done checking mul_bits");
959
960 if !cs.is_satisfied().unwrap() {
961 println!("Not satisfied");
962 println!("{:?}", cs.which_is_unsatisfied().unwrap());
963 }
964
965 assert!(cs.is_satisfied().unwrap());
966 Ok(())
967}