Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Spartan: High-speed zkSNARKs without trusted setup

License

NotificationsYou must be signed in to change notification settings

microsoft/Spartan

Rust

Spartan 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 provideslibspartan, 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 ourpaper published atCRYPTO 2020. The security of the Spartan variant implemented in this library is based on the discrete logarithm problem in the random oracle model.

A 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 thispaper for an overview and thispaper for details.

Note that this library hasnot received a security review or audit.

Highlights

We now highlight Spartan's distinctive features.

  • No "toxic" waste: Spartan is atransparent 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.

  • 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.

  • Sub-linear verification costs: Spartan is the first transparent proof system with sub-linear verification costs for arbitrary NP statements (e.g., R1CS).

  • Standardized security: Spartan's security relies on the hardness of computing discrete logarithms (a standard cryptographic assumption) in the random oracle model.libspartan usesristretto255, a prime-order group abstraction atopcurve25519 (a high-speed elliptic curve). We usecurve25519-dalek for arithmetic overristretto255.

  • State-of-the-art performance: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.

Implementation details

libspartan usesmerlin to automate the Fiat-Shamir transform. We also introduce a new type calledRandomTape that extends aTranscript inmerlin to allow the prover's internal methods to produce private randomness using its private transcript without having to createOsRng objects throughout the code. An object of typeRandomTape is initialized with a new random seed fromOsRng for each proof produced by the library.

Examples

To importlibspartan into your Rust project, add the following dependency toCargo.toml:

spartan = "0.8.0"

The following example shows how to uselibspartan to create and verify a SNARK proof.Some of our public APIs' style is inspired by the underlying crates we use.

