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