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