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