externcrate libspartan;externcrate merlin;use libspartan::{Instance,SNARKGens,SNARK};use merlin::Transcript;fnmain(){// specify the size of an R1CS instancelet num_vars =1024;let num_cons =1024;let num_inputs =10;let num_non_zero_entries =1024;// produce public parameterslet gens =SNARKGens::new(num_cons, num_vars, num_inputs, num_non_zero_entries);// ask the library to produce a synthentic R1CS instancelet(inst, vars, inputs) =Instance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);// create a commitment to the R1CS instancelet(comm, decomm) =SNARK::encode(&inst,&gens);// produce a proof of satisfiabilityletmut prover_transcript =Transcript::new(b"snark_example");let proof =SNARK::prove(&inst,&comm,&decomm, vars,&inputs,&gens,&mut prover_transcript);// verify the proof of satisfiabilityletmut verifier_transcript =Transcript::new(b"snark_example");assert!(proof.verify(&comm,&inputs,&mut verifier_transcript,&gens).is_ok());println!("proof verification successful!");}

Here is another example to use the NIZK variant of the Spartan proof system:

externcrate libspartan;externcrate merlin;use libspartan::{Instance,NIZKGens,NIZK};use merlin::Transcript;fnmain(){// specify the size of an R1CS instancelet num_vars =1024;let num_cons =1024;let num_inputs =10;// produce public parameterslet gens =NIZKGens::new(num_cons, num_vars, num_inputs);// ask the library to produce a synthentic R1CS instancelet(inst, vars, inputs) =Instance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);// produce a proof of satisfiabilityletmut prover_transcript =Transcript::new(b"nizk_example");let proof =NIZK::prove(&inst, vars,&inputs,&gens,&mut prover_transcript);// verify the proof of satisfiabilityletmut verifier_transcript =Transcript::new(b"nizk_example");assert!(proof.verify(&inst,&inputs,&mut verifier_transcript,&gens).is_ok());println!("proof verification successful!");}

Finally, we provide an example that specifies a custom R1CS instance instead of using a synthetic instance

#![allow(non_snake_case)]externcrate curve25519_dalek;externcrate libspartan;externcrate merlin;use curve25519_dalek::scalar::Scalar;use libspartan::{InputsAssignment,Instance,SNARKGens,VarsAssignment,SNARK};use merlin::Transcript;use rand::rngs::OsRng;fnmain(){// produce a tiny instancelet(    num_cons,    num_vars,    num_inputs,    num_non_zero_entries,    inst,    assignment_vars,    assignment_inputs,) =produce_tiny_r1cs();// produce public parameterslet gens =SNARKGens::new(num_cons, num_vars, num_inputs, num_non_zero_entries);// create a commitment to the R1CS instancelet(comm, decomm) =SNARK::encode(&inst,&gens);// produce a proof of satisfiabilityletmut prover_transcript =Transcript::new(b"snark_example");let proof =SNARK::prove(&inst,&comm,&decomm,    assignment_vars,&assignment_inputs,&gens,&mut prover_transcript,);// verify the proof of satisfiabilityletmut verifier_transcript =Transcript::new(b"snark_example");assert!(proof.verify(&comm,&assignment_inputs,&mut verifier_transcript,&gens).is_ok());println!("proof verification successful!");}fnproduce_tiny_r1cs() ->(usize,usize,usize,usize,Instance,VarsAssignment,InputsAssignment,){// We will use the following example, but one could construct any R1CS instance.// Our R1CS instance is three constraints over five variables and two public inputs// (Z0 + Z1) * I0 - Z2 = 0// (Z0 + I1) * Z2 - Z3 = 0// Z4 * 1 - 0 = 0// parameters of the R1CS instance rounded to the nearest power of twolet num_cons =4;let num_vars =5;let num_inputs =2;let num_non_zero_entries =5;// We will encode the above constraints into three matrices, where// the coefficients in the matrix are in the little-endian byte orderletmutA:Vec<(usize,usize,[u8;32])> =Vec::new();letmutB:Vec<(usize,usize,[u8;32])> =Vec::new();letmutC:Vec<(usize,usize,[u8;32])> =Vec::new();// The constraint system is defined over a finite field, which in our case is// the scalar field of ristreeto255/curve25519 i.e., p =  2^{252}+27742317777372353535851937790883648493// To construct these matrices, we will use `curve25519-dalek` but one can use any other method.// a variable that holds a byte representation of 1let one =Scalar::ONE.to_bytes();// R1CS is a set of three sparse matrices A B C, where is a row for every// constraint and a column for every entry in z = (vars, 1, inputs)// An R1CS instance is satisfiable iff:// Az \circ Bz = Cz, where z = (vars, 1, inputs)// constraint 0 entries in (A,B,C)// constraint 0 is (Z0 + Z1) * I0 - Z2 = 0.// We set 1 in matrix A for columns that correspond to Z0 and Z1// We set 1 in matrix B for column that corresponds to I0// We set 1 in matrix C for column that corresponds to Z2A.push((0,0, one));A.push((0,1, one));B.push((0, num_vars +1, one));C.push((0,2, one));// constraint 1 entries in (A,B,C)A.push((1,0, one));A.push((1, num_vars +2, one));B.push((1,2, one));C.push((1,3, one));// constraint 3 entries in (A,B,C)A.push((2,4, one));B.push((2, num_vars, one));let inst =Instance::new(num_cons, num_vars, num_inputs,&A,&B,&C).unwrap();// compute a satisfying assignmentletmut csprng:OsRng =OsRng;let i0 =Scalar::random(&mut csprng);let i1 =Scalar::random(&mut csprng);let z0 =Scalar::random(&mut csprng);let z1 =Scalar::random(&mut csprng);let z2 =(z0 + z1)* i0;// constraint 0let z3 =(z0 + i1)* z2;// constraint 1let z4 =Scalar::ZERO;//constraint 2// create a VarsAssignmentletmut vars =vec![Scalar::ZERO.to_bytes(); num_vars];  vars[0] = z0.to_bytes();  vars[1] = z1.to_bytes();  vars[2] = z2.to_bytes();  vars[3] = z3.to_bytes();  vars[4] = z4.to_bytes();let assignment_vars =VarsAssignment::new(&vars).unwrap();// create an InputsAssignmentletmut inputs =vec![Scalar::ZERO.to_bytes(); num_inputs];  inputs[0] = i0.to_bytes();  inputs[1] = i1.to_bytes();let assignment_inputs =InputsAssignment::new(&inputs).unwrap();// check if the instance we created is satisfiablelet res = inst.is_sat(&assignment_vars,&assignment_inputs);assert_eq!(res.unwrap(),true);(    num_cons,    num_vars,    num_inputs,    num_non_zero_entries,    inst,    assignment_vars,    assignment_inputs,)}

For more examples, seeexamples/ directory in this repo.

Buildinglibspartan

Installrustup

Switch to nightly Rust usingrustup:

rustup default nightly

Clone the repository:

git clone https://github.com/Microsoft/Spartancd Spartan

To build docs for public APIs oflibspartan:

cargo doc

To run tests:

RUSTFLAGS='-C target_cpu=native --cfg curve25519_dalek_backend="BACKEND"' cargo test

To buildlibspartan:

RUSTFLAGS='-C target_cpu=native --cfg curve25519_dalek_backend="BACKEND"' cargo build --release

NOTE: We enable SIMD instructions incurve25519-dalek by default, so if it fails to build remove the argument passed to curve25519_dalek in the above command.

Supported features

  • std: enables std features (enabled by default)
  • profile: enables fine-grained profiling information (see below for its use)

WASM Support

libspartan depends uponrand::OsRng (internally usesgetrandom crate), it has out of box support forwasm32-wasi.

For the targetwasm32-unknown-unknown disable default features for spartanand add direct dependency ongetrandom withwasm-bindgen feature enabled.

[dependencies]spartan = {version ="0.7",default-features =false }# since spartan uses getrandom(rand's OsRng), we need to enable 'wasm-bindgen'# feature to make it feed rand seed from js/nodejs env# https://docs.rs/getrandom/0.1.16/getrandom/index.html#support-for-webassembly-and-asmjsgetrandom = {version ="0.1",features = ["wasm-bindgen"] }

Performance

End-to-end benchmarks

libspartan includes two benches:benches/nizk.rs andbenches/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).

To run end-to-end benchmarks:

RUSTFLAGS='-C target_cpu=native --cfg curve25519_dalek_backend="BACKEND"' cargo bench

Fine-grained profiling

Buildlibspartan withprofile feature enabled. It creates two profilers:./target/release/snark and./target/release/nizk.

These profilers report performance as depicted below (for varying R1CS instance sizes). The reportedperformance 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).See Section 9 in ourpaper to see how this compares with other zkSNARKs in the literature.

