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 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[..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 = blinds_opt.map_or(&default_blinds, |p| p);
330
331 assert_eq!(blinds.blinds.len(), L_size);
332
333 let zero = Scalar::zero();
334 let blind_Zr = blind_Zr_opt.map_or(&zero, |p| p);
335
336 // compute the L and R vectors
337 let eq = EqPolynomial::new(r.to_vec());
338 let (L, R) = eq.compute_factored_evals();
339 assert_eq!(L.len(), L_size);
340 assert_eq!(R.len(), R_size);
341
342 // compute the vector underneath L*Z and the L*blinds
343 // compute vector-matrix product between L and Z viewed as a matrix
344 let LZ = poly.bound(&L);
345 let LZ_blind: Scalar = (0..L.len()).map(|i| blinds.blinds[i] * L[i]).sum();
346
347 // a dot product proof of size R_size
348 let (proof, _C_LR, C_Zr_prime) = DotProductProofLog::prove(
349 &gens.gens,
350 transcript,
351 random_tape,
352 &LZ,
353 &LZ_blind,
354 &R,
355 &Zr,
356 blind_Zr,
357 );
358
359 (PolyEvalProof { proof }, C_Zr_prime)
360 }
361
362 pub fn verify(
363 &self,
364 gens: &PolyCommitmentGens,
365 transcript: &mut Transcript,
366 r: &[Scalar], // point at which the polynomial is evaluated
367 C_Zr: &CompressedGroup, // commitment to \widetilde{Z}(r)
368 comm: &PolyCommitment,
369 ) -> Result<(), ProofVerifyError> {
370 transcript.append_protocol_name(PolyEvalProof::protocol_name());
371
372 // compute L and R
373 let eq = EqPolynomial::new(r.to_vec());
374 let (L, R) = eq.compute_factored_evals();
375
376 // compute a weighted sum of commitments and L
377 let C_decompressed = comm.C.iter().map(|pt| pt.decompress().unwrap());
378
379 let C_LZ = GroupElement::vartime_multiscalar_mul(&L, C_decompressed).compress();
380
381 self
382 .proof
383 .verify(R.len(), &gens.gens, transcript, &R, &C_LZ, C_Zr)
384 }
385
386 pub fn verify_plain(
387 &self,
388 gens: &PolyCommitmentGens,
389 transcript: &mut Transcript,
390 r: &[Scalar], // point at which the polynomial is evaluated
391 Zr: &Scalar, // evaluation \widetilde{Z}(r)
392 comm: &PolyCommitment,
393 ) -> Result<(), ProofVerifyError> {
394 // compute a commitment to Zr with a blind of zero
395 let C_Zr = Zr.commit(&Scalar::zero(), &gens.gens.gens_1).compress();
396
397 self.verify(gens, transcript, r, &C_Zr, comm)
398 }
399}
400
401#[cfg(test)]
402mod tests {
403 use super::super::scalar::ScalarFromPrimitives;
404 use super::*;
405 use rand::rngs::OsRng;
406
407 fn evaluate_with_LR(Z: &Vec<Scalar>, r: &Vec<Scalar>) -> Scalar {
408 let eq = EqPolynomial::new(r.to_vec());
409 let (L, R) = eq.compute_factored_evals();
410
411 let ell = r.len();
412 // ensure ell is even
413 assert!(ell % 2 == 0);
414 // compute n = 2^\ell
415 let n = ell.pow2();
416 // compute m = sqrt(n) = 2^{\ell/2}
417 let m = n.square_root();
418
419 // compute vector-matrix product between L and Z viewed as a matrix
420 let LZ = (0..m)
421 .map(|i| (0..m).map(|j| L[j] * Z[j * m + i]).sum())
422 .collect::<Vec<Scalar>>();
423
424 // compute dot product between LZ and R
425 DotProductProofLog::compute_dotproduct(&LZ, &R)
426 }
427
428 #[test]
429 fn check_polynomial_evaluation() {
430 let mut Z: Vec<Scalar> = Vec::new(); // Z = [1, 2, 1, 4]
431 Z.push(Scalar::one());
432 Z.push((2 as usize).to_scalar());
433 Z.push((1 as usize).to_scalar());
434 Z.push((4 as usize).to_scalar());
435 // r = [4,3]
436 let mut r: Vec<Scalar> = Vec::new();
437 r.push((4 as usize).to_scalar());
438 r.push((3 as usize).to_scalar());
439
440 let eval_with_LR = evaluate_with_LR(&Z, &r);
441 let poly = DensePolynomial::new(Z);
442
443 let eval = poly.evaluate(&r);
444 assert_eq!(eval, (28 as usize).to_scalar());
445 assert_eq!(eval_with_LR, eval);
446 }
447
448 pub fn compute_factored_chis_at_r(r: &Vec<Scalar>) -> (Vec<Scalar>, Vec<Scalar>) {
449 let mut L: Vec<Scalar> = Vec::new();
450 let mut R: Vec<Scalar> = Vec::new();
451
452 let ell = r.len();
453 assert!(ell % 2 == 0); // ensure ell is even
454 let n = ell.pow2();
455 let m = n.square_root();
456
457 // compute row vector L
458 for i in 0..m {
459 let mut chi_i = Scalar::one();
460 for j in 0..ell / 2 {
461 let bit_j = ((m * i) & (1 << (r.len() - j - 1))) > 0;
462 if bit_j {
463 chi_i *= r[j];
464 } else {
465 chi_i *= Scalar::one() - r[j];
466 }
467 }
468 L.push(chi_i);
469 }
470
471 // compute column vector R
472 for i in 0..m {
473 let mut chi_i = Scalar::one();
474 for j in ell / 2..ell {
475 let bit_j = (i & (1 << (r.len() - j - 1))) > 0;
476 if bit_j {
477 chi_i *= r[j];
478 } else {
479 chi_i *= Scalar::one() - r[j];
480 }
481 }
482 R.push(chi_i);
483 }
484 (L, R)
485 }
486
487 pub fn compute_chis_at_r(r: &Vec<Scalar>) -> Vec<Scalar> {
488 let ell = r.len();
489 let n = ell.pow2();
490 let mut chis: Vec<Scalar> = Vec::new();
491 for i in 0..n {
492 let mut chi_i = Scalar::one();
493 for j in 0..r.len() {
494 let bit_j = (i & (1 << (r.len() - j - 1))) > 0;
495 if bit_j {
496 chi_i *= r[j];
497 } else {
498 chi_i *= Scalar::one() - r[j];
499 }
500 }
501 chis.push(chi_i);
502 }
503 chis
504 }
505
506 pub fn compute_outerproduct(L: Vec<Scalar>, R: Vec<Scalar>) -> Vec<Scalar> {
507 assert_eq!(L.len(), R.len());
508
509 let mut O: Vec<Scalar> = Vec::new();
510 let m = L.len();
511 for i in 0..m {
512 for j in 0..m {
513 O.push(L[i] * R[j]);
514 }
515 }
516 O
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 mut Z: Vec<Scalar> = Vec::new(); // Z = [1, 2, 1, 4]
567 Z.push((1 as usize).to_scalar());
568 Z.push((2 as usize).to_scalar());
569 Z.push((1 as usize).to_scalar());
570 Z.push((4 as usize).to_scalar());
571
572 let poly = DensePolynomial::new(Z);
573
574 // r = [4,3]
575 let mut r: Vec<Scalar> = Vec::new();
576 r.push((4 as usize).to_scalar());
577 r.push((3 as usize).to_scalar());
578 let eval = poly.evaluate(&r);
579 assert_eq!(eval, (28 as usize).to_scalar());
580
581 let gens = PolyCommitmentGens::new(poly.get_num_vars(), b"test-two");
582 let (poly_commitment, blinds) = poly.commit(&gens, None);
583
584 let mut random_tape = RandomTape::new(b"proof");
585 let mut prover_transcript = Transcript::new(b"example");
586 let (proof, C_Zr) = PolyEvalProof::prove(
587 &poly,
588 Some(&blinds),
589 &r,
590 &eval,
591 None,
592 &gens,
593 &mut prover_transcript,
594 &mut random_tape,
595 );
596
597 let mut verifier_transcript = Transcript::new(b"example");
598 assert!(proof
599 .verify(&gens, &mut verifier_transcript, &r, &C_Zr, &poly_commitment)
600 .is_ok());
601 }
602}