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