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