sonobe/folding-schemes/src/folding/nova/zk.rs
folding-schemes/src/folding/nova/zk.rsRaw
1/// Implements Nova's zero-knowledge layer, as described in https://eprint.iacr.org/2023/573.pdf.
2///
3/// Remark: this zk layer implementation only covers a subset of the use cases:
4///
5/// We identify 3 interesting places to use the nova zk-layer: one before all the folding pipeline
6/// (Use-case-1), one at the end of the folding pipeline right before the final Decider SNARK
7/// proof (Use-case-2), and a third one for cases where compressed SNARK proofs are not needed, and
8/// just IVC proofs (bigger than SNARK proofs) suffice (Use-case-3):
9///
10/// * Use-case-1: at the beginning of the folding pipeline, right when the user has their original
11/// instance prior to be folded into the running instance, the user can fold it with the
12/// random-satisfying-instance to then have a blinded instance that can be sent to a server that
13/// will fold it with the running instance.
14/// --> In this one, the user could externalize all the IVC folding and also the Decider
15/// final proof generation to a server.
16/// * Use-case-2: at the end of all the IVC folding steps (after n iterations of nova.prove_step),
17/// to 'blind' the IVC proof so then it can be sent to a server that will generate the final
18/// decider SNARK proof.
19/// --> In this one, the user could externalize the Decider final proof generation to a
20/// server.
21/// * Use-case-3: the user does not care about the Decider (final compressed SNARK proof), and
22/// wants to generate a zk-proof of the IVC state to an IVC verifier (without any SNARK proof
23/// involved). In this use-case, the zk is only added at the last IVCProof. Note that this proof
24/// will be much bigger and expensive to verify than a Decider SNARK proof.
25///
26/// The current implementation covers the Use-case-3.
27/// Use-case-1 can be achieved directly by a simpler version of the zk IVC scheme skipping steps
28/// and implemented directly at the app level by folding the original instance with a randomized
29/// instance (steps 2,3,4 from section D.4 of the [HyperNova](https://eprint.iacr.org/2023/573.pdf)
30/// paper).
31/// And the Use-case-2 would require a modified version of the Decider circuits.
32///
33use ark_ff::PrimeField;
34use ark_std::{One, Zero};
35
36use crate::{
37 arith::{r1cs::R1CS, Arith, ArithSampler},
38 folding::traits::CommittedInstanceOps,
39 RngCore,
40};
41use ark_crypto_primitives::sponge::{
42 poseidon::{PoseidonConfig, PoseidonSponge},
43 Absorb, CryptographicSponge,
44};
45use ark_ec::{CurveGroup, Group};
46use ark_r1cs_std::{
47 groups::{CurveVar, GroupOpsBounds},
48 ToConstraintFieldGadget,
49};
50
51use crate::{commitment::CommitmentScheme, folding::circuits::CF2, frontend::FCircuit, Error};
52
53use super::{
54 nifs::{nova::NIFS, NIFSTrait},
55 CommittedInstance, Nova, Witness,
56};
57
58pub struct RandomizedIVCProof<C1: CurveGroup, C2: CurveGroup> {
59 pub U_i: CommittedInstance<C1>,
60 pub u_i: CommittedInstance<C1>,
61 pub U_r: CommittedInstance<C1>,
62 pub pi: C1, // proof = cmT
63 pub pi_prime: C1, // proof' = cmT'
64 pub W_i_prime: Witness<C1>,
65 pub cf_U_i: CommittedInstance<C2>,
66 pub cf_W_i: Witness<C2>,
67}
68
69impl<C1: CurveGroup, C2: CurveGroup> RandomizedIVCProof<C1, C2>
70where
71 <C1 as Group>::ScalarField: Absorb,
72 <C1 as CurveGroup>::BaseField: PrimeField,
73{
74 /// Compute a zero-knowledge proof of a Nova IVC proof
75 /// It implements the prover of appendix D.4.in https://eprint.iacr.org/2023/573.pdf
76 /// For further details on why folding is hiding, see lemma 9
77 pub fn new<
78 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
79 GC2: CurveVar<C2, CF2<C2>>,
80 FC: FCircuit<C1::ScalarField>,
81 CS1: CommitmentScheme<C1, true>,
82 CS2: CommitmentScheme<C2, true>,
83 >(
84 nova: &Nova<C1, GC1, C2, GC2, FC, CS1, CS2, true>,
85 mut rng: impl RngCore,
86 ) -> Result<RandomizedIVCProof<C1, C2>, Error>
87 where
88 <C1 as Group>::ScalarField: Absorb,
89 <C2 as Group>::ScalarField: Absorb,
90 <C2 as Group>::ScalarField: PrimeField,
91 <C2 as CurveGroup>::BaseField: PrimeField,
92 <C2 as CurveGroup>::BaseField: Absorb,
93 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
94 GC2: ToConstraintFieldGadget<<C2 as CurveGroup>::BaseField>,
95 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
96 {
97 let mut transcript = PoseidonSponge::<C1::ScalarField>::new(&nova.poseidon_config);
98
99 // I. Compute proof for 'regular' instances
100 // 1. Fold the instance-witness pairs (U_i, W_i) with (u_i, w_i)
101 let (W_f, U_f, cmT, _) = NIFS::<C1, CS1, PoseidonSponge<C1::ScalarField>, true>::prove(
102 &nova.cs_pp,
103 &nova.r1cs,
104 &mut transcript,
105 nova.pp_hash,
106 &nova.w_i,
107 &nova.u_i,
108 &nova.W_i,
109 &nova.U_i,
110 )?;
111
112 // 2. Sample a satisfying relaxed R1CS instance-witness pair (W_r, U_r)
113 let (W_r, U_r) = nova
114 .r1cs
115 .sample_witness_instance::<CS1>(&nova.cs_pp, &mut rng)?;
116
117 // 3. Fold the instance-witness pair (U_f, W_f) with (U_r, W_r)
118 let (W_i_prime, _, cmT_i_prime, _) =
119 NIFS::<C1, CS1, PoseidonSponge<C1::ScalarField>, true>::prove(
120 &nova.cs_pp,
121 &nova.r1cs,
122 &mut transcript,
123 nova.pp_hash,
124 &W_f,
125 &U_f,
126 &W_r,
127 &U_r,
128 )?;
129
130 Ok(RandomizedIVCProof {
131 U_i: nova.U_i.clone(),
132 u_i: nova.u_i.clone(),
133 U_r,
134 pi: cmT,
135 pi_prime: cmT_i_prime,
136 W_i_prime,
137 cf_U_i: nova.cf_U_i.clone(),
138 cf_W_i: nova.cf_W_i.clone(),
139 })
140 }
141
142 /// Verify a zero-knowledge proof of a Nova IVC proof
143 /// It implements the verifier of appendix D.4. in https://eprint.iacr.org/2023/573.pdf
144 #[allow(clippy::too_many_arguments)]
145 pub fn verify<
146 CS1: CommitmentScheme<C1, true>,
147 GC2: CurveVar<C2, CF2<C2>>,
148 CS2: CommitmentScheme<C2, true>,
149 >(
150 r1cs: &R1CS<C1::ScalarField>,
151 cf_r1cs: &R1CS<C2::ScalarField>,
152 pp_hash: C1::ScalarField,
153 poseidon_config: &PoseidonConfig<C1::ScalarField>,
154 i: C1::ScalarField,
155 z_0: Vec<C1::ScalarField>,
156 z_i: Vec<C1::ScalarField>,
157 proof: &RandomizedIVCProof<C1, C2>,
158 ) -> Result<(), Error>
159 where
160 <C1 as Group>::ScalarField: Absorb,
161 <C2 as Group>::ScalarField: Absorb,
162 <C2 as CurveGroup>::BaseField: PrimeField,
163 <C2 as CurveGroup>::BaseField: Absorb,
164 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
165 GC2: ToConstraintFieldGadget<<C2 as CurveGroup>::BaseField>,
166 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
167 {
168 // Handles case where i=0
169 if i == C1::ScalarField::zero() {
170 if z_0 == z_i {
171 return Ok(());
172 } else {
173 return Err(Error::zkIVCVerificationFail);
174 }
175 }
176
177 // 1. Check that u_i.x is correct - including the cyclefold running instance
178 // a. Check length
179 if proof.u_i.x.len() != 2 {
180 return Err(Error::IVCVerificationFail);
181 }
182
183 // b. Check computed hashes are correct
184 let sponge = PoseidonSponge::<C1::ScalarField>::new(poseidon_config);
185 let expected_u_i_x = proof.U_i.hash(&sponge, pp_hash, i, &z_0, &z_i);
186 if expected_u_i_x != proof.u_i.x[0] {
187 return Err(Error::zkIVCVerificationFail);
188 }
189
190 let expected_cf_u_i_x = proof.cf_U_i.hash_cyclefold(&sponge, pp_hash);
191 if expected_cf_u_i_x != proof.u_i.x[1] {
192 return Err(Error::IVCVerificationFail);
193 }
194
195 // 2. Check that u_i values are correct
196 if !proof.u_i.cmE.is_zero() || proof.u_i.u != C1::ScalarField::one() {
197 return Err(Error::zkIVCVerificationFail);
198 }
199
200 let mut transcript = PoseidonSponge::<C1::ScalarField>::new(poseidon_config);
201 // 3. Obtain the U_f folded instance
202 let (U_f, _) = NIFS::<C1, CS1, PoseidonSponge<C1::ScalarField>, true>::verify(
203 &mut transcript,
204 pp_hash,
205 &proof.u_i,
206 &proof.U_i,
207 &proof.pi,
208 )?;
209
210 // 4. Obtain the U^{\prime}_i folded instance
211 let (U_i_prime, _) = NIFS::<C1, CS1, PoseidonSponge<C1::ScalarField>, true>::verify(
212 &mut transcript,
213 pp_hash,
214 &U_f,
215 &proof.U_r,
216 &proof.pi_prime,
217 )?;
218
219 // 5. Check that W^{\prime}_i is a satisfying witness
220 r1cs.check_relation(&proof.W_i_prime, &U_i_prime)?;
221
222 // 6. Check that the cyclefold instance-witness pair satisfies the cyclefold relaxed r1cs
223 cf_r1cs.check_relation(&proof.cf_W_i, &proof.cf_U_i)?;
224
225 Ok(())
226 }
227}
228
229#[cfg(test)]
230pub mod tests {
231 use super::*;
232 use crate::commitment::pedersen::Pedersen;
233 use crate::folding::nova::tests::test_ivc_opt;
234 use crate::frontend::utils::CubicFCircuit;
235 use crate::transcript::poseidon::poseidon_canonical_config;
236 use ark_bn254::{Fr, G1Projective as Projective};
237 use ark_grumpkin::{constraints::GVar as GVar2, Projective as Projective2};
238 use rand::rngs::OsRng;
239
240 // Tests zk proof generation and verification for a valid nova IVC proof
241 #[test]
242 fn test_zk_nova_ivc() {
243 let mut rng = OsRng;
244 let poseidon_config = poseidon_canonical_config::<Fr>();
245 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
246 let (_, nova) = test_ivc_opt::<Pedersen<Projective, true>, Pedersen<Projective2, true>, true>(
247 poseidon_config.clone(),
248 F_circuit,
249 3,
250 );
251
252 let proof = RandomizedIVCProof::new(&nova, &mut rng).unwrap();
253 let verify = RandomizedIVCProof::verify::<
254 Pedersen<Projective, true>,
255 GVar2,
256 Pedersen<Projective2, true>,
257 >(
258 &nova.r1cs,
259 &nova.cf_r1cs,
260 nova.pp_hash,
261 &nova.poseidon_config,
262 nova.i,
263 nova.z_0,
264 nova.z_i,
265 &proof,
266 );
267 assert!(verify.is_ok());
268 }
269
270 #[test]
271 fn test_zk_nova_when_i_is_zero() {
272 let mut rng = OsRng;
273 let poseidon_config = poseidon_canonical_config::<Fr>();
274 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
275 let (_, nova) = test_ivc_opt::<Pedersen<Projective, true>, Pedersen<Projective2, true>, true>(
276 poseidon_config.clone(),
277 F_circuit,
278 0,
279 );
280
281 let proof = RandomizedIVCProof::new(&nova, &mut rng).unwrap();
282 let verify = RandomizedIVCProof::verify::<
283 Pedersen<Projective, true>,
284 GVar2,
285 Pedersen<Projective2, true>,
286 >(
287 &nova.r1cs,
288 &nova.cf_r1cs,
289 nova.pp_hash,
290 &nova.poseidon_config,
291 nova.i,
292 nova.z_0,
293 nova.z_i,
294 &proof,
295 );
296 assert!(verify.is_ok());
297 }
298
299 #[test]
300 fn test_zk_nova_verification_fails_with_wrong_running_instance() {
301 let mut rng = OsRng;
302 let poseidon_config = poseidon_canonical_config::<Fr>();
303 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
304 let (_, nova) = test_ivc_opt::<Pedersen<Projective, true>, Pedersen<Projective2, true>, true>(
305 poseidon_config.clone(),
306 F_circuit,
307 3,
308 );
309 let (_, sampled_committed_instance) = nova
310 .r1cs
311 .sample_witness_instance::<Pedersen<Projective, true>>(&nova.cs_pp, rng)
312 .unwrap();
313
314 // proof verification fails with incorrect running instance
315 let mut nova_with_incorrect_running_instance = nova.clone();
316 nova_with_incorrect_running_instance.U_i = sampled_committed_instance;
317 let incorrect_proof =
318 RandomizedIVCProof::new(&nova_with_incorrect_running_instance, &mut rng).unwrap();
319 let verify = RandomizedIVCProof::verify::<
320 Pedersen<Projective, true>,
321 GVar2,
322 Pedersen<Projective2, true>,
323 >(
324 &nova_with_incorrect_running_instance.r1cs,
325 &nova_with_incorrect_running_instance.cf_r1cs,
326 nova_with_incorrect_running_instance.pp_hash,
327 &nova_with_incorrect_running_instance.poseidon_config,
328 nova_with_incorrect_running_instance.i,
329 nova_with_incorrect_running_instance.z_0,
330 nova_with_incorrect_running_instance.z_i,
331 &incorrect_proof,
332 );
333 assert!(verify.is_err());
334 }
335
336 #[test]
337 fn test_zk_nova_verification_fails_with_wrong_running_witness() {
338 let mut rng = OsRng;
339 let poseidon_config = poseidon_canonical_config::<Fr>();
340 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
341 let (_, nova) = test_ivc_opt::<Pedersen<Projective, true>, Pedersen<Projective2, true>, true>(
342 poseidon_config.clone(),
343 F_circuit,
344 3,
345 );
346 let (sampled_committed_witness, _) = nova
347 .r1cs
348 .sample_witness_instance::<Pedersen<Projective, true>>(&nova.cs_pp, rng)
349 .unwrap();
350
351 // proof generation fails with incorrect running witness
352 let mut nova_with_incorrect_running_witness = nova.clone();
353 nova_with_incorrect_running_witness.W_i = sampled_committed_witness;
354 let incorrect_proof =
355 RandomizedIVCProof::new(&nova_with_incorrect_running_witness, &mut rng).unwrap();
356 let verify = RandomizedIVCProof::verify::<
357 Pedersen<Projective, true>,
358 GVar2,
359 Pedersen<Projective2, true>,
360 >(
361 &nova_with_incorrect_running_witness.r1cs,
362 &nova_with_incorrect_running_witness.cf_r1cs,
363 nova_with_incorrect_running_witness.pp_hash,
364 &nova_with_incorrect_running_witness.poseidon_config,
365 nova_with_incorrect_running_witness.i,
366 nova_with_incorrect_running_witness.z_0,
367 nova_with_incorrect_running_witness.z_i,
368 &incorrect_proof,
369 );
370 assert!(verify.is_err());
371 }
372}