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