ark-r1cs-std/src/fields/nonnative/allocated_field_var.rs
src/fields/nonnative/allocated_field_var.rsRaw
1use super::params::{get_params, OptimizationType};
2use super::reduce::{bigint_to_basefield, limbs_to_bigint, Reducer};
3use super::AllocatedNonNativeFieldMulResultVar;
4use crate::fields::fp::FpVar;
5use crate::prelude::*;
6use crate::ToConstraintFieldGadget;
7use ark_ff::{BigInteger, PrimeField};
8use ark_relations::r1cs::{OptimizationGoal, Result as R1CSResult};
9use ark_relations::{
10 ns,
11 r1cs::{ConstraintSystemRef, Namespace, SynthesisError},
12};
13use ark_std::cmp::{max, min};
14use ark_std::marker::PhantomData;
15use ark_std::{borrow::Borrow, vec, vec::Vec};
16
17/// The allocated version of `NonNativeFieldVar` (introduced below)
18#[derive(Debug)]
19#[must_use]
20pub struct AllocatedNonNativeFieldVar<TargetField: PrimeField, BaseField: PrimeField> {
21 /// Constraint system reference
22 pub cs: ConstraintSystemRef<BaseField>,
23 /// The limbs, each of which is a BaseField gadget.
24 pub limbs: Vec<FpVar<BaseField>>,
25 /// Number of additions done over this gadget, using which the gadget decides when to reduce.
26 pub num_of_additions_over_normal_form: BaseField,
27 /// Whether the limb representation is the normal form (using only the bits specified in the parameters, and the representation is strictly within the range of TargetField).
28 pub is_in_the_normal_form: bool,
29 #[doc(hidden)]
30 pub target_phantom: PhantomData<TargetField>,
31}
32
33impl<TargetField: PrimeField, BaseField: PrimeField>
34 AllocatedNonNativeFieldVar<TargetField, BaseField>
35{
36 /// Return cs
37 pub fn cs(&self) -> ConstraintSystemRef<BaseField> {
38 self.cs.clone()
39 }
40
41 /// Obtain the value of limbs
42 pub fn limbs_to_value(
43 limbs: Vec<BaseField>,
44 optimization_type: OptimizationType,
45 ) -> TargetField {
46 let params = get_params(
47 TargetField::MODULUS_BIT_SIZE as usize,
48 BaseField::MODULUS_BIT_SIZE as usize,
49 optimization_type,
50 );
51
52 let mut base_repr: <TargetField as PrimeField>::BigInt = TargetField::one().into_bigint();
53
54 // Convert 2^{(params.bits_per_limb - 1)} into the TargetField and then double the base
55 // This is because 2^{(params.bits_per_limb)} might indeed be larger than the target field's prime.
56 base_repr.muln((params.bits_per_limb - 1) as u32);
57 let mut base: TargetField = TargetField::from_bigint(base_repr).unwrap();
58 base = base + &base;
59
60 let mut result = TargetField::zero();
61 let mut power = TargetField::one();
62
63 for limb in limbs.iter().rev() {
64 let mut val = TargetField::zero();
65 let mut cur = TargetField::one();
66
67 for bit in limb.into_bigint().to_bits_be().iter().rev() {
68 if *bit {
69 val += &cur;
70 }
71 cur.double_in_place();
72 }
73
74 result += &(val * power);
75 power *= &base;
76 }
77
78 result
79 }
80
81 /// Obtain the value of a nonnative field element
82 pub fn value(&self) -> R1CSResult<TargetField> {
83 let mut limbs = Vec::new();
84 for limb in self.limbs.iter() {
85 limbs.push(limb.value()?);
86 }
87
88 Ok(Self::limbs_to_value(limbs, self.get_optimization_type()))
89 }
90
91 /// Obtain the nonnative field element of a constant value
92 pub fn constant(cs: ConstraintSystemRef<BaseField>, value: TargetField) -> R1CSResult<Self> {
93 let optimization_type = match cs.optimization_goal() {
94 OptimizationGoal::None => OptimizationType::Constraints,
95 OptimizationGoal::Constraints => OptimizationType::Constraints,
96 OptimizationGoal::Weight => OptimizationType::Weight,
97 };
98
99 let limbs_value = Self::get_limbs_representations(&value, optimization_type)?;
100
101 let mut limbs = Vec::new();
102
103 for limb_value in limbs_value.iter() {
104 limbs.push(FpVar::<BaseField>::new_constant(
105 ns!(cs, "limb"),
106 limb_value,
107 )?);
108 }
109
110 Ok(Self {
111 cs,
112 limbs,
113 num_of_additions_over_normal_form: BaseField::zero(),
114 is_in_the_normal_form: true,
115 target_phantom: PhantomData,
116 })
117 }
118
119 /// Obtain the nonnative field element of one
120 pub fn one(cs: ConstraintSystemRef<BaseField>) -> R1CSResult<Self> {
121 Self::constant(cs, TargetField::one())
122 }
123
124 /// Obtain the nonnative field element of zero
125 pub fn zero(cs: ConstraintSystemRef<BaseField>) -> R1CSResult<Self> {
126 Self::constant(cs, TargetField::zero())
127 }
128
129 /// Add a nonnative field element
130 #[tracing::instrument(target = "r1cs")]
131 pub fn add(&self, other: &Self) -> R1CSResult<Self> {
132 assert_eq!(self.get_optimization_type(), other.get_optimization_type());
133
134 let mut limbs = Vec::new();
135 for (this_limb, other_limb) in self.limbs.iter().zip(other.limbs.iter()) {
136 limbs.push(this_limb + other_limb);
137 }
138
139 let mut res = Self {
140 cs: self.cs(),
141 limbs,
142 num_of_additions_over_normal_form: self
143 .num_of_additions_over_normal_form
144 .add(&other.num_of_additions_over_normal_form)
145 .add(&BaseField::one()),
146 is_in_the_normal_form: false,
147 target_phantom: PhantomData,
148 };
149
150 Reducer::<TargetField, BaseField>::post_add_reduce(&mut res)?;
151 Ok(res)
152 }
153
154 /// Add a constant
155 #[tracing::instrument(target = "r1cs")]
156 pub fn add_constant(&self, other: &TargetField) -> R1CSResult<Self> {
157 let other_limbs = Self::get_limbs_representations(other, self.get_optimization_type())?;
158
159 let mut limbs = Vec::new();
160 for (this_limb, other_limb) in self.limbs.iter().zip(other_limbs.iter()) {
161 limbs.push(this_limb + *other_limb);
162 }
163
164 let mut res = Self {
165 cs: self.cs(),
166 limbs,
167 num_of_additions_over_normal_form: self
168 .num_of_additions_over_normal_form
169 .add(&BaseField::one()),
170 is_in_the_normal_form: false,
171 target_phantom: PhantomData,
172 };
173
174 Reducer::<TargetField, BaseField>::post_add_reduce(&mut res)?;
175
176 Ok(res)
177 }
178
179 /// Subtract a nonnative field element, without the final reduction step
180 #[tracing::instrument(target = "r1cs")]
181 pub fn sub_without_reduce(&self, other: &Self) -> R1CSResult<Self> {
182 assert_eq!(self.get_optimization_type(), other.get_optimization_type());
183
184 let params = get_params(
185 TargetField::MODULUS_BIT_SIZE as usize,
186 BaseField::MODULUS_BIT_SIZE as usize,
187 self.get_optimization_type(),
188 );
189
190 // Step 1: reduce the `other` if needed
191 let mut surfeit = overhead!(other.num_of_additions_over_normal_form + BaseField::one()) + 1;
192 let mut other = other.clone();
193 if (surfeit + params.bits_per_limb > BaseField::MODULUS_BIT_SIZE as usize - 1)
194 || (surfeit
195 + (TargetField::MODULUS_BIT_SIZE as usize
196 - params.bits_per_limb * (params.num_limbs - 1))
197 > BaseField::MODULUS_BIT_SIZE as usize - 1)
198 {
199 Reducer::reduce(&mut other)?;
200 surfeit = overhead!(other.num_of_additions_over_normal_form + BaseField::one()) + 1;
201 }
202
203 // Step 2: construct the padding
204 let mut pad_non_top_limb_repr: <BaseField as PrimeField>::BigInt =
205 BaseField::one().into_bigint();
206 let mut pad_top_limb_repr: <BaseField as PrimeField>::BigInt = pad_non_top_limb_repr;
207
208 pad_non_top_limb_repr.muln((surfeit + params.bits_per_limb) as u32);
209 let pad_non_top_limb = BaseField::from_bigint(pad_non_top_limb_repr).unwrap();
210
211 pad_top_limb_repr.muln(
212 (surfeit
213 + (TargetField::MODULUS_BIT_SIZE as usize
214 - params.bits_per_limb * (params.num_limbs - 1))) as u32,
215 );
216 let pad_top_limb = BaseField::from_bigint(pad_top_limb_repr).unwrap();
217
218 let mut pad_limbs = Vec::new();
219 pad_limbs.push(pad_top_limb);
220 for _ in 0..self.limbs.len() - 1 {
221 pad_limbs.push(pad_non_top_limb);
222 }
223
224 // Step 3: prepare to pad the padding to k * p for some k
225 let pad_to_kp_gap = Self::limbs_to_value(pad_limbs, self.get_optimization_type()).neg();
226 let pad_to_kp_limbs =
227 Self::get_limbs_representations(&pad_to_kp_gap, self.get_optimization_type())?;
228
229 // Step 4: the result is self + pad + pad_to_kp - other
230 let mut limbs = Vec::new();
231 for (i, ((this_limb, other_limb), pad_to_kp_limb)) in self
232 .limbs
233 .iter()
234 .zip(other.limbs.iter())
235 .zip(pad_to_kp_limbs.iter())
236 .enumerate()
237 {
238 if i != 0 {
239 limbs.push(this_limb + pad_non_top_limb + *pad_to_kp_limb - other_limb);
240 } else {
241 limbs.push(this_limb + pad_top_limb + *pad_to_kp_limb - other_limb);
242 }
243 }
244
245 let result = AllocatedNonNativeFieldVar::<TargetField, BaseField> {
246 cs: self.cs(),
247 limbs,
248 num_of_additions_over_normal_form: self.num_of_additions_over_normal_form
249 + (other.num_of_additions_over_normal_form + BaseField::one())
250 + (other.num_of_additions_over_normal_form + BaseField::one()),
251 is_in_the_normal_form: false,
252 target_phantom: PhantomData,
253 };
254
255 Ok(result)
256 }
257
258 /// Subtract a nonnative field element
259 #[tracing::instrument(target = "r1cs")]
260 pub fn sub(&self, other: &Self) -> R1CSResult<Self> {
261 assert_eq!(self.get_optimization_type(), other.get_optimization_type());
262
263 let mut result = self.sub_without_reduce(other)?;
264 Reducer::<TargetField, BaseField>::post_add_reduce(&mut result)?;
265 Ok(result)
266 }
267
268 /// Subtract a constant
269 #[tracing::instrument(target = "r1cs")]
270 pub fn sub_constant(&self, other: &TargetField) -> R1CSResult<Self> {
271 self.sub(&Self::constant(self.cs(), *other)?)
272 }
273
274 /// Multiply a nonnative field element
275 #[tracing::instrument(target = "r1cs")]
276 pub fn mul(&self, other: &Self) -> R1CSResult<Self> {
277 assert_eq!(self.get_optimization_type(), other.get_optimization_type());
278
279 self.mul_without_reduce(&other)?.reduce()
280 }
281
282 /// Multiply a constant
283 pub fn mul_constant(&self, other: &TargetField) -> R1CSResult<Self> {
284 self.mul(&Self::constant(self.cs(), *other)?)
285 }
286
287 /// Compute the negate of a nonnative field element
288 #[tracing::instrument(target = "r1cs")]
289 pub fn negate(&self) -> R1CSResult<Self> {
290 Self::zero(self.cs())?.sub(self)
291 }
292
293 /// Compute the inverse of a nonnative field element
294 #[tracing::instrument(target = "r1cs")]
295 pub fn inverse(&self) -> R1CSResult<Self> {
296 let inverse = Self::new_witness(self.cs(), || {
297 Ok(self.value()?.inverse().unwrap_or_else(TargetField::zero))
298 })?;
299
300 let actual_result = self.clone().mul(&inverse)?;
301 actual_result.conditional_enforce_equal(&Self::one(self.cs())?, &Boolean::TRUE)?;
302 Ok(inverse)
303 }
304
305 /// Convert a `TargetField` element into limbs (not constraints)
306 /// This is an internal function that would be reused by a number of other functions
307 pub fn get_limbs_representations(
308 elem: &TargetField,
309 optimization_type: OptimizationType,
310 ) -> R1CSResult<Vec<BaseField>> {
311 Self::get_limbs_representations_from_big_integer(&elem.into_bigint(), optimization_type)
312 }
313
314 /// Obtain the limbs directly from a big int
315 pub fn get_limbs_representations_from_big_integer(
316 elem: &<TargetField as PrimeField>::BigInt,
317 optimization_type: OptimizationType,
318 ) -> R1CSResult<Vec<BaseField>> {
319 let params = get_params(
320 TargetField::MODULUS_BIT_SIZE as usize,
321 BaseField::MODULUS_BIT_SIZE as usize,
322 optimization_type,
323 );
324
325 // push the lower limbs first
326 let mut limbs: Vec<BaseField> = Vec::new();
327 let mut cur = *elem;
328 for _ in 0..params.num_limbs {
329 let cur_bits = cur.to_bits_be(); // `to_bits` is big endian
330 let cur_mod_r = <BaseField as PrimeField>::BigInt::from_bits_be(
331 &cur_bits[cur_bits.len() - params.bits_per_limb..],
332 ); // therefore, the lowest `bits_per_non_top_limb` bits is what we want.
333 limbs.push(BaseField::from_bigint(cur_mod_r).unwrap());
334 cur.divn(params.bits_per_limb as u32);
335 }
336
337 // then we reserve, so that the limbs are ``big limb first''
338 limbs.reverse();
339
340 Ok(limbs)
341 }
342
343 /// for advanced use, multiply and output the intermediate representations (without reduction)
344 /// This intermediate representations can be added with each other, and they can later be reduced back to the `NonNativeFieldVar`.
345 #[tracing::instrument(target = "r1cs")]
346 pub fn mul_without_reduce(
347 &self,
348 other: &Self,
349 ) -> R1CSResult<AllocatedNonNativeFieldMulResultVar<TargetField, BaseField>> {
350 assert_eq!(self.get_optimization_type(), other.get_optimization_type());
351
352 let params = get_params(
353 TargetField::MODULUS_BIT_SIZE as usize,
354 BaseField::MODULUS_BIT_SIZE as usize,
355 self.get_optimization_type(),
356 );
357
358 // Step 1: reduce `self` and `other` if neceessary
359 let mut self_reduced = self.clone();
360 let mut other_reduced = other.clone();
361 Reducer::<TargetField, BaseField>::pre_mul_reduce(&mut self_reduced, &mut other_reduced)?;
362
363 let mut prod_limbs = Vec::new();
364 if self.get_optimization_type() == OptimizationType::Weight {
365 let zero = FpVar::<BaseField>::zero();
366
367 for _ in 0..2 * params.num_limbs - 1 {
368 prod_limbs.push(zero.clone());
369 }
370
371 for i in 0..params.num_limbs {
372 for j in 0..params.num_limbs {
373 prod_limbs[i + j] =
374 &prod_limbs[i + j] + (&self_reduced.limbs[i] * &other_reduced.limbs[j]);
375 }
376 }
377 } else {
378 let cs = self.cs().or(other.cs());
379
380 for z_index in 0..2 * params.num_limbs - 1 {
381 prod_limbs.push(FpVar::new_witness(ns!(cs, "limb product"), || {
382 let mut z_i = BaseField::zero();
383 for i in 0..=min(params.num_limbs - 1, z_index) {
384 let j = z_index - i;
385 if j < params.num_limbs {
386 z_i += &self_reduced.limbs[i]
387 .value()?
388 .mul(&other_reduced.limbs[j].value()?);
389 }
390 }
391
392 Ok(z_i)
393 })?);
394 }
395
396 for c in 0..(2 * params.num_limbs - 1) {
397 let c_pows: Vec<_> = (0..(2 * params.num_limbs - 1))
398 .map(|i| BaseField::from((c + 1) as u128).pow(&vec![i as u64]))
399 .collect();
400
401 let x = self_reduced
402 .limbs
403 .iter()
404 .zip(c_pows.iter())
405 .map(|(var, c_pow)| var * *c_pow)
406 .fold(FpVar::zero(), |sum, i| sum + i);
407
408 let y = other_reduced
409 .limbs
410 .iter()
411 .zip(c_pows.iter())
412 .map(|(var, c_pow)| var * *c_pow)
413 .fold(FpVar::zero(), |sum, i| sum + i);
414
415 let z = prod_limbs
416 .iter()
417 .zip(c_pows.iter())
418 .map(|(var, c_pow)| var * *c_pow)
419 .fold(FpVar::zero(), |sum, i| sum + i);
420
421 z.enforce_equal(&(x * y))?;
422 }
423 }
424
425 Ok(AllocatedNonNativeFieldMulResultVar {
426 cs: self.cs(),
427 limbs: prod_limbs,
428 prod_of_num_of_additions: (self_reduced.num_of_additions_over_normal_form
429 + BaseField::one())
430 * (other_reduced.num_of_additions_over_normal_form + BaseField::one()),
431 target_phantom: PhantomData,
432 })
433 }
434
435 pub(crate) fn frobenius_map(&self, _power: usize) -> R1CSResult<Self> {
436 Ok(self.clone())
437 }
438
439 pub(crate) fn conditional_enforce_equal(
440 &self,
441 other: &Self,
442 should_enforce: &Boolean<BaseField>,
443 ) -> R1CSResult<()> {
444 assert_eq!(self.get_optimization_type(), other.get_optimization_type());
445
446 let params = get_params(
447 TargetField::MODULUS_BIT_SIZE as usize,
448 BaseField::MODULUS_BIT_SIZE as usize,
449 self.get_optimization_type(),
450 );
451
452 // Get p
453 let p_representations =
454 AllocatedNonNativeFieldVar::<TargetField, BaseField>::get_limbs_representations_from_big_integer(
455 &<TargetField as PrimeField>::MODULUS,
456 self.get_optimization_type()
457 )?;
458 let p_bigint = limbs_to_bigint(params.bits_per_limb, &p_representations);
459
460 let mut p_gadget_limbs = Vec::new();
461 for limb in p_representations.iter() {
462 p_gadget_limbs.push(FpVar::<BaseField>::Constant(*limb));
463 }
464 let p_gadget = AllocatedNonNativeFieldVar::<TargetField, BaseField> {
465 cs: self.cs(),
466 limbs: p_gadget_limbs,
467 num_of_additions_over_normal_form: BaseField::one(),
468 is_in_the_normal_form: false,
469 target_phantom: PhantomData,
470 };
471
472 // Get delta = self - other
473 let cs = self.cs().or(other.cs()).or(should_enforce.cs());
474 let mut delta = self.sub_without_reduce(other)?;
475 delta = should_enforce.select(&delta, &Self::zero(cs.clone())?)?;
476
477 // Allocate k = delta / p
478 let k_gadget = FpVar::<BaseField>::new_witness(ns!(cs, "k"), || {
479 let mut delta_limbs_values = Vec::<BaseField>::new();
480 for limb in delta.limbs.iter() {
481 delta_limbs_values.push(limb.value()?);
482 }
483
484 let delta_bigint = limbs_to_bigint(params.bits_per_limb, &delta_limbs_values);
485
486 Ok(bigint_to_basefield::<BaseField>(&(delta_bigint / p_bigint)))
487 })?;
488
489 let surfeit = overhead!(delta.num_of_additions_over_normal_form + BaseField::one()) + 1;
490 Reducer::<TargetField, BaseField>::limb_to_bits(&k_gadget, surfeit)?;
491
492 // Compute k * p
493 let mut kp_gadget_limbs = Vec::new();
494 for limb in p_gadget.limbs.iter() {
495 kp_gadget_limbs.push(limb * &k_gadget);
496 }
497
498 // Enforce delta = kp
499 Reducer::<TargetField, BaseField>::group_and_check_equality(
500 surfeit,
501 params.bits_per_limb,
502 params.bits_per_limb,
503 &delta.limbs,
504 &kp_gadget_limbs,
505 )?;
506
507 Ok(())
508 }
509
510 #[tracing::instrument(target = "r1cs")]
511 pub(crate) fn conditional_enforce_not_equal(
512 &self,
513 other: &Self,
514 should_enforce: &Boolean<BaseField>,
515 ) -> R1CSResult<()> {
516 assert_eq!(self.get_optimization_type(), other.get_optimization_type());
517
518 let cs = self.cs().or(other.cs()).or(should_enforce.cs());
519
520 let _ = should_enforce
521 .select(&self.sub(other)?, &Self::one(cs)?)?
522 .inverse()?;
523
524 Ok(())
525 }
526
527 pub(crate) fn get_optimization_type(&self) -> OptimizationType {
528 match self.cs().optimization_goal() {
529 OptimizationGoal::None => OptimizationType::Constraints,
530 OptimizationGoal::Constraints => OptimizationType::Constraints,
531 OptimizationGoal::Weight => OptimizationType::Weight,
532 }
533 }
534
535 /// Allocates a new variable, but does not check that the allocation's limbs are in-range.
536 fn new_variable_unchecked<T: Borrow<TargetField>>(
537 cs: impl Into<Namespace<BaseField>>,
538 f: impl FnOnce() -> Result<T, SynthesisError>,
539 mode: AllocationMode,
540 ) -> R1CSResult<Self> {
541 let ns = cs.into();
542 let cs = ns.cs();
543
544 let optimization_type = match cs.optimization_goal() {
545 OptimizationGoal::None => OptimizationType::Constraints,
546 OptimizationGoal::Constraints => OptimizationType::Constraints,
547 OptimizationGoal::Weight => OptimizationType::Weight,
548 };
549
550 let zero = TargetField::zero();
551
552 let elem = match f() {
553 Ok(t) => *(t.borrow()),
554 Err(_) => zero,
555 };
556 let elem_representations = Self::get_limbs_representations(&elem, optimization_type)?;
557 let mut limbs = Vec::new();
558
559 for limb in elem_representations.iter() {
560 limbs.push(FpVar::<BaseField>::new_variable(
561 ark_relations::ns!(cs, "alloc"),
562 || Ok(limb),
563 mode,
564 )?);
565 }
566
567 let num_of_additions_over_normal_form = if mode != AllocationMode::Witness {
568 BaseField::zero()
569 } else {
570 BaseField::one()
571 };
572
573 Ok(Self {
574 cs,
575 limbs,
576 num_of_additions_over_normal_form,
577 is_in_the_normal_form: mode != AllocationMode::Witness,
578 target_phantom: PhantomData,
579 })
580 }
581
582 /// Check that this element is in-range; i.e., each limb is in-range, and the whole number is
583 /// less than the modulus.
584 ///
585 /// Returns the bits of the element, in little-endian form
586 fn enforce_in_range(
587 &self,
588 cs: impl Into<Namespace<BaseField>>,
589 ) -> R1CSResult<Vec<Boolean<BaseField>>> {
590 let ns = cs.into();
591 let cs = ns.cs();
592 let optimization_type = match cs.optimization_goal() {
593 OptimizationGoal::None => OptimizationType::Constraints,
594 OptimizationGoal::Constraints => OptimizationType::Constraints,
595 OptimizationGoal::Weight => OptimizationType::Weight,
596 };
597 let params = get_params(
598 TargetField::MODULUS_BIT_SIZE as usize,
599 BaseField::MODULUS_BIT_SIZE as usize,
600 optimization_type,
601 );
602 let mut bits = Vec::new();
603 for limb in self.limbs.iter().rev().take(params.num_limbs - 1) {
604 bits.extend(
605 Reducer::<TargetField, BaseField>::limb_to_bits(limb, params.bits_per_limb)?
606 .into_iter()
607 .rev(),
608 );
609 }
610
611 bits.extend(
612 Reducer::<TargetField, BaseField>::limb_to_bits(
613 &self.limbs[0],
614 TargetField::MODULUS_BIT_SIZE as usize
615 - (params.num_limbs - 1) * params.bits_per_limb,
616 )?
617 .into_iter()
618 .rev(),
619 );
620 Ok(bits)
621 }
622
623 /// Allocates a new non-native field witness with value given by the function `f`. Enforces
624 /// that the field element has value in `[0, modulus)`, and returns the bits of its binary
625 /// representation. The bits are in little-endian (i.e., the bit at index 0 is the LSB) and the
626 /// bit-vector is empty in non-witness allocation modes.
627 pub fn new_witness_with_le_bits<T: Borrow<TargetField>>(
628 cs: impl Into<Namespace<BaseField>>,
629 f: impl FnOnce() -> Result<T, SynthesisError>,
630 ) -> R1CSResult<(Self, Vec<Boolean<BaseField>>)> {
631 let ns = cs.into();
632 let cs = ns.cs();
633 let this = Self::new_variable_unchecked(ns!(cs, "alloc"), f, AllocationMode::Witness)?;
634 let bits = this.enforce_in_range(ns!(cs, "bits"))?;
635 Ok((this, bits))
636 }
637}
638
639impl<TargetField: PrimeField, BaseField: PrimeField> ToBitsGadget<BaseField>
640 for AllocatedNonNativeFieldVar<TargetField, BaseField>
641{
642 #[tracing::instrument(target = "r1cs")]
643 fn to_bits_le(&self) -> R1CSResult<Vec<Boolean<BaseField>>> {
644 let params = get_params(
645 TargetField::MODULUS_BIT_SIZE as usize,
646 BaseField::MODULUS_BIT_SIZE as usize,
647 self.get_optimization_type(),
648 );
649
650 // Reduce to the normal form
651 // Though, a malicious prover can make it slightly larger than p
652 let mut self_normal = self.clone();
653 Reducer::<TargetField, BaseField>::pre_eq_reduce(&mut self_normal)?;
654
655 // Therefore, we convert it to bits and enforce that it is in the field
656 let mut bits = Vec::<Boolean<BaseField>>::new();
657 for limb in self_normal.limbs.iter() {
658 bits.extend_from_slice(&Reducer::<TargetField, BaseField>::limb_to_bits(
659 &limb,
660 params.bits_per_limb,
661 )?);
662 }
663 bits.reverse();
664
665 let mut b = TargetField::characteristic().to_vec();
666 assert_eq!(b[0] % 2, 1);
667 b[0] -= 1; // This works, because the LSB is one, so there's no borrows.
668 let run = Boolean::<BaseField>::enforce_smaller_or_equal_than_le(&bits, b)?;
669
670 // We should always end in a "run" of zeros, because
671 // the characteristic is an odd prime. So, this should
672 // be empty.
673 assert!(run.is_empty());
674
675 Ok(bits)
676 }
677}
678
679impl<TargetField: PrimeField, BaseField: PrimeField> ToBytesGadget<BaseField>
680 for AllocatedNonNativeFieldVar<TargetField, BaseField>
681{
682 #[tracing::instrument(target = "r1cs")]
683 fn to_bytes(&self) -> R1CSResult<Vec<UInt8<BaseField>>> {
684 let mut bits = self.to_bits_le()?;
685
686 let num_bits = TargetField::BigInt::NUM_LIMBS * 64;
687 assert!(bits.len() <= num_bits);
688 bits.resize_with(num_bits, || Boolean::constant(false));
689
690 let bytes = bits.chunks(8).map(UInt8::from_bits_le).collect();
691 Ok(bytes)
692 }
693}
694
695impl<TargetField: PrimeField, BaseField: PrimeField> CondSelectGadget<BaseField>
696 for AllocatedNonNativeFieldVar<TargetField, BaseField>
697{
698 #[tracing::instrument(target = "r1cs")]
699 fn conditionally_select(
700 cond: &Boolean<BaseField>,
701 true_value: &Self,
702 false_value: &Self,
703 ) -> R1CSResult<Self> {
704 assert_eq!(
705 true_value.get_optimization_type(),
706 false_value.get_optimization_type()
707 );
708
709 let mut limbs_sel = Vec::with_capacity(true_value.limbs.len());
710
711 for (x, y) in true_value.limbs.iter().zip(&false_value.limbs) {
712 limbs_sel.push(FpVar::<BaseField>::conditionally_select(cond, x, y)?);
713 }
714
715 Ok(Self {
716 cs: true_value.cs().or(false_value.cs()),
717 limbs: limbs_sel,
718 num_of_additions_over_normal_form: max(
719 true_value.num_of_additions_over_normal_form,
720 false_value.num_of_additions_over_normal_form,
721 ),
722 is_in_the_normal_form: true_value.is_in_the_normal_form
723 && false_value.is_in_the_normal_form,
724 target_phantom: PhantomData,
725 })
726 }
727}
728
729impl<TargetField: PrimeField, BaseField: PrimeField> TwoBitLookupGadget<BaseField>
730 for AllocatedNonNativeFieldVar<TargetField, BaseField>
731{
732 type TableConstant = TargetField;
733
734 #[tracing::instrument(target = "r1cs")]
735 fn two_bit_lookup(
736 bits: &[Boolean<BaseField>],
737 constants: &[Self::TableConstant],
738 ) -> R1CSResult<Self> {
739 debug_assert!(bits.len() == 2);
740 debug_assert!(constants.len() == 4);
741
742 let cs = bits.cs();
743
744 let optimization_type = match cs.optimization_goal() {
745 OptimizationGoal::None => OptimizationType::Constraints,
746 OptimizationGoal::Constraints => OptimizationType::Constraints,
747 OptimizationGoal::Weight => OptimizationType::Weight,
748 };
749
750 let params = get_params(
751 TargetField::MODULUS_BIT_SIZE as usize,
752 BaseField::MODULUS_BIT_SIZE as usize,
753 optimization_type,
754 );
755 let mut limbs_constants = Vec::new();
756 for _ in 0..params.num_limbs {
757 limbs_constants.push(Vec::new());
758 }
759
760 for constant in constants.iter() {
761 let representations =
762 AllocatedNonNativeFieldVar::<TargetField, BaseField>::get_limbs_representations(
763 constant,
764 optimization_type,
765 )?;
766
767 for (i, representation) in representations.iter().enumerate() {
768 limbs_constants[i].push(*representation);
769 }
770 }
771
772 let mut limbs = Vec::new();
773 for limbs_constant in limbs_constants.iter() {
774 limbs.push(FpVar::<BaseField>::two_bit_lookup(bits, limbs_constant)?);
775 }
776
777 Ok(AllocatedNonNativeFieldVar::<TargetField, BaseField> {
778 cs,
779 limbs,
780 num_of_additions_over_normal_form: BaseField::zero(),
781 is_in_the_normal_form: true,
782 target_phantom: PhantomData,
783 })
784 }
785}
786
787impl<TargetField: PrimeField, BaseField: PrimeField> ThreeBitCondNegLookupGadget<BaseField>
788 for AllocatedNonNativeFieldVar<TargetField, BaseField>
789{
790 type TableConstant = TargetField;
791
792 #[tracing::instrument(target = "r1cs")]
793 fn three_bit_cond_neg_lookup(
794 bits: &[Boolean<BaseField>],
795 b0b1: &Boolean<BaseField>,
796 constants: &[Self::TableConstant],
797 ) -> R1CSResult<Self> {
798 debug_assert!(bits.len() == 3);
799 debug_assert!(constants.len() == 4);
800
801 let cs = bits.cs().or(b0b1.cs());
802
803 let optimization_type = match cs.optimization_goal() {
804 OptimizationGoal::None => OptimizationType::Constraints,
805 OptimizationGoal::Constraints => OptimizationType::Constraints,
806 OptimizationGoal::Weight => OptimizationType::Weight,
807 };
808
809 let params = get_params(
810 TargetField::MODULUS_BIT_SIZE as usize,
811 BaseField::MODULUS_BIT_SIZE as usize,
812 optimization_type,
813 );
814
815 let mut limbs_constants = Vec::new();
816 for _ in 0..params.num_limbs {
817 limbs_constants.push(Vec::new());
818 }
819
820 for constant in constants.iter() {
821 let representations =
822 AllocatedNonNativeFieldVar::<TargetField, BaseField>::get_limbs_representations(
823 constant,
824 optimization_type,
825 )?;
826
827 for (i, representation) in representations.iter().enumerate() {
828 limbs_constants[i].push(*representation);
829 }
830 }
831
832 let mut limbs = Vec::new();
833 for limbs_constant in limbs_constants.iter() {
834 limbs.push(FpVar::<BaseField>::three_bit_cond_neg_lookup(
835 bits,
836 b0b1,
837 limbs_constant,
838 )?);
839 }
840
841 Ok(AllocatedNonNativeFieldVar::<TargetField, BaseField> {
842 cs,
843 limbs,
844 num_of_additions_over_normal_form: BaseField::zero(),
845 is_in_the_normal_form: true,
846 target_phantom: PhantomData,
847 })
848 }
849}
850
851impl<TargetField: PrimeField, BaseField: PrimeField> AllocVar<TargetField, BaseField>
852 for AllocatedNonNativeFieldVar<TargetField, BaseField>
853{
854 fn new_variable<T: Borrow<TargetField>>(
855 cs: impl Into<Namespace<BaseField>>,
856 f: impl FnOnce() -> Result<T, SynthesisError>,
857 mode: AllocationMode,
858 ) -> R1CSResult<Self> {
859 let ns = cs.into();
860 let cs = ns.cs();
861 let this = Self::new_variable_unchecked(ns!(cs, "alloc"), f, mode)?;
862 if mode == AllocationMode::Witness {
863 this.enforce_in_range(ns!(cs, "bits"))?;
864 }
865 Ok(this)
866 }
867}
868
869impl<TargetField: PrimeField, BaseField: PrimeField> ToConstraintFieldGadget<BaseField>
870 for AllocatedNonNativeFieldVar<TargetField, BaseField>
871{
872 fn to_constraint_field(&self) -> R1CSResult<Vec<FpVar<BaseField>>> {
873 // provide a unique representation of the nonnative variable
874 // step 1: convert it into a bit sequence
875 let bits = self.to_bits_le()?;
876
877 // step 2: obtain the parameters for weight-optimized (often, fewer limbs)
878 let params = get_params(
879 TargetField::MODULUS_BIT_SIZE as usize,
880 BaseField::MODULUS_BIT_SIZE as usize,
881 OptimizationType::Weight,
882 );
883
884 // step 3: assemble the limbs
885 let mut limbs = bits
886 .chunks(params.bits_per_limb)
887 .map(|chunk| {
888 let mut limb = FpVar::<BaseField>::zero();
889 let mut w = BaseField::one();
890 for b in chunk.iter() {
891 limb += FpVar::from(b.clone()) * w;
892 w.double_in_place();
893 }
894 limb
895 })
896 .collect::<Vec<FpVar<BaseField>>>();
897
898 limbs.reverse();
899
900 // step 4: output the limbs
901 Ok(limbs)
902 }
903}
904
905/*
906 * Implementation of a few traits
907 */
908
909impl<TargetField: PrimeField, BaseField: PrimeField> Clone
910 for AllocatedNonNativeFieldVar<TargetField, BaseField>
911{
912 fn clone(&self) -> Self {
913 AllocatedNonNativeFieldVar {
914 cs: self.cs(),
915 limbs: self.limbs.clone(),
916 num_of_additions_over_normal_form: self.num_of_additions_over_normal_form,
917 is_in_the_normal_form: self.is_in_the_normal_form,
918 target_phantom: PhantomData,
919 }
920 }
921}