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