ark-r1cs-std/src/fields/nonnative/allocated_mul_result.rs
src/fields/nonnative/allocated_mul_result.rsRaw
1use super::{
2 params::{get_params, OptimizationType},
3 reduce::{bigint_to_basefield, limbs_to_bigint, Reducer},
4 AllocatedNonNativeFieldVar,
5};
6use crate::{fields::fp::FpVar, prelude::*};
7use ark_ff::PrimeField;
8use ark_relations::{
9 ns,
10 r1cs::{ConstraintSystemRef, OptimizationGoal, Result as R1CSResult},
11};
12use ark_std::{marker::PhantomData, vec::Vec};
13use num_bigint::BigUint;
14
15/// The allocated form of `NonNativeFieldMulResultVar` (introduced below)
16#[derive(Debug)]
17#[must_use]
18pub struct AllocatedNonNativeFieldMulResultVar<TargetField: PrimeField, BaseField: PrimeField> {
19 /// Constraint system reference
20 pub cs: ConstraintSystemRef<BaseField>,
21 /// Limbs of the intermediate representations
22 pub limbs: Vec<FpVar<BaseField>>,
23 /// The cumulative num of additions
24 pub prod_of_num_of_additions: BaseField,
25 #[doc(hidden)]
26 pub target_phantom: PhantomData<TargetField>,
27}
28
29impl<TargetField: PrimeField, BaseField: PrimeField>
30 From<&AllocatedNonNativeFieldVar<TargetField, BaseField>>
31 for AllocatedNonNativeFieldMulResultVar<TargetField, BaseField>
32{
33 fn from(src: &AllocatedNonNativeFieldVar<TargetField, BaseField>) -> Self {
34 let params = get_params(
35 TargetField::MODULUS_BIT_SIZE as usize,
36 BaseField::MODULUS_BIT_SIZE as usize,
37 src.get_optimization_type(),
38 );
39
40 let mut limbs = src.limbs.clone();
41 limbs.reverse();
42 limbs.resize(2 * params.num_limbs - 1, FpVar::<BaseField>::zero());
43 limbs.reverse();
44
45 let prod_of_num_of_additions = src.num_of_additions_over_normal_form + &BaseField::one();
46
47 Self {
48 cs: src.cs(),
49 limbs,
50 prod_of_num_of_additions,
51 target_phantom: PhantomData,
52 }
53 }
54}
55
56impl<TargetField: PrimeField, BaseField: PrimeField>
57 AllocatedNonNativeFieldMulResultVar<TargetField, BaseField>
58{
59 /// Get the CS
60 pub fn cs(&self) -> ConstraintSystemRef<BaseField> {
61 self.cs.clone()
62 }
63
64 /// Get the value of the multiplication result
65 pub fn value(&self) -> R1CSResult<TargetField> {
66 let params = get_params(
67 TargetField::MODULUS_BIT_SIZE as usize,
68 BaseField::MODULUS_BIT_SIZE as usize,
69 self.get_optimization_type(),
70 );
71
72 let p_representations =
73 AllocatedNonNativeFieldVar::<TargetField, BaseField>::get_limbs_representations_from_big_integer(
74 &<TargetField as PrimeField>::MODULUS,
75 self.get_optimization_type()
76 )?;
77 let p_bigint = limbs_to_bigint(params.bits_per_limb, &p_representations);
78
79 let mut limbs_values = Vec::<BaseField>::new();
80 for limb in self.limbs.iter() {
81 limbs_values.push(limb.value().unwrap_or_default());
82 }
83 let value_bigint = limbs_to_bigint(params.bits_per_limb, &limbs_values);
84
85 let res = bigint_to_basefield::<TargetField>(&(value_bigint % p_bigint));
86 Ok(res)
87 }
88
89 /// Constraints for reducing the result of a multiplication mod p, to get an
90 /// original representation.
91 pub fn reduce(&self) -> R1CSResult<AllocatedNonNativeFieldVar<TargetField, BaseField>> {
92 let params = get_params(
93 TargetField::MODULUS_BIT_SIZE as usize,
94 BaseField::MODULUS_BIT_SIZE as usize,
95 self.get_optimization_type(),
96 );
97
98 // Step 1: get p
99 let p_representations =
100 AllocatedNonNativeFieldVar::<TargetField, BaseField>::get_limbs_representations_from_big_integer(
101 &<TargetField as PrimeField>::MODULUS,
102 self.get_optimization_type()
103 )?;
104 let p_bigint = limbs_to_bigint(params.bits_per_limb, &p_representations);
105
106 let mut p_gadget_limbs = Vec::new();
107 for limb in p_representations.iter() {
108 p_gadget_limbs.push(FpVar::<BaseField>::new_constant(self.cs(), limb)?);
109 }
110 let p_gadget = AllocatedNonNativeFieldVar::<TargetField, BaseField> {
111 cs: self.cs(),
112 limbs: p_gadget_limbs,
113 num_of_additions_over_normal_form: BaseField::one(),
114 is_in_the_normal_form: false,
115 target_phantom: PhantomData,
116 };
117
118 // Step 2: compute surfeit
119 let surfeit = overhead!(self.prod_of_num_of_additions + BaseField::one()) + 1 + 1;
120
121 // Step 3: allocate k
122 let k_bits = {
123 let mut res = Vec::new();
124
125 let mut limbs_values = Vec::<BaseField>::new();
126 for limb in self.limbs.iter() {
127 limbs_values.push(limb.value().unwrap_or_default());
128 }
129
130 let value_bigint = limbs_to_bigint(params.bits_per_limb, &limbs_values);
131 let mut k_cur = value_bigint / p_bigint;
132
133 let total_len = TargetField::MODULUS_BIT_SIZE as usize + surfeit;
134
135 for _ in 0..total_len {
136 res.push(Boolean::<BaseField>::new_witness(self.cs(), || {
137 Ok(&k_cur % 2u64 == BigUint::from(1u64))
138 })?);
139 k_cur /= 2u64;
140 }
141 res
142 };
143
144 let k_limbs = {
145 let zero = FpVar::Constant(BaseField::zero());
146 let mut limbs = Vec::new();
147
148 let mut k_bits_cur = k_bits.clone();
149
150 for i in 0..params.num_limbs {
151 let this_limb_size = if i != params.num_limbs - 1 {
152 params.bits_per_limb
153 } else {
154 k_bits.len() - (params.num_limbs - 1) * params.bits_per_limb
155 };
156
157 let this_limb_bits = k_bits_cur[0..this_limb_size].to_vec();
158 k_bits_cur = k_bits_cur[this_limb_size..].to_vec();
159
160 let mut limb = zero.clone();
161 let mut cur = BaseField::one();
162
163 for bit in this_limb_bits.iter() {
164 limb += &(FpVar::<BaseField>::from(bit.clone()) * cur);
165 cur.double_in_place();
166 }
167 limbs.push(limb);
168 }
169
170 limbs.reverse();
171 limbs
172 };
173
174 let k_gadget = AllocatedNonNativeFieldVar::<TargetField, BaseField> {
175 cs: self.cs(),
176 limbs: k_limbs,
177 num_of_additions_over_normal_form: self.prod_of_num_of_additions,
178 is_in_the_normal_form: false,
179 target_phantom: PhantomData,
180 };
181
182 let cs = self.cs();
183
184 let r_gadget = AllocatedNonNativeFieldVar::<TargetField, BaseField>::new_witness(
185 ns!(cs, "r"),
186 || Ok(self.value()?),
187 )?;
188
189 let params = get_params(
190 TargetField::MODULUS_BIT_SIZE as usize,
191 BaseField::MODULUS_BIT_SIZE as usize,
192 self.get_optimization_type(),
193 );
194
195 // Step 1: reduce `self` and `other` if neceessary
196 let mut prod_limbs = Vec::new();
197 let zero = FpVar::<BaseField>::zero();
198
199 for _ in 0..2 * params.num_limbs - 1 {
200 prod_limbs.push(zero.clone());
201 }
202
203 for i in 0..params.num_limbs {
204 for j in 0..params.num_limbs {
205 prod_limbs[i + j] = &prod_limbs[i + j] + (&p_gadget.limbs[i] * &k_gadget.limbs[j]);
206 }
207 }
208
209 let mut kp_plus_r_gadget = Self {
210 cs,
211 limbs: prod_limbs,
212 prod_of_num_of_additions: (p_gadget.num_of_additions_over_normal_form
213 + BaseField::one())
214 * (k_gadget.num_of_additions_over_normal_form + BaseField::one()),
215 target_phantom: PhantomData,
216 };
217
218 let kp_plus_r_limbs_len = kp_plus_r_gadget.limbs.len();
219 for (i, limb) in r_gadget.limbs.iter().rev().enumerate() {
220 kp_plus_r_gadget.limbs[kp_plus_r_limbs_len - 1 - i] += limb;
221 }
222
223 Reducer::<TargetField, BaseField>::group_and_check_equality(
224 surfeit,
225 2 * params.bits_per_limb,
226 params.bits_per_limb,
227 &self.limbs,
228 &kp_plus_r_gadget.limbs,
229 )?;
230
231 Ok(r_gadget)
232 }
233
234 /// Add unreduced elements.
235 #[tracing::instrument(target = "r1cs")]
236 pub fn add(&self, other: &Self) -> R1CSResult<Self> {
237 assert_eq!(self.get_optimization_type(), other.get_optimization_type());
238
239 let mut new_limbs = Vec::new();
240
241 for (l1, l2) in self.limbs.iter().zip(other.limbs.iter()) {
242 let new_limb = l1 + l2;
243 new_limbs.push(new_limb);
244 }
245
246 Ok(Self {
247 cs: self.cs(),
248 limbs: new_limbs,
249 prod_of_num_of_additions: self.prod_of_num_of_additions
250 + other.prod_of_num_of_additions,
251 target_phantom: PhantomData,
252 })
253 }
254
255 /// Add native constant elem
256 #[tracing::instrument(target = "r1cs")]
257 pub fn add_constant(&self, other: &TargetField) -> R1CSResult<Self> {
258 let mut other_limbs =
259 AllocatedNonNativeFieldVar::<TargetField, BaseField>::get_limbs_representations(
260 other,
261 self.get_optimization_type(),
262 )?;
263 other_limbs.reverse();
264
265 let mut new_limbs = Vec::new();
266
267 for (i, limb) in self.limbs.iter().rev().enumerate() {
268 if i < other_limbs.len() {
269 new_limbs.push(limb + other_limbs[i]);
270 } else {
271 new_limbs.push((*limb).clone());
272 }
273 }
274
275 new_limbs.reverse();
276
277 Ok(Self {
278 cs: self.cs(),
279 limbs: new_limbs,
280 prod_of_num_of_additions: self.prod_of_num_of_additions + BaseField::one(),
281 target_phantom: PhantomData,
282 })
283 }
284
285 pub(crate) fn get_optimization_type(&self) -> OptimizationType {
286 match self.cs().optimization_goal() {
287 OptimizationGoal::None => OptimizationType::Constraints,
288 OptimizationGoal::Constraints => OptimizationType::Constraints,
289 OptimizationGoal::Weight => OptimizationType::Weight,
290 }
291 }
292}