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