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 time-optimal 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
24offers the fastest prover with speedups of 36–152× depending on the baseline,
25produces proofs that are shorter by 1.2–416×, and incurs the lowest verification
26times with speedups of 3.6–1326×. When compared to the state-of-the-art zkSNARK
27with trusted setup, Spartan’s prover is 2× faster for arbitrary R1CS instances and
2816× faster for data-parallel workloads.
29
30### Status
31Development is ongoing (PRs are welcome!). For example, the library does not yet offer APIs to specify an NP statement, but we will in the future offer standardized APIs and also integrate with a compiler that produces R1CS instances from high level programs.
32
33### Implementation details
34`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.
35
36## Examples
37The following example shows how to use `libspartan` to create and verify a SNARK proof.
38Some of our public APIs' style is inspired by the underlying crates we use.
39
40```rust
41# extern crate libspartan;
42# extern crate merlin;
43# use libspartan::{Instance, SNARKGens, SNARK};
44# use merlin::Transcript;
45# fn main() {
46 // specify the size of an R1CS instance
47 let num_vars = 1024;
48 let num_cons = 1024;
49 let num_inputs = 10;
50 let num_non_zero_entries = 1024;
51
52 // produce public parameters
53 let gens = SNARKGens::new(num_cons, num_vars, num_inputs, num_non_zero_entries);
54
55 // ask the library to produce a synthentic R1CS instance
56 let (inst, vars, inputs) = Instance::new(num_cons, num_vars, num_inputs);
57
58 // create a commitment to the R1CS instance
59 let (comm, decomm) = SNARK::encode(&inst, &gens);
60
61 // produce a proof of satisfiability
62 let mut prover_transcript = Transcript::new(b"snark_example");
63 let proof = SNARK::prove(&inst, &decomm, vars, &inputs, &gens, &mut prover_transcript);
64
65 // verify the proof of satisfiability
66 let mut verifier_transcript = Transcript::new(b"snark_example");
67 assert!(proof
68 .verify(&comm, &inputs, &mut verifier_transcript, &gens)
69 .is_ok());
70# }
71```
72
73Here is another example to use the NIZK variant of the Spartan proof system:
74```rust
75# extern crate libspartan;
76# extern crate merlin;
77# use libspartan::{Instance, NIZKGens, NIZK};
78# use merlin::Transcript;
79# fn main() {
80 // specify the size of an R1CS instance
81 let num_vars = 1024;
82 let num_cons = 1024;
83 let num_inputs = 10;
84
85 // produce public parameters
86 let gens = NIZKGens::new(num_cons, num_vars);
87
88 // ask the library to produce a synthentic R1CS instance
89 let (inst, vars, inputs) = Instance::new(num_cons, num_vars, num_inputs);
90
91 // produce a proof of satisfiability
92 let mut prover_transcript = Transcript::new(b"nizk_example");
93 let proof = NIZK::prove(&inst, vars, &inputs, &gens, &mut prover_transcript);
94
95 // verify the proof of satisfiability
96 let mut verifier_transcript = Transcript::new(b"nizk_example");
97 assert!(proof
98 .verify(&inst, &inputs, &mut verifier_transcript, &gens)
99 .is_ok());
100# }
101```
102
103## Building `libspartan`
104Install [`rustup`](https://rustup.rs/)
105
106Switch to nightly Rust using `rustup`:
107```text
108rustup default nightly
109```
110
111Clone the repository:
112```text
113git clone https://github.com/Microsoft/Spartan
114cd Spartan
115```
116
117To build docs for public APIs of `libspartan`:
118```text
119cargo doc
120```
121
122To run tests:
123```text
124RUSTFLAGS="-C target_cpu=native" cargo test
125```
126
127To build `libspartan`:
128```text
129RUSTFLAGS="-C target_cpu=native" cargo build --release
130```
131
132> 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`.
133
134### Supported features
135* `profile`: enables fine-grained profiling information (see below for its use)
136
137## Performance
138
139### End-to-end benchmarks
140`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).
141
142To run end-to-end benchmarks:
143```text
144RUSTFLAGS="-C target_cpu=native" cargo bench
145```
146
147### Fine-grained profiling
148Build `libspartan` with `profile` feature enabled. It creates two profilers: `./target/release/snark` and `./target/release/nizk`.
149
150These profilers report performance as depicted below (for varying R1CS instance sizes). The reported
151performance 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).
152See Section 9 in our [paper](https://eprint.iacr.org/2019/550) to see how this compares with other zkSNARKs in the literature.
153
154```text
155$ ./target/release/snark
156Profiler:: SNARK
157 * number_of_constraints 1048576
158 * number_of_variables 1048576
159 * number_of_inputs 10
160 * number_non-zero_entries_A 1048576
161 * number_non-zero_entries_B 1048576
162 * number_non-zero_entries_C 1048576
163 * SNARK::encode
164 * SNARK::encode 14.2644201s
165 * SNARK::prove
166 * R1CSProof::prove
167 * polycommit
168 * polycommit 2.7175848s
169 * prove_sc_phase_one
170 * prove_sc_phase_one 683.7481ms
171 * prove_sc_phase_two
172 * prove_sc_phase_two 846.1056ms
173 * polyeval
174 * polyeval 193.4216ms
175 * R1CSProof::prove 4.4416193s
176 * len_r1cs_sat_proof 47024
177 * eval_sparse_polys
178 * eval_sparse_polys 377.357ms
179 * R1CSEvalProof::prove
180 * commit_nondet_witness
181 * commit_nondet_witness 14.4507331s
182 * build_layered_network
183 * build_layered_network 3.4360521s
184 * evalproof_layered_network
185 * len_product_layer_proof 64712
186 * evalproof_layered_network 15.5708066s
187 * R1CSEvalProof::prove 34.2930559s
188 * len_r1cs_eval_proof 133720
189 * SNARK::prove 39.1297568s
190 * SNARK::proof_compressed_len 141768
191 * SNARK::verify
192 * verify_sat_proof
193 * verify_sat_proof 20.0828ms
194 * verify_eval_proof
195 * verify_polyeval_proof
196 * verify_prod_proof
197 * verify_prod_proof 1.1847ms
198 * verify_hash_proof
199 * verify_hash_proof 81.06ms
200 * verify_polyeval_proof 82.3583ms
201 * verify_eval_proof 82.8937ms
202 * SNARK::verify 103.0536ms
203```
204
205```text
206$ ./target/release/nizk
207Profiler:: NIZK
208 * number_of_constraints 1048576
209 * number_of_variables 1048576
210 * number_of_inputs 10
211 * number_non-zero_entries_A 1048576
212 * number_non-zero_entries_B 1048576
213 * number_non-zero_entries_C 1048576
214 * NIZK::prove
215 * R1CSProof::prove
216 * polycommit
217 * polycommit 2.7220635s
218 * prove_sc_phase_one
219 * prove_sc_phase_one 722.5487ms
220 * prove_sc_phase_two
221 * prove_sc_phase_two 862.6796ms
222 * polyeval
223 * polyeval 190.2233ms
224 * R1CSProof::prove 4.4982305s
225 * len_r1cs_sat_proof 47024
226 * NIZK::prove 4.5139888s
227 * NIZK::proof_compressed_len 48134
228 * NIZK::verify
229 * eval_sparse_polys
230 * eval_sparse_polys 395.0847ms
231 * verify_sat_proof
232 * verify_sat_proof 19.286ms
233 * NIZK::verify 414.5102ms
234```
235
236## LICENSE
237
238See [LICENSE](./LICENSE)
239
240## Contributing
241
242See [CONTRIBUTING](./CONTRIBUTING.md)