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