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