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