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