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::*, Assignment, 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-Cool-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 Toom-Cook-3x method to compute multiplication.
402 #[inline]
403 fn square<CS: ConstraintSystem<ConstraintF>>(
404 &self,
405 mut cs: CS,
406 ) -> Result<Self, SynthesisError> {
407 // Uses Toom-Cool-3x multiplication from
408 //
409 // Reference:
410 // "Multiplication and Squaring on Pairing-Friendly Fields"
411 // Devegili, OhEigeartaigh, Scott, Dahab
412
413 // v0 = a(0)^2 = a0^2
414 let v0 = self.c0.square(&mut cs.ns(|| "Calc v0"))?;
415
416 // v1 = a(1)^2 = (a0 + a1 + a2)^2
417 let v1 = {
418 let a0_plus_a1_plus_a2 = self
419 .c0
420 .add(cs.ns(|| "a0 + a1"), &self.c1)?
421 .add(cs.ns(|| "a0 + a1 + a2"), &self.c2)?;
422 a0_plus_a1_plus_a2.square(&mut cs.ns(|| "(a0 + a1 + a2)^2"))?
423 };
424
425 // v2 = a(−1)^2 = (a0 − a1 + a2)^2
426 let v2 = {
427 let a0_minus_a1_plus_a2 = self
428 .c0
429 .sub(cs.ns(|| "a0 - a1"), &self.c1)?
430 .add(cs.ns(|| "a0 - a2 + a2"), &self.c2)?;
431 a0_minus_a1_plus_a2.square(&mut cs.ns(|| "(a0 - a1 + a2)^2"))?
432 };
433
434 // v3 = a(2)^2 = (a0 + 2a1 + 4a2)^2
435 let v3 = {
436 let a1_double = self.c1.double(cs.ns(|| "2a1"))?;
437 let a2_quad = self.c2.double(cs.ns(|| "2a2"))?.double(cs.ns(|| "4a2"))?;
438 let a0_plus_2_a1_plus_4_a2 = self
439 .c0
440 .add(cs.ns(|| "a0 + 2a1"), &a1_double)?
441 .add(cs.ns(|| "a0 + 2a1 + 4a2"), &a2_quad)?;
442
443 a0_plus_2_a1_plus_4_a2.square(&mut cs.ns(|| "(a0 + 2a1 + 4a2)^2"))?
444 };
445
446 // v4 = a(∞)^2 = a2^2
447 let v4 = self.c2.square(&mut cs.ns(|| "a2^2"))?;
448
449 let two = <P::Fp2Params as Fp2Parameters>::Fp::one().double();
450 let six = two.double() + &two;
451 let mut two_and_six = [two, six];
452 algebra::fields::batch_inversion(&mut two_and_six);
453 let (two_inverse, six_inverse) = (two_and_six[0], two_and_six[1]);
454
455 let half_v0 = v0.mul_by_fp_constant(cs.ns(|| "half_v0"), &two_inverse)?;
456 let half_v1 = v1.mul_by_fp_constant(cs.ns(|| "half_v1"), &two_inverse)?;
457 let one_sixth_v2 = v2.mul_by_fp_constant(cs.ns(|| "one_sixth_v2"), &six_inverse)?;
458 let one_sixth_v3 = v3.mul_by_fp_constant(cs.ns(|| "one_sixth_v3"), &six_inverse)?;
459 let two_v4 = v4.double(cs.ns(|| "double_v4"))?;
460
461 // c0 = v0 + β((1/2)v0 − (1/2)v1 − (1/6)v2 + (1/6)v3 − 2v4)
462 let c0 = {
463 let mut c0_cs = cs.ns(|| "c0");
464 // No constraints, only get a linear combination back.
465 let inner = half_v0
466 .sub(c0_cs.ns(|| "sub1"), &half_v1)?
467 .sub(c0_cs.ns(|| "sub2"), &one_sixth_v2)?
468 .add(c0_cs.ns(|| "add3"), &one_sixth_v3)?
469 .sub(c0_cs.ns(|| "sub4"), &two_v4)?;
470 let non_residue_times_inner =
471 inner.mul_by_constant(c0_cs.ns(|| "mul_by_res"), &P::NONRESIDUE)?;
472 v0.add(c0_cs.ns(|| "add5"), &non_residue_times_inner)?
473 };
474
475 // −(1/2)v0 + v1 − (1/3)v2 − (1/6)v3 + 2v4 + βv4
476 let c1 = {
477 let mut c1_cs = cs.ns(|| "c1");
478 let one_third_v2 = one_sixth_v2.double(c1_cs.ns(|| "v2_by_3"))?;
479 let non_residue_v4 = v4.mul_by_constant(c1_cs.ns(|| "mul_by_res"), &P::NONRESIDUE)?;
480
481 half_v0
482 .negate(c1_cs.ns(|| "neg1"))?
483 .add(c1_cs.ns(|| "add1"), &v1)?
484 .sub(c1_cs.ns(|| "sub2"), &one_third_v2)?
485 .sub(c1_cs.ns(|| "sub3"), &one_sixth_v3)?
486 .add(c1_cs.ns(|| "add4"), &two_v4)?
487 .add(c1_cs.ns(|| "add5"), &non_residue_v4)?
488 };
489
490 // -v0 + (1/2)v1 + (1/2)v2 −v4
491 let c2 = {
492 let mut c2_cs = cs.ns(|| "c2");
493 let half_v2 = v2.mul_by_fp_constant(c2_cs.ns(|| "half_v2"), &two_inverse)?;
494 half_v1
495 .add(c2_cs.ns(|| "add1"), &half_v2)?
496 .sub(c2_cs.ns(|| "sub1"), &v4)?
497 .sub(c2_cs.ns(|| "sub2"), &v0)?
498 };
499
500 Ok(Self::new(c0, c1, c2))
501 }
502
503 // 18 constaints, we can probably do better but not sure it's worth it.
504 #[inline]
505 fn inverse<CS: ConstraintSystem<ConstraintF>>(
506 &self,
507 mut cs: CS,
508 ) -> Result<Self, SynthesisError> {
509 let inverse = Self::alloc(&mut cs.ns(|| "alloc inverse"), || {
510 self.get_value().and_then(|val| val.inverse()).get()
511 })?;
512 let one = Self::one(cs.ns(|| "one"))?;
513 inverse.mul_equals(cs.ns(|| "check inverse"), &self, &one)?;
514 Ok(inverse)
515 }
516
517 #[inline]
518 fn add_constant<CS: ConstraintSystem<ConstraintF>>(
519 &self,
520 mut cs: CS,
521 other: &Fp6<P>,
522 ) -> Result<Self, SynthesisError> {
523 let c0 = self.c0.add_constant(cs.ns(|| "c0"), &other.c0)?;
524 let c1 = self.c1.add_constant(cs.ns(|| "c1"), &other.c1)?;
525 let c2 = self.c2.add_constant(cs.ns(|| "c2"), &other.c2)?;
526
527 Ok(Self::new(c0, c1, c2))
528 }
529
530 #[inline]
531 fn add_constant_in_place<CS: ConstraintSystem<ConstraintF>>(
532 &mut self,
533 mut cs: CS,
534 other: &Fp6<P>,
535 ) -> Result<&mut Self, SynthesisError> {
536 self.c0.add_constant_in_place(cs.ns(|| "c0"), &other.c0)?;
537 self.c1.add_constant_in_place(cs.ns(|| "c1"), &other.c1)?;
538 self.c2.add_constant_in_place(cs.ns(|| "c2"), &other.c2)?;
539 Ok(self)
540 }
541
542 /// Use the Toom-Cook-3x method to compute multiplication.
543 #[inline]
544 fn mul_by_constant<CS: ConstraintSystem<ConstraintF>>(
545 &self,
546 mut cs: CS,
547 other: &Fp6<P>,
548 ) -> Result<Self, SynthesisError> {
549 // Uses Toom-Cook-3x multiplication from
550 //
551 // Reference:
552 // "Multiplication and Squaring on Pairing-Friendly Fields"
553 // Devegili, OhEigeartaigh, Scott, Dahab
554
555 // v0 = a(0)b(0) = a0 * b0
556 let v0 = self.c0.mul_by_constant(cs.ns(|| "v0"), &other.c0)?;
557
558 // v1 = a(1)b(1) = (a0 + a1 + a2)(b0 + b1 + b2)
559 let v1 = {
560 let mut v1_cs = cs.ns(|| "v1");
561 let mut a0_plus_a1_plus_a2 = self
562 .c0
563 .add(v1_cs.ns(|| "a0 + a1"), &self.c1)?
564 .add(v1_cs.ns(|| "a0 + a1 + a2"), &self.c2)?;
565 let b0_plus_b1_plus_b2 = other.c0 + &other.c1 + &other.c2;
566
567 a0_plus_a1_plus_a2.mul_by_constant_in_place(
568 v1_cs.ns(|| "(a0 + a1 + a2)*(b0 + b1 + b2)"),
569 &b0_plus_b1_plus_b2,
570 )?;
571 a0_plus_a1_plus_a2
572 };
573
574 // v2 = a(−1)b(−1) = (a0 − a1 + a2)(b0 − b1 + b2)
575 let mut v2 = {
576 let mut v2_cs = cs.ns(|| "v2");
577 let mut a0_minus_a1_plus_a2 = self
578 .c0
579 .sub(v2_cs.ns(|| "sub1"), &self.c1)?
580 .add(v2_cs.ns(|| "add2"), &self.c2)?;
581 let b0_minus_b1_plus_b2 = other.c0 - &other.c1 + &other.c2;
582 a0_minus_a1_plus_a2.mul_by_constant_in_place(
583 v2_cs.ns(|| "(a0 - a1 + a2)*(b0 - b1 + b2)"),
584 &b0_minus_b1_plus_b2,
585 )?;
586 a0_minus_a1_plus_a2
587 };
588
589 // v3 = a(2)b(2) = (a0 + 2a1 + 4a2)(b0 + 2b1 + 4b2)
590 let mut v3 = {
591 let mut v3_cs = cs.ns(|| "v3");
592 let a1_double = self.c1.double(v3_cs.ns(|| "2a1"))?;
593 let a2_quad = self
594 .c2
595 .double(v3_cs.ns(|| "2a2"))?
596 .double(v3_cs.ns(|| "4a2"))?;
597 let mut a0_plus_2_a1_plus_4_a2 = self
598 .c0
599 .add(v3_cs.ns(|| "a0 + 2a1"), &a1_double)?
600 .add(v3_cs.ns(|| "a0 + 2a1 + 4a2"), &a2_quad)?;
601
602 let b1_double = other.c1.double();
603 let b2_quad = other.c2.double().double();
604 let b0_plus_2_b1_plus_4_b2 = other.c0 + &b1_double + &b2_quad;
605
606 a0_plus_2_a1_plus_4_a2.mul_by_constant_in_place(
607 v3_cs.ns(|| "(a0 + 2a1 + 4a2)*(b0 + 2b1 + 4b2)"),
608 &b0_plus_2_b1_plus_4_b2,
609 )?;
610 a0_plus_2_a1_plus_4_a2
611 };
612
613 // v4 = a(∞)b(∞) = a2 * b2
614 let v4 = self.c2.mul_by_constant(cs.ns(|| "v4"), &other.c2)?;
615
616 let two = <P::Fp2Params as Fp2Parameters>::Fp::one().double();
617 let six = two.double() + &two;
618 let mut two_and_six = [two, six];
619 algebra::fields::batch_inversion(&mut two_and_six);
620 let (two_inverse, six_inverse) = (two_and_six[0], two_and_six[1]);
621
622 let mut half_v0 = v0.mul_by_fp_constant(cs.ns(|| "half_v0"), &two_inverse)?;
623 let half_v1 = v1.mul_by_fp_constant(cs.ns(|| "half_v1"), &two_inverse)?;
624 let mut one_sixth_v2 = v2.mul_by_fp_constant(cs.ns(|| "v2_by_6"), &six_inverse)?;
625 let one_sixth_v3 = v3.mul_by_fp_constant_in_place(cs.ns(|| "v3_by_6"), &six_inverse)?;
626 let two_v4 = v4.double(cs.ns(|| "2v4"))?;
627
628 // c0 = v0 + β((1/2)v0 − (1/2)v1 − (1/6)v2 + (1/6)v3 − 2v4)
629 let c0 = {
630 let mut c0_cs = cs.ns(|| "c0");
631
632 // No constraints, only get a linear combination back.
633 let mut inner = half_v0
634 .sub(c0_cs.ns(|| "sub1"), &half_v1)?
635 .sub(c0_cs.ns(|| "sub2"), &one_sixth_v2)?
636 .add(c0_cs.ns(|| "add3"), &one_sixth_v3)?
637 .sub(c0_cs.ns(|| "sub4"), &two_v4)?;
638 let non_residue_times_inner =
639 inner.mul_by_constant_in_place(&mut c0_cs, &P::NONRESIDUE)?;
640 v0.add(c0_cs.ns(|| "add5"), non_residue_times_inner)?
641 };
642
643 // −(1/2)v0 + v1 − (1/3)v2 − (1/6)v3 + 2v4 + βv4
644 let c1 = {
645 let mut c1_cs = cs.ns(|| "c1");
646 let one_third_v2 = one_sixth_v2.double_in_place(c1_cs.ns(|| "double1"))?;
647 let non_residue_v4 =
648 v4.mul_by_constant(c1_cs.ns(|| "mul_by_const1"), &P::NONRESIDUE)?;
649
650 half_v0
651 .negate_in_place(c1_cs.ns(|| "neg1"))?
652 .add(c1_cs.ns(|| "add1"), &v1)?
653 .sub(c1_cs.ns(|| "sub2"), one_third_v2)?
654 .sub(c1_cs.ns(|| "sub3"), &one_sixth_v3)?
655 .add(c1_cs.ns(|| "add4"), &two_v4)?
656 .add(c1_cs.ns(|| "add5"), &non_residue_v4)?
657 };
658
659 // -v0 + (1/2)v1 + (1/2)v2 −v4
660 let c2 = {
661 let mut c2_cs = cs.ns(|| "c2");
662 let half_v2 = v2.mul_by_fp_constant_in_place(c2_cs.ns(|| "half_v2"), &two_inverse)?;
663 half_v1
664 .add(c2_cs.ns(|| "add1"), half_v2)?
665 .sub(c2_cs.ns(|| "sub2"), &v4)?
666 .sub(c2_cs.ns(|| "sub3"), &v0)?
667 };
668
669 Ok(Self::new(c0, c1, c2))
670 }
671
672 fn frobenius_map<CS: ConstraintSystem<ConstraintF>>(
673 &self,
674 cs: CS,
675 power: usize,
676 ) -> Result<Self, SynthesisError> {
677 let mut result = self.clone();
678 result.frobenius_map_in_place(cs, power)?;
679 Ok(result)
680 }
681
682 fn frobenius_map_in_place<CS: ConstraintSystem<ConstraintF>>(
683 &mut self,
684 mut cs: CS,
685 power: usize,
686 ) -> Result<&mut Self, SynthesisError> {
687 self.c0.frobenius_map_in_place(&mut cs.ns(|| "c0"), power)?;
688 self.c1.frobenius_map_in_place(&mut cs.ns(|| "c1"), power)?;
689 self.c2.frobenius_map_in_place(&mut cs.ns(|| "c2"), power)?;
690
691 self.c1.mul_by_constant_in_place(
692 cs.ns(|| "c1_power"),
693 &P::FROBENIUS_COEFF_FP6_C1[power % 6],
694 )?;
695 self.c2.mul_by_constant_in_place(
696 cs.ns(|| "c2_power"),
697 &P::FROBENIUS_COEFF_FP6_C2[power % 6],
698 )?;
699
700 Ok(self)
701 }
702
703 fn cost_of_mul() -> usize {
704 5 * Fp2Gadget::<P, ConstraintF>::cost_of_mul()
705 }
706
707 fn cost_of_inv() -> usize {
708 Self::cost_of_mul() + <Self as EqGadget<ConstraintF>>::cost()
709 }
710}
711
712impl<P, ConstraintF: PrimeField> PartialEq for Fp6Gadget<P, ConstraintF>
713where
714 P: Fp6Parameters,
715 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
716{
717 fn eq(&self, other: &Self) -> bool {
718 self.c0 == other.c0 && self.c1 == other.c1 && self.c2 == other.c2
719 }
720}
721
722impl<P, ConstraintF: PrimeField> Eq for Fp6Gadget<P, ConstraintF>
723where
724 P: Fp6Parameters,
725 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
726{
727}
728
729impl<P, ConstraintF: PrimeField> EqGadget<ConstraintF> for Fp6Gadget<P, ConstraintF>
730where
731 P: Fp6Parameters,
732 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
733{
734}
735
736impl<P, ConstraintF: PrimeField> ConditionalEqGadget<ConstraintF> for Fp6Gadget<P, ConstraintF>
737where
738 P: Fp6Parameters,
739 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
740{
741 #[inline]
742 fn conditional_enforce_equal<CS: ConstraintSystem<ConstraintF>>(
743 &self,
744 mut cs: CS,
745 other: &Self,
746 condition: &Boolean,
747 ) -> Result<(), SynthesisError> {
748 self.c0
749 .conditional_enforce_equal(&mut cs.ns(|| "c0"), &other.c0, condition)?;
750 self.c1
751 .conditional_enforce_equal(&mut cs.ns(|| "c1"), &other.c1, condition)?;
752 self.c2
753 .conditional_enforce_equal(&mut cs.ns(|| "c2"), &other.c2, condition)?;
754 Ok(())
755 }
756
757 fn cost() -> usize {
758 3 * <Fp2Gadget<P, ConstraintF> as ConditionalEqGadget<ConstraintF>>::cost()
759 }
760}
761
762impl<P, ConstraintF: PrimeField> NEqGadget<ConstraintF> for Fp6Gadget<P, ConstraintF>
763where
764 P: Fp6Parameters,
765 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
766{
767 #[inline]
768 fn enforce_not_equal<CS: ConstraintSystem<ConstraintF>>(
769 &self,
770 mut cs: CS,
771 other: &Self,
772 ) -> Result<(), SynthesisError> {
773 self.c0.enforce_not_equal(&mut cs.ns(|| "c0"), &other.c0)?;
774 self.c1.enforce_not_equal(&mut cs.ns(|| "c1"), &other.c1)?;
775 self.c2.enforce_not_equal(&mut cs.ns(|| "c2"), &other.c2)?;
776 Ok(())
777 }
778
779 fn cost() -> usize {
780 3 * <Fp2Gadget<P, ConstraintF> as NEqGadget<ConstraintF>>::cost()
781 }
782}
783
784impl<P, ConstraintF: PrimeField> ToBitsGadget<ConstraintF> for Fp6Gadget<P, ConstraintF>
785where
786 P: Fp6Parameters,
787 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
788{
789 fn to_bits<CS: ConstraintSystem<ConstraintF>>(
790 &self,
791 mut cs: CS,
792 ) -> Result<Vec<Boolean>, SynthesisError> {
793 let mut c0 = self.c0.to_bits(cs.ns(|| "c0"))?;
794 let mut c1 = self.c1.to_bits(cs.ns(|| "c1"))?;
795 let mut c2 = self.c2.to_bits(cs.ns(|| "c2"))?;
796
797 c0.append(&mut c1);
798 c0.append(&mut c2);
799
800 Ok(c0)
801 }
802
803 fn to_bits_strict<CS: ConstraintSystem<ConstraintF>>(
804 &self,
805 mut cs: CS,
806 ) -> Result<Vec<Boolean>, SynthesisError> {
807 let mut c0 = self.c0.to_bits_strict(cs.ns(|| "c0"))?;
808 let mut c1 = self.c1.to_bits_strict(cs.ns(|| "c1"))?;
809 let mut c2 = self.c2.to_bits_strict(cs.ns(|| "c2"))?;
810
811 c0.append(&mut c1);
812 c0.append(&mut c2);
813
814 Ok(c0)
815 }
816}
817
818impl<P, ConstraintF: PrimeField> ToBytesGadget<ConstraintF> for Fp6Gadget<P, ConstraintF>
819where
820 P: Fp6Parameters,
821 P::Fp2Params: Fp2Parameters<Fp = ConstraintF>,
822{
823 fn to_bytes<CS: ConstraintSystem<ConstraintF>>(
824 &self,
825 mut cs: CS,
826 ) -> Result<Vec<UInt8>, SynthesisError> {
827 let mut c0 = self.c0.to_bytes(cs.ns(|| "c0"))?;
828 let mut c1 = self.c1.to_bytes(cs.ns(|| "c1"))?;
829 let mut c2 = self.c2.to_bytes(cs.ns(|| "c2"))?;
830
831 c0.append(&mut c1);
832 c0.append(&mut c2);
833
834 Ok(c0)
835 }
836
837 fn to_bytes_strict<CS: ConstraintSystem<ConstraintF>>(
838 &self,
839 cs: CS,
840 ) -> Result<Vec<UInt8>, SynthesisError> {
841 self.to_bytes(cs)
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<F, T, CS: ConstraintSystem<ConstraintF>>(
969 mut cs: CS,
970 value_gen: F,
971 ) -> Result<Self, SynthesisError>
972 where
973 F: FnOnce() -> Result<T, SynthesisError>,
974 T: Borrow<Fp6<P>>,
975 {
976 let (c0, c1, c2) = match value_gen() {
977 Ok(fe) => {
978 let fe = *fe.borrow();
979 (Ok(fe.c0), Ok(fe.c1), Ok(fe.c2))
980 },
981 _ => (
982 Err(SynthesisError::AssignmentMissing),
983 Err(SynthesisError::AssignmentMissing),
984 Err(SynthesisError::AssignmentMissing),
985 ),
986 };
987
988 let c0 = Fp2Gadget::<P, ConstraintF>::alloc(&mut cs.ns(|| "c0"), || c0)?;
989 let c1 = Fp2Gadget::<P, ConstraintF>::alloc(&mut cs.ns(|| "c1"), || c1)?;
990 let c2 = Fp2Gadget::<P, ConstraintF>::alloc(&mut cs.ns(|| "c2"), || c2)?;
991 Ok(Self::new(c0, c1, c2))
992 }
993
994 #[inline]
995 fn alloc_input<F, T, CS: ConstraintSystem<ConstraintF>>(
996 mut cs: CS,
997 value_gen: F,
998 ) -> Result<Self, SynthesisError>
999 where
1000 F: FnOnce() -> Result<T, SynthesisError>,
1001 T: Borrow<Fp6<P>>,
1002 {
1003 let (c0, c1, c2) = match value_gen() {
1004 Ok(fe) => {
1005 let fe = *fe.borrow();
1006 (Ok(fe.c0), Ok(fe.c1), Ok(fe.c2))
1007 },
1008 _ => (
1009 Err(SynthesisError::AssignmentMissing),
1010 Err(SynthesisError::AssignmentMissing),
1011 Err(SynthesisError::AssignmentMissing),
1012 ),
1013 };
1014
1015 let c0 = Fp2Gadget::<P, ConstraintF>::alloc_input(&mut cs.ns(|| "c0"), || c0)?;
1016 let c1 = Fp2Gadget::<P, ConstraintF>::alloc_input(&mut cs.ns(|| "c1"), || c1)?;
1017 let c2 = Fp2Gadget::<P, ConstraintF>::alloc_input(&mut cs.ns(|| "c2"), || c2)?;
1018 Ok(Self::new(c0, c1, c2))
1019 }
1020}