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