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