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