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 (i, _) in cccs_instances.iter().enumerate() {
153 for z_cccs_i in z_cccs.iter() {
154 let Q = ccs.compute_Q(z_cccs_i, beta);
155 vec_Q.push(Q);
156 }
157 let mut g = vec_Ls[0].clone();
158
159 // note: the following two loops can be integrated in the previous two loops, but left
160 // separated for clarity in the PoC implementation.
161 for (j, L_j) in vec_Ls.iter_mut().enumerate().skip(1) {
162 let gamma_j = gamma.pow([j as u64]);
163 L_j.scalar_mul(&gamma_j);
164 g = g.add(L_j);
165 }
166 for (i, Q_i) in vec_Q.iter_mut().enumerate() {
167 let gamma_mut_i = gamma.pow([(mu * ccs.t + i) as u64]);
168 Q_i.scalar_mul(&gamma_mut_i);
169 g = g.add(Q_i);
170 }
171 g
172}
173
174#[cfg(test)]
175pub mod tests {
176 use super::*;
177
178 use ark_pallas::{Fr, Projective};
179 use ark_std::test_rng;
180 use ark_std::One;
181 use ark_std::UniformRand;
182 use ark_std::Zero;
183
184 use crate::ccs::tests::{get_test_ccs, get_test_z};
185 use crate::commitment::{pedersen::Pedersen, CommitmentScheme};
186 use crate::utils::multilinear_polynomial::tests::fix_last_variables;
187 use crate::utils::virtual_polynomial::eq_eval;
188
189 #[test]
190 fn test_compute_sum_Mz_over_boolean_hypercube() {
191 let ccs = get_test_ccs::<Fr>();
192 let z = get_test_z(3);
193 ccs.check_relation(&z).unwrap();
194 let z_mle = dense_vec_to_mle(ccs.s_prime, &z);
195
196 // check that evaluating over all the values x over the boolean hypercube, the result of
197 // the next for loop is equal to 0
198 for x in BooleanHypercube::new(ccs.s) {
199 let mut r = Fr::zero();
200 for i in 0..ccs.q {
201 let mut Sj_prod = Fr::one();
202 for j in ccs.S[i].clone() {
203 let M_j = matrix_to_mle(ccs.M[j].clone());
204 let sum_Mz = compute_sum_Mz(M_j, &z_mle, ccs.s_prime);
205 let sum_Mz_x = sum_Mz.evaluate(&x).unwrap();
206 Sj_prod *= sum_Mz_x;
207 }
208 r += Sj_prod * ccs.c[i];
209 }
210 assert_eq!(r, Fr::zero());
211 }
212 }
213
214 /// Given M(x,y) matrix and a random field element `r`, test that ~M(r,y) is is an s'-variable polynomial which
215 /// compresses every column j of the M(x,y) matrix by performing a random linear combination between the elements
216 /// of the column and the values eq_i(r) where i is the row of that element
217 ///
218 /// For example, for matrix M:
219 ///
220 /// [2, 3, 4, 4
221 /// 4, 4, 3, 2
222 /// 2, 8, 9, 2
223 /// 9, 4, 2, 0]
224 ///
225 /// The polynomial ~M(r,y) is a polynomial in F^2 which evaluates to the following values in the hypercube:
226 /// - M(00) = 2*eq_00(r) + 4*eq_10(r) + 2*eq_01(r) + 9*eq_11(r)
227 /// - M(10) = 3*eq_00(r) + 4*eq_10(r) + 8*eq_01(r) + 4*eq_11(r)
228 /// - M(01) = 4*eq_00(r) + 3*eq_10(r) + 9*eq_01(r) + 2*eq_11(r)
229 /// - M(11) = 4*eq_00(r) + 2*eq_10(r) + 2*eq_01(r) + 0*eq_11(r)
230 ///
231 /// This is used by HyperNova in LCCCS to perform a verifier-chosen random linear combination between the columns
232 /// of the matrix and the z vector. This technique is also used extensively in "An Algebraic Framework for
233 /// Universal and Updatable SNARKs".
234 #[test]
235 fn test_compute_M_r_y_compression() {
236 let mut rng = test_rng();
237
238 // s = 2, s' = 3
239 let ccs = get_test_ccs::<Fr>();
240
241 let M = ccs.M[0].clone().to_dense();
242 let M_mle = matrix_to_mle(ccs.M[0].clone());
243
244 // Fix the polynomial ~M(r,y)
245 let r: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
246 let M_r_y = fix_last_variables(&M_mle, &r);
247
248 // compute M_r_y the other way around
249 for j in 0..M[0].len() {
250 // Go over every column of M
251 let column_j: Vec<Fr> = M.clone().iter().map(|x| x[j]).collect();
252 // and perform the random lincomb between the elements of the column and eq_i(r)
253 let rlc = BooleanHypercube::new(ccs.s)
254 .enumerate()
255 .map(|(i, x)| column_j[i] * eq_eval(&x, &r).unwrap())
256 .fold(Fr::zero(), |acc, result| acc + result);
257
258 assert_eq!(M_r_y.evaluations[j], rlc);
259 }
260 }
261
262 #[test]
263 fn test_compute_sigmas_and_thetas() {
264 let ccs = get_test_ccs();
265 let z1 = get_test_z(3);
266 let z2 = get_test_z(4);
267 ccs.check_relation(&z1).unwrap();
268 ccs.check_relation(&z2).unwrap();
269
270 let mut rng = test_rng();
271 let gamma: Fr = Fr::rand(&mut rng);
272 let beta: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
273 let r_x_prime: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
274
275 // Initialize a multifolding object
276 let (pedersen_params, _) =
277 Pedersen::<Projective>::setup(&mut rng, ccs.n - ccs.l - 1).unwrap();
278 let (lcccs_instance, _) = ccs.to_lcccs(&mut rng, &pedersen_params, &z1).unwrap();
279
280 let sigmas_thetas =
281 compute_sigmas_and_thetas(&ccs, &[z1.clone()], &[z2.clone()], &r_x_prime);
282
283 let g = compute_g(
284 &ccs,
285 &[lcccs_instance.clone()],
286 &[z1.clone()],
287 &[z2.clone()],
288 gamma,
289 &beta,
290 );
291
292 // we expect g(r_x_prime) to be equal to:
293 // c = (sum gamma^j * e1 * sigma_j) + gamma^{t+1} * e2 * sum c_i * prod theta_j
294 // from compute_c
295 let expected_c = g.evaluate(&r_x_prime).unwrap();
296 let c = compute_c::<Fr>(
297 &ccs,
298 &sigmas_thetas,
299 gamma,
300 &beta,
301 &vec![lcccs_instance.r_x],
302 &r_x_prime,
303 );
304 assert_eq!(c, expected_c);
305 }
306
307 #[test]
308 fn test_compute_g() {
309 let ccs = get_test_ccs();
310 let z1 = get_test_z(3);
311 let z2 = get_test_z(4);
312 ccs.check_relation(&z1).unwrap();
313 ccs.check_relation(&z2).unwrap();
314
315 let mut rng = test_rng(); // TMP
316 let gamma: Fr = Fr::rand(&mut rng);
317 let beta: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
318
319 // Initialize a multifolding object
320 let (pedersen_params, _) =
321 Pedersen::<Projective>::setup(&mut rng, ccs.n - ccs.l - 1).unwrap();
322 let (lcccs_instance, _) = ccs.to_lcccs(&mut rng, &pedersen_params, &z1).unwrap();
323
324 let mut sum_v_j_gamma = Fr::zero();
325 for j in 0..lcccs_instance.v.len() {
326 let gamma_j = gamma.pow([j as u64]);
327 sum_v_j_gamma += lcccs_instance.v[j] * gamma_j;
328 }
329
330 // Compute g(x) with that r_x
331 let g = compute_g::<Projective>(
332 &ccs,
333 &[lcccs_instance.clone()],
334 &[z1.clone()],
335 &[z2.clone()],
336 gamma,
337 &beta,
338 );
339
340 // evaluate g(x) over x \in {0,1}^s
341 let mut g_on_bhc = Fr::zero();
342 for x in BooleanHypercube::new(ccs.s) {
343 g_on_bhc += g.evaluate(&x).unwrap();
344 }
345
346 // evaluate sum_{j \in [t]} (gamma^j * Lj(x)) over x \in {0,1}^s
347 let mut sum_Lj_on_bhc = Fr::zero();
348 let vec_L = lcccs_instance.compute_Ls(&ccs, &z1);
349 for x in BooleanHypercube::new(ccs.s) {
350 for (j, Lj) in vec_L.iter().enumerate() {
351 let gamma_j = gamma.pow([j as u64]);
352 sum_Lj_on_bhc += Lj.evaluate(&x).unwrap() * gamma_j;
353 }
354 }
355
356 // Q(x) over bhc is assumed to be zero, as checked in the test 'test_compute_Q'
357 assert_ne!(g_on_bhc, Fr::zero());
358
359 // evaluating g(x) over the boolean hypercube should give the same result as evaluating the
360 // sum of gamma^j * Lj(x) over the boolean hypercube
361 assert_eq!(g_on_bhc, sum_Lj_on_bhc);
362
363 // evaluating g(x) over the boolean hypercube should give the same result as evaluating the
364 // sum of gamma^j * v_j over j \in [t]
365 assert_eq!(g_on_bhc, sum_v_j_gamma);
366 }
367}