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