sonobe/folding-schemes/src/folding/ova/nifs.rs
folding-schemes/src/folding/ova/nifs.rsRaw
1/// This module contains the implementation of the Ova scheme NIFS (Non-Interactive Folding Scheme) as
2/// outlined in the protocol description doc: <https://hackmd.io/V4838nnlRKal9ZiTHiGYzw?both#Construction>
3/// authored by Benedikt Bünz.
4use ark_crypto_primitives::sponge::Absorb;
5use ark_ec::{CurveGroup, Group};
6use ark_std::One;
7use std::marker::PhantomData;
8
9use super::{CommittedInstance, Witness};
10use crate::arith::r1cs::R1CS;
11use crate::commitment::CommitmentScheme;
12use crate::transcript::Transcript;
13use crate::utils::vec::{hadamard, mat_vec_mul, vec_scalar_mul, vec_sub};
14use crate::Error;
15
16/// Implements all the operations executed by the Non-Interactive Folding Scheme described in the protocol
17/// spec by Bünz in the [original HackMD](https://hackmd.io/V4838nnlRKal9ZiTHiGYzw?both#Construction).
18/// `H` specifies whether the NIFS will use a blinding factor
19pub struct NIFS<C: CurveGroup, CS: CommitmentScheme<C, H>, const H: bool = false> {
20 _c: PhantomData<C>,
21 _cp: PhantomData<CS>,
22}
23
24impl<C: CurveGroup, CS: CommitmentScheme<C, H>, const H: bool> NIFS<C, CS, H>
25where
26 <C as Group>::ScalarField: Absorb,
27{
28 /// Computes the T parameter (Cross Terms) as in Nova.
29 /// The wrapper is only in place to facilitate the calling as we need
30 /// to reconstruct the `z`s being folded in order to compute T.
31 pub fn compute_T(
32 r1cs: &R1CS<C::ScalarField>,
33 w_i: &Witness<C>,
34 x_i: &[C::ScalarField],
35 W_i: &Witness<C>,
36 X_i: &[C::ScalarField],
37 mu: C::ScalarField,
38 ) -> Result<Vec<C::ScalarField>, Error> {
39 crate::folding::nova::nifs::NIFS::<C, CS, H>::compute_T(
40 r1cs,
41 C::ScalarField::one(),
42 mu,
43 &[vec![C::ScalarField::one()], x_i.to_vec(), w_i.w.to_vec()].concat(),
44 &[vec![mu], X_i.to_vec(), W_i.w.to_vec()].concat(),
45 )
46 }
47
48 /// Computes the E parameter (Error Terms) as in Nova.
49 /// The wrapper is only in place to facilitate the calling as we need
50 /// to reconstruct the `z`s being folded in order to compute E.
51 ///
52 /// Not only that, but notice that the incoming-instance `mu` parameter is always
53 /// equal to 1. Therefore, we can save the some computations.
54 pub fn compute_E(
55 r1cs: &R1CS<C::ScalarField>,
56 W_i: &Witness<C>,
57 X_i: &[C::ScalarField],
58 mu: C::ScalarField,
59 ) -> Result<Vec<C::ScalarField>, Error> {
60 let (A, B, C) = (r1cs.A.clone(), r1cs.B.clone(), r1cs.C.clone());
61
62 let z_prime = [&[mu], X_i, &W_i.w].concat();
63 // this is parallelizable (for the future)
64 let Az_prime = mat_vec_mul(&A, &z_prime)?;
65 let Bz_prime = mat_vec_mul(&B, &z_prime)?;
66 let Cz_prime = mat_vec_mul(&C, &z_prime)?;
67
68 let Az_prime_Bz_prime = hadamard(&Az_prime, &Bz_prime)?;
69 let muCz_prime = vec_scalar_mul(&Cz_prime, &mu);
70
71 vec_sub(&Az_prime_Bz_prime, &muCz_prime)
72 }
73
74 /// Folds 2 [`CommittedInstance`]s returning a freshly folded one as is specified
75 /// in: <https://hackmd.io/V4838nnlRKal9ZiTHiGYzw?both#Construction>.
76 /// Here, alpha is a randomness sampled from a [`Transcript`].
77 pub fn fold_committed_instance(
78 alpha: C::ScalarField,
79 // This is W (incoming)
80 u_i: &CommittedInstance<C>,
81 // This is W' (running)
82 U_i: &CommittedInstance<C>,
83 ) -> CommittedInstance<C> {
84 let mu = U_i.mu + alpha; // u_i.mu **IS ALWAYS 1 in OVA** as we just can do sequential IVC.
85 let cmWE = U_i.cmWE + u_i.cmWE.mul(alpha);
86 let x = U_i
87 .x
88 .iter()
89 .zip(&u_i.x)
90 .map(|(a, b)| *a + (alpha * b))
91 .collect::<Vec<C::ScalarField>>();
92
93 CommittedInstance::<C> { cmWE, mu, x }
94 }
95
96 /// Folds 2 [`Witness`]s returning a freshly folded one as is specified
97 /// in: <https://hackmd.io/V4838nnlRKal9ZiTHiGYzw?both#Construction>.
98 /// Here, alpha is a randomness sampled from a [`Transcript`].
99 pub fn fold_witness(
100 alpha: C::ScalarField,
101 // incoming instance
102 w_i: &Witness<C>,
103 // running instance
104 W_i: &Witness<C>,
105 ) -> Result<Witness<C>, Error> {
106 let w: Vec<C::ScalarField> = W_i
107 .w
108 .iter()
109 .zip(&w_i.w)
110 .map(|(a, b)| *a + (alpha * b))
111 .collect();
112
113 let rW = W_i.rW + alpha * w_i.rW;
114 Ok(Witness::<C> { w, rW })
115 }
116
117 /// fold_instances is part of the NIFS.P logic described in
118 /// [Ova](https://hackmd.io/V4838nnlRKal9ZiTHiGYzw?both#Construction)'s Construction section.
119 /// It returns the folded [`CommittedInstance`] and [`Witness`].
120 pub fn fold_instances(
121 r: C::ScalarField,
122 // incoming instance
123 w_i: &Witness<C>,
124 u_i: &CommittedInstance<C>,
125 // running instance
126 W_i: &Witness<C>,
127 U_i: &CommittedInstance<C>,
128 ) -> Result<(Witness<C>, CommittedInstance<C>), Error> {
129 // fold witness
130 let w3 = NIFS::<C, CS, H>::fold_witness(r, w_i, W_i)?;
131
132 // fold committed instances
133 let ci3 = NIFS::<C, CS, H>::fold_committed_instance(r, u_i, U_i);
134
135 Ok((w3, ci3))
136 }
137
138 /// Implements NIFS.V (accumulation verifier) logic described in [Ova](https://hackmd.io/V4838nnlRKal9ZiTHiGYzw?both#Construction)'s
139 /// Construction section.
140 /// It returns the folded [`CommittedInstance`].
141 pub fn verify(
142 // r comes from the transcript, and is a n-bit (N_BITS_CHALLENGE) element
143 alpha: C::ScalarField,
144 // incoming instance
145 u_i: &CommittedInstance<C>,
146 // running instance
147 U_i: &CommittedInstance<C>,
148 ) -> CommittedInstance<C> {
149 NIFS::<C, CS, H>::fold_committed_instance(alpha, u_i, U_i)
150 }
151
152 #[cfg(test)]
153 /// Verify committed folded instance (ui) relations. Notice that this method does not open the
154 /// commitments, but just checks that the given committed instances (ui1, ui2) when folded
155 /// result in the folded committed instance (ui3) values.
156 pub(crate) fn verify_folded_instance(
157 r: C::ScalarField,
158 // incoming instance
159 u_i: &CommittedInstance<C>,
160 // running instance
161 U_i: &CommittedInstance<C>,
162 // folded instance
163 folded_instance: &CommittedInstance<C>,
164 ) -> Result<(), Error> {
165 let expected = Self::fold_committed_instance(r, u_i, U_i);
166 if folded_instance.mu != expected.mu
167 || folded_instance.cmWE != expected.cmWE
168 || folded_instance.x != expected.x
169 {
170 return Err(Error::NotSatisfied);
171 }
172 Ok(())
173 }
174
175 /// Generates a [`CS::Proof`] for the given [`CommittedInstance`] and [`Witness`] pair.
176 pub fn prove_commitment(
177 r1cs: &R1CS<C::ScalarField>,
178 tr: &mut impl Transcript<C::ScalarField>,
179 cs_prover_params: &CS::ProverParams,
180 w: &Witness<C>,
181 ci: &CommittedInstance<C>,
182 ) -> Result<CS::Proof, Error> {
183 let e = NIFS::<C, CS, H>::compute_E(r1cs, w, &ci.x, ci.mu).unwrap();
184 let w_concat_e: Vec<C::ScalarField> = [w.w.clone(), e].concat();
185 CS::prove(cs_prover_params, tr, &ci.cmWE, &w_concat_e, &w.rW, None)
186 }
187}
188
189#[cfg(test)]
190pub mod tests {
191 use super::*;
192 use crate::folding::ova::ChallengeGadget;
193 use crate::transcript::poseidon::poseidon_canonical_config;
194 use crate::{
195 arith::{
196 r1cs::tests::{get_test_r1cs, get_test_z},
197 Arith,
198 },
199 folding::traits::Dummy,
200 };
201 use crate::{
202 commitment::pedersen::{Params as PedersenParams, Pedersen},
203 folding::ova::TestingWitness,
204 };
205 use ark_crypto_primitives::sponge::{
206 poseidon::{PoseidonConfig, PoseidonSponge},
207 CryptographicSponge,
208 };
209 use ark_ff::{BigInteger, PrimeField};
210 use ark_pallas::{Fr, Projective};
211 use ark_std::{test_rng, UniformRand, Zero};
212
213 fn compute_E_check_relation<C: CurveGroup, CS: CommitmentScheme<C, H>, const H: bool>(
214 r1cs: &R1CS<C::ScalarField>,
215 w: &Witness<C>,
216 u: &CommittedInstance<C>,
217 ) where
218 <C as Group>::ScalarField: Absorb,
219 {
220 let e = NIFS::<C, CS, H>::compute_E(r1cs, w, &u.x, u.mu).unwrap();
221 r1cs.check_relation(&TestingWitness::<C> { e, w: w.w.clone() }, u)
222 .unwrap();
223 }
224
225 #[allow(clippy::type_complexity)]
226 pub(crate) fn prepare_simple_fold_inputs<C>() -> (
227 PedersenParams<C>,
228 PoseidonConfig<C::ScalarField>,
229 R1CS<C::ScalarField>,
230 Witness<C>, // w
231 CommittedInstance<C>, // u
232 Witness<C>, // W
233 CommittedInstance<C>, // U
234 Witness<C>, // w_fold
235 CommittedInstance<C>, // u_fold
236 Vec<bool>, // r_bits
237 C::ScalarField, // r_Fr
238 )
239 where
240 C: CurveGroup,
241 <C as CurveGroup>::BaseField: PrimeField,
242 C::ScalarField: Absorb,
243 {
244 // Index 1 represents the incoming instance
245 // Index 2 represents the accumulated instance
246 let r1cs = get_test_r1cs();
247 let z1 = get_test_z(3);
248 let z2 = get_test_z(4);
249 let (w1, x1) = r1cs.split_z(&z1);
250 let (w2, x2) = r1cs.split_z(&z2);
251
252 let w = Witness::<C>::new::<false>(w1.clone(), test_rng());
253 let W: Witness<C> = Witness::<C>::new::<false>(w2.clone(), test_rng());
254
255 let mut rng = ark_std::test_rng();
256 let (pedersen_params, _) = Pedersen::<C>::setup(&mut rng, r1cs.A.n_cols).unwrap();
257
258 // In order to be able to compute the committed instances, we need to compute `t` and `e`
259 // compute t
260 let t = NIFS::<C, Pedersen<C>>::compute_T(&r1cs, &w, &x1, &W, &x2, C::ScalarField::one())
261 .unwrap();
262 // compute e (mu is 1 although is the running instance as we are "crafting it").
263 let e = NIFS::<C, Pedersen<C>>::compute_E(&r1cs, &W, &x2, C::ScalarField::one()).unwrap();
264 // compute committed instances
265 // Incoming-instance
266 let u = w
267 .commit::<Pedersen<C>, false>(&pedersen_params, t, x1.clone())
268 .unwrap();
269 // Running-instance
270 let U = W
271 .commit::<Pedersen<C>, false>(&pedersen_params, e, x2.clone())
272 .unwrap();
273
274 let poseidon_config = poseidon_canonical_config::<C::ScalarField>();
275 let mut transcript = PoseidonSponge::<C::ScalarField>::new(&poseidon_config);
276
277 let pp_hash = C::ScalarField::from(42u32); // only for test
278
279 let alpha_bits = ChallengeGadget::<C>::get_challenge_native(
280 &mut transcript,
281 pp_hash,
282 u.clone(),
283 U.clone(),
284 );
285 let alpha_Fr = C::ScalarField::from_bigint(BigInteger::from_bits_le(&alpha_bits)).unwrap();
286
287 let (w_fold, u_fold) =
288 NIFS::<C, Pedersen<C>, false>::fold_instances(alpha_Fr, &w, &u, &W, &U).unwrap();
289
290 // Check correctness of the R1CS relation of the folded instance.
291 compute_E_check_relation::<C, Pedersen<C>, false>(&r1cs, &w_fold, &u_fold);
292
293 (
294 pedersen_params,
295 poseidon_config,
296 r1cs,
297 w,
298 u,
299 W,
300 U,
301 w_fold,
302 u_fold,
303 alpha_bits,
304 alpha_Fr,
305 )
306 }
307
308 // fold 2 dummy instances and check that the folded instance holds the relaxed R1CS relation
309 #[test]
310 fn test_nifs_fold_dummy() {
311 let mut rng = ark_std::test_rng();
312 let r1cs = get_test_r1cs::<Fr>();
313
314 let w_dummy = Witness::<Projective>::dummy(&r1cs);
315 let (pedersen_params, _) = Pedersen::<Projective>::setup(&mut rng, r1cs.A.n_cols).unwrap();
316
317 // In order to be able to compute the committed instances, we need to compute `t` and `e`
318 // compute t
319 let t = NIFS::<Projective, Pedersen<Projective>>::compute_T(
320 &r1cs,
321 &w_dummy,
322 &[Fr::zero()],
323 &w_dummy,
324 &[Fr::zero()],
325 Fr::one(),
326 )
327 .unwrap();
328
329 // compute e
330 let e = NIFS::<Projective, Pedersen<Projective>>::compute_E(
331 &r1cs,
332 &w_dummy,
333 &[Fr::zero()],
334 Fr::one(),
335 )
336 .unwrap();
337
338 // dummy incoming instance, witness and public inputs
339 let u_dummy = w_dummy
340 .commit::<Pedersen<Projective>, false>(&pedersen_params, t, vec![Fr::zero()])
341 .unwrap();
342
343 // dummy accumulated instance, witness and public inputs
344 let U_dummy = w_dummy
345 .commit::<Pedersen<Projective>, false>(&pedersen_params, e.clone(), vec![Fr::zero()])
346 .unwrap();
347
348 let w_i = w_dummy.clone();
349 let u_i = u_dummy.clone();
350 let W_i = w_dummy.clone();
351 let U_i = U_dummy.clone();
352
353 // Check correctness of the R1CS relations of both instances.
354 compute_E_check_relation::<Projective, Pedersen<Projective>, false>(&r1cs, &w_i, &u_i);
355 compute_E_check_relation::<Projective, Pedersen<Projective>, false>(&r1cs, &W_i, &U_i);
356
357 // NIFS.P
358 let r_Fr = Fr::from(3_u32);
359 let (w_fold, u_fold) =
360 NIFS::<Projective, Pedersen<Projective>>::fold_instances(r_Fr, &w_i, &u_i, &W_i, &U_i)
361 .unwrap();
362
363 // Check correctness of the R1CS relation of both instances.
364 compute_E_check_relation::<Projective, Pedersen<Projective>, false>(
365 &r1cs, &w_fold, &u_fold,
366 );
367 }
368
369 // fold 2 instances into one
370 #[test]
371 fn test_nifs_one_fold() {
372 let (pedersen_params, poseidon_config, r1cs, w, u, W, U, w_fold, u_fold, _, r) =
373 prepare_simple_fold_inputs();
374
375 // NIFS.V
376 let u_fold_v = NIFS::<Projective, Pedersen<Projective>>::verify(r, &u, &U);
377 assert_eq!(u_fold_v, u_fold);
378
379 // Check that relations hold for the 2 inputted instances and the folded one
380 compute_E_check_relation::<Projective, Pedersen<Projective>, false>(&r1cs, &w, &u);
381 compute_E_check_relation::<Projective, Pedersen<Projective>, false>(&r1cs, &W, &U);
382 compute_E_check_relation::<Projective, Pedersen<Projective>, false>(
383 &r1cs, &w_fold, &u_fold,
384 );
385
386 // check that folded commitments from folded instance (u) are equal to folding the
387 // use folded rW to commit w_fold
388 let e_fold = NIFS::<Projective, Pedersen<Projective>>::compute_E(
389 &r1cs, &w_fold, &u_fold.x, u_fold.mu,
390 )
391 .unwrap();
392 let mut u_fold_expected = w_fold
393 .commit::<Pedersen<Projective>, false>(&pedersen_params, e_fold, u_fold.x.clone())
394 .unwrap();
395 u_fold_expected.mu = u_fold.mu;
396 assert_eq!(u_fold_expected.cmWE, u_fold.cmWE);
397
398 // NIFS.Verify_Folded_Instance:
399 NIFS::<Projective, Pedersen<Projective>>::verify_folded_instance(r, &u, &U, &u_fold)
400 .unwrap();
401
402 // init Prover's transcript
403 let mut transcript_p = PoseidonSponge::<Fr>::new(&poseidon_config);
404 // init Verifier's transcript
405 let mut transcript_v = PoseidonSponge::<Fr>::new(&poseidon_config);
406
407 // prove the u_fold.cmWE
408 let cm_proof = NIFS::<Projective, Pedersen<Projective>>::prove_commitment(
409 &r1cs,
410 &mut transcript_p,
411 &pedersen_params,
412 &w_fold,
413 &u_fold,
414 )
415 .unwrap();
416
417 // verify the u_fold.cmWE.
418 Pedersen::<Projective>::verify(
419 &pedersen_params,
420 &mut transcript_v,
421 &u_fold.cmWE,
422 &cm_proof,
423 )
424 .unwrap();
425 }
426
427 #[test]
428 fn test_nifs_fold_loop() {
429 let r1cs = get_test_r1cs();
430 let z = get_test_z(3);
431 let (w, x) = r1cs.split_z(&z);
432
433 let mut rng = ark_std::test_rng();
434 let (pedersen_params, _) = Pedersen::<Projective>::setup(&mut rng, r1cs.A.n_cols).unwrap();
435
436 // prepare the running instance
437 let mut W = Witness::<Projective>::new::<false>(w.clone(), &mut rng);
438 // Compute e
439 let e =
440 NIFS::<Projective, Pedersen<Projective>>::compute_E(&r1cs, &W, &x, Fr::one()).unwrap();
441 // Compute running `CommittedInstance`.
442 let mut U = W
443 .commit::<Pedersen<Projective>, false>(&pedersen_params, e, x)
444 .unwrap();
445
446 let num_iters = 10;
447 for i in 0..num_iters {
448 // prepare the incoming instance
449 let incoming_instance_z = get_test_z(i + 4);
450 let (w, x) = r1cs.split_z(&incoming_instance_z);
451 let w = Witness::<Projective>::new::<false>(w, test_rng());
452 let t =
453 NIFS::<Projective, Pedersen<Projective>>::compute_T(&r1cs, &w, &U.x, &w, &x, U.mu)
454 .unwrap();
455 let u = w
456 .commit::<Pedersen<Projective>, false>(&pedersen_params, t, x)
457 .unwrap();
458
459 // Check incoming instance is Ok.
460 compute_E_check_relation::<Projective, Pedersen<Projective>, false>(&r1cs, &w, &u);
461
462 // Generate "transcript randomness"
463 let alpha = Fr::rand(&mut rng); // folding challenge would come from the RO
464
465 // NIFS.P
466 let (w_folded, _) =
467 NIFS::<Projective, Pedersen<Projective>>::fold_instances(alpha, &w, &u, &W, &u)
468 .unwrap();
469
470 // NIFS.V
471 let u_folded = NIFS::<Projective, Pedersen<Projective>>::verify(alpha, &u, &U);
472
473 compute_E_check_relation::<Projective, Pedersen<Projective>, false>(
474 &r1cs, &w_folded, &u_folded,
475 );
476
477 // set running_instance for next loop iteration
478 W = w_folded;
479 U = u_folded;
480 }
481 }
482}