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 // 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,
181 U1: &R1CSInstance,
182 W1: &R1CSWitness,
183 U2: &R1CSInstance,
184 W2: &R1CSWitness,
185 ) -> Result<(Vec<Scalar>, CompressedCommitment), 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<Scalar>>();
199 let AZ_2_circ_BZ_1 = (0..AZ_2.len())
200 .map(|i| AZ_2[i] * BZ_1[i])
201 .collect::<Vec<Scalar>>();
202 let u_1_cdot_CZ_2 = (0..CZ_2.len())
203 .map(|i| U1.u * CZ_2[i])
204 .collect::<Vec<Scalar>>();
205 let u_2_cdot_CZ_1 = (0..CZ_1.len())
206 .map(|i| U2.u * CZ_1[i])
207 .collect::<Vec<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<Scalar>>();
216
217 let comm_T = T.commit(&gens.gens_E).compress();
218
219 Ok((T, comm_T))
220 }
221}
222
223impl R1CSWitness {
224 pub fn new(S: &R1CSShape, W: &[Scalar], E: &[Scalar]) -> Result<R1CSWitness, NovaError> {
225 if S.num_vars != W.len() || S.num_cons != E.len() {
226 Err(NovaError::InvalidWitnessLength)
227 } else {
228 Ok(R1CSWitness {
229 W: W.to_owned(),
230 E: E.to_owned(),
231 })
232 }
233 }
234
235 pub fn commit(&self, gens: &R1CSGens) -> (Commitment, Commitment) {
236 (self.W.commit(&gens.gens_W), self.E.commit(&gens.gens_E))
237 }
238
239 pub fn fold(&self, W2: &R1CSWitness, T: &[Scalar], r: &Scalar) -> Result<R1CSWitness, NovaError> {
240 let (W1, E1) = (&self.W, &self.E);
241 let (W2, E2) = (&W2.W, &W2.E);
242
243 if W1.len() != W2.len() {
244 return Err(NovaError::InvalidWitnessLength);
245 }
246
247 let W = W1
248 .par_iter()
249 .zip(W2)
250 .map(|(a, b)| a + r * b)
251 .collect::<Vec<Scalar>>();
252 let E = E1
253 .par_iter()
254 .zip(T)
255 .zip(E2)
256 .map(|((a, b), c)| a + r * b + r * r * c)
257 .collect::<Vec<Scalar>>();
258 Ok(R1CSWitness { W, E })
259 }
260}
261
262impl R1CSInstance {
263 pub fn new(
264 S: &R1CSShape,
265 comm_W: &Commitment,
266 comm_E: &Commitment,
267 X: &[Scalar],
268 u: &Scalar,
269 ) -> Result<R1CSInstance, NovaError> {
270 if S.num_inputs != X.len() {
271 Err(NovaError::InvalidInputLength)
272 } else {
273 Ok(R1CSInstance {
274 comm_W: comm_W.clone(),
275 comm_E: comm_E.clone(),
276 X: X.to_owned(),
277 u: *u,
278 })
279 }
280 }
281
282 pub fn fold(
283 &self,
284 U2: &R1CSInstance,
285 comm_T: &CompressedCommitment,
286 r: &Scalar,
287 ) -> Result<R1CSInstance, NovaError> {
288 let comm_T_unwrapped = comm_T.decompress()?;
289 let (X1, u1, comm_W_1, comm_E_1) =
290 (&self.X, &self.u, &self.comm_W.clone(), &self.comm_E.clone());
291 let (X2, u2, comm_W_2, comm_E_2) = (&U2.X, &U2.u, &U2.comm_W, &U2.comm_E);
292
293 // weighted sum of X
294 let X = X1
295 .par_iter()
296 .zip(X2)
297 .map(|(a, b)| a + r * b)
298 .collect::<Vec<Scalar>>();
299 let comm_W = comm_W_1 + r * comm_W_2;
300 let comm_E = comm_E_1 + r * comm_T_unwrapped + r * r * comm_E_2;
301 let u = u1 + r * u2;
302
303 Ok(R1CSInstance {
304 comm_W,
305 comm_E,
306 X,
307 u,
308 })
309 }
310}