testudo/src/r1csinstance.rs
src/r1csinstance.rsRaw
1use super::dense_mlpoly::DensePolynomial;
2use super::errors::ProofVerifyError;
3use super::math::Math;
4use super::random::RandomTape;
5use super::scalar::Scalar;
6use super::sparse_mlpoly::{
7 MultiSparseMatPolynomialAsDense, SparseMatEntry, SparseMatPolyCommitment,
8 SparseMatPolyCommitmentGens, SparseMatPolyEvalProof, SparseMatPolynomial,
9};
10use super::timer::Timer;
11use merlin::Transcript;
12use rand::rngs::OsRng;
13use serde::{Deserialize, Serialize};
14
15#[derive(Debug)]
16pub struct R1CSInstance {
17 num_cons: usize,
18 num_vars: usize,
19 num_inputs: usize,
20 A: SparseMatPolynomial,
21 B: SparseMatPolynomial,
22 C: SparseMatPolynomial,
23}
24
25pub struct R1CSCommitmentGens {
26 gens: SparseMatPolyCommitmentGens,
27}
28
29impl R1CSCommitmentGens {
30 pub fn new(
31 label: &'static [u8],
32 num_cons: usize,
33 num_vars: usize,
34 num_inputs: usize,
35 num_nz_entries: usize,
36 ) -> R1CSCommitmentGens {
37 assert!(num_inputs < num_vars);
38 let num_poly_vars_x = num_cons.log2();
39 let num_poly_vars_y = (2 * num_vars).log2();
40 let gens =
41 SparseMatPolyCommitmentGens::new(label, num_poly_vars_x, num_poly_vars_y, num_nz_entries, 3);
42 R1CSCommitmentGens { gens }
43 }
44}
45
46pub struct R1CSCommitment {
47 num_cons: usize,
48 num_vars: usize,
49 num_inputs: usize,
50 comm: SparseMatPolyCommitment,
51}
52
53pub struct R1CSDecommitment {
54 dense: MultiSparseMatPolynomialAsDense,
55}
56
57impl R1CSCommitment {
58 pub fn get_num_cons(&self) -> usize {
59 self.num_cons
60 }
61
62 pub fn get_num_vars(&self) -> usize {
63 self.num_vars
64 }
65
66 pub fn get_num_inputs(&self) -> usize {
67 self.num_inputs
68 }
69}
70
71impl R1CSInstance {
72 pub fn new(
73 num_cons: usize,
74 num_vars: usize,
75 num_inputs: usize,
76 A: SparseMatPolynomial,
77 B: SparseMatPolynomial,
78 C: SparseMatPolynomial,
79 ) -> Self {
80 R1CSInstance {
81 num_cons,
82 num_vars,
83 num_inputs,
84 A,
85 B,
86 C,
87 }
88 }
89
90 pub fn get_num_vars(&self) -> usize {
91 self.num_vars
92 }
93
94 pub fn get_num_cons(&self) -> usize {
95 self.num_cons
96 }
97
98 pub fn get_num_inputs(&self) -> usize {
99 self.num_inputs
100 }
101
102 pub fn produce_synthetic_r1cs(
103 num_cons: usize,
104 num_vars: usize,
105 num_inputs: usize,
106 ) -> (R1CSInstance, Vec<Scalar>, Vec<Scalar>) {
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
111 let mut csprng: OsRng = OsRng;
112
113 // assert num_cons and num_vars are power of 2
114 assert_eq!(num_cons.log2().pow2(), num_cons);
115 assert_eq!(num_vars.log2().pow2(), num_vars);
116
117 // num_inputs + 1 <= num_vars
118 assert!(num_inputs < num_vars);
119
120 // z is organized as [vars,1,io]
121 let size_z = num_vars + num_inputs + 1;
122
123 // produce a random satisfying assignment
124 let Z = {
125 let mut Z: Vec<Scalar> = (0..size_z)
126 .map(|_i| Scalar::random(&mut csprng))
127 .collect::<Vec<Scalar>>();
128 Z[num_vars] = Scalar::one(); // set the constant term to 1
129 Z
130 };
131
132 // three sparse matrices
133 let mut A: Vec<SparseMatEntry> = Vec::new();
134 let mut B: Vec<SparseMatEntry> = Vec::new();
135 let mut C: Vec<SparseMatEntry> = Vec::new();
136 let one = Scalar::one();
137 for i in 0..num_cons {
138 let A_idx = i % size_z;
139 let B_idx = (i + 2) % size_z;
140 A.push(SparseMatEntry::new(i, A_idx, one));
141 B.push(SparseMatEntry::new(i, B_idx, one));
142 let AB_val = Z[A_idx] * Z[B_idx];
143
144 let C_idx = (i + 3) % size_z;
145 let C_val = Z[C_idx];
146
147 if C_val == Scalar::zero() {
148 C.push(SparseMatEntry::new(i, num_vars, AB_val));
149 } else {
150 C.push(SparseMatEntry::new(
151 i,
152 C_idx,
153 AB_val * C_val.invert().unwrap(),
154 ));
155 }
156 }
157
158 Timer::print(&format!("number_non-zero_entries_A {}", A.len()));
159 Timer::print(&format!("number_non-zero_entries_B {}", B.len()));
160 Timer::print(&format!("number_non-zero_entries_C {}", C.len()));
161
162 let num_poly_vars_x = num_cons.log2();
163 let num_poly_vars_y = (2 * num_vars).log2();
164 let poly_A = SparseMatPolynomial::new(num_poly_vars_x, num_poly_vars_y, A);
165 let poly_B = SparseMatPolynomial::new(num_poly_vars_x, num_poly_vars_y, B);
166 let poly_C = SparseMatPolynomial::new(num_poly_vars_x, num_poly_vars_y, C);
167
168 let inst = R1CSInstance::new(num_cons, num_vars, num_inputs, poly_A, poly_B, poly_C);
169
170 assert_eq!(
171 inst.is_sat(&Z[0..num_vars].to_vec(), &Z[num_vars + 1..].to_vec()),
172 true,
173 );
174
175 (inst, Z[0..num_vars].to_vec(), Z[num_vars + 1..].to_vec())
176 }
177
178 pub fn is_sat(&self, vars: &[Scalar], input: &[Scalar]) -> bool {
179 assert_eq!(vars.len(), self.num_vars);
180 assert_eq!(input.len(), self.num_inputs);
181
182 let z = {
183 let mut z = vars.to_vec();
184 z.extend(&vec![Scalar::one()]);
185 z.extend(input);
186 z
187 };
188
189 // verify if Az * Bz - Cz = [0...]
190 let Az = self
191 .A
192 .multiply_vec(self.num_cons, self.num_vars + self.num_inputs + 1, &z);
193 let Bz = self
194 .B
195 .multiply_vec(self.num_cons, self.num_vars + self.num_inputs + 1, &z);
196 let Cz = self
197 .C
198 .multiply_vec(self.num_cons, self.num_vars + self.num_inputs + 1, &z);
199
200 assert_eq!(Az.len(), self.num_cons);
201 assert_eq!(Bz.len(), self.num_cons);
202 assert_eq!(Cz.len(), self.num_cons);
203 let res: usize = (0..self.num_cons)
204 .map(|i| if Az[i] * Bz[i] == Cz[i] { 0 } else { 1 })
205 .sum();
206
207 res == 0
208 }
209
210 pub fn multiply_vec(
211 &self,
212 num_rows: usize,
213 num_cols: usize,
214 z: &[Scalar],
215 ) -> (DensePolynomial, DensePolynomial, DensePolynomial) {
216 assert_eq!(num_rows, self.num_cons);
217 assert_eq!(z.len(), num_cols);
218 assert!(num_cols > self.num_vars);
219 (
220 DensePolynomial::new(self.A.multiply_vec(num_rows, num_cols, z)),
221 DensePolynomial::new(self.B.multiply_vec(num_rows, num_cols, z)),
222 DensePolynomial::new(self.C.multiply_vec(num_rows, num_cols, z)),
223 )
224 }
225
226 pub fn compute_eval_table_sparse(
227 &self,
228 num_rows: usize,
229 num_cols: usize,
230 evals: &[Scalar],
231 ) -> (Vec<Scalar>, Vec<Scalar>, Vec<Scalar>) {
232 assert_eq!(num_rows, self.num_cons);
233 assert!(num_cols > self.num_vars);
234
235 let evals_A = self.A.compute_eval_table_sparse(&evals, num_rows, num_cols);
236 let evals_B = self.B.compute_eval_table_sparse(&evals, num_rows, num_cols);
237 let evals_C = self.C.compute_eval_table_sparse(&evals, num_rows, num_cols);
238
239 (evals_A, evals_B, evals_C)
240 }
241
242 pub fn evaluate(&self, rx: &[Scalar], ry: &[Scalar]) -> (Scalar, Scalar, Scalar) {
243 let evals = SparseMatPolynomial::multi_evaluate(&[&self.A, &self.B, &self.C], rx, ry);
244 (evals[0], evals[1], evals[2])
245 }
246
247 pub fn commit(&self, gens: &R1CSCommitmentGens) -> (R1CSCommitment, R1CSDecommitment) {
248 assert_eq!(self.A.get_num_nz_entries(), self.B.get_num_nz_entries());
249 assert_eq!(self.A.get_num_nz_entries(), self.C.get_num_nz_entries());
250 let (comm, dense) = SparseMatPolynomial::multi_commit(&[&self.A, &self.B, &self.C], &gens.gens);
251 let r1cs_comm = R1CSCommitment {
252 num_cons: self.num_cons,
253 num_vars: self.num_vars,
254 num_inputs: self.num_inputs,
255 comm,
256 };
257
258 let r1cs_decomm = R1CSDecommitment { dense };
259
260 (r1cs_comm, r1cs_decomm)
261 }
262}
263
264#[derive(Debug, Serialize, Deserialize)]
265pub struct R1CSEvalProof {
266 proof: SparseMatPolyEvalProof,
267}
268
269impl R1CSEvalProof {
270 pub fn prove(
271 decomm: &R1CSDecommitment,
272 rx: &[Scalar], // point at which the polynomial is evaluated
273 ry: &[Scalar],
274 evals: &(Scalar, Scalar, Scalar),
275 gens: &R1CSCommitmentGens,
276 transcript: &mut Transcript,
277 random_tape: &mut RandomTape,
278 ) -> R1CSEvalProof {
279 let timer = Timer::new("R1CSEvalProof::prove");
280 let proof = SparseMatPolyEvalProof::prove(
281 &decomm.dense,
282 rx,
283 ry,
284 &[evals.0, evals.1, evals.2],
285 &gens.gens,
286 transcript,
287 random_tape,
288 );
289 timer.stop();
290
291 R1CSEvalProof { proof }
292 }
293
294 pub fn verify(
295 &self,
296 comm: &R1CSCommitment,
297 rx: &[Scalar], // point at which the R1CS matrix polynomials are evaluated
298 ry: &[Scalar],
299 evals: &(Scalar, Scalar, Scalar),
300 gens: &R1CSCommitmentGens,
301 transcript: &mut Transcript,
302 ) -> Result<(), ProofVerifyError> {
303 assert!(self
304 .proof
305 .verify(
306 &comm.comm,
307 rx,
308 ry,
309 &[evals.0, evals.1, evals.2],
310 &gens.gens,
311 transcript
312 )
313 .is_ok());
314
315 Ok(())
316 }
317}