ark-r1cs-std/src/fields/nonnative/field_var.rs
src/fields/nonnative/field_var.rsRaw
1use super::{params::OptimizationType, AllocatedNonNativeFieldVar, NonNativeFieldMulResultVar};
2use crate::{
3 boolean::Boolean,
4 fields::{fp::FpVar, FieldVar},
5 prelude::*,
6 R1CSVar, ToConstraintFieldGadget,
7};
8use ark_ff::{BigInteger, PrimeField};
9use ark_relations::r1cs::{ConstraintSystemRef, Namespace, Result as R1CSResult, SynthesisError};
10use ark_std::{
11 borrow::Borrow,
12 hash::{Hash, Hasher},
13 vec::Vec,
14};
15
16/// A gadget for representing non-native (`TargetField`) field elements over the
17/// constraint field (`BaseField`).
18#[derive(Clone, Debug)]
19#[must_use]
20pub enum NonNativeFieldVar<TargetField: PrimeField, BaseField: PrimeField> {
21 /// Constant
22 Constant(TargetField),
23 /// Allocated gadget
24 Var(AllocatedNonNativeFieldVar<TargetField, BaseField>),
25}
26
27impl<TargetField: PrimeField, BaseField: PrimeField> PartialEq
28 for NonNativeFieldVar<TargetField, BaseField>
29{
30 fn eq(&self, other: &Self) -> bool {
31 self.value()
32 .unwrap_or_default()
33 .eq(&other.value().unwrap_or_default())
34 }
35}
36
37impl<TargetField: PrimeField, BaseField: PrimeField> Eq
38 for NonNativeFieldVar<TargetField, BaseField>
39{
40}
41
42impl<TargetField: PrimeField, BaseField: PrimeField> Hash
43 for NonNativeFieldVar<TargetField, BaseField>
44{
45 fn hash<H: Hasher>(&self, state: &mut H) {
46 self.value().unwrap_or_default().hash(state);
47 }
48}
49
50impl<TargetField: PrimeField, BaseField: PrimeField> R1CSVar<BaseField>
51 for NonNativeFieldVar<TargetField, BaseField>
52{
53 type Value = TargetField;
54
55 fn cs(&self) -> ConstraintSystemRef<BaseField> {
56 match self {
57 Self::Constant(_) => ConstraintSystemRef::None,
58 Self::Var(a) => a.cs(),
59 }
60 }
61
62 fn value(&self) -> R1CSResult<Self::Value> {
63 match self {
64 Self::Constant(v) => Ok(*v),
65 Self::Var(v) => v.value(),
66 }
67 }
68}
69
70impl<TargetField: PrimeField, BaseField: PrimeField> From<Boolean<BaseField>>
71 for NonNativeFieldVar<TargetField, BaseField>
72{
73 fn from(other: Boolean<BaseField>) -> Self {
74 if let Boolean::Constant(b) = other {
75 Self::Constant(<TargetField as From<u128>>::from(b as u128))
76 } else {
77 // `other` is a variable
78 let one = Self::Constant(TargetField::one());
79 let zero = Self::Constant(TargetField::zero());
80 Self::conditionally_select(&other, &one, &zero).unwrap()
81 }
82 }
83}
84
85impl<TargetField: PrimeField, BaseField: PrimeField>
86 From<AllocatedNonNativeFieldVar<TargetField, BaseField>>
87 for NonNativeFieldVar<TargetField, BaseField>
88{
89 fn from(other: AllocatedNonNativeFieldVar<TargetField, BaseField>) -> Self {
90 Self::Var(other)
91 }
92}
93
94impl<'a, TargetField: PrimeField, BaseField: PrimeField> FieldOpsBounds<'a, TargetField, Self>
95 for NonNativeFieldVar<TargetField, BaseField>
96{
97}
98
99impl<'a, TargetField: PrimeField, BaseField: PrimeField>
100 FieldOpsBounds<'a, TargetField, NonNativeFieldVar<TargetField, BaseField>>
101 for &'a NonNativeFieldVar<TargetField, BaseField>
102{
103}
104
105impl<TargetField: PrimeField, BaseField: PrimeField> FieldVar<TargetField, BaseField>
106 for NonNativeFieldVar<TargetField, BaseField>
107{
108 fn zero() -> Self {
109 Self::Constant(TargetField::zero())
110 }
111
112 fn one() -> Self {
113 Self::Constant(TargetField::one())
114 }
115
116 fn constant(v: TargetField) -> Self {
117 Self::Constant(v)
118 }
119
120 #[tracing::instrument(target = "r1cs")]
121 fn negate(&self) -> R1CSResult<Self> {
122 match self {
123 Self::Constant(c) => Ok(Self::Constant(-*c)),
124 Self::Var(v) => Ok(Self::Var(v.negate()?)),
125 }
126 }
127
128 #[tracing::instrument(target = "r1cs")]
129 fn inverse(&self) -> R1CSResult<Self> {
130 match self {
131 Self::Constant(c) => Ok(Self::Constant(c.inverse().unwrap_or_default())),
132 Self::Var(v) => Ok(Self::Var(v.inverse()?)),
133 }
134 }
135
136 #[tracing::instrument(target = "r1cs")]
137 fn frobenius_map(&self, power: usize) -> R1CSResult<Self> {
138 match self {
139 Self::Constant(c) => Ok(Self::Constant({
140 let mut tmp = *c;
141 tmp.frobenius_map_in_place(power);
142 tmp
143 })),
144 Self::Var(v) => Ok(Self::Var(v.frobenius_map(power)?)),
145 }
146 }
147}
148
149impl_bounded_ops!(
150 NonNativeFieldVar<TargetField, BaseField>,
151 TargetField,
152 Add,
153 add,
154 AddAssign,
155 add_assign,
156 |this: &'a NonNativeFieldVar<TargetField, BaseField>, other: &'a NonNativeFieldVar<TargetField, BaseField>| {
157 use NonNativeFieldVar::*;
158 match (this, other) {
159 (Constant(c1), Constant(c2)) => Constant(*c1 + c2),
160 (Constant(c), Var(v)) | (Var(v), Constant(c)) => Var(v.add_constant(c).unwrap()),
161 (Var(v1), Var(v2)) => Var(v1.add(v2).unwrap()),
162 }
163 },
164 |this: &'a NonNativeFieldVar<TargetField, BaseField>, other: TargetField| { this + &NonNativeFieldVar::Constant(other) },
165 (TargetField: PrimeField, BaseField: PrimeField),
166);
167
168impl_bounded_ops!(
169 NonNativeFieldVar<TargetField, BaseField>,
170 TargetField,
171 Sub,
172 sub,
173 SubAssign,
174 sub_assign,
175 |this: &'a NonNativeFieldVar<TargetField, BaseField>, other: &'a NonNativeFieldVar<TargetField, BaseField>| {
176 use NonNativeFieldVar::*;
177 match (this, other) {
178 (Constant(c1), Constant(c2)) => Constant(*c1 - c2),
179 (Var(v), Constant(c)) => Var(v.sub_constant(c).unwrap()),
180 (Constant(c), Var(v)) => Var(v.sub_constant(c).unwrap().negate().unwrap()),
181 (Var(v1), Var(v2)) => Var(v1.sub(v2).unwrap()),
182 }
183 },
184 |this: &'a NonNativeFieldVar<TargetField, BaseField>, other: TargetField| {
185 this - &NonNativeFieldVar::Constant(other)
186 },
187 (TargetField: PrimeField, BaseField: PrimeField),
188);
189
190impl_bounded_ops!(
191 NonNativeFieldVar<TargetField, BaseField>,
192 TargetField,
193 Mul,
194 mul,
195 MulAssign,
196 mul_assign,
197 |this: &'a NonNativeFieldVar<TargetField, BaseField>, other: &'a NonNativeFieldVar<TargetField, BaseField>| {
198 use NonNativeFieldVar::*;
199 match (this, other) {
200 (Constant(c1), Constant(c2)) => Constant(*c1 * c2),
201 (Constant(c), Var(v)) | (Var(v), Constant(c)) => Var(v.mul_constant(c).unwrap()),
202 (Var(v1), Var(v2)) => Var(v1.mul(v2).unwrap()),
203 }
204 },
205 |this: &'a NonNativeFieldVar<TargetField, BaseField>, other: TargetField| {
206 if other.is_zero() {
207 NonNativeFieldVar::zero()
208 } else {
209 this * &NonNativeFieldVar::Constant(other)
210 }
211 },
212 (TargetField: PrimeField, BaseField: PrimeField),
213);
214
215/// *************************************************************************
216/// *************************************************************************
217
218impl<TargetField: PrimeField, BaseField: PrimeField> EqGadget<BaseField>
219 for NonNativeFieldVar<TargetField, BaseField>
220{
221 #[tracing::instrument(target = "r1cs")]
222 fn is_eq(&self, other: &Self) -> R1CSResult<Boolean<BaseField>> {
223 let cs = self.cs().or(other.cs());
224
225 if cs == ConstraintSystemRef::None {
226 Ok(Boolean::Constant(self.value()? == other.value()?))
227 } else {
228 let should_enforce_equal =
229 Boolean::new_witness(cs, || Ok(self.value()? == other.value()?))?;
230
231 self.conditional_enforce_equal(other, &should_enforce_equal)?;
232 self.conditional_enforce_not_equal(other, &should_enforce_equal.not())?;
233
234 Ok(should_enforce_equal)
235 }
236 }
237
238 #[tracing::instrument(target = "r1cs")]
239 fn conditional_enforce_equal(
240 &self,
241 other: &Self,
242 should_enforce: &Boolean<BaseField>,
243 ) -> R1CSResult<()> {
244 match (self, other) {
245 (Self::Constant(c1), Self::Constant(c2)) => {
246 if c1 != c2 {
247 should_enforce.enforce_equal(&Boolean::FALSE)?;
248 }
249 Ok(())
250 },
251 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
252 let cs = v.cs();
253 let c = AllocatedNonNativeFieldVar::new_constant(cs, c)?;
254 c.conditional_enforce_equal(v, should_enforce)
255 },
256 (Self::Var(v1), Self::Var(v2)) => v1.conditional_enforce_equal(v2, should_enforce),
257 }
258 }
259
260 #[tracing::instrument(target = "r1cs")]
261 fn conditional_enforce_not_equal(
262 &self,
263 other: &Self,
264 should_enforce: &Boolean<BaseField>,
265 ) -> R1CSResult<()> {
266 match (self, other) {
267 (Self::Constant(c1), Self::Constant(c2)) => {
268 if c1 == c2 {
269 should_enforce.enforce_equal(&Boolean::FALSE)?;
270 }
271 Ok(())
272 },
273 (Self::Constant(c), Self::Var(v)) | (Self::Var(v), Self::Constant(c)) => {
274 let cs = v.cs();
275 let c = AllocatedNonNativeFieldVar::new_constant(cs, c)?;
276 c.conditional_enforce_not_equal(v, should_enforce)
277 },
278 (Self::Var(v1), Self::Var(v2)) => v1.conditional_enforce_not_equal(v2, should_enforce),
279 }
280 }
281}
282
283impl<TargetField: PrimeField, BaseField: PrimeField> ToBitsGadget<BaseField>
284 for NonNativeFieldVar<TargetField, BaseField>
285{
286 #[tracing::instrument(target = "r1cs")]
287 fn to_bits_le(&self) -> R1CSResult<Vec<Boolean<BaseField>>> {
288 match self {
289 Self::Constant(_) => self.to_non_unique_bits_le(),
290 Self::Var(v) => v.to_bits_le(),
291 }
292 }
293
294 #[tracing::instrument(target = "r1cs")]
295 fn to_non_unique_bits_le(&self) -> R1CSResult<Vec<Boolean<BaseField>>> {
296 use ark_ff::BitIteratorLE;
297 match self {
298 Self::Constant(c) => Ok(BitIteratorLE::new(&c.into_bigint())
299 .take((TargetField::MODULUS_BIT_SIZE) as usize)
300 .map(Boolean::constant)
301 .collect::<Vec<_>>()),
302 Self::Var(v) => v.to_non_unique_bits_le(),
303 }
304 }
305}
306
307impl<TargetField: PrimeField, BaseField: PrimeField> ToBytesGadget<BaseField>
308 for NonNativeFieldVar<TargetField, BaseField>
309{
310 /// Outputs the unique byte decomposition of `self` in *little-endian*
311 /// form.
312 #[tracing::instrument(target = "r1cs")]
313 fn to_bytes(&self) -> R1CSResult<Vec<UInt8<BaseField>>> {
314 match self {
315 Self::Constant(c) => Ok(UInt8::constant_vec(
316 c.into_bigint().to_bytes_le().as_slice(),
317 )),
318
319 Self::Var(v) => v.to_bytes(),
320 }
321 }
322
323 #[tracing::instrument(target = "r1cs")]
324 fn to_non_unique_bytes(&self) -> R1CSResult<Vec<UInt8<BaseField>>> {
325 match self {
326 Self::Constant(c) => Ok(UInt8::constant_vec(
327 c.into_bigint().to_bytes_le().as_slice(),
328 )),
329 Self::Var(v) => v.to_non_unique_bytes(),
330 }
331 }
332}
333
334impl<TargetField: PrimeField, BaseField: PrimeField> CondSelectGadget<BaseField>
335 for NonNativeFieldVar<TargetField, BaseField>
336{
337 #[tracing::instrument(target = "r1cs")]
338 fn conditionally_select(
339 cond: &Boolean<BaseField>,
340 true_value: &Self,
341 false_value: &Self,
342 ) -> R1CSResult<Self> {
343 match cond {
344 Boolean::Constant(true) => Ok(true_value.clone()),
345 Boolean::Constant(false) => Ok(false_value.clone()),
346 _ => {
347 let cs = cond.cs();
348 let true_value = match true_value {
349 Self::Constant(f) => AllocatedNonNativeFieldVar::new_constant(cs.clone(), f)?,
350 Self::Var(v) => v.clone(),
351 };
352 let false_value = match false_value {
353 Self::Constant(f) => AllocatedNonNativeFieldVar::new_constant(cs, f)?,
354 Self::Var(v) => v.clone(),
355 };
356 cond.select(&true_value, &false_value).map(Self::Var)
357 },
358 }
359 }
360}
361
362/// Uses two bits to perform a lookup into a table
363/// `b` is little-endian: `b[0]` is LSB.
364impl<TargetField: PrimeField, BaseField: PrimeField> TwoBitLookupGadget<BaseField>
365 for NonNativeFieldVar<TargetField, BaseField>
366{
367 type TableConstant = TargetField;
368
369 #[tracing::instrument(target = "r1cs")]
370 fn two_bit_lookup(b: &[Boolean<BaseField>], c: &[Self::TableConstant]) -> R1CSResult<Self> {
371 debug_assert_eq!(b.len(), 2);
372 debug_assert_eq!(c.len(), 4);
373 if b.cs().is_none() {
374 // We're in the constant case
375
376 let lsb = b[0].value()? as usize;
377 let msb = b[1].value()? as usize;
378 let index = lsb + (msb << 1);
379 Ok(Self::Constant(c[index]))
380 } else {
381 AllocatedNonNativeFieldVar::two_bit_lookup(b, c).map(Self::Var)
382 }
383 }
384}
385
386impl<TargetField: PrimeField, BaseField: PrimeField> ThreeBitCondNegLookupGadget<BaseField>
387 for NonNativeFieldVar<TargetField, BaseField>
388{
389 type TableConstant = TargetField;
390
391 #[tracing::instrument(target = "r1cs")]
392 fn three_bit_cond_neg_lookup(
393 b: &[Boolean<BaseField>],
394 b0b1: &Boolean<BaseField>,
395 c: &[Self::TableConstant],
396 ) -> R1CSResult<Self> {
397 debug_assert_eq!(b.len(), 3);
398 debug_assert_eq!(c.len(), 4);
399
400 if b.cs().or(b0b1.cs()).is_none() {
401 // We're in the constant case
402
403 let lsb = b[0].value()? as usize;
404 let msb = b[1].value()? as usize;
405 let index = lsb + (msb << 1);
406 let intermediate = c[index];
407
408 let is_negative = b[2].value()?;
409 let y = if is_negative {
410 -intermediate
411 } else {
412 intermediate
413 };
414 Ok(Self::Constant(y))
415 } else {
416 AllocatedNonNativeFieldVar::three_bit_cond_neg_lookup(b, b0b1, c).map(Self::Var)
417 }
418 }
419}
420
421impl<TargetField: PrimeField, BaseField: PrimeField> AllocVar<TargetField, BaseField>
422 for NonNativeFieldVar<TargetField, BaseField>
423{
424 fn new_variable<T: Borrow<TargetField>>(
425 cs: impl Into<Namespace<BaseField>>,
426 f: impl FnOnce() -> Result<T, SynthesisError>,
427 mode: AllocationMode,
428 ) -> R1CSResult<Self> {
429 let ns = cs.into();
430 let cs = ns.cs();
431
432 if cs == ConstraintSystemRef::None || mode == AllocationMode::Constant {
433 Ok(Self::Constant(*f()?.borrow()))
434 } else {
435 AllocatedNonNativeFieldVar::new_variable(cs, f, mode).map(Self::Var)
436 }
437 }
438}
439
440impl<TargetField: PrimeField, BaseField: PrimeField> ToConstraintFieldGadget<BaseField>
441 for NonNativeFieldVar<TargetField, BaseField>
442{
443 #[tracing::instrument(target = "r1cs")]
444 fn to_constraint_field(&self) -> R1CSResult<Vec<FpVar<BaseField>>> {
445 // Use one group element to represent the optimization type.
446 //
447 // By default, the constant is converted in the weight-optimized type, because
448 // it results in fewer elements.
449 match self {
450 Self::Constant(c) => Ok(AllocatedNonNativeFieldVar::get_limbs_representations(
451 c,
452 OptimizationType::Weight,
453 )?
454 .into_iter()
455 .map(FpVar::constant)
456 .collect()),
457 Self::Var(v) => v.to_constraint_field(),
458 }
459 }
460}
461
462impl<TargetField: PrimeField, BaseField: PrimeField> NonNativeFieldVar<TargetField, BaseField> {
463 /// The `mul_without_reduce` for `NonNativeFieldVar`
464 #[tracing::instrument(target = "r1cs")]
465 pub fn mul_without_reduce(
466 &self,
467 other: &Self,
468 ) -> R1CSResult<NonNativeFieldMulResultVar<TargetField, BaseField>> {
469 match self {
470 Self::Constant(c) => match other {
471 Self::Constant(other_c) => Ok(NonNativeFieldMulResultVar::Constant(*c * other_c)),
472 Self::Var(other_v) => {
473 let self_v =
474 AllocatedNonNativeFieldVar::<TargetField, BaseField>::new_constant(
475 self.cs(),
476 c,
477 )?;
478 Ok(NonNativeFieldMulResultVar::Var(
479 other_v.mul_without_reduce(&self_v)?,
480 ))
481 },
482 },
483 Self::Var(v) => {
484 let other_v = match other {
485 Self::Constant(other_c) => {
486 AllocatedNonNativeFieldVar::<TargetField, BaseField>::new_constant(
487 self.cs(),
488 other_c,
489 )?
490 },
491 Self::Var(other_v) => other_v.clone(),
492 };
493 Ok(NonNativeFieldMulResultVar::Var(
494 v.mul_without_reduce(&other_v)?,
495 ))
496 },
497 }
498 }
499}