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