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