Efficient zkSNARKs Without Trusted Setup: Spartan Overview

 
Spartan
Efficient and general-purpose zkSNARKs
without trusted setup
 
Srinath Setty
Microsoft Research
 
https://github.com/Microsoft/Spartan
What is a zkSNARK?
 
Ar
gument of 
K
nowledge
Prove the knowledge of a secret
witness w such that C(x,w) = 1
 
Z
ero-
k
nowledge
π
 hides w
 
N
on-interactive
 
S
uccinct
|
π
| is sub-linear in |C|
Verifier runs in time sub-linear in |C|
 
Applications in practice:
Proving the correct operation of
cloud services
Offload blockchain processing to
the cloud
Transaction privacy
Many approaches to build zkSNARKs
 
PCPs + Merkle trees 
[Kilian92, Micali94]
 
A breakthrough result: 
[GGPR13]
 
building on 
[IKO07, Groth10, Lipmaa12]
Supports arbitrary circuits
Near-optimal asymptotics with good constants
Prover: O
λ
(|C| log |C|)
Proof size: O
λ
(1)
Verifier: O
λ
(|x| + |y|)
 
Requires a per-circuit trusted setup where the trapdoor used must be kept secret
Recent focus: zkSNARKs without trusted setup
 
Several schemes: Ligero, Hyrax, STARK, Bulletproofs, Aurora
Some of these achieve better performance than GGPR-derived schemes
 
Prior works can support arbitrary circuits or a succinct verifier, not both
 
Spartan
(this work)
layered, parallel circuits
A sequence of repeated
sub-circuits
Challenges with achieving succinct verification
 
1.
Arbitrary circuits have no structure
2.
The verifier must know what statement is being proven!
 
(1) + (2)  Verification must be at least O(|C|)
 
The Spartan verifier preprocesses circuits—
without
 
secret trapdoors
The verifier retains a commitment to circuit—
computation commitment
Preprocessing incurs O(|C|) costs, but is amortized
The amortization is similar to that of 
[GGPR13]
Spartan: A family of zkSNARKs without trusted setup
Polynomial
commitments
The sum-check
protocol
Computation
commitments
Spartan unifies different strands of theory (Short PCPs)
Short PCPs
of [BFLS91]
With 
[Kilian92, Micali94]
:
 
Concretely inefficient
Requires uniform circuits
for sub-linear verification
 
Spartan unifies different strands of theory (MIPs)
MIPs
of [BTVW14]
 
With 
[BC12]
:
 
Concretely inefficient
Designated verifier
MIPs
of [BTVW14]
 
Concretely efficient
Publicly verifiable
 
With Spartan:
 
Spartan unifies different strands of theory (IPs)
Doubly-
efficient IPs
of GKR08
 
With 
[Zhang et al. 17, Wahby et al. 2018]
:
 
Low-depth circuits
Uniform circuits
Doubly-
efficient IPs
of GKR08
 
Arbitrary circuits (no depth
or structure limitations)
 
With Spartan:
 
Spartan improves zkSNARKs with trusted setup
 
Using polynomial commitments from Libra 
[Xie et al. CRYPTO19]
, Spartan
offers an alternative to Libra:
 
Like Libra, universal trusted setup instead of per-circuit setup in 
[GGPR13]
 
Libra is restricted to layered arithmetic circuits; Spartan offers R1CS
Libra is restricted to uniform circuits, Spartan supports arbitrary circuits
 
Rest of this talk
 
Overview of Spartan
 
Experimental results
Spartan’s base: The sum-check protocol
 
[LFKN90]
Rank-1 constraint satisfiability (R1CS)
Encoding R1CS instances as sum-check instances
Recap: What is missing with the sum-check protocol?
Computation commitment
This almost works, but …
Our solution: SPARK
SPARK
compiler
Spartan’s techniques in a nutshell
 
Rest of this talk
 
Overview of Spartan
 
Experimental results
 
Implementation
 
Implement Spartan
DL 
is secure under DLOG in the RO model
 
8,000 lines of Rust, with many optimizations (see the paper)
 
Open source: 
https://github.com/Microsoft/Spartan
Experimental evaluation
Metrics:
 (1) prover’s time, (2) verifier’s time, and (3) proof sizes
Testbed:
 A Microsoft Surface Laptop 3, with Intel i7 and 16 GB RAM
