sonobe/src/folding/nova/nifs.rs
src/folding/nova/nifs.rsRaw
1use ark_crypto_primitives::sponge::Absorb;
2use ark_ec::{CurveGroup, Group};
3use ark_std::One;
4use std::marker::PhantomData;
5
6use crate::ccs::r1cs::R1CS;
7use crate::folding::nova::{CommittedInstance, Witness};
8use crate::pedersen::{Params as PedersenParams, Pedersen, Proof as PedersenProof};
9use crate::transcript::Transcript;
10use crate::utils::vec::*;
11use crate::Error;
12
13/// Implements the Non-Interactive Folding Scheme described in section 4 of
14/// https://eprint.iacr.org/2021/370.pdf
15pub struct NIFS<C: CurveGroup> {
16 _phantom: PhantomData<C>,
17}
18
19impl<C: CurveGroup> NIFS<C>
20where
21 <C as Group>::ScalarField: Absorb,
22{
23 // compute_T: compute cross-terms T
24 pub fn compute_T(
25 r1cs: &R1CS<C::ScalarField>,
26 u1: C::ScalarField,
27 u2: C::ScalarField,
28 z1: &[C::ScalarField],
29 z2: &[C::ScalarField],
30 ) -> Result<Vec<C::ScalarField>, Error> {
31 let (A, B, C) = (r1cs.A.clone(), r1cs.B.clone(), r1cs.C.clone());
32
33 // this is parallelizable (for the future)
34 let Az1 = mat_vec_mul_sparse(&A, z1);
35 let Bz1 = mat_vec_mul_sparse(&B, z1);
36 let Cz1 = mat_vec_mul_sparse(&C, z1);
37 let Az2 = mat_vec_mul_sparse(&A, z2);
38 let Bz2 = mat_vec_mul_sparse(&B, z2);
39 let Cz2 = mat_vec_mul_sparse(&C, z2);
40
41 let Az1_Bz2 = hadamard(&Az1, &Bz2)?;
42 let Az2_Bz1 = hadamard(&Az2, &Bz1)?;
43 let u1Cz2 = vec_scalar_mul(&Cz2, &u1);
44 let u2Cz1 = vec_scalar_mul(&Cz1, &u2);
45
46 vec_sub(&vec_sub(&vec_add(&Az1_Bz2, &Az2_Bz1)?, &u1Cz2)?, &u2Cz1)
47 }
48
49 pub fn fold_witness(
50 r: C::ScalarField,
51 w1: &Witness<C>,
52 w2: &Witness<C>,
53 T: &[C::ScalarField],
54 rT: C::ScalarField,
55 ) -> Result<Witness<C>, Error> {
56 let r2 = r * r;
57 let E: Vec<C::ScalarField> = vec_add(
58 &vec_add(&w1.E, &vec_scalar_mul(T, &r))?,
59 &vec_scalar_mul(&w2.E, &r2),
60 )?;
61 let rE = w1.rE + r * rT + r2 * w2.rE;
62 let W: Vec<C::ScalarField> = w1.W.iter().zip(&w2.W).map(|(a, b)| *a + (r * b)).collect();
63
64 let rW = w1.rW + r * w2.rW;
65 Ok(Witness::<C> { E, rE, W, rW })
66 }
67
68 pub fn fold_committed_instance(
69 r: C::ScalarField,
70 ci1: &CommittedInstance<C>,
71 ci2: &CommittedInstance<C>,
72 cmT: &C,
73 ) -> CommittedInstance<C> {
74 let r2 = r * r;
75 let cmE = ci1.cmE + cmT.mul(r) + ci2.cmE.mul(r2);
76 let u = ci1.u + r * ci2.u;
77 let cmW = ci1.cmW + ci2.cmW.mul(r);
78 let x = ci1
79 .x
80 .iter()
81 .zip(&ci2.x)
82 .map(|(a, b)| *a + (r * b))
83 .collect::<Vec<C::ScalarField>>();
84
85 CommittedInstance::<C> { cmE, u, cmW, x }
86 }
87
88 // NIFS.P
89 #[allow(clippy::type_complexity)]
90 pub fn prove(
91 pedersen_params: &PedersenParams<C>,
92 // r comes from the transcript, and is a n-bit (N_BITS_CHALLENGE) element
93 r: C::ScalarField,
94 r1cs: &R1CS<C::ScalarField>,
95 w1: &Witness<C>,
96 ci1: &CommittedInstance<C>,
97 w2: &Witness<C>,
98 ci2: &CommittedInstance<C>,
99 ) -> Result<(Witness<C>, CommittedInstance<C>, Vec<C::ScalarField>, C), Error> {
100 let z1: Vec<C::ScalarField> = [vec![ci1.u], ci1.x.to_vec(), w1.W.to_vec()].concat();
101 let z2: Vec<C::ScalarField> = [vec![ci2.u], ci2.x.to_vec(), w2.W.to_vec()].concat();
102
103 // compute cross terms
104 let T = Self::compute_T(r1cs, ci1.u, ci2.u, &z1, &z2)?;
105 let rT = C::ScalarField::one(); // use 1 as rT since we don't need hiding property for cm(T)
106 let cmT = Pedersen::commit(pedersen_params, &T, &rT);
107
108 // fold witness
109 let w3 = NIFS::<C>::fold_witness(r, w1, w2, &T, rT)?;
110
111 // fold committed instancs
112 let ci3 = NIFS::<C>::fold_committed_instance(r, ci1, ci2, &cmT);
113
114 Ok((w3, ci3, T, cmT))
115 }
116
117 // NIFS.V
118 pub fn verify(
119 // r comes from the transcript, and is a n-bit (N_BITS_CHALLENGE) element
120 r: C::ScalarField,
121 ci1: &CommittedInstance<C>,
122 ci2: &CommittedInstance<C>,
123 cmT: &C,
124 ) -> CommittedInstance<C> {
125 NIFS::<C>::fold_committed_instance(r, ci1, ci2, cmT)
126 }
127
128 /// Verify commited folded instance (ci) relations. Notice that this method does not open the
129 /// commitments, but just checks that the given committed instances (ci1, ci2) when folded
130 /// result in the folded committed instance (ci3) values.
131 pub fn verify_folded_instance(
132 r: C::ScalarField,
133 ci1: &CommittedInstance<C>,
134 ci2: &CommittedInstance<C>,
135 ci3: &CommittedInstance<C>,
136 cmT: &C,
137 ) -> Result<(), Error> {
138 let r2 = r * r;
139 if ci3.cmE != (ci1.cmE + cmT.mul(r) + ci2.cmE.mul(r2)) {
140 return Err(Error::NotSatisfied);
141 }
142 if ci3.u != ci1.u + r * ci2.u {
143 return Err(Error::NotSatisfied);
144 }
145 if ci3.cmW != (ci1.cmW + ci2.cmW.mul(r)) {
146 return Err(Error::NotSatisfied);
147 }
148 if ci3.x != vec_add(&ci1.x, &vec_scalar_mul(&ci2.x, &r))? {
149 return Err(Error::NotSatisfied);
150 }
151 Ok(())
152 }
153
154 pub fn open_commitments(
155 tr: &mut impl Transcript<C>,
156 pedersen_params: &PedersenParams<C>,
157 w: &Witness<C>,
158 ci: &CommittedInstance<C>,
159 T: Vec<C::ScalarField>,
160 cmT: &C,
161 ) -> Result<[PedersenProof<C>; 3], Error> {
162 let cmE_proof = Pedersen::prove(pedersen_params, tr, &ci.cmE, &w.E, &w.rE)?;
163 let cmW_proof = Pedersen::prove(pedersen_params, tr, &ci.cmW, &w.W, &w.rW)?;
164 let cmT_proof = Pedersen::prove(pedersen_params, tr, cmT, &T, &C::ScalarField::one())?; // cm(T) is committed with rT=1
165 Ok([cmE_proof, cmW_proof, cmT_proof])
166 }
167 pub fn verify_commitments(
168 tr: &mut impl Transcript<C>,
169 pedersen_params: &PedersenParams<C>,
170 ci: CommittedInstance<C>,
171 cmT: C,
172 cm_proofs: [PedersenProof<C>; 3],
173 ) -> Result<(), Error> {
174 if cm_proofs.len() != 3 {
175 // cm_proofs should have length 3: [cmE_proof, cmW_proof, cmT_proof]
176 return Err(Error::NotExpectedLength);
177 }
178 if !Pedersen::verify(pedersen_params, tr, ci.cmE, cm_proofs[0].clone()) {
179 return Err(Error::CommitmentVerificationFail);
180 }
181 if !Pedersen::verify(pedersen_params, tr, ci.cmW, cm_proofs[1].clone()) {
182 return Err(Error::CommitmentVerificationFail);
183 }
184 if !Pedersen::verify(pedersen_params, tr, cmT, cm_proofs[2].clone()) {
185 return Err(Error::CommitmentVerificationFail);
186 }
187 Ok(())
188 }
189}
190
191#[cfg(test)]
192mod tests {
193 use super::*;
194 use crate::ccs::r1cs::tests::{get_test_r1cs, get_test_z};
195 use crate::transcript::poseidon::{tests::poseidon_test_config, PoseidonTranscript};
196 use ark_ff::PrimeField;
197 use ark_pallas::{Fr, Projective};
198 use ark_std::UniformRand;
199
200 pub fn check_relaxed_r1cs<F: PrimeField>(r1cs: &R1CS<F>, z: Vec<F>, u: F, E: &[F]) {
201 let Az = mat_vec_mul_sparse(&r1cs.A, &z);
202 let Bz = mat_vec_mul_sparse(&r1cs.B, &z);
203 let Cz = mat_vec_mul_sparse(&r1cs.C, &z);
204 assert_eq!(hadamard(&Az, &Bz), vec_add(&vec_scalar_mul(&Cz, &u), E));
205 }
206
207 // fold 2 instances into one
208 #[test]
209 fn test_nifs_one_fold() {
210 let r1cs = get_test_r1cs();
211 let z1 = get_test_z(3);
212 let z2 = get_test_z(4);
213 let (w1, x1) = r1cs.split_z(&z1);
214 let (w2, x2) = r1cs.split_z(&z2);
215
216 let w1 = Witness::<Projective>::new(w1.clone(), r1cs.A.n_rows);
217 let w2 = Witness::<Projective>::new(w2.clone(), r1cs.A.n_rows);
218
219 let mut rng = ark_std::test_rng();
220 let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, r1cs.A.n_cols);
221
222 let r = Fr::rand(&mut rng); // folding challenge would come from the transcript
223
224 // compute committed instances
225 let ci1 = w1.commit(&pedersen_params, x1.clone());
226 let ci2 = w2.commit(&pedersen_params, x2.clone());
227
228 // NIFS.P
229 let (w3, _, T, cmT) =
230 NIFS::<Projective>::prove(&pedersen_params, r, &r1cs, &w1, &ci1, &w2, &ci2).unwrap();
231
232 // NIFS.V
233 let ci3 = NIFS::<Projective>::verify(r, &ci1, &ci2, &cmT);
234
235 // naive check that the folded witness satisfies the relaxed r1cs
236 let z3: Vec<Fr> = [vec![ci3.u], ci3.x.to_vec(), w3.W.to_vec()].concat();
237 // check that z3 is as expected
238 let z3_aux = vec_add(&z1, &vec_scalar_mul(&z2, &r)).unwrap();
239 assert_eq!(z3, z3_aux);
240 // check that relations hold for the 2 inputted instances and the folded one
241 check_relaxed_r1cs(&r1cs, z1, ci1.u, &w1.E);
242 check_relaxed_r1cs(&r1cs, z2, ci2.u, &w2.E);
243 check_relaxed_r1cs(&r1cs, z3, ci3.u, &w3.E);
244
245 // check that folded commitments from folded instance (ci) are equal to folding the
246 // use folded rE, rW to commit w3
247 let ci3_expected = w3.commit(&pedersen_params, ci3.x.clone());
248 assert_eq!(ci3_expected.cmE, ci3.cmE);
249 assert_eq!(ci3_expected.cmW, ci3.cmW);
250
251 // NIFS.Verify_Folded_Instance:
252 NIFS::<Projective>::verify_folded_instance(r, &ci1, &ci2, &ci3, &cmT).unwrap();
253
254 let poseidon_config = poseidon_test_config::<Fr>();
255 // init Prover's transcript
256 let mut transcript_p = PoseidonTranscript::<Projective>::new(&poseidon_config);
257 // init Verifier's transcript
258 let mut transcript_v = PoseidonTranscript::<Projective>::new(&poseidon_config);
259
260 // check openings of ci3.cmE, ci3.cmW and cmT
261 let cm_proofs = NIFS::<Projective>::open_commitments(
262 &mut transcript_p,
263 &pedersen_params,
264 &w3,
265 &ci3,
266 T,
267 &cmT,
268 )
269 .unwrap();
270 NIFS::<Projective>::verify_commitments(
271 &mut transcript_v,
272 &pedersen_params,
273 ci3,
274 cmT,
275 cm_proofs,
276 )
277 .unwrap();
278 }
279
280 #[test]
281 fn test_nifs_fold_loop() {
282 let r1cs = get_test_r1cs();
283 let z = get_test_z(3);
284 let (w, x) = r1cs.split_z(&z);
285
286 let mut rng = ark_std::test_rng();
287 let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, r1cs.A.n_cols);
288
289 // prepare the running instance
290 let mut running_instance_w = Witness::<Projective>::new(w.clone(), r1cs.A.n_rows);
291 let mut running_committed_instance = running_instance_w.commit(&pedersen_params, x);
292 check_relaxed_r1cs(
293 &r1cs,
294 z,
295 running_committed_instance.u,
296 &running_instance_w.E,
297 );
298
299 let num_iters = 10;
300 for i in 0..num_iters {
301 // prepare the incomming instance
302 let incomming_instance_z = get_test_z(i + 4);
303 let (w, x) = r1cs.split_z(&incomming_instance_z);
304 let incomming_instance_w = Witness::<Projective>::new(w.clone(), r1cs.A.n_rows);
305 let incomming_committed_instance = incomming_instance_w.commit(&pedersen_params, x);
306 check_relaxed_r1cs(
307 &r1cs,
308 incomming_instance_z.clone(),
309 incomming_committed_instance.u,
310 &incomming_instance_w.E,
311 );
312
313 let r = Fr::rand(&mut rng); // folding challenge would come from the transcript
314
315 // NIFS.P
316 let (folded_w, _, _, cmT) = NIFS::<Projective>::prove(
317 &pedersen_params,
318 r,
319 &r1cs,
320 &running_instance_w,
321 &running_committed_instance,
322 &incomming_instance_w,
323 &incomming_committed_instance,
324 )
325 .unwrap();
326
327 // NIFS.V
328 let folded_committed_instance = NIFS::<Projective>::verify(
329 r,
330 &running_committed_instance,
331 &incomming_committed_instance,
332 &cmT,
333 );
334
335 let folded_z: Vec<Fr> = [
336 vec![folded_committed_instance.u],
337 folded_committed_instance.x.to_vec(),
338 folded_w.W.to_vec(),
339 ]
340 .concat();
341
342 check_relaxed_r1cs(&r1cs, folded_z, folded_committed_instance.u, &folded_w.E);
343
344 // set running_instance for next loop iteration
345 running_instance_w = folded_w;
346 running_committed_instance = folded_committed_instance;
347 }
348 }
349}