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