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            // It's okay to use `unchecked` here, because the precondition of `add_unchecked` is that
 59            // self != ±other, which means that `numerator` and `denominator` are both non-zero.
 60            let lambda = numerator.mul_by_inverse_unchecked(&denominator)?;
 61            let x3 = lambda.square()? - x1 - x2;
 62            let y3 = lambda * &(x1 - &x3) - y1;
 63            Ok(Self::new(x3, y3))
 64        }
 65    }
 66
 67    /// Doubles `self`. As this is a prime order curve point,
 68    /// the output is guaranteed to not be the point at infinity.
 69    #[tracing::instrument(target = "r1cs", skip(self))]
 70    pub(crate) fn double(&self) -> Result<Self, SynthesisError> {
 71        if [self].is_constant() {
 72            let result = self.value()?.into_projective().double().into_affine();
 73            // Panic if the result is zero.
 74            assert!(!result.is_zero());
 75            Ok(Self::new(F::constant(result.x), F::constant(result.y)))
 76        } else {
 77            let (x1, y1) = (&self.x, &self.y);
 78            let x1_sqr = x1.square()?;
 79            // Then,
 80            // tangent lambda := (3 * x1^2 + a) / (2 * y1);
 81            // x3 = lambda^2 - 2x1
 82            // y3 = lambda * (x1 - x3) - y1
 83            let numerator = x1_sqr.double()? + &x1_sqr + P::COEFF_A;
 84            let denominator = y1.double()?;
 85            // It's okay to use `unchecked` here, because the precondition of `double` is that
 86            // self != zero.
 87            let lambda = numerator.mul_by_inverse_unchecked(&denominator)?;
 88            let x3 = lambda.square()? - x1.double()?;
 89            let y3 = lambda * &(x1 - &x3) - y1;
 90            Ok(Self::new(x3, y3))
 91        }
 92    }
 93
 94    /// Computes `(self + other) + self`. This method requires only 5 constraints,
 95    /// less than the 7 required when computing via `self.double() + other`.
 96    ///
 97    /// This follows the formulae from [\[ELM03\]](https://arxiv.org/abs/math/0208038).
 98    #[tracing::instrument(target = "r1cs", skip(self))]
 99    pub(crate) fn double_and_add_unchecked(&self, other: &Self) -> Result<Self, SynthesisError> {
100        if [self].is_constant() || other.is_constant() {
101            self.double()?.add_unchecked(other)
102        } else {
103            // It's okay to use `unchecked` the precondition is that `self != ±other` (i.e. same logic as in `add_unchecked`)
104            let (x1, y1) = (&self.x, &self.y);
105            let (x2, y2) = (&other.x, &other.y);
106
107            // Calculate self + other:
108            // slope lambda := (y2 - y1)/(x2 - x1);
109            // x3 = lambda^2 - x1 - x2;
110            // y3 = lambda * (x1 - x3) - y1
111            let numerator = y2 - y1;
112            let denominator = x2 - x1;
113            let lambda_1 = numerator.mul_by_inverse_unchecked(&denominator)?;
114
115            let x3 = lambda_1.square()? - x1 - x2;
116
117            // Calculate final addition slope:
118            let lambda_2 =
119                (lambda_1 + y1.double()?.mul_by_inverse_unchecked(&(&x3 - x1))?).negate()?;
120
121            let x4 = lambda_2.square()? - x1 - x3;
122            let y4 = lambda_2 * &(x1 - &x4) - y1;
123            Ok(Self::new(x4, y4))
124        }
125    }
126
127    /// Doubles `self` in place.
128    #[tracing::instrument(target = "r1cs", skip(self))]
129    pub(crate) fn double_in_place(&mut self) -> Result<(), SynthesisError> {
130        *self = self.double()?;
131        Ok(())
132    }
133}
134
135impl<P, F> R1CSVar<<P::BaseField as Field>::BasePrimeField> for NonZeroAffineVar<P, F>
136where
137    P: SWModelParameters,
138    F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
139    for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
140{
141    type Value = SWAffine<P>;
142
143    fn cs(&self) -> ConstraintSystemRef<<P::BaseField as Field>::BasePrimeField> {
144        self.x.cs().or(self.y.cs())
145    }
146
147    fn value(&self) -> Result<SWAffine<P>, SynthesisError> {
148        Ok(SWAffine::new(self.x.value()?, self.y.value()?, false))
149    }
150}
151
152impl<P, F> CondSelectGadget<<P::BaseField as Field>::BasePrimeField> for NonZeroAffineVar<P, F>
153where
154    P: SWModelParameters,
155    F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
156    for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
157{
158    #[inline]
159    #[tracing::instrument(target = "r1cs")]
160    fn conditionally_select(
161        cond: &Boolean<<P::BaseField as Field>::BasePrimeField>,
162        true_value: &Self,
163        false_value: &Self,
164    ) -> Result<Self, SynthesisError> {
165        let x = cond.select(&true_value.x, &false_value.x)?;
166        let y = cond.select(&true_value.y, &false_value.y)?;
167
168        Ok(Self::new(x, y))
169    }
170}
171
172#[cfg(test)]
173mod test_non_zero_affine {
174    use crate::alloc::AllocVar;
175    use crate::fields::fp::{AllocatedFp, FpVar};
176    use crate::groups::curves::short_weierstrass::non_zero_affine::NonZeroAffineVar;
177    use crate::groups::curves::short_weierstrass::ProjectiveVar;
178    use crate::groups::CurveVar;
179    use crate::R1CSVar;
180    use ark_ec::{ProjectiveCurve, SWModelParameters};
181    use ark_relations::r1cs::ConstraintSystem;
182    use ark_std::{vec::Vec, One};
183    use ark_test_curves::bls12_381::{g1::Parameters as G1Parameters, Fq};
184
185    #[test]
186    fn correctness_test_1() {
187        let cs = ConstraintSystem::<Fq>::new_ref();
188
189        let x = FpVar::Var(
190            AllocatedFp::<Fq>::new_witness(cs.clone(), || {
191                Ok(G1Parameters::AFFINE_GENERATOR_COEFFS.0)
192            })
193            .unwrap(),
194        );
195        let y = FpVar::Var(
196            AllocatedFp::<Fq>::new_witness(cs.clone(), || {
197                Ok(G1Parameters::AFFINE_GENERATOR_COEFFS.1)
198            })
199            .unwrap(),
200        );
201
202        // The following code uses `double` and `add` (`add_unchecked`) to compute
203        // (1 + 2 + ... + 2^9) G
204
205        let sum_a = {
206            let mut a = ProjectiveVar::<G1Parameters, FpVar<Fq>>::new(
207                x.clone(),
208                y.clone(),
209                FpVar::Constant(Fq::one()),
210            );
211
212            let mut double_sequence = Vec::new();
213            double_sequence.push(a.clone());
214
215            for _ in 1..10 {
216                a = a.double().unwrap();
217                double_sequence.push(a.clone());
218            }
219
220            let mut sum = double_sequence[0].clone();
221            for elem in double_sequence.iter().skip(1) {
222                sum = sum + elem;
223            }
224
225            let sum = sum.value().unwrap().into_affine();
226            (sum.x, sum.y)
227        };
228
229        let sum_b = {
230            let mut a = NonZeroAffineVar::<G1Parameters, FpVar<Fq>>::new(x, y);
231
232            let mut double_sequence = Vec::new();
233            double_sequence.push(a.clone());
234
235            for _ in 1..10 {
236                a = a.double().unwrap();
237                double_sequence.push(a.clone());
238            }
239
240            let mut sum = double_sequence[0].clone();
241            for elem in double_sequence.iter().skip(1) {
242                sum = sum.add_unchecked(&elem).unwrap();
243            }
244
245            (sum.x.value().unwrap(), sum.y.value().unwrap())
246        };
247
248        assert_eq!(sum_a.0, sum_b.0);
249        assert_eq!(sum_a.1, sum_b.1);
250    }
251
252    #[test]
253    fn correctness_test_2() {
254        let cs = ConstraintSystem::<Fq>::new_ref();
255
256        let x = FpVar::Var(
257            AllocatedFp::<Fq>::new_witness(cs.clone(), || {
258                Ok(G1Parameters::AFFINE_GENERATOR_COEFFS.0)
259            })
260            .unwrap(),
261        );
262        let y = FpVar::Var(
263            AllocatedFp::<Fq>::new_witness(cs.clone(), || {
264                Ok(G1Parameters::AFFINE_GENERATOR_COEFFS.1)
265            })
266            .unwrap(),
267        );
268
269        // The following code tests `double_and_add`.
270        let sum_a = {
271            let a = ProjectiveVar::<G1Parameters, FpVar<Fq>>::new(
272                x.clone(),
273                y.clone(),
274                FpVar::Constant(Fq::one()),
275            );
276
277            let mut cur = a.clone();
278            cur.double_in_place().unwrap();
279            for _ in 1..10 {
280                cur.double_in_place().unwrap();
281                cur = cur + &a;
282            }
283
284            let sum = cur.value().unwrap().into_affine();
285            (sum.x, sum.y)
286        };
287
288        let sum_b = {
289            let a = NonZeroAffineVar::<G1Parameters, FpVar<Fq>>::new(x, y);
290
291            let mut cur = a.double().unwrap();
292            for _ in 1..10 {
293                cur = cur.double_and_add_unchecked(&a).unwrap();
294            }
295
296            (cur.x.value().unwrap(), cur.y.value().unwrap())
297        };
298
299        assert!(cs.is_satisfied().unwrap());
300        assert_eq!(sum_a.0, sum_b.0);
301        assert_eq!(sum_a.1, sum_b.1);
302    }
303}