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