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