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