ark-r1cs-std/r1cs-std/src/fields/quadratic_extension.rs
r1cs-std/src/fields/quadratic_extension.rsRaw
1use algebra::{
2 fields::{Field, QuadExtField, QuadExtParameters},
3 Zero,
4};
5use core::{borrow::Borrow, marker::PhantomData};
6use r1cs_core::{ConstraintSystemRef, Namespace, SynthesisError};
7
8use crate::fields::fp::FpVar;
9use crate::{
10 fields::{FieldOpsBounds, FieldVar},
11 prelude::*,
12 ToConstraintFieldGadget, Vec,
13};
14
15/// This struct is the `R1CS` equivalent of the quadratic extension field type
16/// in `algebra-core`, i.e. `algebra_core::QuadExtField`.
17#[derive(Derivative)]
18#[derivative(Debug(bound = "BF: core::fmt::Debug"), Clone(bound = "BF: Clone"))]
19#[must_use]
20pub struct QuadExtVar<BF: FieldVar<P::BaseField, P::BasePrimeField>, P: QuadExtVarParams<BF>>
21where
22 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
23{
24 /// The zero-th coefficient of this field element.
25 pub c0: BF,
26 /// The first coefficient of this field element.
27 pub c1: BF,
28 #[derivative(Debug = "ignore")]
29 _params: PhantomData<P>,
30}
31
32/// This trait describes parameters that are used to implement arithmetic for `QuadExtVar`.
33pub trait QuadExtVarParams<BF: FieldVar<Self::BaseField, Self::BasePrimeField>>:
34 QuadExtParameters
35where
36 for<'a> &'a BF: FieldOpsBounds<'a, Self::BaseField, BF>,
37{
38 /// Multiply the base field of the `QuadExtVar` by the appropriate Frobenius coefficient.
39 /// This is equivalent to `Self::mul_base_field_by_frob_coeff(power)`.
40 fn mul_base_field_var_by_frob_coeff(fe: &mut BF, power: usize);
41}
42
43impl<BF: FieldVar<P::BaseField, P::BasePrimeField>, P: QuadExtVarParams<BF>> QuadExtVar<BF, P>
44where
45 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
46{
47 /// Constructs a `QuadExtVar` from the underlying coefficients.
48 pub fn new(c0: BF, c1: BF) -> Self {
49 Self {
50 c0,
51 c1,
52 _params: PhantomData,
53 }
54 }
55
56 /// Multiplies a variable of the base field by the quadratic nonresidue `P::NONRESIDUE` that
57 /// is used to construct the extension field.
58 #[inline]
59 pub fn mul_base_field_by_nonresidue(fe: &BF) -> Result<BF, SynthesisError> {
60 Ok(fe * P::NONRESIDUE)
61 }
62
63 /// Multiplies `self` by a constant from the base field.
64 #[inline]
65 pub fn mul_by_base_field_constant(&self, fe: P::BaseField) -> Self {
66 let c0 = self.c0.clone() * fe;
67 let c1 = self.c1.clone() * fe;
68 QuadExtVar::new(c0, c1)
69 }
70
71 /// Sets `self = self.mul_by_base_field_constant(fe)`.
72 #[inline]
73 pub fn mul_assign_by_base_field_constant(&mut self, fe: P::BaseField) {
74 *self = (&*self).mul_by_base_field_constant(fe);
75 }
76
77 /// This is only to be used when the element is *known* to be in the cyclotomic subgroup.
78 #[inline]
79 pub fn unitary_inverse(&self) -> Result<Self, SynthesisError> {
80 Ok(Self::new(self.c0.clone(), self.c1.negate()?))
81 }
82
83 /// This is only to be used when the element is *known* to be in the cyclotomic subgroup.
84 #[inline]
85 #[tracing::instrument(target = "r1cs", skip(exponent))]
86 pub fn cyclotomic_exp(&self, exponent: impl AsRef<[u64]>) -> Result<Self, SynthesisError>
87 where
88 Self: FieldVar<QuadExtField<P>, P::BasePrimeField>,
89 {
90 use algebra::biginteger::arithmetic::find_wnaf;
91 let mut res = Self::one();
92 let self_inverse = self.unitary_inverse()?;
93
94 let mut found_nonzero = false;
95 let naf = find_wnaf(exponent.as_ref());
96
97 for &value in naf.iter().rev() {
98 if found_nonzero {
99 res.square_in_place()?;
100 }
101
102 if value != 0 {
103 found_nonzero = true;
104
105 if value > 0 {
106 res *= self;
107 } else {
108 res *= &self_inverse;
109 }
110 }
111 }
112
113 Ok(res)
114 }
115}
116
117impl<BF, P> R1CSVar<P::BasePrimeField> for QuadExtVar<BF, P>
118where
119 BF: FieldVar<P::BaseField, P::BasePrimeField>,
120 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
121 P: QuadExtVarParams<BF>,
122{
123 type Value = QuadExtField<P>;
124
125 fn cs(&self) -> ConstraintSystemRef<P::BasePrimeField> {
126 [&self.c0, &self.c1].cs()
127 }
128
129 #[inline]
130 fn value(&self) -> Result<Self::Value, SynthesisError> {
131 match (self.c0.value(), self.c1.value()) {
132 (Ok(c0), Ok(c1)) => Ok(QuadExtField::new(c0, c1)),
133 (..) => Err(SynthesisError::AssignmentMissing),
134 }
135 }
136}
137
138impl<BF, P> From<Boolean<P::BasePrimeField>> for QuadExtVar<BF, P>
139where
140 BF: FieldVar<P::BaseField, P::BasePrimeField>,
141 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
142 P: QuadExtVarParams<BF>,
143{
144 fn from(other: Boolean<P::BasePrimeField>) -> Self {
145 let c0 = BF::from(other);
146 let c1 = BF::zero();
147 Self::new(c0, c1)
148 }
149}
150
151impl<'a, BF, P> FieldOpsBounds<'a, QuadExtField<P>, QuadExtVar<BF, P>> for QuadExtVar<BF, P>
152where
153 BF: FieldVar<P::BaseField, P::BasePrimeField>,
154 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
155 P: QuadExtVarParams<BF>,
156{
157}
158impl<'a, BF, P> FieldOpsBounds<'a, QuadExtField<P>, QuadExtVar<BF, P>> for &'a QuadExtVar<BF, P>
159where
160 BF: FieldVar<P::BaseField, P::BasePrimeField>,
161 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
162 P: QuadExtVarParams<BF>,
163{
164}
165
166impl<BF, P> FieldVar<QuadExtField<P>, P::BasePrimeField> for QuadExtVar<BF, P>
167where
168 BF: FieldVar<P::BaseField, P::BasePrimeField>,
169 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
170 P: QuadExtVarParams<BF>,
171{
172 fn constant(other: QuadExtField<P>) -> Self {
173 let c0 = BF::constant(other.c0);
174 let c1 = BF::constant(other.c1);
175 Self::new(c0, c1)
176 }
177
178 fn zero() -> Self {
179 let c0 = BF::zero();
180 let c1 = BF::zero();
181 Self::new(c0, c1)
182 }
183
184 fn one() -> Self {
185 let c0 = BF::one();
186 let c1 = BF::zero();
187 Self::new(c0, c1)
188 }
189
190 #[inline]
191 #[tracing::instrument(target = "r1cs")]
192 fn double(&self) -> Result<Self, SynthesisError> {
193 let c0 = self.c0.double()?;
194 let c1 = self.c1.double()?;
195 Ok(Self::new(c0, c1))
196 }
197
198 #[inline]
199 #[tracing::instrument(target = "r1cs")]
200 fn negate(&self) -> Result<Self, SynthesisError> {
201 let mut result = self.clone();
202 result.c0.negate_in_place()?;
203 result.c1.negate_in_place()?;
204 Ok(result)
205 }
206
207 #[inline]
208 #[tracing::instrument(target = "r1cs")]
209 fn square(&self) -> Result<Self, SynthesisError> {
210 // From Libsnark/fp2_gadget.tcc
211 // Complex multiplication for Fp2:
212 // "Multiplication and Squaring on Pairing-Friendly Fields"
213 // Devegili, OhEigeartaigh, Scott, Dahab
214
215 // v0 = c0 - c1
216 let mut v0 = &self.c0 - &self.c1;
217 // v3 = c0 - beta * c1
218 let v3 = &self.c0 - &Self::mul_base_field_by_nonresidue(&self.c1)?;
219 // v2 = c0 * c1
220 let v2 = &self.c0 * &self.c1;
221
222 // v0 = (v0 * v3) + v2
223 v0 *= &v3;
224 v0 += &v2;
225
226 let c0 = &v0 + &Self::mul_base_field_by_nonresidue(&v2)?;
227 let c1 = v2.double()?;
228
229 Ok(Self::new(c0, c1))
230 }
231
232 #[tracing::instrument(target = "r1cs")]
233 fn mul_equals(&self, other: &Self, result: &Self) -> Result<(), SynthesisError> {
234 // Karatsuba multiplication for Fp2:
235 // v0 = A.c0 * B.c0
236 // v1 = A.c1 * B.c1
237 // result.c0 = v0 + non_residue * v1
238 // result.c1 = (A.c0 + A.c1) * (B.c0 + B.c1) - v0 - v1
239 // Enforced with 3 constraints:
240 // A.c1 * B.c1 = v1
241 // A.c0 * B.c0 = result.c0 - non_residue * v1
242 // (A.c0+A.c1)*(B.c0+B.c1) = result.c1 + result.c0 + (1 - non_residue) * v1
243 // Reference:
244 // "Multiplication and Squaring on Pairing-Friendly Fields"
245 // Devegili, OhEigeartaigh, Scott, Dahab
246 // Compute v1
247 let v1 = &self.c1 * &other.c1;
248
249 // Perform second check
250 let non_residue_times_v1 = Self::mul_base_field_by_nonresidue(&v1)?;
251 let rhs = &result.c0 - &non_residue_times_v1;
252 self.c0.mul_equals(&other.c0, &rhs)?;
253
254 // Last check
255 let a0_plus_a1 = &self.c0 + &self.c1;
256 let b0_plus_b1 = &other.c0 + &other.c1;
257 let one_minus_non_residue_v1 = &v1 - &non_residue_times_v1;
258
259 let tmp = &(&result.c1 + &result.c0) + &one_minus_non_residue_v1;
260 a0_plus_a1.mul_equals(&b0_plus_b1, &tmp)?;
261
262 Ok(())
263 }
264
265 #[tracing::instrument(target = "r1cs")]
266 fn frobenius_map(&self, power: usize) -> Result<Self, SynthesisError> {
267 let mut result = self.clone();
268 result.c0.frobenius_map_in_place(power)?;
269 result.c1.frobenius_map_in_place(power)?;
270 P::mul_base_field_var_by_frob_coeff(&mut result.c1, power);
271 Ok(result)
272 }
273
274 #[tracing::instrument(target = "r1cs")]
275 fn inverse(&self) -> Result<Self, SynthesisError> {
276 let mode = if self.is_constant() {
277 AllocationMode::Constant
278 } else {
279 AllocationMode::Witness
280 };
281 let inverse = Self::new_variable(
282 self.cs(),
283 || {
284 self.value()
285 .map(|f| f.inverse().unwrap_or(QuadExtField::zero()))
286 },
287 mode,
288 )?;
289 self.mul_equals(&inverse, &Self::one())?;
290 Ok(inverse)
291 }
292}
293
294impl_bounded_ops!(
295 QuadExtVar<BF, P>,
296 QuadExtField<P>,
297 Add,
298 add,
299 AddAssign,
300 add_assign,
301 |this: &'a QuadExtVar<BF, P>, other: &'a QuadExtVar<BF, P>| {
302 let c0 = &this.c0 + &other.c0;
303 let c1 = &this.c1 + &other.c1;
304 QuadExtVar::new(c0, c1)
305 },
306 |this: &'a QuadExtVar<BF, P>, other: QuadExtField<P>| {
307 this + QuadExtVar::constant(other)
308 },
309 (BF: FieldVar<P::BaseField, P::BasePrimeField>, P: QuadExtVarParams<BF>),
310 for <'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>
311);
312impl_bounded_ops!(
313 QuadExtVar<BF, P>,
314 QuadExtField<P>,
315 Sub,
316 sub,
317 SubAssign,
318 sub_assign,
319 |this: &'a QuadExtVar<BF, P>, other: &'a QuadExtVar<BF, P>| {
320 let c0 = &this.c0 - &other.c0;
321 let c1 = &this.c1 - &other.c1;
322 QuadExtVar::new(c0, c1)
323 },
324 |this: &'a QuadExtVar<BF, P>, other: QuadExtField<P>| {
325 this - QuadExtVar::constant(other)
326 },
327 (BF: FieldVar<P::BaseField, P::BasePrimeField>, P: QuadExtVarParams<BF>),
328 for <'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>
329);
330impl_bounded_ops!(
331 QuadExtVar<BF, P>,
332 QuadExtField<P>,
333 Mul,
334 mul,
335 MulAssign,
336 mul_assign,
337 |this: &'a QuadExtVar<BF, P>, other: &'a QuadExtVar<BF, P>| {
338 // Karatsuba multiplication for Fp2:
339 // v0 = A.c0 * B.c0
340 // v1 = A.c1 * B.c1
341 // result.c0 = v0 + non_residue * v1
342 // result.c1 = (A.c0 + A.c1) * (B.c0 + B.c1) - v0 - v1
343 // Enforced with 3 constraints:
344 // A.c1 * B.c1 = v1
345 // A.c0 * B.c0 = result.c0 - non_residue * v1
346 // (A.c0+A.c1)*(B.c0+B.c1) = result.c1 + result.c0 + (1 - non_residue) * v1
347 // Reference:
348 // "Multiplication and Squaring on Pairing-Friendly Fields"
349 // Devegili, OhEigeartaigh, Scott, Dahab
350 let mut result = this.clone();
351 let v0 = &this.c0 * &other.c0;
352 let v1 = &this.c1 * &other.c1;
353
354 result.c1 += &this.c0;
355 result.c1 *= &other.c0 + &other.c1;
356 result.c1 -= &v0;
357 result.c1 -= &v1;
358 result.c0 = v0 + &QuadExtVar::<BF, P>::mul_base_field_by_nonresidue(&v1).unwrap();
359 result
360 },
361 |this: &'a QuadExtVar<BF, P>, other: QuadExtField<P>| {
362 this * QuadExtVar::constant(other)
363 },
364 (BF: FieldVar<P::BaseField, P::BasePrimeField>, P: QuadExtVarParams<BF>),
365 for <'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>
366);
367
368impl<BF, P> EqGadget<P::BasePrimeField> for QuadExtVar<BF, P>
369where
370 BF: FieldVar<P::BaseField, P::BasePrimeField>,
371 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
372 P: QuadExtVarParams<BF>,
373{
374 #[tracing::instrument(target = "r1cs")]
375 fn is_eq(&self, other: &Self) -> Result<Boolean<P::BasePrimeField>, SynthesisError> {
376 let b0 = self.c0.is_eq(&other.c0)?;
377 let b1 = self.c1.is_eq(&other.c1)?;
378 b0.and(&b1)
379 }
380
381 #[inline]
382 #[tracing::instrument(target = "r1cs")]
383 fn conditional_enforce_equal(
384 &self,
385 other: &Self,
386 condition: &Boolean<P::BasePrimeField>,
387 ) -> Result<(), SynthesisError> {
388 self.c0.conditional_enforce_equal(&other.c0, condition)?;
389 self.c1.conditional_enforce_equal(&other.c1, condition)?;
390 Ok(())
391 }
392
393 #[inline]
394 #[tracing::instrument(target = "r1cs")]
395 fn conditional_enforce_not_equal(
396 &self,
397 other: &Self,
398 condition: &Boolean<P::BasePrimeField>,
399 ) -> Result<(), SynthesisError> {
400 let is_equal = self.is_eq(other)?;
401 is_equal
402 .and(condition)?
403 .enforce_equal(&Boolean::Constant(false))
404 }
405}
406
407impl<BF, P> ToBitsGadget<P::BasePrimeField> for QuadExtVar<BF, P>
408where
409 BF: FieldVar<P::BaseField, P::BasePrimeField>,
410 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
411 P: QuadExtVarParams<BF>,
412{
413 #[tracing::instrument(target = "r1cs")]
414 fn to_bits_le(&self) -> Result<Vec<Boolean<P::BasePrimeField>>, SynthesisError> {
415 let mut c0 = self.c0.to_bits_le()?;
416 let mut c1 = self.c1.to_bits_le()?;
417 c0.append(&mut c1);
418 Ok(c0)
419 }
420
421 #[tracing::instrument(target = "r1cs")]
422 fn to_non_unique_bits_le(&self) -> Result<Vec<Boolean<P::BasePrimeField>>, SynthesisError> {
423 let mut c0 = self.c0.to_non_unique_bits_le()?;
424 let mut c1 = self.c1.to_non_unique_bits_le()?;
425 c0.append(&mut c1);
426 Ok(c0)
427 }
428}
429
430impl<BF, P> ToBytesGadget<P::BasePrimeField> for QuadExtVar<BF, P>
431where
432 BF: FieldVar<P::BaseField, P::BasePrimeField>,
433 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
434 P: QuadExtVarParams<BF>,
435{
436 #[tracing::instrument(target = "r1cs")]
437 fn to_bytes(&self) -> Result<Vec<UInt8<P::BasePrimeField>>, SynthesisError> {
438 let mut c0 = self.c0.to_bytes()?;
439 let mut c1 = self.c1.to_bytes()?;
440 c0.append(&mut c1);
441 Ok(c0)
442 }
443
444 #[tracing::instrument(target = "r1cs")]
445 fn to_non_unique_bytes(&self) -> Result<Vec<UInt8<P::BasePrimeField>>, SynthesisError> {
446 let mut c0 = self.c0.to_non_unique_bytes()?;
447 let mut c1 = self.c1.to_non_unique_bytes()?;
448 c0.append(&mut c1);
449 Ok(c0)
450 }
451}
452
453impl<BF, P> ToConstraintFieldGadget<P::BasePrimeField> for QuadExtVar<BF, P>
454where
455 BF: FieldVar<P::BaseField, P::BasePrimeField>,
456 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
457 P: QuadExtVarParams<BF>,
458 BF: ToConstraintFieldGadget<P::BasePrimeField>,
459{
460 #[tracing::instrument(target = "r1cs")]
461 fn to_constraint_field(&self) -> Result<Vec<FpVar<P::BasePrimeField>>, SynthesisError> {
462 let mut res = Vec::new();
463
464 res.extend_from_slice(&self.c0.to_constraint_field()?);
465 res.extend_from_slice(&self.c1.to_constraint_field()?);
466
467 Ok(res)
468 }
469}
470
471impl<BF, P> CondSelectGadget<P::BasePrimeField> for QuadExtVar<BF, P>
472where
473 BF: FieldVar<P::BaseField, P::BasePrimeField>,
474 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
475 P: QuadExtVarParams<BF>,
476{
477 #[inline]
478 fn conditionally_select(
479 cond: &Boolean<P::BasePrimeField>,
480 true_value: &Self,
481 false_value: &Self,
482 ) -> Result<Self, SynthesisError> {
483 let c0 = BF::conditionally_select(cond, &true_value.c0, &false_value.c0)?;
484 let c1 = BF::conditionally_select(cond, &true_value.c1, &false_value.c1)?;
485 Ok(Self::new(c0, c1))
486 }
487}
488
489impl<BF, P> TwoBitLookupGadget<P::BasePrimeField> for QuadExtVar<BF, P>
490where
491 BF: FieldVar<P::BaseField, P::BasePrimeField>
492 + TwoBitLookupGadget<P::BasePrimeField, TableConstant = P::BaseField>,
493 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
494 P: QuadExtVarParams<BF>,
495{
496 type TableConstant = QuadExtField<P>;
497
498 #[tracing::instrument(target = "r1cs")]
499 fn two_bit_lookup(
500 b: &[Boolean<P::BasePrimeField>],
501 c: &[Self::TableConstant],
502 ) -> Result<Self, SynthesisError> {
503 let c0s = c.iter().map(|f| f.c0).collect::<Vec<_>>();
504 let c1s = c.iter().map(|f| f.c1).collect::<Vec<_>>();
505 let c0 = BF::two_bit_lookup(b, &c0s)?;
506 let c1 = BF::two_bit_lookup(b, &c1s)?;
507 Ok(Self::new(c0, c1))
508 }
509}
510
511impl<BF, P> ThreeBitCondNegLookupGadget<P::BasePrimeField> for QuadExtVar<BF, P>
512where
513 BF: FieldVar<P::BaseField, P::BasePrimeField>
514 + ThreeBitCondNegLookupGadget<P::BasePrimeField, TableConstant = P::BaseField>,
515 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
516 P: QuadExtVarParams<BF>,
517{
518 type TableConstant = QuadExtField<P>;
519
520 #[tracing::instrument(target = "r1cs")]
521 fn three_bit_cond_neg_lookup(
522 b: &[Boolean<P::BasePrimeField>],
523 b0b1: &Boolean<P::BasePrimeField>,
524 c: &[Self::TableConstant],
525 ) -> Result<Self, SynthesisError> {
526 let c0s = c.iter().map(|f| f.c0).collect::<Vec<_>>();
527 let c1s = c.iter().map(|f| f.c1).collect::<Vec<_>>();
528 let c0 = BF::three_bit_cond_neg_lookup(b, b0b1, &c0s)?;
529 let c1 = BF::three_bit_cond_neg_lookup(b, b0b1, &c1s)?;
530 Ok(Self::new(c0, c1))
531 }
532}
533
534impl<BF, P> AllocVar<QuadExtField<P>, P::BasePrimeField> for QuadExtVar<BF, P>
535where
536 BF: FieldVar<P::BaseField, P::BasePrimeField>,
537 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
538 P: QuadExtVarParams<BF>,
539{
540 fn new_variable<T: Borrow<QuadExtField<P>>>(
541 cs: impl Into<Namespace<P::BasePrimeField>>,
542 f: impl FnOnce() -> Result<T, SynthesisError>,
543 mode: AllocationMode,
544 ) -> Result<Self, SynthesisError> {
545 let ns = cs.into();
546 let cs = ns.cs();
547 let (c0, c1) = match f() {
548 Ok(fe) => (Ok(fe.borrow().c0), Ok(fe.borrow().c1)),
549 Err(_) => (
550 Err(SynthesisError::AssignmentMissing),
551 Err(SynthesisError::AssignmentMissing),
552 ),
553 };
554
555 let c0 = BF::new_variable(r1cs_core::ns!(cs, "c0"), || c0, mode)?;
556 let c1 = BF::new_variable(r1cs_core::ns!(cs, "c1"), || c1, mode)?;
557 Ok(Self::new(c0, c1))
558 }
559}