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, 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>::size_in_bits();
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 if bit.is_constant() {
321 if *bit == &Boolean::TRUE {
322 accumulator = accumulator.add_unchecked(&multiple_of_power_of_two)?;
323 }
324 } else {
325 let temp = accumulator.add_unchecked(&multiple_of_power_of_two)?;
326 accumulator = bit.select(&temp, &accumulator)?;
327 }
328 multiple_of_power_of_two.double_in_place()?;
329 }
330 // Perform conditional subtraction:
331
332 // We can convert to projective safely because the result is guaranteed to be non-zero
333 // by the condition on `affine_bits.len()`, and by the fact that `accumulator` is non-zero
334 let result = accumulator.into_projective();
335 // If bits[0] is 0, then we have to subtract `self`; else, we subtract zero.
336 let subtrahend = bits[0].select(&Self::zero(), &initial_acc_value)?;
337 *mul_result += result - subtrahend;
338
339 // Now, let's finish off the rest of the bits using our complete formulae
340 for bit in proj_bits {
341 if bit.is_constant() {
342 if *bit == &Boolean::TRUE {
343 *mul_result += &multiple_of_power_of_two.into_projective();
344 }
345 } else {
346 let temp = &*mul_result + &multiple_of_power_of_two.into_projective();
347 *mul_result = bit.select(&temp, &mul_result)?;
348 }
349 multiple_of_power_of_two.double_in_place()?;
350 }
351 Ok(())
352 }
353}
354
355impl<P, F> CurveVar<SWProjective<P>, <P::BaseField as Field>::BasePrimeField>
356 for ProjectiveVar<P, F>
357where
358 P: SWModelParameters,
359 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
360 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
361{
362 fn constant(g: SWProjective<P>) -> Self {
363 let cs = ConstraintSystemRef::None;
364 Self::new_variable_omit_on_curve_check(cs, || Ok(g), AllocationMode::Constant).unwrap()
365 }
366
367 fn zero() -> Self {
368 Self::new(F::zero(), F::one(), F::zero())
369 }
370
371 fn is_zero(&self) -> Result<Boolean<<P::BaseField as Field>::BasePrimeField>, SynthesisError> {
372 self.z.is_zero()
373 }
374
375 #[tracing::instrument(target = "r1cs", skip(cs, f))]
376 fn new_variable_omit_prime_order_check(
377 cs: impl Into<Namespace<<P::BaseField as Field>::BasePrimeField>>,
378 f: impl FnOnce() -> Result<SWProjective<P>, SynthesisError>,
379 mode: AllocationMode,
380 ) -> Result<Self, SynthesisError> {
381 let ns = cs.into();
382 let cs = ns.cs();
383 // Curve equation in projective form:
384 // E: Y² * Z = X³ + aX * Z² + bZ³
385 //
386 // This can be re-written as
387 // E: Y² * Z - bZ³ = X³ + aX * Z²
388 // E: Z * (Y² - bZ²) = X * (X² + aZ²)
389 // so, compute X², Y², Z²,
390 // compute temp = X * (X² + aZ²)
391 // check Z.mul_equals((Y² - bZ²), temp)
392 //
393 // A total of 5 multiplications
394
395 let g = Self::new_variable_omit_on_curve_check(cs, f, mode)?;
396
397 if mode != AllocationMode::Constant {
398 // Perform on-curve check.
399 let b = P::COEFF_B;
400 let a = P::COEFF_A;
401
402 let x2 = g.x.square()?;
403 let y2 = g.y.square()?;
404 let z2 = g.z.square()?;
405 let t = &g.x * (x2 + &z2 * a);
406
407 g.z.mul_equals(&(y2 - z2 * b), &t)?;
408 }
409 Ok(g)
410 }
411
412 /// Enforce that `self` is in the prime-order subgroup.
413 ///
414 /// Does so by multiplying by the prime order, and checking that the result
415 /// is unchanged.
416 // TODO: at the moment this doesn't work, because the addition and doubling
417 // formulae are incomplete for even-order points.
418 #[tracing::instrument(target = "r1cs")]
419 fn enforce_prime_order(&self) -> Result<(), SynthesisError> {
420 unimplemented!("cannot enforce prime order");
421 // let r_minus_1 = (-P::ScalarField::one()).into_repr();
422
423 // let mut result = Self::zero();
424 // for b in BitIteratorBE::without_leading_zeros(r_minus_1) {
425 // result.double_in_place()?;
426
427 // if b {
428 // result += self;
429 // }
430 // }
431 // self.negate()?.enforce_equal(&result)?;
432 // Ok(())
433 }
434
435 #[inline]
436 #[tracing::instrument(target = "r1cs")]
437 fn double_in_place(&mut self) -> Result<(), SynthesisError> {
438 // Complete doubling formula from Renes-Costello-Batina 2015
439 // Algorithm 3
440 // (https://eprint.iacr.org/2015/1060).
441 // Below, comments at the end of a line denote the corresponding
442 // step(s) of the algorithm
443 //
444 // Adapted from code in
445 // https://github.com/RustCrypto/elliptic-curves/blob/master/p256/src/arithmetic/projective.rs
446 let three_b = P::COEFF_B.double() + &P::COEFF_B;
447
448 let xx = self.x.square()?; // 1
449 let yy = self.y.square()?; // 2
450 let zz = self.z.square()?; // 3
451 let xy2 = (&self.x * &self.y).double()?; // 4, 5
452 let xz2 = (&self.x * &self.z).double()?; // 6, 7
453
454 let axz2 = mul_by_coeff_a::<P, F>(&xz2); // 8
455
456 let bzz3_part = &axz2 + &zz * three_b; // 9, 10
457 let yy_m_bzz3 = &yy - &bzz3_part; // 11
458 let yy_p_bzz3 = &yy + &bzz3_part; // 12
459 let y_frag = yy_p_bzz3 * &yy_m_bzz3; // 13
460 let x_frag = yy_m_bzz3 * &xy2; // 14
461
462 let bxz3 = xz2 * three_b; // 15
463 let azz = mul_by_coeff_a::<P, F>(&zz); // 16
464 let b3_xz_pairs = mul_by_coeff_a::<P, F>(&(&xx - &azz)) + &bxz3; // 15, 16, 17, 18, 19
465 let xx3_p_azz = (xx.double()? + &xx + &azz) * &b3_xz_pairs; // 23, 24, 25
466
467 let y = y_frag + &xx3_p_azz; // 26, 27
468 let yz2 = (&self.y * &self.z).double()?; // 28, 29
469 let x = x_frag - &(b3_xz_pairs * &yz2); // 30, 31
470 let z = (yz2 * &yy).double()?.double()?; // 32, 33, 34
471 self.x = x;
472 self.y = y;
473 self.z = z;
474 Ok(())
475 }
476
477 #[tracing::instrument(target = "r1cs")]
478 fn negate(&self) -> Result<Self, SynthesisError> {
479 Ok(Self::new(self.x.clone(), self.y.negate()?, self.z.clone()))
480 }
481
482 /// Computes `bits * self`, where `bits` is a little-endian
483 /// `Boolean` representation of a scalar.
484 #[tracing::instrument(target = "r1cs", skip(bits))]
485 fn scalar_mul_le<'a>(
486 &self,
487 bits: impl Iterator<Item = &'a Boolean<<P::BaseField as Field>::BasePrimeField>>,
488 ) -> Result<Self, SynthesisError> {
489 if self.is_constant() {
490 if self.value().unwrap().is_zero() {
491 return Ok(self.clone());
492 }
493 }
494 let self_affine = self.to_affine()?;
495 let (x, y, infinity) = (self_affine.x, self_affine.y, self_affine.infinity);
496 // We first handle the non-zero case, and then later
497 // will conditionally select zero if `self` was zero.
498 let non_zero_self = NonZeroAffineVar::new(x, y);
499
500 let mut bits = bits.collect::<Vec<_>>();
501 if bits.len() == 0 {
502 return Ok(Self::zero());
503 }
504 // Remove unnecessary constant zeros in the most-significant positions.
505 bits = bits
506 .into_iter()
507 // We iterate from the MSB down.
508 .rev()
509 // Skip leading zeros, if they are constants.
510 .skip_while(|b| b.is_constant() && (b.value().unwrap() == false))
511 .collect();
512 // After collecting we are in big-endian form; we have to reverse to get back to
513 // little-endian.
514 bits.reverse();
515
516 let scalar_modulus_bits = <P::ScalarField as PrimeField>::size_in_bits();
517 let mut mul_result = Self::zero();
518 let mut power_of_two_times_self = non_zero_self;
519 // We chunk up `bits` into `p`-sized chunks.
520 for bits in bits.chunks(scalar_modulus_bits) {
521 self.fixed_scalar_mul_le(&mut mul_result, &mut power_of_two_times_self, bits)?;
522 }
523
524 // The foregoing algorithm relies on incomplete addition, and so does not
525 // work when the input (`self`) is zero. We hence have to perform
526 // a check to ensure that if the input is zero, then so is the output.
527 // The cost of this check should be less than the benefit of using
528 // mixed addition in almost all cases.
529 infinity.select(&Self::zero(), &mul_result)
530 }
531
532 #[tracing::instrument(target = "r1cs", skip(scalar_bits_with_bases))]
533 fn precomputed_base_scalar_mul_le<'a, I, B>(
534 &mut self,
535 scalar_bits_with_bases: I,
536 ) -> Result<(), SynthesisError>
537 where
538 I: Iterator<Item = (B, &'a SWProjective<P>)>,
539 B: Borrow<Boolean<<P::BaseField as Field>::BasePrimeField>>,
540 {
541 // We just ignore the provided bases and use the faster scalar multiplication.
542 let (bits, bases): (Vec<_>, Vec<_>) = scalar_bits_with_bases
543 .map(|(b, c)| (b.borrow().clone(), *c))
544 .unzip();
545 let base = bases[0];
546 *self = Self::constant(base).scalar_mul_le(bits.iter())?;
547 Ok(())
548 }
549}
550
551impl<P, F> ToConstraintFieldGadget<<P::BaseField as Field>::BasePrimeField> for ProjectiveVar<P, F>
552where
553 P: SWModelParameters,
554 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
555 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
556 F: ToConstraintFieldGadget<<P::BaseField as Field>::BasePrimeField>,
557{
558 fn to_constraint_field(
559 &self,
560 ) -> Result<Vec<FpVar<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
561 self.to_affine()?.to_constraint_field()
562 }
563}
564
565fn mul_by_coeff_a<
566 P: SWModelParameters,
567 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
568>(
569 f: &F,
570) -> F
571where
572 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
573{
574 if !P::COEFF_A.is_zero() {
575 f * P::COEFF_A
576 } else {
577 F::zero()
578 }
579}
580
581impl_bounded_ops!(
582 ProjectiveVar<P, F>,
583 SWProjective<P>,
584 Add,
585 add,
586 AddAssign,
587 add_assign,
588 |mut this: &'a ProjectiveVar<P, F>, mut other: &'a ProjectiveVar<P, F>| {
589 // Implement complete addition for Short Weierstrass curves, following
590 // the complete addition formula from Renes-Costello-Batina 2015
591 // (https://eprint.iacr.org/2015/1060).
592 //
593 // We special case handling of constants to get better constraint weight.
594 if this.is_constant() {
595 // we'll just act like `other` is constant.
596 core::mem::swap(&mut this, &mut other);
597 }
598
599 if other.is_constant() {
600 // The value should exist because `other` is a constant.
601 let other = other.value().unwrap();
602 if other.is_zero() {
603 // this + 0 = this
604 this.clone()
605 } else {
606 // We'll use mixed addition to add non-zero constants.
607 let x = F::constant(other.x);
608 let y = F::constant(other.y);
609 this.add_mixed(&NonZeroAffineVar::new(x, y)).unwrap()
610 }
611 } else {
612 // Complete addition formula from Renes-Costello-Batina 2015
613 // Algorithm 1
614 // (https://eprint.iacr.org/2015/1060).
615 // Below, comments at the end of a line denote the corresponding
616 // step(s) of the algorithm
617 //
618 // Adapted from code in
619 // https://github.com/RustCrypto/elliptic-curves/blob/master/p256/src/arithmetic/projective.rs
620 let three_b = P::COEFF_B.double() + &P::COEFF_B;
621 let (x1, y1, z1) = (&this.x, &this.y, &this.z);
622 let (x2, y2, z2) = (&other.x, &other.y, &other.z);
623
624 let xx = x1 * x2; // 1
625 let yy = y1 * y2; // 2
626 let zz = z1 * z2; // 3
627 let xy_pairs = ((x1 + y1) * &(x2 + y2)) - (&xx + &yy); // 4, 5, 6, 7, 8
628 let xz_pairs = ((x1 + z1) * &(x2 + z2)) - (&xx + &zz); // 9, 10, 11, 12, 13
629 let yz_pairs = ((y1 + z1) * &(y2 + z2)) - (&yy + &zz); // 14, 15, 16, 17, 18
630
631 let axz = mul_by_coeff_a::<P, F>(&xz_pairs); // 19
632
633 let bzz3_part = &axz + &zz * three_b; // 20, 21
634
635 let yy_m_bzz3 = &yy - &bzz3_part; // 22
636 let yy_p_bzz3 = &yy + &bzz3_part; // 23
637
638 let azz = mul_by_coeff_a::<P, F>(&zz);
639 let xx3_p_azz = xx.double().unwrap() + &xx + &azz; // 25, 26, 27, 29
640
641 let bxz3 = &xz_pairs * three_b; // 28
642 let b3_xz_pairs = mul_by_coeff_a::<P, F>(&(&xx - &azz)) + &bxz3; // 30, 31, 32
643
644 let x = (&yy_m_bzz3 * &xy_pairs) - &yz_pairs * &b3_xz_pairs; // 35, 39, 40
645 let y = (&yy_p_bzz3 * &yy_m_bzz3) + &xx3_p_azz * b3_xz_pairs; // 24, 36, 37, 38
646 let z = (&yy_p_bzz3 * &yz_pairs) + xy_pairs * xx3_p_azz; // 41, 42, 43
647
648 ProjectiveVar::new(x, y, z)
649 }
650
651 },
652 |this: &'a ProjectiveVar<P, F>, other: SWProjective<P>| {
653 this + ProjectiveVar::constant(other)
654 },
655 (F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>, P: SWModelParameters),
656 for <'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
657);
658
659impl_bounded_ops!(
660 ProjectiveVar<P, F>,
661 SWProjective<P>,
662 Sub,
663 sub,
664 SubAssign,
665 sub_assign,
666 |this: &'a ProjectiveVar<P, F>, other: &'a ProjectiveVar<P, F>| this + other.negate().unwrap(),
667 |this: &'a ProjectiveVar<P, F>, other: SWProjective<P>| this - ProjectiveVar::constant(other),
668 (F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>, P: SWModelParameters),
669 for <'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>
670);
671
672impl<'a, P, F> GroupOpsBounds<'a, SWProjective<P>, ProjectiveVar<P, F>> for ProjectiveVar<P, F>
673where
674 P: SWModelParameters,
675 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
676 for<'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
677{
678}
679
680impl<'a, P, F> GroupOpsBounds<'a, SWProjective<P>, ProjectiveVar<P, F>> for &'a ProjectiveVar<P, F>
681where
682 P: SWModelParameters,
683 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
684 for<'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
685{
686}
687
688impl<P, F> CondSelectGadget<<P::BaseField as Field>::BasePrimeField> for ProjectiveVar<P, F>
689where
690 P: SWModelParameters,
691 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
692 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
693{
694 #[inline]
695 #[tracing::instrument(target = "r1cs")]
696 fn conditionally_select(
697 cond: &Boolean<<P::BaseField as Field>::BasePrimeField>,
698 true_value: &Self,
699 false_value: &Self,
700 ) -> Result<Self, SynthesisError> {
701 let x = cond.select(&true_value.x, &false_value.x)?;
702 let y = cond.select(&true_value.y, &false_value.y)?;
703 let z = cond.select(&true_value.z, &false_value.z)?;
704
705 Ok(Self::new(x, y, z))
706 }
707}
708
709impl<P, F> EqGadget<<P::BaseField as Field>::BasePrimeField> for ProjectiveVar<P, F>
710where
711 P: SWModelParameters,
712 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
713 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
714{
715 #[tracing::instrument(target = "r1cs")]
716 fn is_eq(
717 &self,
718 other: &Self,
719 ) -> Result<Boolean<<P::BaseField as Field>::BasePrimeField>, SynthesisError> {
720 let x_equal = (&self.x * &other.z).is_eq(&(&other.x * &self.z))?;
721 let y_equal = (&self.y * &other.z).is_eq(&(&other.y * &self.z))?;
722 let coordinates_equal = x_equal.and(&y_equal)?;
723 let both_are_zero = self.is_zero()?.and(&other.is_zero()?)?;
724 both_are_zero.or(&coordinates_equal)
725 }
726
727 #[inline]
728 #[tracing::instrument(target = "r1cs")]
729 fn conditional_enforce_equal(
730 &self,
731 other: &Self,
732 condition: &Boolean<<P::BaseField as Field>::BasePrimeField>,
733 ) -> Result<(), SynthesisError> {
734 let x_equal = (&self.x * &other.z).is_eq(&(&other.x * &self.z))?;
735 let y_equal = (&self.y * &other.z).is_eq(&(&other.y * &self.z))?;
736 let coordinates_equal = x_equal.and(&y_equal)?;
737 let both_are_zero = self.is_zero()?.and(&other.is_zero()?)?;
738 both_are_zero
739 .or(&coordinates_equal)?
740 .conditional_enforce_equal(&Boolean::Constant(true), condition)?;
741 Ok(())
742 }
743
744 #[inline]
745 #[tracing::instrument(target = "r1cs")]
746 fn conditional_enforce_not_equal(
747 &self,
748 other: &Self,
749 condition: &Boolean<<P::BaseField as Field>::BasePrimeField>,
750 ) -> Result<(), SynthesisError> {
751 let is_equal = self.is_eq(other)?;
752 is_equal
753 .and(condition)?
754 .enforce_equal(&Boolean::Constant(false))
755 }
756}
757
758impl<P, F> AllocVar<SWAffine<P>, <P::BaseField as Field>::BasePrimeField> for ProjectiveVar<P, F>
759where
760 P: SWModelParameters,
761 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
762 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
763{
764 fn new_variable<T: Borrow<SWAffine<P>>>(
765 cs: impl Into<Namespace<<P::BaseField as Field>::BasePrimeField>>,
766 f: impl FnOnce() -> Result<T, SynthesisError>,
767 mode: AllocationMode,
768 ) -> Result<Self, SynthesisError> {
769 Self::new_variable(cs, || f().map(|b| b.borrow().into_projective()), mode)
770 }
771}
772
773impl<P, F> AllocVar<SWProjective<P>, <P::BaseField as Field>::BasePrimeField>
774 for ProjectiveVar<P, F>
775where
776 P: SWModelParameters,
777 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
778 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
779{
780 fn new_variable<T: Borrow<SWProjective<P>>>(
781 cs: impl Into<Namespace<<P::BaseField as Field>::BasePrimeField>>,
782 f: impl FnOnce() -> Result<T, SynthesisError>,
783 mode: AllocationMode,
784 ) -> Result<Self, SynthesisError> {
785 let ns = cs.into();
786 let cs = ns.cs();
787 let f = || Ok(*f()?.borrow());
788 match mode {
789 AllocationMode::Constant => Self::new_variable_omit_prime_order_check(cs, f, mode),
790 AllocationMode::Input => Self::new_variable_omit_prime_order_check(cs, f, mode),
791 AllocationMode::Witness => {
792 // if cofactor.is_even():
793 // divide until you've removed all even factors
794 // else:
795 // just directly use double and add.
796 let mut power_of_2: u32 = 0;
797 let mut cofactor = P::COFACTOR.to_vec();
798 while cofactor[0] % 2 == 0 {
799 div2(&mut cofactor);
800 power_of_2 += 1;
801 }
802
803 let cofactor_weight = BitIteratorBE::new(cofactor.as_slice())
804 .filter(|b| *b)
805 .count();
806 let modulus_minus_1 = (-P::ScalarField::one()).into_repr(); // r - 1
807 let modulus_minus_1_weight =
808 BitIteratorBE::new(modulus_minus_1).filter(|b| *b).count();
809
810 // We pick the most efficient method of performing the prime order check:
811 // If the cofactor has lower hamming weight than the scalar field's modulus,
812 // we first multiply by the inverse of the cofactor, and then, after allocating,
813 // multiply by the cofactor. This ensures the resulting point has no cofactors
814 //
815 // Else, we multiply by the scalar field's modulus and ensure that the result
816 // equals the identity.
817
818 let (mut ge, iter) = if cofactor_weight < modulus_minus_1_weight {
819 let ge = Self::new_variable_omit_prime_order_check(
820 ark_relations::ns!(cs, "Witness without subgroup check with cofactor mul"),
821 || f().map(|g| g.borrow().into_affine().mul_by_cofactor_inv().into()),
822 mode,
823 )?;
824 (
825 ge,
826 BitIteratorBE::without_leading_zeros(cofactor.as_slice()),
827 )
828 } else {
829 let ge = Self::new_variable_omit_prime_order_check(
830 ark_relations::ns!(cs, "Witness without subgroup check with `r` check"),
831 || {
832 f().map(|g| {
833 let g = g.into_affine();
834 let mut power_of_two = P::ScalarField::one().into_repr();
835 power_of_two.muln(power_of_2);
836 let power_of_two_inv = P::ScalarField::from_repr(power_of_two)
837 .and_then(|n| n.inverse())
838 .unwrap();
839 g.mul(power_of_two_inv)
840 })
841 },
842 mode,
843 )?;
844
845 (
846 ge,
847 BitIteratorBE::without_leading_zeros(modulus_minus_1.as_ref()),
848 )
849 };
850 // Remove the even part of the cofactor
851 for _ in 0..power_of_2 {
852 ge.double_in_place()?;
853 }
854
855 let mut result = Self::zero();
856 for b in iter {
857 result.double_in_place()?;
858
859 if b {
860 result += &ge
861 }
862 }
863 if cofactor_weight < modulus_minus_1_weight {
864 Ok(result)
865 } else {
866 ge.enforce_equal(&ge)?;
867 Ok(ge)
868 }
869 }
870 }
871 }
872}
873
874#[inline]
875fn div2(limbs: &mut [u64]) {
876 let mut t = 0;
877 for i in limbs.iter_mut().rev() {
878 let t2 = *i << 63;
879 *i >>= 1;
880 *i |= t;
881 t = t2;
882 }
883}
884
885impl<P, F> ToBitsGadget<<P::BaseField as Field>::BasePrimeField> for ProjectiveVar<P, F>
886where
887 P: SWModelParameters,
888 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
889 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
890{
891 #[tracing::instrument(target = "r1cs")]
892 fn to_bits_le(
893 &self,
894 ) -> Result<Vec<Boolean<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
895 let g = self.to_affine()?;
896 let mut bits = g.x.to_bits_le()?;
897 let y_bits = g.y.to_bits_le()?;
898 bits.extend_from_slice(&y_bits);
899 bits.push(g.infinity);
900 Ok(bits)
901 }
902
903 #[tracing::instrument(target = "r1cs")]
904 fn to_non_unique_bits_le(
905 &self,
906 ) -> Result<Vec<Boolean<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
907 let g = self.to_affine()?;
908 let mut bits = g.x.to_non_unique_bits_le()?;
909 let y_bits = g.y.to_non_unique_bits_le()?;
910 bits.extend_from_slice(&y_bits);
911 bits.push(g.infinity);
912 Ok(bits)
913 }
914}
915
916impl<P, F> ToBytesGadget<<P::BaseField as Field>::BasePrimeField> for ProjectiveVar<P, F>
917where
918 P: SWModelParameters,
919 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
920 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
921{
922 #[tracing::instrument(target = "r1cs")]
923 fn to_bytes(
924 &self,
925 ) -> Result<Vec<UInt8<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
926 let g = self.to_affine()?;
927 let mut bytes = g.x.to_bytes()?;
928 let y_bytes = g.y.to_bytes()?;
929 let inf_bytes = g.infinity.to_bytes()?;
930 bytes.extend_from_slice(&y_bytes);
931 bytes.extend_from_slice(&inf_bytes);
932 Ok(bytes)
933 }
934
935 #[tracing::instrument(target = "r1cs")]
936 fn to_non_unique_bytes(
937 &self,
938 ) -> Result<Vec<UInt8<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
939 let g = self.to_affine()?;
940 let mut bytes = g.x.to_non_unique_bytes()?;
941 let y_bytes = g.y.to_non_unique_bytes()?;
942 let inf_bytes = g.infinity.to_non_unique_bytes()?;
943 bytes.extend_from_slice(&y_bytes);
944 bytes.extend_from_slice(&inf_bytes);
945 Ok(bytes)
946 }
947}