ark-r1cs-std/src/groups/curves/short_weierstrass/non_zero_affine.rs
src/groups/curves/short_weierstrass/non_zero_affine.rsRaw
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 x_equal.and(&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.and(&y_equal)?;
204 coordinates_equal.conditional_enforce_equal(&Boolean::Constant(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
225 .and(condition)?
226 .enforce_equal(&Boolean::Constant(false))
227 }
228}
229
230#[cfg(test)]
231mod test_non_zero_affine {
232 use crate::{
233 alloc::AllocVar,
234 eq::EqGadget,
235 fields::fp::{AllocatedFp, FpVar},
236 groups::{
237 curves::short_weierstrass::{non_zero_affine::NonZeroAffineVar, ProjectiveVar},
238 CurveVar,
239 },
240 R1CSVar,
241 };
242 use ark_ec::{models::short_weierstrass::SWCurveConfig, CurveGroup};
243 use ark_relations::r1cs::ConstraintSystem;
244 use ark_std::{vec::Vec, One};
245 use ark_test_curves::bls12_381::{g1::Config as G1Config, Fq};
246
247 #[test]
248 fn correctness_test_1() {
249 let cs = ConstraintSystem::<Fq>::new_ref();
250
251 let x = FpVar::Var(
252 AllocatedFp::<Fq>::new_witness(cs.clone(), || Ok(G1Config::GENERATOR.x)).unwrap(),
253 );
254 let y = FpVar::Var(
255 AllocatedFp::<Fq>::new_witness(cs.clone(), || Ok(G1Config::GENERATOR.y)).unwrap(),
256 );
257
258 // The following code uses `double` and `add` (`add_unchecked`) to compute
259 // (1 + 2 + ... + 2^9) G
260
261 let sum_a = {
262 let mut a = ProjectiveVar::<G1Config, FpVar<Fq>>::new(
263 x.clone(),
264 y.clone(),
265 FpVar::Constant(Fq::one()),
266 );
267
268 let mut double_sequence = Vec::new();
269 double_sequence.push(a.clone());
270
271 for _ in 1..10 {
272 a = a.double().unwrap();
273 double_sequence.push(a.clone());
274 }
275
276 let mut sum = double_sequence[0].clone();
277 for elem in double_sequence.iter().skip(1) {
278 sum = sum + elem;
279 }
280
281 let sum = sum.value().unwrap().into_affine();
282 (sum.x, sum.y)
283 };
284
285 let sum_b = {
286 let mut a = NonZeroAffineVar::<G1Config, FpVar<Fq>>::new(x, y);
287
288 let mut double_sequence = Vec::new();
289 double_sequence.push(a.clone());
290
291 for _ in 1..10 {
292 a = a.double().unwrap();
293 double_sequence.push(a.clone());
294 }
295
296 let mut sum = double_sequence[0].clone();
297 for elem in double_sequence.iter().skip(1) {
298 sum = sum.add_unchecked(&elem).unwrap();
299 }
300
301 (sum.x.value().unwrap(), sum.y.value().unwrap())
302 };
303
304 assert_eq!(sum_a.0, sum_b.0);
305 assert_eq!(sum_a.1, sum_b.1);
306 }
307
308 #[test]
309 fn correctness_test_2() {
310 let cs = ConstraintSystem::<Fq>::new_ref();
311
312 let x = FpVar::Var(
313 AllocatedFp::<Fq>::new_witness(cs.clone(), || Ok(G1Config::GENERATOR.x)).unwrap(),
314 );
315 let y = FpVar::Var(
316 AllocatedFp::<Fq>::new_witness(cs.clone(), || Ok(G1Config::GENERATOR.y)).unwrap(),
317 );
318
319 // The following code tests `double_and_add`.
320 let sum_a = {
321 let a = ProjectiveVar::<G1Config, FpVar<Fq>>::new(
322 x.clone(),
323 y.clone(),
324 FpVar::Constant(Fq::one()),
325 );
326
327 let mut cur = a.clone();
328 cur.double_in_place().unwrap();
329 for _ in 1..10 {
330 cur.double_in_place().unwrap();
331 cur = cur + &a;
332 }
333
334 let sum = cur.value().unwrap().into_affine();
335 (sum.x, sum.y)
336 };
337
338 let sum_b = {
339 let a = NonZeroAffineVar::<G1Config, FpVar<Fq>>::new(x, y);
340
341 let mut cur = a.double().unwrap();
342 for _ in 1..10 {
343 cur = cur.double_and_add_unchecked(&a).unwrap();
344 }
345
346 (cur.x.value().unwrap(), cur.y.value().unwrap())
347 };
348
349 assert!(cs.is_satisfied().unwrap());
350 assert_eq!(sum_a.0, sum_b.0);
351 assert_eq!(sum_a.1, sum_b.1);
352 }
353
354 #[test]
355 fn correctness_test_eq() {
356 let cs = ConstraintSystem::<Fq>::new_ref();
357
358 let x = FpVar::Var(
359 AllocatedFp::<Fq>::new_witness(cs.clone(), || Ok(G1Config::GENERATOR.x)).unwrap(),
360 );
361 let y = FpVar::Var(
362 AllocatedFp::<Fq>::new_witness(cs.clone(), || Ok(G1Config::GENERATOR.y)).unwrap(),
363 );
364
365 let a = NonZeroAffineVar::<G1Config, FpVar<Fq>>::new(x, y);
366
367 let n = 10;
368
369 let a_multiples: Vec<NonZeroAffineVar<G1Config, FpVar<Fq>>> =
370 std::iter::successors(Some(a.clone()), |acc| Some(acc.add_unchecked(&a).unwrap()))
371 .take(n)
372 .collect();
373
374 let all_equal: Vec<NonZeroAffineVar<G1Config, FpVar<Fq>>> = (0..n / 2)
375 .map(|i| {
376 a_multiples[i]
377 .add_unchecked(&a_multiples[n - i - 1])
378 .unwrap()
379 })
380 .collect();
381
382 for i in 0..n - 1 {
383 a_multiples[i]
384 .enforce_not_equal(&a_multiples[i + 1])
385 .unwrap();
386 }
387 for i in 0..all_equal.len() - 1 {
388 all_equal[i].enforce_equal(&all_equal[i + 1]).unwrap();
389 }
390
391 assert!(cs.is_satisfied().unwrap());
392 }
393}