Baselines:
Groth16, the state-of-the-art zkSNARK with trusted setup based on 
[GGPR13]
Ligero
Hyrax
Aurora
Fractal (achieves sub-linear verification using computation commitments)
 
log(number of constraints)
 
Prover’s time (seconds)
 
SpartanSNARK is 36x faster than Fractal and 2x faster than Groth16
SpartanNIZK is 24—152x faster than Ligero, Hyrax, and Aurora
 
Prover’s costs (one CPU core)
 
log(number of constraints)
 
Proof sizes (KB)
 
Groth16 (not depicted) produces shortest proofs (128 bytes)
SpartanSNARK’s proofs are 23x smaller than Fractal
SpartanNIZK offers 1.2—416x smaller proofs than Ligero, Hyrax, and Aurora
 
Proof sizes
 
log(number of constraints)
 
Verifier’s time (ms)
 
Groth16 (not depicted) features the fastest verifier (~3ms)
SpartanSNARK is 3.6x faster than Fractal
SpartanNIZK offers 22—363x faster than Ligero, Hyrax, and Aurora
SpartanSNARK beats SpartanNIZK at roughly 2
17
 constraints
 
Verifier’s cost (one CPU core)
 
Summary
 
Spartan is a new family of zkSNARKs without trusted setup
First to achieve sub-linear verification costs for arbitrary circuits
Features schemes with a linear-time prover
 
Introduces new techniques:
Computation commitments to preprocess NP statements without trapdoors
SPARK compiler to transform polynomial commitments to handle sparse multilinear
polynomials efficiently
A compact encoding of R1CS instances as sum-check instances
 
Concrete implementation in Rust and evaluation up to 2
20 
constraints.
Among transparent schemes:
Fastest prover and verifier
Shortest proof sizes (except for Bulletproofs)
Slide Note
Embed
Share

Spartan is a family of zkSNARKs that offer efficient and general-purpose zero-knowledge proofs without the need for a trusted setup. These zkSNARKs allow for proving the correctness of cloud services, ensuring transaction privacy, and more, with applications in cloud computing and blockchain technology. Unlike previous approaches, Spartan achieves sub-linear verification times and supports arbitrary circuits without compromising succinctness.

  • zkSNARKs
  • Zero-Knowledge Proofs
  • Trusted Setup
  • Spartan

