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