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