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