sonobe/folding-schemes/src/folding/hypernova/utils.rs
folding-schemes/src/folding/hypernova/utils.rsRaw
1use ark_ec::CurveGroup;
2use ark_ff::{Field, PrimeField};
3use ark_poly::DenseMultilinearExtension;
4use ark_poly::MultilinearExtension;
5use ark_std::{One, Zero};
6use std::ops::Add;
7
8use crate::utils::multilinear_polynomial::fix_variables;
9use crate::utils::multilinear_polynomial::scalar_mul;
10
11use super::lcccs::LCCCS;
12use super::nimfs::SigmasThetas;
13use crate::ccs::CCS;
14use crate::utils::hypercube::BooleanHypercube;
15use crate::utils::mle::dense_vec_to_mle;
16use crate::utils::mle::matrix_to_mle;
17use crate::utils::vec::SparseMatrix;
18use crate::utils::virtual_polynomial::{eq_eval, VirtualPolynomial};
19
20/// Return a vector of evaluations p_j(r) = \sum_{y \in {0,1}^s'} M_j(r, y) * z(y) for all j values
21/// in 0..self.t
22pub fn compute_all_sum_Mz_evals<F: PrimeField>(
23 vec_M: &[SparseMatrix<F>],
24 z: &Vec<F>,
25 r: &[F],
26 s_prime: usize,
27) -> Vec<F> {
28 // Convert z to MLE
29 let z_y_mle = dense_vec_to_mle(s_prime, z);
30 // Convert all matrices to MLE
31 let M_x_y_mle: Vec<DenseMultilinearExtension<F>> =
32 vec_M.iter().cloned().map(matrix_to_mle).collect();
33
34 let mut v = Vec::with_capacity(M_x_y_mle.len());
35 for M_i in M_x_y_mle {
36 let sum_Mz = compute_sum_Mz(M_i, &z_y_mle, s_prime);
37 let v_i = sum_Mz.evaluate(r).unwrap();
38 v.push(v_i);
39 }
40 v
41}
42
43/// Return the multilinear polynomial p(x) = \sum_{y \in {0,1}^s'} M_j(x, y) * z(y)
44pub fn compute_sum_Mz<F: PrimeField>(
45 M_j: DenseMultilinearExtension<F>,
46 z: &DenseMultilinearExtension<F>,
47 s_prime: usize,
48) -> DenseMultilinearExtension<F> {
49 let mut sum_Mz = DenseMultilinearExtension {
50 evaluations: vec![F::zero(); M_j.evaluations.len()],
51 num_vars: M_j.num_vars - s_prime,
52 };
53
54 let bhc = BooleanHypercube::new(s_prime);
55 for y in bhc.into_iter() {
56 // In a slightly counter-intuitive fashion fix_variables() fixes the right-most variables of the polynomial. So
57 // for a polynomial M(x,y) and a random field element r, if we do fix_variables(M,r) we will get M(x,r).
58 let M_j_y = fix_variables(&M_j, &y);
59 let z_y = z.evaluate(&y).unwrap();
60 let M_j_z = scalar_mul(&M_j_y, &z_y);
61 sum_Mz = sum_Mz.add(M_j_z);
62 }
63 sum_Mz
64}
65
66/// Compute the arrays of sigma_i and theta_i from step 4 corresponding to the LCCCS and CCCS
67/// instances
68pub fn compute_sigmas_and_thetas<C: CurveGroup>(
69 ccs: &CCS<C>,
70 z_lcccs: &[Vec<C::ScalarField>],
71 z_cccs: &[Vec<C::ScalarField>],
72 r_x_prime: &[C::ScalarField],
73) -> SigmasThetas<C::ScalarField> {
74 let mut sigmas: Vec<Vec<C::ScalarField>> = Vec::new();
75 for z_lcccs_i in z_lcccs {
76 // sigmas
77 let sigma_i = compute_all_sum_Mz_evals(&ccs.M, z_lcccs_i, r_x_prime, ccs.s_prime);
78 sigmas.push(sigma_i);
79 }
80 let mut thetas: Vec<Vec<C::ScalarField>> = Vec::new();
81 for z_cccs_i in z_cccs {
82 // thetas
83 let theta_i = compute_all_sum_Mz_evals(&ccs.M, z_cccs_i, r_x_prime, ccs.s_prime);
84 thetas.push(theta_i);
85 }
86 SigmasThetas(sigmas, thetas)
87}
88
89/// Computes the sum $\sum_{j = 0}^{n} \gamma^{\text{pow} + j} \cdot eq_eval \cdot \sigma_{j}$
90/// `pow` corresponds to `i * ccs.t` in `compute_c_from_sigmas_and_thetas`
91pub fn sum_muls_gamma_pows_eq_sigma<F: PrimeField>(
92 gamma: F,
93 eq_eval: F,
94 sigmas: &[F],
95 pow: u64,
96) -> F {
97 let mut result = F::zero();
98 for (j, sigma_j) in sigmas.iter().enumerate() {
99 let gamma_j = gamma.pow([(pow + (j as u64))]);
100 result += gamma_j * eq_eval * sigma_j;
101 }
102 result
103}
104
105/// Computes $\sum_{i=1}^{q} c_i * \prod_{j \in S_i} theta_j$
106pub fn sum_ci_mul_prod_thetaj<C: CurveGroup>(
107 ccs: &CCS<C>,
108 thetas: &[C::ScalarField],
109) -> C::ScalarField {
110 let mut result = C::ScalarField::zero();
111 for i in 0..ccs.q {
112 let mut prod = C::ScalarField::one();
113 for j in ccs.S[i].clone() {
114 prod *= thetas[j];
115 }
116 result += ccs.c[i] * prod;
117 }
118 result
119}
120
121/// Compute the right-hand-side of step 5 of the multifolding scheme
122pub fn compute_c_from_sigmas_and_thetas<C: CurveGroup>(
123 ccs: &CCS<C>,
124 st: &SigmasThetas<C::ScalarField>,
125 gamma: C::ScalarField,
126 beta: &[C::ScalarField],
127 vec_r_x: &Vec<Vec<C::ScalarField>>,
128 r_x_prime: &[C::ScalarField],
129) -> C::ScalarField {
130 let (vec_sigmas, vec_thetas) = (st.0.clone(), st.1.clone());
131 let mut c = C::ScalarField::zero();
132
133 let mut e_lcccs = Vec::new();
134 for r_x in vec_r_x {
135 e_lcccs.push(eq_eval(r_x, r_x_prime).unwrap());
136 }
137 for (i, sigmas) in vec_sigmas.iter().enumerate() {
138 // (sum gamma^j * e_i * sigma_j)
139 c += sum_muls_gamma_pows_eq_sigma(gamma, e_lcccs[i], sigmas, (i * ccs.t) as u64);
140 }
141
142 let mu = vec_sigmas.len();
143 let e2 = eq_eval(beta, r_x_prime).unwrap();
144 for (k, thetas) in vec_thetas.iter().enumerate() {
145 // + gamma^{t+1} * e2 * sum c_i * prod theta_j
146 let lhs = sum_ci_mul_prod_thetaj(ccs, thetas);
147 let gamma_t1 = gamma.pow([(mu * ccs.t + k) as u64]);
148 c += gamma_t1 * e2 * lhs;
149 }
150 c
151}
152
153/// Compute g(x) polynomial for the given inputs.
154pub fn compute_g<C: CurveGroup>(
155 ccs: &CCS<C>,
156 running_instances: &[LCCCS<C>],
157 z_lcccs: &[Vec<C::ScalarField>],
158 z_cccs: &[Vec<C::ScalarField>],
159 gamma: C::ScalarField,
160 beta: &[C::ScalarField],
161) -> VirtualPolynomial<C::ScalarField> {
162 let mu = running_instances.len();
163 let mut vec_Ls: Vec<VirtualPolynomial<C::ScalarField>> = Vec::new();
164 for (i, running_instance) in running_instances.iter().enumerate() {
165 let mut Ls = running_instance.compute_Ls(ccs, &z_lcccs[i]);
166 vec_Ls.append(&mut Ls);
167 }
168 let mut vec_Q: Vec<VirtualPolynomial<C::ScalarField>> = Vec::new();
169 // for (i, _) in cccs_instances.iter().enumerate() {
170 for z_cccs_i in z_cccs.iter() {
171 let Q = ccs.compute_Q(z_cccs_i, beta);
172 vec_Q.push(Q);
173 }
174 let mut g = vec_Ls[0].clone();
175
176 // note: the following two loops can be integrated in the previous two loops, but left
177 // separated for clarity in the PoC implementation.
178 for (j, L_j) in vec_Ls.iter_mut().enumerate().skip(1) {
179 let gamma_j = gamma.pow([j as u64]);
180 L_j.scalar_mul(&gamma_j);
181 g = g.add(L_j);
182 }
183 for (i, Q_i) in vec_Q.iter_mut().enumerate() {
184 let gamma_mut_i = gamma.pow([(mu * ccs.t + i) as u64]);
185 Q_i.scalar_mul(&gamma_mut_i);
186 g = g.add(Q_i);
187 }
188 g
189}
190
191#[cfg(test)]
192pub mod tests {
193 use super::*;
194
195 use ark_pallas::{Fr, Projective};
196 use ark_std::test_rng;
197 use ark_std::One;
198 use ark_std::UniformRand;
199 use ark_std::Zero;
200
201 use crate::ccs::tests::{get_test_ccs, get_test_z};
202 use crate::commitment::pedersen::Pedersen;
203 use crate::utils::multilinear_polynomial::tests::fix_last_variables;
204 use crate::utils::virtual_polynomial::eq_eval;
205
206 #[test]
207 fn test_compute_sum_Mz_over_boolean_hypercube() {
208 let ccs = get_test_ccs::<Projective>();
209 let z = get_test_z(3);
210 ccs.check_relation(&z).unwrap();
211 let z_mle = dense_vec_to_mle(ccs.s_prime, &z);
212
213 // check that evaluating over all the values x over the boolean hypercube, the result of
214 // the next for loop is equal to 0
215 for x in BooleanHypercube::new(ccs.s) {
216 let mut r = Fr::zero();
217 for i in 0..ccs.q {
218 let mut Sj_prod = Fr::one();
219 for j in ccs.S[i].clone() {
220 let M_j = matrix_to_mle(ccs.M[j].clone());
221 let sum_Mz = compute_sum_Mz(M_j, &z_mle, ccs.s_prime);
222 let sum_Mz_x = sum_Mz.evaluate(&x).unwrap();
223 Sj_prod *= sum_Mz_x;
224 }
225 r += Sj_prod * ccs.c[i];
226 }
227 assert_eq!(r, Fr::zero());
228 }
229 }
230
231 /// Given M(x,y) matrix and a random field element `r`, test that ~M(r,y) is is an s'-variable polynomial which
232 /// compresses every column j of the M(x,y) matrix by performing a random linear combination between the elements
233 /// of the column and the values eq_i(r) where i is the row of that element
234 ///
235 /// For example, for matrix M:
236 ///
237 /// [2, 3, 4, 4
238 /// 4, 4, 3, 2
239 /// 2, 8, 9, 2
240 /// 9, 4, 2, 0]
241 ///
242 /// The polynomial ~M(r,y) is a polynomial in F^2 which evaluates to the following values in the hypercube:
243 /// - M(00) = 2*eq_00(r) + 4*eq_10(r) + 2*eq_01(r) + 9*eq_11(r)
244 /// - M(10) = 3*eq_00(r) + 4*eq_10(r) + 8*eq_01(r) + 4*eq_11(r)
245 /// - M(01) = 4*eq_00(r) + 3*eq_10(r) + 9*eq_01(r) + 2*eq_11(r)
246 /// - M(11) = 4*eq_00(r) + 2*eq_10(r) + 2*eq_01(r) + 0*eq_11(r)
247 ///
248 /// This is used by Hypernova in LCCCS to perform a verifier-chosen random linear combination between the columns
249 /// of the matrix and the z vector. This technique is also used extensively in "An Algebraic Framework for
250 /// Universal and Updatable SNARKs".
251 #[test]
252 fn test_compute_M_r_y_compression() {
253 let mut rng = test_rng();
254
255 // s = 2, s' = 3
256 let ccs = get_test_ccs::<Projective>();
257
258 let M = ccs.M[0].clone().to_dense();
259 let M_mle = matrix_to_mle(ccs.M[0].clone());
260
261 // Fix the polynomial ~M(r,y)
262 let r: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
263 let M_r_y = fix_last_variables(&M_mle, &r);
264
265 // compute M_r_y the other way around
266 for j in 0..M[0].len() {
267 // Go over every column of M
268 let column_j: Vec<Fr> = M.clone().iter().map(|x| x[j]).collect();
269 // and perform the random lincomb between the elements of the column and eq_i(r)
270 let rlc = BooleanHypercube::new(ccs.s)
271 .enumerate()
272 .map(|(i, x)| column_j[i] * eq_eval(&x, &r).unwrap())
273 .fold(Fr::zero(), |acc, result| acc + result);
274
275 assert_eq!(M_r_y.evaluations[j], rlc);
276 }
277 }
278
279 #[test]
280 fn test_compute_sigmas_and_thetas() {
281 let ccs = get_test_ccs();
282 let z1 = get_test_z(3);
283 let z2 = get_test_z(4);
284 ccs.check_relation(&z1).unwrap();
285 ccs.check_relation(&z2).unwrap();
286
287 let mut rng = test_rng();
288 let gamma: Fr = Fr::rand(&mut rng);
289 let beta: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
290 let r_x_prime: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
291
292 // Initialize a multifolding object
293 let pedersen_params = Pedersen::new_params(&mut rng, ccs.n - ccs.l - 1);
294 let (lcccs_instance, _) = ccs.to_lcccs(&mut rng, &pedersen_params, &z1).unwrap();
295
296 let sigmas_thetas =
297 compute_sigmas_and_thetas(&ccs, &[z1.clone()], &[z2.clone()], &r_x_prime);
298
299 let g = compute_g(
300 &ccs,
301 &[lcccs_instance.clone()],
302 &[z1.clone()],
303 &[z2.clone()],
304 gamma,
305 &beta,
306 );
307
308 // we expect g(r_x_prime) to be equal to:
309 // c = (sum gamma^j * e1 * sigma_j) + gamma^{t+1} * e2 * sum c_i * prod theta_j
310 // from compute_c_from_sigmas_and_thetas
311 let expected_c = g.evaluate(&r_x_prime).unwrap();
312 let c = compute_c_from_sigmas_and_thetas::<Projective>(
313 &ccs,
314 &sigmas_thetas,
315 gamma,
316 &beta,
317 &vec![lcccs_instance.r_x],
318 &r_x_prime,
319 );
320 assert_eq!(c, expected_c);
321 }
322
323 #[test]
324 fn test_compute_g() {
325 let ccs = get_test_ccs();
326 let z1 = get_test_z(3);
327 let z2 = get_test_z(4);
328 ccs.check_relation(&z1).unwrap();
329 ccs.check_relation(&z2).unwrap();
330
331 let mut rng = test_rng(); // TMP
332 let gamma: Fr = Fr::rand(&mut rng);
333 let beta: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
334
335 // Initialize a multifolding object
336 let pedersen_params = Pedersen::new_params(&mut rng, ccs.n - ccs.l - 1);
337 let (lcccs_instance, _) = ccs.to_lcccs(&mut rng, &pedersen_params, &z1).unwrap();
338
339 let mut sum_v_j_gamma = Fr::zero();
340 for j in 0..lcccs_instance.v.len() {
341 let gamma_j = gamma.pow([j as u64]);
342 sum_v_j_gamma += lcccs_instance.v[j] * gamma_j;
343 }
344
345 // Compute g(x) with that r_x
346 let g = compute_g::<Projective>(
347 &ccs,
348 &[lcccs_instance.clone()],
349 &[z1.clone()],
350 &[z2.clone()],
351 gamma,
352 &beta,
353 );
354
355 // evaluate g(x) over x \in {0,1}^s
356 let mut g_on_bhc = Fr::zero();
357 for x in BooleanHypercube::new(ccs.s) {
358 g_on_bhc += g.evaluate(&x).unwrap();
359 }
360
361 // evaluate sum_{j \in [t]} (gamma^j * Lj(x)) over x \in {0,1}^s
362 let mut sum_Lj_on_bhc = Fr::zero();
363 let vec_L = lcccs_instance.compute_Ls(&ccs, &z1);
364 for x in BooleanHypercube::new(ccs.s) {
365 for (j, Lj) in vec_L.iter().enumerate() {
366 let gamma_j = gamma.pow([j as u64]);
367 sum_Lj_on_bhc += Lj.evaluate(&x).unwrap() * gamma_j;
368 }
369 }
370
371 // Q(x) over bhc is assumed to be zero, as checked in the test 'test_compute_Q'
372 assert_ne!(g_on_bhc, Fr::zero());
373
374 // evaluating g(x) over the boolean hypercube should give the same result as evaluating the
375 // sum of gamma^j * Lj(x) over the boolean hypercube
376 assert_eq!(g_on_bhc, sum_Lj_on_bhc);
377
378 // evaluating g(x) over the boolean hypercube should give the same result as evaluating the
379 // sum of gamma^j * v_j over j \in [t]
380 assert_eq!(g_on_bhc, sum_v_j_gamma);
381 }
382}