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