sonobe/src/folding/hypernova/circuit.rs
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 folding::hypernova::utils::{
161 compute_c_from_sigmas_and_thetas, compute_sigmas_and_thetas, sum_ci_mul_prod_thetaj,
162 sum_muls_gamma_pows_eq_sigma,
163 },
164 pedersen::Pedersen,
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 = Pedersen::new_params(&mut rng, ccs.n - ccs.l - 1);
184 let (lcccs_instance, _) = ccs.to_lcccs(&mut rng, &pedersen_params, &z1).unwrap();
185 let sigmas_thetas =
186 compute_sigmas_and_thetas(&ccs, &[z1.clone()], &[z2.clone()], &r_x_prime);
187
188 let mut e_lcccs = Vec::new();
189 for r_x in &vec![lcccs_instance.r_x] {
190 e_lcccs.push(eq_eval(r_x, &r_x_prime).unwrap());
191 }
192
193 // Initialize cs and gamma
194 let cs = ConstraintSystem::<Fr>::new_ref();
195 let gamma_var = FpVar::<Fr>::new_witness(cs.clone(), || Ok(gamma)).unwrap();
196
197 for (i, sigmas) in sigmas_thetas.0.iter().enumerate() {
198 let expected =
199 sum_muls_gamma_pows_eq_sigma(gamma, e_lcccs[i], sigmas, (i * ccs.t) as u64);
200 let sigmas_var =
201 Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(sigmas.clone())).unwrap();
202 let eq_var = FpVar::<Fr>::new_witness(cs.clone(), || Ok(e_lcccs[i])).unwrap();
203 let pow =
204 FpVar::<Fr>::new_witness(cs.clone(), || Ok(Fr::from((i * ccs.t) as u64))).unwrap();
205 let computed =
206 ComputeCFromSigmasAndThetasGadget::<Projective>::sum_muls_gamma_pows_eq_sigma(
207 gamma_var.clone(),
208 eq_var,
209 sigmas_var,
210 pow,
211 )
212 .unwrap();
213 assert_eq!(expected, computed.value().unwrap());
214 }
215 }
216
217 #[test]
218 pub fn test_sum_ci_mul_prod_thetaj_gadget() {
219 let mut rng = test_rng();
220 let ccs: CCS<Projective> = get_test_ccs();
221 let z1 = get_test_z(3);
222 let z2 = get_test_z(4);
223
224 let r_x_prime: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
225
226 // Initialize a multifolding object
227 let pedersen_params = Pedersen::new_params(&mut rng, ccs.n - ccs.l - 1);
228 let (lcccs_instance, _) = ccs.to_lcccs(&mut rng, &pedersen_params, &z1).unwrap();
229 let sigmas_thetas =
230 compute_sigmas_and_thetas(&ccs, &[z1.clone()], &[z2.clone()], &r_x_prime);
231
232 let mut e_lcccs = Vec::new();
233 for r_x in &vec![lcccs_instance.r_x] {
234 e_lcccs.push(eq_eval(r_x, &r_x_prime).unwrap());
235 }
236
237 // Initialize cs
238 let cs = ConstraintSystem::<Fr>::new_ref();
239 let vec_thetas = sigmas_thetas.1;
240 for (_, thetas) in vec_thetas.iter().enumerate() {
241 // sum c_i * prod theta_j
242 let expected = sum_ci_mul_prod_thetaj(&ccs, thetas); // from `compute_c_from_sigmas_and_thetas`
243 let mut prepared_thetas = Vec::new();
244 for i in 0..ccs.q {
245 let prepared: Vec<Fr> = ccs.S[i].iter().map(|j| thetas[*j]).collect();
246 prepared_thetas
247 .push(Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(prepared)).unwrap());
248 }
249 let computed = ComputeCFromSigmasAndThetasGadget::<Projective>::sum_ci_mul_prod_thetaj(
250 Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(ccs.c.clone())).unwrap(),
251 prepared_thetas,
252 )
253 .unwrap();
254 assert_eq!(expected, computed.value().unwrap());
255 }
256 }
257
258 #[test]
259 pub fn test_compute_c_from_sigmas_and_thetas_gadget() {
260 let ccs: CCS<Projective> = get_test_ccs();
261 let z1 = get_test_z(3);
262 let z2 = get_test_z(4);
263
264 let mut rng = test_rng();
265 let gamma: Fr = Fr::rand(&mut rng);
266 let beta: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
267 let r_x_prime: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
268
269 // Initialize a multifolding object
270 let pedersen_params = Pedersen::new_params(&mut rng, ccs.n - ccs.l - 1);
271 let (lcccs_instance, _) = ccs.to_lcccs(&mut rng, &pedersen_params, &z1).unwrap();
272 let sigmas_thetas =
273 compute_sigmas_and_thetas(&ccs, &[z1.clone()], &[z2.clone()], &r_x_prime);
274
275 let expected_c = compute_c_from_sigmas_and_thetas(
276 &ccs,
277 &sigmas_thetas,
278 gamma,
279 &beta,
280 &vec![lcccs_instance.r_x.clone()],
281 &r_x_prime,
282 );
283
284 let cs = ConstraintSystem::<Fr>::new_ref();
285 let mut vec_sigmas = Vec::new();
286 let mut vec_thetas = Vec::new();
287 for sigmas in sigmas_thetas.0 {
288 vec_sigmas
289 .push(Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(sigmas.clone())).unwrap());
290 }
291 for thetas in sigmas_thetas.1 {
292 vec_thetas
293 .push(Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(thetas.clone())).unwrap());
294 }
295 let vec_r_x =
296 vec![
297 Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(lcccs_instance.r_x.clone()))
298 .unwrap(),
299 ];
300 let vec_r_x_prime =
301 Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(r_x_prime.clone())).unwrap();
302 let gamma_var = FpVar::<Fr>::new_witness(cs.clone(), || Ok(gamma)).unwrap();
303 let beta_var = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(beta.clone())).unwrap();
304 let computed_c = ComputeCFromSigmasAndThetasGadget::compute_c_from_sigmas_and_thetas(
305 cs,
306 &ccs,
307 vec_sigmas,
308 vec_thetas,
309 gamma_var,
310 beta_var,
311 vec_r_x,
312 vec_r_x_prime,
313 )
314 .unwrap();
315
316 assert_eq!(expected_c, computed_c.value().unwrap());
317 }
318}