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