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