Nova/src/r1cs.rs
src/r1cs.rsRaw
1#![allow(clippy::type_complexity)]
2use super::commitments::Scalar;
3use super::commitments::{CommitGens, CommitTrait, Commitment, CompressedCommitment};
4use super::errors::NovaError;
5use itertools::concat;
6use rayon::prelude::*;
7
8pub struct R1CSGens {
9 gens_W: CommitGens,
10 gens_E: CommitGens,
11}
12
13#[derive(Debug)]
14pub struct R1CSShape {
15 num_cons: usize,
16 num_vars: usize,
17 num_inputs: usize,
18 A: Vec<(usize, usize, Scalar)>,
19 B: Vec<(usize, usize, Scalar)>,
20 C: Vec<(usize, usize, Scalar)>,
21}
22
23#[derive(Clone, Debug)]
24pub struct R1CSWitness {
25 W: Vec<Scalar>,
26 E: Vec<Scalar>,
27}
28
29#[derive(Clone, Debug, PartialEq, Eq)]
30pub struct R1CSInstance {
31 comm_W: Commitment,
32 comm_E: Commitment,
33 X: Vec<Scalar>,
34 u: Scalar,
35}
36
37impl R1CSGens {
38 pub fn new(num_cons: usize, num_vars: usize) -> R1CSGens {
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 R1CSShape {
50 pub fn new(
51 num_cons: usize,
52 num_vars: usize,
53 num_inputs: usize,
54 A: &[(usize, usize, Scalar)],
55 B: &[(usize, usize, Scalar)],
56 C: &[(usize, usize, Scalar)],
57 ) -> Result<R1CSShape, NovaError> {
58 let is_valid = |num_cons: usize,
59 num_vars: usize,
60 num_io: usize,
61 M: &[(usize, usize, 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: &[Scalar],
104 ) -> Result<(Vec<Scalar>, Vec<Scalar>, Vec<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, Scalar)>, num_rows: usize, z: &[Scalar]| -> Vec<Scalar> {
114 (0..M.len())
115 .map(|i| {
116 let (row, col, val) = M[i];
117 (row, val * z[col])
118 })
119 .fold(vec![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,
135 U: &R1CSInstance,
136 W: &R1CSWitness,
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 assert!(res_eq, true);
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 assert!(res_comm, true);
174
175 if res_eq && res_comm {
176 Ok(())
177 } else {
178 Err(NovaError::UnSat)
179 }
180 }
181
182 pub fn commit_T(
183 &self,
184 gens: &R1CSGens,
185 U1: &R1CSInstance,
186 W1: &R1CSWitness,
187 U2: &R1CSInstance,
188 W2: &R1CSWitness,
189 ) -> Result<(Vec<Scalar>, CompressedCommitment), NovaError> {
190 let (AZ_1, BZ_1, CZ_1) = {
191 let Z1 = concat(vec![W1.W.clone(), vec![U1.u], U1.X.clone()]);
192 self.multiply_vec(&Z1)?
193 };
194
195 let (AZ_2, BZ_2, CZ_2) = {
196 let Z2 = concat(vec![W2.W.clone(), vec![U2.u], U2.X.clone()]);
197 self.multiply_vec(&Z2)?
198 };
199
200 let AZ_1_circ_BZ_2 = (0..AZ_1.len())
201 .map(|i| AZ_1[i] * BZ_2[i])
202 .collect::<Vec<Scalar>>();
203 let AZ_2_circ_BZ_1 = (0..AZ_2.len())
204 .map(|i| AZ_2[i] * BZ_1[i])
205 .collect::<Vec<Scalar>>();
206 let u_1_cdot_CZ_2 = (0..CZ_2.len())
207 .map(|i| U1.u * CZ_2[i])
208 .collect::<Vec<Scalar>>();
209 let u_2_cdot_CZ_1 = (0..CZ_1.len())
210 .map(|i| U2.u * CZ_1[i])
211 .collect::<Vec<Scalar>>();
212
213 let T = AZ_1_circ_BZ_2
214 .par_iter()
215 .zip(&AZ_2_circ_BZ_1)
216 .zip(&u_1_cdot_CZ_2)
217 .zip(&u_2_cdot_CZ_1)
218 .map(|(((a, b), c), d)| a + b - c - d)
219 .collect::<Vec<Scalar>>();
220
221 let T_commit = T.commit(&gens.gens_E).compress();
222
223 Ok((T, T_commit))
224 }
225}
226
227impl R1CSWitness {
228 pub fn new(S: &R1CSShape, W: &[Scalar], E: &[Scalar]) -> Result<R1CSWitness, 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) -> (Commitment, Commitment) {
240 (self.W.commit(&gens.gens_W), self.E.commit(&gens.gens_E))
241 }
242
243 pub fn fold(&self, W2: &R1CSWitness, T: &[Scalar], r: &Scalar) -> Result<R1CSWitness, NovaError> {
244 let (W1, E1) = (&self.W, &self.E);
245 let (W2, E2) = (&W2.W, &W2.E);
246
247 if W1.len() != W2.len() {
248 return Err(NovaError::InvalidWitnessLength);
249 }
250
251 let W = W1
252 .par_iter()
253 .zip(W2)
254 .map(|(a, b)| a + r * b)
255 .collect::<Vec<Scalar>>();
256 let E = E1
257 .par_iter()
258 .zip(T)
259 .zip(E2)
260 .map(|((a, b), c)| a + r * b + r * r * c)
261 .collect::<Vec<Scalar>>();
262 Ok(R1CSWitness { W, E })
263 }
264}
265
266impl R1CSInstance {
267 pub fn new(
268 S: &R1CSShape,
269 comm_W: &Commitment,
270 comm_E: &Commitment,
271 X: &[Scalar],
272 u: &Scalar,
273 ) -> Result<R1CSInstance, NovaError> {
274 if S.num_inputs != X.len() {
275 Err(NovaError::InvalidInputLength)
276 } else {
277 Ok(R1CSInstance {
278 comm_W: comm_W.clone(),
279 comm_E: comm_E.clone(),
280 X: X.to_owned(),
281 u: *u,
282 })
283 }
284 }
285
286 pub fn fold(
287 &self,
288 U2: &R1CSInstance,
289 comm_T: &CompressedCommitment,
290 r: &Scalar,
291 ) -> Result<R1CSInstance, NovaError> {
292 let comm_T_unwrapped = comm_T.decompress()?;
293 let (X1, u1, comm_W_1, comm_E_1) =
294 (&self.X, &self.u, &self.comm_W.clone(), &self.comm_E.clone());
295 let (X2, u2, comm_W_2, comm_E_2) = (&U2.X, &U2.u, &U2.comm_W, &U2.comm_E);
296
297 // weighted sum of X
298 let X = X1
299 .par_iter()
300 .zip(X2)
301 .map(|(a, b)| a + r * b)
302 .collect::<Vec<Scalar>>();
303 let comm_W = comm_W_1 + r * comm_W_2;
304 let comm_E = comm_E_1 + r * comm_T_unwrapped + r * r * comm_E_2;
305 let u = u1 + r * u2;
306
307 Ok(R1CSInstance {
308 comm_W,
309 comm_E,
310 X,
311 u,
312 })
313 }
314}