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