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