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