sonobe/folding-schemes/src/folding/nova/nifs/mod.rs
folding-schemes/src/folding/nova/nifs/mod.rsRaw
1/// This module defines the traits related to the NIFS (Non-Interactive Folding Scheme).
2/// - NIFSTrait, which implements the NIFS interface
3/// - NIFSGadget, which implements the NIFS in-circuit
4/// both traits implemented by the various Nova variants schemes; ie.
5/// [Nova](https://eprint.iacr.org/2021/370.pdf), [Ova](https://hackmd.io/V4838nnlRKal9ZiTHiGYzw),
6/// [Mova](https://eprint.iacr.org/2024/1220.pdf).
7use ark_crypto_primitives::sponge::{constraints::AbsorbGadget, Absorb, CryptographicSponge};
8use ark_ec::CurveGroup;
9use ark_r1cs_std::{alloc::AllocVar, boolean::Boolean, fields::fp::FpVar};
10use ark_relations::r1cs::SynthesisError;
11use ark_std::fmt::Debug;
12use ark_std::rand::RngCore;
13
14use crate::arith::r1cs::R1CS;
15use crate::commitment::CommitmentScheme;
16use crate::folding::circuits::CF1;
17use crate::folding::traits::{CommittedInstanceOps, CommittedInstanceVarOps};
18use crate::transcript::{Transcript, TranscriptVar};
19use crate::Error;
20
21pub mod mova;
22pub mod nova;
23pub mod nova_circuits;
24pub mod ova;
25pub mod ova_circuits;
26pub mod pointvsline;
27
28/// Defines the NIFS (Non-Interactive Folding Scheme) trait, initially defined in
29/// [Nova](https://eprint.iacr.org/2021/370.pdf), and it's variants
30/// [Ova](https://hackmd.io/V4838nnlRKal9ZiTHiGYzw) and
31/// [Mova](https://eprint.iacr.org/2024/1220.pdf).
32/// `H` specifies whether the NIFS will use a blinding factor.
33pub trait NIFSTrait<
34 C: CurveGroup,
35 CS: CommitmentScheme<C, H>,
36 T: Transcript<C::ScalarField>,
37 const H: bool = false,
38>
39{
40 type CommittedInstance: Debug + Clone + Absorb; // + CommittedInstanceOps<C>;
41 type Witness: Debug + Clone;
42 type ProverAux: Debug + Clone; // Prover's aux params. eg. in Nova is T
43 type Proof: Debug + Clone; // proof. eg. in Nova is cmT
44
45 fn new_witness(w: Vec<C::ScalarField>, e_len: usize, rng: impl RngCore) -> Self::Witness;
46
47 fn new_instance(
48 rng: impl RngCore,
49 params: &CS::ProverParams,
50 w: &Self::Witness,
51 x: Vec<C::ScalarField>,
52 aux: Vec<C::ScalarField>, // t_or_e in Ova, empty for Nova
53 ) -> Result<Self::CommittedInstance, Error>;
54
55 fn fold_witness(
56 r: C::ScalarField,
57 W: &Self::Witness, // running witness
58 w: &Self::Witness, // incoming witness
59 aux: &Self::ProverAux,
60 ) -> Result<Self::Witness, Error>;
61
62 /// NIFS.P. Returns a tuple containing the folded Witness, the folded CommittedInstance, and
63 /// the used challenge `r` as a vector of bits, so that it can be reused in other methods.
64 #[allow(clippy::type_complexity)]
65 #[allow(clippy::too_many_arguments)]
66 fn prove(
67 cs_prover_params: &CS::ProverParams,
68 r1cs: &R1CS<C::ScalarField>,
69 transcript: &mut T,
70 pp_hash: C::ScalarField,
71 W_i: &Self::Witness, // running witness
72 U_i: &Self::CommittedInstance, // running committed instance
73 w_i: &Self::Witness, // incoming witness
74 u_i: &Self::CommittedInstance, // incoming committed instance
75 ) -> Result<
76 (
77 Self::Witness,
78 Self::CommittedInstance,
79 Self::Proof,
80 Vec<bool>,
81 ),
82 Error,
83 >;
84
85 /// NIFS.V. Returns the folded CommittedInstance and the used challenge `r` as a vector of
86 /// bits, so that it can be reused in other methods.
87 fn verify(
88 transcript: &mut T,
89 pp_hash: C::ScalarField,
90 U_i: &Self::CommittedInstance,
91 u_i: &Self::CommittedInstance,
92 proof: &Self::Proof,
93 ) -> Result<(Self::CommittedInstance, Vec<bool>), Error>;
94}
95
96/// Defines the NIFS (Non-Interactive Folding Scheme) Gadget trait, which specifies the in-circuit
97/// logic of the NIFS.Verify defined in [Nova](https://eprint.iacr.org/2021/370.pdf) and it's
98/// variants [Ova](https://hackmd.io/V4838nnlRKal9ZiTHiGYzw) and
99/// [Mova](https://eprint.iacr.org/2024/1220.pdf).
100pub trait NIFSGadgetTrait<C: CurveGroup, S: CryptographicSponge, T: TranscriptVar<CF1<C>, S>> {
101 type CommittedInstance: Debug + Clone + Absorb + CommittedInstanceOps<C>;
102 type CommittedInstanceVar: Debug
103 + Clone
104 + AbsorbGadget<C::ScalarField>
105 + AllocVar<Self::CommittedInstance, CF1<C>>
106 + CommittedInstanceVarOps<C>;
107 type Proof: Debug + Clone;
108 type ProofVar: Debug + Clone + AllocVar<Self::Proof, CF1<C>>;
109
110 /// Implements the constraints for NIFS.V for u and x, since cm(E) and cm(W) are delegated to
111 /// the CycleFold circuit.
112 #[allow(clippy::type_complexity)]
113 fn verify(
114 transcript: &mut T,
115 pp_hash: FpVar<CF1<C>>,
116 U_i: Self::CommittedInstanceVar,
117 // U_i_vec is passed to reuse the already computed U_i_vec from previous methods
118 U_i_vec: Vec<FpVar<CF1<C>>>,
119 u_i: Self::CommittedInstanceVar,
120 proof: Option<Self::ProofVar>,
121 ) -> Result<(Self::CommittedInstanceVar, Vec<Boolean<CF1<C>>>), SynthesisError>;
122}
123
124/// These tests are the generic tests so that in the tests of Nova, Mova, Ova, we just need to
125/// instantiate these tests to test both the NIFSTrait and NIFSGadgetTrait implementations for each
126/// of the schemes.
127#[cfg(test)]
128pub mod tests {
129 use ark_crypto_primitives::sponge::{
130 constraints::{AbsorbGadget, CryptographicSpongeVar},
131 poseidon::constraints::PoseidonSpongeVar,
132 Absorb,
133 };
134 use ark_crypto_primitives::sponge::{poseidon::PoseidonSponge, CryptographicSponge};
135 use ark_pallas::{Fr, Projective};
136 use ark_r1cs_std::{alloc::AllocVar, fields::fp::FpVar, R1CSVar};
137 use ark_relations::r1cs::ConstraintSystem;
138 use ark_std::{test_rng, UniformRand};
139
140 use super::NIFSTrait;
141 use super::*;
142 use crate::arith::r1cs::tests::{get_test_r1cs, get_test_z};
143 use crate::commitment::pedersen::Pedersen;
144 use crate::folding::traits::{CommittedInstanceOps, CommittedInstanceVarOps};
145 use crate::transcript::poseidon::poseidon_canonical_config;
146
147 /// Test method used to test the different implementations of the NIFSTrait (ie. Nova, Mova,
148 /// Ova). Runs a loop using the NIFS trait, and returns the last Witness and CommittedInstance
149 /// so that their relation can be checked.
150 pub(crate) fn test_nifs_opt<
151 N: NIFSTrait<Projective, Pedersen<Projective>, PoseidonSponge<Fr>>,
152 >() -> (N::Witness, N::CommittedInstance) {
153 let r1cs: R1CS<Fr> = get_test_r1cs();
154
155 let mut rng = ark_std::test_rng();
156 let (pedersen_params, _) = Pedersen::<Projective>::setup(&mut rng, r1cs.A.n_cols).unwrap();
157
158 let poseidon_config = poseidon_canonical_config::<Fr>();
159 let mut transcript_p = PoseidonSponge::<Fr>::new(&poseidon_config);
160 let mut transcript_v = PoseidonSponge::<Fr>::new(&poseidon_config);
161 let pp_hash = Fr::rand(&mut rng);
162
163 // prepare the running instance
164 let z = get_test_z(3);
165 let (w, x) = r1cs.split_z(&z);
166 let mut W_i = N::new_witness(w.clone(), r1cs.A.n_rows, test_rng());
167 let mut U_i = N::new_instance(&mut rng, &pedersen_params, &W_i, x, vec![]).unwrap();
168
169 let num_iters = 10;
170 for i in 0..num_iters {
171 // prepare the incoming instance
172 let incoming_instance_z = get_test_z(i + 4);
173 let (w, x) = r1cs.split_z(&incoming_instance_z);
174 let w_i = N::new_witness(w.clone(), r1cs.A.n_rows, test_rng());
175 let u_i = N::new_instance(&mut rng, &pedersen_params, &w_i, x, vec![]).unwrap();
176
177 // NIFS.P
178 let (folded_witness, _, proof, _) = N::prove(
179 &pedersen_params,
180 &r1cs,
181 &mut transcript_p,
182 pp_hash,
183 &W_i,
184 &U_i,
185 &w_i,
186 &u_i,
187 )
188 .unwrap();
189
190 // NIFS.V
191 let (folded_committed_instance, _) =
192 N::verify(&mut transcript_v, pp_hash, &U_i, &u_i, &proof).unwrap();
193
194 // set running_instance for next loop iteration
195 W_i = folded_witness;
196 U_i = folded_committed_instance;
197 }
198
199 (W_i, U_i)
200 }
201
202 /// Test method used to test the different implementations of the NIFSGadgetTrait (ie. Nova,
203 /// Mova, Ova). It returns the last Witness and CommittedInstance so that it can be checked at
204 /// the parent test that their values match.
205 pub(crate) fn test_nifs_gadget_opt<N, NG>(
206 ci: Vec<NG::CommittedInstance>,
207 proof: NG::Proof,
208 ) -> Result<(NG::CommittedInstance, NG::CommittedInstanceVar), Error>
209 where
210 N: NIFSTrait<Projective, Pedersen<Projective>, PoseidonSponge<Fr>>,
211 NG: NIFSGadgetTrait<
212 Projective,
213 PoseidonSponge<Fr>,
214 PoseidonSpongeVar<Fr>,
215 CommittedInstance = N::CommittedInstance, // constrain that N::CI==NG::CI
216 Proof = N::Proof, // constrain that N::Proof==NG::Proof
217 >,
218 {
219 let mut rng = ark_std::test_rng();
220
221 let (U_i, u_i) = (ci[0].clone(), ci[1].clone());
222 let pp_hash = Fr::rand(&mut rng);
223 let poseidon_config = poseidon_canonical_config::<Fr>();
224 let mut transcript = PoseidonSponge::<Fr>::new(&poseidon_config);
225 let (ci3, _) = N::verify(&mut transcript, pp_hash, &U_i, &u_i, &proof)?;
226
227 let cs = ConstraintSystem::<Fr>::new_ref();
228
229 let mut transcriptVar = PoseidonSpongeVar::<Fr>::new(cs.clone(), &poseidon_config);
230 let pp_hashVar = FpVar::<Fr>::new_witness(cs.clone(), || Ok(pp_hash))?;
231 let ci1Var = NG::CommittedInstanceVar::new_witness(cs.clone(), || Ok(U_i.clone()))?;
232 let ci2Var = NG::CommittedInstanceVar::new_witness(cs.clone(), || Ok(u_i.clone()))?;
233 let proofVar = NG::ProofVar::new_witness(cs.clone(), || Ok(proof))?;
234
235 let ci1Var_vec = ci1Var.to_sponge_field_elements()?;
236 let (out, _) = NG::verify(
237 &mut transcriptVar,
238 pp_hashVar,
239 ci1Var.clone(),
240 ci1Var_vec,
241 ci2Var.clone(),
242 Some(proofVar.clone()),
243 )?;
244 assert!(cs.is_satisfied()?);
245
246 // return the NIFS.V and the NIFSGadget.V obtained values, so that they are checked at the
247 // parent test
248 Ok((ci3, out))
249 }
250
251 /// test that checks the native CommittedInstance.to_sponge_{bytes,field_elements}
252 /// vs the R1CS constraints version
253 pub(crate) fn test_committed_instance_to_sponge_preimage_opt<N, NG>(ci: N::CommittedInstance)
254 where
255 N: NIFSTrait<Projective, Pedersen<Projective>, PoseidonSponge<Fr>>,
256 NG: NIFSGadgetTrait<
257 Projective,
258 PoseidonSponge<Fr>,
259 PoseidonSpongeVar<Fr>,
260 CommittedInstance = N::CommittedInstance, // constrain that N::CI==NG::CI
261 >,
262 {
263 let bytes = ci.to_sponge_bytes_as_vec();
264 let field_elements = ci.to_sponge_field_elements_as_vec();
265
266 let cs = ConstraintSystem::<Fr>::new_ref();
267
268 let ciVar = NG::CommittedInstanceVar::new_witness(cs.clone(), || Ok(ci.clone())).unwrap();
269 let bytes_var = ciVar.to_sponge_bytes().unwrap();
270 let field_elements_var = ciVar.to_sponge_field_elements().unwrap();
271
272 assert!(cs.is_satisfied().unwrap());
273
274 // check that the natively computed and in-circuit computed hashes match
275 assert_eq!(bytes_var.value().unwrap(), bytes);
276 assert_eq!(field_elements_var.value().unwrap(), field_elements);
277 }
278
279 pub(crate) fn test_committed_instance_hash_opt<N, NG>(ci: NG::CommittedInstance)
280 where
281 N: NIFSTrait<Projective, Pedersen<Projective>, PoseidonSponge<Fr>>,
282 NG: NIFSGadgetTrait<
283 Projective,
284 PoseidonSponge<Fr>,
285 PoseidonSpongeVar<Fr>,
286 CommittedInstance = N::CommittedInstance, // constrain that N::CI==NG::CI
287 >,
288 N::CommittedInstance: CommittedInstanceOps<Projective>,
289 {
290 let poseidon_config = poseidon_canonical_config::<Fr>();
291 let sponge = PoseidonSponge::<Fr>::new(&poseidon_config);
292 let pp_hash = Fr::from(42u32); // only for test
293
294 let i = Fr::from(3_u32);
295 let z_0 = vec![Fr::from(3_u32)];
296 let z_i = vec![Fr::from(3_u32)];
297
298 // compute the CommittedInstance hash natively
299 let h = ci.hash(&sponge, pp_hash, i, &z_0, &z_i);
300
301 let cs = ConstraintSystem::<Fr>::new_ref();
302
303 let pp_hashVar = FpVar::<Fr>::new_witness(cs.clone(), || Ok(pp_hash)).unwrap();
304 let iVar = FpVar::<Fr>::new_witness(cs.clone(), || Ok(i)).unwrap();
305 let z_0Var = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(z_0.clone())).unwrap();
306 let z_iVar = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(z_i.clone())).unwrap();
307 let ciVar = NG::CommittedInstanceVar::new_witness(cs.clone(), || Ok(ci.clone())).unwrap();
308
309 let sponge = PoseidonSpongeVar::<Fr>::new(cs.clone(), &poseidon_config);
310
311 // compute the CommittedInstance hash in-circuit
312 let (hVar, _) = ciVar
313 .hash(&sponge, &pp_hashVar, &iVar, &z_0Var, &z_iVar)
314 .unwrap();
315 assert!(cs.is_satisfied().unwrap());
316
317 // check that the natively computed and in-circuit computed hashes match
318 assert_eq!(hVar.value().unwrap(), h);
319 }
320}