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_inputs: 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 E: 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 comm_E: Commitment<G>,
38 X: Vec<G::Scalar>,
39 u: G::Scalar,
40}
41
42impl<G: Group> R1CSGens<G> {
43 /// Samples public parameters for the specified number of constraints and variables in an R1CS
44 pub fn new(num_cons: usize, num_vars: usize) -> R1CSGens<G> {
45 // generators to commit to witness vector `W`
46 let gens_W = CommitGens::new(b"gens_W", num_vars);
47
48 // generators to commit to the error/slack vector `E`
49 let gens_E = CommitGens::new(b"gens_E", num_cons);
50
51 R1CSGens { gens_E, gens_W }
52 }
53}
54
55impl<G: Group> R1CSShape<G> {
56 /// Create an object of type `R1CSShape` from the explicitly specified R1CS matrices
57 pub fn new(
58 num_cons: usize,
59 num_vars: usize,
60 num_inputs: usize,
61 A: &[(usize, usize, G::Scalar)],
62 B: &[(usize, usize, G::Scalar)],
63 C: &[(usize, usize, G::Scalar)],
64 ) -> Result<R1CSShape<G>, NovaError> {
65 let is_valid = |num_cons: usize,
66 num_vars: usize,
67 num_io: usize,
68 M: &[(usize, usize, G::Scalar)]|
69 -> Result<(), NovaError> {
70 let res = (0..num_cons)
71 .map(|i| {
72 let (row, col, _val) = M[i];
73 if row >= num_cons || col > num_io + num_vars {
74 Err(NovaError::InvalidIndex)
75 } else {
76 Ok(())
77 }
78 })
79 .collect::<Result<Vec<()>, NovaError>>();
80
81 if res.is_err() {
82 Err(NovaError::InvalidIndex)
83 } else {
84 Ok(())
85 }
86 };
87
88 let res_A = is_valid(num_cons, num_vars, num_inputs, A);
89 let res_B = is_valid(num_cons, num_vars, num_inputs, B);
90 let res_C = is_valid(num_cons, num_vars, num_inputs, C);
91
92 if res_A.is_err() || res_B.is_err() || res_C.is_err() {
93 return Err(NovaError::InvalidIndex);
94 }
95
96 let shape = R1CSShape {
97 num_cons,
98 num_vars,
99 num_inputs,
100 A: A.to_owned(),
101 B: B.to_owned(),
102 C: C.to_owned(),
103 };
104
105 Ok(shape)
106 }
107
108 fn multiply_vec(
109 &self,
110 z: &[G::Scalar],
111 ) -> Result<(Vec<G::Scalar>, Vec<G::Scalar>, Vec<G::Scalar>), NovaError> {
112 if z.len() != self.num_inputs + self.num_vars + 1 {
113 return Err(NovaError::InvalidWitnessLength);
114 }
115
116 // computes a product between a sparse matrix `M` and a vector `z`
117 // This does not perform any validation of entries in M (e.g., if entries in `M` reference indexes outside the range of `z`)
118 // This is safe since we know that `M` is valid
119 let sparse_matrix_vec_product =
120 |M: &Vec<(usize, usize, G::Scalar)>, num_rows: usize, z: &[G::Scalar]| -> Vec<G::Scalar> {
121 (0..M.len())
122 .map(|i| {
123 let (row, col, val) = M[i];
124 (row, val * z[col])
125 })
126 .fold(vec![G::Scalar::zero(); num_rows], |mut Mz, (r, v)| {
127 Mz[r] += v;
128 Mz
129 })
130 };
131
132 let Az = sparse_matrix_vec_product(&self.A, self.num_cons, z);
133 let Bz = sparse_matrix_vec_product(&self.B, self.num_cons, z);
134 let Cz = sparse_matrix_vec_product(&self.C, self.num_cons, z);
135
136 Ok((Az, Bz, Cz))
137 }
138
139 /// Checks if the R1CS instance is satisfiable given a witness and its shape
140 pub fn is_sat(
141 &self,
142 gens: &R1CSGens<G>,
143 U: &R1CSInstance<G>,
144 W: &R1CSWitness<G>,
145 ) -> Result<(), NovaError> {
146 assert_eq!(W.W.len(), self.num_vars);
147 assert_eq!(W.E.len(), self.num_cons);
148 assert_eq!(U.X.len(), self.num_inputs);
149
150 // verify if Az * Bz = u*Cz + E
151 let res_eq: bool = {
152 let z = concat(vec![W.W.clone(), vec![U.u], U.X.clone()]);
153 let (Az, Bz, Cz) = self.multiply_vec(&z)?;
154 assert_eq!(Az.len(), self.num_cons);
155 assert_eq!(Bz.len(), self.num_cons);
156 assert_eq!(Cz.len(), self.num_cons);
157
158 let res: usize = (0..self.num_cons)
159 .map(|i| {
160 if Az[i] * Bz[i] == U.u * Cz[i] + W.E[i] {
161 0
162 } else {
163 1
164 }
165 })
166 .sum();
167
168 res == 0
169 };
170
171 // verify if comm_E and comm_W are commitments to E and W
172 let res_comm: bool = {
173 let comm_W = W.W.commit(&gens.gens_W);
174 let comm_E = W.E.commit(&gens.gens_E);
175
176 U.comm_W == comm_W && U.comm_E == comm_E
177 };
178
179 if res_eq && res_comm {
180 Ok(())
181 } else {
182 Err(NovaError::UnSat)
183 }
184 }
185
186 /// A method to compute a commitment to the cross-term `T` given two R1CS instance-witness pairs
187 pub fn commit_T(
188 &self,
189 gens: &R1CSGens<G>,
190 U1: &R1CSInstance<G>,
191 W1: &R1CSWitness<G>,
192 U2: &R1CSInstance<G>,
193 W2: &R1CSWitness<G>,
194 ) -> Result<
195 (
196 Vec<G::Scalar>,
197 CompressedCommitment<G::CompressedGroupElement>,
198 ),
199 NovaError,
200 > {
201 let (AZ_1, BZ_1, CZ_1) = {
202 let Z1 = concat(vec![W1.W.clone(), vec![U1.u], U1.X.clone()]);
203 self.multiply_vec(&Z1)?
204 };
205
206 let (AZ_2, BZ_2, CZ_2) = {
207 let Z2 = concat(vec![W2.W.clone(), vec![U2.u], U2.X.clone()]);
208 self.multiply_vec(&Z2)?
209 };
210
211 let AZ_1_circ_BZ_2 = (0..AZ_1.len())
212 .map(|i| AZ_1[i] * BZ_2[i])
213 .collect::<Vec<G::Scalar>>();
214 let AZ_2_circ_BZ_1 = (0..AZ_2.len())
215 .map(|i| AZ_2[i] * BZ_1[i])
216 .collect::<Vec<G::Scalar>>();
217 let u_1_cdot_CZ_2 = (0..CZ_2.len())
218 .map(|i| U1.u * CZ_2[i])
219 .collect::<Vec<G::Scalar>>();
220 let u_2_cdot_CZ_1 = (0..CZ_1.len())
221 .map(|i| U2.u * CZ_1[i])
222 .collect::<Vec<G::Scalar>>();
223
224 let T = AZ_1_circ_BZ_2
225 .par_iter()
226 .zip(&AZ_2_circ_BZ_1)
227 .zip(&u_1_cdot_CZ_2)
228 .zip(&u_2_cdot_CZ_1)
229 .map(|(((a, b), c), d)| *a + *b - *c - *d)
230 .collect::<Vec<G::Scalar>>();
231
232 let comm_T = T.commit(&gens.gens_E).compress();
233
234 Ok((T, comm_T))
235 }
236}
237
238impl<G: Group> R1CSWitness<G> {
239 /// A method to create a witness object using a vector of scalars
240 pub fn new(
241 S: &R1CSShape<G>,
242 W: &[G::Scalar],
243 E: &[G::Scalar],
244 ) -> Result<R1CSWitness<G>, NovaError> {
245 if S.num_vars != W.len() || S.num_cons != E.len() {
246 Err(NovaError::InvalidWitnessLength)
247 } else {
248 Ok(R1CSWitness {
249 W: W.to_owned(),
250 E: E.to_owned(),
251 })
252 }
253 }
254
255 /// Commits to the witness using the supplied generators
256 pub fn commit(&self, gens: &R1CSGens<G>) -> (Commitment<G>, Commitment<G>) {
257 (self.W.commit(&gens.gens_W), self.E.commit(&gens.gens_E))
258 }
259
260 /// Folds an incoming R1CSWitness into the current one
261 pub fn fold(
262 &self,
263 W2: &R1CSWitness<G>,
264 T: &[G::Scalar],
265 r: &G::Scalar,
266 ) -> Result<R1CSWitness<G>, NovaError> {
267 let (W1, E1) = (&self.W, &self.E);
268 let (W2, E2) = (&W2.W, &W2.E);
269
270 if W1.len() != W2.len() {
271 return Err(NovaError::InvalidWitnessLength);
272 }
273
274 let W = W1
275 .par_iter()
276 .zip(W2)
277 .map(|(a, b)| *a + *r * *b)
278 .collect::<Vec<G::Scalar>>();
279 let E = E1
280 .par_iter()
281 .zip(T)
282 .zip(E2)
283 .map(|((a, b), c)| *a + *r * *b + *r * *r * *c)
284 .collect::<Vec<G::Scalar>>();
285 Ok(R1CSWitness { W, E })
286 }
287}
288
289impl<G: Group> R1CSInstance<G> {
290 /// A method to create an instance object using consitituent elements
291 pub fn new(
292 S: &R1CSShape<G>,
293 comm_W: &Commitment<G>,
294 comm_E: &Commitment<G>,
295 X: &[G::Scalar],
296 u: &G::Scalar,
297 ) -> Result<R1CSInstance<G>, NovaError> {
298 if S.num_inputs != X.len() {
299 Err(NovaError::InvalidInputLength)
300 } else {
301 Ok(R1CSInstance {
302 comm_W: *comm_W,
303 comm_E: *comm_E,
304 X: X.to_owned(),
305 u: *u,
306 })
307 }
308 }
309
310 /// Folds an incoming R1CSInstance into the current one
311 pub fn fold(
312 &self,
313 U2: &R1CSInstance<G>,
314 comm_T: &CompressedCommitment<G::CompressedGroupElement>,
315 r: &G::Scalar,
316 ) -> Result<R1CSInstance<G>, NovaError> {
317 let comm_T_unwrapped = comm_T.decompress()?;
318 let (X1, u1, comm_W_1, comm_E_1) =
319 (&self.X, &self.u, &self.comm_W.clone(), &self.comm_E.clone());
320 let (X2, u2, comm_W_2, comm_E_2) = (&U2.X, &U2.u, &U2.comm_W, &U2.comm_E);
321
322 // weighted sum of X
323 let X = X1
324 .par_iter()
325 .zip(X2)
326 .map(|(a, b)| *a + *r * *b)
327 .collect::<Vec<G::Scalar>>();
328 let comm_W = comm_W_1 + comm_W_2 * r;
329 let comm_E = *comm_E_1 + comm_T_unwrapped * *r + comm_E_2 * r * *r;
330 let u = *u1 + *r * *u2;
331
332 Ok(R1CSInstance {
333 comm_W,
334 comm_E,
335 X,
336 u,
337 })
338 }
339}