1use super::*;
  2use ark_ff::AdditiveGroup;
  3use ark_std::ops::Add;
  4
  5/// An affine representation of a prime order curve point that is guaranteed
  6/// to *not* be the point at infinity.
  7#[derive(Derivative)]
  8#[derivative(Debug, Clone)]
  9#[must_use]
 10pub struct NonZeroAffineVar<
 11    P: SWCurveConfig,
 12    F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
 13> where
 14    for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
 15{
 16    /// The x-coordinate.
 17    pub x: F,
 18    /// The y-coordinate.
 19    pub y: F,
 20    #[derivative(Debug = "ignore")]
 21    _params: PhantomData<P>,
 22}
 23
 24impl<P, F> NonZeroAffineVar<P, F>
 25where
 26    P: SWCurveConfig,
 27    F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
 28    for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
 29{
 30    pub fn new(x: F, y: F) -> Self {
 31        Self {
 32            x,
 33            y,
 34            _params: PhantomData,
 35        }
 36    }
 37
 38    /// Converts self into a non-zero projective point.
 39    #[tracing::instrument(target = "r1cs", skip(self))]
 40    pub fn into_projective(&self) -> ProjectiveVar<P, F> {
 41        ProjectiveVar::new(self.x.clone(), self.y.clone(), F::one())
 42    }
 43
 44    /// Performs an addition without checking that other != ±self.
 45    #[tracing::instrument(target = "r1cs", skip(self, other))]
 46    pub fn add_unchecked(&self, other: &Self) -> Result<Self, SynthesisError> {
 47        if [self, other].is_constant() {
 48            let result = self.value()?.add(other.value()?).into_affine();
 49            Ok(Self::new(F::constant(result.x), F::constant(result.y)))
 50        } else {
 51            let (x1, y1) = (&self.x, &self.y);
 52            let (x2, y2) = (&other.x, &other.y);
 53            // Then,
 54            // slope lambda := (y2 - y1)/(x2 - x1);
 55            // x3 = lambda^2 - x1 - x2;
 56            // y3 = lambda * (x1 - x3) - y1
 57            let numerator = y2 - y1;
 58            let denominator = x2 - x1;
 59            // It's okay to use `unchecked` here, because the precondition of
 60            // `add_unchecked` is that self != ±other, which means that
 61            // `numerator` and `denominator` are both non-zero.
 62            let lambda = numerator.mul_by_inverse_unchecked(&denominator)?;
 63            let x3 = lambda.square()? - x1 - x2;
 64            let y3 = lambda * &(x1 - &x3) - y1;
 65            Ok(Self::new(x3, y3))
 66        }
 67    }
 68
 69    /// Doubles `self`. As this is a prime order curve point,
 70    /// the output is guaranteed to not be the point at infinity.
 71    #[tracing::instrument(target = "r1cs", skip(self))]
 72    pub fn double(&self) -> Result<Self, SynthesisError> {
 73        if [self].is_constant() {
 74            let result = SWProjective::<P>::from(self.value()?)
 75                .double()
 76                .into_affine();
 77            // Panic if the result is zero.
 78            assert!(!result.is_zero());
 79            Ok(Self::new(F::constant(result.x), F::constant(result.y)))
 80        } else {
 81            let (x1, y1) = (&self.x, &self.y);
 82            let x1_sqr = x1.square()?;
 83            // Then,
 84            // tangent lambda := (3 * x1^2 + a) / (2 * y1);
 85            // x3 = lambda^2 - 2x1
 86            // y3 = lambda * (x1 - x3) - y1
 87            let numerator = x1_sqr.double()? + &x1_sqr + P::COEFF_A;
 88            let denominator = y1.double()?;
 89            // It's okay to use `unchecked` here, because the precondition of `double` is
 90            // that self != zero.
 91            let lambda = numerator.mul_by_inverse_unchecked(&denominator)?;
 92            let x3 = lambda.square()? - x1.double()?;
 93            let y3 = lambda * &(x1 - &x3) - y1;
 94            Ok(Self::new(x3, y3))
 95        }
 96    }
 97
 98    /// Computes `(self + other) + self`. This method requires only 5
 99    /// constraints, less than the 7 required when computing via
100    /// `self.double() + other`.
101    ///
102    /// This follows the formulae from [\[ELM03\]](https://arxiv.org/abs/math/0208038).
103    #[tracing::instrument(target = "r1cs", skip(self))]
104    pub fn double_and_add_unchecked(&self, other: &Self) -> Result<Self, SynthesisError> {
105        if [self].is_constant() || other.is_constant() {
106            self.double()?.add_unchecked(other)
107        } else {
108            // It's okay to use `unchecked` the precondition is that `self != ±other` (i.e.
109            // same logic as in `add_unchecked`)
110            let (x1, y1) = (&self.x, &self.y);
111            let (x2, y2) = (&other.x, &other.y);
112
113            // Calculate self + other:
114            // slope lambda := (y2 - y1)/(x2 - x1);
115            // x3 = lambda^2 - x1 - x2;
116            // y3 = lambda * (x1 - x3) - y1
117            let numerator = y2 - y1;
118            let denominator = x2 - x1;
119            let lambda_1 = numerator.mul_by_inverse_unchecked(&denominator)?;
120
121            let x3 = lambda_1.square()? - x1 - x2;
122
123            // Calculate final addition slope:
124            let lambda_2 =
125                (lambda_1 + y1.double()?.mul_by_inverse_unchecked(&(&x3 - x1))?).negate()?;
126
127            let x4 = lambda_2.square()? - x1 - x3;
128            let y4 = lambda_2 * &(x1 - &x4) - y1;
129            Ok(Self::new(x4, y4))
130        }
131    }
132
133    /// Doubles `self` in place.
134    #[tracing::instrument(target = "r1cs", skip(self))]
135    pub fn double_in_place(&mut self) -> Result<(), SynthesisError> {
136        *self = self.double()?;
137        Ok(())
138    }
139}
140
141impl<P, F> R1CSVar<<P::BaseField as Field>::BasePrimeField> for NonZeroAffineVar<P, F>
142where
143    P: SWCurveConfig,
144    F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
145    for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
146{
147    type Value = SWAffine<P>;
148
149    fn cs(&self) -> ConstraintSystemRef<<P::BaseField as Field>::BasePrimeField> {
150        self.x.cs().or(self.y.cs())
151    }
152
153    fn value(&self) -> Result<SWAffine<P>, SynthesisError> {
154        Ok(SWAffine::new(self.x.value()?, self.y.value()?))
155    }
156}
157
158impl<P, F> CondSelectGadget<<P::BaseField as Field>::BasePrimeField> for NonZeroAffineVar<P, F>
159where
160    P: SWCurveConfig,
161    F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
162    for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
163{
164    #[inline]
165    #[tracing::instrument(target = "r1cs")]
166    fn conditionally_select(
167        cond: &Boolean<<P::BaseField as Field>::BasePrimeField>,
168        true_value: &Self,
169        false_value: &Self,
170    ) -> Result<Self, SynthesisError> {
171        let x = cond.select(&true_value.x, &false_value.x)?;
172        let y = cond.select(&true_value.y, &false_value.y)?;
173
174        Ok(Self::new(x, y))
175    }
176}
177
178impl<P, F> EqGadget<<P::BaseField as Field>::BasePrimeField> for NonZeroAffineVar<P, F>
179where
180    P: SWCurveConfig,
181    F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
182    for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
183{
184    #[tracing::instrument(target = "r1cs")]
185    fn is_eq(
186        &self,
187        other: &Self,
188    ) -> Result<Boolean<<P::BaseField as Field>::BasePrimeField>, SynthesisError> {
189        let x_equal = self.x.is_eq(&other.x)?;
190        let y_equal = self.y.is_eq(&other.y)?;
191        Ok(x_equal & y_equal)
192    }
193
194    #[inline]
195    #[tracing::instrument(target = "r1cs")]
196    fn conditional_enforce_equal(
197        &self,
198        other: &Self,
199        condition: &Boolean<<P::BaseField as Field>::BasePrimeField>,
200    ) -> Result<(), SynthesisError> {
201        let x_equal = self.x.is_eq(&other.x)?;
202        let y_equal = self.y.is_eq(&other.y)?;
203        let coordinates_equal = x_equal & y_equal;
204        coordinates_equal.conditional_enforce_equal(&Boolean::TRUE, condition)?;
205        Ok(())
206    }
207
208    #[inline]
209    #[tracing::instrument(target = "r1cs")]
210    fn enforce_equal(&self, other: &Self) -> Result<(), SynthesisError> {
211        self.x.enforce_equal(&other.x)?;
212        self.y.enforce_equal(&other.y)?;
213        Ok(())
214    }
215
216    #[inline]
217    #[tracing::instrument(target = "r1cs")]
218    fn conditional_enforce_not_equal(
219        &self,
220        other: &Self,
221        condition: &Boolean<<P::BaseField as Field>::BasePrimeField>,
222    ) -> Result<(), SynthesisError> {
223        let is_equal = self.is_eq(other)?;
224        (is_equal & condition).enforce_equal(&Boolean::FALSE)
225    }
226}
227
228#[cfg(test)]
229mod test_non_zero_affine {
230    use crate::{
231        alloc::AllocVar,
232        eq::EqGadget,
233        fields::fp::{AllocatedFp, FpVar},
234        groups::{
235            curves::short_weierstrass::{non_zero_affine::NonZeroAffineVar, ProjectiveVar},
236            CurveVar,
237        },
238        R1CSVar,
239    };
240    use ark_ec::{models::short_weierstrass::SWCurveConfig, CurveGroup};
241    use ark_relations::r1cs::ConstraintSystem;
242    use ark_std::{vec::Vec, One};
243    use ark_test_curves::bls12_381::{g1::Config as G1Config, Fq};
244
245    #[test]
246    fn correctness_test_1() {
247        let cs = ConstraintSystem::<Fq>::new_ref();
248
249        let x = FpVar::Var(
250            AllocatedFp::<Fq>::new_witness(cs.clone(), || Ok(G1Config::GENERATOR.x)).unwrap(),
251        );
252        let y = FpVar::Var(
253            AllocatedFp::<Fq>::new_witness(cs.clone(), || Ok(G1Config::GENERATOR.y)).unwrap(),
254        );
255
256        // The following code uses `double` and `add` (`add_unchecked`) to compute
257        // (1 + 2 + ... + 2^9) G
258
259        let sum_a = {
260            let mut a = ProjectiveVar::<G1Config, FpVar<Fq>>::new(
261                x.clone(),
262                y.clone(),
263                FpVar::Constant(Fq::one()),
264            );
265
266            let mut double_sequence = Vec::new();
267            double_sequence.push(a.clone());
268
269            for _ in 1..10 {
270                a = a.double().unwrap();
271                double_sequence.push(a.clone());
272            }
273
274            let mut sum = double_sequence[0].clone();
275            for elem in double_sequence.iter().skip(1) {
276                sum = sum + elem;
277            }
278
279            let sum = sum.value().unwrap().into_affine();
280            (sum.x, sum.y)
281        };
282
283        let sum_b = {
284            let mut a = NonZeroAffineVar::<G1Config, FpVar<Fq>>::new(x, y);
285
286            let mut double_sequence = Vec::new();
287            double_sequence.push(a.clone());
288
289            for _ in 1..10 {
290                a = a.double().unwrap();
291                double_sequence.push(a.clone());
292            }
293
294            let mut sum = double_sequence[0].clone();
295            for elem in double_sequence.iter().skip(1) {
296                sum = sum.add_unchecked(&elem).unwrap();
297            }
298
299            (sum.x.value().unwrap(), sum.y.value().unwrap())
300        };
301
302        assert_eq!(sum_a.0, sum_b.0);
303        assert_eq!(sum_a.1, sum_b.1);
304    }
305
306    #[test]
307    fn correctness_test_2() {
308        let cs = ConstraintSystem::<Fq>::new_ref();
309
310        let x = FpVar::Var(
311            AllocatedFp::<Fq>::new_witness(cs.clone(), || Ok(G1Config::GENERATOR.x)).unwrap(),
312        );
313        let y = FpVar::Var(
314            AllocatedFp::<Fq>::new_witness(cs.clone(), || Ok(G1Config::GENERATOR.y)).unwrap(),
315        );
316
317        // The following code tests `double_and_add`.
318        let sum_a = {
319            let a = ProjectiveVar::<G1Config, FpVar<Fq>>::new(
320                x.clone(),
321                y.clone(),
322                FpVar::Constant(Fq::one()),
323            );
324
325            let mut cur = a.clone();
326            cur.double_in_place().unwrap();
327            for _ in 1..10 {
328                cur.double_in_place().unwrap();
329                cur = cur + &a;
330            }
331
332            let sum = cur.value().unwrap().into_affine();
333            (sum.x, sum.y)
334        };
335
336        let sum_b = {
337            let a = NonZeroAffineVar::<G1Config, FpVar<Fq>>::new(x, y);
338
339            let mut cur = a.double().unwrap();
340            for _ in 1..10 {
341                cur = cur.double_and_add_unchecked(&a).unwrap();
342            }
343
344            (cur.x.value().unwrap(), cur.y.value().unwrap())
345        };
346
347        assert!(cs.is_satisfied().unwrap());
348        assert_eq!(sum_a.0, sum_b.0);
349        assert_eq!(sum_a.1, sum_b.1);
350    }
351
352    #[test]
353    fn correctness_test_eq() {
354        let cs = ConstraintSystem::<Fq>::new_ref();
355
356        let x = FpVar::Var(
357            AllocatedFp::<Fq>::new_witness(cs.clone(), || Ok(G1Config::GENERATOR.x)).unwrap(),
358        );
359        let y = FpVar::Var(
360            AllocatedFp::<Fq>::new_witness(cs.clone(), || Ok(G1Config::GENERATOR.y)).unwrap(),
361        );
362
363        let a = NonZeroAffineVar::<G1Config, FpVar<Fq>>::new(x, y);
364
365        let n = 10;
366
367        let a_multiples: Vec<NonZeroAffineVar<G1Config, FpVar<Fq>>> =
368            std::iter::successors(Some(a.clone()), |acc| Some(acc.add_unchecked(&a).unwrap()))
369                .take(n)
370                .collect();
371
372        let all_equal: Vec<NonZeroAffineVar<G1Config, FpVar<Fq>>> = (0..n / 2)
373            .map(|i| {
374                a_multiples[i]
375                    .add_unchecked(&a_multiples[n - i - 1])
376                    .unwrap()
377            })
378            .collect();
379
380        for i in 0..n - 1 {
381            a_multiples[i]
382                .enforce_not_equal(&a_multiples[i + 1])
383                .unwrap();
384        }
385        for i in 0..all_equal.len() - 1 {
386            all_equal[i].enforce_equal(&all_equal[i + 1]).unwrap();
387        }
388
389        assert!(cs.is_satisfied().unwrap());
390    }
391}