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