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