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