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::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::ccs::tests::{get_test_ccs, get_test_z};
171 use crate::commitment::{pedersen::Pedersen, CommitmentScheme};
172 use crate::folding::hypernova::lcccs::tests::compute_Ls;
173 use crate::utils::hypercube::BooleanHypercube;
174 use crate::utils::mle::matrix_to_dense_mle;
175 use crate::utils::multilinear_polynomial::tests::fix_last_variables;
176 use crate::utils::virtual_polynomial::eq_eval;
177
178 /// Given M(x,y) matrix and a random field element `r`, test that ~M(r,y) is is an s'-variable polynomial which
179 /// compresses every column j of the M(x,y) matrix by performing a random linear combination between the elements
180 /// of the column and the values eq_i(r) where i is the row of that element
181 ///
182 /// For example, for matrix M:
183 ///
184 /// [2, 3, 4, 4
185 /// 4, 4, 3, 2
186 /// 2, 8, 9, 2
187 /// 9, 4, 2, 0]
188 ///
189 /// The polynomial ~M(r,y) is a polynomial in F^2 which evaluates to the following values in the hypercube:
190 /// - M(00) = 2*eq_00(r) + 4*eq_10(r) + 2*eq_01(r) + 9*eq_11(r)
191 /// - M(10) = 3*eq_00(r) + 4*eq_10(r) + 8*eq_01(r) + 4*eq_11(r)
192 /// - M(01) = 4*eq_00(r) + 3*eq_10(r) + 9*eq_01(r) + 2*eq_11(r)
193 /// - M(11) = 4*eq_00(r) + 2*eq_10(r) + 2*eq_01(r) + 0*eq_11(r)
194 ///
195 /// This is used by HyperNova in LCCCS to perform a verifier-chosen random linear combination between the columns
196 /// of the matrix and the z vector. This technique is also used extensively in "An Algebraic Framework for
197 /// Universal and Updatable SNARKs".
198 #[test]
199 fn test_compute_M_r_y_compression() {
200 let mut rng = test_rng();
201
202 // s = 2, s' = 3
203 let ccs = get_test_ccs::<Fr>();
204
205 let M = ccs.M[0].clone().to_dense();
206 let M_mle = matrix_to_dense_mle(ccs.M[0].clone());
207
208 // Fix the polynomial ~M(r,y)
209 let r: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
210 let M_r_y = fix_last_variables(&M_mle, &r);
211
212 // compute M_r_y the other way around
213 for j in 0..M[0].len() {
214 // Go over every column of M
215 let column_j: Vec<Fr> = M.clone().iter().map(|x| x[j]).collect();
216 // and perform the random lincomb between the elements of the column and eq_i(r)
217 let rlc = BooleanHypercube::new(ccs.s)
218 .enumerate()
219 .map(|(i, x)| column_j[i] * eq_eval(&x, &r).unwrap())
220 .fold(Fr::zero(), |acc, result| acc + result);
221
222 assert_eq!(M_r_y.evaluations[j], rlc);
223 }
224 }
225
226 #[test]
227 fn test_compute_sigmas_thetas() {
228 let ccs = get_test_ccs();
229 let z1 = get_test_z(3);
230 let z2 = get_test_z(4);
231 ccs.check_relation(&z1).unwrap();
232 ccs.check_relation(&z2).unwrap();
233
234 let mut rng = test_rng();
235 let gamma: Fr = Fr::rand(&mut rng);
236 let beta: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
237 let r_x_prime: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
238
239 // Initialize a multifolding object
240 let (pedersen_params, _) =
241 Pedersen::<Projective>::setup(&mut rng, ccs.n - ccs.l - 1).unwrap();
242 let (lcccs_instance, _) = ccs
243 .to_lcccs::<_, _, Pedersen<Projective>>(&mut rng, &pedersen_params, &z1)
244 .unwrap();
245
246 let sigmas_thetas =
247 compute_sigmas_thetas(&ccs, &[z1.clone()], &[z2.clone()], &r_x_prime).unwrap();
248
249 let g = compute_g(
250 &ccs,
251 &[lcccs_instance.clone()],
252 &[z1.clone()],
253 &[z2.clone()],
254 gamma,
255 &beta,
256 )
257 .unwrap();
258
259 // we expect g(r_x_prime) to be equal to:
260 // c = (sum gamma^j * e1 * sigma_j) + gamma^{t+1} * e2 * sum c_i * prod theta_j
261 // from compute_c
262 let expected_c = g.evaluate(&r_x_prime).unwrap();
263 let c = compute_c::<Fr>(
264 &ccs,
265 &sigmas_thetas,
266 gamma,
267 &beta,
268 &vec![lcccs_instance.r_x],
269 &r_x_prime,
270 )
271 .unwrap();
272 assert_eq!(c, expected_c);
273 }
274
275 #[test]
276 fn test_compute_g() {
277 let mut rng = test_rng();
278
279 // generate test CCS & z vectors
280 let ccs: CCS<Fr> = get_test_ccs();
281 let z1 = get_test_z(3);
282 let z2 = get_test_z(4);
283 ccs.check_relation(&z1).unwrap();
284 ccs.check_relation(&z2).unwrap();
285
286 let gamma: Fr = Fr::rand(&mut rng);
287 let beta: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
288
289 // Initialize a multifolding object
290 let (pedersen_params, _) =
291 Pedersen::<Projective>::setup(&mut rng, ccs.n - ccs.l - 1).unwrap();
292 let (lcccs_instance, _) = ccs
293 .to_lcccs::<_, _, Pedersen<Projective>>(&mut rng, &pedersen_params, &z1)
294 .unwrap();
295
296 // Compute g(x) with that r_x
297 let g = compute_g::<Projective>(
298 &ccs,
299 &[lcccs_instance.clone()],
300 &[z1.clone()],
301 &[z2.clone()],
302 gamma,
303 &beta,
304 )
305 .unwrap();
306
307 // evaluate g(x) over x \in {0,1}^s
308 let mut g_on_bhc = Fr::zero();
309 for x in BooleanHypercube::new(ccs.s) {
310 g_on_bhc += g.evaluate(&x).unwrap();
311 }
312
313 // Q(x) over bhc is assumed to be zero, as checked in the test 'test_compute_Q'
314 assert_ne!(g_on_bhc, Fr::zero());
315
316 let mut sum_v_j_gamma = Fr::zero();
317 for j in 0..lcccs_instance.v.len() {
318 let gamma_j = gamma.pow([j as u64]);
319 sum_v_j_gamma += lcccs_instance.v[j] * gamma_j;
320 }
321
322 // evaluating g(x) over the boolean hypercube should give the same result as evaluating the
323 // sum of gamma^j * v_j over j \in [t]
324 assert_eq!(g_on_bhc, sum_v_j_gamma);
325
326 // evaluate sum_{j \in [t]} (gamma^j * Lj(x)) over x \in {0,1}^s
327 let mut sum_Lj_on_bhc = Fr::zero();
328 let vec_L = compute_Ls(&ccs, &lcccs_instance, &z1);
329 for x in BooleanHypercube::new(ccs.s) {
330 for (j, Lj) in vec_L.iter().enumerate() {
331 let gamma_j = gamma.pow([j as u64]);
332 sum_Lj_on_bhc += Lj.evaluate(&x).unwrap() * gamma_j;
333 }
334 }
335
336 // evaluating g(x) over the boolean hypercube should give the same result as evaluating the
337 // sum of gamma^j * Lj(x) over the boolean hypercube
338 assert_eq!(g_on_bhc, sum_Lj_on_bhc);
339 }
340}