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