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