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