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