SoK: Understanding zk-SNARKs: The Gap Between Research and Practice

SoK: Understanding zk-SNARKs: The Gap Between Research and Practice

Speakers: Junkai Liang

Conference: USENIX Security

YouTube: https://www.youtube.com/watch?v=CXRswZPRfMM

Overview

This talk, presented by Junkai Liang at USENIX Security, delves into a "Systematization of Knowledge" (SoK) regarding Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARKs). The core objective of this work is to bridge the significant chasm between the theoretical advancements in zk-SNARK research and their practical adoption and implementation in real-world applications. Despite the immense financial potential and widespread interest from companies in leveraging zk-SNARKs for privacy and scalability, the field is plagued by complexity, with over 40 distinct schemes detailed in top conferences, each difficult to grasp even for experts.

The speaker highlights a critical dilemma: the sheer volume of intricate mathematical formulations and complex papers—some exceeding 80 pages—makes it nearly impossible for developers, programmers, and even researchers to fully comprehend and correctly implement these systems. This complexity isn't merely an academic hurdle; it has tangible, negative impacts, manifesting in "hundreds of vulnerabilities" found in recent years within zk-SNARK components like compilers and proving systems. The article aims to demystify zk-SNARKs, offering a structured understanding for various stakeholders—researchers, developers, programmers, and users—and pinpointing the practical challenges that hinder their secure and efficient deployment.

Ultimately, the talk serves as a call to action, providing a framework (the "master recipe") for understanding zk-SNARK constructions and classifying existing schemes based on practical properties like transparency, post-quantum security, and scalability. By systematically analyzing the ecosystem of zk-SNARK libraries and identifying critical bottlenecks, particularly within compilers, the work not only sheds light on the current state of the art but also proposes concrete steps and open-source initiatives to foster greater accessibility, reduce vulnerabilities, and accelerate the secure adoption of this transformative technology.

Background

▶ Watch: The dilemma: complexity and vulnerabilities in zk-SNARKs (1:50)

The concept of a zero-knowledge proof allows one party (the prover) to convince another party (the verifier) that a statement is true, without revealing any information beyond the validity of the statement itself. The talk uses a simple card game analogy to illustrate this fundamental principle. zk-SNARKs enhance this concept by adding two crucial properties: succinctness (S), meaning the proof is small and verifiable quickly, and non-interactivity (NI), meaning the proof can be verified without further communication with the prover after it's generated. These properties make zk-SNARKs incredibly powerful for applications requiring privacy and scalability, such as cryptocurrencies, identity verification, and confidential computing.

The motivation behind this SoK stems from the rapidly increasing interest and investment in zk-SNARK technology, juxtaposed with the significant practical difficulties in its implementation. As mentioned, the field boasts over 40 distinct zk-SNARK schemes, each with its own intricate mathematical underpinnings. Understanding a single scheme, like Groth16, often requires sifting through dozens of pages of dense academic papers filled with complex formulas. This steep learning curve has led to a proliferation of vulnerabilities in real-world implementations, spanning various layers from circuit design to backend integration. Programmers, unfamiliar with the nuances of these cryptographic components, inadvertently introduce flaws into systems that are meant to provide ironclad security guarantees.

The paper aims to address this by considering four key participant groups:

1. Researchers: Who need to identify open research problems.
2. Developers: Who are responsible for implementing core toolkits.
3. Programmers: Who build applications using these toolkits.
4. Users: Who need assurance that their applications are indeed secure and private.

To achieve this, the work poses three central questions: How can a survey help researchers quickly identify problems? Can existing zk-SNARKs be classified based on practical properties to aid developers, programmers, and users? What exactly is the gap between research and practice, and how can it be mitigated? The foundation for answering these questions is the "master recipe" framework, which breaks down the construction of any zk-SNARK into four main components: the original program, the constraint system, the proving system, and optimizers. This structured approach provides a common language and understanding to navigate the complex landscape of zk-SNARKs.

Key Findings

▶ Watch: Master recipe framework for zk-SNARK construction (3:45)

The research yielded several significant findings, primarily centered on the classification of existing zk-SNARK schemes and the identification of a critical gap between theoretical research and practical deployment.

