1use super::*;
  2
  3/// An affine representation of a prime order curve point that is guaranteed
  4/// to *not* be the point at infinity.
  5#[derive(Derivative)]
  6#[derivative(Debug, Clone)]
  7#[must_use]
  8pub struct NonZeroAffineVar<
  9    P: SWModelParameters,
 10    F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
 11> where
 12    for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
 13{
 14    /// The x-coordinate.
 15    pub x: F,
 16    /// The y-coordinate.
 17    pub y: F,
 18    #[derivative(Debug = "ignore")]
 19    _params: PhantomData<P>,
 20}
 21
 22impl<P, F> NonZeroAffineVar<P, F>
 23where
 24    P: SWModelParameters,
 25    F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
 26    for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
 27{
 28    pub(crate) fn new(x: F, y: F) -> Self {
 29        Self {
 30            x,
 31            y,
 32            _params: PhantomData,
 33        }
 34    }
 35
 36    /// Converts self into a non-zero projective point.
 37    #[tracing::instrument(target = "r1cs", skip(self))]
 38    pub(crate) fn into_projective(&self) -> ProjectiveVar<P, F> {
 39        ProjectiveVar::new(self.x.clone(), self.y.clone(), F::one())
 40    }
 41
 42    /// Performs an addition without checking that other != ±self.
 43    #[tracing::instrument(target = "r1cs", skip(self, other))]
 44    pub(crate) fn add_unchecked(&self, other: &Self) -> Result<Self, SynthesisError> {
 45        if [self, other].is_constant() {
 46            let result =
 47                (self.value()?.into_projective() + other.value()?.into_projective()).into_affine();
 48            Ok(Self::new(F::constant(result.x), F::constant(result.y)))
 49        } else {
 50            let (x1, y1) = (&self.x, &self.y);
 51            let (x2, y2) = (&other.x, &other.y);
 52            // Then,
 53            // slope lambda := (y2 - y1)/(x2 - x1);
 54            // x3 = lambda^2 - x1 - x2;
 55            // y3 = lambda * (x1 - x3) - y1
 56            let numerator = y2 - y1;
 57            let denominator = x2 - x1;
 58            let lambda = numerator.mul_by_inverse(&denominator)?;
 59            let x3 = lambda.square()? - x1 - x2;
 60            let y3 = lambda * &(x1 - &x3) - y1;
 61            Ok(Self::new(x3, y3))
 62        }
 63    }
 64
 65    /// Doubles `self`. As this is a prime order curve point,
 66    /// the output is guaranteed to not be the point at infinity.
 67    #[tracing::instrument(target = "r1cs", skip(self))]
 68    pub(crate) fn double(&self) -> Result<Self, SynthesisError> {
 69        if [self].is_constant() {
 70            let result = self.value()?.into_projective().double().into_affine();
 71            // Panic if the result is zero.
 72            assert!(!result.is_zero());
 73            Ok(Self::new(F::constant(result.x), F::constant(result.y)))
 74        } else {
 75            let (x1, y1) = (&self.x, &self.y);
 76            let x1_sqr = x1.square()?;
 77            // Then,
 78            // tangent lambda := (3 * x1^2 + a) / (2 * y1);
 79            // x3 = lambda^2 - 2x1
 80            // y3 = lambda * (x1 - x3) - y1
 81            let numerator = x1_sqr.double()? + &x1_sqr + P::COEFF_A;
 82            let denominator = y1.double()?;
 83            let lambda = numerator.mul_by_inverse(&denominator)?;
 84            let x3 = lambda.square()? - x1.double()?;
 85            let y3 = lambda * &(x1 - &x3) - y1;
 86            Ok(Self::new(x3, y3))
 87        }
 88    }
 89
 90    /// Computes `(self + other) + self`. This method requires only 5 constraints,
 91    /// less than the 7 required when computing via `self.double() + other`.
 92    ///
 93    /// This follows the formulae from [\[ELM03\]](https://arxiv.org/abs/math/0208038).
 94    #[tracing::instrument(target = "r1cs", skip(self))]
 95    pub(crate) fn double_and_add(&self, other: &Self) -> Result<Self, SynthesisError> {
 96        if [self].is_constant() || other.is_constant() {
 97            self.double()?.add_unchecked(other)
 98        } else {
 99            let (x1, y1) = (&self.x, &self.y);
100            let (x2, y2) = (&other.x, &other.y);
101
102            // Calculate self + other:
103            // slope lambda := (y2 - y1)/(x2 - x1);
104            // x3 = lambda^2 - x1 - x2;
105            // y3 = lambda * (x1 - x3) - y1
106            let numerator = y2 - y1;
107            let denominator = x2 - x1;
108            let lambda_1 = numerator.mul_by_inverse(&denominator)?;
109
110            let x3 = lambda_1.square()? - x1 - x2;
111
112            // Calculate final addition slope:
113            let lambda_2 = (lambda_1 + y1.double()?.mul_by_inverse(&(&x3 - x1))?).negate()?;
114
115            let x4 = lambda_2.square()? - x1 - x3;
116            let y4 = lambda_2 * &(x1 - &x4) - y1;
117            Ok(Self::new(x4, y4))
118        }
119    }
120
121    /// Doubles `self` in place.
122    #[tracing::instrument(target = "r1cs", skip(self))]
123    pub(crate) fn double_in_place(&mut self) -> Result<(), SynthesisError> {
124        *self = self.double()?;
125        Ok(())
126    }
127}
128
129impl<P, F> R1CSVar<<P::BaseField as Field>::BasePrimeField> for NonZeroAffineVar<P, F>
130where
131    P: SWModelParameters,
132    F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
133    for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
134{
135    type Value = SWAffine<P>;
136
137    fn cs(&self) -> ConstraintSystemRef<<P::BaseField as Field>::BasePrimeField> {
138        self.x.cs().or(self.y.cs())
139    }
140
141    fn value(&self) -> Result<SWAffine<P>, SynthesisError> {
142        Ok(SWAffine::new(self.x.value()?, self.y.value()?, false))
143    }
144}
145
146impl<P, F> CondSelectGadget<<P::BaseField as Field>::BasePrimeField> for NonZeroAffineVar<P, F>
147where
148    P: SWModelParameters,
149    F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
150    for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
151{
152    #[inline]
153    #[tracing::instrument(target = "r1cs")]
154    fn conditionally_select(
155        cond: &Boolean<<P::BaseField as Field>::BasePrimeField>,
156        true_value: &Self,
157        false_value: &Self,
158    ) -> Result<Self, SynthesisError> {
159        let x = cond.select(&true_value.x, &false_value.x)?;
160        let y = cond.select(&true_value.y, &false_value.y)?;
161
162        Ok(Self::new(x, y))
163    }
164}
165
166#[cfg(test)]
167mod test {
168    use crate::alloc::AllocVar;
169    use crate::fields::fp::{AllocatedFp, FpVar};
170    use crate::groups::curves::short_weierstrass::non_zero_affine::NonZeroAffineVar;
171    use crate::groups::curves::short_weierstrass::ProjectiveVar;
172    use crate::groups::CurveVar;
173    use crate::R1CSVar;
174    use ark_ec::SWModelParameters;
175    use ark_relations::r1cs::ConstraintSystem;
176    use ark_std::{vec::Vec, One};
177    use ark_test_curves::bls12_381::{g1::Parameters as G1Parameters, Fq};
178
179    #[test]
180    fn test_non_zero_affine_cost() {
181        let cs = ConstraintSystem::<Fq>::new_ref();
182
183        let x = FpVar::Var(
184            AllocatedFp::<Fq>::new_witness(cs.clone(), || {
185                Ok(G1Parameters::AFFINE_GENERATOR_COEFFS.0)
186            })
187            .unwrap(),
188        );
189        let y = FpVar::Var(
190            AllocatedFp::<Fq>::new_witness(cs.clone(), || {
191                Ok(G1Parameters::AFFINE_GENERATOR_COEFFS.1)
192            })
193            .unwrap(),
194        );
195
196        // The following code uses `double` and `add` (`add_unchecked`) to compute
197        // (1 + 2 + ... + 2^9) G
198
199        let sum_a = {
200            let mut a = ProjectiveVar::<G1Parameters, FpVar<Fq>>::new(
201                x.clone(),
202                y.clone(),
203                FpVar::Constant(Fq::one()),
204            );
205
206            let mut double_sequence = Vec::new();
207            double_sequence.push(a.clone());
208
209            for _ in 1..10 {
210                a = a.double().unwrap();
211                double_sequence.push(a.clone());
212            }
213
214            let mut sum = double_sequence[0].clone();
215            for elem in double_sequence.iter().skip(1) {
216                sum = sum + elem;
217            }
218
219            let sum = sum.value().unwrap();
220            (sum.x, sum.y)
221        };
222
223        let sum_b = {
224            let mut a = NonZeroAffineVar::<G1Parameters, FpVar<Fq>>::new(x, y);
225
226            let mut double_sequence = Vec::new();
227            double_sequence.push(a.clone());
228
229            for _ in 1..10 {
230                a = a.double().unwrap();
231                double_sequence.push(a.clone());
232            }
233
234            let mut sum = double_sequence[0].clone();
235            for elem in double_sequence.iter().skip(1) {
236                sum = sum.add_unchecked(&elem).unwrap();
237            }
238
239            (sum.x.value().unwrap(), sum.y.value().unwrap())
240        };
241
242        assert_eq!(sum_a.0, sum_b.0);
243        assert_eq!(sum_a.1, sum_b.1);
244    }
245}