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