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