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