Firstly, the talk presents a novel classification of zk-SNARK schemes based on practical properties that are directly relevant to developers, programmers, and users. These properties include transparency (whether a trusted setup is required), post-quantum security (resistance to quantum computer attacks), and scalability (how performance scales with problem size). This classification reveals how specific underlying techniques in the proving system construction dictate these properties. For instance, QAP-based zk-SNARKs (often leveraging Pairing-based Cryptography) typically require a trusted setup and are not post-quantum secure due to their reliance on discrete logarithm problems, but offer small proof sizes and are applicable to general circuits. In contrast, PCP with PCS-based schemes offer a wider spectrum of properties, with their characteristics heavily dependent on the chosen Polynomial Commitment Scheme (PCS). This systematic categorization helps practitioners select appropriate schemes based on their specific application requirements.

Secondly, and perhaps most critically, the work pinpoints compilers as the primary bottleneck in the practical adoption and design of zk-SNARK applications. While much academic research focuses on advancing the underlying proving systems—making them faster, smaller, or more secure—the tools that convert high-level application logic into the mathematical forms required by these proving systems are severely lacking. The identified issues with existing compilers include:

• Time-consuming development: Writing circuits in compiler-supported languages is often arduous and takes significant effort.
• Bug undetectability: There are no obvious or standardized ways to determine if a generated circuit is secure or correctly implements the intended logic, leading to the "hundreds of vulnerabilities" previously mentioned.
• Lack of standardization: Circuits generated by different compilers are often incompatible, hindering interoperability between various zk-SNARK libraries.
• Efficiency issues: Compiler implementations themselves can significantly impact performance, adding overhead in tools like snarkjs.

This highlights a fundamental disconnect: researchers are pushing the boundaries of cryptographic theory, while practical implementation tools are struggling to keep up, creating a significant "gap between research and practice." The findings underscore that without robust, user-friendly, and secure compilers, the full potential of zk-SNARKs cannot be realized, leading to limited real-world adoption despite their theoretical promise.

Technical Deep Dive

▶ Watch: How constraint systems represent computations (4:15)

The core of understanding zk-SNARKs, as presented in this SoK, lies in its "master recipe" framework, which decomposes the construction into four sequential components: the Original Program, the Constraint System, the Proving System, and Optimizers.

The process begins with the Original Program, which is the high-level application logic written in a language supported by a compiler or library. This program defines the computation that needs to be proven in zero-knowledge. For example, it could be a function f(x) where one wants to prove knowledge of x such that f(x) = y without revealing x.

The next step is to convert this high-level program into a Constraint System. This is the mathematical representation of the program, a form that the proving system can understand and process. The talk exemplifies this transformation by showing how a function f can be represented using variables and a set of constraints, often in a matrix form. A common constraint system is Rank-1 Constraint System (R1CS), where computations are expressed as a series of equations of the form a * b = c, where a, b, and c are linear combinations of input and intermediate variables. These constraints are then often mapped to polynomials, for instance, using Quadratic Arithmetic Programs (QAPs), which represent the entire set of constraints as a relationship between a few polynomials. The satisfiability of the original program is equivalent to the satisfiability of the constraint system, which in turn is equivalent to a specific polynomial relationship.

The Proving System is where the cryptographic magic happens. It takes the constraint system (e.g., in QAP form) and generates a succinct zero-knowledge proof that the constraints are satisfied. The talk classifies proving systems into two main categories:

1. QAP-based zk-SNARKs (PCP with Pairing): These schemes, exemplified by Groth16, leverage Pairing-based Cryptography. The core idea is to use pairings (bilinear maps on elliptic curves) to check polynomial constraints at specific points.

