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 SparseMatPolynomialSize,
10};
11use super::timer::Timer;
12use super::transcript::{AppendToTranscript, ProofTranscript};
13use merlin::Transcript;
14use rand::rngs::OsRng;
15use serde::{Deserialize, Serialize};
16
17#[derive(Debug)]
18pub struct R1CSInstance {
19 num_cons: usize,
20 num_vars: usize,
21 num_inputs: usize,
22 A: SparseMatPolynomial,
23 B: SparseMatPolynomial,
24 C: SparseMatPolynomial,
25}
26
27pub struct R1CSInstanceSize {
28 num_cons: usize,
29 num_vars: usize,
30 num_inputs: usize,
31 size_A: SparseMatPolynomialSize,
32 size_B: SparseMatPolynomialSize,
33 size_C: SparseMatPolynomialSize,
34}
35
36impl R1CSInstanceSize {
37 pub fn get_num_cons(&self) -> usize {
38 self.num_cons
39 }
40
41 pub fn get_num_vars(&self) -> usize {
42 self.num_vars
43 }
44
45 pub fn get_num_inputs(&self) -> usize {
46 self.num_inputs
47 }
48}
49
50pub struct R1CSCommitmentGens {
51 gens: SparseMatPolyCommitmentGens,
52}
53
54impl R1CSCommitmentGens {
55 pub fn new(size: &R1CSInstanceSize, label: &'static [u8]) -> R1CSCommitmentGens {
56 assert_eq!(size.size_A, size.size_B);
57 assert_eq!(size.size_A, size.size_C);
58 let gens = SparseMatPolyCommitmentGens::new(&size.size_A, 3, label);
59 R1CSCommitmentGens { gens }
60 }
61}
62
63pub struct R1CSCommitment {
64 num_cons: usize,
65 num_vars: usize,
66 num_inputs: usize,
67 comm: SparseMatPolyCommitment,
68}
69
70pub struct R1CSDecommitment {
71 dense: MultiSparseMatPolynomialAsDense,
72}
73
74impl R1CSCommitment {
75 pub fn get_num_cons(&self) -> usize {
76 self.num_cons
77 }
78
79 pub fn get_num_vars(&self) -> usize {
80 self.num_vars
81 }
82
83 pub fn get_num_inputs(&self) -> usize {
84 self.num_inputs
85 }
86}
87
88#[derive(Serialize, Deserialize, Debug)]
89pub struct R1CSInstanceEvals {
90 eval_A_r: Scalar,
91 eval_B_r: Scalar,
92 eval_C_r: Scalar,
93}
94
95impl R1CSInstanceEvals {
96 pub fn get_evaluations(&self) -> (Scalar, Scalar, Scalar) {
97 (self.eval_A_r, self.eval_B_r, self.eval_C_r)
98 }
99}
100
101impl AppendToTranscript for R1CSInstanceEvals {
102 fn append_to_transcript(&self, label: &'static [u8], transcript: &mut Transcript) {
103 transcript.append_message(label, b"R1CSInstanceEvals_begin");
104 transcript.append_scalar(b"Ar_eval", &self.eval_A_r);
105 transcript.append_scalar(b"Br_eval", &self.eval_B_r);
106 transcript.append_scalar(b"Cr_eval", &self.eval_C_r);
107 transcript.append_message(label, b"R1CSInstanceEvals_end");
108 }
109}
110
111impl R1CSInstance {
112 pub fn new(
113 num_cons: usize,
114 num_vars: usize,
115 num_inputs: usize,
116 A: SparseMatPolynomial,
117 B: SparseMatPolynomial,
118 C: SparseMatPolynomial,
119 ) -> Self {
120 R1CSInstance {
121 num_cons,
122 num_vars,
123 num_inputs,
124 A,
125 B,
126 C,
127 }
128 }
129
130 pub fn get_num_vars(&self) -> usize {
131 self.num_vars
132 }
133
134 pub fn get_num_cons(&self) -> usize {
135 self.num_cons
136 }
137
138 pub fn get_num_inputs(&self) -> usize {
139 self.num_inputs
140 }
141
142 pub fn size(&self) -> R1CSInstanceSize {
143 R1CSInstanceSize {
144 num_cons: self.num_cons,
145 num_vars: self.num_vars,
146 num_inputs: self.num_inputs,
147 size_A: self.A.size(),
148 size_B: self.B.size(),
149 size_C: self.C.size(),
150 }
151 }
152
153 pub fn produce_synthetic_r1cs(
154 num_cons: usize,
155 num_vars: usize,
156 num_inputs: usize,
157 ) -> (R1CSInstance, Vec<Scalar>, Vec<Scalar>) {
158 let mut csprng: OsRng = OsRng;
159
160 // assert num_cons and num_vars are power of 2
161 assert_eq!(num_cons.log2().pow2(), num_cons);
162 assert_eq!(num_vars.log2().pow2(), num_vars);
163
164 // num_inputs + 1 <= num_vars
165 assert!(num_inputs + 1 <= num_vars);
166
167 // z is organized as [vars,1,io]
168 let size_z = num_vars + num_inputs + 1;
169
170 // produce a random satisfying assignment
171 let Z = {
172 let mut Z: Vec<Scalar> = (0..size_z)
173 .map(|_i| Scalar::random(&mut csprng))
174 .collect::<Vec<Scalar>>();
175 Z[num_vars] = Scalar::one(); // set the constant term to 1
176 Z
177 };
178
179 // three sparse matrices
180 let mut A: Vec<SparseMatEntry> = Vec::new();
181 let mut B: Vec<SparseMatEntry> = Vec::new();
182 let mut C: Vec<SparseMatEntry> = Vec::new();
183 let one = Scalar::one();
184 for i in 0..num_cons {
185 let A_idx = i % size_z;
186 let B_idx = (i + 2) % size_z;
187 A.push(SparseMatEntry::new(i, A_idx, one));
188 B.push(SparseMatEntry::new(i, B_idx, one));
189 let AB_val = Z[A_idx] * Z[B_idx];
190
191 let C_idx = (i + 3) % size_z;
192 let C_val = Z[C_idx];
193
194 if C_val == Scalar::zero() {
195 C.push(SparseMatEntry::new(i, num_vars, AB_val));
196 } else {
197 C.push(SparseMatEntry::new(
198 i,
199 C_idx,
200 AB_val * C_val.invert().unwrap(),
201 ));
202 }
203 }
204
205 let num_poly_vars_x = num_cons.log2();
206 let num_poly_vars_y = (2 * num_vars).log2();
207 let poly_A = SparseMatPolynomial::new(num_poly_vars_x, num_poly_vars_y, A);
208 let poly_B = SparseMatPolynomial::new(num_poly_vars_x, num_poly_vars_y, B);
209 let poly_C = SparseMatPolynomial::new(num_poly_vars_x, num_poly_vars_y, C);
210
211 let inst = R1CSInstance::new(num_cons, num_vars, num_inputs, poly_A, poly_B, poly_C);
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: &Vec<Scalar>, input: &Vec<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.clone();
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 if res > 0 {
250 false
251 } else {
252 true
253 }
254 }
255
256 pub fn multiply_vec(
257 &self,
258 num_rows: usize,
259 num_cols: usize,
260 z: &Vec<Scalar>,
261 ) -> (DensePolynomial, DensePolynomial, DensePolynomial) {
262 assert_eq!(num_rows, self.num_cons);
263 assert_eq!(z.len(), num_cols);
264 assert!(num_cols > self.num_vars);
265 (
266 DensePolynomial::new(self.A.multiply_vec(num_rows, num_cols, z)),
267 DensePolynomial::new(self.B.multiply_vec(num_rows, num_cols, z)),
268 DensePolynomial::new(self.C.multiply_vec(num_rows, num_cols, z)),
269 )
270 }
271
272 pub fn compute_eval_table_sparse(
273 &self,
274 num_rows: usize,
275 num_cols: usize,
276 evals: &Vec<Scalar>,
277 ) -> (Vec<Scalar>, Vec<Scalar>, Vec<Scalar>) {
278 assert_eq!(num_rows, self.num_cons);
279 assert!(num_cols > self.num_vars);
280
281 let evals_A = self.A.compute_eval_table_sparse(&evals, num_rows, num_cols);
282 let evals_B = self.B.compute_eval_table_sparse(&evals, num_rows, num_cols);
283 let evals_C = self.C.compute_eval_table_sparse(&evals, num_rows, num_cols);
284
285 (evals_A, evals_B, evals_C)
286 }
287
288 pub fn evaluate_with_tables(
289 &self,
290 evals_rx: &Vec<Scalar>,
291 evals_ry: &Vec<Scalar>,
292 ) -> R1CSInstanceEvals {
293 R1CSInstanceEvals {
294 eval_A_r: self.A.evaluate_with_tables(evals_rx, evals_ry),
295 eval_B_r: self.B.evaluate_with_tables(evals_rx, evals_ry),
296 eval_C_r: self.C.evaluate_with_tables(evals_rx, evals_ry),
297 }
298 }
299
300 pub fn commit(&self, gens: &R1CSCommitmentGens) -> (R1CSCommitment, R1CSDecommitment) {
301 assert_eq!(self.A.get_num_nz_entries(), self.B.get_num_nz_entries());
302 assert_eq!(self.A.get_num_nz_entries(), self.C.get_num_nz_entries());
303 let (comm, dense) =
304 SparseMatPolynomial::multi_commit(&vec![&self.A, &self.B, &self.C], &gens.gens);
305 let r1cs_comm = R1CSCommitment {
306 num_cons: self.num_cons,
307 num_vars: self.num_vars,
308 num_inputs: self.num_inputs,
309 comm,
310 };
311
312 let r1cs_decomm = R1CSDecommitment { dense };
313
314 (r1cs_comm, r1cs_decomm)
315 }
316}
317
318#[derive(Debug, Serialize, Deserialize)]
319pub struct R1CSEvalProof {
320 proof: SparseMatPolyEvalProof,
321}
322
323impl R1CSEvalProof {
324 pub fn prove(
325 decomm: &R1CSDecommitment,
326 rx: &Vec<Scalar>, // point at which the polynomial is evaluated
327 ry: &Vec<Scalar>,
328 evals: &R1CSInstanceEvals,
329 gens: &R1CSCommitmentGens,
330 transcript: &mut Transcript,
331 random_tape: &mut RandomTape,
332 ) -> R1CSEvalProof {
333 let timer = Timer::new("R1CSEvalProof::prove");
334 let proof = SparseMatPolyEvalProof::prove(
335 &decomm.dense,
336 rx,
337 ry,
338 &vec![evals.eval_A_r, evals.eval_B_r, evals.eval_C_r],
339 &gens.gens,
340 transcript,
341 random_tape,
342 );
343 timer.stop();
344
345 R1CSEvalProof { proof }
346 }
347
348 pub fn verify(
349 &self,
350 comm: &R1CSCommitment,
351 rx: &Vec<Scalar>, // point at which the R1CS matrix polynomials are evaluated
352 ry: &Vec<Scalar>,
353 eval: &R1CSInstanceEvals,
354 gens: &R1CSCommitmentGens,
355 transcript: &mut Transcript,
356 ) -> Result<(), ProofVerifyError> {
357 assert!(self
358 .proof
359 .verify(
360 &comm.comm,
361 rx,
362 ry,
363 &vec![eval.eval_A_r, eval.eval_B_r, eval.eval_C_r],
364 &gens.gens,
365 transcript
366 )
367 .is_ok());
368
369 Ok(())
370 }
371}