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