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