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