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