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