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