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 size_A: SparseMatPolynomialSize,
29 size_B: SparseMatPolynomialSize,
30 size_C: SparseMatPolynomialSize,
31}
32
33pub struct R1CSCommitmentGens {
34 gens: SparseMatPolyCommitmentGens,
35}
36
37impl R1CSCommitmentGens {
38 pub fn new(size: &R1CSInstanceSize, label: &'static [u8]) -> R1CSCommitmentGens {
39 assert_eq!(size.size_A, size.size_B);
40 assert_eq!(size.size_A, size.size_C);
41 let gens = SparseMatPolyCommitmentGens::new(&size.size_A, 3, label);
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
71#[derive(Serialize, Deserialize, Debug)]
72pub struct R1CSInstanceEvals {
73 eval_A_r: Scalar,
74 eval_B_r: Scalar,
75 eval_C_r: Scalar,
76}
77
78impl R1CSInstanceEvals {
79 pub fn get_evaluations(&self) -> (Scalar, Scalar, Scalar) {
80 (self.eval_A_r, self.eval_B_r, self.eval_C_r)
81 }
82}
83
84impl AppendToTranscript for R1CSInstanceEvals {
85 fn append_to_transcript(&self, label: &'static [u8], transcript: &mut Transcript) {
86 transcript.append_message(label, b"R1CSInstanceEvals_begin");
87 transcript.append_scalar(b"Ar_eval", &self.eval_A_r);
88 transcript.append_scalar(b"Br_eval", &self.eval_B_r);
89 transcript.append_scalar(b"Cr_eval", &self.eval_C_r);
90 transcript.append_message(label, b"R1CSInstanceEvals_end");
91 }
92}
93
94impl R1CSInstance {
95 pub fn new(
96 num_cons: usize,
97 num_vars: usize,
98 num_inputs: usize,
99 A: SparseMatPolynomial,
100 B: SparseMatPolynomial,
101 C: SparseMatPolynomial,
102 ) -> Self {
103 R1CSInstance {
104 num_cons,
105 num_vars,
106 num_inputs,
107 A,
108 B,
109 C,
110 }
111 }
112
113 pub fn get_num_vars(&self) -> usize {
114 self.num_vars
115 }
116
117 pub fn get_num_cons(&self) -> usize {
118 self.num_cons
119 }
120
121 pub fn get_num_inputs(&self) -> usize {
122 self.num_inputs
123 }
124
125 pub fn size(&self) -> R1CSInstanceSize {
126 R1CSInstanceSize {
127 size_A: self.A.size(),
128 size_B: self.B.size(),
129 size_C: self.C.size(),
130 }
131 }
132
133 pub fn produce_synthetic_r1cs(
134 num_cons: usize,
135 num_vars: usize,
136 num_inputs: usize,
137 ) -> (R1CSInstance, Vec<Scalar>, Vec<Scalar>) {
138 let mut csprng: OsRng = OsRng;
139
140 // assert num_cons and num_vars are power of 2
141 assert_eq!(num_cons.log2().pow2(), num_cons);
142 assert_eq!(num_vars.log2().pow2(), num_vars);
143
144 // num_inputs + 1 <= num_vars
145 assert!(num_inputs + 1 <= num_vars);
146
147 // z is organized as [vars,1,io]
148 let size_z = num_vars + num_inputs + 1;
149
150 // produce a random satisfying assignment
151 let Z = {
152 let mut Z: Vec<Scalar> = (0..size_z)
153 .map(|_i| Scalar::random(&mut csprng))
154 .collect::<Vec<Scalar>>();
155 Z[num_vars] = Scalar::one(); // set the constant term to 1
156 Z
157 };
158
159 // three sparse matrices
160 let mut A: Vec<SparseMatEntry> = Vec::new();
161 let mut B: Vec<SparseMatEntry> = Vec::new();
162 let mut C: Vec<SparseMatEntry> = Vec::new();
163 let one = Scalar::one();
164 for i in 0..num_cons {
165 let A_idx = i % size_z;
166 let B_idx = (i + 2) % size_z;
167 A.push(SparseMatEntry::new(i, A_idx, one));
168 B.push(SparseMatEntry::new(i, B_idx, one));
169 let AB_val = Z[A_idx] * Z[B_idx];
170
171 let C_idx = (i + 3) % size_z;
172 let C_val = Z[C_idx];
173
174 if C_val == Scalar::zero() {
175 C.push(SparseMatEntry::new(i, num_vars, AB_val));
176 } else {
177 C.push(SparseMatEntry::new(
178 i,
179 C_idx,
180 AB_val * C_val.invert().unwrap(),
181 ));
182 }
183 }
184
185 let num_poly_vars_x = num_cons.log2();
186 let num_poly_vars_y = (2 * num_vars).log2();
187 let poly_A = SparseMatPolynomial::new(num_poly_vars_x, num_poly_vars_y, A);
188 let poly_B = SparseMatPolynomial::new(num_poly_vars_x, num_poly_vars_y, B);
189 let poly_C = SparseMatPolynomial::new(num_poly_vars_x, num_poly_vars_y, C);
190
191 let inst = R1CSInstance::new(num_cons, num_vars, num_inputs, poly_A, poly_B, poly_C);
192
193 assert_eq!(
194 inst.is_sat(&Z[0..num_vars].to_vec(), &Z[num_vars + 1..].to_vec()),
195 true,
196 );
197
198 (inst, Z[0..num_vars].to_vec(), Z[num_vars + 1..].to_vec())
199 }
200
201 pub fn is_sat(&self, vars: &Vec<Scalar>, input: &Vec<Scalar>) -> bool {
202 assert_eq!(vars.len(), self.num_vars);
203 assert_eq!(input.len(), self.num_inputs);
204
205 let z = {
206 let mut z = vars.clone();
207 z.extend(&vec![Scalar::one()]);
208 z.extend(input);
209 z
210 };
211
212 // verify if Az * Bz - Cz = [0...]
213 let Az = self
214 .A
215 .multiply_vec(self.num_cons, self.num_vars + self.num_inputs + 1, &z);
216 let Bz = self
217 .B
218 .multiply_vec(self.num_cons, self.num_vars + self.num_inputs + 1, &z);
219 let Cz = self
220 .C
221 .multiply_vec(self.num_cons, self.num_vars + self.num_inputs + 1, &z);
222
223 assert_eq!(Az.len(), self.num_cons);
224 assert_eq!(Bz.len(), self.num_cons);
225 assert_eq!(Cz.len(), self.num_cons);
226 let res: usize = (0..self.num_cons)
227 .map(|i| if Az[i] * Bz[i] == Cz[i] { 0 } else { 1 })
228 .sum();
229 if res > 0 {
230 false
231 } else {
232 true
233 }
234 }
235
236 pub fn multiply_vec(
237 &self,
238 num_rows: usize,
239 num_cols: usize,
240 z: &Vec<Scalar>,
241 ) -> (DensePolynomial, DensePolynomial, DensePolynomial) {
242 assert_eq!(num_rows, self.num_cons);
243 assert_eq!(z.len(), num_cols);
244 assert!(num_cols > self.num_vars);
245 (
246 DensePolynomial::new(self.A.multiply_vec(num_rows, num_cols, z)),
247 DensePolynomial::new(self.B.multiply_vec(num_rows, num_cols, z)),
248 DensePolynomial::new(self.C.multiply_vec(num_rows, num_cols, z)),
249 )
250 }
251
252 pub fn compute_eval_table_sparse(
253 &self,
254 num_rows: usize,
255 num_cols: usize,
256 evals: &Vec<Scalar>,
257 ) -> (Vec<Scalar>, Vec<Scalar>, Vec<Scalar>) {
258 assert_eq!(num_rows, self.num_cons);
259 assert!(num_cols > self.num_vars);
260
261 let evals_A = self.A.compute_eval_table_sparse(&evals, num_rows, num_cols);
262 let evals_B = self.B.compute_eval_table_sparse(&evals, num_rows, num_cols);
263 let evals_C = self.C.compute_eval_table_sparse(&evals, num_rows, num_cols);
264
265 (evals_A, evals_B, evals_C)
266 }
267
268 pub fn evaluate_with_tables(
269 &self,
270 evals_rx: &Vec<Scalar>,
271 evals_ry: &Vec<Scalar>,
272 ) -> R1CSInstanceEvals {
273 R1CSInstanceEvals {
274 eval_A_r: self.A.evaluate_with_tables(evals_rx, evals_ry),
275 eval_B_r: self.B.evaluate_with_tables(evals_rx, evals_ry),
276 eval_C_r: self.C.evaluate_with_tables(evals_rx, evals_ry),
277 }
278 }
279
280 pub fn commit(&self, gens: &R1CSCommitmentGens) -> (R1CSCommitment, R1CSDecommitment) {
281 assert_eq!(self.A.get_num_nz_entries(), self.B.get_num_nz_entries());
282 assert_eq!(self.A.get_num_nz_entries(), self.C.get_num_nz_entries());
283 let (comm, dense) =
284 SparseMatPolynomial::multi_commit(&vec![&self.A, &self.B, &self.C], &gens.gens);
285 let r1cs_comm = R1CSCommitment {
286 num_cons: self.num_cons,
287 num_vars: self.num_vars,
288 num_inputs: self.num_inputs,
289 comm,
290 };
291
292 let r1cs_decomm = R1CSDecommitment { dense };
293
294 (r1cs_comm, r1cs_decomm)
295 }
296}
297
298#[derive(Debug, Serialize, Deserialize)]
299pub struct R1CSEvalProof {
300 proof: SparseMatPolyEvalProof,
301}
302
303impl R1CSEvalProof {
304 pub fn prove(
305 decomm: &R1CSDecommitment,
306 rx: &Vec<Scalar>, // point at which the polynomial is evaluated
307 ry: &Vec<Scalar>,
308 evals: &R1CSInstanceEvals,
309 gens: &R1CSCommitmentGens,
310 transcript: &mut Transcript,
311 random_tape: &mut RandomTape,
312 ) -> R1CSEvalProof {
313 let timer = Timer::new("R1CSEvalProof::prove");
314 let proof = SparseMatPolyEvalProof::prove(
315 &decomm.dense,
316 rx,
317 ry,
318 &vec![evals.eval_A_r, evals.eval_B_r, evals.eval_C_r],
319 &gens.gens,
320 transcript,
321 random_tape,
322 );
323 timer.stop();
324
325 R1CSEvalProof { proof }
326 }
327
328 pub fn verify(
329 &self,
330 comm: &R1CSCommitment,
331 rx: &Vec<Scalar>, // point at which the R1CS matrix polynomials are evaluated
332 ry: &Vec<Scalar>,
333 eval: &R1CSInstanceEvals,
334 gens: &R1CSCommitmentGens,
335 transcript: &mut Transcript,
336 ) -> Result<(), ProofVerifyError> {
337 assert!(self
338 .proof
339 .verify(
340 &comm.comm,
341 rx,
342 ry,
343 &vec![eval.eval_A_r, eval.eval_B_r, eval.eval_C_r],
344 &gens.gens,
345 transcript
346 )
347 .is_ok());
348
349 Ok(())
350 }
351}