Nova/src/r1cs.rs
src/r1cs.rsRaw
1//! This module defines R1CS related types and a folding scheme for Relaxed R1CS
2#![allow(clippy::type_complexity)]
3use super::commitments::{CommitGens, CommitTrait, Commitment, CompressedCommitment};
4use super::errors::NovaError;
5use super::traits::{Group, PrimeField};
6use itertools::concat;
7use rayon::prelude::*;
8
9/// Public parameters for a given R1CS
10pub struct R1CSGens<G: Group> {
11 gens_W: CommitGens<G>,
12 gens_E: CommitGens<G>,
13}
14
15/// A type that holds the shape of the R1CS matrices
16#[derive(Debug)]
17pub struct R1CSShape<G: Group> {
18 num_cons: usize,
19 num_vars: usize,
20 num_io: usize,
21 A: Vec<(usize, usize, G::Scalar)>,
22 B: Vec<(usize, usize, G::Scalar)>,
23 C: Vec<(usize, usize, G::Scalar)>,
24}
25
26/// A type that holds a witness for a given R1CS instance
27#[derive(Clone, Debug)]
28pub struct R1CSWitness<G: Group> {
29 W: Vec<G::Scalar>,
30}
31
32/// A type that holds an R1CS instance
33#[derive(Clone, Debug, PartialEq, Eq)]
34pub struct R1CSInstance<G: Group> {
35 comm_W: Commitment<G>,
36 X: Vec<G::Scalar>,
37}
38
39/// A type that holds a witness for a given Relaxed R1CS instance
40#[derive(Clone, Debug)]
41pub struct RelaxedR1CSWitness<G: Group> {
42 W: Vec<G::Scalar>,
43 E: Vec<G::Scalar>,
44}
45
46/// A type that holds a Relaxed R1CS instance
47#[derive(Clone, Debug, PartialEq, Eq)]
48pub struct RelaxedR1CSInstance<G: Group> {
49 comm_W: Commitment<G>,
50 comm_E: Commitment<G>,
51 X: Vec<G::Scalar>,
52 u: G::Scalar,
53 Y_last: Vec<G::Scalar>, // output of the last instance that was folded
54 counter: usize, // the number of folds thus far
55}
56
57impl<G: Group> R1CSGens<G> {
58 /// Samples public parameters for the specified number of constraints and variables in an R1CS
59 pub fn new(num_cons: usize, num_vars: usize) -> R1CSGens<G> {
60 // generators to commit to witness vector `W`
61 let gens_W = CommitGens::new(b"gens_W", num_vars);
62
63 // generators to commit to the error/slack vector `E`
64 let gens_E = CommitGens::new(b"gens_E", num_cons);
65
66 R1CSGens { gens_E, gens_W }
67 }
68}
69
70impl<G: Group> R1CSShape<G> {
71 /// Create an object of type `R1CSShape` from the explicitly specified R1CS matrices
72 pub fn new(
73 num_cons: usize,
74 num_vars: usize,
75 num_io: usize,
76 A: &[(usize, usize, G::Scalar)],
77 B: &[(usize, usize, G::Scalar)],
78 C: &[(usize, usize, G::Scalar)],
79 ) -> Result<R1CSShape<G>, NovaError> {
80 let is_valid = |num_cons: usize,
81 num_vars: usize,
82 num_io: usize,
83 M: &[(usize, usize, G::Scalar)]|
84 -> Result<(), NovaError> {
85 let res = (0..num_cons)
86 .map(|i| {
87 let (row, col, _val) = M[i];
88 if row >= num_cons || col > num_io + num_vars {
89 Err(NovaError::InvalidIndex)
90 } else {
91 Ok(())
92 }
93 })
94 .collect::<Result<Vec<()>, NovaError>>();
95
96 if res.is_err() {
97 Err(NovaError::InvalidIndex)
98 } else {
99 Ok(())
100 }
101 };
102
103 let res_A = is_valid(num_cons, num_vars, num_io, A);
104 let res_B = is_valid(num_cons, num_vars, num_io, B);
105 let res_C = is_valid(num_cons, num_vars, num_io, C);
106
107 if res_A.is_err() || res_B.is_err() || res_C.is_err() {
108 return Err(NovaError::InvalidIndex);
109 }
110
111 // We require the number of public inputs/outputs to be even
112 if num_io % 2 != 0 {
113 return Err(NovaError::OddInputLength);
114 }
115
116 let shape = R1CSShape {
117 num_cons,
118 num_vars,
119 num_io,
120 A: A.to_owned(),
121 B: B.to_owned(),
122 C: C.to_owned(),
123 };
124
125 Ok(shape)
126 }
127
128 fn multiply_vec(
129 &self,
130 z: &[G::Scalar],
131 ) -> Result<(Vec<G::Scalar>, Vec<G::Scalar>, Vec<G::Scalar>), NovaError> {
132 if z.len() != self.num_io + self.num_vars + 1 {
133 return Err(NovaError::InvalidWitnessLength);
134 }
135
136 // computes a product between a sparse matrix `M` and a vector `z`
137 // This does not perform any validation of entries in M (e.g., if entries in `M` reference indexes outside the range of `z`)
138 // This is safe since we know that `M` is valid
139 let sparse_matrix_vec_product =
140 |M: &Vec<(usize, usize, G::Scalar)>, num_rows: usize, z: &[G::Scalar]| -> Vec<G::Scalar> {
141 (0..M.len())
142 .map(|i| {
143 let (row, col, val) = M[i];
144 (row, val * z[col])
145 })
146 .fold(vec![G::Scalar::zero(); num_rows], |mut Mz, (r, v)| {
147 Mz[r] += v;
148 Mz
149 })
150 };
151
152 let Az = sparse_matrix_vec_product(&self.A, self.num_cons, z);
153 let Bz = sparse_matrix_vec_product(&self.B, self.num_cons, z);
154 let Cz = sparse_matrix_vec_product(&self.C, self.num_cons, z);
155
156 Ok((Az, Bz, Cz))
157 }
158
159 /// Checks if the Relaxed R1CS instance is satisfiable given a witness and its shape
160 pub fn is_sat_relaxed(
161 &self,
162 gens: &R1CSGens<G>,
163 U: &RelaxedR1CSInstance<G>,
164 W: &RelaxedR1CSWitness<G>,
165 ) -> Result<(), NovaError> {
166 assert_eq!(W.W.len(), self.num_vars);
167 assert_eq!(W.E.len(), self.num_cons);
168 assert_eq!(U.X.len(), self.num_io);
169
170 // verify if Az * Bz = u*Cz + E
171 let res_eq: bool = {
172 let z = concat(vec![W.W.clone(), vec![U.u], U.X.clone()]);
173 let (Az, Bz, Cz) = self.multiply_vec(&z)?;
174 assert_eq!(Az.len(), self.num_cons);
175 assert_eq!(Bz.len(), self.num_cons);
176 assert_eq!(Cz.len(), self.num_cons);
177
178 let res: usize = (0..self.num_cons)
179 .map(|i| {
180 if Az[i] * Bz[i] == U.u * Cz[i] + W.E[i] {
181 0
182 } else {
183 1
184 }
185 })
186 .sum();
187
188 res == 0
189 };
190
191 // verify if comm_E and comm_W are commitments to E and W
192 let res_comm: bool = {
193 let comm_W = W.W.commit(&gens.gens_W);
194 let comm_E = W.E.commit(&gens.gens_E);
195
196 U.comm_W == comm_W && U.comm_E == comm_E
197 };
198
199 if res_eq && res_comm {
200 Ok(())
201 } else {
202 Err(NovaError::UnSat)
203 }
204 }
205
206 /// Checks if the R1CS instance is satisfiable given a witness and its shape
207 pub fn is_sat(
208 &self,
209 gens: &R1CSGens<G>,
210 U: &R1CSInstance<G>,
211 W: &R1CSWitness<G>,
212 ) -> Result<(), NovaError> {
213 assert_eq!(W.W.len(), self.num_vars);
214 assert_eq!(U.X.len(), self.num_io);
215
216 // verify if Az * Bz = u*Cz
217 let res_eq: bool = {
218 let z = concat(vec![W.W.clone(), vec![G::Scalar::one()], U.X.clone()]);
219 let (Az, Bz, Cz) = self.multiply_vec(&z)?;
220 assert_eq!(Az.len(), self.num_cons);
221 assert_eq!(Bz.len(), self.num_cons);
222 assert_eq!(Cz.len(), self.num_cons);
223
224 let res: usize = (0..self.num_cons)
225 .map(|i| if Az[i] * Bz[i] == Cz[i] { 0 } else { 1 })
226 .sum();
227
228 res == 0
229 };
230
231 // verify if comm_W is a commitment to W
232 let res_comm: bool = U.comm_W == W.W.commit(&gens.gens_W);
233
234 if res_eq && res_comm {
235 Ok(())
236 } else {
237 Err(NovaError::UnSat)
238 }
239 }
240
241 /// A method to compute a commitment to the cross-term `T` given a
242 /// Relaxed R1CS instance-witness pair and an R1CS instance-witness pair
243 pub fn commit_T(
244 &self,
245 gens: &R1CSGens<G>,
246 U1: &RelaxedR1CSInstance<G>,
247 W1: &RelaxedR1CSWitness<G>,
248 U2: &R1CSInstance<G>,
249 W2: &R1CSWitness<G>,
250 ) -> Result<
251 (
252 Vec<G::Scalar>,
253 CompressedCommitment<G::CompressedGroupElement>,
254 ),
255 NovaError,
256 > {
257 let (AZ_1, BZ_1, CZ_1) = {
258 let Z1 = concat(vec![W1.W.clone(), vec![U1.u], U1.X.clone()]);
259 self.multiply_vec(&Z1)?
260 };
261
262 let (AZ_2, BZ_2, CZ_2) = {
263 let Z2 = concat(vec![W2.W.clone(), vec![G::Scalar::one()], U2.X.clone()]);
264 self.multiply_vec(&Z2)?
265 };
266
267 let AZ_1_circ_BZ_2 = (0..AZ_1.len())
268 .map(|i| AZ_1[i] * BZ_2[i])
269 .collect::<Vec<G::Scalar>>();
270 let AZ_2_circ_BZ_1 = (0..AZ_2.len())
271 .map(|i| AZ_2[i] * BZ_1[i])
272 .collect::<Vec<G::Scalar>>();
273 let u_1_cdot_CZ_2 = (0..CZ_2.len())
274 .map(|i| U1.u * CZ_2[i])
275 .collect::<Vec<G::Scalar>>();
276 let u_2_cdot_CZ_1 = (0..CZ_1.len()).map(|i| CZ_1[i]).collect::<Vec<G::Scalar>>();
277
278 let T = AZ_1_circ_BZ_2
279 .par_iter()
280 .zip(&AZ_2_circ_BZ_1)
281 .zip(&u_1_cdot_CZ_2)
282 .zip(&u_2_cdot_CZ_1)
283 .map(|(((a, b), c), d)| *a + *b - *c - *d)
284 .collect::<Vec<G::Scalar>>();
285
286 let comm_T = T.commit(&gens.gens_E).compress();
287
288 Ok((T, comm_T))
289 }
290}
291
292impl<G: Group> R1CSWitness<G> {
293 /// A method to create a witness object using a vector of scalars
294 pub fn new(S: &R1CSShape<G>, W: &[G::Scalar]) -> Result<R1CSWitness<G>, NovaError> {
295 if S.num_vars != W.len() {
296 Err(NovaError::InvalidWitnessLength)
297 } else {
298 Ok(R1CSWitness { W: W.to_owned() })
299 }
300 }
301
302 /// Commits to the witness using the supplied generators
303 pub fn commit(&self, gens: &R1CSGens<G>) -> Commitment<G> {
304 self.W.commit(&gens.gens_W)
305 }
306}
307
308impl<G: Group> R1CSInstance<G> {
309 /// A method to create an instance object using consitituent elements
310 pub fn new(
311 S: &R1CSShape<G>,
312 comm_W: &Commitment<G>,
313 X: &[G::Scalar],
314 ) -> Result<R1CSInstance<G>, NovaError> {
315 if S.num_io != X.len() {
316 Err(NovaError::InvalidInputLength)
317 } else {
318 Ok(R1CSInstance {
319 comm_W: *comm_W,
320 X: X.to_owned(),
321 })
322 }
323 }
324}
325
326impl<G: Group> RelaxedR1CSWitness<G> {
327 /// Produces a default RelaxedR1CSWitness given an R1CSShape
328 pub fn default(S: &R1CSShape<G>) -> RelaxedR1CSWitness<G> {
329 RelaxedR1CSWitness {
330 W: vec![G::Scalar::zero(); S.num_vars],
331 E: vec![G::Scalar::zero(); S.num_cons],
332 }
333 }
334
335 /// Commits to the witness using the supplied generators
336 pub fn commit(&self, gens: &R1CSGens<G>) -> (Commitment<G>, Commitment<G>) {
337 (self.W.commit(&gens.gens_W), self.E.commit(&gens.gens_E))
338 }
339
340 /// Folds an incoming R1CSWitness into the current one
341 pub fn fold(
342 &self,
343 W2: &R1CSWitness<G>,
344 T: &[G::Scalar],
345 r: &G::Scalar,
346 ) -> Result<RelaxedR1CSWitness<G>, NovaError> {
347 let (W1, E1) = (&self.W, &self.E);
348 let W2 = &W2.W;
349
350 if W1.len() != W2.len() {
351 return Err(NovaError::InvalidWitnessLength);
352 }
353
354 let W = W1
355 .par_iter()
356 .zip(W2)
357 .map(|(a, b)| *a + *r * *b)
358 .collect::<Vec<G::Scalar>>();
359 let E = E1
360 .par_iter()
361 .zip(T)
362 .map(|(a, b)| *a + *r * *b)
363 .collect::<Vec<G::Scalar>>();
364 Ok(RelaxedR1CSWitness { W, E })
365 }
366}
367
368impl<G: Group> RelaxedR1CSInstance<G> {
369 /// Produces a default RelaxedR1CSInstance given R1CSGens and R1CSShape
370 pub fn default(gens: &R1CSGens<G>, S: &R1CSShape<G>) -> RelaxedR1CSInstance<G> {
371 let (comm_W, comm_E) = RelaxedR1CSWitness::default(S).commit(gens);
372 RelaxedR1CSInstance {
373 comm_W,
374 comm_E,
375 u: G::Scalar::zero(),
376 X: vec![G::Scalar::zero(); S.num_io],
377 Y_last: vec![G::Scalar::zero(); S.num_io / 2],
378 counter: 0,
379 }
380 }
381
382 /// Folds an incoming RelaxedR1CSInstance into the current one
383 pub fn fold(
384 &self,
385 U2: &R1CSInstance<G>,
386 comm_T: &CompressedCommitment<G::CompressedGroupElement>,
387 r: &G::Scalar,
388 ) -> Result<RelaxedR1CSInstance<G>, NovaError> {
389 let comm_T_unwrapped = comm_T.decompress()?;
390 let (X1, u1, comm_W_1, comm_E_1) =
391 (&self.X, &self.u, &self.comm_W.clone(), &self.comm_E.clone());
392 let (X2, comm_W_2) = (&U2.X, &U2.comm_W);
393
394 // check if the input of the incoming instance matches the output
395 // of the incremental computation thus far if counter > 0
396 if self.counter > 0 {
397 if self.Y_last.len() != U2.X.len() / 2 {
398 return Err(NovaError::InvalidInputLength);
399 }
400 for i in 0..self.Y_last.len() {
401 if self.Y_last[i] != U2.X[i] {
402 return Err(NovaError::InputOutputMismatch);
403 }
404 }
405 }
406
407 // weighted sum of X, comm_W, comm_E, and u
408 let X = X1
409 .par_iter()
410 .zip(X2)
411 .map(|(a, b)| *a + *r * *b)
412 .collect::<Vec<G::Scalar>>();
413 let comm_W = comm_W_1 + comm_W_2 * r;
414 let comm_E = *comm_E_1 + comm_T_unwrapped * *r;
415 let u = *u1 + *r;
416
417 Ok(RelaxedR1CSInstance {
418 comm_W,
419 comm_E,
420 X,
421 u,
422 Y_last: U2.X[U2.X.len() / 2..].to_owned(),
423 counter: self.counter + 1,
424 })
425 }
426}