USENIX Security '22 - Experimenting with Collaborative zk-SNARKs: Zero-Knowledge Proofs for

Introduction

This tutorial explores the concepts presented in the USENIX Security '22 talk on collaborative zk-SNARKs, focusing on how zero-knowledge proofs can be implemented among multiple parties who do not trust each other. The goal is to provide an actionable guide for understanding the principles of zk-SNARKs and their application in distributed secret sharing, emphasizing their efficiency and optimization.

Step 1: Understand zk-SNARK Fundamentals

• Definition: zk-SNARK stands for Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge. It allows one party (the prover) to prove possession of certain information without revealing that information to another party (the verifier).
• Key Features:
  • Succinctness: The proof size is small and can be verified quickly.
  • Non-interactivity: The proof can be generated and verified without back-and-forth communication.
  • Zero-knowledge: The verifier learns nothing beyond the validity of the statement.

Step 2: Explore Collaborative zk-SNARKs

• Need for Collaboration: In many scenarios, secrets are distributed among multiple parties. Traditional zk-SNARKs are not designed for this, necessitating the development of collaborative zk-SNARKs.
• Implementation:
  • Use secure protocols among N provers.
  • Jointly produce a single proof over distributed witnesses.

Step 3: Optimize Proof Generation Algorithm

• Utilize Algebraic Techniques: Leverage multiparty computation (MPC) techniques to enhance the efficiency of proof generation in pairing-based zk-SNARKs.
• Challenge of Optimization: Some zk-SNARKs may be more complex to optimize, leading to the concept of "MPC-friendliness" as a criterion for evaluating zk-SNARKs.

Step 4: Evaluate Collaborative Proofs

• Implementation of Collaborative Proofs: Conduct experiments to implement three different collaborative zk-SNARK proofs.
• Performance Metrics:
  • Measure the concrete cost of proof generation.
  • Analyze runtime efficiency against malicious parties.

Step 5: Analyze Security and Performance Trade-offs

• Malicious Minority Security: Determine that security against a malicious minority of provers can be achieved with performance comparable to a single prover.
• Malicious Majority Security: Understand that ensuring security against N-1 malicious provers may result in a 2x slowdown, which is efficient compared to typical multiparty computation performance.

Conclusion

Collaborative zk-SNARKs present a promising approach for securely sharing secrets among multiple untrusting parties, maintaining efficiency comparable to single-prover systems. By understanding the fundamentals, exploring collaborative implementations, and optimizing proof generation, you can effectively apply these concepts in real-world applications. For further exploration, consider reviewing the full USENIX Security '22 program and other resources on zk-SNARKs and multiparty computation techniques.