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 IdentityPolynomial {
119 size_point: usize,
120}
121
122impl IdentityPolynomial {
123 pub fn new(size_point: usize) -> Self {
124 IdentityPolynomial { size_point }
125 }
126
127 pub fn evaluate(&self, r: &Vec<Scalar>) -> Scalar {
128 let len = r.len();
129 assert_eq!(len, self.size_point);
130 (0..len)
131 .map(|i| Scalar::from((len - i - 1).pow2() as u64) * r[i])
132 .sum()
133 }
134}
135
136impl DensePolynomial {
137 pub fn new(Z: Vec<Scalar>) -> Self {
138 let len = Z.len();
139 let num_vars = len.log2();
140 DensePolynomial { num_vars, Z, len }
141 }
142
143 pub fn get_num_vars(&self) -> usize {
144 self.num_vars
145 }
146
147 pub fn len(&self) -> usize {
148 self.len
149 }
150
151 pub fn clone(&self) -> DensePolynomial {
152 DensePolynomial::new(self.Z[0..self.len].to_vec())
153 }
154
155 pub fn split(&self, idx: usize) -> (DensePolynomial, DensePolynomial) {
156 assert!(idx < self.len());
157 (
158 DensePolynomial::new(self.Z[0..idx].to_vec()),
159 DensePolynomial::new(self.Z[idx..2 * idx].to_vec()),
160 )
161 }
162
163 #[cfg(feature = "rayon_par")]
164 fn commit_inner(&self, blinds: &Vec<Scalar>, gens: &MultiCommitGens) -> PolyCommitment {
165 let L_size = blinds.len();
166 let R_size = self.Z.len() / L_size;
167 assert_eq!(L_size * R_size, self.Z.len());
168 let C = (0..L_size)
169 .collect::<Vec<usize>>()
170 .par_iter()
171 .map(|&i| {
172 self.Z[R_size * i..R_size * (i + 1)]
173 .commit(&blinds[i], gens)
174 .compress()
175 })
176 .collect();
177 PolyCommitment { C }
178 }
179
180 #[cfg(not(feature = "rayon_par"))]
181 fn commit_inner(&self, blinds: &Vec<Scalar>, gens: &MultiCommitGens) -> PolyCommitment {
182 let L_size = blinds.len();
183 let R_size = self.Z.len() / L_size;
184 assert_eq!(L_size * R_size, self.Z.len());
185 let C = (0..L_size)
186 .map(|i| {
187 self.Z[R_size * i..R_size * (i + 1)]
188 .commit(&blinds[i], gens)
189 .compress()
190 })
191 .collect();
192 PolyCommitment { C }
193 }
194
195 pub fn commit(
196 &self,
197 hiding: bool,
198 gens: &PolyCommitmentGens,
199 random_tape: Option<&mut RandomTape>,
200 ) -> (PolyCommitment, PolyCommitmentBlinds) {
201 let n = self.Z.len();
202 let ell = self.get_num_vars();
203 assert_eq!(n, ell.pow2());
204
205 let (left_num_vars, right_num_vars) = EqPolynomial::compute_factored_lens(ell);
206 let L_size = left_num_vars.pow2();
207 let R_size = right_num_vars.pow2();
208 assert_eq!(L_size * R_size, n);
209
210 let blinds = match hiding {
211 true => PolyCommitmentBlinds {
212 blinds: random_tape.unwrap().random_vector(b"poly_blinds", L_size),
213 },
214 false => PolyCommitmentBlinds {
215 blinds: vec![Scalar::zero(); L_size],
216 },
217 };
218
219 (self.commit_inner(&blinds.blinds, &gens.gens.gens_n), blinds)
220 }
221
222 pub fn bound(&self, L: &Vec<Scalar>) -> Vec<Scalar> {
223 let (left_num_vars, right_num_vars) = EqPolynomial::compute_factored_lens(self.get_num_vars());
224 let L_size = left_num_vars.pow2();
225 let R_size = right_num_vars.pow2();
226 (0..R_size)
227 .map(|i| (0..L_size).map(|j| &L[j] * &self.Z[j * R_size + i]).sum())
228 .collect::<Vec<Scalar>>()
229 }
230
231 pub fn bound_poly_var_top(&mut self, r: &Scalar) {
232 let n = self.len() / 2;
233 for i in 0..n {
234 self.Z[i] = &self.Z[i] + r * (&self.Z[i + n] - &self.Z[i]);
235 }
236 self.num_vars = self.num_vars - 1;
237 self.len = n;
238 }
239
240 pub fn bound_poly_var_bot(&mut self, r: &Scalar) {
241 let n = self.len() / 2;
242 for i in 0..n {
243 self.Z[i] = &self.Z[2 * i] + r * (&self.Z[2 * i + 1] - &self.Z[2 * i]);
244 }
245 self.num_vars = self.num_vars - 1;
246 self.len = n;
247 }
248
249 pub fn dotproduct(&self, other: &DensePolynomial) -> Scalar {
250 assert_eq!(self.len(), other.len());
251 let mut res = Scalar::zero();
252 for i in 0..self.len() {
253 res = &res + &self.Z[i] * &other[i];
254 }
255 res
256 }
257
258 // returns Z(r) in O(n) time
259 pub fn evaluate(&self, r: &Vec<Scalar>) -> Scalar {
260 // r must have a value for each variable
261 assert_eq!(r.len(), self.get_num_vars());
262 let chis = EqPolynomial::new(r.to_vec()).evals();
263 assert_eq!(chis.len(), self.Z.len());
264 DotProductProofLog::compute_dotproduct(&self.Z, &chis)
265 }
266
267 fn vec(&self) -> &Vec<Scalar> {
268 &self.Z
269 }
270
271 pub fn extend(&mut self, other: &DensePolynomial) {
272 // TODO: allow extension even when some vars are bound
273 assert_eq!(self.Z.len(), self.len);
274 let other_vec = other.vec();
275 assert_eq!(other_vec.len(), self.len);
276 self.Z.extend(other_vec);
277 self.num_vars = self.num_vars + 1;
278 self.len = 2 * self.len;
279 assert_eq!(self.Z.len(), self.len);
280 }
281
282 pub fn merge<'a, I>(polys: I) -> DensePolynomial
283 where
284 I: IntoIterator<Item = &'a DensePolynomial>,
285 {
286 //assert!(polys.len() > 0);
287 //let num_vars = polys[0].num_vars();
288 let mut Z: Vec<Scalar> = Vec::new();
289 for poly in polys.into_iter() {
290 //assert_eq!(poly.get_num_vars(), num_vars); // ensure each polynomial has the same number of variables
291 //assert_eq!(poly.len, poly.vec().len()); // ensure no variable is already bound
292 Z.extend(poly.vec());
293 }
294
295 // pad the polynomial with zero polynomial at the end
296 Z.resize(Z.len().next_power_of_two(), Scalar::zero());
297
298 DensePolynomial::new(Z)
299 }
300
301 pub fn from_usize(Z: &Vec<usize>) -> Self {
302 DensePolynomial::new(
303 (0..Z.len())
304 .map(|i| Scalar::from(Z[i] as u64))
305 .collect::<Vec<Scalar>>(),
306 )
307 }
308}
309
310impl Index<usize> for DensePolynomial {
311 type Output = Scalar;
312
313 #[inline(always)]
314 fn index(&self, _index: usize) -> &Scalar {
315 &(self.Z[_index])
316 }
317}
318
319impl AppendToTranscript for PolyCommitment {
320 fn append_to_transcript(&self, label: &'static [u8], transcript: &mut Transcript) {
321 transcript.append_message(label, b"poly_commitment_begin");
322 for i in 0..self.C.len() {
323 transcript.append_point(b"poly_commitment_share", &self.C[i]);
324 }
325 transcript.append_message(label, b"poly_commitment_end");
326 }
327}
328
329#[derive(Debug, Serialize, Deserialize)]
330pub struct PolyEvalProof {
331 proof: DotProductProofLog,
332}
333
334impl PolyEvalProof {
335 fn protocol_name() -> &'static [u8] {
336 b"polynomial evaluation proof"
337 }
338
339 pub fn prove(
340 poly: &DensePolynomial,
341 blinds_opt: Option<&PolyCommitmentBlinds>,
342 r: &Vec<Scalar>, // point at which the polynomial is evaluated
343 Zr: &Scalar, // evaluation of \widetilde{Z}(r)
344 blind_Zr_opt: Option<&Scalar>, // specifies a blind for Zr
345 gens: &PolyCommitmentGens,
346 transcript: &mut Transcript,
347 random_tape: &mut RandomTape,
348 ) -> (PolyEvalProof, CompressedGroup) {
349 transcript.append_protocol_name(PolyEvalProof::protocol_name());
350
351 // assert vectors are of the right size
352 assert_eq!(poly.get_num_vars(), r.len());
353
354 let (left_num_vars, right_num_vars) = EqPolynomial::compute_factored_lens(r.len());
355 let L_size = left_num_vars.pow2();
356 let R_size = right_num_vars.pow2();
357
358 let default_blinds = PolyCommitmentBlinds {
359 blinds: vec![Scalar::zero(); L_size],
360 };
361 let blinds = match blinds_opt {
362 Some(p) => p,
363 None => &default_blinds,
364 };
365
366 assert_eq!(blinds.blinds.len(), L_size);
367
368 let zero = Scalar::zero();
369 let blind_Zr = match blind_Zr_opt {
370 Some(p) => p,
371 None => &zero,
372 };
373
374 // compute the L and R vectors
375 let eq = EqPolynomial::new(r.to_vec());
376 let (L, R) = eq.compute_factored_evals();
377 assert_eq!(L.len(), L_size);
378 assert_eq!(R.len(), R_size);
379
380 // compute the vector underneath L*Z and the L*blinds
381 // compute vector-matrix product between L and Z viewed as a matrix
382 let LZ = poly.bound(&L);
383 let LZ_blind: Scalar = (0..L.len()).map(|i| blinds.blinds[i] * L[i]).sum();
384
385 // a dot product proof of size R_size
386 let (proof, _C_LR, C_Zr_prime) = DotProductProofLog::prove(
387 &gens.gens,
388 transcript,
389 random_tape,
390 &LZ,
391 &LZ_blind,
392 &R,
393 &Zr,
394 blind_Zr,
395 );
396
397 (PolyEvalProof { proof }, C_Zr_prime)
398 }
399
400 pub fn verify(
401 &self,
402 gens: &PolyCommitmentGens,
403 transcript: &mut Transcript,
404 r: &Vec<Scalar>, // point at which the polynomial is evaluated
405 C_Zr: &CompressedGroup, // commitment to \widetilde{Z}(r)
406 comm: &PolyCommitment,
407 ) -> Result<(), ProofVerifyError> {
408 transcript.append_protocol_name(PolyEvalProof::protocol_name());
409
410 // compute L and R
411 let eq = EqPolynomial::new(r.to_vec());
412 let (L, R) = eq.compute_factored_evals();
413
414 // compute a weighted sum of commitments and L
415 let C_decompressed = comm.C.iter().map(|pt| pt.decompress().unwrap());
416
417 let C_LZ = GroupElement::vartime_multiscalar_mul(&L, C_decompressed).compress();
418
419 self
420 .proof
421 .verify(R.len(), &gens.gens, transcript, &R, &C_LZ, C_Zr)
422 }
423
424 pub fn verify_plain(
425 &self,
426 gens: &PolyCommitmentGens,
427 transcript: &mut Transcript,
428 r: &Vec<Scalar>, // point at which the polynomial is evaluated
429 Zr: &Scalar, // evaluation \widetilde{Z}(r)
430 comm: &PolyCommitment,
431 ) -> Result<(), ProofVerifyError> {
432 // compute a commitment to Zr with a blind of zero
433 let C_Zr = Zr.commit(&Scalar::zero(), &gens.gens.gens_1).compress();
434
435 self.verify(gens, transcript, r, &C_Zr, comm)
436 }
437}
438
439#[cfg(test)]
440mod tests {
441 use super::super::scalar::ScalarFromPrimitives;
442 use super::*;
443 use rand::rngs::OsRng;
444
445 fn evaluate_with_LR(Z: &Vec<Scalar>, r: &Vec<Scalar>) -> Scalar {
446 let eq = EqPolynomial::new(r.to_vec());
447 let (L, R) = eq.compute_factored_evals();
448
449 let ell = r.len();
450 // ensure ell is even
451 assert!(ell % 2 == 0);
452 // compute n = 2^\ell
453 let n = ell.pow2();
454 // compute m = sqrt(n) = 2^{\ell/2}
455 let m = n.square_root();
456
457 // compute vector-matrix product between L and Z viewed as a matrix
458 let LZ = (0..m)
459 .map(|i| (0..m).map(|j| L[j] * Z[j * m + i]).sum())
460 .collect::<Vec<Scalar>>();
461
462 // compute dot product between LZ and R
463 DotProductProofLog::compute_dotproduct(&LZ, &R)
464 }
465
466 #[test]
467 fn check_polynomial_evaluation() {
468 let mut Z: Vec<Scalar> = Vec::new(); // Z = [1, 2, 1, 4]
469 Z.push(Scalar::one());
470 Z.push((2 as usize).to_scalar());
471 Z.push((1 as usize).to_scalar());
472 Z.push((4 as usize).to_scalar());
473 // r = [4,3]
474 let mut r: Vec<Scalar> = Vec::new();
475 r.push((4 as usize).to_scalar());
476 r.push((3 as usize).to_scalar());
477
478 let eval_with_LR = evaluate_with_LR(&Z, &r);
479 let poly = DensePolynomial::new(Z);
480
481 let eval = poly.evaluate(&r);
482 assert_eq!(eval, (28 as usize).to_scalar());
483 assert_eq!(eval_with_LR, eval);
484 }
485
486 pub fn compute_factored_chis_at_r(r: &Vec<Scalar>) -> (Vec<Scalar>, Vec<Scalar>) {
487 let mut L: Vec<Scalar> = Vec::new();
488 let mut R: Vec<Scalar> = Vec::new();
489
490 let ell = r.len();
491 assert!(ell % 2 == 0); // ensure ell is even
492 let n = ell.pow2();
493 let m = n.square_root();
494
495 // compute row vector L
496 for i in 0..m {
497 let mut chi_i = Scalar::one();
498 for j in 0..ell / 2 {
499 let bit_j = ((m * i) & (1 << (r.len() - j - 1))) > 0;
500 if bit_j {
501 chi_i *= r[j];
502 } else {
503 chi_i *= Scalar::one() - r[j];
504 }
505 }
506 L.push(chi_i);
507 }
508
509 // compute column vector R
510 for i in 0..m {
511 let mut chi_i = Scalar::one();
512 for j in ell / 2..ell {
513 let bit_j = (i & (1 << (r.len() - j - 1))) > 0;
514 if bit_j {
515 chi_i *= r[j];
516 } else {
517 chi_i *= Scalar::one() - r[j];
518 }
519 }
520 R.push(chi_i);
521 }
522 (L, R)
523 }
524
525 pub fn compute_chis_at_r(r: &Vec<Scalar>) -> Vec<Scalar> {
526 let ell = r.len();
527 let n = ell.pow2();
528 let mut chis: Vec<Scalar> = Vec::new();
529 for i in 0..n {
530 let mut chi_i = Scalar::one();
531 for j in 0..r.len() {
532 let bit_j = (i & (1 << (r.len() - j - 1))) > 0;
533 if bit_j {
534 chi_i *= r[j];
535 } else {
536 chi_i *= Scalar::one() - r[j];
537 }
538 }
539 chis.push(chi_i);
540 }
541 chis
542 }
543
544 pub fn compute_outerproduct(L: Vec<Scalar>, R: Vec<Scalar>) -> Vec<Scalar> {
545 assert_eq!(L.len(), R.len());
546
547 let mut O: Vec<Scalar> = Vec::new();
548 let m = L.len();
549 for i in 0..m {
550 for j in 0..m {
551 O.push(L[i] * R[j]);
552 }
553 }
554 O
555 }
556
557 #[test]
558 fn check_memoized_chis() {
559 let mut csprng: OsRng = OsRng;
560
561 let s = 10;
562 let mut r: Vec<Scalar> = Vec::new();
563 for _i in 0..s {
564 r.push(Scalar::random(&mut csprng));
565 }
566 let chis = tests::compute_chis_at_r(&r);
567 let chis_m = EqPolynomial::new(r).evals();
568 assert_eq!(chis, chis_m);
569 }
570
571 #[test]
572 fn check_factored_chis() {
573 let mut csprng: OsRng = OsRng;
574
575 let s = 10;
576 let mut r: Vec<Scalar> = Vec::new();
577 for _i in 0..s {
578 r.push(Scalar::random(&mut csprng));
579 }
580 let chis = EqPolynomial::new(r.clone()).evals();
581 let (L, R) = EqPolynomial::new(r).compute_factored_evals();
582 let O = compute_outerproduct(L, R);
583 assert_eq!(chis, O);
584 }
585
586 #[test]
587 fn check_memoized_factored_chis() {
588 let mut csprng: OsRng = OsRng;
589
590 let s = 10;
591 let mut r: Vec<Scalar> = Vec::new();
592 for _i in 0..s {
593 r.push(Scalar::random(&mut csprng));
594 }
595 let (L, R) = tests::compute_factored_chis_at_r(&r);
596 let eq = EqPolynomial::new(r);
597 let (L2, R2) = eq.compute_factored_evals();
598 assert_eq!(L, L2);
599 assert_eq!(R, R2);
600 }
601
602 #[test]
603 fn check_polynomial_commit() {
604 let mut Z: Vec<Scalar> = Vec::new(); // Z = [1, 2, 1, 4]
605 Z.push((1 as usize).to_scalar());
606 Z.push((2 as usize).to_scalar());
607 Z.push((1 as usize).to_scalar());
608 Z.push((4 as usize).to_scalar());
609
610 let poly = DensePolynomial::new(Z);
611
612 // r = [4,3]
613 let mut r: Vec<Scalar> = Vec::new();
614 r.push((4 as usize).to_scalar());
615 r.push((3 as usize).to_scalar());
616 let eval = poly.evaluate(&r);
617 assert_eq!(eval, (28 as usize).to_scalar());
618
619 let gens = PolyCommitmentGens::new(poly.get_num_vars(), b"test-two");
620 let (poly_commitment, blinds) = poly.commit(false, &gens, None);
621
622 let mut random_tape = RandomTape::new(b"proof");
623 let mut prover_transcript = Transcript::new(b"example");
624 let (proof, C_Zr) = PolyEvalProof::prove(
625 &poly,
626 Some(&blinds),
627 &r,
628 &eval,
629 None,
630 &gens,
631 &mut prover_transcript,
632 &mut random_tape,
633 );
634
635 let mut verifier_transcript = Transcript::new(b"example");
636 assert!(proof
637 .verify(&gens, &mut verifier_transcript, &r, &C_Zr, &poly_commitment)
638 .is_ok());
639 }
640}