testudo/src/r1csinstance.rs
src/r1csinstance.rsRaw
1use crate::poseidon_transcript::{AppendToPoseidon, PoseidonTranscript};
2use crate::transcript::AppendToTranscript;
3
4use super::dense_mlpoly::DensePolynomial;
5use super::errors::ProofVerifyError;
6use super::math::Math;
7use super::random::RandomTape;
8use super::scalar::Scalar;
9use super::sparse_mlpoly::{
10 MultiSparseMatPolynomialAsDense, SparseMatEntry, SparseMatPolyCommitment,
11 SparseMatPolyCommitmentGens, SparseMatPolyEvalProof, SparseMatPolynomial,
12};
13use super::timer::Timer;
14use ark_ff::Field;
15use ark_serialize::*;
16use ark_std::{One, UniformRand, Zero};
17use merlin::Transcript;
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
29pub struct R1CSCommitmentGens {
30 gens: SparseMatPolyCommitmentGens,
31}
32
33impl R1CSCommitmentGens {
34 pub fn new(
35 label: &'static [u8],
36 num_cons: usize,
37 num_vars: usize,
38 num_inputs: usize,
39 num_nz_entries: usize,
40 ) -> R1CSCommitmentGens {
41 assert!(num_inputs < num_vars);
42 let num_poly_vars_x = num_cons.log_2();
43 let num_poly_vars_y = (2 * num_vars).log_2();
44 let gens =
45 SparseMatPolyCommitmentGens::new(label, num_poly_vars_x, num_poly_vars_y, num_nz_entries, 3);
46 R1CSCommitmentGens { gens }
47 }
48}
49
50#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
51pub struct R1CSCommitment {
52 num_cons: usize,
53 num_vars: usize,
54 num_inputs: usize,
55 comm: SparseMatPolyCommitment,
56}
57
58impl AppendToTranscript for R1CSCommitment {
59 fn append_to_transcript(&self, _label: &'static [u8], transcript: &mut Transcript) {
60 transcript.append_u64(b"num_cons", self.num_cons as u64);
61 transcript.append_u64(b"num_vars", self.num_vars as u64);
62 transcript.append_u64(b"num_inputs", self.num_inputs as u64);
63 self.comm.append_to_transcript(b"comm", transcript);
64 }
65}
66
67impl AppendToPoseidon for R1CSCommitment {
68 fn append_to_poseidon(&self, transcript: &mut PoseidonTranscript) {
69 transcript.append_u64(self.num_cons as u64);
70 transcript.append_u64(self.num_vars as u64);
71 transcript.append_u64(self.num_inputs as u64);
72 self.comm.append_to_poseidon(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.log_2();
121 let num_poly_vars_y = (2 * num_vars).log_2();
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 get_digest(&self) -> Vec<u8> {
160 let mut bytes = Vec::new();
161 self.serialize(&mut bytes).unwrap();
162 bytes
163 }
164
165 pub fn produce_synthetic_r1cs(
166 num_cons: usize,
167 num_vars: usize,
168 num_inputs: usize,
169 ) -> (R1CSInstance, Vec<Scalar>, Vec<Scalar>) {
170 Timer::print(&format!("number_of_constraints {}", num_cons));
171 Timer::print(&format!("number_of_variables {}", num_vars));
172 Timer::print(&format!("number_of_inputs {}", num_inputs));
173
174 let mut rng = ark_std::rand::thread_rng();
175
176 // assert num_cons and num_vars are power of 2
177 assert_eq!((num_cons.log_2()).pow2(), num_cons);
178 assert_eq!((num_vars.log_2()).pow2(), num_vars);
179
180 // num_inputs + 1 <= num_vars
181 assert!(num_inputs < num_vars);
182
183 // z is organized as [vars,1,io]
184 let size_z = num_vars + num_inputs + 1;
185
186 // produce a random satisfying assignment
187 let Z = {
188 let mut Z: Vec<Scalar> = (0..size_z)
189 .map(|_i| Scalar::rand(&mut rng))
190 .collect::<Vec<Scalar>>();
191 Z[num_vars] = Scalar::one(); // set the constant term to 1
192 Z
193 };
194
195 // three sparse matrices
196 let mut A: Vec<SparseMatEntry> = Vec::new();
197 let mut B: Vec<SparseMatEntry> = Vec::new();
198 let mut C: Vec<SparseMatEntry> = Vec::new();
199 let one = Scalar::one();
200 for i in 0..num_cons {
201 let A_idx = i % size_z;
202 let B_idx = (i + 2) % size_z;
203 A.push(SparseMatEntry::new(i, A_idx, one));
204 B.push(SparseMatEntry::new(i, B_idx, one));
205 let AB_val = Z[A_idx] * Z[B_idx];
206
207 let C_idx = (i + 3) % size_z;
208 let C_val = Z[C_idx];
209
210 if C_val == Scalar::zero() {
211 C.push(SparseMatEntry::new(i, num_vars, AB_val));
212 } else {
213 C.push(SparseMatEntry::new(
214 i,
215 C_idx,
216 AB_val * C_val.inverse().unwrap(),
217 ));
218 }
219 }
220
221 Timer::print(&format!("number_non-zero_entries_A {}", A.len()));
222 Timer::print(&format!("number_non-zero_entries_B {}", B.len()));
223 Timer::print(&format!("number_non-zero_entries_C {}", C.len()));
224
225 let num_poly_vars_x = num_cons.log_2();
226 let num_poly_vars_y = (2 * num_vars).log_2();
227 let poly_A = SparseMatPolynomial::new(num_poly_vars_x, num_poly_vars_y, A);
228 let poly_B = SparseMatPolynomial::new(num_poly_vars_x, num_poly_vars_y, B);
229 let poly_C = SparseMatPolynomial::new(num_poly_vars_x, num_poly_vars_y, C);
230
231 let inst = R1CSInstance {
232 num_cons,
233 num_vars,
234 num_inputs,
235 A: poly_A,
236 B: poly_B,
237 C: poly_C,
238 };
239
240 assert!(inst.is_sat(&Z[..num_vars], &Z[num_vars + 1..]));
241
242 (inst, Z[..num_vars].to_vec(), Z[num_vars + 1..].to_vec())
243 }
244
245 pub fn is_sat(&self, vars: &[Scalar], input: &[Scalar]) -> bool {
246 assert_eq!(vars.len(), self.num_vars);
247 assert_eq!(input.len(), self.num_inputs);
248
249 let z = {
250 let mut z = vars.to_vec();
251 z.extend(&vec![Scalar::one()]);
252 z.extend(input);
253 z
254 };
255
256 // verify if Az * Bz - Cz = [0...]
257 let Az = self
258 .A
259 .multiply_vec(self.num_cons, self.num_vars + self.num_inputs + 1, &z);
260 let Bz = self
261 .B
262 .multiply_vec(self.num_cons, self.num_vars + self.num_inputs + 1, &z);
263 let Cz = self
264 .C
265 .multiply_vec(self.num_cons, self.num_vars + self.num_inputs + 1, &z);
266
267 assert_eq!(Az.len(), self.num_cons);
268 assert_eq!(Bz.len(), self.num_cons);
269 assert_eq!(Cz.len(), self.num_cons);
270 let res: usize = (0..self.num_cons)
271 .map(|i| usize::from(Az[i] * Bz[i] != Cz[i]))
272 .sum();
273
274 res == 0
275 }
276
277 pub fn multiply_vec(
278 &self,
279 num_rows: usize,
280 num_cols: usize,
281 z: &[Scalar],
282 ) -> (DensePolynomial, DensePolynomial, DensePolynomial) {
283 assert_eq!(num_rows, self.num_cons);
284 assert_eq!(z.len(), num_cols);
285 assert!(num_cols > self.num_vars);
286 (
287 DensePolynomial::new(self.A.multiply_vec(num_rows, num_cols, z)),
288 DensePolynomial::new(self.B.multiply_vec(num_rows, num_cols, z)),
289 DensePolynomial::new(self.C.multiply_vec(num_rows, num_cols, z)),
290 )
291 }
292
293 pub fn compute_eval_table_sparse(
294 &self,
295 num_rows: usize,
296 num_cols: usize,
297 evals: &[Scalar],
298 ) -> (Vec<Scalar>, Vec<Scalar>, Vec<Scalar>) {
299 assert_eq!(num_rows, self.num_cons);
300 assert!(num_cols > self.num_vars);
301
302 let evals_A = self.A.compute_eval_table_sparse(evals, num_rows, num_cols);
303 let evals_B = self.B.compute_eval_table_sparse(evals, num_rows, num_cols);
304 let evals_C = self.C.compute_eval_table_sparse(evals, num_rows, num_cols);
305
306 (evals_A, evals_B, evals_C)
307 }
308
309 pub fn evaluate(&self, rx: &[Scalar], ry: &[Scalar]) -> (Scalar, Scalar, Scalar) {
310 let evals = SparseMatPolynomial::multi_evaluate(&[&self.A, &self.B, &self.C], rx, ry);
311 (evals[0], evals[1], evals[2])
312 }
313
314 pub fn commit(&self, gens: &R1CSCommitmentGens) -> (R1CSCommitment, R1CSDecommitment) {
315 let (comm, dense) = SparseMatPolynomial::multi_commit(&[&self.A, &self.B, &self.C], &gens.gens);
316 let r1cs_comm = R1CSCommitment {
317 num_cons: self.num_cons,
318 num_vars: self.num_vars,
319 num_inputs: self.num_inputs,
320 comm,
321 };
322
323 let r1cs_decomm = R1CSDecommitment { dense };
324
325 (r1cs_comm, r1cs_decomm)
326 }
327}
328
329#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
330pub struct R1CSEvalProof {
331 proof: SparseMatPolyEvalProof,
332}
333
334impl R1CSEvalProof {
335 pub fn prove(
336 decomm: &R1CSDecommitment,
337 rx: &[Scalar], // point at which the polynomial is evaluated
338 ry: &[Scalar],
339 evals: &(Scalar, Scalar, Scalar),
340 gens: &R1CSCommitmentGens,
341 transcript: &mut PoseidonTranscript,
342 random_tape: &mut RandomTape,
343 ) -> R1CSEvalProof {
344 let timer = Timer::new("R1CSEvalProof::prove");
345 let proof = SparseMatPolyEvalProof::prove(
346 &decomm.dense,
347 rx,
348 ry,
349 &[evals.0, evals.1, evals.2],
350 &gens.gens,
351 transcript,
352 random_tape,
353 );
354 timer.stop();
355
356 R1CSEvalProof { proof }
357 }
358
359 pub fn verify(
360 &self,
361 comm: &R1CSCommitment,
362 rx: &[Scalar], // point at which the R1CS matrix polynomials are evaluated
363 ry: &[Scalar],
364 evals: &(Scalar, Scalar, Scalar),
365 gens: &R1CSCommitmentGens,
366 transcript: &mut PoseidonTranscript,
367 ) -> Result<(), ProofVerifyError> {
368 self.proof.verify(
369 &comm.comm,
370 rx,
371 ry,
372 &[evals.0, evals.1, evals.2],
373 &gens.gens,
374 transcript,
375 )
376 }
377}