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