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