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