Nova/src/r1cs.rs
src/r1cs.rsRaw
1#![allow(clippy::type_complexity)]
2use super::commitments::{CommitGens, CommitTrait, Commitment};
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<(Vec<G::Scalar>, Commitment<G>), NovaError> {
186 let (AZ_1, BZ_1, CZ_1) = {
187 let Z1 = concat(vec![W1.W.clone(), vec![U1.u], U1.X.clone()]);
188 self.multiply_vec(&Z1)?
189 };
190
191 let (AZ_2, BZ_2, CZ_2) = {
192 let Z2 = concat(vec![W2.W.clone(), vec![U2.u], U2.X.clone()]);
193 self.multiply_vec(&Z2)?
194 };
195
196 let AZ_1_circ_BZ_2 = (0..AZ_1.len())
197 .map(|i| AZ_1[i] * BZ_2[i])
198 .collect::<Vec<G::Scalar>>();
199 let AZ_2_circ_BZ_1 = (0..AZ_2.len())
200 .map(|i| AZ_2[i] * BZ_1[i])
201 .collect::<Vec<G::Scalar>>();
202 let u_1_cdot_CZ_2 = (0..CZ_2.len())
203 .map(|i| U1.u * CZ_2[i])
204 .collect::<Vec<G::Scalar>>();
205 let u_2_cdot_CZ_1 = (0..CZ_1.len())
206 .map(|i| U2.u * CZ_1[i])
207 .collect::<Vec<G::Scalar>>();
208
209 let T = AZ_1_circ_BZ_2
210 .par_iter()
211 .zip(&AZ_2_circ_BZ_1)
212 .zip(&u_1_cdot_CZ_2)
213 .zip(&u_2_cdot_CZ_1)
214 .map(|(((a, b), c), d)| *a + *b - *c - *d)
215 .collect::<Vec<G::Scalar>>();
216
217 let comm_T = T.commit(&gens.gens_E);
218
219 Ok((T, comm_T))
220 }
221}
222
223impl<G: Group> R1CSWitness<G> {
224 pub fn new(
225 S: &R1CSShape<G>,
226 W: &[G::Scalar],
227 E: &[G::Scalar],
228 ) -> Result<R1CSWitness<G>, NovaError> {
229 if S.num_vars != W.len() || S.num_cons != E.len() {
230 Err(NovaError::InvalidWitnessLength)
231 } else {
232 Ok(R1CSWitness {
233 W: W.to_owned(),
234 E: E.to_owned(),
235 })
236 }
237 }
238
239 pub fn commit(&self, gens: &R1CSGens<G>) -> (Commitment<G>, Commitment<G>) {
240 (self.W.commit(&gens.gens_W), self.E.commit(&gens.gens_E))
241 }
242
243 pub fn fold(
244 &self,
245 W2: &R1CSWitness<G>,
246 T: &[G::Scalar],
247 r: &G::Scalar,
248 ) -> Result<R1CSWitness<G>, NovaError> {
249 let (W1, E1) = (&self.W, &self.E);
250 let (W2, E2) = (&W2.W, &W2.E);
251
252 if W1.len() != W2.len() {
253 return Err(NovaError::InvalidWitnessLength);
254 }
255
256 let W = W1
257 .par_iter()
258 .zip(W2)
259 .map(|(a, b)| *a + *r * *b)
260 .collect::<Vec<G::Scalar>>();
261 let E = E1
262 .par_iter()
263 .zip(T)
264 .zip(E2)
265 .map(|((a, b), c)| *a + *r * *b + *r * *r * *c)
266 .collect::<Vec<G::Scalar>>();
267 Ok(R1CSWitness { W, E })
268 }
269}
270
271impl<G: Group> R1CSInstance<G> {
272 pub fn new(
273 S: &R1CSShape<G>,
274 comm_W: &Commitment<G>,
275 comm_E: &Commitment<G>,
276 X: &[G::Scalar],
277 u: &G::Scalar,
278 ) -> Result<R1CSInstance<G>, NovaError> {
279 if S.num_inputs != X.len() {
280 Err(NovaError::InvalidInputLength)
281 } else {
282 Ok(R1CSInstance {
283 comm_W: comm_W.clone(),
284 comm_E: comm_E.clone(),
285 X: X.to_owned(),
286 u: *u,
287 })
288 }
289 }
290
291 pub fn fold(
292 &self,
293 U2: &R1CSInstance<G>,
294 comm_T: &Commitment<G>,
295 r: &G::Scalar,
296 ) -> R1CSInstance<G> {
297 let (X1, u1, comm_W_1, comm_E_1) =
298 (&self.X, &self.u, &self.comm_W.clone(), &self.comm_E.clone());
299 let (X2, u2, comm_W_2, comm_E_2) = (&U2.X, &U2.u, &U2.comm_W, &U2.comm_E);
300
301 // weighted sum of X
302 let X = X1
303 .par_iter()
304 .zip(X2)
305 .map(|(a, b)| *a + *r * *b)
306 .collect::<Vec<G::Scalar>>();
307 let comm_W = comm_W_1 + *comm_W_2 * *r;
308 let comm_E = *comm_E_1 + *comm_T * *r + *comm_E_2 * *r * *r;
309 let u = *u1 + *r * *u2;
310
311 R1CSInstance {
312 comm_W,
313 comm_E,
314 X,
315 u,
316 }
317 }
318}