testudo/src/sqrt_pst.rs
src/sqrt_pst.rsRaw
1use crate::mipp::MippProof;
2use ark_ec::{pairing::Pairing, scalar_mul::variable_base::VariableBaseMSM, CurveGroup};
3use ark_ff::One;
4use ark_poly_commit::multilinear_pc::{
5 data_structures::{Commitment, CommitterKey, Proof, VerifierKey},
6 MultilinearPC,
7};
8use rayon::prelude::{IntoParallelIterator, IntoParallelRefIterator, ParallelIterator};
9
10use crate::{
11 dense_mlpoly::DensePolynomial, math::Math, poseidon_transcript::PoseidonTranscript, timer::Timer,
12};
13
14pub struct Polynomial<E: Pairing> {
15 m: usize,
16 odd: usize,
17 polys: Vec<DensePolynomial<E::ScalarField>>,
18 q: Option<DensePolynomial<E::ScalarField>>,
19 chis_b: Option<Vec<E::ScalarField>>,
20}
21
22impl<E: Pairing> Polynomial<E> {
23 // Given the evaluations over the boolean hypercube of a polynomial p of size
24 // n compute the sqrt-sized polynomials p_i as
25 // p_i(X) = \sum_{j \in \{0,1\}^m} p(j, i) * chi_j(X)
26 // where p(X,Y) = \sum_{i \in \{0,\1}^m}
27 // (\sum_{j \in \{0, 1\}^{m}} p(j, i) * \chi_j(X)) * \chi_i(Y)
28 // and m is n/2.
29 // To handle the case in which n is odd, the number of variables in the
30 // sqrt-sized polynomials will be increased by a factor of 2 (i.e. 2^{m+1})
31 // while the number of polynomials remains the same (i.e. 2^m)
32 pub fn from_evaluations(Z: &[E::ScalarField]) -> Self {
33 let pl_timer = Timer::new("poly_list_build");
34 // check the evaluation list is a power of 2
35 debug_assert!(Z.len() & (Z.len() - 1) == 0);
36
37 let num_vars = Z.len().log_2();
38 let m_col = num_vars / 2;
39 let m_row = if num_vars % 2 == 0 {
40 num_vars / 2
41 } else {
42 num_vars / 2 + 1
43 };
44
45 let pow_m_col = 2_usize.pow(m_col as u32);
46 let pow_m_row = 2_usize.pow(m_row as u32);
47
48 let polys: Vec<DensePolynomial<E::ScalarField>> = (0..pow_m_col)
49 .into_par_iter()
50 .map(|i| {
51 let z: Vec<E::ScalarField> = (0..pow_m_row)
52 .into_par_iter()
53 // viewing the list of evaluation as a square matrix
54 // we select by row j and column i
55 // to handle the odd case, we add another row to the matrix i.e.
56 // we add an extra variable to the polynomials while keeping their
57 // number tje same
58 .map(|j| Z[(j << m_col) | i])
59 .collect();
60 DensePolynomial::new(z)
61 })
62 .collect();
63
64 debug_assert!(polys.len() == pow_m_col);
65 debug_assert!(polys[0].len == pow_m_row);
66
67 pl_timer.stop();
68 Self {
69 m: m_col,
70 odd: if num_vars % 2 == 1 { 1 } else { 0 },
71 polys,
72 q: None,
73 chis_b: None,
74 }
75 }
76
77 // Given point = (\vec{a}, \vec{b}), compute the polynomial q as
78 // q(Y) =
79 // \sum_{j \in \{0,1\}^m}(\sum_{i \in \{0,1\}^m} p(j,i) * chi_i(b)) * chi_j(Y)
80 // and p(a,b) = q(a) where p is the initial polynomial
81 fn get_q(&mut self, point: &[E::ScalarField]) {
82 let q_timer = Timer::new("build_q");
83
84 debug_assert!(point.len() == 2 * self.m + self.odd);
85 let b = &point[self.m + self.odd..];
86 let pow_m = 2_usize.pow(self.m as u32);
87
88 let chis: Vec<E::ScalarField> = (0..pow_m)
89 .into_par_iter()
90 .map(|i| Self::get_chi_i(b, i))
91 .collect();
92
93 let z_q: Vec<E::ScalarField> = (0..(pow_m * 2_usize.pow(self.odd as u32)))
94 .into_par_iter()
95 .map(|j| (0..pow_m).map(|i| self.polys[i].Z[j] * chis[i]).sum())
96 .collect();
97 q_timer.stop();
98
99 self.q = Some(DensePolynomial::new(z_q));
100 self.chis_b = Some(chis);
101 }
102
103 // Given point = (\vec{a}, \vec{b}) used to construct q
104 // compute q(a) = p(a,b).
105 pub fn eval(&mut self, point: &[E::ScalarField]) -> E::ScalarField {
106 let a = &point[0..point.len() / 2 + self.odd];
107 if self.q.is_none() {
108 self.get_q(point);
109 }
110 let q = self.q.clone().unwrap();
111 (0..q.Z.len())
112 .into_par_iter()
113 .map(|j| q.Z[j] * Polynomial::<E>::get_chi_i(&a, j))
114 .sum()
115 }
116
117 pub fn commit(&self, ck: &CommitterKey<E>) -> (Vec<Commitment<E>>, E::TargetField) {
118 let timer_commit = Timer::new("sqrt_commit");
119 let timer_list = Timer::new("comm_list");
120 // commit to each of the sqrt sized p_i
121 let comm_list: Vec<Commitment<E>> = self
122 .polys
123 .par_iter()
124 .map(|p| MultilinearPC::<E>::commit(&ck, p))
125 .collect();
126 timer_list.stop();
127
128 let h_vec = ck.powers_of_h[self.odd].clone();
129 assert!(comm_list.len() == h_vec.len());
130
131 let ipp_timer = Timer::new("ipp");
132 let left_pairs: Vec<_> = comm_list
133 .clone()
134 .into_par_iter()
135 .map(|c| E::G1Prepared::from(c.g_product))
136 .collect();
137 let right_pairs: Vec<_> = h_vec
138 .into_par_iter()
139 .map(|h| E::G2Prepared::from(h))
140 .collect();
141
142 // compute the IPP commitment
143 let t = E::multi_pairing(left_pairs, right_pairs).0;
144 ipp_timer.stop();
145
146 timer_commit.stop();
147
148 (comm_list, t)
149 }
150
151 // computes \chi_i(\vec{b}) = \prod_{i_j = 0}(1 - b_j)\prod_{i_j = 1}(b_j)
152 pub fn get_chi_i(b: &[E::ScalarField], i: usize) -> E::ScalarField {
153 let m = b.len();
154 let mut prod = E::ScalarField::one();
155 for j in 0..m {
156 let b_j = b[j];
157 // iterate from first (msb) to last (lsb) bit of i
158 // to build chi_i using the formula above
159 if i >> (m - j - 1) & 1 == 1 {
160 prod = prod * b_j;
161 } else {
162 prod = prod * (E::ScalarField::one() - b_j)
163 };
164 }
165 prod
166 }
167
168 pub fn open(
169 &mut self,
170 transcript: &mut PoseidonTranscript<E::ScalarField>,
171 comm_list: Vec<Commitment<E>>,
172 ck: &CommitterKey<E>,
173 point: &[E::ScalarField],
174 t: &E::TargetField,
175 ) -> (Commitment<E>, Proof<E>, MippProof<E>) {
176 let a = &point[0..self.m + self.odd];
177 if self.q.is_none() {
178 self.get_q(point);
179 }
180
181 let q = self.q.clone().unwrap();
182
183 let timer_open = Timer::new("sqrt_open");
184
185 // Compute the PST commitment to q obtained as the inner products of the
186 // commitments to the polynomials p_i and chi_i(\vec{b}) for i ranging over
187 // the boolean hypercube of size m.
188 let timer_msm = Timer::new("msm");
189 if self.chis_b.is_none() {
190 panic!("chis(b) should have been computed for q");
191 }
192 // TODO remove that cloning - the whole option thing
193 let chis = self.chis_b.clone().unwrap();
194 assert!(chis.len() == comm_list.len());
195
196 let comms: Vec<_> = comm_list.par_iter().map(|c| c.g_product).collect();
197
198 let c_u = <E::G1 as VariableBaseMSM>::msm_unchecked(&comms, &chis).into_affine();
199 timer_msm.stop();
200
201 let U: Commitment<E> = Commitment {
202 nv: q.num_vars,
203 g_product: c_u,
204 };
205 let comm = MultilinearPC::<E>::commit(ck, &q);
206 debug_assert!(c_u == comm.g_product);
207 let h_vec = ck.powers_of_h[self.odd].clone();
208
209 // construct MIPP proof that U is the inner product of the vector A
210 // and the vector y, where A is the opening vector to T
211 let timer_mipp_proof = Timer::new("mipp_prove");
212 let mipp_proof =
213 MippProof::<E>::prove(transcript, ck, comms, chis.to_vec(), h_vec, &c_u, t).unwrap();
214 timer_mipp_proof.stop();
215
216 let timer_proof = Timer::new("pst_open");
217
218 // reversing a is necessary because the sumcheck code in spartan generates
219 // the point in reverse order compared to how the polynomial commitment
220 // expects it
221 let mut a_rev = a.to_vec().clone();
222 a_rev.reverse();
223
224 // construct PST proof for opening q at a
225 let pst_proof = MultilinearPC::<E>::open(ck, &q, &a_rev);
226 timer_proof.stop();
227
228 timer_open.stop();
229 (U, pst_proof, mipp_proof)
230 }
231
232 pub fn verify(
233 transcript: &mut PoseidonTranscript<E::ScalarField>,
234 vk: &VerifierKey<E>,
235 U: &Commitment<E>,
236 point: &[E::ScalarField],
237 v: E::ScalarField,
238 pst_proof: &Proof<E>,
239 mipp_proof: &MippProof<E>,
240 T: &E::TargetField,
241 ) -> bool {
242 let len = point.len();
243 let odd = if len % 2 == 1 { 1 } else { 0 };
244 let a = &point[0..len / 2 + odd];
245 let b = &point[len / 2 + odd..len];
246
247 let timer_mipp_verify = Timer::new("mipp_verify");
248 // verify that U = A^y where A is the opening vector of T
249 let res_mipp = MippProof::<E>::verify(vk, transcript, mipp_proof, b.to_vec(), &U.g_product, T);
250 assert!(res_mipp == true);
251 timer_mipp_verify.stop();
252
253 // reversing a is necessary because the sumcheck code in spartan generates
254 // the point in reverse order compared to how the polynomial commitment
255 // expects
256 let mut a_rev = a.to_vec().clone();
257 a_rev.reverse();
258
259 let timer_pst_verify = Timer::new("pst_verify");
260 // PST proof that q(a) is indeed equal to value claimed by the prover
261 let res = MultilinearPC::<E>::check(vk, U, &a_rev, v, pst_proof);
262 timer_pst_verify.stop();
263 res
264 }
265}
266
267#[cfg(test)]
268mod tests {
269
270 use crate::parameters::poseidon_params;
271
272 use super::*;
273 type F = ark_bls12_377::Fr;
274 type E = ark_bls12_377::Bls12_377;
275
276 use ark_std::UniformRand;
277 #[test]
278 fn check_sqrt_poly_eval() {
279 let mut rng = ark_std::test_rng();
280 let num_vars = 6;
281 let len = 2_usize.pow(num_vars);
282 let Z: Vec<F> = (0..len).into_iter().map(|_| F::rand(&mut rng)).collect();
283 let r: Vec<F> = (0..num_vars)
284 .into_iter()
285 .map(|_| F::rand(&mut rng))
286 .collect();
287
288 let p = DensePolynomial::new(Z.clone());
289 let res1 = p.evaluate(&r);
290
291 let mut pl = Polynomial::<E>::from_evaluations(&Z.clone());
292 let res2 = pl.eval(&r);
293
294 assert!(res1 == res2);
295 }
296
297 #[test]
298 fn check_commit() {
299 // check odd case
300 check_sqrt_poly_commit(5);
301
302 // check even case
303 check_sqrt_poly_commit(6);
304 }
305
306 fn check_sqrt_poly_commit(num_vars: u32) {
307 let mut rng = ark_std::test_rng();
308 let len = 2_usize.pow(num_vars);
309 let Z: Vec<F> = (0..len).into_iter().map(|_| F::rand(&mut rng)).collect();
310 let r: Vec<F> = (0..num_vars)
311 .into_iter()
312 .map(|_| F::rand(&mut rng))
313 .collect();
314
315 let gens = MultilinearPC::<E>::setup(3, &mut rng);
316 let (ck, vk) = MultilinearPC::<E>::trim(&gens, 3);
317
318 let mut pl = Polynomial::from_evaluations(&Z.clone());
319
320 let v = pl.eval(&r);
321
322 let (comm_list, t) = pl.commit(&ck);
323
324 let params = poseidon_params();
325 let mut prover_transcript = PoseidonTranscript::new(¶ms);
326
327 let (u, pst_proof, mipp_proof) = pl.open(&mut prover_transcript, comm_list, &ck, &r, &t);
328
329 let mut verifier_transcript = PoseidonTranscript::new(¶ms);
330
331 let res = Polynomial::verify(
332 &mut verifier_transcript,
333 &vk,
334 &u,
335 &r,
336 v,
337 &pst_proof,
338 &mipp_proof,
339 &t,
340 );
341 assert!(res == true);
342 }
343}