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