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