testudo/src/r1csinstance.rs
src/r1csinstance.rsRaw
1use super::dense_mlpoly::DensePolynomial;
2use super::errors::ProofVerifyError;
3use super::math::Math;
4use super::random::RandomTape;
5use super::scalar::Scalar;
6use super::sparse_mlpoly::{
7 MultiSparseMatPolynomialAsDense, SparseMatEntry, SparseMatPolyCommitment,
8 SparseMatPolyCommitmentGens, SparseMatPolyEvalProof, SparseMatPolynomial,
9};
10use super::timer::Timer;
11use merlin::Transcript;
12use rand::rngs::OsRng;
13use serde::{Deserialize, Serialize};
14
15#[derive(Debug)]
16pub struct R1CSInstance {
17 num_cons: usize,
18 num_vars: usize,
19 num_inputs: usize,
20 A: SparseMatPolynomial,
21 B: SparseMatPolynomial,
22 C: SparseMatPolynomial,
23}
24
25pub struct R1CSCommitmentGens {
26 gens: SparseMatPolyCommitmentGens,
27}
28
29impl R1CSCommitmentGens {
30 pub fn new(
31 label: &'static [u8],
32 num_cons: usize,
33 num_vars: usize,
34 num_inputs: usize,
35 num_nz_entries: usize,
36 ) -> R1CSCommitmentGens {
37 assert!(num_inputs < num_vars);
38 let num_poly_vars_x = num_cons.log2();
39 let num_poly_vars_y = (2 * num_vars).log2();
40 let gens =
41 SparseMatPolyCommitmentGens::new(label, num_poly_vars_x, num_poly_vars_y, num_nz_entries, 3);
42 R1CSCommitmentGens { gens }
43 }
44}
45
46pub struct R1CSCommitment {
47 num_cons: usize,
48 num_vars: usize,
49 num_inputs: usize,
50 comm: SparseMatPolyCommitment,
51}
52
53pub struct R1CSDecommitment {
54 dense: MultiSparseMatPolynomialAsDense,
55}
56
57impl R1CSCommitment {
58 pub fn get_num_cons(&self) -> usize {
59 self.num_cons
60 }
61
62 pub fn get_num_vars(&self) -> usize {
63 self.num_vars
64 }
65
66 pub fn get_num_inputs(&self) -> usize {
67 self.num_inputs
68 }
69}
70
71impl R1CSInstance {
72 pub fn new(
73 num_cons: usize,
74 num_vars: usize,
75 num_inputs: usize,
76 A: &Vec<(usize, usize, Scalar)>,
77 B: &Vec<(usize, usize, Scalar)>,
78 C: &Vec<(usize, usize, Scalar)>,
79 ) -> R1CSInstance {
80 Timer::print(&format!("number_of_constraints {}", num_cons));
81 Timer::print(&format!("number_of_variables {}", num_vars));
82 Timer::print(&format!("number_of_inputs {}", num_inputs));
83 Timer::print(&format!("number_non-zero_entries_A {}", A.len()));
84 Timer::print(&format!("number_non-zero_entries_B {}", B.len()));
85 Timer::print(&format!("number_non-zero_entries_C {}", C.len()));
86
87 // check that num_cons is a power of 2
88 assert_eq!(num_cons.next_power_of_two(), num_cons);
89
90 // check that num_vars is a power of 2
91 assert_eq!(num_vars.next_power_of_two(), num_vars);
92
93 // check that number_inputs + 1 <= num_vars
94 assert!(num_inputs < num_vars);
95
96 // no errors, so create polynomials
97 let num_poly_vars_x = num_cons.log2();
98 let num_poly_vars_y = (2 * num_vars).log2();
99
100 let mat_A = (0..A.len())
101 .map(|i| SparseMatEntry::new(A[i].0, A[i].1, A[i].2))
102 .collect::<Vec<SparseMatEntry>>();
103 let mat_B = (0..B.len())
104 .map(|i| SparseMatEntry::new(B[i].0, B[i].1, B[i].2))
105 .collect::<Vec<SparseMatEntry>>();
106 let mat_C = (0..C.len())
107 .map(|i| SparseMatEntry::new(C[i].0, C[i].1, C[i].2))
108 .collect::<Vec<SparseMatEntry>>();
109
110 let poly_A = SparseMatPolynomial::new(num_poly_vars_x, num_poly_vars_y, mat_A);
111 let poly_B = SparseMatPolynomial::new(num_poly_vars_x, num_poly_vars_y, mat_B);
112 let poly_C = SparseMatPolynomial::new(num_poly_vars_x, num_poly_vars_y, mat_C);
113
114 let inst = R1CSInstance {
115 num_cons,
116 num_vars,
117 num_inputs,
118 A: poly_A,
119 B: poly_B,
120 C: poly_C,
121 };
122
123 inst
124 }
125
126 pub fn get_num_vars(&self) -> usize {
127 self.num_vars
128 }
129
130 pub fn get_num_cons(&self) -> usize {
131 self.num_cons
132 }
133
134 pub fn get_num_inputs(&self) -> usize {
135 self.num_inputs
136 }
137
138 pub fn produce_synthetic_r1cs(
139 num_cons: usize,
140 num_vars: usize,
141 num_inputs: usize,
142 ) -> (R1CSInstance, Vec<Scalar>, Vec<Scalar>) {
143 Timer::print(&format!("number_of_constraints {}", num_cons));
144 Timer::print(&format!("number_of_variables {}", num_vars));
145 Timer::print(&format!("number_of_inputs {}", num_inputs));
146
147 let mut csprng: OsRng = OsRng;
148
149 // assert num_cons and num_vars are power of 2
150 assert_eq!(num_cons.log2().pow2(), num_cons);
151 assert_eq!(num_vars.log2().pow2(), num_vars);
152
153 // num_inputs + 1 <= num_vars
154 assert!(num_inputs < num_vars);
155
156 // z is organized as [vars,1,io]
157 let size_z = num_vars + num_inputs + 1;
158
159 // produce a random satisfying assignment
160 let Z = {
161 let mut Z: Vec<Scalar> = (0..size_z)
162 .map(|_i| Scalar::random(&mut csprng))
163 .collect::<Vec<Scalar>>();
164 Z[num_vars] = Scalar::one(); // set the constant term to 1
165 Z
166 };
167
168 // three sparse matrices
169 let mut A: Vec<SparseMatEntry> = Vec::new();
170 let mut B: Vec<SparseMatEntry> = Vec::new();
171 let mut C: Vec<SparseMatEntry> = Vec::new();
172 let one = Scalar::one();
173 for i in 0..num_cons {
174 let A_idx = i % size_z;
175 let B_idx = (i + 2) % size_z;
176 A.push(SparseMatEntry::new(i, A_idx, one));
177 B.push(SparseMatEntry::new(i, B_idx, one));
178 let AB_val = Z[A_idx] * Z[B_idx];
179
180 let C_idx = (i + 3) % size_z;
181 let C_val = Z[C_idx];
182
183 if C_val == Scalar::zero() {
184 C.push(SparseMatEntry::new(i, num_vars, AB_val));
185 } else {
186 C.push(SparseMatEntry::new(
187 i,
188 C_idx,
189 AB_val * C_val.invert().unwrap(),
190 ));
191 }
192 }
193
194 Timer::print(&format!("number_non-zero_entries_A {}", A.len()));
195 Timer::print(&format!("number_non-zero_entries_B {}", B.len()));
196 Timer::print(&format!("number_non-zero_entries_C {}", C.len()));
197
198 let num_poly_vars_x = num_cons.log2();
199 let num_poly_vars_y = (2 * num_vars).log2();
200 let poly_A = SparseMatPolynomial::new(num_poly_vars_x, num_poly_vars_y, A);
201 let poly_B = SparseMatPolynomial::new(num_poly_vars_x, num_poly_vars_y, B);
202 let poly_C = SparseMatPolynomial::new(num_poly_vars_x, num_poly_vars_y, C);
203
204 let inst = R1CSInstance {
205 num_cons,
206 num_vars,
207 num_inputs,
208 A: poly_A,
209 B: poly_B,
210 C: poly_C,
211 };
212
213 assert_eq!(
214 inst.is_sat(&Z[0..num_vars].to_vec(), &Z[num_vars + 1..].to_vec()),
215 true,
216 );
217
218 (inst, Z[0..num_vars].to_vec(), Z[num_vars + 1..].to_vec())
219 }
220
221 pub fn is_sat(&self, vars: &[Scalar], input: &[Scalar]) -> bool {
222 assert_eq!(vars.len(), self.num_vars);
223 assert_eq!(input.len(), self.num_inputs);
224
225 let z = {
226 let mut z = vars.to_vec();
227 z.extend(&vec![Scalar::one()]);
228 z.extend(input);
229 z
230 };
231
232 // verify if Az * Bz - Cz = [0...]
233 let Az = self
234 .A
235 .multiply_vec(self.num_cons, self.num_vars + self.num_inputs + 1, &z);
236 let Bz = self
237 .B
238 .multiply_vec(self.num_cons, self.num_vars + self.num_inputs + 1, &z);
239 let Cz = self
240 .C
241 .multiply_vec(self.num_cons, self.num_vars + self.num_inputs + 1, &z);
242
243 assert_eq!(Az.len(), self.num_cons);
244 assert_eq!(Bz.len(), self.num_cons);
245 assert_eq!(Cz.len(), self.num_cons);
246 let res: usize = (0..self.num_cons)
247 .map(|i| if Az[i] * Bz[i] == Cz[i] { 0 } else { 1 })
248 .sum();
249
250 res == 0
251 }
252
253 pub fn multiply_vec(
254 &self,
255 num_rows: usize,
256 num_cols: usize,
257 z: &[Scalar],
258 ) -> (DensePolynomial, DensePolynomial, DensePolynomial) {
259 assert_eq!(num_rows, self.num_cons);
260 assert_eq!(z.len(), num_cols);
261 assert!(num_cols > self.num_vars);
262 (
263 DensePolynomial::new(self.A.multiply_vec(num_rows, num_cols, z)),
264 DensePolynomial::new(self.B.multiply_vec(num_rows, num_cols, z)),
265 DensePolynomial::new(self.C.multiply_vec(num_rows, num_cols, z)),
266 )
267 }
268
269 pub fn compute_eval_table_sparse(
270 &self,
271 num_rows: usize,
272 num_cols: usize,
273 evals: &[Scalar],
274 ) -> (Vec<Scalar>, Vec<Scalar>, Vec<Scalar>) {
275 assert_eq!(num_rows, self.num_cons);
276 assert!(num_cols > self.num_vars);
277
278 let evals_A = self.A.compute_eval_table_sparse(&evals, num_rows, num_cols);
279 let evals_B = self.B.compute_eval_table_sparse(&evals, num_rows, num_cols);
280 let evals_C = self.C.compute_eval_table_sparse(&evals, num_rows, num_cols);
281
282 (evals_A, evals_B, evals_C)
283 }
284
285 pub fn evaluate(&self, rx: &[Scalar], ry: &[Scalar]) -> (Scalar, Scalar, Scalar) {
286 let evals = SparseMatPolynomial::multi_evaluate(&[&self.A, &self.B, &self.C], rx, ry);
287 (evals[0], evals[1], evals[2])
288 }
289
290 pub fn commit(&self, gens: &R1CSCommitmentGens) -> (R1CSCommitment, R1CSDecommitment) {
291 let (comm, dense) = SparseMatPolynomial::multi_commit(&[&self.A, &self.B, &self.C], &gens.gens);
292 let r1cs_comm = R1CSCommitment {
293 num_cons: self.num_cons,
294 num_vars: self.num_vars,
295 num_inputs: self.num_inputs,
296 comm,
297 };
298
299 let r1cs_decomm = R1CSDecommitment { dense };
300
301 (r1cs_comm, r1cs_decomm)
302 }
303}
304
305#[derive(Debug, Serialize, Deserialize)]
306pub struct R1CSEvalProof {
307 proof: SparseMatPolyEvalProof,
308}
309
310impl R1CSEvalProof {
311 pub fn prove(
312 decomm: &R1CSDecommitment,
313 rx: &[Scalar], // point at which the polynomial is evaluated
314 ry: &[Scalar],
315 evals: &(Scalar, Scalar, Scalar),
316 gens: &R1CSCommitmentGens,
317 transcript: &mut Transcript,
318 random_tape: &mut RandomTape,
319 ) -> R1CSEvalProof {
320 let timer = Timer::new("R1CSEvalProof::prove");
321 let proof = SparseMatPolyEvalProof::prove(
322 &decomm.dense,
323 rx,
324 ry,
325 &[evals.0, evals.1, evals.2],
326 &gens.gens,
327 transcript,
328 random_tape,
329 );
330 timer.stop();
331
332 R1CSEvalProof { proof }
333 }
334
335 pub fn verify(
336 &self,
337 comm: &R1CSCommitment,
338 rx: &[Scalar], // point at which the R1CS matrix polynomials are evaluated
339 ry: &[Scalar],
340 evals: &(Scalar, Scalar, Scalar),
341 gens: &R1CSCommitmentGens,
342 transcript: &mut Transcript,
343 ) -> Result<(), ProofVerifyError> {
344 assert!(self
345 .proof
346 .verify(
347 &comm.comm,
348 rx,
349 ry,
350 &[evals.0, evals.1, evals.2],
351 &gens.gens,
352 transcript
353 )
354 .is_ok());
355
356 Ok(())
357 }
358}