testudo/src/spartan.rs
src/spartan.rsRaw
1use super::dense_mlpoly::EqPolynomial;
2use super::errors::ProofVerifyError;
3use super::r1csinstance::{
4 R1CSCommitment, R1CSCommitmentGens, R1CSDecommitment, R1CSEvalProof, R1CSInstance,
5 R1CSInstanceEvals,
6};
7use super::r1csproof::{R1CSGens, R1CSProof};
8use super::scalar::Scalar;
9use super::timer::Timer;
10use super::transcript::{AppendToTranscript, ProofTranscript};
11use merlin::Transcript;
12use rand::rngs::OsRng;
13use serde::{Deserialize, Serialize};
14
15pub struct SNARKGens {
16 gens_r1cs_sat: R1CSGens,
17 gens_r1cs_eval: R1CSCommitmentGens,
18}
19
20impl SNARKGens {
21 pub fn new(gens_r1cs_sat: R1CSGens, gens_r1cs_eval: R1CSCommitmentGens) -> Self {
22 SNARKGens {
23 gens_r1cs_sat,
24 gens_r1cs_eval,
25 }
26 }
27}
28
29#[derive(Serialize, Deserialize, Debug)]
30pub struct SNARK {
31 r1cs_sat_proof: R1CSProof,
32 inst_evals: R1CSInstanceEvals,
33 r1cs_eval_proof: R1CSEvalProof,
34}
35
36impl SNARK {
37 fn protocol_name() -> &'static [u8] {
38 b"Spartan SNARK proof"
39 }
40
41 /// A public computation to create a commitment to an R1CS instance
42 pub fn encode(
43 inst: &R1CSInstance,
44 gens: &R1CSCommitmentGens,
45 ) -> (R1CSCommitment, R1CSDecommitment) {
46 inst.commit(gens)
47 }
48
49 /// A method to produce a proof of the satisfiability of an R1CS instance
50 pub fn prove(
51 inst: &R1CSInstance,
52 decomm: &R1CSDecommitment,
53 vars: Vec<Scalar>,
54 input: &Vec<Scalar>,
55 gens: &SNARKGens,
56 transcript: &mut Transcript,
57 ) -> Self {
58 // we create a Transcript object seeded with a random Scalar
59 // to aid the prover produce its randomness
60 let mut random_tape = {
61 let mut csprng: OsRng = OsRng;
62 let mut tape = Transcript::new(b"SpartanSNARKProof");
63 tape.append_scalar(b"init_randomness", &Scalar::random(&mut csprng));
64 tape
65 };
66
67 transcript.append_protocol_name(SNARK::protocol_name());
68 let (r1cs_sat_proof, rx, ry) = {
69 let (proof, rx, ry) = R1CSProof::prove(
70 inst,
71 vars,
72 input,
73 &gens.gens_r1cs_sat,
74 transcript,
75 &mut random_tape,
76 );
77 let proof_encoded: Vec<u8> = bincode::serialize(&proof).unwrap();
78 Timer::print(&format!("len_r1cs_sat_proof {:?}", proof_encoded.len()));
79
80 (proof, rx, ry)
81 };
82
83 // We send evaluations of A, B, C at r = (rx, ry) as claims
84 // to enable the verifier complete the first sum-check
85 let timer_eval = Timer::new("eval_sparse_polys");
86 let inst_evals = {
87 let eval_table_rx = EqPolynomial::new(rx.clone()).evals();
88 let eval_table_ry = EqPolynomial::new(ry.clone()).evals();
89 inst.evaluate_with_tables(&eval_table_rx, &eval_table_ry)
90 };
91 inst_evals.append_to_transcript(b"r1cs_inst_evals", transcript);
92 timer_eval.stop();
93
94 let r1cs_eval_proof = {
95 let proof = R1CSEvalProof::prove(
96 decomm,
97 &rx,
98 &ry,
99 &inst_evals,
100 &gens.gens_r1cs_eval,
101 transcript,
102 &mut random_tape,
103 );
104
105 let proof_encoded: Vec<u8> = bincode::serialize(&proof).unwrap();
106 Timer::print(&format!("len_r1cs_eval_proof {:?}", proof_encoded.len()));
107 proof
108 };
109
110 SNARK {
111 r1cs_sat_proof,
112 inst_evals,
113 r1cs_eval_proof,
114 }
115 }
116
117 /// A method to verify the proof of the satisfiability of an R1CS instance
118 pub fn verify(
119 &self,
120 comm: &R1CSCommitment,
121 input: &Vec<Scalar>,
122 transcript: &mut Transcript,
123 gens: &SNARKGens,
124 ) -> Result<(), ProofVerifyError> {
125 transcript.append_protocol_name(SNARK::protocol_name());
126
127 let timer_sat_proof = Timer::new("verify_sat_proof");
128 assert_eq!(input.len(), comm.get_num_inputs());
129 let (rx, ry) = self
130 .r1cs_sat_proof
131 .verify(
132 comm.get_num_vars(),
133 comm.get_num_cons(),
134 input,
135 &self.inst_evals,
136 transcript,
137 &gens.gens_r1cs_sat,
138 )
139 .unwrap();
140 timer_sat_proof.stop();
141
142 let timer_eval_proof = Timer::new("verify_eval_proof");
143 self
144 .inst_evals
145 .append_to_transcript(b"r1cs_inst_evals", transcript);
146 assert!(self
147 .r1cs_eval_proof
148 .verify(
149 comm,
150 &rx,
151 &ry,
152 &self.inst_evals,
153 &gens.gens_r1cs_eval,
154 transcript
155 )
156 .is_ok());
157 timer_eval_proof.stop();
158 Ok(())
159 }
160}
161
162pub struct NIZKGens {
163 gens_r1cs_sat: R1CSGens,
164}
165
166impl NIZKGens {
167 pub fn new(gens_r1cs_sat: R1CSGens) -> Self {
168 NIZKGens { gens_r1cs_sat }
169 }
170}
171
172#[derive(Serialize, Deserialize, Debug)]
173pub struct NIZK {
174 r1cs_sat_proof: R1CSProof,
175 r: (Vec<Scalar>, Vec<Scalar>),
176}
177
178impl NIZK {
179 fn protocol_name() -> &'static [u8] {
180 b"Spartan NIZK proof"
181 }
182
183 /// A method to produce a proof of the satisfiability of an R1CS instance
184 pub fn prove(
185 inst: &R1CSInstance,
186 vars: Vec<Scalar>,
187 input: &Vec<Scalar>,
188 gens: &NIZKGens,
189 transcript: &mut Transcript,
190 ) -> Self {
191 // we create a Transcript object seeded with a random Scalar
192 // to aid the prover produce its randomness
193 let mut random_tape = {
194 let mut csprng: OsRng = OsRng;
195 let mut tape = Transcript::new(b"SpartanNIZKProof");
196 tape.append_scalar(b"init_randomness", &Scalar::random(&mut csprng));
197 tape
198 };
199
200 transcript.append_protocol_name(NIZK::protocol_name());
201 let (r1cs_sat_proof, rx, ry) = {
202 let (proof, rx, ry) = R1CSProof::prove(
203 inst,
204 vars,
205 input,
206 &gens.gens_r1cs_sat,
207 transcript,
208 &mut random_tape,
209 );
210 let proof_encoded: Vec<u8> = bincode::serialize(&proof).unwrap();
211 Timer::print(&format!("len_r1cs_sat_proof {:?}", proof_encoded.len()));
212
213 (proof, rx, ry)
214 };
215
216 NIZK {
217 r1cs_sat_proof,
218 r: (rx, ry),
219 }
220 }
221
222 /// A method to verify the proof of the satisfiability of an R1CS instance
223 pub fn verify(
224 &self,
225 inst: &R1CSInstance,
226 input: &Vec<Scalar>,
227 transcript: &mut Transcript,
228 gens: &NIZKGens,
229 ) -> Result<(), ProofVerifyError> {
230 transcript.append_protocol_name(NIZK::protocol_name());
231
232 // We send evaluations of A, B, C at r = (rx, ry) as claims
233 // to enable the verifier complete the first sum-check
234 let timer_eval = Timer::new("eval_sparse_polys");
235 let (claimed_rx, claimed_ry) = &self.r;
236 let inst_evals = {
237 let eval_table_rx = EqPolynomial::new(claimed_rx.clone()).evals();
238 let eval_table_ry = EqPolynomial::new(claimed_ry.clone()).evals();
239 inst.evaluate_with_tables(&eval_table_rx, &eval_table_ry)
240 };
241 timer_eval.stop();
242
243 let timer_sat_proof = Timer::new("verify_sat_proof");
244 assert_eq!(input.len(), inst.get_num_inputs());
245 let (rx, ry) = self
246 .r1cs_sat_proof
247 .verify(
248 inst.get_num_vars(),
249 inst.get_num_cons(),
250 input,
251 &inst_evals,
252 transcript,
253 &gens.gens_r1cs_sat,
254 )
255 .unwrap();
256
257 // verify if claimed rx and ry are correct
258 assert_eq!(rx, *claimed_rx);
259 assert_eq!(ry, *claimed_ry);
260 timer_sat_proof.stop();
261
262 Ok(())
263 }
264}
265
266#[cfg(test)]
267mod tests {
268 use super::*;
269
270 #[test]
271 pub fn check_snark() {
272 let num_vars = 256;
273 let num_cons = num_vars;
274 let num_inputs = 10;
275 let (inst, vars, input) = R1CSInstance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
276
277 let r1cs_size = inst.size();
278 let gens_r1cs_eval = R1CSCommitmentGens::new(&r1cs_size, b"gens_r1cs_eval");
279
280 // create a commitment to R1CSInstance
281 let (comm, decomm) = SNARK::encode(&inst, &gens_r1cs_eval);
282
283 let gens_r1cs_sat = R1CSGens::new(num_cons, num_vars, b"gens_r1cs_sat");
284 let gens = SNARKGens::new(gens_r1cs_sat, gens_r1cs_eval);
285
286 let mut prover_transcript = Transcript::new(b"example");
287 let proof = SNARK::prove(&inst, &decomm, vars, &input, &gens, &mut prover_transcript);
288
289 let mut verifier_transcript = Transcript::new(b"example");
290 assert!(proof
291 .verify(&comm, &input, &mut verifier_transcript, &gens)
292 .is_ok());
293 }
294}