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