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