Uploaded on Oct 03, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Spartan Efficient and general-purpose zkSNARKs without trusted setup Srinath Setty Microsoft Research https://github.com/Microsoft/Spartan

  2. What is a zkSNARK? Argument of Knowledge Prove the knowledge of a secret witness w such that C(x,w) = 1 Prover Verifier Zero-knowledge hides w Applications in practice: Proving the correct operation of cloud services Offload blockchain processing to the cloud Transaction privacy Non-interactive Succinct | | is sub-linear in |C| Verifier runs in time sub-linear in |C|

  3. Many approaches to build zkSNARKs PCPs + Merkle trees [Kilian92, Micali94] A breakthrough result: [GGPR13] building on [IKO07, Groth10, Lipmaa12] Supports arbitrary circuits Near-optimal asymptotics with good constants Prover: O (|C| log |C|) Proof size: O (1) Verifier: O (|x| + |y|) Requires a per-circuit trusted setup where the trapdoor used must be kept secret

  4. Recent focus: zkSNARKs without trusted setup Several schemes: Ligero, Hyrax, STARK, Bulletproofs, Aurora Some of these achieve better performance than GGPR-derived schemes Prior works can support arbitrary circuits or a succinct verifier, not both Succinct verifier Arbitrary circuits Aurora Hyrax layered, parallel circuits Spartan (this work) Ligero A sequence of repeated sub-circuits STARK Bulletproofs

  5. Challenges with achieving succinct verification 1. Arbitrary circuits have no structure 2. The verifier must know what statement is being proven! (1) + (2) Verification must be at least O(|C|) The Spartan verifier preprocesses circuits withoutsecret trapdoors The verifier retains a commitment to circuit computation commitment Preprocessing incurs O(|C|) costs, but is amortized The amortization is similar to that of [GGPR13]

  6. Spartan: A family of zkSNARKs without trusted setup Supports arbitrary circuits, specifically R1CS A new recipe for constructing zkSNARKs The sum-check protocol Polynomial commitments Computation commitments Four new zkSNARKs (using different polynomial commitments) Verification and proof sizes: O(log2n) to O( ?) Prover: O(n) to O(n log n) A Rust implementation of a member of the family (~8,000 SLOC) Fastest prover. Fastest verifier; shortest proof sizes (except for Bulletproofs) for n 220 constraints

  7. Spartan unifies different strands of theory (Short PCPs) With [Kilian92, Micali94]: Concretely inefficient Requires uniform circuits for sub-linear verification Short PCPs of [BFLS91] Merkle trees zkSNARKs With Spartan: Short PCPs of [BFLS91] Polynomial commitments Concretely efficient Supports arbitrary circuits zkSNARKs Computation commitments

  8. Spartan unifies different strands of theory (MIPs) With [BC12]: Concretely inefficient Designated verifier FHE-based compiler MIPs zkSNARKs of [BTVW14] With Spartan: MIPs Polynomial commitments of [BTVW14] Concretely efficient Publicly verifiable zkSNARKs Computation commitments

  9. Spartan unifies different strands of theory (IPs) With [Zhang et al. 17, Wahby et al. 2018]: Doubly- efficient IPs of GKR08 Low-depth circuits Uniform circuits Polynomial commitments zkSNARKs With Spartan: Doubly- efficient IPs of GKR08 Polynomial commitments Arbitrary circuits (no depth or structure limitations) zkSNARKs Computation commitments

  10. Rest of this talk Overview of Spartan Experimental results

  11. Spartans base: The sum-check protocol[LFKN90] A proof system for proving statements of the form i.e., sum-check instances (G is a multivariate polynomial over a finite field): ? = ?1, ,?? {0,1}?(?1, ,??) The proof system does not require a trusted setup It can be made zero-knowledge and non-interactive with existing compilers What is missing? We need an efficient reduction from R1CS statements to sum-check instances The proof system is not succinct (both proof sizes and verification times) The verifier must evaluate G at a random point in its domain (?1, ,??)

  12. Rank-1 constraint satisfiability (R1CS) Given three public matrices A, B, C over a finite field ?, does there exist a secret witness z such that: ?? ?? = ?? ? ( is entry-wise product) An NP-complete problem that generalizes arithmetic circuit satisfiability Implicit in [GGPR13], but made explicit by subsequent works There exist many compiler toolchains from high-level programs (C, Java, Rust, etc.) of interest to R1CS since the early 2010s Ginger, Pinocchio, Pantry, Buffet, Geppetto, xJsnark, etc.

  13. Encoding R1CS instances as sum-check instances Given three public matrices A, B, C over a finite field ?, does there exist a secret witness z such that: ?? ?? = ?? ? View A, B, C, and z as functions (s = logm and m is matrix dimension) A, B, C: {0,1}s x {0,1}s ? and z: {0,1}s ? We prove: ?? ?? = ?? iff (except small soundness error): eq(x, ) = 1 if x = , 0 otherwise 0 = ? {0,1}??? ?, ?(?) ? ?,? ? ? ? 0,1? ? ?,? ?(?) ? 0,1? ? ?,? ?(?) ? ? = ? {0,1}? ?(x, ?) = A(x, ?) for ?,? {0,1}?

  14. Recap: What is missing with the sum-check protocol? We need a reduction from R1CS statements to sum-check instances 0 = ? {0,1}??? ?, ?(?) ? ?,? ? ? ? 0,1? ? ?,? ?(?) ? 0,1? ? ?,? ?(?) ? ? = ? {0,1}? (See the paper for how to apply the sum-check protocol on double sums.) The protocol is not succinct (both proof sizes and verification times). The verifier must evaluate four multilinear polynomials: ? ?? The first one depends on the prover s witness ? ??,??, ? ??,??, ? ??,?? The last three depend only on the statement

  15. Evaluating ? ?? succinctly (for the verifier) Idea: Employ an extractable polynomial commitment scheme (we assume background on polynomial commitments) Prover Verifier: Commit(pp, ?) (before the sum-check protocol) [Run the sum-check protocol] Prover Verifier: ? ??, (a proof of correct evaluation) Verifier: Verify using the commitment and use the supplied ? ?? to evaluate G There are many polynomial commitments without trusted setup (see the paper) | | and the cost to verify are succinct (i.e., sub-linear in |z|)

  16. Evaluating ? ??,??, ? ??,??,? ??,?? succinctly Computation commitment Idea: Employ a polynomial commitment scheme In a preprocessing phase, the verifier computes: ?????? ??, ? ,?????? ??, ? ,??????(??, ?) Prover Verifier: Commit(pp, ?) (before the sum-check protocol) [Run the sum-check protocol] Prover Verifier: ? ??,?? ? ??,??, ? ??,??, ? ??,?? , ??,??,?? Verifier: Verify proofs against commitments and evaluate G using the supplied evaluations

  17. This almost works, but ?, ?, ? are sparse polynomials. That is, A, B, C are sparse matrices In practice, the number of non-zero entries is n = O(m) But, the total number of entries is O(m2) 5 2 0 0 0 1 0 0 0 Existing commitment schemes incur O(m2) costs (for creating commitments and producing evaluation proofs) Prover is quadratic in the statement size (Theoretically efficient, but not in practice)

  18. Our solution: SPARK PolyCommit for multilinear polynomials PolyCommit for sparse multilinear polynomials SPARK compiler (1) Commitments: commit to dense representations 0 8 0 0 5 0 0 0 0 9 0 0 col val row 0 1 1 1 0 2 5 8 9 Each polynomial size = O(n), #non-zero entries (2) Polynomial evaluation (see the paper for details): An O(n)-sized uniform circuit (employs offline memory checking techniques) A tailored zkSNARK where the verifier incurs sub-linear costs

  19. Spartans techniques in a nutshell R1CS instance An argument of knowledge Existing compilers Sum-check instance Theorem 5.1 NIZKs Theorem 4.1 PolyCommit for multilinear polynomials PolyCommit for sparse multilinear polynomials SPARK compiler Computation commitments zkSNARKs for R1CS

  20. Rest of this talk Overview of Spartan Experimental results

  21. Implementation Implement SpartanDL is secure under DLOG in the RO model 8,000 lines of Rust, with many optimizations (see the paper) Open source: https://github.com/Microsoft/Spartan

  22. Experimental evaluation Metrics:(1) prover s time, (2) verifier s time, and (3) proof sizes Testbed: A Microsoft Surface Laptop 3, with Intel i7 and 16 GB RAM Baselines: Groth16, the state-of-the-art zkSNARK with trusted setup based on [GGPR13] Ligero Hyrax Aurora Fractal (achieves sub-linear verification using computation commitments) Incur linear-time costs for arbitrary circuits

  23. Provers costs (one CPU core) 10000 SpartanNIZK SpartanSNARK Groth16 Ligero Hyrax Aurora Fractal 1000 Prover s time (seconds) 100 10 1 0.1 15 16 17 18 19 20 log(number of constraints) SpartanSNARK is 36x faster than Fractal and 2x faster than Groth16 SpartanNIZK is 24 152x faster than Ligero, Hyrax, and Aurora

  24. Proof sizes 100000 SpartanNIZK SpartanSNARK Hyrax Ligero Aurora Fractal 10000 Proof sizes (KB) 1000 100 10 1 15 16 17 18 19 20 log(number of constraints) Groth16 (not depicted) produces shortest proofs (128 bytes) SpartanSNARK s proofs are 23x smaller than Fractal SpartanNIZK offers 1.2 416x smaller proofs than Ligero, Hyrax, and Aurora

  25. Verifiers cost (one CPU core) 1000000 SpartanNIZK SpartanSNARK Hyrax Fractal Ligero Aurora 100000 Verifier s time (ms) 10000 1000 100 10 1 15 16 17 18 19 20 log(number of constraints) Groth16 (not depicted) features the fastest verifier (~3ms) SpartanSNARK is 3.6x faster than Fractal SpartanNIZK offers 22 363x faster than Ligero, Hyrax, and Aurora SpartanSNARK beats SpartanNIZK at roughly 217 constraints

  26. Summary Spartan is a new family of zkSNARKs without trusted setup First to achieve sub-linear verification costs for arbitrary circuits Features schemes with a linear-time prover Introduces new techniques: Computation commitments to preprocess NP statements without trapdoors SPARK compiler to transform polynomial commitments to handle sparse multilinear polynomials efficiently A compact encoding of R1CS instances as sum-check instances Concrete implementation in Rust and evaluation up to 220 constraints. Among transparent schemes: Fastest prover and verifier Shortest proof sizes (except for Bulletproofs)

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#