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