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