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