• Properties: They typically require a trusted setup, where a set of secret parameters (known as the Common Reference String or CRS) must be generated, and the "toxic waste" (the secrets used to generate the CRS) must be securely destroyed. If these secrets are compromised, a malicious prover could generate fake proofs. They offer a quasi-linear prover (meaning the prover's time complexity is nearly linear with the circuit size, often due to operations like Fast Fourier Transform) and provide small proof sizes (constant number of group elements). However, they are not post-quantum secure because the underlying discrete logarithm problem on elliptic curves can be solved by quantum computers. Despite this, their efficiency and small proof size make them popular for general circuits.

1. PCP with PCS-based zk-SNARKs: This class is more flexible, with its properties heavily dependent on the chosen Polynomial Commitment Scheme (PCS). A PCS allows a prover to commit to a polynomial without revealing it, and later open the commitment at a specific point, proving the polynomial's value at that point. This is an instantiation of Polynomial Oracles (POPs), where the prover generates polynomial points and sends them to the verifier.

• How PCS works: The prover sends a commitment of a polynomial P(x) to the verifier. The verifier then sends a random point u to the prover. The prover computes P(u) and a proof π, sending both to the verifier. The verifier checks that π is a valid proof that P(u) is indeed the value committed to.
• Types of PCS:
• Pairing-based PCS: Similar to QAP-based SNARKs, these require a trusted setup, achieve constant proof size, and have constant verifier time. They typically require a linear prover. Examples include KZG commitments.
• Inner Product Argument (IPA) PCS: These offer a transparent setup (no trusted setup required, as the CRS can be publicly generated), sublinear proof size, and sublinear verifier time. They also often require a linear prover. An example is used in Bulletproofs and Halo2.
• Code Theory-based PCS: These are typically more computationally intensive to instantiate but can achieve both a transparent setup and post-quantum security. They represent polynomials as codewords of error-correcting codes.
• The flexibility of PCS-based schemes allows for various trade-offs in properties like setup requirements, proof size, and post-quantum resistance, making them a rich area of research. PlonK is a prominent example of a PCS-based scheme.

Finally, Optimizers are components that enhance the efficiency of the proving system. While not detailed extensively in the talk, they are crucial for making zk-SNARKs practical by reducing prover time, proof size, or verifier time.

The talk also surveys 11 popular open-source libraries, focusing on their compilers and documentation. Compilers are categorized into:

• Domain-Specific Languages (DSLs): These are new languages specifically designed for circuit description. They can be Hardware Description Languages (HDLs), which are very specific to circuit structure, or Programming Languages (PLs), which are more high-level. DSLs require programmers to learn a new language, with HDLs having limited data types but often more comprehensive documentation.
• Embedded DSLs (EDSsL): These are libraries implemented within existing general-purpose languages (e.g., Rust, Go). They allow leveraging existing language features and libraries, eliminating the need to learn a new language. However, they can still require specifying circuits in a waveform-like manner and may offer less compatibility between different language ecosystems (e.g., a circuit in Rust EDSL might not be directly convertible to a Go EDSL).

The evaluation of these compilers, through implementing three example programs using schemes like Groth16 (in snarkjs), PlonK (in chino), and Halo2 (in halo2tools), revealed the critical bottlenecks and issues that form the "gap between research and practice."

Demo / Proof of Concept

▶ Watch: PoP with PCS-based zk-SNARKs: variable properties (8:00)

While the talk did not feature a live, interactive demonstration of a specific exploit or a novel tool in the traditional "demo" sense, the speaker detailed a crucial practical evaluation that served as a proof of concept for the identified challenges. The research team implemented "three program examples" using various open-source zk-SNARK libraries and their respective compilers. This hands-on exercise involved writing circuits in different domain-specific languages (DSLs) and embedded DSLs (EDSsLs) supported by popular schemes like Groth16, PlonK, and Halo2.

This practical engagement with the existing toolchain directly informed the key finding that compilers are the primary bottleneck in zk-SNARK application design. The experience of writing these example circuits highlighted the significant time investment required, the difficulty in detecting bugs within the generated circuits, and the lack of standardization across different compiler outputs. For instance, the speaker noted the efficiency issues observed with compiler implementations, citing "overload in tools like snarkjs." This empirical approach, by attempting to use the tools as a programmer would, effectively demonstrated the real-world friction and limitations developers face when trying to leverage cutting-edge zk-SNARK research. The "demo" was, in essence, the act of attempting to build with current tools, which then exposed their deficiencies.

Defensive Implications

▶ Watch: Understanding Polynomial Commitment Schemes (PCS) and their types (10:00)

The findings of this SoK carry significant implications for defenders and anyone involved in building or securing systems that utilize zk-SNARKs. The most critical defensive takeaway is the direct correlation between the complexity and lack of standardization in zk-SNARK compilers and the "hundreds of vulnerabilities" discovered in recent years. This underscores a fundamental security risk: even if the underlying cryptographic proving system is theoretically sound, a flawed or poorly understood compiler can introduce critical vulnerabilities at the application or circuit definition layer.

Defenders must prioritize the following:

1. Robust Compiler Selection and Auditing: Given that compilers are identified as the primary bottleneck and a source of bugs, organizations must exercise extreme caution in selecting which zk-SNARK compilers and libraries to use. Thorough security audits of these compilers themselves are paramount, not just of the cryptographic primitives. Developers should look for compilers with comprehensive documentation, active community support, and a strong track record of security reviews.
2. Standardization and Interoperability: The lack of standardization leads to incompatible circuits and hinders the development of robust security tools that can operate across different zk-SNARK ecosystems. Defenders should advocate for and contribute to efforts that promote standardized circuit description languages, intermediate representations, and proof formats. This would enable better tooling for formal verification, static analysis, and bug detection.
3. Enhanced Documentation and Developer Education: The "unfamiliarity" of programmers with zk-SNARK components is a direct cause of vulnerabilities. Defensive strategies must include investing in clear, accessible, and comprehensive documentation for zk-SNARK libraries and compilers. Educational initiatives for developers, focusing on secure circuit design patterns, common pitfalls, and best practices for using zk-SNARK tools, are essential to mitigate risks.
4. Circuit Security Analysis Tools: The current difficulty in "judging if a circuit is secure" necessitates the development of specialized security analysis tools for zk-SNARK circuits. These could include static analyzers to identify common logical errors, formal verification tools to prove circuit correctness, and fuzzing tools to uncover unexpected behavior.
5. Addressing Efficiency Issues: While not directly a security vulnerability, compiler efficiency issues can lead to workarounds or compromises in deployment that might indirectly introduce security risks. Optimizing compiler performance and ensuring they do not add undue overhead is crucial for practical and secure adoption.
6. Transparency and Trusted Setup: For schemes requiring a trusted setup, defenders must implement rigorous protocols for generating and destroying the "toxic waste." Auditing these setup ceremonies and understanding their security implications is vital. For schemes with transparent setups, the security properties should be carefully reviewed to ensure they meet the application's requirements, especially concerning post-quantum security.

The call to the open-source community to address these critical compiler issues is a defensive imperative. By improving the quality, usability, and security of zk-SNARK development tools, the overall security posture of applications leveraging this powerful technology can be significantly enhanced.

Key Takeaways

• Complexity is a Major Barrier: The vast number of complex zk-SNARK schemes and their dense academic documentation significantly hinder practical adoption and lead to "hundreds of vulnerabilities" in real-world implementations.
• Compilers are the Bottleneck: While research focuses on proving systems, the tools (compilers) that convert high-level programs into zk-SNARK circuits are the primary source of practical challenges, suffering from being time-consuming, bug-undetectable, and lacking standardization.
• Classification Aids Selection: zk-SNARK schemes can be effectively classified based on practical properties like transparency, post-quantum security, and scalability, helping developers choose the right scheme for their specific needs.
• Master Recipe for Understanding: The "master recipe" framework (Original Program, Constraint System, Proving System, Optimizers) provides a structured approach to understand the construction and identify research problems in zk-SNARKs.
• PCS-based Schemes Offer Flexibility: Polynomial Commitment Schemes (PCS), used in schemes like PlonK and Halo2, offer diverse properties depending on their underlying cryptographic construction, allowing for trade-offs between trusted setup, proof size, verifier time, and post-quantum security.
• Call for Open-Source Collaboration: There's an urgent need for the open-source community to collaborate on improving zk-SNARK compilers, documentation, and interoperability to bridge the gap between research and practical, secure applications.

About the Speaker(s)

Junkai Liang is a researcher whose work focuses on the challenging intersection of theoretical cryptography, specifically Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARKs), and their practical application. His presentation at USENIX Security, an SoK (Systematization of Knowledge), highlights his commitment to making complex cryptographic concepts more accessible and understandable for a broader audience, including researchers, developers, programmers, and users. Liang's work directly addresses the real-world problems faced by those attempting to implement zk-SNARKs, identifying critical bottlenecks in tooling and proposing solutions to enhance security and foster wider adoption of this transformative technology. His contributions aim to bridge the significant gap between academic advancements and the practical realities of building secure, privacy-preserving systems.