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