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