testudo/README.md
README.mdRaw
1# Spartan: High-speed zkSNARKs without trusted setup
2
3
4[]((https://crates.io/crates/spartan))
5
6Spartan 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/). The security of the Spartan variant implemented in this library is based on the discrete logarithm problem in the random oracle model.
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 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.
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:** Spartan is the first transparent proof system with sub-linear verification costs for arbitrary NP statements (e.g., R1CS).
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 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.
25
26### Implementation details
27`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.
28
29## Examples
30To import `libspartan` into your Rust project, add the following dependency to `Cargo.toml`:
31```text
32spartan = "0.4.1"
33```
34
35The following example shows how to use `libspartan` to create and verify a SNARK proof.
36Some of our public APIs' style is inspired by the underlying crates we use.
37
38```rust
39# extern crate libspartan;
40# extern crate merlin;
41# use libspartan::{Instance, SNARKGens, SNARK};
42# use merlin::Transcript;
43# fn main() {
44 // specify the size of an R1CS instance
45 let num_vars = 1024;
46 let num_cons = 1024;
47 let num_inputs = 10;
48 let num_non_zero_entries = 1024;
49
50 // produce public parameters
51 let gens = SNARKGens::new(num_cons, num_vars, num_inputs, num_non_zero_entries);
52
53 // ask the library to produce a synthentic R1CS instance
54 let (inst, vars, inputs) = Instance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
55
56 // create a commitment to the R1CS instance
57 let (comm, decomm) = SNARK::encode(&inst, &gens);
58
59 // produce a proof of satisfiability
60 let mut prover_transcript = Transcript::new(b"snark_example");
61 let proof = SNARK::prove(&inst, &comm, &decomm, vars, &inputs, &gens, &mut prover_transcript);
62
63 // verify the proof of satisfiability
64 let mut verifier_transcript = Transcript::new(b"snark_example");
65 assert!(proof
66 .verify(&comm, &inputs, &mut verifier_transcript, &gens)
67 .is_ok());
68 println!("proof verification successful!");
69# }
70```
71
72Here is another example to use the NIZK variant of the Spartan proof system:
73```rust
74# extern crate libspartan;
75# extern crate merlin;
76# use libspartan::{Instance, NIZKGens, NIZK};
77# use merlin::Transcript;
78# fn main() {
79 // specify the size of an R1CS instance
80 let num_vars = 1024;
81 let num_cons = 1024;
82 let num_inputs = 10;
83
84 // produce public parameters
85 let gens = NIZKGens::new(num_cons, num_vars, num_inputs);
86
87 // ask the library to produce a synthentic R1CS instance
88 let (inst, vars, inputs) = Instance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
89
90 // produce a proof of satisfiability
91 let mut prover_transcript = Transcript::new(b"nizk_example");
92 let proof = NIZK::prove(&inst, vars, &inputs, &gens, &mut prover_transcript);
93
94 // verify the proof of satisfiability
95 let mut verifier_transcript = Transcript::new(b"nizk_example");
96 assert!(proof
97 .verify(&inst, &inputs, &mut verifier_transcript, &gens)
98 .is_ok());
99 println!("proof verification successful!");
100# }
101```
102
103Finally, we provide an example that specifies a custom R1CS instance instead of using a synthetic instance
104```rust
105#![allow(non_snake_case)]
106# extern crate curve25519_dalek;
107# extern crate libspartan;
108# extern crate merlin;
109# use curve25519_dalek::scalar::Scalar;
110# use libspartan::{InputsAssignment, Instance, SNARKGens, VarsAssignment, SNARK};
111# use merlin::Transcript;
112# use rand::rngs::OsRng;
113# fn main() {
114 // produce a tiny instance
115 let (
116 num_cons,
117 num_vars,
118 num_inputs,
119 num_non_zero_entries,
120 inst,
121 assignment_vars,
122 assignment_inputs,
123 ) = produce_tiny_r1cs();
124
125 // produce public parameters
126 let gens = SNARKGens::new(num_cons, num_vars, num_inputs, num_non_zero_entries);
127
128 // create a commitment to the R1CS instance
129 let (comm, decomm) = SNARK::encode(&inst, &gens);
130
131 // produce a proof of satisfiability
132 let mut prover_transcript = Transcript::new(b"snark_example");
133 let proof = SNARK::prove(
134 &inst,
135 &comm,
136 &decomm,
137 assignment_vars,
138 &assignment_inputs,
139 &gens,
140 &mut prover_transcript,
141 );
142
143 // verify the proof of satisfiability
144 let mut verifier_transcript = Transcript::new(b"snark_example");
145 assert!(proof
146 .verify(&comm, &assignment_inputs, &mut verifier_transcript, &gens)
147 .is_ok());
148 println!("proof verification successful!");
149# }
150
151# fn produce_tiny_r1cs() -> (
152# usize,
153# usize,
154# usize,
155# usize,
156# Instance,
157# VarsAssignment,
158# InputsAssignment,
159# ) {
160 // We will use the following example, but one could construct any R1CS instance.
161 // Our R1CS instance is three constraints over five variables and two public inputs
162 // (Z0 + Z1) * I0 - Z2 = 0
163 // (Z0 + I1) * Z2 - Z3 = 0
164 // Z4 * 1 - 0 = 0
165
166 // parameters of the R1CS instance rounded to the nearest power of two
167 let num_cons = 4;
168 let num_vars = 5;
169 let num_inputs = 2;
170 let num_non_zero_entries = 5;
171
172 // We will encode the above constraints into three matrices, where
173 // the coefficients in the matrix are in the little-endian byte order
174 let mut A: Vec<(usize, usize, [u8; 32])> = Vec::new();
175 let mut B: Vec<(usize, usize, [u8; 32])> = Vec::new();
176 let mut C: Vec<(usize, usize, [u8; 32])> = Vec::new();
177
178 // The constraint system is defined over a finite field, which in our case is
179 // the scalar field of ristreeto255/curve25519 i.e., p = 2^{252}+27742317777372353535851937790883648493
180 // To construct these matrices, we will use `curve25519-dalek` but one can use any other method.
181
182 // a variable that holds a byte representation of 1
183 let one = Scalar::one().to_bytes();
184
185 // R1CS is a set of three sparse matrices A B C, where is a row for every
186 // constraint and a column for every entry in z = (vars, 1, inputs)
187 // An R1CS instance is satisfiable iff:
188 // Az \circ Bz = Cz, where z = (vars, 1, inputs)
189
190 // constraint 0 entries in (A,B,C)
191 // constraint 0 is (Z0 + Z1) * I0 - Z2 = 0.
192 // We set 1 in matrix A for columns that correspond to Z0 and Z1
193 // We set 1 in matrix B for column that corresponds to I0
194 // We set 1 in matrix C for column that corresponds to Z2
195 A.push((0, 0, one));
196 A.push((0, 1, one));
197 B.push((0, num_vars + 1, one));
198 C.push((0, 2, one));
199
200 // constraint 1 entries in (A,B,C)
201 A.push((1, 0, one));
202 A.push((1, num_vars + 2, one));
203 B.push((1, 2, one));
204 C.push((1, 3, one));
205
206 // constraint 3 entries in (A,B,C)
207 A.push((2, 4, one));
208 B.push((2, num_vars, one));
209
210 let inst = Instance::new(num_cons, num_vars, num_inputs, &A, &B, &C).unwrap();
211
212 // compute a satisfying assignment
213 let mut csprng: OsRng = OsRng;
214 let i0 = Scalar::random(&mut csprng);
215 let i1 = Scalar::random(&mut csprng);
216 let z0 = Scalar::random(&mut csprng);
217 let z1 = Scalar::random(&mut csprng);
218 let z2 = (z0 + z1) * i0; // constraint 0
219 let z3 = (z0 + i1) * z2; // constraint 1
220 let z4 = Scalar::zero(); //constraint 2
221
222 // create a VarsAssignment
223 let mut vars = vec![Scalar::zero().to_bytes(); num_vars];
224 vars[0] = z0.to_bytes();
225 vars[1] = z1.to_bytes();
226 vars[2] = z2.to_bytes();
227 vars[3] = z3.to_bytes();
228 vars[4] = z4.to_bytes();
229 let assignment_vars = VarsAssignment::new(&vars).unwrap();
230
231 // create an InputsAssignment
232 let mut inputs = vec![Scalar::zero().to_bytes(); num_inputs];
233 inputs[0] = i0.to_bytes();
234 inputs[1] = i1.to_bytes();
235 let assignment_inputs = InputsAssignment::new(&inputs).unwrap();
236
237 // check if the instance we created is satisfiable
238 let res = inst.is_sat(&assignment_vars, &assignment_inputs);
239 assert_eq!(res.unwrap(), true);
240
241 (
242 num_cons,
243 num_vars,
244 num_inputs,
245 num_non_zero_entries,
246 inst,
247 assignment_vars,
248 assignment_inputs,
249 )
250# }
251```
252
253For more examples, see [`examples/`](examples) directory in this repo.
254
255## Building `libspartan`
256Install [`rustup`](https://rustup.rs/)
257
258Switch to nightly Rust using `rustup`:
259```text
260rustup default nightly
261```
262
263Clone the repository:
264```text
265git clone https://github.com/Microsoft/Spartan
266cd Spartan
267```
268
269To build docs for public APIs of `libspartan`:
270```text
271cargo doc
272```
273
274To run tests:
275```text
276RUSTFLAGS="-C target_cpu=native" cargo test
277```
278
279To build `libspartan`:
280```text
281RUSTFLAGS="-C target_cpu=native" cargo build --release
282```
283
284> 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`.
285
286### Supported features
287* `profile`: enables fine-grained profiling information (see below for its use)
288
289## Performance
290
291### End-to-end benchmarks
292`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).
293
294To run end-to-end benchmarks:
295```text
296RUSTFLAGS="-C target_cpu=native" cargo bench
297```
298
299### Fine-grained profiling
300Build `libspartan` with `profile` feature enabled. It creates two profilers: `./target/release/snark` and `./target/release/nizk`.
301
302These profilers report performance as depicted below (for varying R1CS instance sizes). The reported
303performance 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).
304See Section 9 in our [paper](https://eprint.iacr.org/2019/550) to see how this compares with other zkSNARKs in the literature.
305
306```text
307$ ./target/release/snark
308Profiler:: SNARK
309 * number_of_constraints 1048576
310 * number_of_variables 1048576
311 * number_of_inputs 10
312 * number_non-zero_entries_A 1048576
313 * number_non-zero_entries_B 1048576
314 * number_non-zero_entries_C 1048576
315 * SNARK::encode
316 * SNARK::encode 14.2644201s
317 * SNARK::prove
318 * R1CSProof::prove
319 * polycommit
320 * polycommit 2.7175848s
321 * prove_sc_phase_one
322 * prove_sc_phase_one 683.7481ms
323 * prove_sc_phase_two
324 * prove_sc_phase_two 846.1056ms
325 * polyeval
326 * polyeval 193.4216ms
327 * R1CSProof::prove 4.4416193s
328 * len_r1cs_sat_proof 47024
329 * eval_sparse_polys
330 * eval_sparse_polys 377.357ms
331 * R1CSEvalProof::prove
332 * commit_nondet_witness
333 * commit_nondet_witness 14.4507331s
334 * build_layered_network
335 * build_layered_network 3.4360521s
336 * evalproof_layered_network
337 * len_product_layer_proof 64712
338 * evalproof_layered_network 15.5708066s
339 * R1CSEvalProof::prove 34.2930559s
340 * len_r1cs_eval_proof 133720
341 * SNARK::prove 39.1297568s
342 * SNARK::proof_compressed_len 141768
343 * SNARK::verify
344 * verify_sat_proof
345 * verify_sat_proof 20.0828ms
346 * verify_eval_proof
347 * verify_polyeval_proof
348 * verify_prod_proof
349 * verify_prod_proof 1.1847ms
350 * verify_hash_proof
351 * verify_hash_proof 81.06ms
352 * verify_polyeval_proof 82.3583ms
353 * verify_eval_proof 82.8937ms
354 * SNARK::verify 103.0536ms
355```
356
357```text
358$ ./target/release/nizk
359Profiler:: NIZK
360 * number_of_constraints 1048576
361 * number_of_variables 1048576
362 * number_of_inputs 10
363 * number_non-zero_entries_A 1048576
364 * number_non-zero_entries_B 1048576
365 * number_non-zero_entries_C 1048576
366 * NIZK::prove
367 * R1CSProof::prove
368 * polycommit
369 * polycommit 2.7220635s
370 * prove_sc_phase_one
371 * prove_sc_phase_one 722.5487ms
372 * prove_sc_phase_two
373 * prove_sc_phase_two 862.6796ms
374 * polyeval
375 * polyeval 190.2233ms
376 * R1CSProof::prove 4.4982305s
377 * len_r1cs_sat_proof 47024
378 * NIZK::prove 4.5139888s
379 * NIZK::proof_compressed_len 48134
380 * NIZK::verify
381 * eval_sparse_polys
382 * eval_sparse_polys 395.0847ms
383 * verify_sat_proof
384 * verify_sat_proof 19.286ms
385 * NIZK::verify 414.5102ms
386```
387
388## LICENSE
389
390See [LICENSE](./LICENSE)
391
392## Contributing
393
394See [CONTRIBUTING](./CONTRIBUTING.md)