A comprehensive comparison: What are zk-SNARKs and zk-STARKs?

Source: ChainDeng Community

What are zk-SNARKs and zk-STARKs? They are both zero-knowledge proofs, but what are their characteristics and how do they compare to each other?

Zero-knowledge proofs (ZKPs) are cryptographic protocols that allow 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. ZKP is a revolutionary technology for the blockchain ecosystem, enabling blockchain scalability through second-layer solutions and building privacy-preserving applications. The two most prominent types of ZKPs are zk-SNARKs and zk-STARKs, each with different characteristics and use cases.

In this article, we will discuss zk-SNARKs and zk-STARKs, their key characteristics, and a comparison between them.

Prerequisites

Understand ZKPs: You need to know what circuits, constraints, witnesses, verifiers, and provers are.

What are zk-SNARKs (Succinct Non-Interactive Arguments of Knowledge)

Zk-SNARKs are a broad class of ZKP systems that are non-interactive, meaning there is no back-and-forth communication between the prover and the verifier after the initial proof is generated. They are known for being efficient, offering small proof sizes and fast verification times, which remain constant regardless of complexity.

Key Features of zk-SNARKs

• Trusted Setup: SNARKs require a trusted setup phase where a set of initial parameters, often called a Structured Reference String (SRS), are generated. This setup phase uses a secret that, if revealed, would undermine the security of all subsequent proofs created using the setup. This setup data is often referred to as "toxic waste". Trusted setups are often seen as a drawback because they introduce potential trust issues: users must trust that the setup was performed correctly and that the secret was destroyed afterwards.

• Elliptic Curve Cryptography (ECC): Many SNARK constructions rely on elliptic curve cryptography, which depends on the difficulty of the discrete logarithm problem (DLP). While this provides strong security for classical computers, it makes SNARKs potentially vulnerable to attacks by future quantum computers, which can solve DLP efficiently.

Popular zk-SNARK Protocols

• Groth16: Groth16 is one of the most widely used SNARK protocols. It requires a trusted setup of a specific circuit and is very efficient, generating very small proofs and fast verification times. Due to its compact proof size, it is often used in blockchain projects such as Zcash.

• PLONK (Permutation Argument for Universal Non-Interactive Knowledge Arguments Based on Lagrangian Basis): PLONK is a more flexible SNARK protocol that uses a generic and updatable SRS, which means it can be used for any circuit and can be modified to support larger circuits. Unlike Groth16, the setup of PLONK is not specific to any particular circuit and can be reused for multiple circuits. This reduces the need to repeat the trusted setup and makes it easier to add new programs or circuits without re-doing the entire setup.

Properties of zk-SNARKs

• Proof Size: Small, which makes SNARKs suitable for applications with limited bandwidth and storage.

• Post-Quantum Security: Limited, due to reliance on ECC. SNARKs are not quantum resistant, as sufficiently powerful quantum computers could potentially solve DLP.

• Trusted Setup: This is required (in most SNARKs). The setup phase introduces a trust assumption that can pose potential security risks if not managed properly.

• Scalability: Very efficient for applications that require compact proofs and fast verification, although the need for a trusted setup can be a limitation in highly dynamic environments.

What are zk-STARKs (Scalable Transparent Arguments of Knowledge)

Zk-STARKs are another class of ZKPs that aim to address the shortcomings of zk-SNARKs. They are designed to be scalable and “transparent”, meaning they do not require a trusted setup phase. Instead, zk-STARKs use hash functions and publicly known randomness to construct proofs, which enhances their security and scalability.

Key Features of zk-STARKs

• Transparent Setup: STARKs do not rely on secret parameters. Instead, their proofs are generated using public randomness, which means they have no "toxic waste" that could corrupt the system and do not require a trusted setup.

• Hash-based Security: STARKs rely on hash functions, such as SHA-256, rather than elliptic curve cryptography. This makes them resistant to quantum attacks, as hash functions are believed to be secure against quantum computers under current cryptographic assumptions.

Features of STARKs

• Proof Size: STARK proofs can be several times larger than SNARK proofs, which increases verification time and is a drawback in environments with limited bandwidth or storage. This is due to their transparency, use of polynomial commitments, and approach to achieving scalability.

• Post-Quantum Security: Strong. Since STARKs use hash functions instead of elliptic curve cryptography, they are not vulnerable to quantum attacks under current cryptographic assumptions.

• Trusted Setup: Not required. STARKs use a transparent setup, which removes the need for trust during the setup phase, enhancing security.

• Scalability: Highly scalable, especially for large computations, where they show significant performance advantages as complexity increases. Since no trusted setup is required, they are more flexible as the setup does not need to be redone for each new application or use case.

Comparison of zk-SNARKs and zk-STARKs

Summary

Zk-SNARKs are zero-knowledge proof systems. They offer efficient proof size and fast verification time, but require a trusted setup and use elliptic curve cryptography, making them vulnerable to quantum attacks.

Zk-STARKs do not require a trusted setup. Instead, they rely on hash functions for security (making them quantum-resistant) and are more scalable for large computations. However, their proof size is large and they are slower to verify for smaller computations.

These two major ZKPs are critical to building ZK protocols in the blockchain ecosystem, enabling blockchain scalability through second-layer solutions and building privacy-preserving applications.