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 #[tracing::instrument(target = "r1cs")]
151 fn double(&self) -> Result<Self, SynthesisError> {
152 let c0 = self.c0.double()?;
153 let c1 = self.c1.double()?;
154 let c2 = self.c2.double()?;
155 Ok(Self::new(c0, c1, c2))
156 }
157
158 #[inline]
159 #[tracing::instrument(target = "r1cs")]
160 fn negate(&self) -> Result<Self, SynthesisError> {
161 let mut result = self.clone();
162 result.c0.negate_in_place()?;
163 result.c1.negate_in_place()?;
164 result.c2.negate_in_place()?;
165 Ok(result)
166 }
167
168 /// Use the Chung-Hasan asymmetric squaring formula.
169 ///
170 /// (Devegili OhEig Scott Dahab --- Multiplication and Squaring on
171 /// Abstract Pairing-Friendly
172 /// Fields.pdf; Section 4 (CH-SQR2))
173 #[inline]
174 #[tracing::instrument(target = "r1cs")]
175 fn square(&self) -> Result<Self, SynthesisError> {
176 let a = self.c0.clone();
177 let b = self.c1.clone();
178 let c = self.c2.clone();
179
180 let s0 = a.square()?;
181 let ab = &a * &b;
182 let s1 = ab.double()?;
183 let s2 = (&a - &b + &c).square()?;
184 let s3 = (&b * &c).double()?;
185 let s4 = c.square()?;
186
187 let c0 = Self::mul_base_field_by_nonresidue(&s3)? + &s0;
188 let c1 = Self::mul_base_field_by_nonresidue(&s4)? + &s1;
189 let c2 = s1 + &s2 + &s3 - &s0 - &s4;
190
191 Ok(Self::new(c0, c1, c2))
192 }
193
194 #[tracing::instrument(target = "r1cs")]
195 fn mul_equals(&self, other: &Self, result: &Self) -> Result<(), SynthesisError> {
196 // Karatsuba multiplication for cubic extensions:
197 // v0 = A.c0 * B.c0
198 // v1 = A.c1 * B.c1
199 // v2 = A.c2 * B.c2
200 // result.c0 = v0 + β((a1 + a2)(b1 + b2) − v1 − v2)
201 // result.c1 = (a0 + a1)(b0 + b1) − v0 − v1 + βv2
202 // result.c2 = (a0 + a2)(b0 + b2) − v0 + v1 − v2,
203 // We enforce this with six constraints:
204 //
205 // v0 = A.c0 * B.c0
206 // v1 = A.c1 * B.c1
207 // v2 = A.c2 * B.c2
208 //
209 // result.c0 - v0 + \beta*(v1 + v2) = β(a1 + a2)(b1 + b2))
210 // result.c1 + v0 + v1 - βv2 = (a0 + a1)(b0 + b1)
211 // result.c2 + v0 - v1 + v2 = (a0 + a2)(b0 + b2)
212 // Reference:
213 // "Multiplication and Squaring on Pairing-Friendly Fields"
214 // Devegili, OhEigeartaigh, Scott, Dahab
215 //
216 // This implementation adapted from
217 // https://github.com/ZencashOfficial/ginger-lib/blob/development/r1cs/gadgets/std/src/fields/fp3.rs
218 let v0 = &self.c0 * &other.c0;
219 let v1 = &self.c1 * &other.c1;
220 let v2 = &self.c2 * &other.c2;
221
222 // Check c0
223 let nr_a1_plus_a2 = (&self.c1 + &self.c2) * P::NONRESIDUE;
224 let b1_plus_b2 = &other.c1 + &other.c2;
225 let nr_v1 = &v1 * P::NONRESIDUE;
226 let nr_v2 = &v2 * P::NONRESIDUE;
227 let to_check = &result.c0 - &v0 + &nr_v1 + &nr_v2;
228 nr_a1_plus_a2.mul_equals(&b1_plus_b2, &to_check)?;
229
230 // Check c1
231 let a0_plus_a1 = &self.c0 + &self.c1;
232 let b0_plus_b1 = &other.c0 + &other.c1;
233 let to_check = &result.c1 - &nr_v2 + &v0 + &v1;
234 a0_plus_a1.mul_equals(&b0_plus_b1, &to_check)?;
235
236 // Check c2
237 let a0_plus_a2 = &self.c0 + &self.c2;
238 let b0_plus_b2 = &other.c0 + &other.c2;
239 let to_check = &result.c2 + &v0 - &v1 + &v2;
240 a0_plus_a2.mul_equals(&b0_plus_b2, &to_check)?;
241 Ok(())
242 }
243
244 #[tracing::instrument(target = "r1cs")]
245 fn frobenius_map(&self, power: usize) -> Result<Self, SynthesisError> {
246 let mut result = self.clone();
247 result.c0.frobenius_map_in_place(power)?;
248 result.c1.frobenius_map_in_place(power)?;
249 result.c2.frobenius_map_in_place(power)?;
250
251 P::mul_base_field_vars_by_frob_coeff(&mut result.c1, &mut result.c2, power);
252 Ok(result)
253 }
254
255 #[tracing::instrument(target = "r1cs")]
256 fn inverse(&self) -> Result<Self, SynthesisError> {
257 let cs = self.cs().get()?.clone();
258 let one = Self::new_constant(cs.clone(), CubicExtField::one())?;
259
260 let inverse = Self::new_witness(self.cs().get()?.clone(), || {
261 self.value()
262 .map(|f| f.inverse().unwrap_or(CubicExtField::zero()))
263 })?;
264 self.mul_equals(&inverse, &one)?;
265 Ok(inverse)
266 }
267}
268
269impl_bounded_ops!(
270 CubicExtVar<BF, P>,
271 CubicExtField<P>,
272 Add,
273 add,
274 AddAssign,
275 add_assign,
276 |this: &'a CubicExtVar<BF, P>, other: &'a CubicExtVar<BF, P>| {
277 let c0 = &this.c0 + &other.c0;
278 let c1 = &this.c1 + &other.c1;
279 let c2 = &this.c2 + &other.c2;
280 CubicExtVar::new(c0, c1, c2)
281 },
282 |this: &'a CubicExtVar<BF, P>, other: CubicExtField<P>| {
283 this + CubicExtVar::constant(other)
284 },
285 (BF: FieldVar<P::BaseField, P::BasePrimeField>, P: CubicExtVarParams<BF>),
286 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
287);
288impl_bounded_ops!(
289 CubicExtVar<BF, P>,
290 CubicExtField<P>,
291 Sub,
292 sub,
293 SubAssign,
294 sub_assign,
295 |this: &'a CubicExtVar<BF, P>, other: &'a CubicExtVar<BF, P>| {
296 let c0 = &this.c0 - &other.c0;
297 let c1 = &this.c1 - &other.c1;
298 let c2 = &this.c2 - &other.c2;
299 CubicExtVar::new(c0, c1, c2)
300 },
301 |this: &'a CubicExtVar<BF, P>, other: CubicExtField<P>| {
302 this - CubicExtVar::constant(other)
303 },
304 (BF: FieldVar<P::BaseField, P::BasePrimeField>, P: CubicExtVarParams<BF>),
305 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
306);
307impl_bounded_ops!(
308 CubicExtVar<BF, P>,
309 CubicExtField<P>,
310 Mul,
311 mul,
312 MulAssign,
313 mul_assign,
314 |this: &'a CubicExtVar<BF, P>, other: &'a CubicExtVar<BF, P>| {
315 // Karatsuba multiplication for cubic extensions:
316 // v0 = A.c0 * B.c0
317 // v1 = A.c1 * B.c1
318 // v2 = A.c2 * B.c2
319 // result.c0 = v0 + β((a1 + a2)(b1 + b2) − v1 − v2)
320 // result.c1 = (a0 + a1)(b0 + b1) − v0 − v1 + βv2
321 // result.c2 = (a0 + a2)(b0 + b2) − v0 + v1 − v2,
322 //
323 // Reference:
324 // "Multiplication and Squaring on Pairing-Friendly Fields"
325 // Devegili, OhEigeartaigh, Scott, Dahab
326 let v0 = &this.c0 * &other.c0;
327 let v1 = &this.c1 * &other.c1;
328 let v2 = &this.c2 * &other.c2;
329 let c0 =
330 (((&this.c1 + &this.c2) * (&other.c1 + &other.c2) - &v1 - &v2) * P::NONRESIDUE) + &v0 ;
331 let c1 =
332 (&this.c0 + &this.c1) * (&other.c0 + &other.c1) - &v0 - &v1 + (&v2 * P::NONRESIDUE);
333 let c2 =
334 (&this.c0 + &this.c2) * (&other.c0 + &other.c2) - &v0 + &v1 - &v2;
335
336 CubicExtVar::new(c0, c1, c2)
337 },
338 |this: &'a CubicExtVar<BF, P>, other: CubicExtField<P>| {
339 this * CubicExtVar::constant(other)
340 },
341 (BF: FieldVar<P::BaseField, P::BasePrimeField>, P: CubicExtVarParams<BF>),
342 for<'b> &'b BF: FieldOpsBounds<'b, P::BaseField, BF>,
343);
344
345impl<BF, P> EqGadget<P::BasePrimeField> for CubicExtVar<BF, P>
346where
347 BF: FieldVar<P::BaseField, P::BasePrimeField>,
348 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
349 P: CubicExtVarParams<BF>,
350{
351 #[tracing::instrument(target = "r1cs")]
352 fn is_eq(&self, other: &Self) -> Result<Boolean<P::BasePrimeField>, SynthesisError> {
353 let b0 = self.c0.is_eq(&other.c0)?;
354 let b1 = self.c1.is_eq(&other.c1)?;
355 let b2 = self.c2.is_eq(&other.c2)?;
356 b0.and(&b1)?.and(&b2)
357 }
358
359 #[inline]
360 #[tracing::instrument(target = "r1cs")]
361 fn conditional_enforce_equal(
362 &self,
363 other: &Self,
364 condition: &Boolean<P::BasePrimeField>,
365 ) -> Result<(), SynthesisError> {
366 self.c0.conditional_enforce_equal(&other.c0, condition)?;
367 self.c1.conditional_enforce_equal(&other.c1, condition)?;
368 self.c2.conditional_enforce_equal(&other.c2, condition)?;
369 Ok(())
370 }
371
372 #[inline]
373 #[tracing::instrument(target = "r1cs")]
374 fn conditional_enforce_not_equal(
375 &self,
376 other: &Self,
377 condition: &Boolean<P::BasePrimeField>,
378 ) -> Result<(), SynthesisError> {
379 let is_equal = self.is_eq(other)?;
380 is_equal
381 .and(condition)?
382 .enforce_equal(&Boolean::Constant(false))
383 }
384}
385
386impl<BF, P> ToBitsGadget<P::BasePrimeField> for CubicExtVar<BF, P>
387where
388 BF: FieldVar<P::BaseField, P::BasePrimeField>,
389 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
390 P: CubicExtVarParams<BF>,
391{
392 #[tracing::instrument(target = "r1cs")]
393 fn to_bits_le(&self) -> Result<Vec<Boolean<P::BasePrimeField>>, SynthesisError> {
394 let mut c0 = self.c0.to_bits_le()?;
395 let mut c1 = self.c1.to_bits_le()?;
396 let mut c2 = self.c2.to_bits_le()?;
397 c0.append(&mut c1);
398 c0.append(&mut c2);
399 Ok(c0)
400 }
401
402 #[tracing::instrument(target = "r1cs")]
403 fn to_non_unique_bits_le(&self) -> Result<Vec<Boolean<P::BasePrimeField>>, SynthesisError> {
404 let mut c0 = self.c0.to_non_unique_bits_le()?;
405 let mut c1 = self.c1.to_non_unique_bits_le()?;
406 let mut c2 = self.c2.to_non_unique_bits_le()?;
407 c0.append(&mut c1);
408 c0.append(&mut c2);
409 Ok(c0)
410 }
411}
412
413impl<BF, P> ToBytesGadget<P::BasePrimeField> for CubicExtVar<BF, P>
414where
415 BF: FieldVar<P::BaseField, P::BasePrimeField>,
416 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
417 P: CubicExtVarParams<BF>,
418{
419 #[tracing::instrument(target = "r1cs")]
420 fn to_bytes(&self) -> Result<Vec<UInt8<P::BasePrimeField>>, SynthesisError> {
421 let mut c0 = self.c0.to_bytes()?;
422 let mut c1 = self.c1.to_bytes()?;
423 let mut c2 = self.c2.to_bytes()?;
424 c0.append(&mut c1);
425 c0.append(&mut c2);
426
427 Ok(c0)
428 }
429
430 #[tracing::instrument(target = "r1cs")]
431 fn to_non_unique_bytes(&self) -> Result<Vec<UInt8<P::BasePrimeField>>, SynthesisError> {
432 let mut c0 = self.c0.to_non_unique_bytes()?;
433 let mut c1 = self.c1.to_non_unique_bytes()?;
434 let mut c2 = self.c2.to_non_unique_bytes()?;
435
436 c0.append(&mut c1);
437 c0.append(&mut c2);
438
439 Ok(c0)
440 }
441}
442
443impl<BF, P> CondSelectGadget<P::BasePrimeField> for CubicExtVar<BF, P>
444where
445 BF: FieldVar<P::BaseField, P::BasePrimeField>,
446 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
447 P: CubicExtVarParams<BF>,
448{
449 #[inline]
450 #[tracing::instrument(target = "r1cs")]
451 fn conditionally_select(
452 cond: &Boolean<P::BasePrimeField>,
453 true_value: &Self,
454 false_value: &Self,
455 ) -> Result<Self, SynthesisError> {
456 let c0 = BF::conditionally_select(cond, &true_value.c0, &false_value.c0)?;
457 let c1 = BF::conditionally_select(cond, &true_value.c1, &false_value.c1)?;
458 let c2 = BF::conditionally_select(cond, &true_value.c2, &false_value.c2)?;
459 Ok(Self::new(c0, c1, c2))
460 }
461}
462
463impl<BF, P> TwoBitLookupGadget<P::BasePrimeField> for CubicExtVar<BF, P>
464where
465 BF: FieldVar<P::BaseField, P::BasePrimeField>
466 + TwoBitLookupGadget<P::BasePrimeField, TableConstant = P::BaseField>,
467 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
468 P: CubicExtVarParams<BF>,
469{
470 type TableConstant = CubicExtField<P>;
471
472 #[tracing::instrument(target = "r1cs")]
473 fn two_bit_lookup(
474 b: &[Boolean<P::BasePrimeField>],
475 c: &[Self::TableConstant],
476 ) -> Result<Self, SynthesisError> {
477 let c0s = c.iter().map(|f| f.c0).collect::<Vec<_>>();
478 let c1s = c.iter().map(|f| f.c1).collect::<Vec<_>>();
479 let c2s = c.iter().map(|f| f.c2).collect::<Vec<_>>();
480 let c0 = BF::two_bit_lookup(b, &c0s)?;
481 let c1 = BF::two_bit_lookup(b, &c1s)?;
482 let c2 = BF::two_bit_lookup(b, &c2s)?;
483 Ok(Self::new(c0, c1, c2))
484 }
485}
486
487impl<BF, P> ThreeBitCondNegLookupGadget<P::BasePrimeField> for CubicExtVar<BF, P>
488where
489 BF: FieldVar<P::BaseField, P::BasePrimeField>
490 + ThreeBitCondNegLookupGadget<P::BasePrimeField, TableConstant = P::BaseField>,
491 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
492 P: CubicExtVarParams<BF>,
493{
494 type TableConstant = CubicExtField<P>;
495
496 #[tracing::instrument(target = "r1cs")]
497 fn three_bit_cond_neg_lookup(
498 b: &[Boolean<P::BasePrimeField>],
499 b0b1: &Boolean<P::BasePrimeField>,
500 c: &[Self::TableConstant],
501 ) -> Result<Self, SynthesisError> {
502 let c0s = c.iter().map(|f| f.c0).collect::<Vec<_>>();
503 let c1s = c.iter().map(|f| f.c1).collect::<Vec<_>>();
504 let c2s = c.iter().map(|f| f.c2).collect::<Vec<_>>();
505 let c0 = BF::three_bit_cond_neg_lookup(b, b0b1, &c0s)?;
506 let c1 = BF::three_bit_cond_neg_lookup(b, b0b1, &c1s)?;
507 let c2 = BF::three_bit_cond_neg_lookup(b, b0b1, &c2s)?;
508 Ok(Self::new(c0, c1, c2))
509 }
510}
511
512impl<BF, P> AllocVar<CubicExtField<P>, P::BasePrimeField> for CubicExtVar<BF, P>
513where
514 BF: FieldVar<P::BaseField, P::BasePrimeField>,
515 for<'a> &'a BF: FieldOpsBounds<'a, P::BaseField, BF>,
516 P: CubicExtVarParams<BF>,
517{
518 fn new_variable<T: Borrow<CubicExtField<P>>>(
519 cs: impl Into<Namespace<P::BasePrimeField>>,
520 f: impl FnOnce() -> Result<T, SynthesisError>,
521 mode: AllocationMode,
522 ) -> Result<Self, SynthesisError> {
523 let ns = cs.into();
524 let cs = ns.cs();
525
526 use SynthesisError::*;
527 let (c0, c1, c2) = match f() {
528 Ok(fe) => (Ok(fe.borrow().c0), Ok(fe.borrow().c1), Ok(fe.borrow().c2)),
529 Err(_) => (
530 Err(AssignmentMissing),
531 Err(AssignmentMissing),
532 Err(AssignmentMissing),
533 ),
534 };
535
536 let c0 = BF::new_variable(r1cs_core::ns!(cs, "c0"), || c0, mode)?;
537 let c1 = BF::new_variable(r1cs_core::ns!(cs, "c1"), || c1, mode)?;
538 let c2 = BF::new_variable(r1cs_core::ns!(cs, "c2"), || c2, mode)?;
539 Ok(Self::new(c0, c1, c2))
540 }
541}