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
226impl<P, F> CurveVar<SWProjective<P>, <P::BaseField as Field>::BasePrimeField>
227 for ProjectiveVar<P, F>
228where
229 P: SWModelParameters,
230 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
231 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
232{
233 fn constant(g: SWProjective<P>) -> Self {
234 let cs = ConstraintSystemRef::None;
235 Self::new_variable_omit_on_curve_check(cs, || Ok(g), AllocationMode::Constant).unwrap()
236 }
237
238 fn zero() -> Self {
239 Self::new(F::zero(), F::one(), F::zero())
240 }
241
242 fn is_zero(&self) -> Result<Boolean<<P::BaseField as Field>::BasePrimeField>, SynthesisError> {
243 self.z.is_zero()
244 }
245
246 #[tracing::instrument(target = "r1cs", skip(cs, f))]
247 fn new_variable_omit_prime_order_check(
248 cs: impl Into<Namespace<<P::BaseField as Field>::BasePrimeField>>,
249 f: impl FnOnce() -> Result<SWProjective<P>, SynthesisError>,
250 mode: AllocationMode,
251 ) -> Result<Self, SynthesisError> {
252 let ns = cs.into();
253 let cs = ns.cs();
254 // Curve equation in projective form:
255 // E: Y² * Z = X³ + aX * Z² + bZ³
256 //
257 // This can be re-written as
258 // E: Y² * Z - bZ³ = X³ + aX * Z²
259 // E: Z * (Y² - bZ²) = X * (X² + aZ²)
260 // so, compute X², Y², Z²,
261 // compute temp = X * (X² + aZ²)
262 // check Z.mul_equals((Y² - bZ²), temp)
263 //
264 // A total of 5 multiplications
265
266 let g = Self::new_variable_omit_on_curve_check(cs, f, mode)?;
267
268 if mode != AllocationMode::Constant {
269 // Perform on-curve check.
270 let b = P::COEFF_B;
271 let a = P::COEFF_A;
272
273 let x2 = g.x.square()?;
274 let y2 = g.y.square()?;
275 let z2 = g.z.square()?;
276 let t = &g.x * (x2 + &z2 * a);
277
278 g.z.mul_equals(&(y2 - z2 * b), &t)?;
279 }
280 Ok(g)
281 }
282
283 /// Enforce that `self` is in the prime-order subgroup.
284 ///
285 /// Does so by multiplying by the prime order, and checking that the result
286 /// is unchanged.
287 // TODO: at the moment this doesn't work, because the addition and doubling
288 // formulae are incomplete for even-order points.
289 #[tracing::instrument(target = "r1cs")]
290 fn enforce_prime_order(&self) -> Result<(), SynthesisError> {
291 let r_minus_1 = (-P::ScalarField::one()).into_repr();
292
293 let mut result = Self::zero();
294 for b in BitIteratorBE::without_leading_zeros(r_minus_1) {
295 result.double_in_place()?;
296
297 if b {
298 result += self;
299 }
300 }
301 self.negate()?.enforce_equal(&result)?;
302 Ok(())
303 }
304
305 #[inline]
306 #[tracing::instrument(target = "r1cs")]
307 fn double_in_place(&mut self) -> Result<(), SynthesisError> {
308 // Complete doubling formula from Renes-Costello-Batina 2015
309 // Algorithm 3
310 // (https://eprint.iacr.org/2015/1060).
311 //
312 // Adapted from code in
313 // https://github.com/RustCrypto/elliptic-curves/blob/master/p256/src/arithmetic.rs
314 let three_b = P::COEFF_B.double() + &P::COEFF_B;
315
316 let xx = self.x.square()?; // 1
317 let yy = self.y.square()?; // 2
318 let zz = self.z.square()?; // 3
319 let xy2 = (&self.x * &self.y).double()?; // 4, 5
320 let xz2 = (&self.x * &self.z).double()?; // 6, 7
321
322 let axz2 = mul_by_coeff_a::<P, F>(&xz2); // 8
323
324 let bzz3_part = &axz2 + &zz * three_b; // 9, 10
325 let yy_m_bzz3 = &yy - &bzz3_part; // 11
326 let yy_p_bzz3 = &yy + &bzz3_part; // 12
327 let y_frag = yy_p_bzz3 * &yy_m_bzz3; // 13
328 let x_frag = yy_m_bzz3 * &xy2; // 14
329
330 let bxz3 = xz2 * three_b; // 15
331 let azz = mul_by_coeff_a::<P, F>(&zz); // 16
332 let b3_xz_pairs = mul_by_coeff_a::<P, F>(&(&xx - &azz)) + &bxz3; // 15, 16, 17, 18, 19
333 let xx3_p_azz = (xx.double()? + &xx + &azz) * &b3_xz_pairs; // 23, 24, 25
334
335 let y = y_frag + &xx3_p_azz; // 26, 27
336 let yz2 = (&self.y * &self.z).double()?; // 28, 29
337 let x = x_frag - &(b3_xz_pairs * &yz2); // 30, 31
338 let z = (yz2 * &yy).double()?.double()?; // 32, 33, 34
339 self.x = x;
340 self.y = y;
341 self.z = z;
342 Ok(())
343 }
344
345 #[tracing::instrument(target = "r1cs")]
346 fn negate(&self) -> Result<Self, SynthesisError> {
347 Ok(Self::new(self.x.clone(), self.y.negate()?, self.z.clone()))
348 }
349}
350
351impl<P, F> ToConstraintFieldGadget<<P::BaseField as Field>::BasePrimeField> for ProjectiveVar<P, F>
352where
353 P: SWModelParameters,
354 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
355 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
356 F: ToConstraintFieldGadget<<P::BaseField as Field>::BasePrimeField>,
357{
358 fn to_constraint_field(
359 &self,
360 ) -> Result<Vec<FpVar<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
361 self.to_affine()?.to_constraint_field()
362 }
363}
364
365fn mul_by_coeff_a<
366 P: SWModelParameters,
367 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
368>(
369 f: &F,
370) -> F
371where
372 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
373{
374 if !P::COEFF_A.is_zero() {
375 f * P::COEFF_A
376 } else {
377 F::zero()
378 }
379}
380
381impl_bounded_ops!(
382 ProjectiveVar<P, F>,
383 SWProjective<P>,
384 Add,
385 add,
386 AddAssign,
387 add_assign,
388 |this: &'a ProjectiveVar<P, F>, other: &'a ProjectiveVar<P, F>| {
389 // Complete addition formula from Renes-Costello-Batina 2015
390 // Algorithm 1
391 // (https://eprint.iacr.org/2015/1060).
392 //
393 // Adapted from code in
394 // https://github.com/RustCrypto/elliptic-curves/blob/master/p256/src/arithmetic.rs
395
396 let three_b = P::COEFF_B.double() + &P::COEFF_B;
397
398 let xx = &this.x * &other.x; // 1
399 let yy = &this.y * &other.y; // 2
400 let zz = &this.z * &other.z; // 3
401 let xy_pairs = ((&this.x + &this.y) * &(&other.x + &other.y)) - (&xx + &yy); // 4, 5, 6, 7, 8
402 let xz_pairs = ((&this.x + &this.z) * &(&other.x + &other.z)) - (&xx + &zz); // 9, 10, 11, 12, 13
403 let yz_pairs = ((&this.y + &this.z) * &(&other.y + &other.z)) - (&yy + &zz); // 14, 15, 16, 17, 18
404
405 let axz = mul_by_coeff_a::<P, F>(&xz_pairs); // 19
406
407 let bzz3_part = &axz + &zz * three_b; // 20, 21
408
409 let yy_m_bzz3 = &yy - &bzz3_part; // 22
410 let yy_p_bzz3 = &yy + &bzz3_part; // 23
411
412 let azz = mul_by_coeff_a::<P, F>(&zz);
413 let xx3_p_azz = xx.double().unwrap() + &xx + &azz; // 25, 26, 27, 29
414
415 let bxz3 = &xz_pairs * three_b; // 28
416 let b3_xz_pairs = mul_by_coeff_a::<P, F>(&(&xx - &azz)) + &bxz3; // 30, 31, 32
417
418 let x = (&yy_m_bzz3 * &xy_pairs) - &yz_pairs * &b3_xz_pairs; // 35, 39, 40
419 let y = (&yy_p_bzz3 * &yy_m_bzz3) + &xx3_p_azz * b3_xz_pairs; // 24, 36, 37, 38
420 let z = (&yy_p_bzz3 * &yz_pairs) + xy_pairs * xx3_p_azz; // 41, 42, 43
421
422 ProjectiveVar::new(x, y, z)
423 },
424 |this: &'a ProjectiveVar<P, F>, other: SWProjective<P>| {
425 this + ProjectiveVar::constant(other)
426 },
427 (F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>, P: SWModelParameters),
428 for <'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
429);
430
431impl_bounded_ops!(
432 ProjectiveVar<P, F>,
433 SWProjective<P>,
434 Sub,
435 sub,
436 SubAssign,
437 sub_assign,
438 |this: &'a ProjectiveVar<P, F>, other: &'a ProjectiveVar<P, F>| this + other.negate().unwrap(),
439 |this: &'a ProjectiveVar<P, F>, other: SWProjective<P>| this - ProjectiveVar::constant(other),
440 (F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>, P: SWModelParameters),
441 for <'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>
442);
443
444impl<'a, P, F> GroupOpsBounds<'a, SWProjective<P>, ProjectiveVar<P, F>> for ProjectiveVar<P, F>
445where
446 P: SWModelParameters,
447 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
448 for<'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
449{
450}
451
452impl<'a, P, F> GroupOpsBounds<'a, SWProjective<P>, ProjectiveVar<P, F>> for &'a ProjectiveVar<P, F>
453where
454 P: SWModelParameters,
455 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
456 for<'b> &'b F: FieldOpsBounds<'b, P::BaseField, F>,
457{
458}
459
460impl<P, F> CondSelectGadget<<P::BaseField as Field>::BasePrimeField> for ProjectiveVar<P, F>
461where
462 P: SWModelParameters,
463 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
464 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
465{
466 #[inline]
467 #[tracing::instrument(target = "r1cs")]
468 fn conditionally_select(
469 cond: &Boolean<<P::BaseField as Field>::BasePrimeField>,
470 true_value: &Self,
471 false_value: &Self,
472 ) -> Result<Self, SynthesisError> {
473 let x = cond.select(&true_value.x, &false_value.x)?;
474 let y = cond.select(&true_value.y, &false_value.y)?;
475 let z = cond.select(&true_value.z, &false_value.z)?;
476
477 Ok(Self::new(x, y, z))
478 }
479}
480
481impl<P, F> EqGadget<<P::BaseField as Field>::BasePrimeField> for ProjectiveVar<P, F>
482where
483 P: SWModelParameters,
484 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
485 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
486{
487 #[tracing::instrument(target = "r1cs")]
488 fn is_eq(
489 &self,
490 other: &Self,
491 ) -> Result<Boolean<<P::BaseField as Field>::BasePrimeField>, SynthesisError> {
492 let x_equal = (&self.x * &other.z).is_eq(&(&other.x * &self.z))?;
493 let y_equal = (&self.y * &other.z).is_eq(&(&other.y * &self.z))?;
494 let coordinates_equal = x_equal.and(&y_equal)?;
495 let both_are_zero = self.is_zero()?.and(&other.is_zero()?)?;
496 both_are_zero.or(&coordinates_equal)
497 }
498
499 #[inline]
500 #[tracing::instrument(target = "r1cs")]
501 fn conditional_enforce_equal(
502 &self,
503 other: &Self,
504 condition: &Boolean<<P::BaseField as Field>::BasePrimeField>,
505 ) -> Result<(), SynthesisError> {
506 let x_equal = (&self.x * &other.z).is_eq(&(&other.x * &self.z))?;
507 let y_equal = (&self.y * &other.z).is_eq(&(&other.y * &self.z))?;
508 let coordinates_equal = x_equal.and(&y_equal)?;
509 let both_are_zero = self.is_zero()?.and(&other.is_zero()?)?;
510 both_are_zero
511 .or(&coordinates_equal)?
512 .conditional_enforce_equal(&Boolean::Constant(true), condition)?;
513 Ok(())
514 }
515
516 #[inline]
517 #[tracing::instrument(target = "r1cs")]
518 fn conditional_enforce_not_equal(
519 &self,
520 other: &Self,
521 condition: &Boolean<<P::BaseField as Field>::BasePrimeField>,
522 ) -> Result<(), SynthesisError> {
523 let is_equal = self.is_eq(other)?;
524 is_equal
525 .and(condition)?
526 .enforce_equal(&Boolean::Constant(false))
527 }
528}
529
530impl<P, F> AllocVar<SWAffine<P>, <P::BaseField as Field>::BasePrimeField> for ProjectiveVar<P, F>
531where
532 P: SWModelParameters,
533 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
534 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
535{
536 fn new_variable<T: Borrow<SWAffine<P>>>(
537 cs: impl Into<Namespace<<P::BaseField as Field>::BasePrimeField>>,
538 f: impl FnOnce() -> Result<T, SynthesisError>,
539 mode: AllocationMode,
540 ) -> Result<Self, SynthesisError> {
541 Self::new_variable(cs, || f().map(|b| b.borrow().into_projective()), mode)
542 }
543}
544
545impl<P, F> AllocVar<SWProjective<P>, <P::BaseField as Field>::BasePrimeField>
546 for ProjectiveVar<P, F>
547where
548 P: SWModelParameters,
549 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
550 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
551{
552 fn new_variable<T: Borrow<SWProjective<P>>>(
553 cs: impl Into<Namespace<<P::BaseField as Field>::BasePrimeField>>,
554 f: impl FnOnce() -> Result<T, SynthesisError>,
555 mode: AllocationMode,
556 ) -> Result<Self, SynthesisError> {
557 let ns = cs.into();
558 let cs = ns.cs();
559 let f = || Ok(*f()?.borrow());
560 match mode {
561 AllocationMode::Constant => Self::new_variable_omit_prime_order_check(cs, f, mode),
562 AllocationMode::Input => Self::new_variable_omit_prime_order_check(cs, f, mode),
563 AllocationMode::Witness => {
564 // if cofactor.is_even():
565 // divide until you've removed all even factors
566 // else:
567 // just directly use double and add.
568 let mut power_of_2: u32 = 0;
569 let mut cofactor = P::COFACTOR.to_vec();
570 while cofactor[0] % 2 == 0 {
571 div2(&mut cofactor);
572 power_of_2 += 1;
573 }
574
575 let cofactor_weight = BitIteratorBE::new(cofactor.as_slice())
576 .filter(|b| *b)
577 .count();
578 let modulus_minus_1 = (-P::ScalarField::one()).into_repr(); // r - 1
579 let modulus_minus_1_weight =
580 BitIteratorBE::new(modulus_minus_1).filter(|b| *b).count();
581
582 // We pick the most efficient method of performing the prime order check:
583 // If the cofactor has lower hamming weight than the scalar field's modulus,
584 // we first multiply by the inverse of the cofactor, and then, after allocating,
585 // multiply by the cofactor. This ensures the resulting point has no cofactors
586 //
587 // Else, we multiply by the scalar field's modulus and ensure that the result
588 // equals the identity.
589
590 let (mut ge, iter) = if cofactor_weight < modulus_minus_1_weight {
591 let ge = Self::new_variable_omit_prime_order_check(
592 ark_relations::ns!(cs, "Witness without subgroup check with cofactor mul"),
593 || f().map(|g| g.borrow().into_affine().mul_by_cofactor_inv().into()),
594 mode,
595 )?;
596 (
597 ge,
598 BitIteratorBE::without_leading_zeros(cofactor.as_slice()),
599 )
600 } else {
601 let ge = Self::new_variable_omit_prime_order_check(
602 ark_relations::ns!(cs, "Witness without subgroup check with `r` check"),
603 || {
604 f().map(|g| {
605 let g = g.into_affine();
606 let mut power_of_two = P::ScalarField::one().into_repr();
607 power_of_two.muln(power_of_2);
608 let power_of_two_inv = P::ScalarField::from_repr(power_of_two)
609 .and_then(|n| n.inverse())
610 .unwrap();
611 g.mul(power_of_two_inv)
612 })
613 },
614 mode,
615 )?;
616
617 (
618 ge,
619 BitIteratorBE::without_leading_zeros(modulus_minus_1.as_ref()),
620 )
621 };
622 // Remove the even part of the cofactor
623 for _ in 0..power_of_2 {
624 ge.double_in_place()?;
625 }
626
627 let mut result = Self::zero();
628 for b in iter {
629 result.double_in_place()?;
630
631 if b {
632 result += &ge
633 }
634 }
635 if cofactor_weight < modulus_minus_1_weight {
636 Ok(result)
637 } else {
638 ge.enforce_equal(&ge)?;
639 Ok(ge)
640 }
641 }
642 }
643 }
644}
645
646#[inline]
647fn div2(limbs: &mut [u64]) {
648 let mut t = 0;
649 for i in limbs.iter_mut().rev() {
650 let t2 = *i << 63;
651 *i >>= 1;
652 *i |= t;
653 t = t2;
654 }
655}
656
657impl<P, F> ToBitsGadget<<P::BaseField as Field>::BasePrimeField> for ProjectiveVar<P, F>
658where
659 P: SWModelParameters,
660 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
661 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
662{
663 #[tracing::instrument(target = "r1cs")]
664 fn to_bits_le(
665 &self,
666 ) -> Result<Vec<Boolean<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
667 let g = self.to_affine()?;
668 let mut bits = g.x.to_bits_le()?;
669 let y_bits = g.y.to_bits_le()?;
670 bits.extend_from_slice(&y_bits);
671 bits.push(g.infinity);
672 Ok(bits)
673 }
674
675 #[tracing::instrument(target = "r1cs")]
676 fn to_non_unique_bits_le(
677 &self,
678 ) -> Result<Vec<Boolean<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
679 let g = self.to_affine()?;
680 let mut bits = g.x.to_non_unique_bits_le()?;
681 let y_bits = g.y.to_non_unique_bits_le()?;
682 bits.extend_from_slice(&y_bits);
683 bits.push(g.infinity);
684 Ok(bits)
685 }
686}
687
688impl<P, F> ToBytesGadget<<P::BaseField as Field>::BasePrimeField> for ProjectiveVar<P, F>
689where
690 P: SWModelParameters,
691 F: FieldVar<P::BaseField, <P::BaseField as Field>::BasePrimeField>,
692 for<'a> &'a F: FieldOpsBounds<'a, P::BaseField, F>,
693{
694 #[tracing::instrument(target = "r1cs")]
695 fn to_bytes(
696 &self,
697 ) -> Result<Vec<UInt8<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
698 let g = self.to_affine()?;
699 let mut bytes = g.x.to_bytes()?;
700 let y_bytes = g.y.to_bytes()?;
701 let inf_bytes = g.infinity.to_bytes()?;
702 bytes.extend_from_slice(&y_bytes);
703 bytes.extend_from_slice(&inf_bytes);
704 Ok(bytes)
705 }
706
707 #[tracing::instrument(target = "r1cs")]
708 fn to_non_unique_bytes(
709 &self,
710 ) -> Result<Vec<UInt8<<P::BaseField as Field>::BasePrimeField>>, SynthesisError> {
711 let g = self.to_affine()?;
712 let mut bytes = g.x.to_non_unique_bytes()?;
713 let y_bytes = g.y.to_non_unique_bytes()?;
714 let inf_bytes = g.infinity.to_non_unique_bytes()?;
715 bytes.extend_from_slice(&y_bytes);
716 bytes.extend_from_slice(&inf_bytes);
717 Ok(bytes)
718 }
719}