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