ark-r1cs-std/r1cs-std/src/fields/fp6_3over2.rs
r1cs-std/src/fields/fp6_3over2.rsRaw
1use algebra::{
2 fields::{
3 fp6_3over2::{Fp6, Fp6Parameters},
4 Field, Fp2Parameters,
5 },
6 PrimeField,
7};
8use core::{borrow::Borrow, marker::PhantomData};
9use r1cs_core::{ConstraintSystem, ConstraintVar, SynthesisError};
10
11use crate::{prelude::*, Vec};
12
13type Fp2Gadget<P, ConstraintF> =
14 super::fp2::Fp2Gadget<<P as Fp6Parameters>::Fp2Params, ConstraintF>;
15
16#[derive(Derivative)]
17#[derivative(Debug(bound = "ConstraintF: PrimeField"))]
18#[must_use]
19pub struct Fp6Gadget<P, ConstraintF: PrimeField>
20where
21 P: Fp6Parameters,
22 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
23{
24 pub c0: Fp2Gadget<P, ConstraintF>,
25 pub c1: Fp2Gadget<P, ConstraintF>,
26 pub c2: Fp2Gadget<P, ConstraintF>,
27 #[derivative(Debug = "ignore")]
28 _params: PhantomData<P>,
29}
30
31impl<P, ConstraintF: PrimeField> Fp6Gadget<P, ConstraintF>
32where
33 P: Fp6Parameters,
34 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
35{
36 #[inline]
37 pub fn new(
38 c0: Fp2Gadget<P, ConstraintF>,
39 c1: Fp2Gadget<P, ConstraintF>,
40 c2: Fp2Gadget<P, ConstraintF>,
41 ) -> Self {
42 Self {
43 c0,
44 c1,
45 c2,
46 _params: PhantomData,
47 }
48 }
49 /// Multiply a Fp2Gadget by cubic nonresidue P::NONRESIDUE.
50 #[inline]
51 pub fn mul_fp2_gadget_by_nonresidue<CS: ConstraintSystem<ConstraintF>>(
52 cs: CS,
53 fe: &Fp2Gadget<P, ConstraintF>,
54 ) -> Result<Fp2Gadget<P, ConstraintF>, SynthesisError> {
55 fe.mul_by_constant(cs, &P::NONRESIDUE)
56 }
57
58 #[inline]
59 pub fn mul_by_0_c1_0<CS: ConstraintSystem<ConstraintF>>(
60 &self,
61 mut cs: CS,
62 c1: &Fp2Gadget<P, ConstraintF>,
63 ) -> Result<Self, SynthesisError> {
64 // Karatsuba multiplication
65 // v0 = a0 * b0 = 0
66
67 // v1 = a1 * b1
68 let v1 = self.c1.mul(cs.ns(|| "first mul"), c1)?;
69
70 // v2 = a2 * b2 = 0
71
72 let a1_plus_a2 = self.c1.add(cs.ns(|| "a1 + a2"), &self.c2)?;
73 let b1_plus_b2 = c1.clone();
74
75 let a0_plus_a1 = self.c0.add(cs.ns(|| "a0 + a1"), &self.c1)?;
76
77 // c0 = (NONRESIDUE * ((a1 + a2)*(b1 + b2) - v1 - v2)) + v0
78 // = NONRESIDUE * ((a1 + a2) * b1 - v1)
79 let c0 = a1_plus_a2
80 .mul(cs.ns(|| "second mul"), &b1_plus_b2)?
81 .sub(cs.ns(|| "first sub"), &v1)?
82 .mul_by_constant(cs.ns(|| "mul_by_nonresidue"), &P::NONRESIDUE)?;
83
84 // c1 = (a0 + a1) * (b0 + b1) - v0 - v1 + NONRESIDUE * v2
85 // = (a0 + a1) * b1 - v1
86 let c1 = a0_plus_a1
87 .mul(cs.ns(|| "third mul"), &c1)?
88 .sub(cs.ns(|| "second sub"), &v1)?;
89 // c2 = (a0 + a2) * (b0 + b2) - v0 - v2 + v1
90 // = v1
91 let c2 = v1;
92 Ok(Self::new(c0, c1, c2))
93 }
94
95 // #[inline]
96 pub fn mul_by_c0_c1_0<CS: ConstraintSystem<ConstraintF>>(
97 &self,
98 mut cs: CS,
99 c0: &Fp2Gadget<P, ConstraintF>,
100 c1: &Fp2Gadget<P, ConstraintF>,
101 ) -> Result<Self, SynthesisError> {
102 let v0 = self.c0.mul(cs.ns(|| "v0"), c0)?;
103 let v1 = self.c1.mul(cs.ns(|| "v1"), c1)?;
104 // v2 = 0.
105
106 let a1_plus_a2 = self.c1.add(cs.ns(|| "a1 + a2"), &self.c2)?;
107 let a0_plus_a1 = self.c0.add(cs.ns(|| "a0 + a1"), &self.c1)?;
108 let a0_plus_a2 = self.c0.add(cs.ns(|| "a0 + a2"), &self.c2)?;
109
110 let b1_plus_b2 = c1.clone();
111 let b0_plus_b1 = c0.add(cs.ns(|| "b0 + b1"), &c1)?;
112 let b0_plus_b2 = c0.clone();
113
114 let c0 = {
115 let cs = &mut cs.ns(|| "c0");
116 a1_plus_a2
117 .mul(cs.ns(|| "(a1 + a2) * (b1 + b2)"), &b1_plus_b2)?
118 .sub(cs.ns(|| "sub v1"), &v1)?
119 .mul_by_constant(cs.ns(|| "First mul_by_nonresidue"), &P::NONRESIDUE)?
120 .add(cs.ns(|| "add v0"), &v0)?
121 };
122
123 let c1 = {
124 let cs = &mut cs.ns(|| "c1");
125 a0_plus_a1
126 .mul(cs.ns(|| "(a0 + a1) * (b0 + b1)"), &b0_plus_b1)?
127 .sub(cs.ns(|| "sub v0"), &v0)?
128 .sub(cs.ns(|| "sub v1"), &v1)?
129 };
130
131 let c2 = {
132 a0_plus_a2
133 .mul(cs.ns(|| "(a0 + a2) * (b0 + b2)"), &b0_plus_b2)?
134 .sub(cs.ns(|| "sub v0"), &v0)?
135 .add(cs.ns(|| "add v1"), &v1)?
136 };
137
138 Ok(Self::new(c0, c1, c2))
139 }
140}
141
142impl<P, ConstraintF: PrimeField> FieldGadget<Fp6<P>, ConstraintF> for Fp6Gadget<P, ConstraintF>
143where
144 P: Fp6Parameters,
145 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
146{
147 type Variable = (
148 (ConstraintVar<ConstraintF>, ConstraintVar<ConstraintF>),
149 (ConstraintVar<ConstraintF>, ConstraintVar<ConstraintF>),
150 (ConstraintVar<ConstraintF>, ConstraintVar<ConstraintF>),
151 );
152
153 #[inline]
154 fn get_value(&self) -> Option<Fp6<P>> {
155 match (
156 self.c0.get_value(),
157 self.c1.get_value(),
158 self.c2.get_value(),
159 ) {
160 (Some(c0), Some(c1), Some(c2)) => Some(Fp6::new(c0, c1, c2)),
161 (..) => None,
162 }
163 }
164
165 #[inline]
166 fn get_variable(&self) -> Self::Variable {
167 (
168 self.c0.get_variable(),
169 self.c1.get_variable(),
170 self.c2.get_variable(),
171 )
172 }
173
174 #[inline]
175 fn zero<CS: ConstraintSystem<ConstraintF>>(mut cs: CS) -> Result<Self, SynthesisError> {
176 let c0 = Fp2Gadget::<P, ConstraintF>::zero(cs.ns(|| "c0"))?;
177 let c1 = Fp2Gadget::<P, ConstraintF>::zero(cs.ns(|| "c1"))?;
178 let c2 = Fp2Gadget::<P, ConstraintF>::zero(cs.ns(|| "c2"))?;
179 Ok(Self::new(c0, c1, c2))
180 }
181
182 #[inline]
183 fn one<CS: ConstraintSystem<ConstraintF>>(mut cs: CS) -> Result<Self, SynthesisError> {
184 let c0 = Fp2Gadget::<P, ConstraintF>::one(cs.ns(|| "c0"))?;
185 let c1 = Fp2Gadget::<P, ConstraintF>::zero(cs.ns(|| "c1"))?;
186 let c2 = Fp2Gadget::<P, ConstraintF>::zero(cs.ns(|| "c2"))?;
187 Ok(Self::new(c0, c1, c2))
188 }
189
190 #[inline]
191 fn conditionally_add_constant<CS: ConstraintSystem<ConstraintF>>(
192 &self,
193 mut cs: CS,
194 bit: &Boolean,
195 coeff: Fp6<P>,
196 ) -> Result<Self, SynthesisError> {
197 let c0 = self
198 .c0
199 .conditionally_add_constant(cs.ns(|| "c0"), bit, coeff.c0)?;
200 let c1 = self
201 .c1
202 .conditionally_add_constant(cs.ns(|| "c1"), bit, coeff.c1)?;
203 let c2 = self
204 .c2
205 .conditionally_add_constant(cs.ns(|| "c2"), bit, coeff.c2)?;
206 Ok(Self::new(c0, c1, c2))
207 }
208
209 #[inline]
210 fn add<CS: ConstraintSystem<ConstraintF>>(
211 &self,
212 mut cs: CS,
213 other: &Self,
214 ) -> Result<Self, SynthesisError> {
215 let c0 = self.c0.add(&mut cs.ns(|| "add c0"), &other.c0)?;
216 let c1 = self.c1.add(&mut cs.ns(|| "add c1"), &other.c1)?;
217 let c2 = self.c2.add(&mut cs.ns(|| "add c2"), &other.c2)?;
218 Ok(Self::new(c0, c1, c2))
219 }
220
221 #[inline]
222 fn sub<CS: ConstraintSystem<ConstraintF>>(
223 &self,
224 mut cs: CS,
225 other: &Self,
226 ) -> Result<Self, SynthesisError> {
227 let c0 = self.c0.sub(&mut cs.ns(|| "sub c0"), &other.c0)?;
228 let c1 = self.c1.sub(&mut cs.ns(|| "sub c1"), &other.c1)?;
229 let c2 = self.c2.sub(&mut cs.ns(|| "sub c2"), &other.c2)?;
230 Ok(Self::new(c0, c1, c2))
231 }
232
233 #[inline]
234 fn negate<CS: ConstraintSystem<ConstraintF>>(
235 &self,
236 mut cs: CS,
237 ) -> Result<Self, SynthesisError> {
238 let c0 = self.c0.negate(&mut cs.ns(|| "negate c0"))?;
239 let c1 = self.c1.negate(&mut cs.ns(|| "negate c1"))?;
240 let c2 = self.c2.negate(&mut cs.ns(|| "negate c2"))?;
241 Ok(Self::new(c0, c1, c2))
242 }
243
244 #[inline]
245 fn negate_in_place<CS: ConstraintSystem<ConstraintF>>(
246 &mut self,
247 mut cs: CS,
248 ) -> Result<&mut Self, SynthesisError> {
249 self.c0.negate_in_place(&mut cs.ns(|| "negate c0"))?;
250 self.c1.negate_in_place(&mut cs.ns(|| "negate c1"))?;
251 self.c2.negate_in_place(&mut cs.ns(|| "negate c2"))?;
252 Ok(self)
253 }
254
255 /// Use the Toom-Cook-3x method to compute multiplication.
256 #[inline]
257 fn mul<CS: ConstraintSystem<ConstraintF>>(
258 &self,
259 mut cs: CS,
260 other: &Self,
261 ) -> Result<Self, SynthesisError> {
262 // Uses Toom-Cook-3x multiplication from
263 //
264 // Reference:
265 // "Multiplication and Squaring on Pairing-Friendly Fields"
266 // Devegili, OhEigeartaigh, Scott, Dahab
267
268 // v0 = a(0)b(0) = a0 * b0
269 let v0 = self.c0.mul(&mut cs.ns(|| "Calc v0"), &other.c0)?;
270
271 // v1 = a(1)b(1) = (a0 + a1 + a2)(b0 + b1 + b2)
272 let v1 = {
273 let mut v1_cs = cs.ns(|| "compute v1");
274 let a0_plus_a1_plus_a2 = self
275 .c0
276 .add(v1_cs.ns(|| "a0 + a1"), &self.c1)?
277 .add(v1_cs.ns(|| "a0 + a1 + a2"), &self.c2)?;
278 let b0_plus_b1_plus_b2 = other
279 .c0
280 .add(v1_cs.ns(|| "b0 + b1"), &other.c1)?
281 .add(v1_cs.ns(|| "b0 + b1 + b2"), &other.c2)?;
282
283 a0_plus_a1_plus_a2.mul(
284 v1_cs.ns(|| "(a0 + a1 + a2)(b0 + b1 + b2)"),
285 &b0_plus_b1_plus_b2,
286 )?
287 };
288
289 // v2 = a(−1)b(−1) = (a0 − a1 + a2)(b0 − b1 + b2)
290 let v2 = {
291 let mut v2_cs = cs.ns(|| "compute v2");
292
293 let a0_minus_a1_plus_a2 = self
294 .c0
295 .sub(v2_cs.ns(|| "a0 - a1"), &self.c1)?
296 .add(v2_cs.ns(|| "a0 - a1 + a2"), &self.c2)?;
297
298 let b0_minus_b1_plus_b2 = other
299 .c0
300 .sub(v2_cs.ns(|| "b0 - b1"), &other.c1)?
301 .add(v2_cs.ns(|| "b0 - b1 + b2"), &other.c2)?;
302
303 a0_minus_a1_plus_a2.mul(
304 v2_cs.ns(|| "(a0 - a1 + a2)(b0 - b1 + b2)"),
305 &b0_minus_b1_plus_b2,
306 )?
307 };
308
309 // v3 = a(2)b(2) = (a0 + 2a1 + 4a2)(b0 + 2b1 + 4b2)
310 let v3 = {
311 let v3_cs = &mut cs.ns(|| "compute v3");
312
313 let a1_double = self.c1.double(v3_cs.ns(|| "2 * a1"))?;
314 let a2_quad = self
315 .c2
316 .double(v3_cs.ns(|| "2 * a2"))?
317 .double(v3_cs.ns(|| "4 * a2"))?;
318
319 let a0_plus_2_a1_plus_4_a2 = self
320 .c0
321 .add(v3_cs.ns(|| "a0 + 2a1"), &a1_double)?
322 .add(v3_cs.ns(|| "a0 + 2a1 + 4a2"), &a2_quad)?;
323
324 let b1_double = other.c1.double(v3_cs.ns(|| "2 * b1"))?;
325 let b2_quad = other
326 .c2
327 .double(v3_cs.ns(|| "2 * b2"))?
328 .double(v3_cs.ns(|| "4 * b2"))?;
329 let b0_plus_2_b1_plus_4_b2 = other
330 .c0
331 .add(v3_cs.ns(|| "b0 + 2b1"), &b1_double)?
332 .add(v3_cs.ns(|| "b0 + 2b1 + 4b2"), &b2_quad)?;
333
334 a0_plus_2_a1_plus_4_a2.mul(
335 v3_cs.ns(|| "(a0 + 2a1 + 4a2)(b0 + 2b1 + 4b2)"),
336 &b0_plus_2_b1_plus_4_b2,
337 )?
338 };
339
340 // v4 = a(∞)b(∞) = a2 * b2
341 let v4 = self.c2.mul(cs.ns(|| "v2: a2 * b2"), &other.c2)?;
342
343 let two = <P::Fp2Params as Fp2Parameters>::Fp::one().double();
344 let six = two.double() + &two;
345 let mut two_and_six = [two, six];
346 algebra::fields::batch_inversion(&mut two_and_six);
347 let (two_inverse, six_inverse) = (two_and_six[0], two_and_six[1]);
348
349 let half_v0 = v0.mul_by_fp_constant(cs.ns(|| "half_v0"), &two_inverse)?;
350 let half_v1 = v1.mul_by_fp_constant(cs.ns(|| "half_v1"), &two_inverse)?;
351 let one_sixth_v2 = v2.mul_by_fp_constant(cs.ns(|| "v2_by_six"), &six_inverse)?;
352 let one_sixth_v3 = v3.mul_by_fp_constant(cs.ns(|| "v3_by_six"), &six_inverse)?;
353 let two_v4 = v4.double(cs.ns(|| "2 * v4"))?;
354
355 // c0 = v0 + β((1/2)v0 − (1/2)v1 − (1/6)v2 + (1/6)v3 − 2v4)
356 let c0 = {
357 let c0_cs = &mut cs.ns(|| "c0");
358
359 // No constraints, only get a linear combination back.
360 let temp = half_v0
361 .sub(c0_cs.ns(|| "sub1"), &half_v1)?
362 .sub(c0_cs.ns(|| "sub2"), &one_sixth_v2)?
363 .add(c0_cs.ns(|| "add3"), &one_sixth_v3)?
364 .sub(c0_cs.ns(|| "sub4"), &two_v4)?;
365 let non_residue_times_inner =
366 temp.mul_by_constant(&mut c0_cs.ns(|| "mul5"), &P::NONRESIDUE)?;
367 v0.add(c0_cs.ns(|| "add6"), &non_residue_times_inner)?
368 };
369
370 // −(1/2)v0 + v1 − (1/3)v2 − (1/6)v3 + 2v4 + βv4
371 let c1 = {
372 let c1_cs = &mut cs.ns(|| "c1");
373 let one_third_v2 = one_sixth_v2.double(&mut c1_cs.ns(|| "v2_by_3"))?;
374 let non_residue_v4 =
375 v4.mul_by_constant(&mut c1_cs.ns(|| "mul_by_beta"), &P::NONRESIDUE)?;
376
377 let result = half_v0
378 .negate(c1_cs.ns(|| "neg1"))?
379 .add(c1_cs.ns(|| "add2"), &v1)?
380 .sub(c1_cs.ns(|| "sub3"), &one_third_v2)?
381 .sub(c1_cs.ns(|| "sub4"), &one_sixth_v3)?
382 .add(c1_cs.ns(|| "sub5"), &two_v4)?
383 .add(c1_cs.ns(|| "sub6"), &non_residue_v4)?;
384 result
385 };
386
387 // -v0 + (1/2)v1 + (1/2)v2 −v4
388 let c2 = {
389 let c2_cs = &mut cs.ns(|| "c2");
390 let half_v2 = v2.mul_by_fp_constant(&mut c2_cs.ns(|| "mul1"), &two_inverse)?;
391 let result = half_v1
392 .add(c2_cs.ns(|| "add1"), &half_v2)?
393 .sub(c2_cs.ns(|| "sub1"), &v4)?
394 .sub(c2_cs.ns(|| "sub2"), &v0)?;
395 result
396 };
397
398 Ok(Self::new(c0, c1, c2))
399 }
400
401 /// Use the Chung-Hasan asymmetric squaring formula.
402 ///
403 /// (Devegili OhEig Scott Dahab --- Multiplication and Squaring on
404 /// Abstract Pairing-Friendly
405 /// Fields.pdf; Section 4 (CH-SQR2))
406 #[inline]
407 fn square<CS: ConstraintSystem<ConstraintF>>(
408 &self,
409 mut cs: CS,
410 ) -> Result<Self, SynthesisError> {
411 let a = self.c0.clone();
412 let b = self.c1.clone();
413 let c = self.c2.clone();
414
415 let s0 = a.square(cs.ns(|| "s0"))?;
416 let ab = a.mul(cs.ns(|| "ab"), &b)?;
417 let s1 = ab.double(cs.ns(|| "s1"))?;
418 let s2 = a
419 .sub(cs.ns(|| "a-b"), &b)?
420 .add(cs.ns(|| "plus c"), &c)?
421 .square(cs.ns(|| "s2"))?;
422 let s3 = b.mul(cs.ns(|| "bc"), &c)?.double(cs.ns(|| "s3"))?;
423 let s4 = c.square(cs.ns(|| "s4"))?;
424
425 let c0 = Self::mul_fp2_gadget_by_nonresidue(cs.ns(|| "c0 part 1"), &s3)?
426 .add(cs.ns(|| "c0"), &s0)?;
427
428 let c1 = Self::mul_fp2_gadget_by_nonresidue(cs.ns(|| "c1 part 1"), &s4)?
429 .add(cs.ns(|| "c1"), &s1)?;
430
431 let c2 = s1
432 .add(cs.ns(|| "c2 part1"), &s2)?
433 .add(cs.ns(|| "c2 part2"), &s3)?
434 .sub(cs.ns(|| "c2 part3"), &s0)?
435 .sub(cs.ns(|| "c2 part4"), &s4)?;
436
437 Ok(Self::new(c0, c1, c2))
438 }
439
440 #[inline]
441 fn mul_equals<CS: ConstraintSystem<ConstraintF>>(
442 &self,
443 mut cs: CS,
444 other: &Self,
445 result: &Self,
446 ) -> Result<(), SynthesisError> {
447 // Karatsuba multiplication for Fp3:
448 // v0 = A.c0 * B.c0
449 // v1 = A.c1 * B.c1
450 // v2 = A.c2 * B.c2
451 // result.c0 = v0 + β((a1 + a2)(b1 + b2) − v1 − v2)
452 // result.c1 = (a0 + a1)(b0 + b1) − v0 − v1 + βv2
453 // result.c2 = (a0 + a2)(b0 + b2) − v0 + v1 − v2,
454 // We enforce this with six constraints:
455 //
456 // v0 = A.c0 * B.c0
457 // v1 = A.c1 * B.c1
458 // v2 = A.c2 * B.c2
459 //
460 // result.c0 - v0 + \beta*(v1 + v2) = β(a1 + a2)(b1 + b2))
461 // result.c1 + v0 + v1 - βv2 = (a0 + a1)(b0 + b1)
462 // result.c2 + v0 - v1 + v2 = (a0 + a2)(b0 + b2)
463 // Reference:
464 // "Multiplication and Squaring on Pairing-Friendly Fields"
465 // Devegili, OhEigeartaigh, Scott, Dahab
466 //
467 // This implementation adapted from
468 // https://github.com/ZencashOfficial/ginger-lib/blob/development/r1cs/gadgets/std/src/fields/fp3.rs
469 let v0 = self.c0.mul(cs.ns(|| "v0 = a0 * b0"), &other.c0)?;
470 let v1 = self.c1.mul(cs.ns(|| "v1 = a1 * b1"), &other.c1)?;
471 let v2 = self.c2.mul(cs.ns(|| "v2 = a2 * b2"), &other.c2)?;
472
473 // Check c0
474 let nr_a1_plus_a2 = self
475 .c1
476 .add(cs.ns(|| "a1 + a2"), &self.c2)?
477 .mul_by_constant(cs.ns(|| "nr*(a1 + a2)"), &P::NONRESIDUE)?;
478 let b1_plus_b2 = other.c1.add(cs.ns(|| "b1 + b2"), &other.c2)?;
479 let nr_v1 = v1.mul_by_constant(cs.ns(|| "nr * v1"), &P::NONRESIDUE)?;
480 let nr_v2 = v2.mul_by_constant(cs.ns(|| "nr * v2"), &P::NONRESIDUE)?;
481 let to_check = result
482 .c0
483 .sub(cs.ns(|| "c0 - v0"), &v0)?
484 .add(cs.ns(|| "c0 - v0 + nr * v1"), &nr_v1)?
485 .add(cs.ns(|| "c0 - v0 + nr * v1 + nr * v2"), &nr_v2)?;
486 nr_a1_plus_a2.mul_equals(cs.ns(|| "check c0"), &b1_plus_b2, &to_check)?;
487
488 // Check c1
489 let a0_plus_a1 = self.c0.add(cs.ns(|| "a0 + a1"), &self.c1)?;
490 let b0_plus_b1 = other.c0.add(cs.ns(|| "b0 + b1"), &other.c1)?;
491 let to_check = result
492 .c1
493 .sub(cs.ns(|| "c1 - nr * v2"), &nr_v2)?
494 .add(cs.ns(|| "c1 - nr * v2 + v0"), &v0)?
495 .add(cs.ns(|| "c1 - nr * v2 + v0 + v1"), &v1)?;
496 a0_plus_a1.mul_equals(cs.ns(|| "check c1"), &b0_plus_b1, &to_check)?;
497
498 // Check c2
499 let a0_plus_a2 = self.c0.add(cs.ns(|| "a0 + a2"), &self.c2)?;
500 let b0_plus_b2 = other.c0.add(cs.ns(|| "b0 + b2"), &other.c2)?;
501 let to_check = result
502 .c2
503 .add(cs.ns(|| "c2 + v0"), &v0)?
504 .sub(cs.ns(|| "c2 + v0 - v1"), &v1)?
505 .add(cs.ns(|| "c2 + v0 - v1 + v2"), &v2)?;
506 a0_plus_a2.mul_equals(cs.ns(|| "check c2"), &b0_plus_b2, &to_check)?;
507 Ok(())
508 }
509
510 #[inline]
511 fn add_constant<CS: ConstraintSystem<ConstraintF>>(
512 &self,
513 mut cs: CS,
514 other: &Fp6<P>,
515 ) -> Result<Self, SynthesisError> {
516 let c0 = self.c0.add_constant(cs.ns(|| "c0"), &other.c0)?;
517 let c1 = self.c1.add_constant(cs.ns(|| "c1"), &other.c1)?;
518 let c2 = self.c2.add_constant(cs.ns(|| "c2"), &other.c2)?;
519
520 Ok(Self::new(c0, c1, c2))
521 }
522
523 #[inline]
524 fn add_constant_in_place<CS: ConstraintSystem<ConstraintF>>(
525 &mut self,
526 mut cs: CS,
527 other: &Fp6<P>,
528 ) -> Result<&mut Self, SynthesisError> {
529 self.c0.add_constant_in_place(cs.ns(|| "c0"), &other.c0)?;
530 self.c1.add_constant_in_place(cs.ns(|| "c1"), &other.c1)?;
531 self.c2.add_constant_in_place(cs.ns(|| "c2"), &other.c2)?;
532 Ok(self)
533 }
534
535 /// Use the Toom-Cook-3x method to compute multiplication.
536 #[inline]
537 fn mul_by_constant<CS: ConstraintSystem<ConstraintF>>(
538 &self,
539 mut cs: CS,
540 other: &Fp6<P>,
541 ) -> Result<Self, SynthesisError> {
542 // Uses Toom-Cook-3x multiplication from
543 //
544 // Reference:
545 // "Multiplication and Squaring on Pairing-Friendly Fields"
546 // Devegili, OhEigeartaigh, Scott, Dahab
547
548 // v0 = a(0)b(0) = a0 * b0
549 let v0 = self.c0.mul_by_constant(cs.ns(|| "v0"), &other.c0)?;
550
551 // v1 = a(1)b(1) = (a0 + a1 + a2)(b0 + b1 + b2)
552 let v1 = {
553 let mut v1_cs = cs.ns(|| "v1");
554 let mut a0_plus_a1_plus_a2 = self
555 .c0
556 .add(v1_cs.ns(|| "a0 + a1"), &self.c1)?
557 .add(v1_cs.ns(|| "a0 + a1 + a2"), &self.c2)?;
558 let b0_plus_b1_plus_b2 = other.c0 + &other.c1 + &other.c2;
559
560 a0_plus_a1_plus_a2.mul_by_constant_in_place(
561 v1_cs.ns(|| "(a0 + a1 + a2)*(b0 + b1 + b2)"),
562 &b0_plus_b1_plus_b2,
563 )?;
564 a0_plus_a1_plus_a2
565 };
566
567 // v2 = a(−1)b(−1) = (a0 − a1 + a2)(b0 − b1 + b2)
568 let mut v2 = {
569 let mut v2_cs = cs.ns(|| "v2");
570 let mut a0_minus_a1_plus_a2 = self
571 .c0
572 .sub(v2_cs.ns(|| "sub1"), &self.c1)?
573 .add(v2_cs.ns(|| "add2"), &self.c2)?;
574 let b0_minus_b1_plus_b2 = other.c0 - &other.c1 + &other.c2;
575 a0_minus_a1_plus_a2.mul_by_constant_in_place(
576 v2_cs.ns(|| "(a0 - a1 + a2)*(b0 - b1 + b2)"),
577 &b0_minus_b1_plus_b2,
578 )?;
579 a0_minus_a1_plus_a2
580 };
581
582 // v3 = a(2)b(2) = (a0 + 2a1 + 4a2)(b0 + 2b1 + 4b2)
583 let mut v3 = {
584 let mut v3_cs = cs.ns(|| "v3");
585 let a1_double = self.c1.double(v3_cs.ns(|| "2a1"))?;
586 let a2_quad = self
587 .c2
588 .double(v3_cs.ns(|| "2a2"))?
589 .double(v3_cs.ns(|| "4a2"))?;
590 let mut a0_plus_2_a1_plus_4_a2 = self
591 .c0
592 .add(v3_cs.ns(|| "a0 + 2a1"), &a1_double)?
593 .add(v3_cs.ns(|| "a0 + 2a1 + 4a2"), &a2_quad)?;
594
595 let b1_double = other.c1.double();
596 let b2_quad = other.c2.double().double();
597 let b0_plus_2_b1_plus_4_b2 = other.c0 + &b1_double + &b2_quad;
598
599 a0_plus_2_a1_plus_4_a2.mul_by_constant_in_place(
600 v3_cs.ns(|| "(a0 + 2a1 + 4a2)*(b0 + 2b1 + 4b2)"),
601 &b0_plus_2_b1_plus_4_b2,
602 )?;
603 a0_plus_2_a1_plus_4_a2
604 };
605
606 // v4 = a(∞)b(∞) = a2 * b2
607 let v4 = self.c2.mul_by_constant(cs.ns(|| "v4"), &other.c2)?;
608
609 let two = <P::Fp2Params as Fp2Parameters>::Fp::one().double();
610 let six = two.double() + &two;
611 let mut two_and_six = [two, six];
612 algebra::fields::batch_inversion(&mut two_and_six);
613 let (two_inverse, six_inverse) = (two_and_six[0], two_and_six[1]);
614
615 let mut half_v0 = v0.mul_by_fp_constant(cs.ns(|| "half_v0"), &two_inverse)?;
616 let half_v1 = v1.mul_by_fp_constant(cs.ns(|| "half_v1"), &two_inverse)?;
617 let mut one_sixth_v2 = v2.mul_by_fp_constant(cs.ns(|| "v2_by_6"), &six_inverse)?;
618 let one_sixth_v3 = v3.mul_by_fp_constant_in_place(cs.ns(|| "v3_by_6"), &six_inverse)?;
619 let two_v4 = v4.double(cs.ns(|| "2v4"))?;
620
621 // c0 = v0 + β((1/2)v0 − (1/2)v1 − (1/6)v2 + (1/6)v3 − 2v4)
622 let c0 = {
623 let mut c0_cs = cs.ns(|| "c0");
624
625 // No constraints, only get a linear combination back.
626 let mut inner = half_v0
627 .sub(c0_cs.ns(|| "sub1"), &half_v1)?
628 .sub(c0_cs.ns(|| "sub2"), &one_sixth_v2)?
629 .add(c0_cs.ns(|| "add3"), &one_sixth_v3)?
630 .sub(c0_cs.ns(|| "sub4"), &two_v4)?;
631 let non_residue_times_inner =
632 inner.mul_by_constant_in_place(&mut c0_cs, &P::NONRESIDUE)?;
633 v0.add(c0_cs.ns(|| "add5"), non_residue_times_inner)?
634 };
635
636 // −(1/2)v0 + v1 − (1/3)v2 − (1/6)v3 + 2v4 + βv4
637 let c1 = {
638 let mut c1_cs = cs.ns(|| "c1");
639 let one_third_v2 = one_sixth_v2.double_in_place(c1_cs.ns(|| "double1"))?;
640 let non_residue_v4 =
641 v4.mul_by_constant(c1_cs.ns(|| "mul_by_const1"), &P::NONRESIDUE)?;
642
643 half_v0
644 .negate_in_place(c1_cs.ns(|| "neg1"))?
645 .add(c1_cs.ns(|| "add1"), &v1)?
646 .sub(c1_cs.ns(|| "sub2"), one_third_v2)?
647 .sub(c1_cs.ns(|| "sub3"), &one_sixth_v3)?
648 .add(c1_cs.ns(|| "add4"), &two_v4)?
649 .add(c1_cs.ns(|| "add5"), &non_residue_v4)?
650 };
651
652 // -v0 + (1/2)v1 + (1/2)v2 −v4
653 let c2 = {
654 let mut c2_cs = cs.ns(|| "c2");
655 let half_v2 = v2.mul_by_fp_constant_in_place(c2_cs.ns(|| "half_v2"), &two_inverse)?;
656 half_v1
657 .add(c2_cs.ns(|| "add1"), half_v2)?
658 .sub(c2_cs.ns(|| "sub2"), &v4)?
659 .sub(c2_cs.ns(|| "sub3"), &v0)?
660 };
661
662 Ok(Self::new(c0, c1, c2))
663 }
664
665 fn frobenius_map<CS: ConstraintSystem<ConstraintF>>(
666 &self,
667 cs: CS,
668 power: usize,
669 ) -> Result<Self, SynthesisError> {
670 let mut result = self.clone();
671 result.frobenius_map_in_place(cs, power)?;
672 Ok(result)
673 }
674
675 fn frobenius_map_in_place<CS: ConstraintSystem<ConstraintF>>(
676 &mut self,
677 mut cs: CS,
678 power: usize,
679 ) -> Result<&mut Self, SynthesisError> {
680 self.c0.frobenius_map_in_place(&mut cs.ns(|| "c0"), power)?;
681 self.c1.frobenius_map_in_place(&mut cs.ns(|| "c1"), power)?;
682 self.c2.frobenius_map_in_place(&mut cs.ns(|| "c2"), power)?;
683
684 self.c1.mul_by_constant_in_place(
685 cs.ns(|| "c1_power"),
686 &P::FROBENIUS_COEFF_FP6_C1[power % 6],
687 )?;
688 self.c2.mul_by_constant_in_place(
689 cs.ns(|| "c2_power"),
690 &P::FROBENIUS_COEFF_FP6_C2[power % 6],
691 )?;
692
693 Ok(self)
694 }
695
696 fn cost_of_mul() -> usize {
697 5 * Fp2Gadget::<P, ConstraintF>::cost_of_mul()
698 }
699
700 fn cost_of_mul_equals() -> usize {
701 6 * Fp2Gadget::<P, ConstraintF>::cost_of_mul()
702 }
703}
704
705impl<P, ConstraintF: PrimeField> PartialEq for Fp6Gadget<P, ConstraintF>
706where
707 P: Fp6Parameters,
708 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
709{
710 fn eq(&self, other: &Self) -> bool {
711 self.c0 == other.c0 && self.c1 == other.c1 && self.c2 == other.c2
712 }
713}
714
715impl<P, ConstraintF: PrimeField> Eq for Fp6Gadget<P, ConstraintF>
716where
717 P: Fp6Parameters,
718 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
719{
720}
721
722impl<P, ConstraintF: PrimeField> EqGadget<ConstraintF> for Fp6Gadget<P, ConstraintF>
723where
724 P: Fp6Parameters,
725 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
726{
727}
728
729impl<P, ConstraintF: PrimeField> ConditionalEqGadget<ConstraintF> for Fp6Gadget<P, ConstraintF>
730where
731 P: Fp6Parameters,
732 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
733{
734 #[inline]
735 fn conditional_enforce_equal<CS: ConstraintSystem<ConstraintF>>(
736 &self,
737 mut cs: CS,
738 other: &Self,
739 condition: &Boolean,
740 ) -> Result<(), SynthesisError> {
741 self.c0
742 .conditional_enforce_equal(&mut cs.ns(|| "c0"), &other.c0, condition)?;
743 self.c1
744 .conditional_enforce_equal(&mut cs.ns(|| "c1"), &other.c1, condition)?;
745 self.c2
746 .conditional_enforce_equal(&mut cs.ns(|| "c2"), &other.c2, condition)?;
747 Ok(())
748 }
749
750 fn cost() -> usize {
751 3 * <Fp2Gadget<P, ConstraintF> as ConditionalEqGadget<ConstraintF>>::cost()
752 }
753}
754
755impl<P, ConstraintF: PrimeField> NEqGadget<ConstraintF> for Fp6Gadget<P, ConstraintF>
756where
757 P: Fp6Parameters,
758 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
759{
760 #[inline]
761 fn enforce_not_equal<CS: ConstraintSystem<ConstraintF>>(
762 &self,
763 mut cs: CS,
764 other: &Self,
765 ) -> Result<(), SynthesisError> {
766 self.c0.enforce_not_equal(&mut cs.ns(|| "c0"), &other.c0)?;
767 self.c1.enforce_not_equal(&mut cs.ns(|| "c1"), &other.c1)?;
768 self.c2.enforce_not_equal(&mut cs.ns(|| "c2"), &other.c2)?;
769 Ok(())
770 }
771
772 fn cost() -> usize {
773 3 * <Fp2Gadget<P, ConstraintF> as NEqGadget<ConstraintF>>::cost()
774 }
775}
776
777impl<P, ConstraintF: PrimeField> ToBitsGadget<ConstraintF> for Fp6Gadget<P, ConstraintF>
778where
779 P: Fp6Parameters,
780 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
781{
782 fn to_bits<CS: ConstraintSystem<ConstraintF>>(
783 &self,
784 mut cs: CS,
785 ) -> Result<Vec<Boolean>, SynthesisError> {
786 let mut c0 = self.c0.to_bits(cs.ns(|| "c0"))?;
787 let mut c1 = self.c1.to_bits(cs.ns(|| "c1"))?;
788 let mut c2 = self.c2.to_bits(cs.ns(|| "c2"))?;
789
790 c0.append(&mut c1);
791 c0.append(&mut c2);
792
793 Ok(c0)
794 }
795
796 fn to_non_unique_bits<CS: ConstraintSystem<ConstraintF>>(
797 &self,
798 mut cs: CS,
799 ) -> Result<Vec<Boolean>, SynthesisError> {
800 let mut c0 = self.c0.to_non_unique_bits(cs.ns(|| "c0"))?;
801 let mut c1 = self.c1.to_non_unique_bits(cs.ns(|| "c1"))?;
802 let mut c2 = self.c2.to_non_unique_bits(cs.ns(|| "c2"))?;
803
804 c0.append(&mut c1);
805 c0.append(&mut c2);
806
807 Ok(c0)
808 }
809}
810
811impl<P, ConstraintF: PrimeField> ToBytesGadget<ConstraintF> for Fp6Gadget<P, ConstraintF>
812where
813 P: Fp6Parameters,
814 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
815{
816 fn to_bytes<CS: ConstraintSystem<ConstraintF>>(
817 &self,
818 mut cs: CS,
819 ) -> Result<Vec<UInt8>, SynthesisError> {
820 let mut c0 = self.c0.to_bytes(cs.ns(|| "c0"))?;
821 let mut c1 = self.c1.to_bytes(cs.ns(|| "c1"))?;
822 let mut c2 = self.c2.to_bytes(cs.ns(|| "c2"))?;
823
824 c0.append(&mut c1);
825 c0.append(&mut c2);
826
827 Ok(c0)
828 }
829
830 fn to_non_unique_bytes<CS: ConstraintSystem<ConstraintF>>(
831 &self,
832 mut cs: CS,
833 ) -> Result<Vec<UInt8>, SynthesisError> {
834 let mut c0 = self.c0.to_non_unique_bytes(cs.ns(|| "c0"))?;
835 let mut c1 = self.c1.to_non_unique_bytes(cs.ns(|| "c1"))?;
836 let mut c2 = self.c2.to_non_unique_bytes(cs.ns(|| "c2"))?;
837
838 c0.append(&mut c1);
839 c0.append(&mut c2);
840
841 Ok(c0)
842 }
843}
844
845impl<P, ConstraintF: PrimeField> Clone for Fp6Gadget<P, ConstraintF>
846where
847 P: Fp6Parameters,
848 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
849{
850 fn clone(&self) -> Self {
851 Self::new(self.c0.clone(), self.c1.clone(), self.c2.clone())
852 }
853}
854
855impl<P, ConstraintF: PrimeField> CondSelectGadget<ConstraintF> for Fp6Gadget<P, ConstraintF>
856where
857 P: Fp6Parameters,
858 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
859{
860 #[inline]
861 fn conditionally_select<CS: ConstraintSystem<ConstraintF>>(
862 mut cs: CS,
863 cond: &Boolean,
864 true_value: &Self,
865 false_value: &Self,
866 ) -> Result<Self, SynthesisError> {
867 let c0 = Fp2Gadget::<P, ConstraintF>::conditionally_select(
868 &mut cs.ns(|| "c0"),
869 cond,
870 &true_value.c0,
871 &false_value.c0,
872 )?;
873 let c1 = Fp2Gadget::<P, ConstraintF>::conditionally_select(
874 &mut cs.ns(|| "c1"),
875 cond,
876 &true_value.c1,
877 &false_value.c1,
878 )?;
879 let c2 = Fp2Gadget::<P, ConstraintF>::conditionally_select(
880 &mut cs.ns(|| "c2"),
881 cond,
882 &true_value.c2,
883 &false_value.c2,
884 )?;
885
886 Ok(Self::new(c0, c1, c2))
887 }
888
889 fn cost() -> usize {
890 3 * <Fp2Gadget<P, ConstraintF> as CondSelectGadget<ConstraintF>>::cost()
891 }
892}
893
894impl<P, ConstraintF: PrimeField> TwoBitLookupGadget<ConstraintF> for Fp6Gadget<P, ConstraintF>
895where
896 P: Fp6Parameters,
897 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
898{
899 type TableConstant = Fp6<P>;
900 fn two_bit_lookup<CS: ConstraintSystem<ConstraintF>>(
901 mut cs: CS,
902 b: &[Boolean],
903 c: &[Self::TableConstant],
904 ) -> Result<Self, SynthesisError> {
905 let c0s = c.iter().map(|f| f.c0).collect::<Vec<_>>();
906 let c1s = c.iter().map(|f| f.c1).collect::<Vec<_>>();
907 let c2s = c.iter().map(|f| f.c2).collect::<Vec<_>>();
908 let c0 = Fp2Gadget::<P, ConstraintF>::two_bit_lookup(cs.ns(|| "Lookup c0"), b, &c0s)?;
909 let c1 = Fp2Gadget::<P, ConstraintF>::two_bit_lookup(cs.ns(|| "Lookup c1"), b, &c1s)?;
910 let c2 = Fp2Gadget::<P, ConstraintF>::two_bit_lookup(cs.ns(|| "Lookup c2"), b, &c2s)?;
911 Ok(Self::new(c0, c1, c2))
912 }
913
914 fn cost() -> usize {
915 3 * <Fp2Gadget<P, ConstraintF> as TwoBitLookupGadget<ConstraintF>>::cost()
916 }
917}
918
919impl<P, ConstraintF: PrimeField> ThreeBitCondNegLookupGadget<ConstraintF>
920 for Fp6Gadget<P, ConstraintF>
921where
922 P: Fp6Parameters,
923 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
924{
925 type TableConstant = Fp6<P>;
926
927 fn three_bit_cond_neg_lookup<CS: ConstraintSystem<ConstraintF>>(
928 mut cs: CS,
929 b: &[Boolean],
930 b0b1: &Boolean,
931 c: &[Self::TableConstant],
932 ) -> Result<Self, SynthesisError> {
933 let c0s = c.iter().map(|f| f.c0).collect::<Vec<_>>();
934 let c1s = c.iter().map(|f| f.c1).collect::<Vec<_>>();
935 let c2s = c.iter().map(|f| f.c2).collect::<Vec<_>>();
936 let c0 = Fp2Gadget::<P, ConstraintF>::three_bit_cond_neg_lookup(
937 cs.ns(|| "Lookup c0"),
938 b,
939 b0b1,
940 &c0s,
941 )?;
942 let c1 = Fp2Gadget::<P, ConstraintF>::three_bit_cond_neg_lookup(
943 cs.ns(|| "Lookup c1"),
944 b,
945 b0b1,
946 &c1s,
947 )?;
948 let c2 = Fp2Gadget::<P, ConstraintF>::three_bit_cond_neg_lookup(
949 cs.ns(|| "Lookup c2"),
950 b,
951 b0b1,
952 &c2s,
953 )?;
954 Ok(Self::new(c0, c1, c2))
955 }
956
957 fn cost() -> usize {
958 3 * <Fp2Gadget<P, ConstraintF> as ThreeBitCondNegLookupGadget<ConstraintF>>::cost()
959 }
960}
961
962impl<P, ConstraintF: PrimeField> AllocGadget<Fp6<P>, ConstraintF> for Fp6Gadget<P, ConstraintF>
963where
964 P: Fp6Parameters,
965 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
966{
967 #[inline]
968 fn alloc_constant<T, CS: ConstraintSystem<ConstraintF>>(
969 mut cs: CS,
970 t: T,
971 ) -> Result<Self, SynthesisError>
972 where
973 T: Borrow<Fp6<P>>,
974 {
975 Self::zero(cs.ns(|| "zero"))?.add_constant(cs.ns(|| "add constant"), t.borrow())
976 }
977
978 #[inline]
979 fn alloc<F, T, CS: ConstraintSystem<ConstraintF>>(
980 mut cs: CS,
981 value_gen: F,
982 ) -> Result<Self, SynthesisError>
983 where
984 F: FnOnce() -> Result<T, SynthesisError>,
985 T: Borrow<Fp6<P>>,
986 {
987 let (c0, c1, c2) = match value_gen() {
988 Ok(fe) => {
989 let fe = *fe.borrow();
990 (Ok(fe.c0), Ok(fe.c1), Ok(fe.c2))
991 }
992 _ => (
993 Err(SynthesisError::AssignmentMissing),
994 Err(SynthesisError::AssignmentMissing),
995 Err(SynthesisError::AssignmentMissing),
996 ),
997 };
998
999 let c0 = Fp2Gadget::<P, ConstraintF>::alloc(&mut cs.ns(|| "c0"), || c0)?;
1000 let c1 = Fp2Gadget::<P, ConstraintF>::alloc(&mut cs.ns(|| "c1"), || c1)?;
1001 let c2 = Fp2Gadget::<P, ConstraintF>::alloc(&mut cs.ns(|| "c2"), || c2)?;
1002 Ok(Self::new(c0, c1, c2))
1003 }
1004
1005 #[inline]
1006 fn alloc_input<F, T, CS: ConstraintSystem<ConstraintF>>(
1007 mut cs: CS,
1008 value_gen: F,
1009 ) -> Result<Self, SynthesisError>
1010 where
1011 F: FnOnce() -> Result<T, SynthesisError>,
1012 T: Borrow<Fp6<P>>,
1013 {
1014 let (c0, c1, c2) = match value_gen() {
1015 Ok(fe) => {
1016 let fe = *fe.borrow();
1017 (Ok(fe.c0), Ok(fe.c1), Ok(fe.c2))
1018 }
1019 _ => (
1020 Err(SynthesisError::AssignmentMissing),
1021 Err(SynthesisError::AssignmentMissing),
1022 Err(SynthesisError::AssignmentMissing),
1023 ),
1024 };
1025
1026 let c0 = Fp2Gadget::<P, ConstraintF>::alloc_input(&mut cs.ns(|| "c0"), || c0)?;
1027 let c1 = Fp2Gadget::<P, ConstraintF>::alloc_input(&mut cs.ns(|| "c1"), || c1)?;
1028 let c2 = Fp2Gadget::<P, ConstraintF>::alloc_input(&mut cs.ns(|| "c2"), || c2)?;
1029 Ok(Self::new(c0, c1, c2))
1030 }
1031}