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, BitIterator, Field, One, PrimeField, ProjectiveCurve, Zero,
7};
8use core::{borrow::Borrow, marker::PhantomData, ops::Neg};
9use r1cs_core::{ConstraintSystem, SynthesisError};
10
11use crate::{prelude::*, Assignment, Vec};
12
13pub mod bls12;
14pub mod mnt4;
15pub mod mnt6;
16
17#[derive(Derivative)]
18#[derivative(Debug, Clone)]
19#[must_use]
20pub struct AffineGadget<
21 P: SWModelParameters,
22 ConstraintF: Field,
23 F: FieldGadget<P::BaseField, ConstraintF>,
24> {
25 pub x: F,
26 pub y: F,
27 pub infinity: Boolean,
28 _params: PhantomData<P>,
29 _engine: PhantomData<ConstraintF>,
30}
31
32impl<P: SWModelParameters, ConstraintF: Field, F: FieldGadget<P::BaseField, ConstraintF>>
33 AffineGadget<P, ConstraintF, F>
34{
35 pub fn new(x: F, y: F, infinity: Boolean) -> Self {
36 Self {
37 x,
38 y,
39 infinity,
40 _params: PhantomData,
41 _engine: PhantomData,
42 }
43 }
44
45 pub fn alloc_without_check<FN, CS: ConstraintSystem<ConstraintF>>(
46 mut cs: CS,
47 value_gen: F,
48 ) -> Result<Self, SynthesisError>
49 where
50 F: FnOnce() -> Result<SWProjective<P>, SynthesisError>,
51 {
52 let (x, y, infinity) = match value_gen() {
53 Ok(ge) => {
54 let ge = ge.into_affine();
55 (Ok(ge.x), Ok(ge.y), Ok(ge.infinity))
56 }
57 _ => (
58 Err(SynthesisError::AssignmentMissing),
59 Err(SynthesisError::AssignmentMissing),
60 Err(SynthesisError::AssignmentMissing),
61 ),
62 };
63
64 let x = F::alloc(&mut cs.ns(|| "x"), || x)?;
65 let y = F::alloc(&mut cs.ns(|| "y"), || y)?;
66 let infinity = Boolean::alloc(&mut cs.ns(|| "infinity"), || infinity)?;
67
68 Ok(Self::new(x, y, infinity))
69 }
70}
71
72impl<P, ConstraintF, F> PartialEq for AffineGadget<P, ConstraintF, F>
73where
74 P: SWModelParameters,
75 ConstraintF: Field,
76 F: FieldGadget<P::BaseField, ConstraintF>,
77{
78 fn eq(&self, other: &Self) -> bool {
79 self.x == other.x && self.y == other.y
80 }
81}
82
83impl<P, ConstraintF, F> Eq for AffineGadget<P, ConstraintF, F>
84where
85 P: SWModelParameters,
86 ConstraintF: Field,
87 F: FieldGadget<P::BaseField, ConstraintF>,
88{
89}
90
91impl<P, ConstraintF, F> GroupGadget<SWProjective<P>, ConstraintF>
92 for AffineGadget<P, ConstraintF, F>
93where
94 P: SWModelParameters,
95 ConstraintF: PrimeField,
96 F: FieldGadget<P::BaseField, ConstraintF>,
97{
98 type Value = SWProjective<P>;
99 type Variable = (F::Variable, F::Variable);
100
101 #[inline]
102 fn get_value(&self) -> Option<Self::Value> {
103 match (
104 self.x.get_value(),
105 self.y.get_value(),
106 self.infinity.get_value(),
107 ) {
108 (Some(x), Some(y), Some(infinity)) => {
109 Some(SWAffine::new(x, y, infinity).into_projective())
110 }
111 (None, None, None) => None,
112 _ => unreachable!(),
113 }
114 }
115
116 #[inline]
117 fn get_variable(&self) -> Self::Variable {
118 (self.x.get_variable(), self.y.get_variable())
119 }
120
121 #[inline]
122 fn zero<CS: ConstraintSystem<ConstraintF>>(mut cs: CS) -> Result<Self, SynthesisError> {
123 Ok(Self::new(
124 F::zero(cs.ns(|| "zero"))?,
125 F::one(cs.ns(|| "one"))?,
126 Boolean::Constant(true),
127 ))
128 }
129
130 #[inline]
131 /// Incomplete addition: neither `self` nor `other` can be the neutral
132 /// element.
133 fn add<CS: ConstraintSystem<ConstraintF>>(
134 &self,
135 mut cs: CS,
136 other: &Self,
137 ) -> Result<Self, SynthesisError> {
138 // lambda = (B.y - A.y)/(B.x - A.x)
139 // C.x = lambda^2 - A.x - B.x
140 // C.y = lambda(A.x - C.x) - A.y
141 //
142 // Special cases:
143 //
144 // doubling: if B.y = A.y and B.x = A.x then lambda is unbound and
145 // C = (lambda^2, lambda^3)
146 //
147 // addition of negative point: if B.y = -A.y and B.x = A.x then no
148 // lambda can satisfy the first equation unless B.y - A.y = 0. But
149 // then this reduces to doubling.
150 //
151 // So we need to check that A.x - B.x != 0, which can be done by
152 // enforcing I * (B.x - A.x) = 1
153 // This is done below when we calculate inv (by F::inverse)
154
155 let x2_minus_x1 = other.x.sub(cs.ns(|| "x2 - x1"), &self.x)?;
156 let y2_minus_y1 = other.y.sub(cs.ns(|| "y2 - y1"), &self.y)?;
157
158 let inv = x2_minus_x1.inverse(cs.ns(|| "compute inv"))?;
159
160 let lambda = F::alloc(cs.ns(|| "lambda"), || {
161 Ok(y2_minus_y1.get_value().get()? * &inv.get_value().get()?)
162 })?;
163
164 let x_3 = F::alloc(&mut cs.ns(|| "x_3"), || {
165 let lambda_val = lambda.get_value().get()?;
166 let x1 = self.x.get_value().get()?;
167 let x2 = other.x.get_value().get()?;
168 Ok((lambda_val.square() - &x1) - &x2)
169 })?;
170
171 let y_3 = F::alloc(&mut cs.ns(|| "y_3"), || {
172 let lambda_val = lambda.get_value().get()?;
173 let x_1 = self.x.get_value().get()?;
174 let y_1 = self.y.get_value().get()?;
175 let x_3 = x_3.get_value().get()?;
176 Ok(lambda_val * &(x_1 - &x_3) - &y_1)
177 })?;
178
179 // Check lambda
180 lambda.mul_equals(cs.ns(|| "check lambda"), &x2_minus_x1, &y2_minus_y1)?;
181
182 // Check x3
183 let x3_plus_x1_plus_x2 = x_3
184 .add(cs.ns(|| "x3 + x1"), &self.x)?
185 .add(cs.ns(|| "x3 + x1 + x2"), &other.x)?;
186 lambda.mul_equals(cs.ns(|| "check x3"), &lambda, &x3_plus_x1_plus_x2)?;
187
188 // Check y3
189 let y3_plus_y1 = y_3.add(cs.ns(|| "y3 + y1"), &self.y)?;
190 let x1_minus_x3 = self.x.sub(cs.ns(|| "x1 - x3"), &x_3)?;
191
192 lambda.mul_equals(cs.ns(|| ""), &x1_minus_x3, &y3_plus_y1)?;
193
194 Ok(Self::new(x_3, y_3, Boolean::Constant(false)))
195 }
196
197 /// Incomplete addition: neither `self` nor `other` can be the neutral
198 /// element.
199 fn add_constant<CS: ConstraintSystem<ConstraintF>>(
200 &self,
201 mut cs: CS,
202 other: &SWProjective<P>,
203 ) -> Result<Self, SynthesisError> {
204 // lambda = (B.y - A.y)/(B.x - A.x)
205 // C.x = lambda^2 - A.x - B.x
206 // C.y = lambda(A.x - C.x) - A.y
207 //
208 // Special cases:
209 //
210 // doubling: if B.y = A.y and B.x = A.x then lambda is unbound and
211 // C = (lambda^2, lambda^3)
212 //
213 // addition of negative point: if B.y = -A.y and B.x = A.x then no
214 // lambda can satisfy the first equation unless B.y - A.y = 0. But
215 // then this reduces to doubling.
216 //
217 // So we need to check that A.x - B.x != 0, which can be done by
218 // enforcing I * (B.x - A.x) = 1
219 if other.is_zero() {
220 return Err(SynthesisError::AssignmentMissing);
221 }
222 let other = other.into_affine();
223 let other_x = other.x;
224 let other_y = other.y;
225
226 let x2_minus_x1 = self
227 .x
228 .sub_constant(cs.ns(|| "x2 - x1"), &other_x)?
229 .negate(cs.ns(|| "neg1"))?;
230 let y2_minus_y1 = self
231 .y
232 .sub_constant(cs.ns(|| "y2 - y1"), &other_y)?
233 .negate(cs.ns(|| "neg2"))?;
234
235 let inv = x2_minus_x1.inverse(cs.ns(|| "compute inv"))?;
236
237 let lambda = F::alloc(cs.ns(|| "lambda"), || {
238 Ok(y2_minus_y1.get_value().get()? * &inv.get_value().get()?)
239 })?;
240
241 let x_3 = F::alloc(&mut cs.ns(|| "x_3"), || {
242 let lambda_val = lambda.get_value().get()?;
243 let x1 = self.x.get_value().get()?;
244 let x2 = other_x;
245 Ok((lambda_val.square() - &x1) - &x2)
246 })?;
247
248 let y_3 = F::alloc(&mut cs.ns(|| "y_3"), || {
249 let lambda_val = lambda.get_value().get()?;
250 let x_1 = self.x.get_value().get()?;
251 let y_1 = self.y.get_value().get()?;
252 let x_3 = x_3.get_value().get()?;
253 Ok(lambda_val * &(x_1 - &x_3) - &y_1)
254 })?;
255
256 // Check lambda
257 lambda.mul_equals(cs.ns(|| "check lambda"), &x2_minus_x1, &y2_minus_y1)?;
258
259 // Check x3
260 let x3_plus_x1_plus_x2 = x_3
261 .add(cs.ns(|| "x3 + x1"), &self.x)?
262 .add_constant(cs.ns(|| "x3 + x1 + x2"), &other_x)?;
263 lambda.mul_equals(cs.ns(|| "check x3"), &lambda, &x3_plus_x1_plus_x2)?;
264
265 // Check y3
266 let y3_plus_y1 = y_3.add(cs.ns(|| "y3 + y1"), &self.y)?;
267 let x1_minus_x3 = self.x.sub(cs.ns(|| "x1 - x3"), &x_3)?;
268
269 lambda.mul_equals(cs.ns(|| ""), &x1_minus_x3, &y3_plus_y1)?;
270
271 Ok(Self::new(x_3, y_3, Boolean::Constant(false)))
272 }
273
274 #[inline]
275 fn double_in_place<CS: ConstraintSystem<ConstraintF>>(
276 &mut self,
277 mut cs: CS,
278 ) -> Result<(), SynthesisError> {
279 let a = P::COEFF_A;
280 let x_squared = self.x.square(cs.ns(|| "x^2"))?;
281
282 let one = P::BaseField::one();
283 let two = one.double();
284 let three = two + &one;
285
286 let three_x_squared = x_squared.mul_by_constant(cs.ns(|| "3 * x^2"), &three)?;
287 let three_x_squared_plus_a = three_x_squared.add_constant(cs.ns(|| "3 * x^2 + a"), &a)?;
288
289 let two_y = self.y.double(cs.ns(|| "2y"))?;
290
291 let lambda = F::alloc(cs.ns(|| "lambda"), || {
292 let y_doubled_inv = two_y.get_value().get()?.inverse().get()?;
293 Ok(three_x_squared_plus_a.get_value().get()? * &y_doubled_inv)
294 })?;
295
296 // Check lambda
297 lambda.mul_equals(cs.ns(|| "check lambda"), &two_y, &three_x_squared_plus_a)?;
298
299 let x = lambda
300 .square(cs.ns(|| "lambda^2"))?
301 .sub(cs.ns(|| "lambda^2 - x"), &self.x)?
302 .sub(cs.ns(|| "lambda^2 - 2x"), &self.x)?;
303
304 let y = self
305 .x
306 .sub(cs.ns(|| "x - self.x"), &x)?
307 .mul(cs.ns(|| "times lambda"), &lambda)?
308 .sub(cs.ns(|| "plus self.y"), &self.y)?;
309
310 *self = Self::new(x, y, Boolean::Constant(false));
311 Ok(())
312 }
313
314 fn negate<CS: ConstraintSystem<ConstraintF>>(
315 &self,
316 mut cs: CS,
317 ) -> Result<Self, SynthesisError> {
318 Ok(Self::new(
319 self.x.clone(),
320 self.y.negate(cs.ns(|| "negate y"))?,
321 self.infinity,
322 ))
323 }
324
325 fn cost_of_add() -> usize {
326 3 * F::cost_of_mul_equals() + F::cost_of_inv()
327 }
328
329 fn cost_of_double() -> usize {
330 4 * F::cost_of_mul()
331 }
332}
333
334impl<P, ConstraintF, F> CondSelectGadget<ConstraintF> for AffineGadget<P, ConstraintF, F>
335where
336 P: SWModelParameters,
337 ConstraintF: PrimeField,
338 F: FieldGadget<P::BaseField, ConstraintF>,
339{
340 #[inline]
341 fn conditionally_select<CS: ConstraintSystem<ConstraintF>>(
342 mut cs: CS,
343 cond: &Boolean,
344 true_value: &Self,
345 false_value: &Self,
346 ) -> Result<Self, SynthesisError> {
347 let x = F::conditionally_select(&mut cs.ns(|| "x"), cond, &true_value.x, &false_value.x)?;
348 let y = F::conditionally_select(&mut cs.ns(|| "y"), cond, &true_value.y, &false_value.y)?;
349 let infinity = Boolean::conditionally_select(
350 &mut cs.ns(|| "infinity"),
351 cond,
352 &true_value.infinity,
353 &false_value.infinity,
354 )?;
355
356 Ok(Self::new(x, y, infinity))
357 }
358
359 fn cost() -> usize {
360 2 * <F as CondSelectGadget<ConstraintF>>::cost()
361 + <Boolean as CondSelectGadget<ConstraintF>>::cost()
362 }
363}
364
365impl<P, ConstraintF, F> EqGadget<ConstraintF> for AffineGadget<P, ConstraintF, F>
366where
367 P: SWModelParameters,
368 ConstraintF: Field,
369 F: FieldGadget<P::BaseField, ConstraintF>,
370{
371}
372
373impl<P, ConstraintF, F> ConditionalEqGadget<ConstraintF> for AffineGadget<P, ConstraintF, F>
374where
375 P: SWModelParameters,
376 ConstraintF: Field,
377 F: FieldGadget<P::BaseField, ConstraintF>,
378{
379 #[inline]
380 fn conditional_enforce_equal<CS: ConstraintSystem<ConstraintF>>(
381 &self,
382 mut cs: CS,
383 other: &Self,
384 condition: &Boolean,
385 ) -> Result<(), SynthesisError> {
386 self.x.conditional_enforce_equal(
387 &mut cs.ns(|| "X Coordinate Conditional Equality"),
388 &other.x,
389 condition,
390 )?;
391 self.y.conditional_enforce_equal(
392 &mut cs.ns(|| "Y Coordinate Conditional Equality"),
393 &other.y,
394 condition,
395 )?;
396 self.infinity.conditional_enforce_equal(
397 &mut cs.ns(|| "Infinity Conditional Equality"),
398 &other.infinity,
399 condition,
400 )?;
401 Ok(())
402 }
403
404 fn cost() -> usize {
405 2 * <F as ConditionalEqGadget<ConstraintF>>::cost()
406 }
407}
408
409impl<P, ConstraintF, F> NEqGadget<ConstraintF> for AffineGadget<P, ConstraintF, F>
410where
411 P: SWModelParameters,
412 ConstraintF: Field,
413 F: FieldGadget<P::BaseField, ConstraintF>,
414{
415 #[inline]
416 fn enforce_not_equal<CS: ConstraintSystem<ConstraintF>>(
417 &self,
418 mut cs: CS,
419 other: &Self,
420 ) -> Result<(), SynthesisError> {
421 self.x
422 .enforce_not_equal(&mut cs.ns(|| "X Coordinate Inequality"), &other.x)?;
423 self.y
424 .enforce_not_equal(&mut cs.ns(|| "Y Coordinate Inequality"), &other.y)?;
425 Ok(())
426 }
427
428 fn cost() -> usize {
429 2 * <F as NEqGadget<ConstraintF>>::cost()
430 }
431}
432
433impl<P, ConstraintF, F> AllocGadget<SWProjective<P>, ConstraintF>
434 for AffineGadget<P, ConstraintF, F>
435where
436 P: SWModelParameters,
437 ConstraintF: PrimeField,
438 F: FieldGadget<P::BaseField, ConstraintF>,
439{
440 #[inline]
441 fn alloc_constant<T, CS: ConstraintSystem<ConstraintF>>(
442 mut cs: CS,
443 t: T,
444 ) -> Result<Self, SynthesisError>
445 where
446 T: Borrow<SWProjective<P>>,
447 {
448 let p = t.borrow().into_affine();
449 Ok(Self {
450 x: F::alloc_constant(cs.ns(|| "x"), &p.x)?,
451 y: F::alloc_constant(cs.ns(|| "y"), &p.y)?,
452 infinity: Boolean::constant(p.infinity),
453 _params: PhantomData,
454 _engine: PhantomData,
455 })
456 }
457
458 #[inline]
459 fn alloc<FN, T, CS: ConstraintSystem<ConstraintF>>(
460 mut cs: CS,
461 value_gen: FN,
462 ) -> Result<Self, SynthesisError>
463 where
464 FN: FnOnce() -> Result<T, SynthesisError>,
465 T: Borrow<SWProjective<P>>,
466 {
467 let (x, y, infinity) = match value_gen() {
468 Ok(ge) => {
469 let ge = ge.borrow().into_affine();
470 (Ok(ge.x), Ok(ge.y), Ok(ge.infinity))
471 }
472 _ => (
473 Err(SynthesisError::AssignmentMissing),
474 Err(SynthesisError::AssignmentMissing),
475 Err(SynthesisError::AssignmentMissing),
476 ),
477 };
478
479 // Perform on-curve check.
480 let b = P::COEFF_B;
481 let a = P::COEFF_A;
482
483 let x = F::alloc(&mut cs.ns(|| "x"), || x)?;
484 let y = F::alloc(&mut cs.ns(|| "y"), || y)?;
485 let infinity = Boolean::alloc(&mut cs.ns(|| "infinity"), || infinity)?;
486
487 // Check that y^2 = x^3 + ax +b
488 // We do this by checking that y^2 - b = x * (x^2 +a)
489 let x2 = x.square(&mut cs.ns(|| "x^2"))?;
490 let y2 = y.square(&mut cs.ns(|| "y^2"))?;
491
492 let x2_plus_a = x2.add_constant(cs.ns(|| "x^2 + a"), &a)?;
493 let y2_minus_b = y2.add_constant(cs.ns(|| "y^2 - b"), &b.neg())?;
494
495 x2_plus_a.mul_equals(cs.ns(|| "on curve check"), &x, &y2_minus_b)?;
496
497 Ok(Self::new(x, y, infinity))
498 }
499
500 #[inline]
501 fn alloc_checked<FN, T, CS: ConstraintSystem<ConstraintF>>(
502 mut cs: CS,
503 value_gen: FN,
504 ) -> Result<Self, SynthesisError>
505 where
506 FN: FnOnce() -> Result<T, SynthesisError>,
507 T: Borrow<SWProjective<P>>,
508 {
509 let cofactor_weight = BitIterator::new(P::COFACTOR).filter(|b| *b).count();
510 // If we multiply by r, we actually multiply by r - 2.
511 let r_minus_1 = (-P::ScalarField::one()).into_repr();
512 let r_weight = BitIterator::new(&r_minus_1).filter(|b| *b).count();
513
514 // We pick the most efficient method of performing the prime order check:
515 // If the cofactor has lower hamming weight than the scalar field's modulus,
516 // we first multiply by the inverse of the cofactor, and then, after allocating,
517 // multiply by the cofactor. This ensures the resulting point has no cofactors
518 //
519 // Else, we multiply by the scalar field's modulus and ensure that the result
520 // is zero.
521 if cofactor_weight < r_weight {
522 let ge = Self::alloc(cs.ns(|| "Alloc checked"), || {
523 value_gen().map(|ge| {
524 ge.borrow()
525 .into_affine()
526 .mul_by_cofactor_inv()
527 .into_projective()
528 })
529 })?;
530 let mut seen_one = false;
531 let mut result = Self::zero(cs.ns(|| "result"))?;
532 for (i, b) in BitIterator::new(P::COFACTOR).enumerate() {
533 let mut cs = cs.ns(|| format!("Iteration {}", i));
534
535 let old_seen_one = seen_one;
536 if seen_one {
537 result.double_in_place(cs.ns(|| "Double"))?;
538 } else {
539 seen_one = b;
540 }
541
542 if b {
543 result = if old_seen_one {
544 result.add(cs.ns(|| "Add"), &ge)?
545 } else {
546 ge.clone()
547 };
548 }
549 }
550 Ok(result)
551 } else {
552 let ge = Self::alloc(cs.ns(|| "Alloc checked"), value_gen)?;
553 let mut seen_one = false;
554 let mut result = Self::zero(cs.ns(|| "result"))?;
555 // Returns bits in big-endian order
556 for (i, b) in BitIterator::new(r_minus_1).enumerate() {
557 let mut cs = cs.ns(|| format!("Iteration {}", i));
558
559 let old_seen_one = seen_one;
560 if seen_one {
561 result.double_in_place(cs.ns(|| "Double"))?;
562 } else {
563 seen_one = b;
564 }
565
566 if b {
567 result = if old_seen_one {
568 result.add(cs.ns(|| "Add"), &ge)?
569 } else {
570 ge.clone()
571 };
572 }
573 }
574 let neg_ge = ge.negate(cs.ns(|| "Negate ge"))?;
575 neg_ge.enforce_equal(cs.ns(|| "Check equals"), &result)?;
576 Ok(ge)
577 }
578 }
579
580 #[inline]
581 fn alloc_input<FN, T, CS: ConstraintSystem<ConstraintF>>(
582 mut cs: CS,
583 value_gen: FN,
584 ) -> Result<Self, SynthesisError>
585 where
586 FN: FnOnce() -> Result<T, SynthesisError>,
587 T: Borrow<SWProjective<P>>,
588 {
589 // When allocating the input we assume that the verifier has performed
590 // any on curve checks already.
591 let (x, y, infinity) = match value_gen() {
592 Ok(ge) => {
593 let ge = ge.borrow().into_affine();
594 (Ok(ge.x), Ok(ge.y), Ok(ge.infinity))
595 }
596 _ => (
597 Err(SynthesisError::AssignmentMissing),
598 Err(SynthesisError::AssignmentMissing),
599 Err(SynthesisError::AssignmentMissing),
600 ),
601 };
602
603 let x = F::alloc_input(&mut cs.ns(|| "x"), || x)?;
604 let y = F::alloc_input(&mut cs.ns(|| "y"), || y)?;
605 let infinity = Boolean::alloc_input(&mut cs.ns(|| "infinity"), || infinity)?;
606
607 Ok(Self::new(x, y, infinity))
608 }
609}
610
611impl<P, ConstraintF, F> ToBitsGadget<ConstraintF> for AffineGadget<P, ConstraintF, F>
612where
613 P: SWModelParameters,
614 ConstraintF: Field,
615 F: FieldGadget<P::BaseField, ConstraintF>,
616{
617 fn to_bits<CS: ConstraintSystem<ConstraintF>>(
618 &self,
619 mut cs: CS,
620 ) -> Result<Vec<Boolean>, SynthesisError> {
621 let mut x_bits = self.x.to_bits(&mut cs.ns(|| "X Coordinate To Bits"))?;
622 let y_bits = self.y.to_bits(&mut cs.ns(|| "Y Coordinate To Bits"))?;
623 x_bits.extend_from_slice(&y_bits);
624 x_bits.push(self.infinity);
625 Ok(x_bits)
626 }
627
628 fn to_non_unique_bits<CS: ConstraintSystem<ConstraintF>>(
629 &self,
630 mut cs: CS,
631 ) -> Result<Vec<Boolean>, SynthesisError> {
632 let mut x_bits = self
633 .x
634 .to_non_unique_bits(&mut cs.ns(|| "X Coordinate To Bits"))?;
635 let y_bits = self
636 .y
637 .to_non_unique_bits(&mut cs.ns(|| "Y Coordinate To Bits"))?;
638 x_bits.extend_from_slice(&y_bits);
639 x_bits.push(self.infinity);
640
641 Ok(x_bits)
642 }
643}
644
645impl<P, ConstraintF, F> ToBytesGadget<ConstraintF> for AffineGadget<P, ConstraintF, F>
646where
647 P: SWModelParameters,
648 ConstraintF: Field,
649 F: FieldGadget<P::BaseField, ConstraintF>,
650{
651 fn to_bytes<CS: ConstraintSystem<ConstraintF>>(
652 &self,
653 mut cs: CS,
654 ) -> Result<Vec<UInt8>, SynthesisError> {
655 let mut x_bytes = self.x.to_bytes(&mut cs.ns(|| "X Coordinate To Bytes"))?;
656 let y_bytes = self.y.to_bytes(&mut cs.ns(|| "Y Coordinate To Bytes"))?;
657 let inf_bytes = self.infinity.to_bytes(&mut cs.ns(|| "Infinity to Bytes"))?;
658 x_bytes.extend_from_slice(&y_bytes);
659 x_bytes.extend_from_slice(&inf_bytes);
660 Ok(x_bytes)
661 }
662
663 fn to_non_unique_bytes<CS: ConstraintSystem<ConstraintF>>(
664 &self,
665 mut cs: CS,
666 ) -> Result<Vec<UInt8>, SynthesisError> {
667 let mut x_bytes = self
668 .x
669 .to_non_unique_bytes(&mut cs.ns(|| "X Coordinate To Bytes"))?;
670 let y_bytes = self
671 .y
672 .to_non_unique_bytes(&mut cs.ns(|| "Y Coordinate To Bytes"))?;
673 let inf_bytes = self
674 .infinity
675 .to_non_unique_bytes(&mut cs.ns(|| "Infinity to Bytes"))?;
676 x_bytes.extend_from_slice(&y_bytes);
677 x_bytes.extend_from_slice(&inf_bytes);
678
679 Ok(x_bytes)
680 }
681}
682
683#[cfg(test)]
684#[allow(dead_code)]
685pub(crate) fn test<ConstraintF, P, GG>()
686where
687 ConstraintF: Field,
688 P: SWModelParameters,
689 GG: GroupGadget<SWProjective<P>, ConstraintF, Value = SWProjective<P>>,
690{
691 use crate::{boolean::AllocatedBit, prelude::*, test_constraint_system::TestConstraintSystem};
692 use algebra::{test_rng, Group, UniformRand};
693 use rand::Rng;
694
695 // Incomplete addition doesn't allow us to call the group_test.
696 // group_test::<ConstraintF, SWProjective<P>, GG>();
697
698 let mut rng = test_rng();
699
700 let mut cs = TestConstraintSystem::<ConstraintF>::new();
701
702 let a = SWProjective::<P>::rand(&mut rng);
703 let b = SWProjective::<P>::rand(&mut rng);
704 let a_affine = a.into_affine();
705 let b_affine = b.into_affine();
706 let mut gadget_a = GG::alloc(&mut cs.ns(|| "a"), || Ok(a)).unwrap();
707 let gadget_b = GG::alloc_checked(&mut cs.ns(|| "b"), || Ok(b)).unwrap();
708 assert_eq!(gadget_a.get_value().unwrap().x, a_affine.x);
709 assert_eq!(gadget_a.get_value().unwrap().y, a_affine.y);
710 assert_eq!(gadget_b.get_value().unwrap().x, b_affine.x);
711 assert_eq!(gadget_b.get_value().unwrap().y, b_affine.y);
712
713 // Check addition
714 let ab = a + &b;
715 let ab_affine = ab.into_affine();
716 let gadget_ab = gadget_a.add(&mut cs.ns(|| "ab"), &gadget_b).unwrap();
717 let gadget_ba = gadget_b.add(&mut cs.ns(|| "ba"), &gadget_a).unwrap();
718 gadget_ba
719 .enforce_equal(&mut cs.ns(|| "b + a == a + b?"), &gadget_ab)
720 .unwrap();
721
722 let ab_val = gadget_ab
723 .get_value()
724 .expect("Doubling should be successful")
725 .into_affine();
726 assert_eq!(ab_val, ab_affine, "Result of addition is unequal");
727
728 // Check doubling
729 let aa = Group::double(&a);
730 let aa_affine = aa.into_affine();
731 gadget_a.double_in_place(&mut cs.ns(|| "2a")).unwrap();
732 let aa_val = gadget_a
733 .get_value()
734 .expect("Doubling should be successful")
735 .into_affine();
736 assert_eq!(
737 aa_val, aa_affine,
738 "Gadget and native values are unequal after double."
739 );
740
741 // Check mul_bits
742 let scalar = P::ScalarField::rand(&mut rng);
743 let native_result = aa.into_affine().mul(scalar) + &b;
744 let native_result = native_result.into_affine();
745
746 let mut scalar: Vec<bool> = BitIterator::new(scalar.into_repr()).collect();
747 // Get the scalar bits into little-endian form.
748 scalar.reverse();
749 let input = Vec::<Boolean>::alloc(cs.ns(|| "Input"), || Ok(scalar)).unwrap();
750 let result = gadget_a
751 .mul_bits(cs.ns(|| "mul_bits"), &gadget_b, input.iter())
752 .unwrap();
753 let result_val = result.get_value().unwrap().into_affine();
754 assert_eq!(
755 result_val, native_result,
756 "gadget & native values are diff. after scalar mul"
757 );
758
759 if !cs.is_satisfied() {
760 println!("{:?}", cs.which_is_unsatisfied().unwrap());
761 }
762
763 assert!(cs.is_satisfied());
764
765 // Constraint cost etc.
766 let mut cs = TestConstraintSystem::<ConstraintF>::new();
767
768 let bit = AllocatedBit::alloc(&mut cs.ns(|| "bool"), || Ok(true))
769 .unwrap()
770 .into();
771
772 let mut rng = test_rng();
773 let a: SWProjective<P> = rng.gen();
774 let b: SWProjective<P> = rng.gen();
775 let gadget_a = GG::alloc(&mut cs.ns(|| "a"), || Ok(a)).unwrap();
776 let gadget_b = GG::alloc(&mut cs.ns(|| "b"), || Ok(b)).unwrap();
777 let alloc_cost = cs.num_constraints();
778 let _ =
779 GG::conditionally_select(&mut cs.ns(|| "cond_select"), &bit, &gadget_a, &gadget_b).unwrap();
780 let cond_select_cost = cs.num_constraints() - alloc_cost;
781
782 let _ = gadget_a.add(&mut cs.ns(|| "ab"), &gadget_b).unwrap();
783 let add_cost = cs.num_constraints() - cond_select_cost - alloc_cost;
784
785 assert!(cs.is_satisfied());
786 assert_eq!(
787 cond_select_cost,
788 <GG as CondSelectGadget<ConstraintF>>::cost()
789 );
790 assert_eq!(add_cost, GG::cost_of_add());
791}