ark-r1cs-std/src/fields/emulated_fp/reduce.rs
src/fields/emulated_fp/reduce.rsRaw
1use super::{overhead, params::get_params, AllocatedEmulatedFpVar};
2use crate::{
3 alloc::AllocVar,
4 boolean::Boolean,
5 eq::EqGadget,
6 fields::{fp::FpVar, FieldVar},
7 R1CSVar,
8};
9use ark_ff::{biginteger::BigInteger, BitIteratorBE, One, PrimeField, Zero};
10use ark_relations::{
11 ns,
12 r1cs::{ConstraintSystemRef, Result as R1CSResult},
13};
14use ark_std::{cmp::min, marker::PhantomData, vec, vec::Vec};
15use num_bigint::BigUint;
16use num_integer::Integer;
17
18pub fn limbs_to_bigint<BaseF: PrimeField>(bits_per_limb: usize, limbs: &[BaseF]) -> BigUint {
19 let mut val = BigUint::zero();
20 let mut big_cur = BigUint::one();
21 let two = BigUint::from(2u32);
22 for limb in limbs.iter().rev() {
23 let limb_repr = limb.into_bigint().to_bits_le();
24 let mut small_cur = big_cur.clone();
25 for limb_bit in limb_repr.iter() {
26 if *limb_bit {
27 val += &small_cur;
28 }
29 small_cur *= 2u32;
30 }
31 big_cur *= two.pow(bits_per_limb as u32);
32 }
33
34 val
35}
36
37pub fn bigint_to_basefield<BaseF: PrimeField>(bigint: &BigUint) -> BaseF {
38 let mut val = BaseF::zero();
39 let mut cur = BaseF::one();
40 let bytes = bigint.to_bytes_be();
41
42 let basefield_256 = BaseF::from_bigint(<BaseF as PrimeField>::BigInt::from(256u64)).unwrap();
43
44 for byte in bytes.iter().rev() {
45 let bytes_basefield = BaseF::from(*byte as u128);
46 val += cur * bytes_basefield;
47
48 cur *= &basefield_256;
49 }
50
51 val
52}
53
54/// the collections of methods for reducing the presentations
55pub struct Reducer<TargetF: PrimeField, BaseF: PrimeField> {
56 pub target_phantom: PhantomData<TargetF>,
57 pub base_phantom: PhantomData<BaseF>,
58}
59
60impl<TargetF: PrimeField, BaseF: PrimeField> Reducer<TargetF, BaseF> {
61 /// convert limbs to bits (take at most `BaseF::MODULUS_BIT_SIZE as
62 /// usize - 1` bits) This implementation would be more efficient than
63 /// the original `to_bits` or `to_non_unique_bits` since we enforce that
64 /// some bits are always zero.
65 #[tracing::instrument(target = "r1cs")]
66 pub fn limb_to_bits(limb: &FpVar<BaseF>, num_bits: usize) -> R1CSResult<Vec<Boolean<BaseF>>> {
67 let cs = limb.cs();
68
69 let num_bits = min(BaseF::MODULUS_BIT_SIZE as usize - 1, num_bits);
70 let mut bits_considered = Vec::with_capacity(num_bits);
71 let limb_value = limb.value().unwrap_or_default();
72
73 let num_bits_to_shave = BaseF::BigInt::NUM_LIMBS * 64 - (BaseF::MODULUS_BIT_SIZE as usize);
74
75 for b in BitIteratorBE::new(limb_value.into_bigint())
76 .skip(num_bits_to_shave + (BaseF::MODULUS_BIT_SIZE as usize - num_bits))
77 {
78 bits_considered.push(b);
79 }
80
81 if cs == ConstraintSystemRef::None {
82 let mut bits = vec![];
83 for b in bits_considered {
84 bits.push(Boolean::<BaseF>::Constant(b));
85 }
86
87 Ok(bits)
88 } else {
89 let mut bits = vec![];
90 for b in bits_considered {
91 bits.push(Boolean::<BaseF>::new_witness(
92 ark_relations::ns!(cs, "bit"),
93 || Ok(b),
94 )?);
95 }
96
97 let mut bit_sum = FpVar::<BaseF>::zero();
98 let mut coeff = BaseF::one();
99
100 for bit in bits.iter().rev() {
101 bit_sum += <FpVar<BaseF> as From<Boolean<BaseF>>>::from((*bit).clone()) * coeff;
102 coeff.double_in_place();
103 }
104
105 bit_sum.enforce_equal(limb)?;
106
107 Ok(bits)
108 }
109 }
110
111 /// Reduction to the normal form
112 #[tracing::instrument(target = "r1cs")]
113 pub fn reduce(elem: &mut AllocatedEmulatedFpVar<TargetF, BaseF>) -> R1CSResult<()> {
114 let new_elem = AllocatedEmulatedFpVar::new_witness(ns!(elem.cs(), "normal_form"), || {
115 Ok(elem.value().unwrap_or_default())
116 })?;
117 elem.conditional_enforce_equal(&new_elem, &Boolean::TRUE)?;
118 *elem = new_elem;
119
120 Ok(())
121 }
122
123 /// Reduction to be enforced after additions
124 #[tracing::instrument(target = "r1cs")]
125 pub fn post_add_reduce(elem: &mut AllocatedEmulatedFpVar<TargetF, BaseF>) -> R1CSResult<()> {
126 let params = get_params(
127 TargetF::MODULUS_BIT_SIZE as usize,
128 BaseF::MODULUS_BIT_SIZE as usize,
129 elem.get_optimization_type(),
130 );
131 let surfeit = overhead!(elem.num_of_additions_over_normal_form + BaseF::one()) + 1;
132
133 if BaseF::MODULUS_BIT_SIZE as usize > 2 * params.bits_per_limb + surfeit + 1 {
134 Ok(())
135 } else {
136 Self::reduce(elem)
137 }
138 }
139
140 /// Reduction used before multiplication to reduce the representations in a
141 /// way that allows efficient multiplication
142 #[tracing::instrument(target = "r1cs")]
143 pub fn pre_mul_reduce(
144 elem: &mut AllocatedEmulatedFpVar<TargetF, BaseF>,
145 elem_other: &mut AllocatedEmulatedFpVar<TargetF, BaseF>,
146 ) -> R1CSResult<()> {
147 assert_eq!(
148 elem.get_optimization_type(),
149 elem_other.get_optimization_type()
150 );
151
152 let params = get_params(
153 TargetF::MODULUS_BIT_SIZE as usize,
154 BaseF::MODULUS_BIT_SIZE as usize,
155 elem.get_optimization_type(),
156 );
157
158 if 2 * params.bits_per_limb + ark_std::log2(params.num_limbs) as usize
159 > BaseF::MODULUS_BIT_SIZE as usize - 1
160 {
161 panic!("The current limb parameters do not support multiplication.");
162 }
163
164 loop {
165 let prod_of_num_of_additions = (elem.num_of_additions_over_normal_form + BaseF::one())
166 * (elem_other.num_of_additions_over_normal_form + BaseF::one());
167 let overhead_limb = overhead!(prod_of_num_of_additions.mul(
168 &BaseF::from_bigint(<BaseF as PrimeField>::BigInt::from(
169 (params.num_limbs) as u64
170 ))
171 .unwrap()
172 ));
173 let bits_per_mulresult_limb = 2 * (params.bits_per_limb + 1) + overhead_limb;
174
175 if bits_per_mulresult_limb < BaseF::MODULUS_BIT_SIZE as usize {
176 break;
177 }
178
179 if elem.num_of_additions_over_normal_form
180 >= elem_other.num_of_additions_over_normal_form
181 {
182 Self::reduce(elem)?;
183 } else {
184 Self::reduce(elem_other)?;
185 }
186 }
187
188 Ok(())
189 }
190
191 /// Reduction to the normal form
192 #[tracing::instrument(target = "r1cs")]
193 pub fn pre_eq_reduce(elem: &mut AllocatedEmulatedFpVar<TargetF, BaseF>) -> R1CSResult<()> {
194 if elem.is_in_the_normal_form {
195 return Ok(());
196 }
197
198 Self::reduce(elem)
199 }
200
201 /// Group and check equality
202 #[tracing::instrument(target = "r1cs")]
203 pub fn group_and_check_equality(
204 surfeit: usize,
205 bits_per_limb: usize,
206 shift_per_limb: usize,
207 left: &[FpVar<BaseF>],
208 right: &[FpVar<BaseF>],
209 ) -> R1CSResult<()> {
210 let cs = left.cs().or(right.cs());
211 let zero = FpVar::<BaseF>::zero();
212
213 let mut limb_pairs = Vec::<(FpVar<BaseF>, FpVar<BaseF>)>::new();
214 let num_limb_in_a_group = (BaseF::MODULUS_BIT_SIZE as usize
215 - 1
216 - surfeit
217 - 1
218 - 1
219 - 1
220 - (bits_per_limb - shift_per_limb))
221 / shift_per_limb;
222
223 let shift_array = {
224 let mut array = Vec::new();
225 let mut cur = BaseF::one().into_bigint();
226 for _ in 0..num_limb_in_a_group {
227 array.push(BaseF::from_bigint(cur).unwrap());
228 cur <<= shift_per_limb as u32;
229 }
230
231 array
232 };
233
234 for (left_limb, right_limb) in left.iter().zip(right.iter()).rev() {
235 // note: the `rev` operation is here, so that the first limb (and the first
236 // groupped limb) will be the least significant limb.
237 limb_pairs.push((left_limb.clone(), right_limb.clone()));
238 }
239
240 let mut groupped_limb_pairs = Vec::<(FpVar<BaseF>, FpVar<BaseF>, usize)>::new();
241
242 for limb_pairs_in_a_group in limb_pairs.chunks(num_limb_in_a_group) {
243 let mut left_total_limb = zero.clone();
244 let mut right_total_limb = zero.clone();
245
246 for ((left_limb, right_limb), shift) in
247 limb_pairs_in_a_group.iter().zip(shift_array.iter())
248 {
249 left_total_limb += &(left_limb * *shift);
250 right_total_limb += &(right_limb * *shift);
251 }
252
253 groupped_limb_pairs.push((
254 left_total_limb,
255 right_total_limb,
256 limb_pairs_in_a_group.len(),
257 ));
258 }
259
260 // This part we mostly use the techniques in bellman-bignat
261 // The following code is adapted from https://github.com/alex-ozdemir/bellman-bignat/blob/master/src/mp/bignat.rs#L567
262 let mut carry_in = zero;
263 let mut carry_in_value = BaseF::zero();
264 let mut accumulated_extra = BigUint::zero();
265 for (group_id, (left_total_limb, right_total_limb, num_limb_in_this_group)) in
266 groupped_limb_pairs.iter().enumerate()
267 {
268 let mut pad_limb_repr = BaseF::ONE.into_bigint();
269
270 pad_limb_repr <<= (surfeit
271 + (bits_per_limb - shift_per_limb)
272 + shift_per_limb * num_limb_in_this_group
273 + 1
274 + 1) as u32;
275 let pad_limb = BaseF::from_bigint(pad_limb_repr).unwrap();
276
277 let left_total_limb_value = left_total_limb.value().unwrap_or_default();
278 let right_total_limb_value = right_total_limb.value().unwrap_or_default();
279
280 let mut carry_value =
281 left_total_limb_value + carry_in_value + pad_limb - right_total_limb_value;
282
283 let carry_repr =
284 carry_value.into_bigint() >> (shift_per_limb * num_limb_in_this_group) as u32;
285
286 carry_value = BaseF::from_bigint(carry_repr).unwrap();
287
288 let carry = FpVar::new_witness(cs.clone(), || Ok(carry_value))?;
289
290 accumulated_extra += limbs_to_bigint(bits_per_limb, &[pad_limb]);
291
292 let (new_accumulated_extra, remainder) = accumulated_extra.div_rem(
293 &BigUint::from(2u64).pow((shift_per_limb * num_limb_in_this_group) as u32),
294 );
295 let remainder_limb = bigint_to_basefield::<BaseF>(&remainder);
296
297 // Now check
298 // left_total_limb + pad_limb + carry_in - right_total_limb
299 // = carry shift by (shift_per_limb * num_limb_in_this_group) + remainder
300
301 let eqn_left = left_total_limb + pad_limb + &carry_in - right_total_limb;
302
303 let eqn_right = &carry
304 * BaseF::from(2u64).pow(&[(shift_per_limb * num_limb_in_this_group) as u64])
305 + remainder_limb;
306
307 eqn_left.conditional_enforce_equal(&eqn_right, &Boolean::<BaseF>::TRUE)?;
308
309 accumulated_extra = new_accumulated_extra;
310 carry_in = carry.clone();
311 carry_in_value = carry_value;
312
313 if group_id == groupped_limb_pairs.len() - 1 {
314 carry.enforce_equal(&FpVar::<BaseF>::Constant(bigint_to_basefield(
315 &accumulated_extra,
316 )))?;
317 } else {
318 Reducer::<TargetF, BaseF>::limb_to_bits(&carry, surfeit + bits_per_limb)?;
319 }
320 }
321
322 Ok(())
323 }
324}