testudo/README.md
README.mdRaw
1# Spartan: High-speed zkSNARKs without trusted setup
2
3
4
5Spartan is a high-speed zero-knowledge proof system, a cryptographic primitive that enables a prover to prove a mathematical statement to a verifier without revealing anything besides the validity of the statement. This repository provides `libspartan,` a Rust library that implements a zero-knowledge succinct non-interactive argument of knowledge (zkSNARK), which is a type of zero-knowledge proof system with short proofs and fast verification times. The details of the Spartan proof system are described in our [paper](https://eprint.iacr.org/2019/550) published at [CRYPTO 2020](https://crypto.iacr.org/2020/).
6
7A simple example application is proving the knowledge of a secret s such that H(s) == d for a public d, where H is a cryptographic hash function (e.g., SHA-256, Keccak). A more complex application is a database-backed cloud service that produces proofs of correct state machine transitions for auditability. See this [paper](https://eprint.iacr.org/2020/758.pdf) for an overview and this [paper](https://eprint.iacr.org/2018/907.pdf) for details.
8
9Note that this library has *not* received a security review or audit.
10
11## Highlights
12We now highlight Spartan's distinctive features.
13
14* **No "toxic" waste:** Spartan is a *transparent* zkSNARK and does not require a trusted setup. So, it does not involve any trapdoors that must be kept secret or require a multi-party ceremony to produce public parameters.
15
16* **General-purpose:** Spartan produces proofs for arbitrary NP statements. `libspartan` supports NP statements expressed as rank-1 constraint satisfiability (R1CS) instances, a popular language for which there exists efficient transformations and compiler toolchains from high-level programs of interest.
17
18* **Sub-linear verification costs and linear-time proving costs:** Spartan is the first transparent proof system with sub-linear verification costs for arbitrary NP statements (e.g., R1CS). Spartan also features a linear-time prover, a property that has remained elusive for nearly all zkSNARKs in the literature.
19
20* **Standardized security:** Spartan's security relies on the hardness of computing discrete logarithms (a standard cryptographic assumption) in the random oracle model. `libspartan` uses `ristretto255`, a prime-order group abstraction atop `curve25519` (a high-speed elliptic curve). We use [`curve25519-dalek`](https://docs.rs/curve25519-dalek) for arithmetic over `ristretto255`.
21
22* **State-of-the-art performance:**
23Among transparent SNARKs, Spartan offers the fastest prover with speedups of 36–152× depending on the baseline, produces proofs that are shorter by 1.2–416×, and incurs the lowest verification times with speedups of 3.6–1326×. The only exception is proof sizes under Bulletproofs, but Bulletproofs incurs slower verification both asymptotically and concretely. When compared to the state-of-the-art zkSNARK with trusted setup, Spartan’s prover is 2× faster for arbitrary R1CS instances and 16× faster for data-parallel workloads.
24
25### Implementation details
26`libspartan` uses [`merlin`](https://docs.rs/merlin/) to automate the Fiat-Shamir transform. We also introduce a new type called `RandomTape` that extends a `Transcript` in `merlin` to allow the prover's internal methods to produce private randomness using its private transcript without having to create `OsRng` objects throughout the code. An object of type `RandomTape` is initialized with a new random seed from `OsRng` for each proof produced by the library.
27
28## Examples
29The following example shows how to use `libspartan` to create and verify a SNARK proof.
30Some of our public APIs' style is inspired by the underlying crates we use.
31
32```rust
33# extern crate libspartan;
34# extern crate merlin;
35# use libspartan::{Instance, SNARKGens, SNARK};
36# use merlin::Transcript;
37# fn main() {
38 // specify the size of an R1CS instance
39 let num_vars = 1024;
40 let num_cons = 1024;
41 let num_inputs = 10;
42 let num_non_zero_entries = 1024;
43
44 // produce public parameters
45 let gens = SNARKGens::new(num_cons, num_vars, num_inputs, num_non_zero_entries);
46
47 // ask the library to produce a synthentic R1CS instance
48 let (inst, vars, inputs) = Instance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
49
50 // create a commitment to the R1CS instance
51 let (comm, decomm) = SNARK::encode(&inst, &gens);
52
53 // produce a proof of satisfiability
54 let mut prover_transcript = Transcript::new(b"snark_example");
55 let proof = SNARK::prove(&inst, &decomm, vars, &inputs, &gens, &mut prover_transcript);
56
57 // verify the proof of satisfiability
58 let mut verifier_transcript = Transcript::new(b"snark_example");
59 assert!(proof
60 .verify(&comm, &inputs, &mut verifier_transcript, &gens)
61 .is_ok());
62# }
63```
64
65Here is another example to use the NIZK variant of the Spartan proof system:
66```rust
67# extern crate libspartan;
68# extern crate merlin;
69# use libspartan::{Instance, NIZKGens, NIZK};
70# use merlin::Transcript;
71# fn main() {
72 // specify the size of an R1CS instance
73 let num_vars = 1024;
74 let num_cons = 1024;
75 let num_inputs = 10;
76
77 // produce public parameters
78 let gens = NIZKGens::new(num_cons, num_vars);
79
80 // ask the library to produce a synthentic R1CS instance
81 let (inst, vars, inputs) = Instance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
82
83 // produce a proof of satisfiability
84 let mut prover_transcript = Transcript::new(b"nizk_example");
85 let proof = NIZK::prove(&inst, vars, &inputs, &gens, &mut prover_transcript);
86
87 // verify the proof of satisfiability
88 let mut verifier_transcript = Transcript::new(b"nizk_example");
89 assert!(proof
90 .verify(&inst, &inputs, &mut verifier_transcript, &gens)
91 .is_ok());
92# }
93```
94
95Finally, we provide an example that specifies a custom R1CS instance instead of using a synthetic instance
96```rust
97# extern crate curve25519_dalek;
98# extern crate libspartan;
99# extern crate merlin;
100# use curve25519_dalek::scalar::Scalar;
101# use libspartan::{InputsAssignment, Instance, SNARKGens, VarsAssignment, SNARK};
102# use merlin::Transcript;
103# use rand::rngs::OsRng;
104# fn main() {
105 // produce a tiny instance
106 let (
107 num_cons,
108 num_vars,
109 num_inputs,
110 num_non_zero_entries,
111 inst,
112 assignment_vars,
113 assignment_inputs,
114 ) = produce_tiny_r1cs();
115
116 // produce public parameters
117 let gens = SNARKGens::new(num_cons, num_vars, num_inputs, num_non_zero_entries);
118
119 // create a commitment to the R1CS instance
120 let (comm, decomm) = SNARK::encode(&inst, &gens);
121
122 // produce a proof of satisfiability
123 let mut prover_transcript = Transcript::new(b"snark_example");
124 let proof = SNARK::prove(
125 &inst,
126 &decomm,
127 assignment_vars,
128 &assignment_inputs,
129 &gens,
130 &mut prover_transcript,
131 );
132
133 // verify the proof of satisfiability
134 let mut verifier_transcript = Transcript::new(b"snark_example");
135 assert!(proof
136 .verify(&comm, &assignment_inputs, &mut verifier_transcript, &gens)
137 .is_ok());
138# }
139
140# fn produce_tiny_r1cs() -> (
141# usize,
142# usize,
143# usize,
144# usize,
145# Instance,
146# VarsAssignment,
147# InputsAssignment,
148# ) {
149 // We will use the following example, but one could construct any R1CS instance.
150 // Our R1CS instance is three constraints over five variables and two public inputs
151 // (Z0 + Z1) * I0 - Z2 = 0
152 // (Z0 + I1) * Z2 - Z3 = 0
153 // Z4 * 1 - 0 = 0
154
155 // parameters of the R1CS instance rounded to the nearest power of two
156 let num_cons = 4;
157 let num_vars = 8;
158 let num_inputs = 2;
159 let num_non_zero_entries = 8;
160
161 // We will encode the above constraints into three matrices, where
162 // the coefficients in the matrix are in the little-endian byte order
163 let mut A: Vec<(usize, usize, [u8; 32])> = Vec::new();
164 let mut B: Vec<(usize, usize, [u8; 32])> = Vec::new();
165 let mut C: Vec<(usize, usize, [u8; 32])> = Vec::new();
166
167 // The constraint system is defined over a finite field, which in our case is
168 // the scalar field of ristreeto255/curve25519 i.e., p = 2^{252}+27742317777372353535851937790883648493
169 // To construct these matrices, we will use `curve25519-dalek` but one can use any other method.
170
171 // a variable that holds a byte representation of 1
172 let one = Scalar::one().to_bytes();
173
174 // R1CS is a set of three sparse matrices A B C, where is a row for every
175 // constraint and a column for every entry in z = (vars, 1, inputs)
176 // An R1CS instance is satisfiable iff:
177 // Az \circ Bz = Cz, where z = (vars, 1, inputs)
178
179 // constraint 0 entries in (A,B,C)
180 // constraint 0 is (Z0 + Z1) * I0 - Z2 = 0.
181 // We set 1 in matrix A for columns that correspond to Z0 and Z1
182 // We set 1 in matrix B for column that corresponds to I0
183 // We set 1 in matrix C for column that corresponds to Z2
184 A.push((0, 0, one));
185 A.push((0, 1, one));
186 B.push((0, num_vars + 1, one));
187 C.push((0, 2, one));
188
189 // constraint 1 entries in (A,B,C)
190 A.push((1, 0, one));
191 A.push((1, num_vars + 2, one));
192 B.push((1, 2, one));
193 C.push((1, 3, one));
194
195 // constraint 3 entries in (A,B,C)
196 A.push((2, 4, one));
197 B.push((2, num_vars, one));
198
199 let inst = Instance::new(num_cons, num_vars, num_inputs, &A, &B, &C).unwrap();
200
201 // compute a satisfying assignment
202 let mut csprng: OsRng = OsRng;
203 let i0 = Scalar::random(&mut csprng);
204 let i1 = Scalar::random(&mut csprng);
205 let z0 = Scalar::random(&mut csprng);
206 let z1 = Scalar::random(&mut csprng);
207 let z2 = (z0 + z1) * i0; // constraint 0
208 let z3 = (z0 + i1) * z2; // constraint 1
209 let z4 = Scalar::zero(); //constraint 2
210
211 // create a VarsAssignment
212 let mut vars = vec![Scalar::zero().to_bytes(); num_vars];
213 vars[0] = z0.to_bytes();
214 vars[1] = z1.to_bytes();
215 vars[2] = z2.to_bytes();
216 vars[3] = z3.to_bytes();
217 vars[4] = z4.to_bytes();
218 let assignment_vars = VarsAssignment::new(&vars).unwrap();
219
220 // create an InputsAssignment
221 let mut inputs = vec![Scalar::zero().to_bytes(); num_inputs];
222 inputs[0] = i0.to_bytes();
223 inputs[1] = i1.to_bytes();
224 let assignment_inputs = InputsAssignment::new(&inputs).unwrap();
225
226 // check if the instance we created is satisfiable
227 let res = inst.is_sat(&assignment_vars, &assignment_inputs);
228 assert_eq!(res.unwrap(), true);
229
230 (
231 num_cons,
232 num_vars,
233 num_inputs,
234 num_non_zero_entries,
235 inst,
236 assignment_vars,
237 assignment_inputs,
238 )
239# }
240```
241
242## Building `libspartan`
243Install [`rustup`](https://rustup.rs/)
244
245Switch to nightly Rust using `rustup`:
246```text
247rustup default nightly
248```
249
250Clone the repository:
251```text
252git clone https://github.com/Microsoft/Spartan
253cd Spartan
254```
255
256To build docs for public APIs of `libspartan`:
257```text
258cargo doc
259```
260
261To run tests:
262```text
263RUSTFLAGS="-C target_cpu=native" cargo test
264```
265
266To build `libspartan`:
267```text
268RUSTFLAGS="-C target_cpu=native" cargo build --release
269```
270
271> NOTE: We enable SIMD instructions in `curve25519-dalek` by default, so if it fails to build remove the "simd_backend" feature argument in `Cargo.toml`.
272
273### Supported features
274* `profile`: enables fine-grained profiling information (see below for its use)
275
276## Performance
277
278### End-to-end benchmarks
279`libspartan` includes two benches: `benches/nizk.rs` and `benches/snark.rs`. If you report the performance of Spartan in a research paper, we recommend using these benches for higher accuracy instead of fine-grained profiling (listed below).
280
281To run end-to-end benchmarks:
282```text
283RUSTFLAGS="-C target_cpu=native" cargo bench
284```
285
286### Fine-grained profiling
287Build `libspartan` with `profile` feature enabled. It creates two profilers: `./target/release/snark` and `./target/release/nizk`.
288
289These profilers report performance as depicted below (for varying R1CS instance sizes). The reported
290performance is from running the profilers on a Microsoft Surface Laptop 3 on a single CPU core of Intel Core i7-1065G7 running Ubuntu 20.04 (atop WSL2 on Windows 10).
291See Section 9 in our [paper](https://eprint.iacr.org/2019/550) to see how this compares with other zkSNARKs in the literature.
292
293```text
294$ ./target/release/snark
295Profiler:: SNARK
296 * number_of_constraints 1048576
297 * number_of_variables 1048576
298 * number_of_inputs 10
299 * number_non-zero_entries_A 1048576
300 * number_non-zero_entries_B 1048576
301 * number_non-zero_entries_C 1048576
302 * SNARK::encode
303 * SNARK::encode 14.2644201s
304 * SNARK::prove
305 * R1CSProof::prove
306 * polycommit
307 * polycommit 2.7175848s
308 * prove_sc_phase_one
309 * prove_sc_phase_one 683.7481ms
310 * prove_sc_phase_two
311 * prove_sc_phase_two 846.1056ms
312 * polyeval
313 * polyeval 193.4216ms
314 * R1CSProof::prove 4.4416193s
315 * len_r1cs_sat_proof 47024
316 * eval_sparse_polys
317 * eval_sparse_polys 377.357ms
318 * R1CSEvalProof::prove
319 * commit_nondet_witness
320 * commit_nondet_witness 14.4507331s
321 * build_layered_network
322 * build_layered_network 3.4360521s
323 * evalproof_layered_network
324 * len_product_layer_proof 64712
325 * evalproof_layered_network 15.5708066s
326 * R1CSEvalProof::prove 34.2930559s
327 * len_r1cs_eval_proof 133720
328 * SNARK::prove 39.1297568s
329 * SNARK::proof_compressed_len 141768
330 * SNARK::verify
331 * verify_sat_proof
332 * verify_sat_proof 20.0828ms
333 * verify_eval_proof
334 * verify_polyeval_proof
335 * verify_prod_proof
336 * verify_prod_proof 1.1847ms
337 * verify_hash_proof
338 * verify_hash_proof 81.06ms
339 * verify_polyeval_proof 82.3583ms
340 * verify_eval_proof 82.8937ms
341 * SNARK::verify 103.0536ms
342```
343
344```text
345$ ./target/release/nizk
346Profiler:: NIZK
347 * number_of_constraints 1048576
348 * number_of_variables 1048576
349 * number_of_inputs 10
350 * number_non-zero_entries_A 1048576
351 * number_non-zero_entries_B 1048576
352 * number_non-zero_entries_C 1048576
353 * NIZK::prove
354 * R1CSProof::prove
355 * polycommit
356 * polycommit 2.7220635s
357 * prove_sc_phase_one
358 * prove_sc_phase_one 722.5487ms
359 * prove_sc_phase_two
360 * prove_sc_phase_two 862.6796ms
361 * polyeval
362 * polyeval 190.2233ms
363 * R1CSProof::prove 4.4982305s
364 * len_r1cs_sat_proof 47024
365 * NIZK::prove 4.5139888s
366 * NIZK::proof_compressed_len 48134
367 * NIZK::verify
368 * eval_sparse_polys
369 * eval_sparse_polys 395.0847ms
370 * verify_sat_proof
371 * verify_sat_proof 19.286ms
372 * NIZK::verify 414.5102ms
373```
374
375## LICENSE
376
377See [LICENSE](./LICENSE)
378
379## Contributing
380
381See [CONTRIBUTING](./CONTRIBUTING.md)