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