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 One, 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 Assignment, 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) -> Option<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 one = Self::new_constant(self.cs().get()?.clone(), QuadExtField::one())?;
277 let inverse = Self::new_witness(self.cs().get()?.clone(), || {
278 self.value()
279 .map(|f| f.inverse().unwrap_or(QuadExtField::zero()))
280 })?;
281 self.mul_equals(&inverse, &one)?;
282 Ok(inverse)
283 }
284}
285
286impl_bounded_ops!(
287 QuadExtVar<BF, P>,
288 QuadExtField<P>,
289 Add,
290 add,
291 AddAssign,
292 add_assign,
293 |this: &'a QuadExtVar<BF, P>, other: &'a QuadExtVar<BF, P>| {
294 let c0 = &this.c0 + &other.c0;
295 let c1 = &this.c1 + &other.c1;
296 QuadExtVar::new(c0, c1)
297 },
298 |this: &'a QuadExtVar<BF, P>, other: QuadExtField<P>| {
299 this + QuadExtVar::constant(other)
300 },
301 (BF: FieldVar<P::BaseField, P::BasePrimeField>, P: QuadExtVarParams<BF>),
302 for <'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>
303);
304impl_bounded_ops!(
305 QuadExtVar<BF, P>,
306 QuadExtField<P>,
307 Sub,
308 sub,
309 SubAssign,
310 sub_assign,
311 |this: &'a QuadExtVar<BF, P>, other: &'a QuadExtVar<BF, P>| {
312 let c0 = &this.c0 - &other.c0;
313 let c1 = &this.c1 - &other.c1;
314 QuadExtVar::new(c0, c1)
315 },
316 |this: &'a QuadExtVar<BF, P>, other: QuadExtField<P>| {
317 this - QuadExtVar::constant(other)
318 },
319 (BF: FieldVar<P::BaseField, P::BasePrimeField>, P: QuadExtVarParams<BF>),
320 for <'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>
321);
322impl_bounded_ops!(
323 QuadExtVar<BF, P>,
324 QuadExtField<P>,
325 Mul,
326 mul,
327 MulAssign,
328 mul_assign,
329 |this: &'a QuadExtVar<BF, P>, other: &'a QuadExtVar<BF, P>| {
330 // Karatsuba multiplication for Fp2:
331 // v0 = A.c0 * B.c0
332 // v1 = A.c1 * B.c1
333 // result.c0 = v0 + non_residue * v1
334 // result.c1 = (A.c0 + A.c1) * (B.c0 + B.c1) - v0 - v1
335 // Enforced with 3 constraints:
336 // A.c1 * B.c1 = v1
337 // A.c0 * B.c0 = result.c0 - non_residue * v1
338 // (A.c0+A.c1)*(B.c0+B.c1) = result.c1 + result.c0 + (1 - non_residue) * v1
339 // Reference:
340 // "Multiplication and Squaring on Pairing-Friendly Fields"
341 // Devegili, OhEigeartaigh, Scott, Dahab
342 let mut result = this.clone();
343 let v0 = &this.c0 * &other.c0;
344 let v1 = &this.c1 * &other.c1;
345
346 result.c1 += &this.c0;
347 result.c1 *= &other.c0 + &other.c1;
348 result.c1 -= &v0;
349 result.c1 -= &v1;
350 result.c0 = v0 + &QuadExtVar::<BF, P>::mul_base_field_by_nonresidue(&v1).unwrap();
351 result
352 },
353 |this: &'a QuadExtVar<BF, P>, other: QuadExtField<P>| {
354 this * QuadExtVar::constant(other)
355 },
356 (BF: FieldVar<P::BaseField, P::BasePrimeField>, P: QuadExtVarParams<BF>),
357 for <'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>
358);
359
360impl<BF, P> EqGadget<P::BasePrimeField> for QuadExtVar<BF, P>
361where
362 BF: FieldVar<P::BaseField, P::BasePrimeField>,
363 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
364 P: QuadExtVarParams<BF>,
365{
366 #[tracing::instrument(target = "r1cs")]
367 fn is_eq(&self, other: &Self) -> Result<Boolean<P::BasePrimeField>, SynthesisError> {
368 let b0 = self.c0.is_eq(&other.c0)?;
369 let b1 = self.c1.is_eq(&other.c1)?;
370 b0.and(&b1)
371 }
372
373 #[inline]
374 #[tracing::instrument(target = "r1cs")]
375 fn conditional_enforce_equal(
376 &self,
377 other: &Self,
378 condition: &Boolean<P::BasePrimeField>,
379 ) -> Result<(), SynthesisError> {
380 self.c0.conditional_enforce_equal(&other.c0, condition)?;
381 self.c1.conditional_enforce_equal(&other.c1, condition)?;
382 Ok(())
383 }
384
385 #[inline]
386 #[tracing::instrument(target = "r1cs")]
387 fn conditional_enforce_not_equal(
388 &self,
389 other: &Self,
390 condition: &Boolean<P::BasePrimeField>,
391 ) -> Result<(), SynthesisError> {
392 let is_equal = self.is_eq(other)?;
393 is_equal
394 .and(condition)?
395 .enforce_equal(&Boolean::Constant(false))
396 }
397}
398
399impl<BF, P> ToBitsGadget<P::BasePrimeField> for QuadExtVar<BF, P>
400where
401 BF: FieldVar<P::BaseField, P::BasePrimeField>,
402 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
403 P: QuadExtVarParams<BF>,
404{
405 #[tracing::instrument(target = "r1cs")]
406 fn to_bits_le(&self) -> Result<Vec<Boolean<P::BasePrimeField>>, SynthesisError> {
407 let mut c0 = self.c0.to_bits_le()?;
408 let mut c1 = self.c1.to_bits_le()?;
409 c0.append(&mut c1);
410 Ok(c0)
411 }
412
413 #[tracing::instrument(target = "r1cs")]
414 fn to_non_unique_bits_le(&self) -> Result<Vec<Boolean<P::BasePrimeField>>, SynthesisError> {
415 let mut c0 = self.c0.to_non_unique_bits_le()?;
416 let mut c1 = self.c1.to_non_unique_bits_le()?;
417 c0.append(&mut c1);
418 Ok(c0)
419 }
420}
421
422impl<BF, P> ToBytesGadget<P::BasePrimeField> for QuadExtVar<BF, P>
423where
424 BF: FieldVar<P::BaseField, P::BasePrimeField>,
425 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
426 P: QuadExtVarParams<BF>,
427{
428 #[tracing::instrument(target = "r1cs")]
429 fn to_bytes(&self) -> Result<Vec<UInt8<P::BasePrimeField>>, SynthesisError> {
430 let mut c0 = self.c0.to_bytes()?;
431 let mut c1 = self.c1.to_bytes()?;
432 c0.append(&mut c1);
433 Ok(c0)
434 }
435
436 #[tracing::instrument(target = "r1cs")]
437 fn to_non_unique_bytes(&self) -> Result<Vec<UInt8<P::BasePrimeField>>, SynthesisError> {
438 let mut c0 = self.c0.to_non_unique_bytes()?;
439 let mut c1 = self.c1.to_non_unique_bytes()?;
440 c0.append(&mut c1);
441 Ok(c0)
442 }
443}
444
445impl<BF, P> ToConstraintFieldGadget<P::BasePrimeField> for QuadExtVar<BF, P>
446where
447 BF: FieldVar<P::BaseField, P::BasePrimeField>,
448 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
449 P: QuadExtVarParams<BF>,
450 BF: ToConstraintFieldGadget<P::BasePrimeField>,
451{
452 #[tracing::instrument(target = "r1cs")]
453 fn to_constraint_field(&self) -> Result<Vec<FpVar<P::BasePrimeField>>, SynthesisError> {
454 let mut res = Vec::new();
455
456 res.extend_from_slice(&self.c0.to_constraint_field()?);
457 res.extend_from_slice(&self.c1.to_constraint_field()?);
458
459 Ok(res)
460 }
461}
462
463impl<BF, P> CondSelectGadget<P::BasePrimeField> for QuadExtVar<BF, P>
464where
465 BF: FieldVar<P::BaseField, P::BasePrimeField>,
466 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
467 P: QuadExtVarParams<BF>,
468{
469 #[inline]
470 fn conditionally_select(
471 cond: &Boolean<P::BasePrimeField>,
472 true_value: &Self,
473 false_value: &Self,
474 ) -> Result<Self, SynthesisError> {
475 let c0 = BF::conditionally_select(cond, &true_value.c0, &false_value.c0)?;
476 let c1 = BF::conditionally_select(cond, &true_value.c1, &false_value.c1)?;
477 Ok(Self::new(c0, c1))
478 }
479}
480
481impl<BF, P> TwoBitLookupGadget<P::BasePrimeField> for QuadExtVar<BF, P>
482where
483 BF: FieldVar<P::BaseField, P::BasePrimeField>
484 + TwoBitLookupGadget<P::BasePrimeField, TableConstant = P::BaseField>,
485 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
486 P: QuadExtVarParams<BF>,
487{
488 type TableConstant = QuadExtField<P>;
489
490 #[tracing::instrument(target = "r1cs")]
491 fn two_bit_lookup(
492 b: &[Boolean<P::BasePrimeField>],
493 c: &[Self::TableConstant],
494 ) -> Result<Self, SynthesisError> {
495 let c0s = c.iter().map(|f| f.c0).collect::<Vec<_>>();
496 let c1s = c.iter().map(|f| f.c1).collect::<Vec<_>>();
497 let c0 = BF::two_bit_lookup(b, &c0s)?;
498 let c1 = BF::two_bit_lookup(b, &c1s)?;
499 Ok(Self::new(c0, c1))
500 }
501}
502
503impl<BF, P> ThreeBitCondNegLookupGadget<P::BasePrimeField> for QuadExtVar<BF, P>
504where
505 BF: FieldVar<P::BaseField, P::BasePrimeField>
506 + ThreeBitCondNegLookupGadget<P::BasePrimeField, TableConstant = P::BaseField>,
507 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
508 P: QuadExtVarParams<BF>,
509{
510 type TableConstant = QuadExtField<P>;
511
512 #[tracing::instrument(target = "r1cs")]
513 fn three_bit_cond_neg_lookup(
514 b: &[Boolean<P::BasePrimeField>],
515 b0b1: &Boolean<P::BasePrimeField>,
516 c: &[Self::TableConstant],
517 ) -> Result<Self, SynthesisError> {
518 let c0s = c.iter().map(|f| f.c0).collect::<Vec<_>>();
519 let c1s = c.iter().map(|f| f.c1).collect::<Vec<_>>();
520 let c0 = BF::three_bit_cond_neg_lookup(b, b0b1, &c0s)?;
521 let c1 = BF::three_bit_cond_neg_lookup(b, b0b1, &c1s)?;
522 Ok(Self::new(c0, c1))
523 }
524}
525
526impl<BF, P> AllocVar<QuadExtField<P>, P::BasePrimeField> for QuadExtVar<BF, P>
527where
528 BF: FieldVar<P::BaseField, P::BasePrimeField>,
529 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
530 P: QuadExtVarParams<BF>,
531{
532 fn new_variable<T: Borrow<QuadExtField<P>>>(
533 cs: impl Into<Namespace<P::BasePrimeField>>,
534 f: impl FnOnce() -> Result<T, SynthesisError>,
535 mode: AllocationMode,
536 ) -> Result<Self, SynthesisError> {
537 let ns = cs.into();
538 let cs = ns.cs();
539 let (c0, c1) = match f() {
540 Ok(fe) => (Ok(fe.borrow().c0), Ok(fe.borrow().c1)),
541 Err(_) => (
542 Err(SynthesisError::AssignmentMissing),
543 Err(SynthesisError::AssignmentMissing),
544 ),
545 };
546
547 let c0 = BF::new_variable(r1cs_core::ns!(cs, "c0"), || c0, mode)?;
548 let c1 = BF::new_variable(r1cs_core::ns!(cs, "c1"), || c1, mode)?;
549 Ok(Self::new(c0, c1))
550 }
551}