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<CS: ConstraintSystem<Scalar>>(&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<CS: ConstraintSystem<Scalar>>(
453 &self,
454 other: &Self,
455 ) -> Result<BigNat<Scalar>, SynthesisError> {
456 self.enforce_limb_width_agreement(other, "add")?;
457 let n_limbs = max(self.params.n_limbs, other.params.n_limbs);
458 let max_word = &self.params.max_word + &other.params.max_word;
459 let limbs: Vec<LinearCombination<Scalar>> = (0..n_limbs)
460 .map(|i| match (self.limbs.get(i), other.limbs.get(i)) {
461 (Some(a), Some(b)) => a.clone() + b,
462 (Some(a), None) => a.clone(),
463 (None, Some(b)) => b.clone(),
464 (None, None) => unreachable!(),
465 })
466 .collect();
467 let limb_values: Option<Vec<Scalar>> = self.limb_values.as_ref().and_then(|x| {
468 other.limb_values.as_ref().map(|y| {
469 (0..n_limbs)
470 .map(|i| match (x.get(i), y.get(i)) {
471 (Some(a), Some(b)) => {
472 let mut t = *a;
473 t.add_assign(b);
474 t
475 }
476 (Some(a), None) => *a,
477 (None, Some(a)) => *a,
478 (None, None) => unreachable!(),
479 })
480 .collect()
481 })
482 });
483 let value = self
484 .value
485 .as_ref()
486 .and_then(|x| other.value.as_ref().map(|y| x + y));
487 Ok(Self {
488 limb_values,
489 value,
490 limbs,
491 params: BigNatParams {
492 min_bits: max(self.params.min_bits, other.params.min_bits),
493 n_limbs,
494 max_word,
495 limb_width: self.params.limb_width,
496 },
497 })
498 }
499
500 /// Compute a `BigNat` contrained to be equal to `self * other % modulus`.
501 pub fn mult_mod<CS: ConstraintSystem<Scalar>>(
502 &self,
503 mut cs: CS,
504 other: &Self,
505 modulus: &Self,
506 ) -> Result<(BigNat<Scalar>, BigNat<Scalar>), SynthesisError> {
507 self.enforce_limb_width_agreement(other, "mult_mod")?;
508 let limb_width = self.params.limb_width;
509 let quotient_bits = (self.n_bits() + other.n_bits()).saturating_sub(modulus.params.min_bits);
510 let quotient_limbs = quotient_bits.saturating_sub(1) / limb_width + 1;
511 let quotient = BigNat::alloc_from_nat(
512 cs.namespace(|| "quotient"),
513 || {
514 Ok({
515 let mut x = self.value.grab()?.clone();
516 x *= other.value.grab()?;
517 x /= modulus.value.grab()?;
518 x
519 })
520 },
521 self.params.limb_width,
522 quotient_limbs,
523 )?;
524 quotient.assert_well_formed(cs.namespace(|| "quotient rangecheck"))?;
525 let remainder = BigNat::alloc_from_nat(
526 cs.namespace(|| "remainder"),
527 || {
528 Ok({
529 let mut x = self.value.grab()?.clone();
530 x *= other.value.grab()?;
531 x %= modulus.value.grab()?;
532 x
533 })
534 },
535 self.params.limb_width,
536 modulus.limbs.len(),
537 )?;
538 remainder.assert_well_formed(cs.namespace(|| "remainder rangecheck"))?;
539 let a_poly = Polynomial::from(self.clone());
540 let b_poly = Polynomial::from(other.clone());
541 let mod_poly = Polynomial::from(modulus.clone());
542 let q_poly = Polynomial::from(quotient.clone());
543 let r_poly = Polynomial::from(remainder.clone());
544
545 // a * b
546 let left = a_poly.alloc_product(cs.namespace(|| "left"), &b_poly)?;
547 let right_product = q_poly.alloc_product(cs.namespace(|| "right_product"), &mod_poly)?;
548 // q * m + r
549 let right = right_product.sum(&r_poly);
550
551 let left_max_word = {
552 let mut x = BigInt::from(min(self.limbs.len(), other.limbs.len()));
553 x *= &self.params.max_word;
554 x *= &other.params.max_word;
555 x
556 };
557 let right_max_word = {
558 let mut x = BigInt::from(std::cmp::min(quotient.limbs.len(), modulus.limbs.len()));
559 x *= "ient.params.max_word;
560 x *= &modulus.params.max_word;
561 x += &remainder.params.max_word;
562 x
563 };
564
565 let left_int = BigNat::from_poly(left, limb_width, left_max_word);
566 let right_int = BigNat::from_poly(right, limb_width, right_max_word);
567 left_int.equal_when_carried_regroup(cs.namespace(|| "carry"), &right_int)?;
568 Ok((quotient, remainder))
569 }
570
571 /// Compute a `BigNat` contrained to be equal to `self * other % modulus`.
572 pub fn red_mod<CS: ConstraintSystem<Scalar>>(
573 &self,
574 mut cs: CS,
575 modulus: &Self,
576 ) -> Result<BigNat<Scalar>, SynthesisError> {
577 self.enforce_limb_width_agreement(modulus, "red_mod")?;
578 let limb_width = self.params.limb_width;
579 let quotient_bits = self.n_bits().saturating_sub(modulus.params.min_bits);
580 let quotient_limbs = quotient_bits.saturating_sub(1) / limb_width + 1;
581 let quotient = BigNat::alloc_from_nat(
582 cs.namespace(|| "quotient"),
583 || Ok(self.value.grab()? / modulus.value.grab()?),
584 self.params.limb_width,
585 quotient_limbs,
586 )?;
587 quotient.assert_well_formed(cs.namespace(|| "quotient rangecheck"))?;
588 let remainder = BigNat::alloc_from_nat(
589 cs.namespace(|| "remainder"),
590 || Ok(self.value.grab()? % modulus.value.grab()?),
591 self.params.limb_width,
592 modulus.limbs.len(),
593 )?;
594 remainder.assert_well_formed(cs.namespace(|| "remainder rangecheck"))?;
595 let mod_poly = Polynomial::from(modulus.clone());
596 let q_poly = Polynomial::from(quotient.clone());
597 let r_poly = Polynomial::from(remainder.clone());
598
599 // q * m + r
600 let right_product = q_poly.alloc_product(cs.namespace(|| "right_product"), &mod_poly)?;
601 let right = right_product.sum(&r_poly);
602
603 let right_max_word = {
604 let mut x = BigInt::from(std::cmp::min(quotient.limbs.len(), modulus.limbs.len()));
605 x *= "ient.params.max_word;
606 x *= &modulus.params.max_word;
607 x += &remainder.params.max_word;
608 x
609 };
610
611 let right_int = BigNat::from_poly(right, limb_width, right_max_word);
612 self.equal_when_carried_regroup(cs.namespace(|| "carry"), &right_int)?;
613 Ok(remainder)
614 }
615
616 /// Combines limbs into groups.
617 pub fn group_limbs(&self, limbs_per_group: usize) -> BigNat<Scalar> {
618 let n_groups = (self.limbs.len() - 1) / limbs_per_group + 1;
619 let limb_values = self.limb_values.as_ref().map(|vs| {
620 let mut values: Vec<Scalar> = vec![Scalar::zero(); n_groups];
621 let mut shift = Scalar::one();
622 let limb_block = (0..self.params.limb_width).fold(Scalar::one(), |mut l, _| {
623 l = l.double();
624 l
625 });
626 for (i, v) in vs.iter().enumerate() {
627 if i % limbs_per_group == 0 {
628 shift = Scalar::one();
629 }
630 let mut a = shift;
631 a *= v;
632 values[i / limbs_per_group].add_assign(&a);
633 shift.mul_assign(&limb_block);
634 }
635 values
636 });
637 let limbs = {
638 let mut limbs: Vec<LinearCombination<Scalar>> = vec![LinearCombination::zero(); n_groups];
639 let mut shift = Scalar::one();
640 let limb_block = (0..self.params.limb_width).fold(Scalar::one(), |mut l, _| {
641 l = l.double();
642 l
643 });
644 for (i, limb) in self.limbs.iter().enumerate() {
645 if i % limbs_per_group == 0 {
646 shift = Scalar::one();
647 }
648 limbs[i / limbs_per_group] =
649 std::mem::replace(&mut limbs[i / limbs_per_group], LinearCombination::zero())
650 + (shift, limb);
651 shift.mul_assign(&limb_block);
652 }
653 limbs
654 };
655 let max_word = (0..limbs_per_group).fold(BigInt::from(0u8), |mut acc, i| {
656 acc.set_bit((i * self.params.limb_width) as u64, true);
657 acc
658 }) * &self.params.max_word;
659 BigNat {
660 params: BigNatParams {
661 min_bits: self.params.min_bits,
662 limb_width: self.params.limb_width * limbs_per_group,
663 n_limbs: limbs.len(),
664 max_word,
665 },
666 limbs,
667 limb_values,
668 value: self.value.clone(),
669 }
670 }
671
672 pub fn n_bits(&self) -> usize {
673 assert!(self.params.n_limbs > 0);
674 self.params.limb_width * (self.params.n_limbs - 1) + self.params.max_word.bits() as usize
675 }
676}
677
678pub struct Polynomial<Scalar: PrimeField> {
679 pub coefficients: Vec<LinearCombination<Scalar>>,
680 pub values: Option<Vec<Scalar>>,
681}
682
683impl<Scalar: PrimeField> Polynomial<Scalar> {
684 pub fn alloc_product<CS: ConstraintSystem<Scalar>>(
685 &self,
686 mut cs: CS,
687 other: &Self,
688 ) -> Result<Polynomial<Scalar>, SynthesisError> {
689 let n_product_coeffs = self.coefficients.len() + other.coefficients.len() - 1;
690 let values = self.values.as_ref().and_then(|self_vs| {
691 other.values.as_ref().map(|other_vs| {
692 let mut values: Vec<Scalar> = std::iter::repeat_with(Scalar::zero)
693 .take(n_product_coeffs)
694 .collect();
695 for (self_i, self_v) in self_vs.iter().enumerate() {
696 for (other_i, other_v) in other_vs.iter().enumerate() {
697 let mut v = *self_v;
698 v.mul_assign(other_v);
699 values[self_i + other_i].add_assign(&v);
700 }
701 }
702 values
703 })
704 });
705 let coefficients = (0..n_product_coeffs)
706 .map(|i| {
707 Ok(LinearCombination::zero() + cs.alloc(|| format!("prod {i}"), || Ok(values.grab()?[i]))?)
708 })
709 .collect::<Result<Vec<LinearCombination<Scalar>>, SynthesisError>>()?;
710 let product = Polynomial {
711 coefficients,
712 values,
713 };
714 let one = Scalar::one();
715 let mut x = Scalar::zero();
716 for _ in 1..(n_product_coeffs + 1) {
717 x.add_assign(&one);
718 cs.enforce(
719 || format!("pointwise product @ {x:?}"),
720 |lc| {
721 let mut i = Scalar::one();
722 self.coefficients.iter().fold(lc, |lc, c| {
723 let r = lc + (i, c);
724 i.mul_assign(&x);
725 r
726 })
727 },
728 |lc| {
729 let mut i = Scalar::one();
730 other.coefficients.iter().fold(lc, |lc, c| {
731 let r = lc + (i, c);
732 i.mul_assign(&x);
733 r
734 })
735 },
736 |lc| {
737 let mut i = Scalar::one();
738 product.coefficients.iter().fold(lc, |lc, c| {
739 let r = lc + (i, c);
740 i.mul_assign(&x);
741 r
742 })
743 },
744 )
745 }
746 Ok(product)
747 }
748
749 pub fn sum(&self, other: &Self) -> Self {
750 let n_coeffs = max(self.coefficients.len(), other.coefficients.len());
751 let values = self.values.as_ref().and_then(|self_vs| {
752 other.values.as_ref().map(|other_vs| {
753 (0..n_coeffs)
754 .map(|i| {
755 let mut s = Scalar::zero();
756 if i < self_vs.len() {
757 s.add_assign(&self_vs[i]);
758 }
759 if i < other_vs.len() {
760 s.add_assign(&other_vs[i]);
761 }
762 s
763 })
764 .collect()
765 })
766 });
767 let coefficients = (0..n_coeffs)
768 .map(|i| {
769 let mut lc = LinearCombination::zero();
770 if i < self.coefficients.len() {
771 lc = lc + &self.coefficients[i];
772 }
773 if i < other.coefficients.len() {
774 lc = lc + &other.coefficients[i];
775 }
776 lc
777 })
778 .collect();
779 Polynomial {
780 coefficients,
781 values,
782 }
783 }
784}
785
786#[cfg(test)]
787mod tests {
788 use super::*;
789 use bellperson::Circuit;
790
791 pub struct PolynomialMultiplier<Scalar: PrimeField> {
792 pub a: Vec<Scalar>,
793 pub b: Vec<Scalar>,
794 }
795
796 impl<Scalar: PrimeField> Circuit<Scalar> for PolynomialMultiplier<Scalar> {
797 fn synthesize<CS: ConstraintSystem<Scalar>>(self, cs: &mut CS) -> Result<(), SynthesisError> {
798 let a = Polynomial {
799 coefficients: self
800 .a
801 .iter()
802 .enumerate()
803 .map(|(i, x)| {
804 Ok(LinearCombination::zero() + cs.alloc(|| format!("coeff_a {i}"), || Ok(*x))?)
805 })
806 .collect::<Result<Vec<LinearCombination<Scalar>>, SynthesisError>>()?,
807 values: Some(self.a),
808 };
809 let b = Polynomial {
810 coefficients: self
811 .b
812 .iter()
813 .enumerate()
814 .map(|(i, x)| {
815 Ok(LinearCombination::zero() + cs.alloc(|| format!("coeff_b {i}"), || Ok(*x))?)
816 })
817 .collect::<Result<Vec<LinearCombination<Scalar>>, SynthesisError>>()?,
818 values: Some(self.b),
819 };
820 let _prod = a.alloc_product(cs.namespace(|| "product"), &b)?;
821 Ok(())
822 }
823 }
824}