STARK vs SNARK

In the world of cryptography and blockchain technology, zero-knowledge proofs have emerged as a powerful tool for ensuring privacy and security. Among the various zero-knowledge proof systems, STARK and SNARK have gained significant attention due to their unique properties and potential applications. This article aims to provide a comprehensive comparison of these two technologies, delving into their differences, advantages, and disadvantages. We will also explore the underlying mathematical concepts and commitment schemes that make these technologies possible.

Understanding STARK and SNARK

STARK (Scalable Transparent ARguments of Knowledge) and SNARK (Succinct Non-interactive ARguments of Knowledge) are both cryptographic proof systems that enable a prover to convince a verifier that a certain statement is true without revealing any information about the statement itself. The primary difference between the two lies in their acronyms: STARK is scalable and transparent, while SNARK is succinct and non-interactive.

Scalable and Transparent in STARK

The word "scalable" refers to the fact that STARKs can handle large circuits and the ability of the proof system to handle large-scale computations efficiently. This is achieved through the use of Algebraic Intermediate Representations (AIR), which allow for efficient representation and verification of complex computations. Transparency, on the other hand, means that STARK does not require a trusted setup, which is a significant advantage in terms of security and trust and basically means that anyone can verify the proof without relying on a trusted party. This makes STARKs more transparent and secure.

R1CS and AIR: SNARK vs. STARK

Before we dive into the differences between STARK and SNARK, it is important to understand the arithmetisation process. Arithmetization, and it is the translation (often referred to as ‘reduction’) of the problem of verifying a computation to the problem of checking that a certain polynomial, which can be evaluated efficiently on the verifier’s side (this is the ‘succinctly’ part), is of low degree. Simply put, it's a process of changing a program, written in a high-level language, to a list of polynomials with constants, variables, and constraints.

The two main mathematical structures used in the arithmetisation process are R1CS and AIR. Rank-1 Constraint Systems (R1CS) and Algebraic Intermediate Representations (AIR) are two mathematical frameworks used to represent and verify computations in zero-knowledge proof systems. R1CS is a way of representing computations using linear equations and inequalities. It is a popular choice for implementing SNARKs as it has a simple structure and is efficient in handling circuits with a small number of variables. It allows for efficient representation of arbitrary computations using a set of quadratic equations.

AIR, on the other hand, stands for "Algebraic Intermediate Representation." It is a more expressive way of representing computations than R1CS, as it allows for more complex and efficient handling of large circuits. It is a more suitable choice for implementing STARKs, where the goal is to handle large circuits with thousands of variables and it enables the efficient representation of large-scale computations using polynomials. Advantages and Disadvantages of STARK and SNARK Now that we understand the difference between R1CS and AIR, let's move on to the differences between STARK and SNARK. STARK and SNARK each have their own set of advantages and disadvantages with respect to loops, building a virtual machine, and arbitrary computations.

STARKs are more scalable and transparent, but they require more computational resources and generate larger proofs. SNARKs are more efficient in terms of computation and storage, but they require a trusted setup and are less transparent.

In terms of handling loops, STARKs are more suitable as they can handle loops more efficiently, whereas SNARKs require all the loops to be explicitly unrolled, which increases the number of circuits significantly.

R1CS, as mentioned earlier, represents computations using linear equations and inequalities. It has a simple structure and is efficient in handling circuits with a small number of variables. As such, R1CS and R1CS-based SNARKs are particularly well-suited for applications that involve simpler computations and have a relatively small number of constraints. It can be used to build efficient virtual machines for specific tasks that do not require complex calculations or a large number of variables. On the other hand, AIR provides a more expressive and efficient representation of computations compared to R1CS. It is designed to capture the algebraic structure of computations, which enables more efficient execution of arbitrary computations. This makes AIR and AIR-based STARKs more suitable for building virtual machines that need to handle a wide range of arbitrary computations. The advantage of using AIR for building a general-purpose virtual machine lies in its ability to handle more complex calculations and larger circuits. It provides a higher degree of flexibility and expressive power, making it suitable for a broader range of computations.

Polynomial Commitment Schemes

Polynomial commitment schemes are cryptographic primitives used in the construction of zero-knowledge proof systems like STARK and SNARK. Some common polynomial commitment schemes include Kate-Zaverucha-Goldberg (KZG), Inner Product Argument (IPA), and Fast Reed-Solomon Interactive Oracle Proofs of Proximity (FRI).

KZG is more suitable for SNARKs as it requires a trusted setup. KZG relies on elliptic curve pairings, which allows for efficient and secure commitments to polynomials. Essentially it uses a bilinear map that lets us use linearity and compress a lot of information to just a few points on an elliptic curve. As such, it enables very small proof sizes of just a few hundred bytes and efficient verification.

Inner Product Argument (IPA) is a commitment scheme that relies on the inner product of two vectors on an elliptic curve to represent a polynomial. This scheme is more suited for STARK, as it does not require a trusted setup. The generated proof is larger than that of KZG, but still rather small of just a few kilobytes.

Fast Reed-Solomon Interactive Oracle Proofs of Proximity (FRI) is a commitment scheme specifically designed for STARK, which allows for efficient and secure commitments to polynomials using a combination of Reed-Solomon codes and interactive oracle proofs. The commitment only relies on hash functions with no need to rely on any other cryptography. Despite FRI having the largest proofs of dozens of kilobytes, it has the fastest verification time as both elliptic curve and elliptic curve pairings are expensive to compute, and there are a lot of existing hardware optimisations to support hash functions computations.

Conclusion

In conclusion, STARK and SNARK are two powerful zero-knowledge proof systems with distinct advantages and disadvantages. While STARK offers better scalability, transparency, and post-quantum security, SNARK provides smaller proof sizes and more mature technology. The choice between the two depends on the specific requirements and constraints of the application in question.

I hope you found this article informative and insightful. Please feel free to leave a comment with your thoughts or suggestions for improvement. Stay tuned for our next article, which will explore the languages used to write zero-knowledge applications and further delve into the fascinating world of cryptography.