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