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, R1CSInstanceSize,
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(size: &R1CSInstanceSize) -> Self {
22 let gens_r1cs_sat = R1CSGens::new(size.get_num_cons(), size.get_num_vars(), b"gens_r1cs_sat");
23 let gens_r1cs_eval = R1CSCommitmentGens::new(size, b"gens_r1cs_eval");
24 SNARKGens {
25 gens_r1cs_sat,
26 gens_r1cs_eval,
27 }
28 }
29}
30
31#[derive(Serialize, Deserialize, Debug)]
32pub struct SNARK {
33 r1cs_sat_proof: R1CSProof,
34 inst_evals: R1CSInstanceEvals,
35 r1cs_eval_proof: R1CSEvalProof,
36}
37
38impl SNARK {
39 fn protocol_name() -> &'static [u8] {
40 b"Spartan SNARK proof"
41 }
42
43 /// A public computation to create a commitment to an R1CS instance
44 pub fn encode(inst: &R1CSInstance, gens: &SNARKGens) -> (R1CSCommitment, R1CSDecommitment) {
45 inst.commit(&gens.gens_r1cs_eval)
46 }
47
48 /// A method to produce a proof of the satisfiability of an R1CS instance
49 pub fn prove(
50 inst: &R1CSInstance,
51 decomm: &R1CSDecommitment,
52 vars: Vec<Scalar>,
53 input: &Vec<Scalar>,
54 gens: &SNARKGens,
55 transcript: &mut Transcript,
56 ) -> Self {
57 // we create a Transcript object seeded with a random Scalar
58 // to aid the prover produce its randomness
59 let mut random_tape = RandomTape::new(b"proof");
60 transcript.append_protocol_name(SNARK::protocol_name());
61 let (r1cs_sat_proof, rx, ry) = {
62 let (proof, rx, ry) = R1CSProof::prove(
63 inst,
64 vars,
65 input,
66 &gens.gens_r1cs_sat,
67 transcript,
68 &mut random_tape,
69 );
70 let proof_encoded: Vec<u8> = bincode::serialize(&proof).unwrap();
71 Timer::print(&format!("len_r1cs_sat_proof {:?}", proof_encoded.len()));
72
73 (proof, rx, ry)
74 };
75
76 // We send evaluations of A, B, C at r = (rx, ry) as claims
77 // to enable the verifier complete the first sum-check
78 let timer_eval = Timer::new("eval_sparse_polys");
79 let inst_evals = {
80 let eval_table_rx = EqPolynomial::new(rx.clone()).evals();
81 let eval_table_ry = EqPolynomial::new(ry.clone()).evals();
82 inst.evaluate_with_tables(&eval_table_rx, &eval_table_ry)
83 };
84 inst_evals.append_to_transcript(b"r1cs_inst_evals", transcript);
85 timer_eval.stop();
86
87 let r1cs_eval_proof = {
88 let proof = R1CSEvalProof::prove(
89 decomm,
90 &rx,
91 &ry,
92 &inst_evals,
93 &gens.gens_r1cs_eval,
94 transcript,
95 &mut random_tape,
96 );
97
98 let proof_encoded: Vec<u8> = bincode::serialize(&proof).unwrap();
99 Timer::print(&format!("len_r1cs_eval_proof {:?}", proof_encoded.len()));
100 proof
101 };
102
103 SNARK {
104 r1cs_sat_proof,
105 inst_evals,
106 r1cs_eval_proof,
107 }
108 }
109
110 /// A method to verify the proof of the satisfiability of an R1CS instance
111 pub fn verify(
112 &self,
113 comm: &R1CSCommitment,
114 input: &Vec<Scalar>,
115 transcript: &mut Transcript,
116 gens: &SNARKGens,
117 ) -> Result<(), ProofVerifyError> {
118 transcript.append_protocol_name(SNARK::protocol_name());
119
120 let timer_sat_proof = Timer::new("verify_sat_proof");
121 assert_eq!(input.len(), comm.get_num_inputs());
122 let (rx, ry) = self
123 .r1cs_sat_proof
124 .verify(
125 comm.get_num_vars(),
126 comm.get_num_cons(),
127 input,
128 &self.inst_evals,
129 transcript,
130 &gens.gens_r1cs_sat,
131 )
132 .unwrap();
133 timer_sat_proof.stop();
134
135 let timer_eval_proof = Timer::new("verify_eval_proof");
136 self
137 .inst_evals
138 .append_to_transcript(b"r1cs_inst_evals", transcript);
139 assert!(self
140 .r1cs_eval_proof
141 .verify(
142 comm,
143 &rx,
144 &ry,
145 &self.inst_evals,
146 &gens.gens_r1cs_eval,
147 transcript
148 )
149 .is_ok());
150 timer_eval_proof.stop();
151 Ok(())
152 }
153}
154
155pub struct NIZKGens {
156 gens_r1cs_sat: R1CSGens,
157}
158
159impl NIZKGens {
160 pub fn new(num_cons: usize, num_vars: usize) -> Self {
161 let gens_r1cs_sat = R1CSGens::new(num_cons, num_vars, b"gens_r1cs_sat");
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 let r1cs_size = inst.size();
265
266 // produce public generators
267 let gens = SNARKGens::new(&r1cs_size);
268
269 // create a commitment to R1CSInstance
270 let (comm, decomm) = SNARK::encode(&inst, &gens);
271
272 // produce a proof
273 let mut prover_transcript = Transcript::new(b"example");
274 let proof = SNARK::prove(&inst, &decomm, vars, &input, &gens, &mut prover_transcript);
275
276 // verify the proof
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}