sonobe/folding-schemes/src/folding/nova/nifs.rs
folding-schemes/src/folding/nova/nifs.rsRaw
1use ark_crypto_primitives::sponge::Absorb;
2use ark_ec::{CurveGroup, Group};
3use ark_ff::PrimeField;
4use ark_std::rand::RngCore;
5use ark_std::Zero;
6use std::marker::PhantomData;
7
8use super::circuits::ChallengeGadget;
9use super::traits::NIFSTrait;
10use super::{CommittedInstance, Witness};
11use crate::arith::r1cs::R1CS;
12use crate::commitment::CommitmentScheme;
13use crate::folding::circuits::cyclefold::{CycleFoldCommittedInstance, CycleFoldWitness};
14use crate::transcript::Transcript;
15use crate::utils::vec::{hadamard, mat_vec_mul, vec_add, vec_scalar_mul, vec_sub};
16use crate::Error;
17
18/// Implements the Non-Interactive Folding Scheme described in section 4 of
19/// [Nova](https://eprint.iacr.org/2021/370.pdf)
20/// `H` specifies whether the NIFS will use a blinding factor
21pub struct NIFS<C: CurveGroup, CS: CommitmentScheme<C, H>, const H: bool = false> {
22 _c: PhantomData<C>,
23 _cp: PhantomData<CS>,
24}
25
26impl<C: CurveGroup, CS: CommitmentScheme<C, H>, const H: bool> NIFSTrait<C, CS, H>
27 for NIFS<C, CS, H>
28where
29 <C as Group>::ScalarField: Absorb,
30 <C as CurveGroup>::BaseField: PrimeField,
31{
32 type CommittedInstance = CommittedInstance<C>;
33 type Witness = Witness<C>;
34 type ProverAux = Vec<C::ScalarField>;
35 type VerifierAux = C;
36
37 fn new_witness(w: Vec<C::ScalarField>, e_len: usize, rng: impl RngCore) -> Self::Witness {
38 Witness::new::<H>(w, e_len, rng)
39 }
40
41 fn new_instance(
42 W: &Self::Witness,
43 params: &CS::ProverParams,
44 x: Vec<C::ScalarField>,
45 _aux: Vec<C::ScalarField>,
46 ) -> Result<Self::CommittedInstance, Error> {
47 W.commit::<CS, H>(params, x)
48 }
49
50 fn fold_witness(
51 r: C::ScalarField,
52 W_i: &Self::Witness,
53 w_i: &Self::Witness,
54 aux: &Self::ProverAux,
55 ) -> Result<Self::Witness, Error> {
56 let r2 = r * r;
57 let E: Vec<C::ScalarField> = vec_add(
58 &vec_add(&W_i.E, &vec_scalar_mul(aux, &r))?, // aux is Nova's T
59 &vec_scalar_mul(&w_i.E, &r2),
60 )?;
61 // use r_T=0 since we don't need hiding property for cm(T)
62 let rT = C::ScalarField::zero();
63 let rE = W_i.rE + r * rT + r2 * w_i.rE;
64 let W: Vec<C::ScalarField> = W_i
65 .W
66 .iter()
67 .zip(&w_i.W)
68 .map(|(a, b)| *a + (r * b))
69 .collect();
70
71 let rW = W_i.rW + r * w_i.rW;
72 Ok(Self::Witness { E, rE, W, rW })
73 }
74
75 fn compute_aux(
76 cs_prover_params: &CS::ProverParams,
77 r1cs: &R1CS<C::ScalarField>,
78 W_i: &Self::Witness,
79 U_i: &Self::CommittedInstance,
80 w_i: &Self::Witness,
81 u_i: &Self::CommittedInstance,
82 ) -> Result<(Self::ProverAux, Self::VerifierAux), Error> {
83 let z1: Vec<C::ScalarField> = [vec![U_i.u], U_i.x.to_vec(), W_i.W.to_vec()].concat();
84 let z2: Vec<C::ScalarField> = [vec![u_i.u], u_i.x.to_vec(), w_i.W.to_vec()].concat();
85
86 // compute cross terms
87 let T = Self::compute_T(r1cs, U_i.u, u_i.u, &z1, &z2)?;
88 // use r_T=0 since we don't need hiding property for cm(T)
89 let cmT = CS::commit(cs_prover_params, &T, &C::ScalarField::zero())?;
90 Ok((T, cmT))
91 }
92
93 fn get_challenge<T: Transcript<C::ScalarField>>(
94 transcript: &mut T,
95 pp_hash: C::ScalarField, // public params hash
96 U_i: &Self::CommittedInstance,
97 u_i: &Self::CommittedInstance,
98 aux: &Self::VerifierAux, // cmT
99 ) -> Vec<bool> {
100 ChallengeGadget::<C, Self::CommittedInstance>::get_challenge_native(
101 transcript,
102 pp_hash,
103 U_i,
104 u_i,
105 Some(aux),
106 )
107 }
108
109 // Notice: `prove` method is implemented at the trait level.
110
111 fn verify(
112 // r comes from the transcript, and is a n-bit (N_BITS_CHALLENGE) element
113 r: C::ScalarField,
114 U_i: &Self::CommittedInstance,
115 u_i: &Self::CommittedInstance,
116 cmT: &C, // VerifierAux
117 ) -> Self::CommittedInstance {
118 let r2 = r * r;
119 let cmE = U_i.cmE + cmT.mul(r) + u_i.cmE.mul(r2);
120 let u = U_i.u + r * u_i.u;
121 let cmW = U_i.cmW + u_i.cmW.mul(r);
122 let x = U_i
123 .x
124 .iter()
125 .zip(&u_i.x)
126 .map(|(a, b)| *a + (r * b))
127 .collect::<Vec<C::ScalarField>>();
128
129 Self::CommittedInstance { cmE, u, cmW, x }
130 }
131}
132
133impl<C: CurveGroup, CS: CommitmentScheme<C, H>, const H: bool> NIFS<C, CS, H>
134where
135 <C as Group>::ScalarField: Absorb,
136 <C as CurveGroup>::BaseField: PrimeField,
137{
138 /// compute_T: compute cross-terms T
139 pub fn compute_T(
140 r1cs: &R1CS<C::ScalarField>,
141 u1: C::ScalarField,
142 u2: C::ScalarField,
143 z1: &[C::ScalarField],
144 z2: &[C::ScalarField],
145 ) -> Result<Vec<C::ScalarField>, Error> {
146 let (A, B, C) = (r1cs.A.clone(), r1cs.B.clone(), r1cs.C.clone());
147
148 // this is parallelizable (for the future)
149 let Az1 = mat_vec_mul(&A, z1)?;
150 let Bz1 = mat_vec_mul(&B, z1)?;
151 let Cz1 = mat_vec_mul(&C, z1)?;
152 let Az2 = mat_vec_mul(&A, z2)?;
153 let Bz2 = mat_vec_mul(&B, z2)?;
154 let Cz2 = mat_vec_mul(&C, z2)?;
155
156 let Az1_Bz2 = hadamard(&Az1, &Bz2)?;
157 let Az2_Bz1 = hadamard(&Az2, &Bz1)?;
158 let u1Cz2 = vec_scalar_mul(&Cz2, &u1);
159 let u2Cz1 = vec_scalar_mul(&Cz1, &u2);
160
161 vec_sub(&vec_sub(&vec_add(&Az1_Bz2, &Az2_Bz1)?, &u1Cz2)?, &u2Cz1)
162 }
163
164 /// In Nova, NIFS.P is the consecutive combination of compute_cmT with fold_instances,
165 /// ie. compute_cmT is part of the NIFS.P logic.
166 pub fn compute_cmT(
167 cs_prover_params: &CS::ProverParams,
168 r1cs: &R1CS<C::ScalarField>,
169 w1: &Witness<C>,
170 ci1: &CommittedInstance<C>,
171 w2: &Witness<C>,
172 ci2: &CommittedInstance<C>,
173 ) -> Result<(Vec<C::ScalarField>, C), Error> {
174 let z1: Vec<C::ScalarField> = [vec![ci1.u], ci1.x.to_vec(), w1.W.to_vec()].concat();
175 let z2: Vec<C::ScalarField> = [vec![ci2.u], ci2.x.to_vec(), w2.W.to_vec()].concat();
176
177 // compute cross terms
178 let T = Self::compute_T(r1cs, ci1.u, ci2.u, &z1, &z2)?;
179 // use r_T=0 since we don't need hiding property for cm(T)
180 let cmT = CS::commit(cs_prover_params, &T, &C::ScalarField::zero())?;
181 Ok((T, cmT))
182 }
183
184 pub fn compute_cyclefold_cmT(
185 cs_prover_params: &CS::ProverParams,
186 r1cs: &R1CS<C::ScalarField>, // R1CS over C2.Fr=C1.Fq (here C=C2)
187 w1: &CycleFoldWitness<C>,
188 ci1: &CycleFoldCommittedInstance<C>,
189 w2: &CycleFoldWitness<C>,
190 ci2: &CycleFoldCommittedInstance<C>,
191 ) -> Result<(Vec<C::ScalarField>, C), Error>
192 where
193 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
194 {
195 let z1: Vec<C::ScalarField> = [vec![ci1.u], ci1.x.to_vec(), w1.W.to_vec()].concat();
196 let z2: Vec<C::ScalarField> = [vec![ci2.u], ci2.x.to_vec(), w2.W.to_vec()].concat();
197
198 // compute cross terms
199 let T = Self::compute_T(r1cs, ci1.u, ci2.u, &z1, &z2)?;
200 // use r_T=0 since we don't need hiding property for cm(T)
201 let cmT = CS::commit(cs_prover_params, &T, &C::ScalarField::zero())?;
202 Ok((T, cmT))
203 }
204
205 /// Verify committed folded instance (ci) relations. Notice that this method does not open the
206 /// commitments, but just checks that the given committed instances (ci1, ci2) when folded
207 /// result in the folded committed instance (ci3) values.
208 pub fn verify_folded_instance(
209 r: C::ScalarField,
210 ci1: &CommittedInstance<C>,
211 ci2: &CommittedInstance<C>,
212 ci3: &CommittedInstance<C>,
213 cmT: &C,
214 ) -> Result<(), Error> {
215 let expected = Self::verify(r, ci1, ci2, cmT);
216 if ci3.cmE != expected.cmE
217 || ci3.u != expected.u
218 || ci3.cmW != expected.cmW
219 || ci3.x != expected.x
220 {
221 return Err(Error::NotSatisfied);
222 }
223 Ok(())
224 }
225
226 pub fn prove_commitments(
227 tr: &mut impl Transcript<C::ScalarField>,
228 cs_prover_params: &CS::ProverParams,
229 w: &Witness<C>,
230 ci: &CommittedInstance<C>,
231 T: Vec<C::ScalarField>,
232 cmT: &C,
233 ) -> Result<[CS::Proof; 3], Error> {
234 let cmE_proof = CS::prove(cs_prover_params, tr, &ci.cmE, &w.E, &w.rE, None)?;
235 let cmW_proof = CS::prove(cs_prover_params, tr, &ci.cmW, &w.W, &w.rW, None)?;
236 let cmT_proof = CS::prove(cs_prover_params, tr, cmT, &T, &C::ScalarField::zero(), None)?; // cm(T) is committed with rT=0
237 Ok([cmE_proof, cmW_proof, cmT_proof])
238 }
239}
240
241#[cfg(test)]
242pub mod tests {
243 use super::*;
244 use crate::transcript::poseidon::poseidon_canonical_config;
245 use ark_crypto_primitives::sponge::{poseidon::PoseidonSponge, CryptographicSponge};
246 use ark_ff::{BigInteger, PrimeField};
247 use ark_pallas::{Fr, Projective};
248 use ark_std::{test_rng, UniformRand};
249
250 use crate::arith::{
251 r1cs::tests::{get_test_r1cs, get_test_z},
252 Arith,
253 };
254 use crate::commitment::pedersen::Pedersen;
255 use crate::folding::nova::traits::NIFSTrait;
256
257 #[test]
258 fn test_nifs_nova() {
259 let (W, U) = test_nifs_opt::<NIFS<Projective, Pedersen<Projective>>>();
260
261 // check the last folded instance relation
262 let r1cs = get_test_r1cs();
263 r1cs.check_relation(&W, &U).unwrap();
264 }
265
266 /// runs a loop using the NIFS trait, and returns the last Witness and CommittedInstance so
267 /// that their relation can be checked.
268 pub(crate) fn test_nifs_opt<N: NIFSTrait<Projective, Pedersen<Projective>>>(
269 ) -> (N::Witness, N::CommittedInstance) {
270 let r1cs = get_test_r1cs();
271 let z = get_test_z(3);
272 let (w, x) = r1cs.split_z(&z);
273
274 let mut rng = ark_std::test_rng();
275 let (pedersen_params, _) = Pedersen::<Projective>::setup(&mut rng, r1cs.A.n_cols).unwrap();
276
277 let poseidon_config = poseidon_canonical_config::<Fr>();
278 let mut transcript = PoseidonSponge::<Fr>::new(&poseidon_config);
279 let pp_hash = Fr::rand(&mut rng);
280
281 // prepare the running instance
282 let mut running_witness = N::new_witness(w.clone(), r1cs.A.n_rows, test_rng());
283 let mut running_committed_instance =
284 N::new_instance(&running_witness, &pedersen_params, x, vec![]).unwrap();
285
286 let num_iters = 10;
287 for i in 0..num_iters {
288 // prepare the incoming instance
289 let incoming_instance_z = get_test_z(i + 4);
290 let (w, x) = r1cs.split_z(&incoming_instance_z);
291 let incoming_witness = N::new_witness(w.clone(), r1cs.A.n_rows, test_rng());
292 let incoming_committed_instance =
293 N::new_instance(&incoming_witness, &pedersen_params, x, vec![]).unwrap();
294
295 let (aux_p, aux_v) = N::compute_aux(
296 &pedersen_params,
297 &r1cs,
298 &running_witness,
299 &running_committed_instance,
300 &incoming_witness,
301 &incoming_committed_instance,
302 )
303 .unwrap();
304
305 let r_bits = N::get_challenge(
306 &mut transcript,
307 pp_hash,
308 &running_committed_instance,
309 &incoming_committed_instance,
310 &aux_v,
311 );
312 let r = Fr::from_bigint(BigInteger::from_bits_le(&r_bits)).unwrap();
313
314 // NIFS.P
315 let (folded_witness, _) = N::prove(
316 r,
317 &running_witness,
318 &running_committed_instance,
319 &incoming_witness,
320 &incoming_committed_instance,
321 &aux_p,
322 &aux_v,
323 )
324 .unwrap();
325
326 // NIFS.V
327 let folded_committed_instance = N::verify(
328 r,
329 &running_committed_instance,
330 &incoming_committed_instance,
331 &aux_v,
332 );
333
334 // set running_instance for next loop iteration
335 running_witness = folded_witness;
336 running_committed_instance = folded_committed_instance;
337 }
338
339 (running_witness, running_committed_instance)
340 }
341}