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