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