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