sonobe/folding-schemes/src/folding/hypernova/circuit.rs
folding-schemes/src/folding/hypernova/circuit.rsRaw
1// hypernova nimfs verifier circuit
2// see section 5 in https://eprint.iacr.org/2023/573.pdf
3
4use crate::{ccs::CCS, folding::circuits::utils::EqEvalGadget};
5use ark_ec::CurveGroup;
6use ark_r1cs_std::{
7 alloc::AllocVar,
8 fields::{fp::FpVar, FieldVar},
9 ToBitsGadget,
10};
11use ark_relations::r1cs::{ConstraintSystemRef, SynthesisError};
12use ark_std::Zero;
13use std::marker::PhantomData;
14
15/// Gadget to compute $\sum_{j \in [t]} \gamma^{j} \cdot e_1 \cdot \sigma_j + \gamma^{t+1} \cdot e_2 \cdot \sum_{i=1}^{q} c_i * \prod_{j \in S_i} \theta_j$.
16/// This is the sum computed by the verifier and laid out in section 5, step 5 of "A multi-folding scheme for CCS".
17pub struct ComputeCFromSigmasAndThetasGadget<C: CurveGroup> {
18 _c: PhantomData<C>,
19}
20
21impl<C: CurveGroup> ComputeCFromSigmasAndThetasGadget<C> {
22 /// Computes the sum $\sum_{j}^{j + n} \gamma^{j} \cdot eq_eval \cdot \sigma_{j}$, where $n$ is the length of the `sigmas` vector
23 /// It corresponds to the first term of the sum that $\mathcal{V}$ has to compute at section 5, step 5 of "A multi-folding scheme for CCS".
24 ///
25 /// # Arguments
26 /// - `sigmas`: vector of $\sigma_j$ values
27 /// - `eq_eval`: the value of $\tilde{eq}(x_j, x^{\prime})$
28 /// - `gamma`: value $\gamma$
29 /// - `j`: the power at which we start to compute $\gamma^{j}$. This is needed in the context of multifolding.
30 ///
31 /// # Notes
32 /// In the context of multifolding, `j` corresponds to `ccs.t` in `compute_c_from_sigmas_and_thetas`
33 fn sum_muls_gamma_pows_eq_sigma(
34 gamma: FpVar<C::ScalarField>,
35 eq_eval: FpVar<C::ScalarField>,
36 sigmas: Vec<FpVar<C::ScalarField>>,
37 j: FpVar<C::ScalarField>,
38 ) -> Result<FpVar<C::ScalarField>, SynthesisError> {
39 let mut result = FpVar::<C::ScalarField>::zero();
40 let mut gamma_pow = gamma.pow_le(&j.to_bits_le()?)?;
41 for sigma in sigmas {
42 result += gamma_pow.clone() * eq_eval.clone() * sigma;
43 gamma_pow *= gamma.clone();
44 }
45 Ok(result)
46 }
47
48 /// Computes $\sum_{i=1}^{q} c_i * \prod_{j \in S_i} theta_j$
49 ///
50 /// # Arguments
51 /// - `c_i`: vector of $c_i$ values
52 /// - `thetas`: vector of pre-processed $\thetas[j]$ values corresponding to a particular `ccs.S[i]`
53 ///
54 /// # Notes
55 /// This is a part of the second term of the sum that $\mathcal{V}$ has to compute at section 5, step 5 of "A multi-folding scheme for CCS".
56 /// The first term is computed by `SumMulsGammaPowsEqSigmaGadget::sum_muls_gamma_pows_eq_sigma`.
57 /// This is a doct product between a vector of c_i values and a vector of pre-processed $\theta_j$ values, where $j$ is a value from $S_i$.
58 /// Hence, this requires some pre-processing of the $\theta_j$ values, before running this gadget.
59 fn sum_ci_mul_prod_thetaj(
60 c_i: Vec<FpVar<C::ScalarField>>,
61 thetas: Vec<Vec<FpVar<C::ScalarField>>>,
62 ) -> Result<FpVar<C::ScalarField>, SynthesisError> {
63 let mut result = FpVar::<C::ScalarField>::zero();
64 for (i, c_i) in c_i.iter().enumerate() {
65 let prod = &thetas[i].iter().fold(FpVar::one(), |acc, e| acc * e);
66 result += c_i * prod;
67 }
68 Ok(result)
69 }
70
71 /// Computes the sum that the verifier has to compute at section 5, step 5 of "A multi-folding scheme for CCS".
72 ///
73 /// # Arguments
74 /// - `cs`: constraint system
75 /// - `ccs`: the CCS instance
76 /// - `vec_sigmas`: vector of $\sigma_j$ values
77 /// - `vec_thetas`: vector of $\theta_j$ values
78 /// - `gamma`: value $\gamma$
79 /// - `beta`: vector of $\beta_j$ values
80 /// - `vec_r_x`: vector of $r_{x_j}$ values
81 /// - `vec_r_x_prime`: vector of $r_{x_j}^{\prime}$ values
82 ///
83 /// # Notes
84 /// Arguments to this function are *almost* the same as the arguments to `compute_c_from_sigmas_and_thetas` in `utils.rs`.
85 #[allow(clippy::too_many_arguments)]
86 pub fn compute_c_from_sigmas_and_thetas(
87 cs: ConstraintSystemRef<C::ScalarField>,
88 ccs: &CCS<C>,
89 vec_sigmas: Vec<Vec<FpVar<C::ScalarField>>>,
90 vec_thetas: Vec<Vec<FpVar<C::ScalarField>>>,
91 gamma: FpVar<C::ScalarField>,
92 beta: Vec<FpVar<C::ScalarField>>,
93 vec_r_x: Vec<Vec<FpVar<C::ScalarField>>>,
94 vec_r_x_prime: Vec<FpVar<C::ScalarField>>,
95 ) -> Result<FpVar<C::ScalarField>, SynthesisError> {
96 let mut c =
97 FpVar::<C::ScalarField>::new_witness(cs.clone(), || Ok(C::ScalarField::zero()))?;
98 let t = FpVar::<C::ScalarField>::new_witness(cs.clone(), || {
99 Ok(C::ScalarField::from(ccs.t as u64))
100 })?;
101
102 let mut e_lcccs = Vec::new();
103 for r_x in vec_r_x.iter() {
104 let e_1 = EqEvalGadget::eq_eval(r_x.to_vec(), vec_r_x_prime.to_vec())?;
105 e_lcccs.push(e_1);
106 }
107
108 for (i, sigmas) in vec_sigmas.iter().enumerate() {
109 let i_var = FpVar::<C::ScalarField>::new_witness(cs.clone(), || {
110 Ok(C::ScalarField::from(i as u64))
111 })?;
112 let pow = i_var * t.clone();
113 c += Self::sum_muls_gamma_pows_eq_sigma(
114 gamma.clone(),
115 e_lcccs[i].clone(),
116 sigmas.to_vec(),
117 pow,
118 )?;
119 }
120
121 let mu = FpVar::<C::ScalarField>::new_witness(cs.clone(), || {
122 Ok(C::ScalarField::from(vec_sigmas.len() as u64))
123 })?;
124 let e_2 = EqEvalGadget::eq_eval(beta, vec_r_x_prime)?;
125 for (k, thetas) in vec_thetas.iter().enumerate() {
126 // get prepared thetas. only step different from original `compute_c_from_sigmas_and_thetas`
127 let mut prepared_thetas = Vec::new();
128 for i in 0..ccs.q {
129 let prepared: Vec<FpVar<C::ScalarField>> =
130 ccs.S[i].iter().map(|j| thetas[*j].clone()).collect();
131 prepared_thetas.push(prepared.to_vec());
132 }
133
134 let c_i = Vec::<FpVar<C::ScalarField>>::new_witness(cs.clone(), || Ok(ccs.c.clone()))
135 .unwrap();
136 let lhs = Self::sum_ci_mul_prod_thetaj(c_i.clone(), prepared_thetas.clone())?;
137
138 // compute gamma^(t+1)
139 let pow = mu.clone() * t.clone()
140 + FpVar::<C::ScalarField>::new_witness(cs.clone(), || {
141 Ok(C::ScalarField::from(k as u64))
142 })?;
143 let gamma_t1 = gamma.pow_le(&pow.to_bits_le()?)?;
144
145 c += gamma_t1.clone() * e_2.clone() * lhs.clone();
146 }
147
148 Ok(c)
149 }
150}
151
152#[cfg(test)]
153mod tests {
154 use super::ComputeCFromSigmasAndThetasGadget;
155 use crate::{
156 ccs::{
157 tests::{get_test_ccs, get_test_z},
158 CCS,
159 },
160 commitment::{pedersen::Pedersen, CommitmentScheme},
161 folding::hypernova::utils::{
162 compute_c_from_sigmas_and_thetas, compute_sigmas_and_thetas, sum_ci_mul_prod_thetaj,
163 sum_muls_gamma_pows_eq_sigma,
164 },
165 utils::virtual_polynomial::eq_eval,
166 };
167 use ark_pallas::{Fr, Projective};
168 use ark_r1cs_std::{alloc::AllocVar, fields::fp::FpVar, R1CSVar};
169 use ark_relations::r1cs::ConstraintSystem;
170 use ark_std::{test_rng, UniformRand};
171
172 #[test]
173 pub fn test_sum_muls_gamma_pow_eq_sigma_gadget() {
174 let mut rng = test_rng();
175 let ccs: CCS<Projective> = get_test_ccs();
176 let z1 = get_test_z(3);
177 let z2 = get_test_z(4);
178
179 let gamma: Fr = Fr::rand(&mut rng);
180 let r_x_prime: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
181
182 // Initialize a multifolding object
183 let (pedersen_params, _) =
184 Pedersen::<Projective>::setup(&mut rng, ccs.n - ccs.l - 1).unwrap();
185 let (lcccs_instance, _) = ccs.to_lcccs(&mut rng, &pedersen_params, &z1).unwrap();
186 let sigmas_thetas =
187 compute_sigmas_and_thetas(&ccs, &[z1.clone()], &[z2.clone()], &r_x_prime);
188
189 let mut e_lcccs = Vec::new();
190 for r_x in &vec![lcccs_instance.r_x] {
191 e_lcccs.push(eq_eval(r_x, &r_x_prime).unwrap());
192 }
193
194 // Initialize cs and gamma
195 let cs = ConstraintSystem::<Fr>::new_ref();
196 let gamma_var = FpVar::<Fr>::new_witness(cs.clone(), || Ok(gamma)).unwrap();
197
198 for (i, sigmas) in sigmas_thetas.0.iter().enumerate() {
199 let expected =
200 sum_muls_gamma_pows_eq_sigma(gamma, e_lcccs[i], sigmas, (i * ccs.t) as u64);
201 let sigmas_var =
202 Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(sigmas.clone())).unwrap();
203 let eq_var = FpVar::<Fr>::new_witness(cs.clone(), || Ok(e_lcccs[i])).unwrap();
204 let pow =
205 FpVar::<Fr>::new_witness(cs.clone(), || Ok(Fr::from((i * ccs.t) as u64))).unwrap();
206 let computed =
207 ComputeCFromSigmasAndThetasGadget::<Projective>::sum_muls_gamma_pows_eq_sigma(
208 gamma_var.clone(),
209 eq_var,
210 sigmas_var,
211 pow,
212 )
213 .unwrap();
214 assert_eq!(expected, computed.value().unwrap());
215 }
216 }
217
218 #[test]
219 pub fn test_sum_ci_mul_prod_thetaj_gadget() {
220 let mut rng = test_rng();
221 let ccs: CCS<Projective> = get_test_ccs();
222 let z1 = get_test_z(3);
223 let z2 = get_test_z(4);
224
225 let r_x_prime: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
226
227 // Initialize a multifolding object
228 let (pedersen_params, _) =
229 Pedersen::<Projective>::setup(&mut rng, ccs.n - ccs.l - 1).unwrap();
230 let (lcccs_instance, _) = ccs.to_lcccs(&mut rng, &pedersen_params, &z1).unwrap();
231 let sigmas_thetas =
232 compute_sigmas_and_thetas(&ccs, &[z1.clone()], &[z2.clone()], &r_x_prime);
233
234 let mut e_lcccs = Vec::new();
235 for r_x in &vec![lcccs_instance.r_x] {
236 e_lcccs.push(eq_eval(r_x, &r_x_prime).unwrap());
237 }
238
239 // Initialize cs
240 let cs = ConstraintSystem::<Fr>::new_ref();
241 let vec_thetas = sigmas_thetas.1;
242 for thetas in vec_thetas.iter() {
243 // sum c_i * prod theta_j
244 let expected = sum_ci_mul_prod_thetaj(&ccs, thetas); // from `compute_c_from_sigmas_and_thetas`
245 let mut prepared_thetas = Vec::new();
246 for i in 0..ccs.q {
247 let prepared: Vec<Fr> = ccs.S[i].iter().map(|j| thetas[*j]).collect();
248 prepared_thetas
249 .push(Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(prepared)).unwrap());
250 }
251 let computed = ComputeCFromSigmasAndThetasGadget::<Projective>::sum_ci_mul_prod_thetaj(
252 Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(ccs.c.clone())).unwrap(),
253 prepared_thetas,
254 )
255 .unwrap();
256 assert_eq!(expected, computed.value().unwrap());
257 }
258 }
259
260 #[test]
261 pub fn test_compute_c_from_sigmas_and_thetas_gadget() {
262 let ccs: CCS<Projective> = get_test_ccs();
263 let z1 = get_test_z(3);
264 let z2 = get_test_z(4);
265
266 let mut rng = test_rng();
267 let gamma: Fr = Fr::rand(&mut rng);
268 let beta: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
269 let r_x_prime: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
270
271 // Initialize a multifolding object
272 let (pedersen_params, _) =
273 Pedersen::<Projective>::setup(&mut rng, ccs.n - ccs.l - 1).unwrap();
274 let (lcccs_instance, _) = ccs.to_lcccs(&mut rng, &pedersen_params, &z1).unwrap();
275 let sigmas_thetas =
276 compute_sigmas_and_thetas(&ccs, &[z1.clone()], &[z2.clone()], &r_x_prime);
277
278 let expected_c = compute_c_from_sigmas_and_thetas(
279 &ccs,
280 &sigmas_thetas,
281 gamma,
282 &beta,
283 &vec![lcccs_instance.r_x.clone()],
284 &r_x_prime,
285 );
286
287 let cs = ConstraintSystem::<Fr>::new_ref();
288 let mut vec_sigmas = Vec::new();
289 let mut vec_thetas = Vec::new();
290 for sigmas in sigmas_thetas.0 {
291 vec_sigmas
292 .push(Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(sigmas.clone())).unwrap());
293 }
294 for thetas in sigmas_thetas.1 {
295 vec_thetas
296 .push(Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(thetas.clone())).unwrap());
297 }
298 let vec_r_x =
299 vec![
300 Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(lcccs_instance.r_x.clone()))
301 .unwrap(),
302 ];
303 let vec_r_x_prime =
304 Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(r_x_prime.clone())).unwrap();
305 let gamma_var = FpVar::<Fr>::new_witness(cs.clone(), || Ok(gamma)).unwrap();
306 let beta_var = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(beta.clone())).unwrap();
307 let computed_c = ComputeCFromSigmasAndThetasGadget::compute_c_from_sigmas_and_thetas(
308 cs,
309 &ccs,
310 vec_sigmas,
311 vec_thetas,
312 gamma_var,
313 beta_var,
314 vec_r_x,
315 vec_r_x_prime,
316 )
317 .unwrap();
318
319 assert_eq!(expected_c, computed_c.value().unwrap());
320 }
321}