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