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