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