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