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