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