1#![allow(clippy::too_many_arguments)]
  2use crate::group::Fr;
  3use crate::poseidon_transcript::{AppendToPoseidon, PoseidonTranscript};
  4
  5use super::commitments::{Commitments, MultiCommitGens};
  6use super::errors::ProofVerifyError;
  7use super::group::{
  8  CompressGroupElement, CompressedGroup, DecompressGroupElement, GroupElement,
  9  VartimeMultiscalarMul,
 10};
 11use super::math::Math;
 12use super::nizk::{DotProductProofGens, DotProductProofLog};
 13use super::random::RandomTape;
 14use super::scalar::Scalar;
 15use super::transcript::{AppendToTranscript, ProofTranscript};
 16use ark_bls12_377::Bls12_377 as I;
 17use ark_ff::{One, UniformRand, Zero};
 18use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
 19use ark_poly_commit::multilinear_pc::data_structures::{
 20  CommitterKey, UniversalParams, VerifierKey,
 21};
 22use ark_poly_commit::multilinear_pc::MultilinearPC;
 23use ark_serialize::*;
 24use core::ops::Index;
 25use merlin::Transcript;
 26use std::ops::{Add, AddAssign, Neg, Sub, SubAssign};
 27use std::process::abort;
 28
 29#[cfg(feature = "multicore")]
 30use rayon::prelude::*;
 31
 32// TODO: integrate the DenseMultilinearExtension(and Sparse) https://github.com/arkworks-rs/algebra/tree/master/poly/src/evaluations/multivariate/multilinear from arkworks into Spartan. This requires moving the specific Spartan functionalities in separate traits.
 33#[derive(Debug, Clone, Eq, PartialEq, Hash, CanonicalDeserialize, CanonicalSerialize)]
 34pub struct DensePolynomial {
 35  num_vars: usize, // the number of variables in the multilinear polynomial
 36  len: usize,
 37  Z: Vec<Scalar>, // evaluations of the polynomial in all the 2^num_vars Boolean inputs
 38}
 39
 40impl MultilinearExtension<Scalar> for DensePolynomial {
 41  fn num_vars(&self) -> usize {
 42    self.get_num_vars()
 43  }
 44
 45  fn evaluate(&self, point: &[Scalar]) -> Option<Scalar> {
 46    if point.len() == self.num_vars {
 47      Some(self.evaluate(&point))
 48    } else {
 49      None
 50    }
 51  }
 52
 53  fn rand<R: rand::Rng>(num_vars: usize, rng: &mut R) -> Self {
 54    let evals = (0..(1 << num_vars)).map(|_| Scalar::rand(rng)).collect();
 55    Self {
 56      num_vars: num_vars,
 57      len: 1 << num_vars,
 58      Z: evals,
 59    }
 60  }
 61
 62  fn relabel(&self, a: usize, b: usize, k: usize) -> Self {
 63    unimplemented!()
 64  }
 65
 66  fn fix_variables(&self, partial_point: &[Scalar]) -> Self {
 67    unimplemented!()
 68  }
 69
 70  fn to_evaluations(&self) -> Vec<Scalar> {
 71    self.Z.to_vec()
 72  }
 73}
 74
 75impl Zero for DensePolynomial {
 76  fn zero() -> Self {
 77    Self {
 78      num_vars: 0,
 79      len: 1,
 80      Z: vec![Scalar::zero()],
 81    }
 82  }
 83
 84  fn is_zero(&self) -> bool {
 85    self.num_vars == 0 && self.len == 1 && self.Z[0].is_zero()
 86  }
 87}
 88
 89impl Add for DensePolynomial {
 90  type Output = DensePolynomial;
 91  fn add(self, other: Self) -> Self {
 92    &self + &other
 93  }
 94}
 95
 96// function needed because the result might have a different lifetime than the
 97// operands
 98impl<'a, 'b> Add<&'a DensePolynomial> for &'b DensePolynomial {
 99  type Output = DensePolynomial;
100
101  fn add(self, other: &'a DensePolynomial) -> Self::Output {
102    if other.is_zero() {
103      return self.clone();
104    }
105    if self.is_zero() {
106      return other.clone();
107    }
108    assert_eq!(self.num_vars, other.num_vars);
109
110    let res: Vec<Scalar> = self
111      .Z
112      .iter()
113      .zip(other.Z.iter())
114      .map(|(a, b)| *a + *b)
115      .collect();
116    Self::Output {
117      num_vars: self.num_vars,
118      len: self.len,
119      Z: res,
120    }
121  }
122}
123
124impl AddAssign for DensePolynomial {
125  fn add_assign(&mut self, other: Self) {
126    *self = &*self + &other;
127  }
128}
129
130impl<'a, 'b> AddAssign<&'a DensePolynomial> for DensePolynomial {
131  fn add_assign(&mut self, other: &'a DensePolynomial) {
132    *self = &*self + other;
133  }
134}
135
136impl<'a, 'b> AddAssign<(Scalar, &'a DensePolynomial)> for DensePolynomial {
137  fn add_assign(&mut self, (scalar, other): (Scalar, &'a DensePolynomial)) {
138    let other = Self {
139      num_vars: other.num_vars,
140      len: 1 << other.num_vars,
141      Z: other.Z.iter().map(|x| scalar * x).collect(),
142    };
143    *self = &*self + &other;
144  }
145}
146
147impl Neg for DensePolynomial {
148  type Output = DensePolynomial;
149
150  fn neg(self) -> Self::Output {
151    Self::Output {
152      num_vars: self.num_vars,
153      len: self.len,
154      Z: self.Z.iter().map(|x| -*x).collect(),
155    }
156  }
157}
158
159impl Sub for DensePolynomial {
160  type Output = DensePolynomial;
161
162  fn sub(self, other: Self) -> Self::Output {
163    &self - &other
164  }
165}
166
167impl<'a, 'b> Sub<&'a DensePolynomial> for &'b DensePolynomial {
168  type Output = DensePolynomial;
169
170  fn sub(self, other: &'a DensePolynomial) -> Self::Output {
171    self + &other.clone().neg()
172  }
173}
174
175impl SubAssign for DensePolynomial {
176  fn sub_assign(&mut self, other: Self) {
177    *self = &*self - &other;
178  }
179}
180
181impl<'a, 'b> SubAssign<&'a DensePolynomial> for DensePolynomial {
182  fn sub_assign(&mut self, other: &'a DensePolynomial) {
183    *self = &*self - other;
184  }
185}
186
187#[derive(Clone)]
188pub struct PolyCommitmentGens {
189  pub gens: DotProductProofGens,
190  pub ck: CommitterKey<I>,
191  pub vk: VerifierKey<I>,
192}
193
194impl PolyCommitmentGens {
195  // num vars is the number of variables in the multilinear polynomial
196  // this gives the maximum degree bound
197  pub fn new(num_vars: usize, label: &'static [u8]) -> PolyCommitmentGens {
198    let (_left, right) = EqPolynomial::compute_factored_lens(num_vars);
199    let gens = DotProductProofGens::new(right.pow2(), label);
200
201    // Generates the SRS and trims it based on the number of variables in the
202    // multilinear polynomial.
203    let mut rng = ark_std::test_rng();
204    let pst_gens = MultilinearPC::<I>::setup(num_vars, &mut rng);
205    let (ck, vk) = MultilinearPC::<I>::trim(&pst_gens, num_vars);
206
207    PolyCommitmentGens { gens, ck, vk }
208  }
209}
210
211pub struct PolyCommitmentBlinds {
212  blinds: Vec<Scalar>,
213}
214
215#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
216pub struct PolyCommitment {
217  C: Vec<CompressedGroup>,
218}
219
220#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
221pub struct ConstPolyCommitment {
222  C: CompressedGroup,
223}
224
225pub struct EqPolynomial {
226  r: Vec<Scalar>,
227}
228
229impl EqPolynomial {
230  pub fn new(r: Vec<Scalar>) -> Self {
231    EqPolynomial { r }
232  }
233
234  pub fn evaluate(&self, rx: &[Scalar]) -> Scalar {
235    assert_eq!(self.r.len(), rx.len());
236    (0..rx.len())
237      .map(|i| self.r[i] * rx[i] + (Scalar::one() - self.r[i]) * (Scalar::one() - rx[i]))
238      .product()
239  }
240
241  pub fn evals(&self) -> Vec<Scalar> {
242    let ell = self.r.len();
243
244    let mut evals: Vec<Scalar> = vec![Scalar::one(); ell.pow2()];
245    let mut size = 1;
246    for j in 0..ell {
247      // in each iteration, we double the size of chis
248      size *= 2;
249      // TODO: this reverse causes inconsistent evaluation in comparison to the
250      //evaluation function in ark-poly-commit, we should look into this to
251      // avoid the extra constraints in the circuit
252      for i in (0..size).rev().step_by(2) {
253        // copy each element from the prior iteration twice
254        let scalar = evals[i / 2];
255        evals[i] = scalar * self.r[j];
256        evals[i - 1] = scalar - evals[i];
257      }
258    }
259    evals
260  }
261
262  pub fn compute_factored_lens(ell: usize) -> (usize, usize) {
263    (ell / 2, ell - ell / 2)
264  }
265
266  pub fn compute_factored_evals(&self) -> (Vec<Scalar>, Vec<Scalar>) {
267    let ell = self.r.len();
268    let (left_num_vars, _right_num_vars) = EqPolynomial::compute_factored_lens(ell);
269
270    let L = EqPolynomial::new(self.r[..left_num_vars].to_vec()).evals();
271    let R = EqPolynomial::new(self.r[left_num_vars..ell].to_vec()).evals();
272
273    (L, R)
274  }
275}
276
277pub struct IdentityPolynomial {
278  size_point: usize,
279}
280
281impl IdentityPolynomial {
282  pub fn new(size_point: usize) -> Self {
283    IdentityPolynomial { size_point }
284  }
285
286  pub fn evaluate(&self, r: &[Scalar]) -> Scalar {
287    let len = r.len();
288    assert_eq!(len, self.size_point);
289    (0..len)
290      .map(|i| Scalar::from((len - i - 1).pow2() as u64) * r[i])
291      .sum()
292  }
293}
294
295impl DensePolynomial {
296  pub fn new(Z: Vec<Scalar>) -> Self {
297    DensePolynomial {
298      num_vars: Z.len().log_2(),
299      len: Z.len(),
300      Z,
301    }
302  }
303
304  pub fn get_num_vars(&self) -> usize {
305    self.num_vars
306  }
307
308  pub fn len(&self) -> usize {
309    self.len
310  }
311
312  pub fn clone(&self) -> DensePolynomial {
313    DensePolynomial::new(self.Z[0..self.len].to_vec())
314  }
315
316  pub fn split(&self, idx: usize) -> (DensePolynomial, DensePolynomial) {
317    assert!(idx < self.len());
318    (
319      DensePolynomial::new(self.Z[..idx].to_vec()),
320      DensePolynomial::new(self.Z[idx..2 * idx].to_vec()),
321    )
322  }
323
324  #[cfg(feature = "multicore")]
325  fn commit_inner(&self, blinds: &[Scalar], gens: &MultiCommitGens) -> PolyCommitment {
326    let L_size = blinds.len();
327    let R_size = self.Z.len() / L_size;
328    assert_eq!(L_size * R_size, self.Z.len());
329    let C = (0..L_size)
330      .into_par_iter()
331      .map(|i| {
332        self.Z[R_size * i..R_size * (i + 1)]
333          .commit(&blinds[i], gens)
334          .compress()
335      })
336      .collect();
337    PolyCommitment { C }
338  }
339
340  #[cfg(not(feature = "multicore"))]
341  fn commit_inner(&self, blinds: &[Scalar], gens: &MultiCommitGens) -> PolyCommitment {
342    let L_size = blinds.len();
343    let R_size = self.Z.len() / L_size;
344    assert_eq!(L_size * R_size, self.Z.len());
345    let C = (0..L_size)
346      .map(|i| {
347        self.Z[R_size * i..R_size * (i + 1)]
348          .commit(&blinds[i], gens)
349          .compress()
350      })
351      .collect();
352    PolyCommitment { C }
353  }
354
355  pub fn commit(
356    &self,
357    gens: &PolyCommitmentGens,
358    random_tape: Option<&mut RandomTape>,
359  ) -> (PolyCommitment, PolyCommitmentBlinds) {
360    let n = self.Z.len();
361    let ell = self.get_num_vars();
362    assert_eq!(n, ell.pow2());
363
364    let (left_num_vars, right_num_vars) = EqPolynomial::compute_factored_lens(ell);
365    let L_size = left_num_vars.pow2();
366    let R_size = right_num_vars.pow2();
367    assert_eq!(L_size * R_size, n);
368
369    let blinds = if let Some(t) = random_tape {
370      PolyCommitmentBlinds {
371        blinds: t.random_vector(b"poly_blinds", L_size),
372      }
373    } else {
374      PolyCommitmentBlinds {
375        blinds: vec![Scalar::zero(); L_size],
376      }
377    };
378
379    (self.commit_inner(&blinds.blinds, &gens.gens.gens_n), blinds)
380  }
381
382  pub fn bound(&self, L: &[Scalar]) -> Vec<Scalar> {
383    let (left_num_vars, right_num_vars) = EqPolynomial::compute_factored_lens(self.get_num_vars());
384    let L_size = left_num_vars.pow2();
385    let R_size = right_num_vars.pow2();
386    (0..R_size)
387      .map(|i| (0..L_size).map(|j| L[j] * self.Z[j * R_size + i]).sum())
388      .collect()
389  }
390
391  pub fn bound_poly_var_top(&mut self, r: &Scalar) {
392    let n = self.len() / 2;
393    for i in 0..n {
394      self.Z[i] = self.Z[i] + (self.Z[i + n] - self.Z[i]) * r;
395    }
396    self.num_vars -= 1;
397    self.len = n;
398  }
399
400  pub fn bound_poly_var_bot(&mut self, r: &Scalar) {
401    let n = self.len() / 2;
402    for i in 0..n {
403      self.Z[i] = self.Z[2 * i] + (self.Z[2 * i + 1] - self.Z[2 * i]) * r;
404    }
405    self.num_vars -= 1;
406    self.len = n;
407  }
408
409  // returns Z(r) in O(n) time
410  pub fn evaluate(&self, r: &[Scalar]) -> Scalar {
411    // r must have a value for each variable
412    assert_eq!(r.len(), self.get_num_vars());
413    let chis = EqPolynomial::new(r.to_vec()).evals();
414    assert_eq!(chis.len(), self.Z.len());
415    DotProductProofLog::compute_dotproduct(&self.Z, &chis)
416  }
417
418  fn vec(&self) -> &Vec<Scalar> {
419    &self.Z
420  }
421
422  pub fn extend(&mut self, other: &DensePolynomial) {
423    // TODO: allow extension even when some vars are bound
424    assert_eq!(self.Z.len(), self.len);
425    let other_vec = other.vec();
426    assert_eq!(other_vec.len(), self.len);
427    self.Z.extend(other_vec);
428    self.num_vars += 1;
429    self.len *= 2;
430    assert_eq!(self.Z.len(), self.len);
431  }
432
433  pub fn merge<'a, I>(polys: I) -> DensePolynomial
434  where
435    I: IntoIterator<Item = &'a DensePolynomial>,
436  {
437    let mut Z: Vec<Scalar> = Vec::new();
438    for poly in polys.into_iter() {
439      Z.extend(poly.vec());
440    }
441
442    // pad the polynomial with zero polynomial at the end
443    Z.resize(Z.len().next_power_of_two(), Scalar::zero());
444
445    DensePolynomial::new(Z)
446  }
447
448  pub fn from_usize(Z: &[usize]) -> Self {
449    DensePolynomial::new(
450      (0..Z.len())
451        .map(|i| Scalar::from(Z[i] as u64))
452        .collect::<Vec<Scalar>>(),
453    )
454  }
455}
456
457impl Index<usize> for DensePolynomial {
458  type Output = Scalar;
459
460  #[inline(always)]
461  fn index(&self, _index: usize) -> &Scalar {
462    &(self.Z[_index])
463  }
464}
465
466impl AppendToTranscript for PolyCommitment {
467  fn append_to_transcript(&self, label: &'static [u8], transcript: &mut Transcript) {
468    transcript.append_message(label, b"poly_commitment_begin");
469    for i in 0..self.C.len() {
470      transcript.append_point(b"poly_commitment_share", &self.C[i]);
471    }
472    transcript.append_message(label, b"poly_commitment_end");
473  }
474}
475
476impl AppendToPoseidon for PolyCommitment {
477  fn append_to_poseidon(&self, transcript: &mut PoseidonTranscript) {
478    for i in 0..self.C.len() {
479      transcript.append_point(&self.C[i]);
480    }
481  }
482}
483
484#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
485pub struct PolyEvalProof {
486  proof: DotProductProofLog,
487}
488
489impl PolyEvalProof {
490  fn protocol_name() -> &'static [u8] {
491    b"polynomial evaluation proof"
492  }
493
494  pub fn prove(
495    poly: &DensePolynomial,
496    blinds_opt: Option<&PolyCommitmentBlinds>,
497    r: &[Scalar],                  // point at which the polynomial is evaluated
498    Zr: &Scalar,                   // evaluation of \widetilde{Z}(r)
499    blind_Zr_opt: Option<&Scalar>, // specifies a blind for Zr
500    gens: &PolyCommitmentGens,
501    transcript: &mut PoseidonTranscript,
502    random_tape: &mut RandomTape,
503  ) -> (PolyEvalProof, CompressedGroup) {
504    // transcript.append_protocol_name(PolyEvalProof::protocol_name());
505
506    // assert vectors are of the right size
507    assert_eq!(poly.get_num_vars(), r.len());
508
509    let (left_num_vars, right_num_vars) = EqPolynomial::compute_factored_lens(r.len());
510    let L_size = left_num_vars.pow2();
511    let R_size = right_num_vars.pow2();
512
513    let default_blinds = PolyCommitmentBlinds {
514      blinds: vec![Scalar::zero(); L_size],
515    };
516    let blinds = blinds_opt.map_or(&default_blinds, |p| p);
517
518    assert_eq!(blinds.blinds.len(), L_size);
519
520    let zero = Scalar::zero();
521    let blind_Zr = blind_Zr_opt.map_or(&zero, |p| p);
522
523    // compute the L and R vectors
524    let eq = EqPolynomial::new(r.to_vec());
525    let (L, R) = eq.compute_factored_evals();
526    assert_eq!(L.len(), L_size);
527    assert_eq!(R.len(), R_size);
528
529    // compute the vector underneath L*Z and the L*blinds
530    // compute vector-matrix product between L and Z viewed as a matrix
531    let LZ = poly.bound(&L);
532    let LZ_blind: Scalar = (0..L.len()).map(|i| blinds.blinds[i] * L[i]).sum();
533
534    // a dot product proof of size R_size
535    let (proof, _C_LR, C_Zr_prime) = DotProductProofLog::prove(
536      &gens.gens,
537      transcript,
538      random_tape,
539      &LZ,
540      &LZ_blind,
541      &R,
542      Zr,
543      blind_Zr,
544    );
545
546    (PolyEvalProof { proof }, C_Zr_prime)
547  }
548
549  pub fn verify(
550    &self,
551    gens: &PolyCommitmentGens,
552    transcript: &mut PoseidonTranscript,
553    r: &[Scalar],           // point at which the polynomial is evaluated
554    C_Zr: &CompressedGroup, // commitment to \widetilde{Z}(r)
555    comm: &PolyCommitment,
556  ) -> Result<(), ProofVerifyError> {
557    // transcript.append_protocol_name(PolyEvalProof::protocol_name());
558
559    // compute L and R
560    let eq = EqPolynomial::new(r.to_vec());
561    let (L, R) = eq.compute_factored_evals();
562
563    // compute a weighted sum of commitments and L
564    let C_decompressed = comm
565      .C
566      .iter()
567      .map(|pt| GroupElement::decompress(pt).unwrap())
568      .collect::<Vec<GroupElement>>();
569
570    let C_LZ = GroupElement::vartime_multiscalar_mul(&L, C_decompressed.as_slice()).compress();
571
572    self
573      .proof
574      .verify(R.len(), &gens.gens, transcript, &R, &C_LZ, C_Zr)
575  }
576
577  pub fn verify_plain(
578    &self,
579    gens: &PolyCommitmentGens,
580    transcript: &mut PoseidonTranscript,
581    r: &[Scalar], // point at which the polynomial is evaluated
582    Zr: &Scalar,  // evaluation \widetilde{Z}(r)
583    comm: &PolyCommitment,
584  ) -> Result<(), ProofVerifyError> {
585    // compute a commitment to Zr with a blind of zero
586    let C_Zr = Zr.commit(&Scalar::zero(), &gens.gens.gens_1).compress();
587
588    self.verify(gens, transcript, r, &C_Zr, comm)
589  }
590}
591
592#[cfg(test)]
593mod tests {
594  use crate::parameters::poseidon_params;
595
596  use super::*;
597  use ark_std::UniformRand;
598
599  fn evaluate_with_LR(Z: &[Scalar], r: &[Scalar]) -> Scalar {
600    let eq = EqPolynomial::new(r.to_vec());
601    let (L, R) = eq.compute_factored_evals();
602
603    let ell = r.len();
604    // ensure ell is even
605    assert!(ell % 2 == 0);
606    // compute n = 2^\ell
607    let n = ell.pow2();
608    // compute m = sqrt(n) = 2^{\ell/2}
609    let m = n.square_root();
610
611    // compute vector-matrix product between L and Z viewed as a matrix
612    let LZ = (0..m)
613      .map(|i| (0..m).map(|j| L[j] * Z[j * m + i]).sum())
614      .collect::<Vec<Scalar>>();
615
616    // compute dot product between LZ and R
617    DotProductProofLog::compute_dotproduct(&LZ, &R)
618  }
619
620  #[test]
621  fn check_polynomial_evaluation() {
622    // Z = [1, 2, 1, 4]
623    let Z = vec![
624      Scalar::one(),
625      Scalar::from(2),
626      Scalar::from(1),
627      Scalar::from(4),
628    ];
629
630    // r = [4,3]
631    let r = vec![Scalar::from(4), Scalar::from(3)];
632
633    let eval_with_LR = evaluate_with_LR(&Z, &r);
634    let poly = DensePolynomial::new(Z);
635
636    let eval = poly.evaluate(&r);
637    assert_eq!(eval, Scalar::from(28));
638    assert_eq!(eval_with_LR, eval);
639  }
640
641  pub fn compute_factored_chis_at_r(r: &[Scalar]) -> (Vec<Scalar>, Vec<Scalar>) {
642    let mut L: Vec<Scalar> = Vec::new();
643    let mut R: Vec<Scalar> = Vec::new();
644
645    let ell = r.len();
646    assert!(ell % 2 == 0); // ensure ell is even
647    let n = ell.pow2();
648    let m = n.square_root();
649
650    // compute row vector L
651    for i in 0..m {
652      let mut chi_i = Scalar::one();
653      for j in 0..ell / 2 {
654        let bit_j = ((m * i) & (1 << (r.len() - j - 1))) > 0;
655        if bit_j {
656          chi_i *= r[j];
657        } else {
658          chi_i *= Scalar::one() - r[j];
659        }
660      }
661      L.push(chi_i);
662    }
663
664    // compute column vector R
665    for i in 0..m {
666      let mut chi_i = Scalar::one();
667      for j in ell / 2..ell {
668        let bit_j = (i & (1 << (r.len() - j - 1))) > 0;
669        if bit_j {
670          chi_i *= r[j];
671        } else {
672          chi_i *= Scalar::one() - r[j];
673        }
674      }
675      R.push(chi_i);
676    }
677    (L, R)
678  }
679
680  pub fn compute_chis_at_r(r: &[Scalar]) -> Vec<Scalar> {
681    let ell = r.len();
682    let n = ell.pow2();
683    let mut chis: Vec<Scalar> = Vec::new();
684    for i in 0..n {
685      let mut chi_i = Scalar::one();
686      for j in 0..r.len() {
687        let bit_j = (i & (1 << (r.len() - j - 1))) > 0;
688        if bit_j {
689          chi_i *= r[j];
690        } else {
691          chi_i *= Scalar::one() - r[j];
692        }
693      }
694      chis.push(chi_i);
695    }
696    chis
697  }
698
699  pub fn compute_outerproduct(L: Vec<Scalar>, R: Vec<Scalar>) -> Vec<Scalar> {
700    assert_eq!(L.len(), R.len());
701    (0..L.len())
702      .map(|i| (0..R.len()).map(|j| L[i] * R[j]).collect::<Vec<Scalar>>())
703      .collect::<Vec<Vec<Scalar>>>()
704      .into_iter()
705      .flatten()
706      .collect::<Vec<Scalar>>()
707  }
708
709  #[test]
710  fn check_memoized_chis() {
711    let mut rng = ark_std::rand::thread_rng();
712
713    let s = 10;
714    let mut r: Vec<Scalar> = Vec::new();
715    for _i in 0..s {
716      r.push(Scalar::rand(&mut rng));
717    }
718    let chis = tests::compute_chis_at_r(&r);
719    let chis_m = EqPolynomial::new(r).evals();
720    assert_eq!(chis, chis_m);
721  }
722
723  #[test]
724  fn check_factored_chis() {
725    let mut rng = ark_std::rand::thread_rng();
726
727    let s = 10;
728    let mut r: Vec<Scalar> = Vec::new();
729    for _i in 0..s {
730      r.push(Scalar::rand(&mut rng));
731    }
732    let chis = EqPolynomial::new(r.clone()).evals();
733    let (L, R) = EqPolynomial::new(r).compute_factored_evals();
734    let O = compute_outerproduct(L, R);
735    assert_eq!(chis, O);
736  }
737
738  #[test]
739  fn check_memoized_factored_chis() {
740    let mut rng = ark_std::rand::thread_rng();
741
742    let s = 10;
743    let mut r: Vec<Scalar> = Vec::new();
744    for _i in 0..s {
745      r.push(Scalar::rand(&mut rng));
746    }
747    let (L, R) = tests::compute_factored_chis_at_r(&r);
748    let eq = EqPolynomial::new(r);
749    let (L2, R2) = eq.compute_factored_evals();
750    assert_eq!(L, L2);
751    assert_eq!(R, R2);
752  }
753
754  #[test]
755  fn check_polynomial_commit() {
756    let Z = vec![
757      Scalar::from(1),
758      Scalar::from(2),
759      Scalar::from(1),
760      Scalar::from(4),
761    ];
762    let poly = DensePolynomial::new(Z);
763
764    // r = [4,3]
765    let r = vec![Scalar::from(4), Scalar::from(3)];
766    let eval = poly.evaluate(&r);
767    assert_eq!(eval, Scalar::from(28));
768
769    let gens = PolyCommitmentGens::new(poly.get_num_vars(), b"test-two");
770    let (poly_commitment, blinds) = poly.commit(&gens, None);
771
772    let mut random_tape = RandomTape::new(b"proof");
773    let params = poseidon_params();
774    let mut prover_transcript = PoseidonTranscript::new(&params);
775    let (proof, C_Zr) = PolyEvalProof::prove(
776      &poly,
777      Some(&blinds),
778      &r,
779      &eval,
780      None,
781      &gens,
782      &mut prover_transcript,
783      &mut random_tape,
784    );
785
786    let mut verifier_transcript = PoseidonTranscript::new(&params);
787    assert!(proof
788      .verify(&gens, &mut verifier_transcript, &r, &C_Zr, &poly_commitment)
789      .is_ok());
790  }
791}