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