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