$ ./target/release/snarkProfiler:: SNARK  * number_of_constraints 1048576  * number_of_variables 1048576  * number_of_inputs 10  * number_non-zero_entries_A 1048576  * number_non-zero_entries_B 1048576  * number_non-zero_entries_C 1048576  * SNARK::encode  * SNARK::encode 14.2644201s  * SNARK::prove    * R1CSProof::prove      * polycommit      * polycommit 2.7175848s      * prove_sc_phase_one      * prove_sc_phase_one 683.7481ms      * prove_sc_phase_two      * prove_sc_phase_two 846.1056ms      * polyeval      * polyeval 193.4216ms    * R1CSProof::prove 4.4416193s    * len_r1cs_sat_proof 47024    * eval_sparse_polys    * eval_sparse_polys 377.357ms    * R1CSEvalProof::prove      * commit_nondet_witness      * commit_nondet_witness 14.4507331s      * build_layered_network      * build_layered_network 3.4360521s      * evalproof_layered_network        * len_product_layer_proof 64712      * evalproof_layered_network 15.5708066s    * R1CSEvalProof::prove 34.2930559s    * len_r1cs_eval_proof 133720  * SNARK::prove 39.1297568s  * SNARK::proof_compressed_len 141768  * SNARK::verify    * verify_sat_proof    * verify_sat_proof 20.0828ms    * verify_eval_proof      * verify_polyeval_proof        * verify_prod_proof        * verify_prod_proof 1.1847ms        * verify_hash_proof        * verify_hash_proof 81.06ms      * verify_polyeval_proof 82.3583ms    * verify_eval_proof 82.8937ms  * SNARK::verify 103.0536ms
$ ./target/release/nizkProfiler:: NIZK  * number_of_constraints 1048576  * number_of_variables 1048576  * number_of_inputs 10  * number_non-zero_entries_A 1048576  * number_non-zero_entries_B 1048576  * number_non-zero_entries_C 1048576  * NIZK::prove    * R1CSProof::prove      * polycommit      * polycommit 2.7220635s      * prove_sc_phase_one      * prove_sc_phase_one 722.5487ms      * prove_sc_phase_two      * prove_sc_phase_two 862.6796ms      * polyeval      * polyeval 190.2233ms    * R1CSProof::prove 4.4982305s    * len_r1cs_sat_proof 47024  * NIZK::prove 4.5139888s  * NIZK::proof_compressed_len 48134  * NIZK::verify    * eval_sparse_polys    * eval_sparse_polys 395.0847ms    * verify_sat_proof    * verify_sat_proof 19.286ms  * NIZK::verify 414.5102ms

LICENSE

SeeLICENSE

Contributing

SeeCONTRIBUTING

[8]ページ先頭
©2009-2026 Movatter.jp