testudo/src/dense_mlpoly.rs
src/dense_mlpoly.rsRaw
1#![allow(clippy::too_many_arguments)]
2use super::commitments::{Commitments, MultiCommitGens};
3use super::errors::ProofVerifyError;
4use super::group::{CompressedGroup, GroupElement, VartimeMultiscalarMul};
5use super::math::Math;
6use super::nizk::{DotProductProofGens, DotProductProofLog};
7use super::random::RandomTape;
8use super::scalar::Scalar;
9use super::transcript::{AppendToTranscript, ProofTranscript};
10use core::ops::Index;
11use merlin::Transcript;
12use serde::{Deserialize, Serialize};
13
14#[cfg(feature = "rayon_par")]
15use rayon::prelude::*;
16
17#[derive(Debug)]
18pub struct DensePolynomial {
19 num_vars: usize, //the number of variables in the multilinear polynomial
20 len: usize,
21 Z: Vec<Scalar>, // evaluations of the polynomial in all the 2^num_vars Boolean inputs
22}
23
24pub struct PolyCommitmentGens {
25 pub gens: DotProductProofGens,
26}
27
28impl PolyCommitmentGens {
29 // the number of variables in the multilinear polynomial
30 pub fn new(num_vars: usize, label: &'static [u8]) -> PolyCommitmentGens {
31 let (_left, right) = EqPolynomial::compute_factored_lens(num_vars);
32 let gens = DotProductProofGens::new(right.pow2(), label);
33 PolyCommitmentGens { gens }
34 }
35}
36
37pub struct PolyCommitmentBlinds {
38 blinds: Vec<Scalar>,
39}
40
41#[derive(Debug, Serialize, Deserialize)]
42pub struct PolyCommitment {
43 C: Vec<CompressedGroup>,
44}
45
46#[derive(Debug, Serialize, Deserialize)]
47pub struct ConstPolyCommitment {
48 C: CompressedGroup,
49}
50
51impl PolyCommitment {
52 pub fn combine(&self, comm: &PolyCommitment, s: &Scalar) -> PolyCommitment {
53 assert_eq!(comm.C.len(), self.C.len());
54 let C = (0..self.C.len())
55 .map(|i| (self.C[i].decompress().unwrap() + s * comm.C[i].decompress().unwrap()).compress())
56 .collect::<Vec<CompressedGroup>>();
57 PolyCommitment { C }
58 }
59
60 pub fn combine_const(&self, comm: &ConstPolyCommitment) -> PolyCommitment {
61 let C = (0..self.C.len())
62 .map(|i| (self.C[i].decompress().unwrap() + comm.C.decompress().unwrap()).compress())
63 .collect::<Vec<CompressedGroup>>();
64 PolyCommitment { C }
65 }
66}
67
68pub struct EqPolynomial {
69 r: Vec<Scalar>,
70}
71
72impl EqPolynomial {
73 pub fn new(r: Vec<Scalar>) -> Self {
74 EqPolynomial { r }
75 }
76
77 pub fn evaluate(&self, rx: &[Scalar]) -> Scalar {
78 assert_eq!(self.r.len(), rx.len());
79 (0..rx.len())
80 .map(|i| self.r[i] * rx[i] + (Scalar::one() - self.r[i]) * (Scalar::one() - rx[i]))
81 .product()
82 }
83
84 pub fn evals(&self) -> Vec<Scalar> {
85 let ell = self.r.len();
86
87 let mut evals: Vec<Scalar> = vec![Scalar::one(); ell.pow2()];
88 let mut size = 1;
89 for j in 0..ell {
90 // in each iteration, we double the size of chis
91 size *= 2;
92 for i in (0..size).rev().step_by(2) {
93 // copy each element from the prior iteration twice
94 let scalar = evals[i / 2];
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 IdentityPolynomial {
118 size_point: usize,
119}
120
121impl IdentityPolynomial {
122 pub fn new(size_point: usize) -> Self {
123 IdentityPolynomial { size_point }
124 }
125
126 pub fn evaluate(&self, r: &[Scalar]) -> Scalar {
127 let len = r.len();
128 assert_eq!(len, self.size_point);
129 (0..len)
130 .map(|i| Scalar::from((len - i - 1).pow2() as u64) * r[i])
131 .sum()
132 }
133}
134
135impl DensePolynomial {
136 pub fn new(Z: Vec<Scalar>) -> Self {
137 let len = Z.len();
138 let num_vars = len.log2();
139 DensePolynomial { num_vars, Z, len }
140 }
141
142 pub fn get_num_vars(&self) -> usize {
143 self.num_vars
144 }
145
146 pub fn len(&self) -> usize {
147 self.len
148 }
149
150 pub fn clone(&self) -> DensePolynomial {
151 DensePolynomial::new(self.Z[0..self.len].to_vec())
152 }
153
154 pub fn split(&self, idx: usize) -> (DensePolynomial, DensePolynomial) {
155 assert!(idx < self.len());
156 (
157 DensePolynomial::new(self.Z[0..idx].to_vec()),
158 DensePolynomial::new(self.Z[idx..2 * idx].to_vec()),
159 )
160 }
161
162 #[cfg(feature = "rayon_par")]
163 fn commit_inner(&self, blinds: &Vec<Scalar>, gens: &MultiCommitGens) -> PolyCommitment {
164 let L_size = blinds.len();
165 let R_size = self.Z.len() / L_size;
166 assert_eq!(L_size * R_size, self.Z.len());
167 let C = (0..L_size)
168 .collect::<Vec<usize>>()
169 .par_iter()
170 .map(|&i| {
171 self.Z[R_size * i..R_size * (i + 1)]
172 .commit(&blinds[i], gens)
173 .compress()
174 })
175 .collect();
176 PolyCommitment { C }
177 }
178
179 #[cfg(not(feature = "rayon_par"))]
180 fn commit_inner(&self, blinds: &[Scalar], gens: &MultiCommitGens) -> PolyCommitment {
181 let L_size = blinds.len();
182 let R_size = self.Z.len() / L_size;
183 assert_eq!(L_size * R_size, self.Z.len());
184 let C = (0..L_size)
185 .map(|i| {
186 self.Z[R_size * i..R_size * (i + 1)]
187 .commit(&blinds[i], gens)
188 .compress()
189 })
190 .collect();
191 PolyCommitment { C }
192 }
193
194 pub fn commit(
195 &self,
196 hiding: bool,
197 gens: &PolyCommitmentGens,
198 random_tape: Option<&mut RandomTape>,
199 ) -> (PolyCommitment, PolyCommitmentBlinds) {
200 let n = self.Z.len();
201 let ell = self.get_num_vars();
202 assert_eq!(n, ell.pow2());
203
204 let (left_num_vars, right_num_vars) = EqPolynomial::compute_factored_lens(ell);
205 let L_size = left_num_vars.pow2();
206 let R_size = right_num_vars.pow2();
207 assert_eq!(L_size * R_size, n);
208
209 let blinds = if hiding {
210 PolyCommitmentBlinds {
211 blinds: random_tape.unwrap().random_vector(b"poly_blinds", L_size),
212 }
213 } else {
214 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: &[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 -= 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 -= 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 += self.Z[i] * other[i];
254 }
255 res
256 }
257
258 // returns Z(r) in O(n) time
259 pub fn evaluate(&self, r: &[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 += 1;
278 self.len *= 2;
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 let mut Z: Vec<Scalar> = Vec::new();
287 for poly in polys.into_iter() {
288 Z.extend(poly.vec());
289 }
290
291 // pad the polynomial with zero polynomial at the end
292 Z.resize(Z.len().next_power_of_two(), Scalar::zero());
293
294 DensePolynomial::new(Z)
295 }
296
297 pub fn from_usize(Z: &[usize]) -> Self {
298 DensePolynomial::new(
299 (0..Z.len())
300 .map(|i| Scalar::from(Z[i] as u64))
301 .collect::<Vec<Scalar>>(),
302 )
303 }
304}
305
306impl Index<usize> for DensePolynomial {
307 type Output = Scalar;
308
309 #[inline(always)]
310 fn index(&self, _index: usize) -> &Scalar {
311 &(self.Z[_index])
312 }
313}
314
315impl AppendToTranscript for PolyCommitment {
316 fn append_to_transcript(&self, label: &'static [u8], transcript: &mut Transcript) {
317 transcript.append_message(label, b"poly_commitment_begin");
318 for i in 0..self.C.len() {
319 transcript.append_point(b"poly_commitment_share", &self.C[i]);
320 }
321 transcript.append_message(label, b"poly_commitment_end");
322 }
323}
324
325#[derive(Debug, Serialize, Deserialize)]
326pub struct PolyEvalProof {
327 proof: DotProductProofLog,
328}
329
330impl PolyEvalProof {
331 fn protocol_name() -> &'static [u8] {
332 b"polynomial evaluation proof"
333 }
334
335 pub fn prove(
336 poly: &DensePolynomial,
337 blinds_opt: Option<&PolyCommitmentBlinds>,
338 r: &[Scalar], // point at which the polynomial is evaluated
339 Zr: &Scalar, // evaluation of \widetilde{Z}(r)
340 blind_Zr_opt: Option<&Scalar>, // specifies a blind for Zr
341 gens: &PolyCommitmentGens,
342 transcript: &mut Transcript,
343 random_tape: &mut RandomTape,
344 ) -> (PolyEvalProof, CompressedGroup) {
345 transcript.append_protocol_name(PolyEvalProof::protocol_name());
346
347 // assert vectors are of the right size
348 assert_eq!(poly.get_num_vars(), r.len());
349
350 let (left_num_vars, right_num_vars) = EqPolynomial::compute_factored_lens(r.len());
351 let L_size = left_num_vars.pow2();
352 let R_size = right_num_vars.pow2();
353
354 let default_blinds = PolyCommitmentBlinds {
355 blinds: vec![Scalar::zero(); L_size],
356 };
357 let blinds = match blinds_opt {
358 Some(p) => p,
359 None => &default_blinds,
360 };
361
362 assert_eq!(blinds.blinds.len(), L_size);
363
364 let zero = Scalar::zero();
365 let blind_Zr = match blind_Zr_opt {
366 Some(p) => p,
367 None => &zero,
368 };
369
370 // compute the L and R vectors
371 let eq = EqPolynomial::new(r.to_vec());
372 let (L, R) = eq.compute_factored_evals();
373 assert_eq!(L.len(), L_size);
374 assert_eq!(R.len(), R_size);
375
376 // compute the vector underneath L*Z and the L*blinds
377 // compute vector-matrix product between L and Z viewed as a matrix
378 let LZ = poly.bound(&L);
379 let LZ_blind: Scalar = (0..L.len()).map(|i| blinds.blinds[i] * L[i]).sum();
380
381 // a dot product proof of size R_size
382 let (proof, _C_LR, C_Zr_prime) = DotProductProofLog::prove(
383 &gens.gens,
384 transcript,
385 random_tape,
386 &LZ,
387 &LZ_blind,
388 &R,
389 &Zr,
390 blind_Zr,
391 );
392
393 (PolyEvalProof { proof }, C_Zr_prime)
394 }
395
396 pub fn verify(
397 &self,
398 gens: &PolyCommitmentGens,
399 transcript: &mut Transcript,
400 r: &[Scalar], // point at which the polynomial is evaluated
401 C_Zr: &CompressedGroup, // commitment to \widetilde{Z}(r)
402 comm: &PolyCommitment,
403 ) -> Result<(), ProofVerifyError> {
404 transcript.append_protocol_name(PolyEvalProof::protocol_name());
405
406 // compute L and R
407 let eq = EqPolynomial::new(r.to_vec());
408 let (L, R) = eq.compute_factored_evals();
409
410 // compute a weighted sum of commitments and L
411 let C_decompressed = comm.C.iter().map(|pt| pt.decompress().unwrap());
412
413 let C_LZ = GroupElement::vartime_multiscalar_mul(&L, C_decompressed).compress();
414
415 self
416 .proof
417 .verify(R.len(), &gens.gens, transcript, &R, &C_LZ, C_Zr)
418 }
419
420 pub fn verify_plain(
421 &self,
422 gens: &PolyCommitmentGens,
423 transcript: &mut Transcript,
424 r: &[Scalar], // point at which the polynomial is evaluated
425 Zr: &Scalar, // evaluation \widetilde{Z}(r)
426 comm: &PolyCommitment,
427 ) -> Result<(), ProofVerifyError> {
428 // compute a commitment to Zr with a blind of zero
429 let C_Zr = Zr.commit(&Scalar::zero(), &gens.gens.gens_1).compress();
430
431 self.verify(gens, transcript, r, &C_Zr, comm)
432 }
433}
434
435#[cfg(test)]
436mod tests {
437 use super::super::scalar::ScalarFromPrimitives;
438 use super::*;
439 use rand::rngs::OsRng;
440
441 fn evaluate_with_LR(Z: &Vec<Scalar>, r: &Vec<Scalar>) -> Scalar {
442 let eq = EqPolynomial::new(r.to_vec());
443 let (L, R) = eq.compute_factored_evals();
444
445 let ell = r.len();
446 // ensure ell is even
447 assert!(ell % 2 == 0);
448 // compute n = 2^\ell
449 let n = ell.pow2();
450 // compute m = sqrt(n) = 2^{\ell/2}
451 let m = n.square_root();
452
453 // compute vector-matrix product between L and Z viewed as a matrix
454 let LZ = (0..m)
455 .map(|i| (0..m).map(|j| L[j] * Z[j * m + i]).sum())
456 .collect::<Vec<Scalar>>();
457
458 // compute dot product between LZ and R
459 DotProductProofLog::compute_dotproduct(&LZ, &R)
460 }
461
462 #[test]
463 fn check_polynomial_evaluation() {
464 let mut Z: Vec<Scalar> = Vec::new(); // Z = [1, 2, 1, 4]
465 Z.push(Scalar::one());
466 Z.push((2 as usize).to_scalar());
467 Z.push((1 as usize).to_scalar());
468 Z.push((4 as usize).to_scalar());
469 // r = [4,3]
470 let mut r: Vec<Scalar> = Vec::new();
471 r.push((4 as usize).to_scalar());
472 r.push((3 as usize).to_scalar());
473
474 let eval_with_LR = evaluate_with_LR(&Z, &r);
475 let poly = DensePolynomial::new(Z);
476
477 let eval = poly.evaluate(&r);
478 assert_eq!(eval, (28 as usize).to_scalar());
479 assert_eq!(eval_with_LR, eval);
480 }
481
482 pub fn compute_factored_chis_at_r(r: &Vec<Scalar>) -> (Vec<Scalar>, Vec<Scalar>) {
483 let mut L: Vec<Scalar> = Vec::new();
484 let mut R: Vec<Scalar> = Vec::new();
485
486 let ell = r.len();
487 assert!(ell % 2 == 0); // ensure ell is even
488 let n = ell.pow2();
489 let m = n.square_root();
490
491 // compute row vector L
492 for i in 0..m {
493 let mut chi_i = Scalar::one();
494 for j in 0..ell / 2 {
495 let bit_j = ((m * i) & (1 << (r.len() - j - 1))) > 0;
496 if bit_j {
497 chi_i *= r[j];
498 } else {
499 chi_i *= Scalar::one() - r[j];
500 }
501 }
502 L.push(chi_i);
503 }
504
505 // compute column vector R
506 for i in 0..m {
507 let mut chi_i = Scalar::one();
508 for j in ell / 2..ell {
509 let bit_j = (i & (1 << (r.len() - j - 1))) > 0;
510 if bit_j {
511 chi_i *= r[j];
512 } else {
513 chi_i *= Scalar::one() - r[j];
514 }
515 }
516 R.push(chi_i);
517 }
518 (L, R)
519 }
520
521 pub fn compute_chis_at_r(r: &Vec<Scalar>) -> Vec<Scalar> {
522 let ell = r.len();
523 let n = ell.pow2();
524 let mut chis: Vec<Scalar> = Vec::new();
525 for i in 0..n {
526 let mut chi_i = Scalar::one();
527 for j in 0..r.len() {
528 let bit_j = (i & (1 << (r.len() - j - 1))) > 0;
529 if bit_j {
530 chi_i *= r[j];
531 } else {
532 chi_i *= Scalar::one() - r[j];
533 }
534 }
535 chis.push(chi_i);
536 }
537 chis
538 }
539
540 pub fn compute_outerproduct(L: Vec<Scalar>, R: Vec<Scalar>) -> Vec<Scalar> {
541 assert_eq!(L.len(), R.len());
542
543 let mut O: Vec<Scalar> = Vec::new();
544 let m = L.len();
545 for i in 0..m {
546 for j in 0..m {
547 O.push(L[i] * R[j]);
548 }
549 }
550 O
551 }
552
553 #[test]
554 fn check_memoized_chis() {
555 let mut csprng: OsRng = OsRng;
556
557 let s = 10;
558 let mut r: Vec<Scalar> = Vec::new();
559 for _i in 0..s {
560 r.push(Scalar::random(&mut csprng));
561 }
562 let chis = tests::compute_chis_at_r(&r);
563 let chis_m = EqPolynomial::new(r).evals();
564 assert_eq!(chis, chis_m);
565 }
566
567 #[test]
568 fn check_factored_chis() {
569 let mut csprng: OsRng = OsRng;
570
571 let s = 10;
572 let mut r: Vec<Scalar> = Vec::new();
573 for _i in 0..s {
574 r.push(Scalar::random(&mut csprng));
575 }
576 let chis = EqPolynomial::new(r.clone()).evals();
577 let (L, R) = EqPolynomial::new(r).compute_factored_evals();
578 let O = compute_outerproduct(L, R);
579 assert_eq!(chis, O);
580 }
581
582 #[test]
583 fn check_memoized_factored_chis() {
584 let mut csprng: OsRng = OsRng;
585
586 let s = 10;
587 let mut r: Vec<Scalar> = Vec::new();
588 for _i in 0..s {
589 r.push(Scalar::random(&mut csprng));
590 }
591 let (L, R) = tests::compute_factored_chis_at_r(&r);
592 let eq = EqPolynomial::new(r);
593 let (L2, R2) = eq.compute_factored_evals();
594 assert_eq!(L, L2);
595 assert_eq!(R, R2);
596 }
597
598 #[test]
599 fn check_polynomial_commit() {
600 let mut Z: Vec<Scalar> = Vec::new(); // Z = [1, 2, 1, 4]
601 Z.push((1 as usize).to_scalar());
602 Z.push((2 as usize).to_scalar());
603 Z.push((1 as usize).to_scalar());
604 Z.push((4 as usize).to_scalar());
605
606 let poly = DensePolynomial::new(Z);
607
608 // r = [4,3]
609 let mut r: Vec<Scalar> = Vec::new();
610 r.push((4 as usize).to_scalar());
611 r.push((3 as usize).to_scalar());
612 let eval = poly.evaluate(&r);
613 assert_eq!(eval, (28 as usize).to_scalar());
614
615 let gens = PolyCommitmentGens::new(poly.get_num_vars(), b"test-two");
616 let (poly_commitment, blinds) = poly.commit(false, &gens, None);
617
618 let mut random_tape = RandomTape::new(b"proof");
619 let mut prover_transcript = Transcript::new(b"example");
620 let (proof, C_Zr) = PolyEvalProof::prove(
621 &poly,
622 Some(&blinds),
623 &r,
624 &eval,
625 None,
626 &gens,
627 &mut prover_transcript,
628 &mut random_tape,
629 );
630
631 let mut verifier_transcript = Transcript::new(b"example");
632 assert!(proof
633 .verify(&gens, &mut verifier_transcript, &r, &C_Zr, &poly_commitment)
634 .is_ok());
635 }
636}