ark-r1cs-std/src/groups/curves/short_weierstrass/mod.rs
src/groups/curves/short_weierstrass/mod.rsRaw
1use ark_ec::{
2 short_weierstrass_jacobian::{GroupAffine as SWAffine, GroupProjective as SWProjective},
3 AffineCurve, ProjectiveCurve, SWModelParameters,
4};
5use ark_ff::{BigInteger, BitIteratorBE, Field, FpParameters, One, PrimeField, Zero};
6use ark_relations::r1cs::{ConstraintSystemRef, Namespace, SynthesisError};
7use core::{borrow::Borrow, marker::PhantomData};
8use non_zero_affine::NonZeroAffineVar;
9
10use crate::{fields::fp::FpVar, prelude::*, ToConstraintFieldGadget, Vec};
11
12/// This module provides a generic implementation of G1 and G2 for
13/// the [\[BLS12]\](https://eprint.iacr.org/2002/088.pdf) family of bilinear groups.
14pub mod bls12;
15
16/// This module provides a generic implementation of G1 and G2 for
17/// the [\[MNT4]\](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.20.8113&rep=rep1&type=pdf)
18/// family of bilinear groups.
19pub mod mnt4;
20/// This module provides a generic implementation of G1 and G2 for
21/// the [\[MNT6]\](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.20.8113&rep=rep1&type=pdf)
22/// family of bilinear groups.
23pub mod mnt6;
24
25mod non_zero_affine;
26/// An implementation of arithmetic for Short Weierstrass curves that relies on
27/// the complete formulae derived in the paper of
28/// [[Renes, Costello, Batina 2015]](https://eprint.iacr.org/2015/1060).
29#[derive(Derivative)]
30#[derivative(Debug, Clone)]
31#[must_use]
32pub struct ProjectiveVar<
33 P: SWModelParameters,
34 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
35> where
36 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
37{
38 /// The x-coordinate.
39 pub x: F,
40 /// The y-coordinate.
41 pub y: F,
42 /// The z-coordinate.
43 pub z: F,
44 #[derivative(Debug = "ignore")]
45 _params: PhantomData<P>,
46}
47
48/// An affine representation of a curve point.
49#[derive(Derivative)]
50#[derivative(Debug, Clone)]
51#[must_use]
52pub struct AffineVar<
53 P: SWModelParameters,
54 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
55> where
56 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
57{
58 /// The x-coordinate.
59 pub x: F,
60 /// The y-coordinate.
61 pub y: F,
62 /// Is `self` the point at infinity.
63 pub infinity: Boolean<<P::BaseField as Field>::BasePrimeField>,
64 #[derivative(Debug = "ignore")]
65 _params: PhantomData<P>,
66}
67
68impl<P, F> AffineVar<P, F>
69where
70 P: SWModelParameters,
71 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
72 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
73{
74 fn new(x: F, y: F, infinity: Boolean<<P::BaseField as Field>::BasePrimeField>) -> Self {
75 Self {
76 x,
77 y,
78 infinity,
79 _params: PhantomData,
80 }
81 }
82
83 /// Returns the value assigned to `self` in the underlying
84 /// constraint system.
85 pub fn value(&self) -> Result<SWAffine<P>, SynthesisError> {
86 Ok(SWAffine::new(
87 self.x.value()?,
88 self.y.value()?,
89 self.infinity.value()?,
90 ))
91 }
92}
93
94impl<P, F> ToConstraintFieldGadget<<P::BaseField as Field>::BasePrimeField> for AffineVar<P, F>
95where
96 P: SWModelParameters,
97 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
98 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
99 F: ToConstraintFieldGadget<<P::BaseField as Field>::BasePrimeField>,
100{
101 fn to_constraint_field(
102 &self,
103 ) -> Result<Vec<FpVar<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
104 let mut res = Vec::<FpVar<<P::BaseField as Field>::BasePrimeField>>::new();
105
106 res.extend_from_slice(&self.x.to_constraint_field()?);
107 res.extend_from_slice(&self.y.to_constraint_field()?);
108 res.extend_from_slice(&self.infinity.to_constraint_field()?);
109
110 Ok(res)
111 }
112}
113
114impl<P, F> R1CSVar<<P::BaseField as Field>::BasePrimeField> for ProjectiveVar<P, F>
115where
116 P: SWModelParameters,
117 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
118 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
119{
120 type Value = SWProjective<P>;
121
122 fn cs(&self) -> ConstraintSystemRef<<P::BaseField as Field>::BasePrimeField> {
123 self.x.cs().or(self.y.cs()).or(self.z.cs())
124 }
125
126 fn value(&self) -> Result<Self::Value, SynthesisError> {
127 let (x, y, z) = (self.x.value()?, self.y.value()?, self.z.value()?);
128 let result = if let Some(z_inv) = z.inverse() {
129 SWAffine::new(x * &z_inv, y * &z_inv, false)
130 } else {
131 SWAffine::zero()
132 };
133 Ok(result.into())
134 }
135}
136
137impl<P: SWModelParameters, F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>>
138 ProjectiveVar<P, F>
139where
140 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
141{
142 /// Constructs `Self` from an `(x, y, z)` coordinate triple.
143 pub fn new(x: F, y: F, z: F) -> Self {
144 Self {
145 x,
146 y,
147 z,
148 _params: PhantomData,
149 }
150 }
151
152 /// Convert this point into affine form.
153 #[tracing::instrument(target = "r1cs")]
154 pub fn to_affine(&self) -> Result<AffineVar<P, F>, SynthesisError> {
155 if self.is_constant() {
156 let point = self.value()?.into_affine();
157 let x = F::new_constant(ConstraintSystemRef::None, point.x)?;
158 let y = F::new_constant(ConstraintSystemRef::None, point.y)?;
159 let infinity = Boolean::constant(point.infinity);
160 Ok(AffineVar::new(x, y, infinity))
161 } else {
162 let cs = self.cs();
163 let infinity = self.is_zero()?;
164 let zero_x = F::zero();
165 let zero_y = F::one();
166 // Allocate a variable whose value is either `self.z.inverse()` if the inverse exists,
167 // and is zero otherwise.
168 let z_inv = F::new_witness(ark_relations::ns!(cs, "z_inverse"), || {
169 Ok(self.z.value()?.inverse().unwrap_or_else(P::BaseField::zero))
170 })?;
171 // The inverse exists if `!self.is_zero()`.
172 // This means that `z_inv * self.z = 1` if `self.is_not_zero()`, and
173 // `z_inv * self.z = 0` if `self.is_zero()`.
174 //
175 // Thus, `z_inv * self.z = !self.is_zero()`.
176 z_inv.mul_equals(&self.z, &F::from(infinity.not()))?;
177
178 let non_zero_x = &self.x * &z_inv;
179 let non_zero_y = &self.y * &z_inv;
180
181 let x = infinity.select(&zero_x, &non_zero_x)?;
182 let y = infinity.select(&zero_y, &non_zero_y)?;
183
184 Ok(AffineVar::new(x, y, infinity))
185 }
186 }
187
188 /// Allocates a new variable without performing an on-curve check, which is
189 /// useful if the variable is known to be on the curve (eg., if the point
190 /// is a constant or is a public input).
191 #[tracing::instrument(target = "r1cs", skip(cs, f))]
192 pub fn new_variable_omit_on_curve_check(
193 cs: impl Into<Namespace<<P::BaseField as Field>::BasePrimeField>>,
194 f: impl FnOnce() -> Result<SWProjective<P>, SynthesisError>,
195 mode: AllocationMode,
196 ) -> Result<Self, SynthesisError> {
197 let ns = cs.into();
198 let cs = ns.cs();
199
200 let (x, y, z) = match f() {
201 Ok(ge) => {
202 let ge = ge.into_affine();
203 if ge.is_zero() {
204 (
205 Ok(P::BaseField::zero()),
206 Ok(P::BaseField::one()),
207 Ok(P::BaseField::zero()),
208 )
209 } else {
210 (Ok(ge.x), Ok(ge.y), Ok(P::BaseField::one()))
211 }
212 }
213 _ => (
214 Err(SynthesisError::AssignmentMissing),
215 Err(SynthesisError::AssignmentMissing),
216 Err(SynthesisError::AssignmentMissing),
217 ),
218 };
219
220 let x = F::new_variable(ark_relations::ns!(cs, "x"), || x, mode)?;
221 let y = F::new_variable(ark_relations::ns!(cs, "y"), || y, mode)?;
222 let z = F::new_variable(ark_relations::ns!(cs, "z"), || z, mode)?;
223
224 Ok(Self::new(x, y, z))
225 }
226
227 /// Mixed addition, which is useful when `other = (x2, y2)` is known to have z = 1.
228 #[tracing::instrument(target = "r1cs", skip(self, other))]
229 pub(crate) fn add_mixed(&self, other: &NonZeroAffineVar<P, F>) -> Result<Self, SynthesisError> {
230 // Complete mixed addition formula from Renes-Costello-Batina 2015
231 // Algorithm 2
232 // (https://eprint.iacr.org/2015/1060).
233 // Below, comments at the end of a line denote the corresponding
234 // step(s) of the algorithm
235 //
236 // Adapted from code in
237 // https://github.com/RustCrypto/elliptic-curves/blob/master/p256/src/arithmetic/projective.rs
238 let three_b = P::COEFF_B.double() + &P::COEFF_B;
239 let (x1, y1, z1) = (&self.x, &self.y, &self.z);
240 let (x2, y2) = (&other.x, &other.y);
241
242 let xx = x1 * x2; // 1
243 let yy = y1 * y2; // 2
244 let xy_pairs = ((x1 + y1) * &(x2 + y2)) - (&xx + &yy); // 4, 5, 6, 7, 8
245 let xz_pairs = (x2 * z1) + x1; // 8, 9
246 let yz_pairs = (y2 * z1) + y1; // 10, 11
247
248 let axz = mul_by_coeff_a::<P, F>(&xz_pairs); // 12
249
250 let bz3_part = &axz + z1 * three_b; // 13, 14
251
252 let yy_m_bz3 = &yy - &bz3_part; // 15
253 let yy_p_bz3 = &yy + &bz3_part; // 16
254
255 let azz = mul_by_coeff_a::<P, F>(z1); // 20
256 let xx3_p_azz = xx.double().unwrap() + &xx + &azz; // 18, 19, 22
257
258 let bxz3 = &xz_pairs * three_b; // 21
259 let b3_xz_pairs = mul_by_coeff_a::<P, F>(&(&xx - &azz)) + &bxz3; // 23, 24, 25
260
261 let x = (&yy_m_bz3 * &xy_pairs) - &yz_pairs * &b3_xz_pairs; // 28,29, 30
262 let y = (&yy_p_bz3 * &yy_m_bz3) + &xx3_p_azz * b3_xz_pairs; // 17, 26, 27
263 let z = (&yy_p_bz3 * &yz_pairs) + xy_pairs * xx3_p_azz; // 31, 32, 33
264
265 Ok(ProjectiveVar::new(x, y, z))
266 }
267
268 /// Computes a scalar multiplication with a little-endian scalar of size `P::ScalarField::MODULUS_BITS`.
269 #[tracing::instrument(
270 target = "r1cs",
271 skip(self, mul_result, multiple_of_power_of_two, bits)
272 )]
273 fn fixed_scalar_mul_le(
274 &self,
275 mul_result: &mut Self,
276 multiple_of_power_of_two: &mut NonZeroAffineVar<P, F>,
277 bits: &[&Boolean<<P::BaseField as Field>::BasePrimeField>],
278 ) -> Result<(), SynthesisError> {
279 let scalar_modulus_bits = <<P::ScalarField as PrimeField>::Params>::MODULUS_BITS as usize;
280
281 assert!(scalar_modulus_bits >= bits.len());
282 let split_len = ark_std::cmp::min(scalar_modulus_bits - 2, bits.len());
283 let (affine_bits, proj_bits) = bits.split_at(split_len);
284 // Computes the standard little-endian double-and-add algorithm
285 // (Algorithm 3.26, Guide to Elliptic Curve Cryptography)
286 //
287 // We rely on *incomplete* affine formulae for partially computing this.
288 // However, we avoid exceptional edge cases because we partition the scalar
289 // into two chunks: one guaranteed to be less than p - 2, and the rest.
290 // We only use incomplete formulae for the first chunk, which means we avoid exceptions:
291 //
292 // `add_unchecked(a, b)` is incomplete when either `b.is_zero()`, or when
293 // `b = ±a`. During scalar multiplication, we don't hit either case:
294 // * `b = ±a`: `b = accumulator = k * a`, where `2 <= k < p - 1`.
295 // This implies that `k != p ± 1`, and so `b != (p ± 1) * a`.
296 // Because the group is finite, this in turn means that `b != ±a`, as required.
297 // * `a` or `b` is zero: for `a`, we handle the zero case after the loop; for `b`, notice
298 // that it is monotonically increasing, and furthermore, equals `k * a`, where
299 // `k != p = 0 mod p`.
300
301 // Unlike normal double-and-add, here we start off with a non-zero `accumulator`,
302 // because `NonZeroAffineVar::add_unchecked` doesn't support addition with `zero`.
303 // In more detail, we initialize `accumulator` to be the initial value of
304 // `multiple_of_power_of_two`. This ensures that all unchecked additions of `accumulator`
305 // with later values of `multiple_of_power_of_two` are safe.
306 // However, to do this correctly, we need to perform two steps:
307 // * We must skip the LSB, and instead proceed assuming that it was 1. Later, we will
308 // conditionally subtract the initial value of `accumulator`:
309 // if LSB == 0: subtract initial_acc_value; else, subtract 0.
310 // * Because we are assuming the first bit, we must double `multiple_of_power_of_two`.
311
312 let mut accumulator = multiple_of_power_of_two.clone();
313 let initial_acc_value = accumulator.into_projective();
314
315 // The powers start at 2 (instead of 1) because we're skipping the first bit.
316 multiple_of_power_of_two.double_in_place()?;
317
318 // As mentioned, we will skip the LSB, and will later handle it via a conditional subtraction.
319 for bit in affine_bits.iter().skip(1) {
320 let temp = accumulator.add_unchecked(&multiple_of_power_of_two)?;
321 accumulator = bit.select(&temp, &accumulator)?;
322 multiple_of_power_of_two.double_in_place()?;
323 }
324 // Perform conditional subtraction:
325
326 // We can convert to projective safely because the result is guaranteed to be non-zero
327 // by the condition on `affine_bits.len()`, and by the fact that `accumulator` is non-zero
328 let result = accumulator.into_projective();
329 // If bits[0] is 0, then we have to subtract `self`; else, we subtract zero.
330 let subtrahend = bits[0].select(&Self::zero(), &initial_acc_value)?;
331 *mul_result += result - subtrahend;
332
333 // Now, let's finish off the rest of the bits using our complete formulae
334 for bit in proj_bits {
335 let temp = &*mul_result + &multiple_of_power_of_two.into_projective();
336 *mul_result = bit.select(&temp, &mul_result)?;
337 multiple_of_power_of_two.double_in_place()?;
338 }
339 Ok(())
340 }
341}
342
343impl<P, F> CurveVar<SWProjective<P>, <P::BaseField as Field>::BasePrimeField>
344 for ProjectiveVar<P, F>
345where
346 P: SWModelParameters,
347 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
348 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
349{
350 fn constant(g: SWProjective<P>) -> Self {
351 let cs = ConstraintSystemRef::None;
352 Self::new_variable_omit_on_curve_check(cs, || Ok(g), AllocationMode::Constant).unwrap()
353 }
354
355 fn zero() -> Self {
356 Self::new(F::zero(), F::one(), F::zero())
357 }
358
359 fn is_zero(&self) -> Result<Boolean<<P::BaseField as Field>::BasePrimeField>, SynthesisError> {
360 self.z.is_zero()
361 }
362
363 #[tracing::instrument(target = "r1cs", skip(cs, f))]
364 fn new_variable_omit_prime_order_check(
365 cs: impl Into<Namespace<<P::BaseField as Field>::BasePrimeField>>,
366 f: impl FnOnce() -> Result<SWProjective<P>, SynthesisError>,
367 mode: AllocationMode,
368 ) -> Result<Self, SynthesisError> {
369 let ns = cs.into();
370 let cs = ns.cs();
371 // Curve equation in projective form:
372 // E: Y² * Z = X³ + aX * Z² + bZ³
373 //
374 // This can be re-written as
375 // E: Y² * Z - bZ³ = X³ + aX * Z²
376 // E: Z * (Y² - bZ²) = X * (X² + aZ²)
377 // so, compute X², Y², Z²,
378 // compute temp = X * (X² + aZ²)
379 // check Z.mul_equals((Y² - bZ²), temp)
380 //
381 // A total of 5 multiplications
382
383 let g = Self::new_variable_omit_on_curve_check(cs, f, mode)?;
384
385 if mode != AllocationMode::Constant {
386 // Perform on-curve check.
387 let b = P::COEFF_B;
388 let a = P::COEFF_A;
389
390 let x2 = g.x.square()?;
391 let y2 = g.y.square()?;
392 let z2 = g.z.square()?;
393 let t = &g.x * (x2 + &z2 * a);
394
395 g.z.mul_equals(&(y2 - z2 * b), &t)?;
396 }
397 Ok(g)
398 }
399
400 /// Enforce that `self` is in the prime-order subgroup.
401 ///
402 /// Does so by multiplying by the prime order, and checking that the result
403 /// is unchanged.
404 // TODO: at the moment this doesn't work, because the addition and doubling
405 // formulae are incomplete for even-order points.
406 #[tracing::instrument(target = "r1cs")]
407 fn enforce_prime_order(&self) -> Result<(), SynthesisError> {
408 unimplemented!("cannot enforce prime order");
409 // let r_minus_1 = (-P::ScalarField::one()).into_repr();
410
411 // let mut result = Self::zero();
412 // for b in BitIteratorBE::without_leading_zeros(r_minus_1) {
413 // result.double_in_place()?;
414
415 // if b {
416 // result += self;
417 // }
418 // }
419 // self.negate()?.enforce_equal(&result)?;
420 // Ok(())
421 }
422
423 #[inline]
424 #[tracing::instrument(target = "r1cs")]
425 fn double_in_place(&mut self) -> Result<(), SynthesisError> {
426 // Complete doubling formula from Renes-Costello-Batina 2015
427 // Algorithm 3
428 // (https://eprint.iacr.org/2015/1060).
429 // Below, comments at the end of a line denote the corresponding
430 // step(s) of the algorithm
431 //
432 // Adapted from code in
433 // https://github.com/RustCrypto/elliptic-curves/blob/master/p256/src/arithmetic/projective.rs
434 let three_b = P::COEFF_B.double() + &P::COEFF_B;
435
436 let xx = self.x.square()?; // 1
437 let yy = self.y.square()?; // 2
438 let zz = self.z.square()?; // 3
439 let xy2 = (&self.x * &self.y).double()?; // 4, 5
440 let xz2 = (&self.x * &self.z).double()?; // 6, 7
441
442 let axz2 = mul_by_coeff_a::<P, F>(&xz2); // 8
443
444 let bzz3_part = &axz2 + &zz * three_b; // 9, 10
445 let yy_m_bzz3 = &yy - &bzz3_part; // 11
446 let yy_p_bzz3 = &yy + &bzz3_part; // 12
447 let y_frag = yy_p_bzz3 * &yy_m_bzz3; // 13
448 let x_frag = yy_m_bzz3 * &xy2; // 14
449
450 let bxz3 = xz2 * three_b; // 15
451 let azz = mul_by_coeff_a::<P, F>(&zz); // 16
452 let b3_xz_pairs = mul_by_coeff_a::<P, F>(&(&xx - &azz)) + &bxz3; // 15, 16, 17, 18, 19
453 let xx3_p_azz = (xx.double()? + &xx + &azz) * &b3_xz_pairs; // 23, 24, 25
454
455 let y = y_frag + &xx3_p_azz; // 26, 27
456 let yz2 = (&self.y * &self.z).double()?; // 28, 29
457 let x = x_frag - &(b3_xz_pairs * &yz2); // 30, 31
458 let z = (yz2 * &yy).double()?.double()?; // 32, 33, 34
459 self.x = x;
460 self.y = y;
461 self.z = z;
462 Ok(())
463 }
464
465 #[tracing::instrument(target = "r1cs")]
466 fn negate(&self) -> Result<Self, SynthesisError> {
467 Ok(Self::new(self.x.clone(), self.y.negate()?, self.z.clone()))
468 }
469
470 /// Computes `bits * self`, where `bits` is a little-endian
471 /// `Boolean` representation of a scalar.
472 #[tracing::instrument(target = "r1cs", skip(bits))]
473 fn scalar_mul_le<'a>(
474 &self,
475 bits: impl Iterator<Item = &'a Boolean<<P::BaseField as Field>::BasePrimeField>>,
476 ) -> Result<Self, SynthesisError> {
477 if self.is_constant() {
478 if self.value().unwrap().is_zero() {
479 return Ok(self.clone());
480 }
481 }
482 let self_affine = self.to_affine()?;
483 let (x, y, infinity) = (self_affine.x, self_affine.y, self_affine.infinity);
484 // We first handle the non-zero case, and then later
485 // will conditionally select zero if `self` was zero.
486 let non_zero_self = NonZeroAffineVar::new(x, y);
487
488 let bits = bits.collect::<Vec<_>>();
489 if bits.len() == 0 {
490 return Ok(Self::zero());
491 }
492 let scalar_modulus_bits = <<P::ScalarField as PrimeField>::Params>::MODULUS_BITS as usize;
493 let mut mul_result = Self::zero();
494 let mut power_of_two_times_self = non_zero_self;
495 // We chunk up `bits` into `p`-sized chunks.
496 for bits in bits.chunks(scalar_modulus_bits) {
497 self.fixed_scalar_mul_le(&mut mul_result, &mut power_of_two_times_self, bits)?;
498 }
499
500 // The foregoing algorithms rely on mixed/incomplete addition, and so do not
501 // work when the input (`self`) is zero. We hence have to perform
502 // a check to ensure that if the input is zero, then so is the output.
503 // The cost of this check should be less than the benefit of using
504 // mixed addition in almost all cases.
505 infinity.select(&Self::zero(), &mul_result)
506 }
507
508 #[tracing::instrument(target = "r1cs", skip(scalar_bits_with_bases))]
509 fn precomputed_base_scalar_mul_le<'a, I, B>(
510 &mut self,
511 scalar_bits_with_bases: I,
512 ) -> Result<(), SynthesisError>
513 where
514 I: Iterator<Item = (B, &'a SWProjective<P>)>,
515 B: Borrow<Boolean<<P::BaseField as Field>::BasePrimeField>>,
516 {
517 // We just ignore the provided bases and use the faster scalar multiplication.
518 let (bits, bases): (Vec<_>, Vec<_>) = scalar_bits_with_bases
519 .map(|(b, c)| (b.borrow().clone(), *c))
520 .unzip();
521 let base = bases[0];
522 *self = Self::constant(base).scalar_mul_le(bits.iter())?;
523 Ok(())
524 }
525}
526
527impl<P, F> ToConstraintFieldGadget<<P::BaseField as Field>::BasePrimeField> for ProjectiveVar<P, F>
528where
529 P: SWModelParameters,
530 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
531 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
532 F: ToConstraintFieldGadget<<P::BaseField as Field>::BasePrimeField>,
533{
534 fn to_constraint_field(
535 &self,
536 ) -> Result<Vec<FpVar<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
537 self.to_affine()?.to_constraint_field()
538 }
539}
540
541fn mul_by_coeff_a<
542 P: SWModelParameters,
543 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
544>(
545 f: &F,
546) -> F
547where
548 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
549{
550 if !P::COEFF_A.is_zero() {
551 f * P::COEFF_A
552 } else {
553 F::zero()
554 }
555}
556
557impl_bounded_ops!(
558 ProjectiveVar<P, F>,
559 SWProjective<P>,
560 Add,
561 add,
562 AddAssign,
563 add_assign,
564 |mut this: &'a ProjectiveVar<P, F>, mut other: &'a ProjectiveVar<P, F>| {
565 // Implement complete addition for Short Weierstrass curves, following
566 // the complete addition formula from Renes-Costello-Batina 2015
567 // (https://eprint.iacr.org/2015/1060).
568 //
569 // We special case handling of constants to get better constraint weight.
570 if this.is_constant() {
571 // we'll just act like `other` is constant.
572 core::mem::swap(&mut this, &mut other);
573 }
574
575 if other.is_constant() {
576 // The value should exist because `other` is a constant.
577 let other = other.value().unwrap();
578 if other.is_zero() {
579 // this + 0 = this
580 this.clone()
581 } else {
582 // We'll use mixed addition to add non-zero constants.
583 let x = F::constant(other.x);
584 let y = F::constant(other.y);
585 this.add_mixed(&NonZeroAffineVar::new(x, y)).unwrap()
586 }
587 } else {
588 // Complete addition formula from Renes-Costello-Batina 2015
589 // Algorithm 1
590 // (https://eprint.iacr.org/2015/1060).
591 // Below, comments at the end of a line denote the corresponding
592 // step(s) of the algorithm
593 //
594 // Adapted from code in
595 // https://github.com/RustCrypto/elliptic-curves/blob/master/p256/src/arithmetic/projective.rs
596 let three_b = P::COEFF_B.double() + &P::COEFF_B;
597 let (x1, y1, z1) = (&this.x, &this.y, &this.z);
598 let (x2, y2, z2) = (&other.x, &other.y, &other.z);
599
600 let xx = x1 * x2; // 1
601 let yy = y1 * y2; // 2
602 let zz = z1 * z2; // 3
603 let xy_pairs = ((x1 + y1) * &(x2 + y2)) - (&xx + &yy); // 4, 5, 6, 7, 8
604 let xz_pairs = ((x1 + z1) * &(x2 + z2)) - (&xx + &zz); // 9, 10, 11, 12, 13
605 let yz_pairs = ((y1 + z1) * &(y2 + z2)) - (&yy + &zz); // 14, 15, 16, 17, 18
606
607 let axz = mul_by_coeff_a::<P, F>(&xz_pairs); // 19
608
609 let bzz3_part = &axz + &zz * three_b; // 20, 21
610
611 let yy_m_bzz3 = &yy - &bzz3_part; // 22
612 let yy_p_bzz3 = &yy + &bzz3_part; // 23
613
614 let azz = mul_by_coeff_a::<P, F>(&zz);
615 let xx3_p_azz = xx.double().unwrap() + &xx + &azz; // 25, 26, 27, 29
616
617 let bxz3 = &xz_pairs * three_b; // 28
618 let b3_xz_pairs = mul_by_coeff_a::<P, F>(&(&xx - &azz)) + &bxz3; // 30, 31, 32
619
620 let x = (&yy_m_bzz3 * &xy_pairs) - &yz_pairs * &b3_xz_pairs; // 35, 39, 40
621 let y = (&yy_p_bzz3 * &yy_m_bzz3) + &xx3_p_azz * b3_xz_pairs; // 24, 36, 37, 38
622 let z = (&yy_p_bzz3 * &yz_pairs) + xy_pairs * xx3_p_azz; // 41, 42, 43
623
624 ProjectiveVar::new(x, y, z)
625 }
626
627 },
628 |this: &'a ProjectiveVar<P, F>, other: SWProjective<P>| {
629 this + ProjectiveVar::constant(other)
630 },
631 (F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>, P: SWModelParameters),
632 for <'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
633);
634
635impl_bounded_ops!(
636 ProjectiveVar<P, F>,
637 SWProjective<P>,
638 Sub,
639 sub,
640 SubAssign,
641 sub_assign,
642 |this: &'a ProjectiveVar<P, F>, other: &'a ProjectiveVar<P, F>| this + other.negate().unwrap(),
643 |this: &'a ProjectiveVar<P, F>, other: SWProjective<P>| this - ProjectiveVar::constant(other),
644 (F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>, P: SWModelParameters),
645 for <'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>
646);
647
648impl<'a, P, F> GroupOpsBounds<'a, SWProjective<P>, ProjectiveVar<P, F>> for ProjectiveVar<P, F>
649where
650 P: SWModelParameters,
651 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
652 for<'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
653{
654}
655
656impl<'a, P, F> GroupOpsBounds<'a, SWProjective<P>, ProjectiveVar<P, F>> for &'a ProjectiveVar<P, F>
657where
658 P: SWModelParameters,
659 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
660 for<'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
661{
662}
663
664impl<P, F> CondSelectGadget<<P::BaseField as Field>::BasePrimeField> for ProjectiveVar<P, F>
665where
666 P: SWModelParameters,
667 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
668 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
669{
670 #[inline]
671 #[tracing::instrument(target = "r1cs")]
672 fn conditionally_select(
673 cond: &Boolean<<P::BaseField as Field>::BasePrimeField>,
674 true_value: &Self,
675 false_value: &Self,
676 ) -> Result<Self, SynthesisError> {
677 let x = cond.select(&true_value.x, &false_value.x)?;
678 let y = cond.select(&true_value.y, &false_value.y)?;
679 let z = cond.select(&true_value.z, &false_value.z)?;
680
681 Ok(Self::new(x, y, z))
682 }
683}
684
685impl<P, F> EqGadget<<P::BaseField as Field>::BasePrimeField> for ProjectiveVar<P, F>
686where
687 P: SWModelParameters,
688 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
689 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
690{
691 #[tracing::instrument(target = "r1cs")]
692 fn is_eq(
693 &self,
694 other: &Self,
695 ) -> Result<Boolean<<P::BaseField as Field>::BasePrimeField>, SynthesisError> {
696 let x_equal = (&self.x * &other.z).is_eq(&(&other.x * &self.z))?;
697 let y_equal = (&self.y * &other.z).is_eq(&(&other.y * &self.z))?;
698 let coordinates_equal = x_equal.and(&y_equal)?;
699 let both_are_zero = self.is_zero()?.and(&other.is_zero()?)?;
700 both_are_zero.or(&coordinates_equal)
701 }
702
703 #[inline]
704 #[tracing::instrument(target = "r1cs")]
705 fn conditional_enforce_equal(
706 &self,
707 other: &Self,
708 condition: &Boolean<<P::BaseField as Field>::BasePrimeField>,
709 ) -> Result<(), SynthesisError> {
710 let x_equal = (&self.x * &other.z).is_eq(&(&other.x * &self.z))?;
711 let y_equal = (&self.y * &other.z).is_eq(&(&other.y * &self.z))?;
712 let coordinates_equal = x_equal.and(&y_equal)?;
713 let both_are_zero = self.is_zero()?.and(&other.is_zero()?)?;
714 both_are_zero
715 .or(&coordinates_equal)?
716 .conditional_enforce_equal(&Boolean::Constant(true), condition)?;
717 Ok(())
718 }
719
720 #[inline]
721 #[tracing::instrument(target = "r1cs")]
722 fn conditional_enforce_not_equal(
723 &self,
724 other: &Self,
725 condition: &Boolean<<P::BaseField as Field>::BasePrimeField>,
726 ) -> Result<(), SynthesisError> {
727 let is_equal = self.is_eq(other)?;
728 is_equal
729 .and(condition)?
730 .enforce_equal(&Boolean::Constant(false))
731 }
732}
733
734impl<P, F> AllocVar<SWAffine<P>, <P::BaseField as Field>::BasePrimeField> for ProjectiveVar<P, F>
735where
736 P: SWModelParameters,
737 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
738 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
739{
740 fn new_variable<T: Borrow<SWAffine<P>>>(
741 cs: impl Into<Namespace<<P::BaseField as Field>::BasePrimeField>>,
742 f: impl FnOnce() -> Result<T, SynthesisError>,
743 mode: AllocationMode,
744 ) -> Result<Self, SynthesisError> {
745 Self::new_variable(cs, || f().map(|b| b.borrow().into_projective()), mode)
746 }
747}
748
749impl<P, F> AllocVar<SWProjective<P>, <P::BaseField as Field>::BasePrimeField>
750 for ProjectiveVar<P, F>
751where
752 P: SWModelParameters,
753 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
754 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
755{
756 fn new_variable<T: Borrow<SWProjective<P>>>(
757 cs: impl Into<Namespace<<P::BaseField as Field>::BasePrimeField>>,
758 f: impl FnOnce() -> Result<T, SynthesisError>,
759 mode: AllocationMode,
760 ) -> Result<Self, SynthesisError> {
761 let ns = cs.into();
762 let cs = ns.cs();
763 let f = || Ok(*f()?.borrow());
764 match mode {
765 AllocationMode::Constant => Self::new_variable_omit_prime_order_check(cs, f, mode),
766 AllocationMode::Input => Self::new_variable_omit_prime_order_check(cs, f, mode),
767 AllocationMode::Witness => {
768 // if cofactor.is_even():
769 // divide until you've removed all even factors
770 // else:
771 // just directly use double and add.
772 let mut power_of_2: u32 = 0;
773 let mut cofactor = P::COFACTOR.to_vec();
774 while cofactor[0] % 2 == 0 {
775 div2(&mut cofactor);
776 power_of_2 += 1;
777 }
778
779 let cofactor_weight = BitIteratorBE::new(cofactor.as_slice())
780 .filter(|b| *b)
781 .count();
782 let modulus_minus_1 = (-P::ScalarField::one()).into_repr(); // r - 1
783 let modulus_minus_1_weight =
784 BitIteratorBE::new(modulus_minus_1).filter(|b| *b).count();
785
786 // We pick the most efficient method of performing the prime order check:
787 // If the cofactor has lower hamming weight than the scalar field's modulus,
788 // we first multiply by the inverse of the cofactor, and then, after allocating,
789 // multiply by the cofactor. This ensures the resulting point has no cofactors
790 //
791 // Else, we multiply by the scalar field's modulus and ensure that the result
792 // equals the identity.
793
794 let (mut ge, iter) = if cofactor_weight < modulus_minus_1_weight {
795 let ge = Self::new_variable_omit_prime_order_check(
796 ark_relations::ns!(cs, "Witness without subgroup check with cofactor mul"),
797 || f().map(|g| g.borrow().into_affine().mul_by_cofactor_inv().into()),
798 mode,
799 )?;
800 (
801 ge,
802 BitIteratorBE::without_leading_zeros(cofactor.as_slice()),
803 )
804 } else {
805 let ge = Self::new_variable_omit_prime_order_check(
806 ark_relations::ns!(cs, "Witness without subgroup check with `r` check"),
807 || {
808 f().map(|g| {
809 let g = g.into_affine();
810 let mut power_of_two = P::ScalarField::one().into_repr();
811 power_of_two.muln(power_of_2);
812 let power_of_two_inv = P::ScalarField::from_repr(power_of_two)
813 .and_then(|n| n.inverse())
814 .unwrap();
815 g.mul(power_of_two_inv)
816 })
817 },
818 mode,
819 )?;
820
821 (
822 ge,
823 BitIteratorBE::without_leading_zeros(modulus_minus_1.as_ref()),
824 )
825 };
826 // Remove the even part of the cofactor
827 for _ in 0..power_of_2 {
828 ge.double_in_place()?;
829 }
830
831 let mut result = Self::zero();
832 for b in iter {
833 result.double_in_place()?;
834
835 if b {
836 result += &ge
837 }
838 }
839 if cofactor_weight < modulus_minus_1_weight {
840 Ok(result)
841 } else {
842 ge.enforce_equal(&ge)?;
843 Ok(ge)
844 }
845 }
846 }
847 }
848}
849
850#[inline]
851fn div2(limbs: &mut [u64]) {
852 let mut t = 0;
853 for i in limbs.iter_mut().rev() {
854 let t2 = *i << 63;
855 *i >>= 1;
856 *i |= t;
857 t = t2;
858 }
859}
860
861impl<P, F> ToBitsGadget<<P::BaseField as Field>::BasePrimeField> for ProjectiveVar<P, F>
862where
863 P: SWModelParameters,
864 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
865 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
866{
867 #[tracing::instrument(target = "r1cs")]
868 fn to_bits_le(
869 &self,
870 ) -> Result<Vec<Boolean<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
871 let g = self.to_affine()?;
872 let mut bits = g.x.to_bits_le()?;
873 let y_bits = g.y.to_bits_le()?;
874 bits.extend_from_slice(&y_bits);
875 bits.push(g.infinity);
876 Ok(bits)
877 }
878
879 #[tracing::instrument(target = "r1cs")]
880 fn to_non_unique_bits_le(
881 &self,
882 ) -> Result<Vec<Boolean<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
883 let g = self.to_affine()?;
884 let mut bits = g.x.to_non_unique_bits_le()?;
885 let y_bits = g.y.to_non_unique_bits_le()?;
886 bits.extend_from_slice(&y_bits);
887 bits.push(g.infinity);
888 Ok(bits)
889 }
890}
891
892impl<P, F> ToBytesGadget<<P::BaseField as Field>::BasePrimeField> for ProjectiveVar<P, F>
893where
894 P: SWModelParameters,
895 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
896 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
897{
898 #[tracing::instrument(target = "r1cs")]
899 fn to_bytes(
900 &self,
901 ) -> Result<Vec<UInt8<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
902 let g = self.to_affine()?;
903 let mut bytes = g.x.to_bytes()?;
904 let y_bytes = g.y.to_bytes()?;
905 let inf_bytes = g.infinity.to_bytes()?;
906 bytes.extend_from_slice(&y_bytes);
907 bytes.extend_from_slice(&inf_bytes);
908 Ok(bytes)
909 }
910
911 #[tracing::instrument(target = "r1cs")]
912 fn to_non_unique_bytes(
913 &self,
914 ) -> Result<Vec<UInt8<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
915 let g = self.to_affine()?;
916 let mut bytes = g.x.to_non_unique_bytes()?;
917 let y_bytes = g.y.to_non_unique_bytes()?;
918 let inf_bytes = g.infinity.to_non_unique_bytes()?;
919 bytes.extend_from_slice(&y_bytes);
920 bytes.extend_from_slice(&inf_bytes);
921 Ok(bytes)
922 }
923}