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