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