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