Nova/src/gadgets/nonnative/bignat.rs
src/gadgets/nonnative/bignat.rsRaw
1use super::{
2 util::{
3 Bitvector, Num, {f_to_nat, nat_to_f},
4 },
5 OptionExt,
6};
7use bellperson::{ConstraintSystem, LinearCombination, SynthesisError};
8use ff::PrimeField;
9use num_bigint::BigInt;
10use num_traits::cast::ToPrimitive;
11use std::borrow::Borrow;
12use std::cmp::{max, min};
13use std::convert::From;
14
15/// Compute the natural number represented by an array of limbs.
16/// The limbs are assumed to be based the `limb_width` power of 2.
17pub fn limbs_to_nat<Scalar: PrimeField, B: Borrow<Scalar>, I: DoubleEndedIterator<Item = B>>(
18 limbs: I,
19 limb_width: usize,
20) -> BigInt {
21 limbs.rev().fold(BigInt::from(0), |mut acc, limb| {
22 acc <<= limb_width as u32;
23 acc += f_to_nat(limb.borrow());
24 acc
25 })
26}
27
28fn int_with_n_ones(n: usize) -> BigInt {
29 let mut m = BigInt::from(1);
30 m <<= n as u32;
31 m -= 1;
32 m
33}
34
35/// Compute the limbs encoding a natural number.
36/// The limbs are assumed to be based the `limb_width` power of 2.
37pub fn nat_to_limbs<Scalar: PrimeField>(
38 nat: &BigInt,
39 limb_width: usize,
40 n_limbs: usize,
41) -> Result<Vec<Scalar>, SynthesisError> {
42 let mask = int_with_n_ones(limb_width);
43 let mut nat = nat.clone();
44 if nat.bits() as usize <= n_limbs * limb_width {
45 Ok(
46 (0..n_limbs)
47 .map(|_| {
48 let r = &nat & &mask;
49 nat >>= limb_width as u32;
50 nat_to_f(&r).unwrap()
51 })
52 .collect(),
53 )
54 } else {
55 eprintln!("nat {nat} does not fit in {n_limbs} limbs of width {limb_width}");
56 Err(SynthesisError::Unsatisfiable)
57 }
58}
59
60#[derive(Clone, PartialEq, Eq)]
61pub struct BigNatParams {
62 pub min_bits: usize,
63 pub max_word: BigInt,
64 pub limb_width: usize,
65 pub n_limbs: usize,
66}
67
68impl BigNatParams {
69 pub fn new(limb_width: usize, n_limbs: usize) -> Self {
70 let mut max_word = BigInt::from(1) << limb_width as u32;
71 max_word -= 1;
72 BigNatParams {
73 max_word,
74 n_limbs,
75 limb_width,
76 min_bits: 0,
77 }
78 }
79}
80
81/// A representation of a large natural number (a member of {0, 1, 2, ... })
82#[derive(Clone)]
83pub struct BigNat<Scalar: PrimeField> {
84 /// The linear combinations which constrain the value of each limb of the number
85 pub limbs: Vec<LinearCombination<Scalar>>,
86 /// The witness values for each limb (filled at witness-time)
87 pub limb_values: Option<Vec<Scalar>>,
88 /// The value of the whole number (filled at witness-time)
89 pub value: Option<BigInt>,
90 /// Parameters
91 pub params: BigNatParams,
92}
93
94impl<Scalar: PrimeField> std::cmp::PartialEq for BigNat<Scalar> {
95 fn eq(&self, other: &Self) -> bool {
96 self.value == other.value && self.params == other.params
97 }
98}
99impl<Scalar: PrimeField> std::cmp::Eq for BigNat<Scalar> {}
100
101impl<Scalar: PrimeField> From<BigNat<Scalar>> for Polynomial<Scalar> {
102 fn from(other: BigNat<Scalar>) -> Polynomial<Scalar> {
103 Polynomial {
104 coefficients: other.limbs,
105 values: other.limb_values,
106 }
107 }
108}
109
110impl<Scalar: PrimeField> BigNat<Scalar> {
111 /// Allocates a `BigNat` in the circuit with `n_limbs` limbs of width `limb_width` each.
112 /// If `max_word` is missing, then it is assumed to be `(2 << limb_width) - 1`.
113 /// The value is provided by a closure returning limb values.
114 pub fn alloc_from_limbs<CS, F>(
115 mut cs: CS,
116 f: F,
117 max_word: Option<BigInt>,
118 limb_width: usize,
119 n_limbs: usize,
120 ) -> Result<Self, SynthesisError>
121 where
122 CS: ConstraintSystem<Scalar>,
123 F: FnOnce() -> Result<Vec<Scalar>, SynthesisError>,
124 {
125 let values_cell = f();
126 let mut value = None;
127 let mut limb_values = None;
128 let limbs = (0..n_limbs)
129 .map(|limb_i| {
130 cs.alloc(
131 || format!("limb {limb_i}"),
132 || match values_cell {
133 Ok(ref vs) => {
134 if vs.len() != n_limbs {
135 eprintln!("Values do not match stated limb count");
136 return Err(SynthesisError::Unsatisfiable);
137 }
138 if value.is_none() {
139 value = Some(limbs_to_nat::<Scalar, _, _>(vs.iter(), limb_width));
140 }
141 if limb_values.is_none() {
142 limb_values = Some(vs.clone());
143 }
144 Ok(vs[limb_i])
145 }
146 // Hack b/c SynthesisError and io::Error don't implement Clone
147 Err(ref e) => Err(SynthesisError::from(std::io::Error::new(
148 std::io::ErrorKind::Other,
149 format!("{e}"),
150 ))),
151 },
152 )
153 .map(|v| LinearCombination::zero() + v)
154 })
155 .collect::<Result<Vec<_>, _>>()?;
156 Ok(Self {
157 value,
158 limb_values,
159 limbs,
160 params: BigNatParams {
161 min_bits: 0,
162 n_limbs,
163 max_word: max_word.unwrap_or_else(|| int_with_n_ones(limb_width)),
164 limb_width,
165 },
166 })
167 }
168
169 /// Allocates a `BigNat` in the circuit with `n_limbs` limbs of width `limb_width` each.
170 /// The `max_word` is gauranteed to be `(2 << limb_width) - 1`.
171 /// The value is provided by a closure returning a natural number.
172 pub fn alloc_from_nat<CS, F>(
173 mut cs: CS,
174 f: F,
175 limb_width: usize,
176 n_limbs: usize,
177 ) -> Result<Self, SynthesisError>
178 where
179 CS: ConstraintSystem<Scalar>,
180 F: FnOnce() -> Result<BigInt, SynthesisError>,
181 {
182 let all_values_cell =
183 f().and_then(|v| Ok((nat_to_limbs::<Scalar>(&v, limb_width, n_limbs)?, v)));
184 let mut value = None;
185 let mut limb_values = Vec::new();
186 let limbs = (0..n_limbs)
187 .map(|limb_i| {
188 cs.alloc(
189 || format!("limb {limb_i}"),
190 || match all_values_cell {
191 Ok((ref vs, ref v)) => {
192 if value.is_none() {
193 value = Some(v.clone());
194 }
195 limb_values.push(vs[limb_i]);
196 Ok(vs[limb_i])
197 }
198 // Hack b/c SynthesisError and io::Error don't implement Clone
199 Err(ref e) => Err(SynthesisError::from(std::io::Error::new(
200 std::io::ErrorKind::Other,
201 format!("{e}"),
202 ))),
203 },
204 )
205 .map(|v| LinearCombination::zero() + v)
206 })
207 .collect::<Result<Vec<_>, _>>()?;
208 Ok(Self {
209 value,
210 limb_values: if !limb_values.is_empty() {
211 Some(limb_values)
212 } else {
213 None
214 },
215 limbs,
216 params: BigNatParams::new(limb_width, n_limbs),
217 })
218 }
219
220 /// Allocates a `BigNat` in the circuit with `n_limbs` limbs of width `limb_width` each.
221 /// The `max_word` is gauranteed to be `(2 << limb_width) - 1`.
222 /// The value is provided by an allocated number
223 pub fn from_num<CS: ConstraintSystem<Scalar>>(
224 mut cs: CS,
225 n: Num<Scalar>,
226 limb_width: usize,
227 n_limbs: usize,
228 ) -> Result<Self, SynthesisError> {
229 let bignat = Self::alloc_from_nat(
230 cs.namespace(|| "bignat"),
231 || {
232 Ok({
233 n.value
234 .as_ref()
235 .map(|n| f_to_nat(n))
236 .ok_or(SynthesisError::AssignmentMissing)?
237 })
238 },
239 limb_width,
240 n_limbs,
241 )?;
242
243 // check if bignat equals n
244 // (1) decompose `bignat` into a bitvector `bv`
245 let bv = bignat.decompose(cs.namespace(|| "bv"))?;
246 // (2) recompose bits and check if it equals n
247 n.is_equal(cs.namespace(|| "n"), &bv)?;
248
249 Ok(bignat)
250 }
251
252 pub fn as_limbs(&self) -> Vec<Num<Scalar>> {
253 let mut limbs = Vec::new();
254 for (i, lc) in self.limbs.iter().enumerate() {
255 limbs.push(Num::new(
256 self.limb_values.as_ref().map(|vs| vs[i]),
257 lc.clone(),
258 ));
259 }
260 limbs
261 }
262
263 pub fn assert_well_formed<CS: ConstraintSystem<Scalar>>(
264 &self,
265 mut cs: CS,
266 ) -> Result<(), SynthesisError> {
267 // swap the option and iterator
268 let limb_values_split =
269 (0..self.limbs.len()).map(|i| self.limb_values.as_ref().map(|vs| vs[i]));
270 for (i, (limb, limb_value)) in self.limbs.iter().zip(limb_values_split).enumerate() {
271 Num::new(limb_value, limb.clone())
272 .fits_in_bits(cs.namespace(|| format!("{i}")), self.params.limb_width)?;
273 }
274 Ok(())
275 }
276
277 /// Break `self` up into a bit-vector.
278 pub fn decompose<CS: ConstraintSystem<Scalar>>(
279 &self,
280 mut cs: CS,
281 ) -> Result<Bitvector<Scalar>, SynthesisError> {
282 let limb_values_split =
283 (0..self.limbs.len()).map(|i| self.limb_values.as_ref().map(|vs| vs[i]));
284 let bitvectors: Vec<Bitvector<Scalar>> = self
285 .limbs
286 .iter()
287 .zip(limb_values_split)
288 .enumerate()
289 .map(|(i, (limb, limb_value))| {
290 Num::new(limb_value, limb.clone()).decompose(
291 cs.namespace(|| format!("subdecmop {i}")),
292 self.params.limb_width,
293 )
294 })
295 .collect::<Result<Vec<_>, _>>()?;
296 let mut bits = Vec::new();
297 let mut values = Vec::new();
298 let mut allocations = Vec::new();
299 for bv in bitvectors {
300 bits.extend(bv.bits);
301 if let Some(vs) = bv.values {
302 values.extend(vs)
303 };
304 allocations.extend(bv.allocations);
305 }
306 let values = if !values.is_empty() {
307 Some(values)
308 } else {
309 None
310 };
311 Ok(Bitvector {
312 bits,
313 values,
314 allocations,
315 })
316 }
317
318 pub fn enforce_limb_width_agreement(
319 &self,
320 other: &Self,
321 location: &str,
322 ) -> Result<usize, SynthesisError> {
323 if self.params.limb_width == other.params.limb_width {
324 Ok(self.params.limb_width)
325 } else {
326 eprintln!(
327 "Limb widths {}, {}, do not agree at {}",
328 self.params.limb_width, other.params.limb_width, location
329 );
330 Err(SynthesisError::Unsatisfiable)
331 }
332 }
333
334 pub fn from_poly(poly: Polynomial<Scalar>, limb_width: usize, max_word: BigInt) -> Self {
335 Self {
336 params: BigNatParams {
337 min_bits: 0,
338 max_word,
339 n_limbs: poly.coefficients.len(),
340 limb_width,
341 },
342 limbs: poly.coefficients,
343 value: poly
344 .values
345 .as_ref()
346 .map(|limb_values| limbs_to_nat::<Scalar, _, _>(limb_values.iter(), limb_width)),
347 limb_values: poly.values,
348 }
349 }
350
351 /// Constrain `self` to be equal to `other`, after carrying both.
352 pub fn equal_when_carried<CS: ConstraintSystem<Scalar>>(
353 &self,
354 mut cs: CS,
355 other: &Self,
356 ) -> Result<(), SynthesisError> {
357 self.enforce_limb_width_agreement(other, "equal_when_carried")?;
358
359 // We'll propegate carries over the first `n` limbs.
360 let n = min(self.limbs.len(), other.limbs.len());
361 let target_base = BigInt::from(1u8) << self.params.limb_width as u32;
362 let mut accumulated_extra = BigInt::from(0usize);
363 let max_word = std::cmp::max(&self.params.max_word, &other.params.max_word);
364 let carry_bits = (((max_word.to_f64().unwrap() * 2.0).log2() - self.params.limb_width as f64)
365 .ceil()
366 + 0.1) as usize;
367 let mut carry_in = Num::new(Some(Scalar::ZERO), LinearCombination::zero());
368
369 for i in 0..n {
370 let carry = Num::alloc(cs.namespace(|| format!("carry value {i}")), || {
371 Ok(
372 nat_to_f(
373 &((f_to_nat(&self.limb_values.grab()?[i])
374 + f_to_nat(&carry_in.value.unwrap())
375 + max_word
376 - f_to_nat(&other.limb_values.grab()?[i]))
377 / &target_base),
378 )
379 .unwrap(),
380 )
381 })?;
382 accumulated_extra += max_word;
383
384 cs.enforce(
385 || format!("carry {i}"),
386 |lc| lc,
387 |lc| lc,
388 |lc| {
389 lc + &carry_in.num + &self.limbs[i] - &other.limbs[i]
390 + (nat_to_f(max_word).unwrap(), CS::one())
391 - (nat_to_f(&target_base).unwrap(), &carry.num)
392 - (
393 nat_to_f(&(&accumulated_extra % &target_base)).unwrap(),
394 CS::one(),
395 )
396 },
397 );
398
399 accumulated_extra /= &target_base;
400
401 if i < n - 1 {
402 carry.fits_in_bits(cs.namespace(|| format!("carry {i} decomp")), carry_bits)?;
403 } else {
404 cs.enforce(
405 || format!("carry {i} is out"),
406 |lc| lc,
407 |lc| lc,
408 |lc| lc + &carry.num - (nat_to_f(&accumulated_extra).unwrap(), CS::one()),
409 );
410 }
411 carry_in = carry;
412 }
413
414 for (i, zero_limb) in self.limbs.iter().enumerate().skip(n) {
415 cs.enforce(
416 || format!("zero self {i}"),
417 |lc| lc,
418 |lc| lc,
419 |lc| lc + zero_limb,
420 );
421 }
422 for (i, zero_limb) in other.limbs.iter().enumerate().skip(n) {
423 cs.enforce(
424 || format!("zero other {i}"),
425 |lc| lc,
426 |lc| lc,
427 |lc| lc + zero_limb,
428 );
429 }
430 Ok(())
431 }
432
433 /// Constrain `self` to be equal to `other`, after carrying both.
434 /// Uses regrouping internally to take full advantage of the field size and reduce the amount
435 /// of carrying.
436 pub fn equal_when_carried_regroup<CS: ConstraintSystem<Scalar>>(
437 &self,
438 mut cs: CS,
439 other: &Self,
440 ) -> Result<(), SynthesisError> {
441 self.enforce_limb_width_agreement(other, "equal_when_carried_regroup")?;
442 let max_word = std::cmp::max(&self.params.max_word, &other.params.max_word);
443 let carry_bits = (((max_word.to_f64().unwrap() * 2.0).log2() - self.params.limb_width as f64)
444 .ceil()
445 + 0.1) as usize;
446 let limbs_per_group = (Scalar::CAPACITY as usize - carry_bits) / self.params.limb_width;
447 let self_grouped = self.group_limbs(limbs_per_group);
448 let other_grouped = other.group_limbs(limbs_per_group);
449 self_grouped.equal_when_carried(cs.namespace(|| "grouped"), &other_grouped)
450 }
451
452 pub fn add(&self, other: &Self) -> Result<BigNat<Scalar>, SynthesisError> {
453 self.enforce_limb_width_agreement(other, "add")?;
454 let n_limbs = max(self.params.n_limbs, other.params.n_limbs);
455 let max_word = &self.params.max_word + &other.params.max_word;
456 let limbs: Vec<LinearCombination<Scalar>> = (0..n_limbs)
457 .map(|i| match (self.limbs.get(i), other.limbs.get(i)) {
458 (Some(a), Some(b)) => a.clone() + b,
459 (Some(a), None) => a.clone(),
460 (None, Some(b)) => b.clone(),
461 (None, None) => unreachable!(),
462 })
463 .collect();
464 let limb_values: Option<Vec<Scalar>> = self.limb_values.as_ref().and_then(|x| {
465 other.limb_values.as_ref().map(|y| {
466 (0..n_limbs)
467 .map(|i| match (x.get(i), y.get(i)) {
468 (Some(a), Some(b)) => {
469 let mut t = *a;
470 t.add_assign(b);
471 t
472 }
473 (Some(a), None) => *a,
474 (None, Some(a)) => *a,
475 (None, None) => unreachable!(),
476 })
477 .collect()
478 })
479 });
480 let value = self
481 .value
482 .as_ref()
483 .and_then(|x| other.value.as_ref().map(|y| x + y));
484 Ok(Self {
485 limb_values,
486 value,
487 limbs,
488 params: BigNatParams {
489 min_bits: max(self.params.min_bits, other.params.min_bits),
490 n_limbs,
491 max_word,
492 limb_width: self.params.limb_width,
493 },
494 })
495 }
496
497 /// Compute a `BigNat` contrained to be equal to `self * other % modulus`.
498 pub fn mult_mod<CS: ConstraintSystem<Scalar>>(
499 &self,
500 mut cs: CS,
501 other: &Self,
502 modulus: &Self,
503 ) -> Result<(BigNat<Scalar>, BigNat<Scalar>), SynthesisError> {
504 self.enforce_limb_width_agreement(other, "mult_mod")?;
505 let limb_width = self.params.limb_width;
506 let quotient_bits = (self.n_bits() + other.n_bits()).saturating_sub(modulus.params.min_bits);
507 let quotient_limbs = quotient_bits.saturating_sub(1) / limb_width + 1;
508 let quotient = BigNat::alloc_from_nat(
509 cs.namespace(|| "quotient"),
510 || {
511 Ok({
512 let mut x = self.value.grab()?.clone();
513 x *= other.value.grab()?;
514 x /= modulus.value.grab()?;
515 x
516 })
517 },
518 self.params.limb_width,
519 quotient_limbs,
520 )?;
521 quotient.assert_well_formed(cs.namespace(|| "quotient rangecheck"))?;
522 let remainder = BigNat::alloc_from_nat(
523 cs.namespace(|| "remainder"),
524 || {
525 Ok({
526 let mut x = self.value.grab()?.clone();
527 x *= other.value.grab()?;
528 x %= modulus.value.grab()?;
529 x
530 })
531 },
532 self.params.limb_width,
533 modulus.limbs.len(),
534 )?;
535 remainder.assert_well_formed(cs.namespace(|| "remainder rangecheck"))?;
536 let a_poly = Polynomial::from(self.clone());
537 let b_poly = Polynomial::from(other.clone());
538 let mod_poly = Polynomial::from(modulus.clone());
539 let q_poly = Polynomial::from(quotient.clone());
540 let r_poly = Polynomial::from(remainder.clone());
541
542 // a * b
543 let left = a_poly.alloc_product(cs.namespace(|| "left"), &b_poly)?;
544 let right_product = q_poly.alloc_product(cs.namespace(|| "right_product"), &mod_poly)?;
545 // q * m + r
546 let right = right_product.sum(&r_poly);
547
548 let left_max_word = {
549 let mut x = BigInt::from(min(self.limbs.len(), other.limbs.len()));
550 x *= &self.params.max_word;
551 x *= &other.params.max_word;
552 x
553 };
554 let right_max_word = {
555 let mut x = BigInt::from(std::cmp::min(quotient.limbs.len(), modulus.limbs.len()));
556 x *= "ient.params.max_word;
557 x *= &modulus.params.max_word;
558 x += &remainder.params.max_word;
559 x
560 };
561
562 let left_int = BigNat::from_poly(left, limb_width, left_max_word);
563 let right_int = BigNat::from_poly(right, limb_width, right_max_word);
564 left_int.equal_when_carried_regroup(cs.namespace(|| "carry"), &right_int)?;
565 Ok((quotient, remainder))
566 }
567
568 /// Compute a `BigNat` contrained to be equal to `self * other % modulus`.
569 pub fn red_mod<CS: ConstraintSystem<Scalar>>(
570 &self,
571 mut cs: CS,
572 modulus: &Self,
573 ) -> Result<BigNat<Scalar>, SynthesisError> {
574 self.enforce_limb_width_agreement(modulus, "red_mod")?;
575 let limb_width = self.params.limb_width;
576 let quotient_bits = self.n_bits().saturating_sub(modulus.params.min_bits);
577 let quotient_limbs = quotient_bits.saturating_sub(1) / limb_width + 1;
578 let quotient = BigNat::alloc_from_nat(
579 cs.namespace(|| "quotient"),
580 || Ok(self.value.grab()? / modulus.value.grab()?),
581 self.params.limb_width,
582 quotient_limbs,
583 )?;
584 quotient.assert_well_formed(cs.namespace(|| "quotient rangecheck"))?;
585 let remainder = BigNat::alloc_from_nat(
586 cs.namespace(|| "remainder"),
587 || Ok(self.value.grab()? % modulus.value.grab()?),
588 self.params.limb_width,
589 modulus.limbs.len(),
590 )?;
591 remainder.assert_well_formed(cs.namespace(|| "remainder rangecheck"))?;
592 let mod_poly = Polynomial::from(modulus.clone());
593 let q_poly = Polynomial::from(quotient.clone());
594 let r_poly = Polynomial::from(remainder.clone());
595
596 // q * m + r
597 let right_product = q_poly.alloc_product(cs.namespace(|| "right_product"), &mod_poly)?;
598 let right = right_product.sum(&r_poly);
599
600 let right_max_word = {
601 let mut x = BigInt::from(std::cmp::min(quotient.limbs.len(), modulus.limbs.len()));
602 x *= "ient.params.max_word;
603 x *= &modulus.params.max_word;
604 x += &remainder.params.max_word;
605 x
606 };
607
608 let right_int = BigNat::from_poly(right, limb_width, right_max_word);
609 self.equal_when_carried_regroup(cs.namespace(|| "carry"), &right_int)?;
610 Ok(remainder)
611 }
612
613 /// Combines limbs into groups.
614 pub fn group_limbs(&self, limbs_per_group: usize) -> BigNat<Scalar> {
615 let n_groups = (self.limbs.len() - 1) / limbs_per_group + 1;
616 let limb_values = self.limb_values.as_ref().map(|vs| {
617 let mut values: Vec<Scalar> = vec![Scalar::ZERO; n_groups];
618 let mut shift = Scalar::ONE;
619 let limb_block = (0..self.params.limb_width).fold(Scalar::ONE, |mut l, _| {
620 l = l.double();
621 l
622 });
623 for (i, v) in vs.iter().enumerate() {
624 if i % limbs_per_group == 0 {
625 shift = Scalar::ONE;
626 }
627 let mut a = shift;
628 a *= v;
629 values[i / limbs_per_group].add_assign(&a);
630 shift.mul_assign(&limb_block);
631 }
632 values
633 });
634 let limbs = {
635 let mut limbs: Vec<LinearCombination<Scalar>> = vec![LinearCombination::zero(); n_groups];
636 let mut shift = Scalar::ONE;
637 let limb_block = (0..self.params.limb_width).fold(Scalar::ONE, |mut l, _| {
638 l = l.double();
639 l
640 });
641 for (i, limb) in self.limbs.iter().enumerate() {
642 if i % limbs_per_group == 0 {
643 shift = Scalar::ONE;
644 }
645 limbs[i / limbs_per_group] =
646 std::mem::replace(&mut limbs[i / limbs_per_group], LinearCombination::zero())
647 + (shift, limb);
648 shift.mul_assign(&limb_block);
649 }
650 limbs
651 };
652 let max_word = (0..limbs_per_group).fold(BigInt::from(0u8), |mut acc, i| {
653 acc.set_bit((i * self.params.limb_width) as u64, true);
654 acc
655 }) * &self.params.max_word;
656 BigNat {
657 params: BigNatParams {
658 min_bits: self.params.min_bits,
659 limb_width: self.params.limb_width * limbs_per_group,
660 n_limbs: limbs.len(),
661 max_word,
662 },
663 limbs,
664 limb_values,
665 value: self.value.clone(),
666 }
667 }
668
669 pub fn n_bits(&self) -> usize {
670 assert!(self.params.n_limbs > 0);
671 self.params.limb_width * (self.params.n_limbs - 1) + self.params.max_word.bits() as usize
672 }
673}
674
675pub struct Polynomial<Scalar: PrimeField> {
676 pub coefficients: Vec<LinearCombination<Scalar>>,
677 pub values: Option<Vec<Scalar>>,
678}
679
680impl<Scalar: PrimeField> Polynomial<Scalar> {
681 pub fn alloc_product<CS: ConstraintSystem<Scalar>>(
682 &self,
683 mut cs: CS,
684 other: &Self,
685 ) -> Result<Polynomial<Scalar>, SynthesisError> {
686 let n_product_coeffs = self.coefficients.len() + other.coefficients.len() - 1;
687 let values = self.values.as_ref().and_then(|self_vs| {
688 other.values.as_ref().map(|other_vs| {
689 let mut values: Vec<Scalar> = std::iter::repeat_with(|| Scalar::ZERO)
690 .take(n_product_coeffs)
691 .collect();
692 for (self_i, self_v) in self_vs.iter().enumerate() {
693 for (other_i, other_v) in other_vs.iter().enumerate() {
694 let mut v = *self_v;
695 v.mul_assign(other_v);
696 values[self_i + other_i].add_assign(&v);
697 }
698 }
699 values
700 })
701 });
702 let coefficients = (0..n_product_coeffs)
703 .map(|i| {
704 Ok(LinearCombination::zero() + cs.alloc(|| format!("prod {i}"), || Ok(values.grab()?[i]))?)
705 })
706 .collect::<Result<Vec<LinearCombination<Scalar>>, SynthesisError>>()?;
707 let product = Polynomial {
708 coefficients,
709 values,
710 };
711 let one = Scalar::ONE;
712 let mut x = Scalar::ZERO;
713 for _ in 1..(n_product_coeffs + 1) {
714 x.add_assign(&one);
715 cs.enforce(
716 || format!("pointwise product @ {x:?}"),
717 |lc| {
718 let mut i = Scalar::ONE;
719 self.coefficients.iter().fold(lc, |lc, c| {
720 let r = lc + (i, c);
721 i.mul_assign(&x);
722 r
723 })
724 },
725 |lc| {
726 let mut i = Scalar::ONE;
727 other.coefficients.iter().fold(lc, |lc, c| {
728 let r = lc + (i, c);
729 i.mul_assign(&x);
730 r
731 })
732 },
733 |lc| {
734 let mut i = Scalar::ONE;
735 product.coefficients.iter().fold(lc, |lc, c| {
736 let r = lc + (i, c);
737 i.mul_assign(&x);
738 r
739 })
740 },
741 )
742 }
743 Ok(product)
744 }
745
746 pub fn sum(&self, other: &Self) -> Self {
747 let n_coeffs = max(self.coefficients.len(), other.coefficients.len());
748 let values = self.values.as_ref().and_then(|self_vs| {
749 other.values.as_ref().map(|other_vs| {
750 (0..n_coeffs)
751 .map(|i| {
752 let mut s = Scalar::ZERO;
753 if i < self_vs.len() {
754 s.add_assign(&self_vs[i]);
755 }
756 if i < other_vs.len() {
757 s.add_assign(&other_vs[i]);
758 }
759 s
760 })
761 .collect()
762 })
763 });
764 let coefficients = (0..n_coeffs)
765 .map(|i| {
766 let mut lc = LinearCombination::zero();
767 if i < self.coefficients.len() {
768 lc = lc + &self.coefficients[i];
769 }
770 if i < other.coefficients.len() {
771 lc = lc + &other.coefficients[i];
772 }
773 lc
774 })
775 .collect();
776 Polynomial {
777 coefficients,
778 values,
779 }
780 }
781}
782
783#[cfg(test)]
784mod tests {
785 use super::*;
786 use bellperson::Circuit;
787
788 pub struct PolynomialMultiplier<Scalar: PrimeField> {
789 pub a: Vec<Scalar>,
790 pub b: Vec<Scalar>,
791 }
792
793 impl<Scalar: PrimeField> Circuit<Scalar> for PolynomialMultiplier<Scalar> {
794 fn synthesize<CS: ConstraintSystem<Scalar>>(self, cs: &mut CS) -> Result<(), SynthesisError> {
795 let a = Polynomial {
796 coefficients: self
797 .a
798 .iter()
799 .enumerate()
800 .map(|(i, x)| {
801 Ok(LinearCombination::zero() + cs.alloc(|| format!("coeff_a {i}"), || Ok(*x))?)
802 })
803 .collect::<Result<Vec<LinearCombination<Scalar>>, SynthesisError>>()?,
804 values: Some(self.a),
805 };
806 let b = Polynomial {
807 coefficients: self
808 .b
809 .iter()
810 .enumerate()
811 .map(|(i, x)| {
812 Ok(LinearCombination::zero() + cs.alloc(|| format!("coeff_b {i}"), || Ok(*x))?)
813 })
814 .collect::<Result<Vec<LinearCombination<Scalar>>, SynthesisError>>()?,
815 values: Some(self.b),
816 };
817 let _prod = a.alloc_product(cs.namespace(|| "product"), &b)?;
818 Ok(())
819 }
820 }
821}