Nova/src/nifs.rs
src/nifs.rsRaw
1//! This module implements a non-interactive folding scheme
2#![allow(non_snake_case)]
3#![allow(clippy::type_complexity)]
4
5use super::{
6 commitments::CompressedCommitment,
7 constants::{NUM_CHALLENGE_BITS, NUM_FE_FOR_RO},
8 errors::NovaError,
9 r1cs::{R1CSGens, R1CSInstance, R1CSShape, R1CSWitness, RelaxedR1CSInstance, RelaxedR1CSWitness},
10 traits::{AbsorbInROTrait, Group, ROTrait},
11};
12use core::marker::PhantomData;
13use serde::{Deserialize, Serialize};
14
15/// A SNARK that holds the proof of a step of an incremental computation
16#[allow(clippy::upper_case_acronyms)]
17#[derive(Clone, Debug, Serialize, Deserialize)]
18pub struct NIFS<G: Group> {
19 pub(crate) comm_T: CompressedCommitment<G::CompressedGroupElement>,
20 _p: PhantomData<G>,
21}
22
23type ROConstants<G> =
24 <<G as Group>::RO as ROTrait<<G as Group>::Base, <G as Group>::Scalar>>::Constants;
25
26impl<G: Group> NIFS<G> {
27 /// Takes as input a Relaxed R1CS instance-witness tuple `(U1, W1)` and
28 /// an R1CS instance-witness tuple `(U2, W2)` with the same structure `shape`
29 /// and defined with respect to the same `gens`, and outputs
30 /// a folded Relaxed R1CS instance-witness tuple `(U, W)` of the same shape `shape`,
31 /// with the guarantee that the folded witness `W` satisfies the folded instance `U`
32 /// if and only if `W1` satisfies `U1` and `W2` satisfies `U2`.
33 pub fn prove(
34 gens: &R1CSGens<G>,
35 ro_consts: &ROConstants<G>,
36 S: &R1CSShape<G>,
37 U1: &RelaxedR1CSInstance<G>,
38 W1: &RelaxedR1CSWitness<G>,
39 U2: &R1CSInstance<G>,
40 W2: &R1CSWitness<G>,
41 ) -> Result<(NIFS<G>, (RelaxedR1CSInstance<G>, RelaxedR1CSWitness<G>)), NovaError> {
42 // initialize a new RO
43 let mut ro = G::RO::new(ro_consts.clone(), NUM_FE_FOR_RO);
44
45 // append S to the transcript
46 S.absorb_in_ro(&mut ro);
47
48 // append U1 and U2 to transcript
49 U1.absorb_in_ro(&mut ro);
50 U2.absorb_in_ro(&mut ro);
51
52 // compute a commitment to the cross-term
53 let (T, comm_T) = S.commit_T(gens, U1, W1, U2, W2)?;
54
55 // append `comm_T` to the transcript and obtain a challenge
56 comm_T.absorb_in_ro(&mut ro);
57
58 // compute a challenge from the RO
59 let r = ro.squeeze(NUM_CHALLENGE_BITS);
60
61 // fold the instance using `r` and `comm_T`
62 let U = U1.fold(U2, &comm_T, &r)?;
63
64 // fold the witness using `r` and `T`
65 let W = W1.fold(W2, &T, &r)?;
66
67 // return the folded instance and witness
68 Ok((
69 Self {
70 comm_T: comm_T.compress(),
71 _p: Default::default(),
72 },
73 (U, W),
74 ))
75 }
76
77 /// Takes as input a relaxed R1CS instance `U1` and and R1CS instance `U2`
78 /// with the same shape and defined with respect to the same parameters,
79 /// and outputs a folded instance `U` with the same shape,
80 /// with the guarantee that the folded instance `U`
81 /// if and only if `U1` and `U2` are satisfiable.
82 pub fn verify(
83 &self,
84 ro_consts: &ROConstants<G>,
85 S: &R1CSShape<G>,
86 U1: &RelaxedR1CSInstance<G>,
87 U2: &R1CSInstance<G>,
88 ) -> Result<RelaxedR1CSInstance<G>, NovaError> {
89 // initialize a new RO
90 let mut ro = G::RO::new(ro_consts.clone(), NUM_FE_FOR_RO);
91
92 // append S to the transcript
93 S.absorb_in_ro(&mut ro);
94
95 // append U1 and U2 to transcript
96 U1.absorb_in_ro(&mut ro);
97 U2.absorb_in_ro(&mut ro);
98
99 // append `comm_T` to the transcript and obtain a challenge
100 let comm_T = self.comm_T.decompress()?;
101 comm_T.absorb_in_ro(&mut ro);
102
103 // compute a challenge from the RO
104 let r = ro.squeeze(NUM_CHALLENGE_BITS);
105
106 // fold the instance using `r` and `comm_T`
107 let U = U1.fold(U2, &comm_T, &r)?;
108
109 // return the folded instance
110 Ok(U)
111 }
112}
113
114#[cfg(test)]
115mod tests {
116 use super::*;
117 use crate::traits::{Group, ROConstantsTrait};
118 use ::bellperson::{gadgets::num::AllocatedNum, ConstraintSystem, SynthesisError};
119 use ff::{Field, PrimeField};
120 use rand::rngs::OsRng;
121
122 type S = pasta_curves::pallas::Scalar;
123 type G = pasta_curves::pallas::Point;
124
125 fn synthesize_tiny_r1cs_bellperson<Scalar: PrimeField, CS: ConstraintSystem<Scalar>>(
126 cs: &mut CS,
127 x_val: Option<Scalar>,
128 ) -> Result<(), SynthesisError> {
129 // Consider a cubic equation: `x^3 + x + 5 = y`, where `x` and `y` are respectively the input and output.
130 let x = AllocatedNum::alloc(cs.namespace(|| "x"), || Ok(x_val.unwrap()))?;
131 let _ = x.inputize(cs.namespace(|| "x is input"));
132
133 let x_sq = x.square(cs.namespace(|| "x_sq"))?;
134 let x_cu = x_sq.mul(cs.namespace(|| "x_cu"), &x)?;
135 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
136 Ok(x_cu.get_value().unwrap() + x.get_value().unwrap() + Scalar::from(5u64))
137 })?;
138 let _ = y.inputize(cs.namespace(|| "y is output"));
139
140 cs.enforce(
141 || "y = x^3 + x + 5",
142 |lc| {
143 lc + x_cu.get_variable()
144 + x.get_variable()
145 + CS::one()
146 + CS::one()
147 + CS::one()
148 + CS::one()
149 + CS::one()
150 },
151 |lc| lc + CS::one(),
152 |lc| lc + y.get_variable(),
153 );
154
155 Ok(())
156 }
157
158 #[test]
159 fn test_tiny_r1cs_bellperson() {
160 use crate::bellperson::{
161 r1cs::{NovaShape, NovaWitness},
162 shape_cs::ShapeCS,
163 solver::SatisfyingAssignment,
164 };
165
166 // First create the shape
167 let mut cs: ShapeCS<G> = ShapeCS::new();
168 let _ = synthesize_tiny_r1cs_bellperson(&mut cs, None);
169 let shape = cs.r1cs_shape();
170 let gens = cs.r1cs_gens();
171 let ro_consts =
172 <<G as Group>::RO as ROTrait<<G as Group>::Base, <G as Group>::Scalar>>::Constants::new();
173
174 // Now get the instance and assignment for one instance
175 let mut cs: SatisfyingAssignment<G> = SatisfyingAssignment::new();
176 let _ = synthesize_tiny_r1cs_bellperson(&mut cs, Some(S::from(5)));
177 let (U1, W1) = cs.r1cs_instance_and_witness(&shape, &gens).unwrap();
178
179 // Make sure that the first instance is satisfiable
180 assert!(shape.is_sat(&gens, &U1, &W1).is_ok());
181
182 // Now get the instance and assignment for second instance
183 let mut cs: SatisfyingAssignment<G> = SatisfyingAssignment::new();
184 let _ = synthesize_tiny_r1cs_bellperson(&mut cs, Some(S::from(135)));
185 let (U2, W2) = cs.r1cs_instance_and_witness(&shape, &gens).unwrap();
186
187 // Make sure that the second instance is satisfiable
188 assert!(shape.is_sat(&gens, &U2, &W2).is_ok());
189
190 // execute a sequence of folds
191 execute_sequence(&gens, &ro_consts, &shape, &U1, &W1, &U2, &W2);
192 }
193
194 fn execute_sequence(
195 gens: &R1CSGens<G>,
196 ro_consts: &<<G as Group>::RO as ROTrait<<G as Group>::Base, <G as Group>::Scalar>>::Constants,
197 shape: &R1CSShape<G>,
198 U1: &R1CSInstance<G>,
199 W1: &R1CSWitness<G>,
200 U2: &R1CSInstance<G>,
201 W2: &R1CSWitness<G>,
202 ) {
203 // produce a default running instance
204 let mut r_W = RelaxedR1CSWitness::default(shape);
205 let mut r_U = RelaxedR1CSInstance::default(gens, shape);
206
207 // produce a step SNARK with (W1, U1) as the first incoming witness-instance pair
208 let res = NIFS::prove(gens, ro_consts, shape, &r_U, &r_W, U1, W1);
209 assert!(res.is_ok());
210 let (nifs, (_U, W)) = res.unwrap();
211
212 // verify the step SNARK with U1 as the first incoming instance
213 let res = nifs.verify(ro_consts, shape, &r_U, U1);
214 assert!(res.is_ok());
215 let U = res.unwrap();
216
217 assert_eq!(U, _U);
218
219 // update the running witness and instance
220 r_W = W;
221 r_U = U;
222
223 // produce a step SNARK with (W2, U2) as the second incoming witness-instance pair
224 let res = NIFS::prove(gens, ro_consts, shape, &r_U, &r_W, U2, W2);
225 assert!(res.is_ok());
226 let (nifs, (_U, W)) = res.unwrap();
227
228 // verify the step SNARK with U1 as the first incoming instance
229 let res = nifs.verify(ro_consts, shape, &r_U, U2);
230 assert!(res.is_ok());
231 let U = res.unwrap();
232
233 assert_eq!(U, _U);
234
235 // update the running witness and instance
236 r_W = W;
237 r_U = U;
238
239 // check if the running instance is satisfiable
240 assert!(shape.is_sat_relaxed(gens, &r_U, &r_W).is_ok());
241 }
242
243 #[test]
244 fn test_tiny_r1cs() {
245 let one = S::one();
246 let (num_cons, num_vars, num_io, A, B, C) = {
247 let num_cons = 4;
248 let num_vars = 4;
249 let num_io = 2;
250
251 // Consider a cubic equation: `x^3 + x + 5 = y`, where `x` and `y` are respectively the input and output.
252 // The R1CS for this problem consists of the following constraints:
253 // `I0 * I0 - Z0 = 0`
254 // `Z0 * I0 - Z1 = 0`
255 // `(Z1 + I0) * 1 - Z2 = 0`
256 // `(Z2 + 5) * 1 - I1 = 0`
257
258 // Relaxed R1CS is a set of three sparse matrices (A B C), where there is a row for every
259 // constraint and a column for every entry in z = (vars, u, inputs)
260 // An R1CS instance is satisfiable iff:
261 // Az \circ Bz = u \cdot Cz + E, where z = (vars, 1, inputs)
262 let mut A: Vec<(usize, usize, S)> = Vec::new();
263 let mut B: Vec<(usize, usize, S)> = Vec::new();
264 let mut C: Vec<(usize, usize, S)> = Vec::new();
265
266 // constraint 0 entries in (A,B,C)
267 // `I0 * I0 - Z0 = 0`
268 A.push((0, num_vars + 1, one));
269 B.push((0, num_vars + 1, one));
270 C.push((0, 0, one));
271
272 // constraint 1 entries in (A,B,C)
273 // `Z0 * I0 - Z1 = 0`
274 A.push((1, 0, one));
275 B.push((1, num_vars + 1, one));
276 C.push((1, 1, one));
277
278 // constraint 2 entries in (A,B,C)
279 // `(Z1 + I0) * 1 - Z2 = 0`
280 A.push((2, 1, one));
281 A.push((2, num_vars + 1, one));
282 B.push((2, num_vars, one));
283 C.push((2, 2, one));
284
285 // constraint 3 entries in (A,B,C)
286 // `(Z2 + 5) * 1 - I1 = 0`
287 A.push((3, 2, one));
288 A.push((3, num_vars, one + one + one + one + one));
289 B.push((3, num_vars, one));
290 C.push((3, num_vars + 2, one));
291
292 (num_cons, num_vars, num_io, A, B, C)
293 };
294
295 // create a shape object
296 let S = {
297 let res = R1CSShape::new(num_cons, num_vars, num_io, &A, &B, &C);
298 assert!(res.is_ok());
299 res.unwrap()
300 };
301
302 // generate generators and ro constants
303 let gens = R1CSGens::new(num_cons, num_vars);
304 let ro_consts =
305 <<G as Group>::RO as ROTrait<<G as Group>::Base, <G as Group>::Scalar>>::Constants::new();
306
307 let rand_inst_witness_generator =
308 |gens: &R1CSGens<G>, I: &S| -> (S, R1CSInstance<G>, R1CSWitness<G>) {
309 let i0 = *I;
310
311 // compute a satisfying (vars, X) tuple
312 let (O, vars, X) = {
313 let z0 = i0 * i0; // constraint 0
314 let z1 = i0 * z0; // constraint 1
315 let z2 = z1 + i0; // constraint 2
316 let i1 = z2 + one + one + one + one + one; // constraint 3
317
318 // store the witness and IO for the instance
319 let W = vec![z0, z1, z2, S::zero()];
320 let X = vec![i0, i1];
321 (i1, W, X)
322 };
323
324 let W = {
325 let res = R1CSWitness::new(&S, &vars);
326 assert!(res.is_ok());
327 res.unwrap()
328 };
329 let U = {
330 let comm_W = W.commit(gens);
331 let res = R1CSInstance::new(&S, &comm_W, &X);
332 assert!(res.is_ok());
333 res.unwrap()
334 };
335
336 // check that generated instance is satisfiable
337 assert!(S.is_sat(gens, &U, &W).is_ok());
338
339 (O, U, W)
340 };
341
342 let mut csprng: OsRng = OsRng;
343 let I = S::random(&mut csprng); // the first input is picked randomly for the first instance
344 let (O, U1, W1) = rand_inst_witness_generator(&gens, &I);
345 let (_O, U2, W2) = rand_inst_witness_generator(&gens, &O);
346
347 // execute a sequence of folds
348 execute_sequence(&gens, &ro_consts, &S, &U1, &W1, &U2, &W2);
349 }
350}