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.to_lcccs(&mut rng, &pedersen_params, &z1).unwrap();
243
244 let sigmas_thetas =
245 compute_sigmas_thetas(&ccs, &[z1.clone()], &[z2.clone()], &r_x_prime).unwrap();
246
247 let g = compute_g(
248 &ccs,
249 &[lcccs_instance.clone()],
250 &[z1.clone()],
251 &[z2.clone()],
252 gamma,
253 &beta,
254 )
255 .unwrap();
256
257 // we expect g(r_x_prime) to be equal to:
258 // c = (sum gamma^j * e1 * sigma_j) + gamma^{t+1} * e2 * sum c_i * prod theta_j
259 // from compute_c
260 let expected_c = g.evaluate(&r_x_prime).unwrap();
261 let c = compute_c::<Fr>(
262 &ccs,
263 &sigmas_thetas,
264 gamma,
265 &beta,
266 &vec![lcccs_instance.r_x],
267 &r_x_prime,
268 )
269 .unwrap();
270 assert_eq!(c, expected_c);
271 }
272
273 #[test]
274 fn test_compute_g() {
275 let mut rng = test_rng();
276
277 // generate test CCS & z vectors
278 let ccs: CCS<Fr> = get_test_ccs();
279 let z1 = get_test_z(3);
280 let z2 = get_test_z(4);
281 ccs.check_relation(&z1).unwrap();
282 ccs.check_relation(&z2).unwrap();
283
284 let gamma: Fr = Fr::rand(&mut rng);
285 let beta: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
286
287 // Initialize a multifolding object
288 let (pedersen_params, _) =
289 Pedersen::<Projective>::setup(&mut rng, ccs.n - ccs.l - 1).unwrap();
290 let (lcccs_instance, _) = ccs.to_lcccs(&mut rng, &pedersen_params, &z1).unwrap();
291
292 // Compute g(x) with that r_x
293 let g = compute_g::<Projective>(
294 &ccs,
295 &[lcccs_instance.clone()],
296 &[z1.clone()],
297 &[z2.clone()],
298 gamma,
299 &beta,
300 )
301 .unwrap();
302
303 // evaluate g(x) over x \in {0,1}^s
304 let mut g_on_bhc = Fr::zero();
305 for x in BooleanHypercube::new(ccs.s) {
306 g_on_bhc += g.evaluate(&x).unwrap();
307 }
308
309 // Q(x) over bhc is assumed to be zero, as checked in the test 'test_compute_Q'
310 assert_ne!(g_on_bhc, Fr::zero());
311
312 let mut sum_v_j_gamma = Fr::zero();
313 for j in 0..lcccs_instance.v.len() {
314 let gamma_j = gamma.pow([j as u64]);
315 sum_v_j_gamma += lcccs_instance.v[j] * gamma_j;
316 }
317
318 // evaluating g(x) over the boolean hypercube should give the same result as evaluating the
319 // sum of gamma^j * v_j over j \in [t]
320 assert_eq!(g_on_bhc, sum_v_j_gamma);
321
322 // evaluate sum_{j \in [t]} (gamma^j * Lj(x)) over x \in {0,1}^s
323 let mut sum_Lj_on_bhc = Fr::zero();
324 let vec_L = compute_Ls(&ccs, &lcccs_instance, &z1);
325 for x in BooleanHypercube::new(ccs.s) {
326 for (j, Lj) in vec_L.iter().enumerate() {
327 let gamma_j = gamma.pow([j as u64]);
328 sum_Lj_on_bhc += Lj.evaluate(&x).unwrap() * gamma_j;
329 }
330 }
331
332 // evaluating g(x) over the boolean hypercube should give the same result as evaluating the
333 // sum of gamma^j * Lj(x) over the boolean hypercube
334 assert_eq!(g_on_bhc, sum_Lj_on_bhc);
335 }
336}