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