ark-r1cs-std/src/fields/emulated_fp/allocated_field_var.rs
src/fields/emulated_fp/allocated_field_var.rsRaw
1use super::{
2 params::{get_params, OptimizationType},
3 reduce::{bigint_to_basefield, limbs_to_bigint, Reducer},
4 AllocatedMulResultVar,
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 `EmulatedFpVar` (introduced below)
23#[derive(Debug)]
24#[must_use]
25pub struct AllocatedEmulatedFpVar<TargetF: PrimeField, BaseF: PrimeField> {
26 /// Constraint system reference
27 pub cs: ConstraintSystemRef<BaseF>,
28 /// The limbs, each of which is a BaseF gadget.
29 pub limbs: Vec<FpVar<BaseF>>,
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: BaseF,
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 TargetF).
36 pub is_in_the_normal_form: bool,
37 #[doc(hidden)]
38 pub target_phantom: PhantomData<TargetF>,
39}
40
41impl<TargetF: PrimeField, BaseF: PrimeField> AllocatedEmulatedFpVar<TargetF, BaseF> {
42 /// Return cs
43 pub fn cs(&self) -> ConstraintSystemRef<BaseF> {
44 self.cs.clone()
45 }
46
47 /// Obtain the value of limbs
48 pub fn limbs_to_value(limbs: Vec<BaseF>, optimization_type: OptimizationType) -> TargetF {
49 let params = get_params(
50 TargetF::MODULUS_BIT_SIZE as usize,
51 BaseF::MODULUS_BIT_SIZE as usize,
52 optimization_type,
53 );
54
55 // Convert 2^{(params.bits_per_limb - 1)} into the TargetF and then double
56 // the base This is because 2^{(params.bits_per_limb)} might indeed be
57 // larger than the target field's prime.
58 let base_repr = TargetF::ONE.into_bigint() << (params.bits_per_limb - 1) as u32;
59
60 let mut base = TargetF::from_bigint(base_repr).unwrap();
61 base.double_in_place();
62
63 let mut result = TargetF::zero();
64 let mut power = TargetF::one();
65
66 for limb in limbs.iter().rev() {
67 let mut val = TargetF::zero();
68 let mut cur = TargetF::one();
69
70 for bit in limb.into_bigint().to_bits_be().iter().rev() {
71 if *bit {
72 val += &cur;
73 }
74 cur.double_in_place();
75 }
76
77 result += &(val * power);
78 power *= &base;
79 }
80
81 result
82 }
83
84 /// Obtain the value of a emulated field element
85 pub fn value(&self) -> R1CSResult<TargetF> {
86 let mut limbs = Vec::new();
87 for limb in self.limbs.iter() {
88 limbs.push(limb.value()?);
89 }
90
91 Ok(Self::limbs_to_value(limbs, self.get_optimization_type()))
92 }
93
94 /// Obtain the emulated field element of a constant value
95 pub fn constant(cs: ConstraintSystemRef<BaseF>, value: TargetF) -> R1CSResult<Self> {
96 let optimization_type = match cs.optimization_goal() {
97 OptimizationGoal::None => OptimizationType::Constraints,
98 OptimizationGoal::Constraints => OptimizationType::Constraints,
99 OptimizationGoal::Weight => OptimizationType::Weight,
100 };
101
102 let limbs_value = Self::get_limbs_representations(&value, optimization_type)?;
103
104 let mut limbs = Vec::new();
105
106 for limb_value in limbs_value.iter() {
107 limbs.push(FpVar::<BaseF>::new_constant(ns!(cs, "limb"), limb_value)?);
108 }
109
110 Ok(Self {
111 cs,
112 limbs,
113 num_of_additions_over_normal_form: BaseF::zero(),
114 is_in_the_normal_form: true,
115 target_phantom: PhantomData,
116 })
117 }
118
119 /// Obtain the emulated field element of one
120 pub fn one(cs: ConstraintSystemRef<BaseF>) -> R1CSResult<Self> {
121 Self::constant(cs, TargetF::one())
122 }
123
124 /// Obtain the emulated field element of zero
125 pub fn zero(cs: ConstraintSystemRef<BaseF>) -> R1CSResult<Self> {
126 Self::constant(cs, TargetF::zero())
127 }
128
129 /// Add a emulated 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(&BaseF::one()),
146 is_in_the_normal_form: false,
147 target_phantom: PhantomData,
148 };
149
150 Reducer::<TargetF, BaseF>::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: &TargetF) -> 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(&BaseF::one()),
170 is_in_the_normal_form: false,
171 target_phantom: PhantomData,
172 };
173
174 Reducer::<TargetF, BaseF>::post_add_reduce(&mut res)?;
175
176 Ok(res)
177 }
178
179 /// Subtract a emulated 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 TargetF::MODULUS_BIT_SIZE as usize,
186 BaseF::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 + BaseF::one()) + 1;
192 let mut other = other.clone();
193 if (surfeit + params.bits_per_limb > BaseF::MODULUS_BIT_SIZE as usize - 1)
194 || (surfeit
195 + (TargetF::MODULUS_BIT_SIZE as usize
196 - params.bits_per_limb * (params.num_limbs - 1))
197 > BaseF::MODULUS_BIT_SIZE as usize - 1)
198 {
199 Reducer::reduce(&mut other)?;
200 surfeit = overhead!(other.num_of_additions_over_normal_form + BaseF::ONE) + 1;
201 }
202
203 // Step 2: construct the padding
204 let mut pad_non_top_limb = BaseF::ONE.into_bigint();
205 let mut pad_top_limb = pad_non_top_limb;
206
207 pad_non_top_limb <<= (surfeit + params.bits_per_limb) as u32;
208 let pad_non_top_limb = BaseF::from_bigint(pad_non_top_limb).unwrap();
209
210 pad_top_limb <<= (surfeit + TargetF::MODULUS_BIT_SIZE as usize
211 - params.bits_per_limb * (params.num_limbs - 1)) as u32;
212 let pad_top_limb = BaseF::from_bigint(pad_top_limb).unwrap();
213
214 let mut pad_limbs = Vec::with_capacity(self.limbs.len());
215 pad_limbs.push(pad_top_limb);
216 for _ in 0..self.limbs.len() - 1 {
217 pad_limbs.push(pad_non_top_limb);
218 }
219
220 // Step 3: prepare to pad the padding to k * p for some k
221 let pad_to_kp_gap = Self::limbs_to_value(pad_limbs, self.get_optimization_type()).neg();
222 let pad_to_kp_limbs =
223 Self::get_limbs_representations(&pad_to_kp_gap, self.get_optimization_type())?;
224
225 // Step 4: the result is self + pad + pad_to_kp - other
226 let mut limbs = Vec::with_capacity(self.limbs.len());
227 for (i, ((this_limb, other_limb), pad_to_kp_limb)) in self
228 .limbs
229 .iter()
230 .zip(&other.limbs)
231 .zip(&pad_to_kp_limbs)
232 .enumerate()
233 {
234 if i != 0 {
235 limbs.push(this_limb + pad_non_top_limb + *pad_to_kp_limb - other_limb);
236 } else {
237 limbs.push(this_limb + pad_top_limb + *pad_to_kp_limb - other_limb);
238 }
239 }
240
241 let result = AllocatedEmulatedFpVar::<TargetF, BaseF> {
242 cs: self.cs(),
243 limbs,
244 num_of_additions_over_normal_form: self.num_of_additions_over_normal_form
245 + (other.num_of_additions_over_normal_form + BaseF::one())
246 + (other.num_of_additions_over_normal_form + BaseF::one()),
247 is_in_the_normal_form: false,
248 target_phantom: PhantomData,
249 };
250
251 Ok(result)
252 }
253
254 /// Subtract a emulated field element
255 #[tracing::instrument(target = "r1cs")]
256 pub fn sub(&self, other: &Self) -> R1CSResult<Self> {
257 assert_eq!(self.get_optimization_type(), other.get_optimization_type());
258
259 let mut result = self.sub_without_reduce(other)?;
260 Reducer::<TargetF, BaseF>::post_add_reduce(&mut result)?;
261 Ok(result)
262 }
263
264 /// Subtract a constant
265 #[tracing::instrument(target = "r1cs")]
266 pub fn sub_constant(&self, other: &TargetF) -> R1CSResult<Self> {
267 self.sub(&Self::constant(self.cs(), *other)?)
268 }
269
270 /// Multiply a emulated field element
271 #[tracing::instrument(target = "r1cs")]
272 pub fn mul(&self, other: &Self) -> R1CSResult<Self> {
273 assert_eq!(self.get_optimization_type(), other.get_optimization_type());
274
275 self.mul_without_reduce(&other)?.reduce()
276 }
277
278 /// Multiply a constant
279 pub fn mul_constant(&self, other: &TargetF) -> R1CSResult<Self> {
280 self.mul(&Self::constant(self.cs(), *other)?)
281 }
282
283 /// Compute the negate of a emulated field element
284 #[tracing::instrument(target = "r1cs")]
285 pub fn negate(&self) -> R1CSResult<Self> {
286 Self::zero(self.cs())?.sub(self)
287 }
288
289 /// Compute the inverse of a emulated field element
290 #[tracing::instrument(target = "r1cs")]
291 pub fn inverse(&self) -> R1CSResult<Self> {
292 let inverse = Self::new_witness(self.cs(), || {
293 Ok(self.value()?.inverse().unwrap_or_else(TargetF::zero))
294 })?;
295
296 let actual_result = self.clone().mul(&inverse)?;
297 actual_result.conditional_enforce_equal(&Self::one(self.cs())?, &Boolean::TRUE)?;
298 Ok(inverse)
299 }
300
301 /// Convert a `TargetF` element into limbs (not constraints)
302 /// This is an internal function that would be reused by a number of other
303 /// functions
304 pub fn get_limbs_representations(
305 elem: &TargetF,
306 optimization_type: OptimizationType,
307 ) -> R1CSResult<Vec<BaseF>> {
308 Self::get_limbs_representations_from_big_integer(&elem.into_bigint(), optimization_type)
309 }
310
311 /// Obtain the limbs directly from a big int
312 pub fn get_limbs_representations_from_big_integer(
313 elem: &<TargetF as PrimeField>::BigInt,
314 optimization_type: OptimizationType,
315 ) -> R1CSResult<Vec<BaseF>> {
316 let params = get_params(
317 TargetF::MODULUS_BIT_SIZE as usize,
318 BaseF::MODULUS_BIT_SIZE as usize,
319 optimization_type,
320 );
321
322 // push the lower limbs first
323 let mut limbs: Vec<BaseF> = Vec::new();
324 let mut cur = *elem;
325 for _ in 0..params.num_limbs {
326 let cur_bits = cur.to_bits_be(); // `to_bits` is big endian
327 let cur_mod_r = <BaseF as PrimeField>::BigInt::from_bits_be(
328 &cur_bits[cur_bits.len() - params.bits_per_limb..],
329 ); // therefore, the lowest `bits_per_non_top_limb` bits is what we want.
330 limbs.push(BaseF::from_bigint(cur_mod_r).unwrap());
331 cur >>= params.bits_per_limb as u32;
332 }
333
334 // then we reserve, so that the limbs are ``big limb first''
335 limbs.reverse();
336
337 Ok(limbs)
338 }
339
340 /// for advanced use, multiply and output the intermediate representations
341 /// (without reduction) This intermediate representations can be added
342 /// with each other, and they can later be reduced back to the
343 /// `EmulatedFpVar`.
344 #[tracing::instrument(target = "r1cs")]
345 pub fn mul_without_reduce(
346 &self,
347 other: &Self,
348 ) -> R1CSResult<AllocatedMulResultVar<TargetF, BaseF>> {
349 assert_eq!(self.get_optimization_type(), other.get_optimization_type());
350
351 let params = get_params(
352 TargetF::MODULUS_BIT_SIZE as usize,
353 BaseF::MODULUS_BIT_SIZE as usize,
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::<TargetF, BaseF>::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::<BaseF>::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 = BaseF::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| BaseF::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(AllocatedMulResultVar {
425 cs: self.cs(),
426 limbs: prod_limbs,
427 prod_of_num_of_additions: (self_reduced.num_of_additions_over_normal_form
428 + BaseF::one())
429 * (other_reduced.num_of_additions_over_normal_form + BaseF::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<BaseF>,
442 ) -> R1CSResult<()> {
443 assert_eq!(self.get_optimization_type(), other.get_optimization_type());
444
445 let params = get_params(
446 TargetF::MODULUS_BIT_SIZE as usize,
447 BaseF::MODULUS_BIT_SIZE as usize,
448 self.get_optimization_type(),
449 );
450
451 // Get p
452 let p_representations =
453 AllocatedEmulatedFpVar::<TargetF, BaseF>::get_limbs_representations_from_big_integer(
454 &<TargetF as PrimeField>::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::<BaseF>::Constant(*limb));
462 }
463 let p_gadget = AllocatedEmulatedFpVar::<TargetF, BaseF> {
464 cs: self.cs(),
465 limbs: p_gadget_limbs,
466 num_of_additions_over_normal_form: BaseF::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::<BaseF>::new_witness(ns!(cs, "k"), || {
478 let mut delta_limbs_values = Vec::<BaseF>::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::<BaseF>(&(delta_bigint / p_bigint)))
486 })?;
487
488 let surfeit = overhead!(delta.num_of_additions_over_normal_form + BaseF::one()) + 1;
489 Reducer::<TargetF, BaseF>::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::<TargetF, BaseF>::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<BaseF>,
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
535 /// are in-range.
536 fn new_variable_unchecked<T: Borrow<TargetF>>(
537 cs: impl Into<Namespace<BaseF>>,
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 = TargetF::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::<BaseF>::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 BaseF::zero()
569 } else {
570 BaseF::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
583 /// the whole number is less than the modulus.
584 ///
585 /// Returns the bits of the element, in little-endian form
586 fn enforce_in_range(&self, cs: impl Into<Namespace<BaseF>>) -> R1CSResult<Vec<Boolean<BaseF>>> {
587 let ns = cs.into();
588 let cs = ns.cs();
589 let optimization_type = match cs.optimization_goal() {
590 OptimizationGoal::None => OptimizationType::Constraints,
591 OptimizationGoal::Constraints => OptimizationType::Constraints,
592 OptimizationGoal::Weight => OptimizationType::Weight,
593 };
594 let params = get_params(
595 TargetF::MODULUS_BIT_SIZE as usize,
596 BaseF::MODULUS_BIT_SIZE as usize,
597 optimization_type,
598 );
599 let mut bits = Vec::new();
600 for limb in self.limbs.iter().rev().take(params.num_limbs - 1) {
601 bits.extend(
602 Reducer::<TargetF, BaseF>::limb_to_bits(limb, params.bits_per_limb)?
603 .into_iter()
604 .rev(),
605 );
606 }
607
608 bits.extend(
609 Reducer::<TargetF, BaseF>::limb_to_bits(
610 &self.limbs[0],
611 TargetF::MODULUS_BIT_SIZE as usize - (params.num_limbs - 1) * params.bits_per_limb,
612 )?
613 .into_iter()
614 .rev(),
615 );
616 Ok(bits)
617 }
618
619 /// Allocates a new non-native field witness with value given by the
620 /// function `f`. Enforces that the field element has value in `[0, modulus)`,
621 /// and returns the bits of its binary representation.
622 /// The bits are in little-endian (i.e., the bit at index 0 is the LSB) and the
623 /// bit-vector is empty in non-witness allocation modes.
624 pub fn new_witness_with_le_bits<T: Borrow<TargetF>>(
625 cs: impl Into<Namespace<BaseF>>,
626 f: impl FnOnce() -> Result<T, SynthesisError>,
627 ) -> R1CSResult<(Self, Vec<Boolean<BaseF>>)> {
628 let ns = cs.into();
629 let cs = ns.cs();
630 let this = Self::new_variable_unchecked(ns!(cs, "alloc"), f, AllocationMode::Witness)?;
631 let bits = this.enforce_in_range(ns!(cs, "bits"))?;
632 Ok((this, bits))
633 }
634}
635
636impl<TargetF: PrimeField, BaseF: PrimeField> ToBitsGadget<BaseF>
637 for AllocatedEmulatedFpVar<TargetF, BaseF>
638{
639 #[tracing::instrument(target = "r1cs")]
640 fn to_bits_le(&self) -> R1CSResult<Vec<Boolean<BaseF>>> {
641 let params = get_params(
642 TargetF::MODULUS_BIT_SIZE as usize,
643 BaseF::MODULUS_BIT_SIZE as usize,
644 self.get_optimization_type(),
645 );
646
647 // Reduce to the normal form
648 // Though, a malicious prover can make it slightly larger than p
649 let mut self_normal = self.clone();
650 Reducer::<TargetF, BaseF>::pre_eq_reduce(&mut self_normal)?;
651
652 // Therefore, we convert it to bits and enforce that it is in the field
653 let mut bits = Vec::<Boolean<BaseF>>::new();
654 for limb in self_normal.limbs.iter() {
655 bits.extend_from_slice(&Reducer::<TargetF, BaseF>::limb_to_bits(
656 &limb,
657 params.bits_per_limb,
658 )?);
659 }
660 bits.reverse();
661
662 let mut b = TargetF::characteristic().to_vec();
663 assert_eq!(b[0] % 2, 1);
664 b[0] -= 1; // This works, because the LSB is one, so there's no borrows.
665 let run = Boolean::<BaseF>::enforce_smaller_or_equal_than_le(&bits, b)?;
666
667 // We should always end in a "run" of zeros, because
668 // the characteristic is an odd prime. So, this should
669 // be empty.
670 assert!(run.is_empty());
671
672 Ok(bits)
673 }
674}
675
676impl<TargetF: PrimeField, BaseF: PrimeField> ToBytesGadget<BaseF>
677 for AllocatedEmulatedFpVar<TargetF, BaseF>
678{
679 #[tracing::instrument(target = "r1cs")]
680 fn to_bytes(&self) -> R1CSResult<Vec<UInt8<BaseF>>> {
681 let mut bits = self.to_bits_le()?;
682
683 let num_bits = TargetF::BigInt::NUM_LIMBS * 64;
684 assert!(bits.len() <= num_bits);
685 bits.resize_with(num_bits, || Boolean::constant(false));
686
687 let bytes = bits.chunks(8).map(UInt8::from_bits_le).collect();
688 Ok(bytes)
689 }
690}
691
692impl<TargetF: PrimeField, BaseF: PrimeField> CondSelectGadget<BaseF>
693 for AllocatedEmulatedFpVar<TargetF, BaseF>
694{
695 #[tracing::instrument(target = "r1cs")]
696 fn conditionally_select(
697 cond: &Boolean<BaseF>,
698 true_value: &Self,
699 false_value: &Self,
700 ) -> R1CSResult<Self> {
701 assert_eq!(
702 true_value.get_optimization_type(),
703 false_value.get_optimization_type()
704 );
705
706 let mut limbs_sel = Vec::with_capacity(true_value.limbs.len());
707
708 for (x, y) in true_value.limbs.iter().zip(&false_value.limbs) {
709 limbs_sel.push(FpVar::<BaseF>::conditionally_select(cond, x, y)?);
710 }
711
712 Ok(Self {
713 cs: true_value.cs().or(false_value.cs()),
714 limbs: limbs_sel,
715 num_of_additions_over_normal_form: max(
716 true_value.num_of_additions_over_normal_form,
717 false_value.num_of_additions_over_normal_form,
718 ),
719 is_in_the_normal_form: true_value.is_in_the_normal_form
720 && false_value.is_in_the_normal_form,
721 target_phantom: PhantomData,
722 })
723 }
724}
725
726impl<TargetF: PrimeField, BaseF: PrimeField> TwoBitLookupGadget<BaseF>
727 for AllocatedEmulatedFpVar<TargetF, BaseF>
728{
729 type TableConstant = TargetF;
730
731 #[tracing::instrument(target = "r1cs")]
732 fn two_bit_lookup(
733 bits: &[Boolean<BaseF>],
734 constants: &[Self::TableConstant],
735 ) -> R1CSResult<Self> {
736 debug_assert!(bits.len() == 2);
737 debug_assert!(constants.len() == 4);
738
739 let cs = bits.cs();
740
741 let optimization_type = match cs.optimization_goal() {
742 OptimizationGoal::None => OptimizationType::Constraints,
743 OptimizationGoal::Constraints => OptimizationType::Constraints,
744 OptimizationGoal::Weight => OptimizationType::Weight,
745 };
746
747 let params = get_params(
748 TargetF::MODULUS_BIT_SIZE as usize,
749 BaseF::MODULUS_BIT_SIZE as usize,
750 optimization_type,
751 );
752 let mut limbs_constants = Vec::new();
753 for _ in 0..params.num_limbs {
754 limbs_constants.push(Vec::new());
755 }
756
757 for constant in constants.iter() {
758 let representations =
759 AllocatedEmulatedFpVar::<TargetF, BaseF>::get_limbs_representations(
760 constant,
761 optimization_type,
762 )?;
763
764 for (i, representation) in representations.iter().enumerate() {
765 limbs_constants[i].push(*representation);
766 }
767 }
768
769 let mut limbs = Vec::new();
770 for limbs_constant in limbs_constants.iter() {
771 limbs.push(FpVar::<BaseF>::two_bit_lookup(bits, limbs_constant)?);
772 }
773
774 Ok(AllocatedEmulatedFpVar::<TargetF, BaseF> {
775 cs,
776 limbs,
777 num_of_additions_over_normal_form: BaseF::zero(),
778 is_in_the_normal_form: true,
779 target_phantom: PhantomData,
780 })
781 }
782}
783
784impl<TargetF: PrimeField, BaseF: PrimeField> ThreeBitCondNegLookupGadget<BaseF>
785 for AllocatedEmulatedFpVar<TargetF, BaseF>
786{
787 type TableConstant = TargetF;
788
789 #[tracing::instrument(target = "r1cs")]
790 fn three_bit_cond_neg_lookup(
791 bits: &[Boolean<BaseF>],
792 b0b1: &Boolean<BaseF>,
793 constants: &[Self::TableConstant],
794 ) -> R1CSResult<Self> {
795 debug_assert!(bits.len() == 3);
796 debug_assert!(constants.len() == 4);
797
798 let cs = bits.cs().or(b0b1.cs());
799
800 let optimization_type = match cs.optimization_goal() {
801 OptimizationGoal::None => OptimizationType::Constraints,
802 OptimizationGoal::Constraints => OptimizationType::Constraints,
803 OptimizationGoal::Weight => OptimizationType::Weight,
804 };
805
806 let params = get_params(
807 TargetF::MODULUS_BIT_SIZE as usize,
808 BaseF::MODULUS_BIT_SIZE as usize,
809 optimization_type,
810 );
811
812 let mut limbs_constants = Vec::new();
813 for _ in 0..params.num_limbs {
814 limbs_constants.push(Vec::new());
815 }
816
817 for constant in constants.iter() {
818 let representations =
819 AllocatedEmulatedFpVar::<TargetF, BaseF>::get_limbs_representations(
820 constant,
821 optimization_type,
822 )?;
823
824 for (i, representation) in representations.iter().enumerate() {
825 limbs_constants[i].push(*representation);
826 }
827 }
828
829 let mut limbs = Vec::new();
830 for limbs_constant in limbs_constants.iter() {
831 limbs.push(FpVar::<BaseF>::three_bit_cond_neg_lookup(
832 bits,
833 b0b1,
834 limbs_constant,
835 )?);
836 }
837
838 Ok(AllocatedEmulatedFpVar::<TargetF, BaseF> {
839 cs,
840 limbs,
841 num_of_additions_over_normal_form: BaseF::zero(),
842 is_in_the_normal_form: true,
843 target_phantom: PhantomData,
844 })
845 }
846}
847
848impl<TargetF: PrimeField, BaseF: PrimeField> AllocVar<TargetF, BaseF>
849 for AllocatedEmulatedFpVar<TargetF, BaseF>
850{
851 fn new_variable<T: Borrow<TargetF>>(
852 cs: impl Into<Namespace<BaseF>>,
853 f: impl FnOnce() -> Result<T, SynthesisError>,
854 mode: AllocationMode,
855 ) -> R1CSResult<Self> {
856 let ns = cs.into();
857 let cs = ns.cs();
858 let this = Self::new_variable_unchecked(ns!(cs, "alloc"), f, mode)?;
859 if mode == AllocationMode::Witness {
860 this.enforce_in_range(ns!(cs, "bits"))?;
861 }
862 Ok(this)
863 }
864}
865
866impl<TargetF: PrimeField, BaseF: PrimeField> ToConstraintFieldGadget<BaseF>
867 for AllocatedEmulatedFpVar<TargetF, BaseF>
868{
869 fn to_constraint_field(&self) -> R1CSResult<Vec<FpVar<BaseF>>> {
870 // provide a unique representation of the emulated variable
871 // step 1: convert it into a bit sequence
872 let bits = self.to_bits_le()?;
873
874 // step 2: obtain the parameters for weight-optimized (often, fewer limbs)
875 let params = get_params(
876 TargetF::MODULUS_BIT_SIZE as usize,
877 BaseF::MODULUS_BIT_SIZE as usize,
878 OptimizationType::Weight,
879 );
880
881 // step 3: assemble the limbs
882 let mut limbs = bits
883 .chunks(params.bits_per_limb)
884 .map(|chunk| {
885 let mut limb = FpVar::<BaseF>::zero();
886 let mut w = BaseF::one();
887 for b in chunk.iter() {
888 limb += FpVar::from(b.clone()) * w;
889 w.double_in_place();
890 }
891 limb
892 })
893 .collect::<Vec<FpVar<BaseF>>>();
894
895 limbs.reverse();
896
897 // step 4: output the limbs
898 Ok(limbs)
899 }
900}
901
902// Implementation of a few traits
903
904impl<TargetF: PrimeField, BaseF: PrimeField> Clone for AllocatedEmulatedFpVar<TargetF, BaseF> {
905 fn clone(&self) -> Self {
906 AllocatedEmulatedFpVar {
907 cs: self.cs(),
908 limbs: self.limbs.clone(),
909 num_of_additions_over_normal_form: self.num_of_additions_over_normal_form,
910 is_in_the_normal_form: self.is_in_the_normal_form,
911 target_phantom: PhantomData,
912 }
913 }
914}