ark-r1cs-std/r1cs-std/src/fields/cubic_extension.rs
r1cs-std/src/fields/cubic_extension.rsRaw
1use algebra::{
2 fields::{CubicExtField, CubicExtParameters, Field},
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 CubicExtVar<BF: FieldVar<P::BaseField, P::BasePrimeField>, P: CubicExtVarParams<BF>>
18where
19 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
20{
21 pub c0: BF,
22 pub c1: BF,
23 pub c2: BF,
24 #[derivative(Debug = "ignore")]
25 _params: PhantomData<P>,
26}
27
28pub trait CubicExtVarParams<BF: FieldVar<Self::BaseField, Self::BasePrimeField>>:
29 CubicExtParameters
30where
31 for<'a> &'a BF: FieldOpsBounds<'a, Self::BaseField, BF>,
32{
33 fn mul_base_field_vars_by_frob_coeff(c1: &mut BF, c2: &mut BF, power: usize);
34}
35
36impl<BF: FieldVar<P::BaseField, P::BasePrimeField>, P: CubicExtVarParams<BF>> CubicExtVar<BF, P>
37where
38 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
39{
40 #[inline]
41 pub fn new(c0: BF, c1: BF, c2: BF) -> Self {
42 let _params = PhantomData;
43 Self {
44 c0,
45 c1,
46 c2,
47 _params,
48 }
49 }
50
51 /// Multiply a BF by cubic nonresidue P::NONRESIDUE.
52 #[inline]
53 pub fn mul_base_field_by_nonresidue(fe: &BF) -> Result<BF, SynthesisError> {
54 Ok(fe * P::NONRESIDUE)
55 }
56
57 /// Multiply a CubicExtVar by an element of `P::BaseField`.
58 #[inline]
59 pub fn mul_by_base_field_constant(&self, fe: P::BaseField) -> Self {
60 let c0 = &self.c0 * fe;
61 let c1 = &self.c1 * fe;
62 let c2 = &self.c2 * fe;
63 Self::new(c0, c1, c2)
64 }
65
66 #[inline]
67 pub fn mul_assign_by_base_field_constant(&mut self, fe: P::BaseField) {
68 *self = (&*self).mul_by_base_field_constant(fe);
69 }
70}
71
72impl<BF, P> R1CSVar<P::BasePrimeField> for CubicExtVar<BF, P>
73where
74 BF: FieldVar<P::BaseField, P::BasePrimeField>,
75 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
76 P: CubicExtVarParams<BF>,
77{
78 type Value = CubicExtField<P>;
79
80 fn cs(&self) -> Option<ConstraintSystemRef<P::BasePrimeField>> {
81 [&self.c0, &self.c1, &self.c2].cs()
82 }
83
84 #[inline]
85 fn value(&self) -> Result<Self::Value, SynthesisError> {
86 match (self.c0.value(), self.c1.value(), self.c2.value()) {
87 (Ok(c0), Ok(c1), Ok(c2)) => Ok(CubicExtField::new(c0, c1, c2)),
88 (..) => Err(SynthesisError::AssignmentMissing),
89 }
90 }
91}
92
93impl<BF, P> From<Boolean<P::BasePrimeField>> for CubicExtVar<BF, P>
94where
95 BF: FieldVar<P::BaseField, P::BasePrimeField>,
96 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
97 P: CubicExtVarParams<BF>,
98{
99 fn from(other: Boolean<P::BasePrimeField>) -> Self {
100 let c0 = BF::from(other);
101 let c1 = BF::zero();
102 let c2 = BF::zero();
103 Self::new(c0, c1, c2)
104 }
105}
106
107impl<'a, BF, P> FieldOpsBounds<'a, CubicExtField<P>, CubicExtVar<BF, P>> for CubicExtVar<BF, P>
108where
109 BF: FieldVar<P::BaseField, P::BasePrimeField>,
110 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
111 P: CubicExtVarParams<BF>,
112{
113}
114impl<'a, BF, P> FieldOpsBounds<'a, CubicExtField<P>, CubicExtVar<BF, P>> for &'a CubicExtVar<BF, P>
115where
116 BF: FieldVar<P::BaseField, P::BasePrimeField>,
117 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
118 P: CubicExtVarParams<BF>,
119{
120}
121
122impl<BF, P> FieldVar<CubicExtField<P>, P::BasePrimeField> for CubicExtVar<BF, P>
123where
124 BF: FieldVar<P::BaseField, P::BasePrimeField>,
125 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
126 P: CubicExtVarParams<BF>,
127{
128 fn constant(other: CubicExtField<P>) -> Self {
129 let c0 = BF::constant(other.c0);
130 let c1 = BF::constant(other.c1);
131 let c2 = BF::constant(other.c2);
132 Self::new(c0, c1, c2)
133 }
134
135 fn zero() -> Self {
136 let c0 = BF::zero();
137 let c1 = BF::zero();
138 let c2 = BF::zero();
139 Self::new(c0, c1, c2)
140 }
141
142 fn one() -> Self {
143 let c0 = BF::one();
144 let c1 = BF::zero();
145 let c2 = BF::zero();
146 Self::new(c0, c1, c2)
147 }
148
149 #[inline]
150 fn double(&self) -> Result<Self, SynthesisError> {
151 let c0 = self.c0.double()?;
152 let c1 = self.c1.double()?;
153 let c2 = self.c2.double()?;
154 Ok(Self::new(c0, c1, c2))
155 }
156
157 #[inline]
158 fn negate(&self) -> Result<Self, SynthesisError> {
159 let mut result = self.clone();
160 result.c0.negate_in_place()?;
161 result.c1.negate_in_place()?;
162 result.c2.negate_in_place()?;
163 Ok(result)
164 }
165
166 /// Use the Chung-Hasan asymmetric squaring formula.
167 ///
168 /// (Devegili OhEig Scott Dahab --- Multiplication and Squaring on
169 /// Abstract Pairing-Friendly
170 /// Fields.pdf; Section 4 (CH-SQR2))
171 #[inline]
172 fn square(&self) -> Result<Self, SynthesisError> {
173 let a = self.c0.clone();
174 let b = self.c1.clone();
175 let c = self.c2.clone();
176
177 let s0 = a.square()?;
178 let ab = &a * &b;
179 let s1 = ab.double()?;
180 let s2 = (&a - &b + &c).square()?;
181 let s3 = (&b * &c).double()?;
182 let s4 = c.square()?;
183
184 let c0 = Self::mul_base_field_by_nonresidue(&s3)? + &s0;
185 let c1 = Self::mul_base_field_by_nonresidue(&s4)? + &s1;
186 let c2 = s1 + &s2 + &s3 - &s0 - &s4;
187
188 Ok(Self::new(c0, c1, c2))
189 }
190
191 fn mul_equals(&self, other: &Self, result: &Self) -> Result<(), SynthesisError> {
192 // Karatsuba multiplication for cubic extensions:
193 // v0 = A.c0 * B.c0
194 // v1 = A.c1 * B.c1
195 // v2 = A.c2 * B.c2
196 // result.c0 = v0 + β((a1 + a2)(b1 + b2) − v1 − v2)
197 // result.c1 = (a0 + a1)(b0 + b1) − v0 − v1 + βv2
198 // result.c2 = (a0 + a2)(b0 + b2) − v0 + v1 − v2,
199 // We enforce this with six constraints:
200 //
201 // v0 = A.c0 * B.c0
202 // v1 = A.c1 * B.c1
203 // v2 = A.c2 * B.c2
204 //
205 // result.c0 - v0 + \beta*(v1 + v2) = β(a1 + a2)(b1 + b2))
206 // result.c1 + v0 + v1 - βv2 = (a0 + a1)(b0 + b1)
207 // result.c2 + v0 - v1 + v2 = (a0 + a2)(b0 + b2)
208 // Reference:
209 // "Multiplication and Squaring on Pairing-Friendly Fields"
210 // Devegili, OhEigeartaigh, Scott, Dahab
211 //
212 // This implementation adapted from
213 // https://github.com/ZencashOfficial/ginger-lib/blob/development/r1cs/gadgets/std/src/fields/fp3.rs
214 let v0 = &self.c0 * &other.c0;
215 let v1 = &self.c1 * &other.c1;
216 let v2 = &self.c2 * &other.c2;
217
218 // Check c0
219 let nr_a1_plus_a2 = (&self.c1 + &self.c2) * P::NONRESIDUE;
220 let b1_plus_b2 = &other.c1 + &other.c2;
221 let nr_v1 = &v1 * P::NONRESIDUE;
222 let nr_v2 = &v2 * P::NONRESIDUE;
223 let to_check = &result.c0 - &v0 + &nr_v1 + &nr_v2;
224 nr_a1_plus_a2.mul_equals(&b1_plus_b2, &to_check)?;
225
226 // Check c1
227 let a0_plus_a1 = &self.c0 + &self.c1;
228 let b0_plus_b1 = &other.c0 + &other.c1;
229 let to_check = &result.c1 - &nr_v2 + &v0 + &v1;
230 a0_plus_a1.mul_equals(&b0_plus_b1, &to_check)?;
231
232 // Check c2
233 let a0_plus_a2 = &self.c0 + &self.c2;
234 let b0_plus_b2 = &other.c0 + &other.c2;
235 let to_check = &result.c2 + &v0 - &v1 + &v2;
236 a0_plus_a2.mul_equals(&b0_plus_b2, &to_check)?;
237 Ok(())
238 }
239
240 fn frobenius_map(&self, power: usize) -> Result<Self, SynthesisError> {
241 let mut result = self.clone();
242 result.c0.frobenius_map_in_place(power)?;
243 result.c1.frobenius_map_in_place(power)?;
244 result.c2.frobenius_map_in_place(power)?;
245
246 P::mul_base_field_vars_by_frob_coeff(&mut result.c1, &mut result.c2, power);
247 Ok(result)
248 }
249
250 fn inverse(&self) -> Result<Self, SynthesisError> {
251 let cs = self.cs().get()?.clone();
252 let one = Self::new_constant(cs.clone(), CubicExtField::one())?;
253
254 let inverse = Self::new_witness(self.cs().get()?.clone(), || {
255 self.value()
256 .map(|f| f.inverse().unwrap_or(CubicExtField::zero()))
257 })?;
258 self.mul_equals(&inverse, &one)?;
259 Ok(inverse)
260 }
261}
262
263impl_bounded_ops!(
264 CubicExtVar<BF, P>,
265 CubicExtField<P>,
266 Add,
267 add,
268 AddAssign,
269 add_assign,
270 |this: &'a CubicExtVar<BF, P>, other: &'a CubicExtVar<BF, P>| {
271 let c0 = &this.c0 + &other.c0;
272 let c1 = &this.c1 + &other.c1;
273 let c2 = &this.c2 + &other.c2;
274 CubicExtVar::new(c0, c1, c2)
275 },
276 |this: &'a CubicExtVar<BF, P>, other: CubicExtField<P>| {
277 this + CubicExtVar::constant(other)
278 },
279 (BF: FieldVar<P::BaseField, P::BasePrimeField>, P: CubicExtVarParams<BF>),
280 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
281);
282impl_bounded_ops!(
283 CubicExtVar<BF, P>,
284 CubicExtField<P>,
285 Sub,
286 sub,
287 SubAssign,
288 sub_assign,
289 |this: &'a CubicExtVar<BF, P>, other: &'a CubicExtVar<BF, P>| {
290 let c0 = &this.c0 - &other.c0;
291 let c1 = &this.c1 - &other.c1;
292 let c2 = &this.c2 - &other.c2;
293 CubicExtVar::new(c0, c1, c2)
294 },
295 |this: &'a CubicExtVar<BF, P>, other: CubicExtField<P>| {
296 this - CubicExtVar::constant(other)
297 },
298 (BF: FieldVar<P::BaseField, P::BasePrimeField>, P: CubicExtVarParams<BF>),
299 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
300);
301impl_bounded_ops!(
302 CubicExtVar<BF, P>,
303 CubicExtField<P>,
304 Mul,
305 mul,
306 MulAssign,
307 mul_assign,
308 |this: &'a CubicExtVar<BF, P>, other: &'a CubicExtVar<BF, P>| {
309 // Karatsuba multiplication for cubic extensions:
310 // v0 = A.c0 * B.c0
311 // v1 = A.c1 * B.c1
312 // v2 = A.c2 * B.c2
313 // result.c0 = v0 + β((a1 + a2)(b1 + b2) − v1 − v2)
314 // result.c1 = (a0 + a1)(b0 + b1) − v0 − v1 + βv2
315 // result.c2 = (a0 + a2)(b0 + b2) − v0 + v1 − v2,
316 //
317 // Reference:
318 // "Multiplication and Squaring on Pairing-Friendly Fields"
319 // Devegili, OhEigeartaigh, Scott, Dahab
320 let v0 = &this.c0 * &other.c0;
321 let v1 = &this.c1 * &other.c1;
322 let v2 = &this.c2 * &other.c2;
323 let c0 =
324 (((&this.c1 + &this.c2) * (&other.c1 + &other.c2) - &v1 - &v2) * P::NONRESIDUE) + &v0 ;
325 let c1 =
326 (&this.c0 + &this.c1) * (&other.c0 + &other.c1) - &v0 - &v1 + (&v2 * P::NONRESIDUE);
327 let c2 =
328 (&this.c0 + &this.c2) * (&other.c0 + &other.c2) - &v0 + &v1 - &v2;
329
330 CubicExtVar::new(c0, c1, c2)
331 },
332 |this: &'a CubicExtVar<BF, P>, other: CubicExtField<P>| {
333 this * CubicExtVar::constant(other)
334 },
335 (BF: FieldVar<P::BaseField, P::BasePrimeField>, P: CubicExtVarParams<BF>),
336 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
337);
338
339impl<BF, P> EqGadget<P::BasePrimeField> for CubicExtVar<BF, P>
340where
341 BF: FieldVar<P::BaseField, P::BasePrimeField>,
342 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
343 P: CubicExtVarParams<BF>,
344{
345 fn is_eq(&self, other: &Self) -> Result<Boolean<P::BasePrimeField>, SynthesisError> {
346 let b0 = self.c0.is_eq(&other.c0)?;
347 let b1 = self.c1.is_eq(&other.c1)?;
348 let b2 = self.c2.is_eq(&other.c2)?;
349 b0.and(&b1)?.and(&b2)
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 self.c2.conditional_enforce_equal(&other.c2, 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 CubicExtVar<BF, P>
378where
379 BF: FieldVar<P::BaseField, P::BasePrimeField>,
380 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
381 P: CubicExtVarParams<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 let mut c2 = self.c2.to_bits_le()?;
387 c0.append(&mut c1);
388 c0.append(&mut c2);
389 Ok(c0)
390 }
391
392 fn to_non_unique_bits_le(&self) -> Result<Vec<Boolean<P::BasePrimeField>>, SynthesisError> {
393 let mut c0 = self.c0.to_non_unique_bits_le()?;
394 let mut c1 = self.c1.to_non_unique_bits_le()?;
395 let mut c2 = self.c2.to_non_unique_bits_le()?;
396 c0.append(&mut c1);
397 c0.append(&mut c2);
398 Ok(c0)
399 }
400}
401
402impl<BF, P> ToBytesGadget<P::BasePrimeField> for CubicExtVar<BF, P>
403where
404 BF: FieldVar<P::BaseField, P::BasePrimeField>,
405 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
406 P: CubicExtVarParams<BF>,
407{
408 fn to_bytes(&self) -> Result<Vec<UInt8<P::BasePrimeField>>, SynthesisError> {
409 let mut c0 = self.c0.to_bytes()?;
410 let mut c1 = self.c1.to_bytes()?;
411 let mut c2 = self.c2.to_bytes()?;
412 c0.append(&mut c1);
413 c0.append(&mut c2);
414
415 Ok(c0)
416 }
417
418 fn to_non_unique_bytes(&self) -> Result<Vec<UInt8<P::BasePrimeField>>, SynthesisError> {
419 let mut c0 = self.c0.to_non_unique_bytes()?;
420 let mut c1 = self.c1.to_non_unique_bytes()?;
421 let mut c2 = self.c2.to_non_unique_bytes()?;
422
423 c0.append(&mut c1);
424 c0.append(&mut c2);
425
426 Ok(c0)
427 }
428}
429
430impl<BF, P> CondSelectGadget<P::BasePrimeField> for CubicExtVar<BF, P>
431where
432 BF: FieldVar<P::BaseField, P::BasePrimeField>,
433 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
434 P: CubicExtVarParams<BF>,
435{
436 #[inline]
437 fn conditionally_select(
438 cond: &Boolean<P::BasePrimeField>,
439 true_value: &Self,
440 false_value: &Self,
441 ) -> Result<Self, SynthesisError> {
442 let c0 = BF::conditionally_select(cond, &true_value.c0, &false_value.c0)?;
443 let c1 = BF::conditionally_select(cond, &true_value.c1, &false_value.c1)?;
444 let c2 = BF::conditionally_select(cond, &true_value.c2, &false_value.c2)?;
445 Ok(Self::new(c0, c1, c2))
446 }
447}
448
449impl<BF, P> TwoBitLookupGadget<P::BasePrimeField> for CubicExtVar<BF, P>
450where
451 BF: FieldVar<P::BaseField, P::BasePrimeField>
452 + TwoBitLookupGadget<P::BasePrimeField, TableConstant = P::BaseField>,
453 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
454 P: CubicExtVarParams<BF>,
455{
456 type TableConstant = CubicExtField<P>;
457
458 fn two_bit_lookup(
459 b: &[Boolean<P::BasePrimeField>],
460 c: &[Self::TableConstant],
461 ) -> Result<Self, SynthesisError> {
462 let c0s = c.iter().map(|f| f.c0).collect::<Vec<_>>();
463 let c1s = c.iter().map(|f| f.c1).collect::<Vec<_>>();
464 let c2s = c.iter().map(|f| f.c2).collect::<Vec<_>>();
465 let c0 = BF::two_bit_lookup(b, &c0s)?;
466 let c1 = BF::two_bit_lookup(b, &c1s)?;
467 let c2 = BF::two_bit_lookup(b, &c2s)?;
468 Ok(Self::new(c0, c1, c2))
469 }
470}
471
472impl<BF, P> ThreeBitCondNegLookupGadget<P::BasePrimeField> for CubicExtVar<BF, P>
473where
474 BF: FieldVar<P::BaseField, P::BasePrimeField>
475 + ThreeBitCondNegLookupGadget<P::BasePrimeField, TableConstant = P::BaseField>,
476 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
477 P: CubicExtVarParams<BF>,
478{
479 type TableConstant = CubicExtField<P>;
480
481 fn three_bit_cond_neg_lookup(
482 b: &[Boolean<P::BasePrimeField>],
483 b0b1: &Boolean<P::BasePrimeField>,
484 c: &[Self::TableConstant],
485 ) -> Result<Self, SynthesisError> {
486 let c0s = c.iter().map(|f| f.c0).collect::<Vec<_>>();
487 let c1s = c.iter().map(|f| f.c1).collect::<Vec<_>>();
488 let c2s = c.iter().map(|f| f.c2).collect::<Vec<_>>();
489 let c0 = BF::three_bit_cond_neg_lookup(b, b0b1, &c0s)?;
490 let c1 = BF::three_bit_cond_neg_lookup(b, b0b1, &c1s)?;
491 let c2 = BF::three_bit_cond_neg_lookup(b, b0b1, &c2s)?;
492 Ok(Self::new(c0, c1, c2))
493 }
494}
495
496impl<BF, P> AllocVar<CubicExtField<P>, P::BasePrimeField> for CubicExtVar<BF, P>
497where
498 BF: FieldVar<P::BaseField, P::BasePrimeField>,
499 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
500 P: CubicExtVarParams<BF>,
501{
502 fn new_variable<T: Borrow<CubicExtField<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
510 use SynthesisError::*;
511 let (c0, c1, c2) = match f() {
512 Ok(fe) => (Ok(fe.borrow().c0), Ok(fe.borrow().c1), Ok(fe.borrow().c2)),
513 Err(_) => (
514 Err(AssignmentMissing),
515 Err(AssignmentMissing),
516 Err(AssignmentMissing),
517 ),
518 };
519
520 let c0 = BF::new_variable(cs.ns("c0"), || c0, mode)?;
521 let c1 = BF::new_variable(cs.ns("c1"), || c1, mode)?;
522 let c2 = BF::new_variable(cs.ns("c2"), || c2, mode)?;
523 Ok(Self::new(c0, c1, c2))
524 }
525}