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