Demystifying SNARKs: Building Blocks and Practical Applications
Structure:
Introduction:
Zero-Knowledge Succinct Non-Interactive ARguments of Knowledge (ZK-SNARKs) have gained significant traction in recent years for their applications in privacy-preserving technologies and blockchain systems. In this article, we explore the fundamental building blocks of a SNARK, including commitment schemes, functional commitment schemes, polynomial commitments, and Interactive Oracle Proofs (IOPs). We discuss how these components come together to create a general framework for building efficient SNARKs and delve into real-world examples and applications.
Recall: SNARK (Non-interactive ARgument of Knowledge)
In this segment, we discuss a general framework for building an efficient SNARK. A SNARK consists of three algorithms, S (setup), P (proving), and V (verifier). The aim of a SNARK is to be succinct, with proof sizes ideally logarithmic or constant in the size of the circuit, and verifier time at most logarithmic in the size of the circuit.
General paradigm: two steps
This is typically done in two steps: combining a functional commitment scheme with a compatible interactive Oracle Proof (IOP). This combination allows us to prove any statement for any circuit C and statement X, where the prover knows a witness w such that C(x,w) is equal to zero.
Review: commitments
A commitment scheme consists of two algorithms, commit and verify. Commit takes a message and some randomness as input, producing a commitment string, while the verify algorithm outputs either accept or reject. Commitment schemes must satisfy binding and hiding properties.
A standard construction
A standard construction for commitment schemes uses a hash function, hashing the message and randomness to create the commitment string. A suitable hash function ensures that the commitment scheme is hiding and binding.
Committing to a function
In a functional commitment scheme, the committer (prover) commits to a function and sends the commitment string to the verifier. The verifier can then send a domain element, and the prover will send back a range element with a proof. This evaluation protocol is a SNARK for the relation stating that F(x) is equal to y, F is in the function family, and the commitment to F,r is the commitment string.
Committing to a function: syntax
A functional commitment scheme for a function family F has a setup algorithm that outputs global parameters, a commit algorithm that takes a function description and randomness, producing a commitment string, and an evaluation protocol.
Four important functional commitments
Polynomial Commitment Scheme: Commits to a univariate polynomial of degree at most d. The prover can open the polynomial at any given point.
Multiline Commitment: Commits to a multiline polynomial with degree at most one in each variable. The prover can open the committed function at any point in the domain.
Vector Commitment: Commits to a vector of dimension d. The prover can open any particular cell in the vector. Merkle trees are an example of a vector commitment scheme.
Inner Product Commitment: Commits to a vector u, defining a function f_u that takes a vector v as input and outputs the inner product of u and v.
These four function families are essential building blocks for creating a ZK-SNARK. They can be built from any of the other four. In particular, let's focus on polynomial commitment schemes.
Polynomial Commitments
In the context of polynomial commitments, the prover commits to a univariate polynomial of degree at most d. The evaluation protocol is used to convince the verifier that the committed polynomial satisfies f(u) = v, with the degree of the polynomial being at most d. The proof size and time for the verifier should be at most logarithmic in the degree of d.
There are several constructions for polynomial commitments, such as the KZG'10 which requires a trusted setup, Dory from 2020 which does not require a trusted setup but is slower, FRI using hash functions, Bulletproofs using elliptic curves, and Dark from 2020 using a group of unknown order. In practice, KZG'10 is the most widely used commitment scheme.
The Trivial Commitment Scheme is Not a Polynomial Commitment
The trivial commitment scheme, where the commitment is a hash of the coefficients of the polynomial, is not a polynomial commitment scheme because the proof size and verification time are both linear in the degree d, while we want them to be logarithmic in d.
A Useful Observation
A useful observation is that the probability of a non-zero univariate polynomial f being zero at a random point r in the finite field is at most d/p, where p is the size of the field. This observation is critical for ZK-SNARKs and extends to multivariate polynomials through the Schwartz-Zippel-DeMillo-Lipton (SZDL) lemma.
领英推荐
Equality Test Protocol
The equality test protocol is used to check if two committed polynomials f and g are equal. The verifier chooses a random element r from the finite field, and the prover evaluates the polynomials at r and sends the evaluations along with the proofs to the verifier. The verifier then checks if the evaluations are equal and if the proofs are valid.
Making it a SNARK (non-interactive)
To make the interactive protocol non-interactive, we can use the Fiat-Shamir Transform, which converts public coin protocols (where the verifier only sends random data to the prover) into non-interactive protocols. In this case, the prover has a statement x and a witness w, while the verifier only has the statement x. The verifier sends randomness to the prover, who sends a response that the verifier checks for validity.
By applying the Fiat-Shamir Transform to the equality test protocol, we obtain a non-interactive protocol for checking the equality of two committed polynomials, which can be used as a building block for ZK-SNARK constructions.
A SNARK for Polynomial Equality Testing
The fundamental idea in this method involves using a hash function, allowing the prover to generate the verifier's random bits independently using hash function H. In this scenario, the prover and verifier possess the commitments com_f and com_g (the statement x), while the prover has the polynomials f and g in the clear (the witness).
The prover hashes the statement x (com_f and com_g) to obtain the random challenge on its own and then computes the response to this random challenge. This response is sent to the verifier, which also computes the challenge r by hashing com_f and com_g. Finally, the verifier checks if the prover's response is correct. This non-interactive protocol is knowledge sound and can be proven to be a SNARK. However, it is not a ZK-SNARK since the verifier learns the value of the polynomials f and g at point r. In practice, the hash function H can be instantiated using a cryptographic hash function like SHA256.
Back to the Paradigm
The discussion on polynomial commitment schemes is complete for now, and we return to the general paradigm that combines a functional commitment scheme with an interactive oracle proof to build a SNARK for general circuits. The goal of an Interactive Oracle Proof (IOP) is to boost a functional commitment for a specific function family into a SNARK for general circuits. For example, a polynomial IOP can boost the polynomial commitment scheme and build a SNARK for any circuit with a maximum of d gates.
Component 2: F - Interactive Oracle Proofs
An F-IOP, given a fixed semi-arithmetic circuit C(x,w) and statement x, is a proof system with a specific structure that proves the prover knows w such that C(x,w) equals zero. The process begins with a setup procedure that preprocesses circuit C, generating public parameters for the prover and verifier. The verifier parameters contain a number of functions (or oracles) that can be replaced by commitments later on.
The prover and verifier engage in a protocol where the prover sends oracles for functions f1, f2, ..., f_t to the verifier. The verifier contributes random data throughout the protocol. Once the prover has sent all oracles, the verifier runs a procedure to decide whether to accept or reject the proof, given access to the functions in the verifier parameters and those sent by the prover. The verifier can evaluate these functions at any point of its choice.
Properties
The properties of an IOP are familiar: completeness, knowledge soundness, and zero knowledge. In the case of an honest prover, the verifier should accept the proof. For knowledge soundness, a malicious prover cannot convince the verifier that it knows w such that C(x,w) equals zero if no such w exists or if it doesn't know w. Extractors can be built using the information given to verify knowledge soundness. Since the extractor is given the functions from the prover in the clear, it can build unconditionally secure extractors, making IOPs information-theoretical objects that can be proven without additional assumptions. Lastly, the IOP may also need to be zero knowledge, ensuring it doesn't leak any information about the witness that the verifier didn't already know.
An Example Poly-IOP (a bit contrived)
This section explains a simple example of a polynomial IOP that is built on top of a polynomial commitment scheme. The example demonstrates an IOP designed for a circuit that tests containment. The public statement is a set X, and the secret witness is a set W. The prover aims to prove that set X is contained in set W, both being subsets of a finite field. To do this, the prover will compute two univariate polynomials, f and g, which have the elements of sets W and X as their roots, respectively. The prover then computes the quotient polynomial, q, by dividing f by g. If the set X is contained in the set W, then q will be a polynomial. The prover sends Oracles for polynomials f and q to the verifier, who then chooses a random value, r, and queries the Oracles at point r. The verifier will accept the proof if the evaluations at the random point are equal.
The IOP Zoo
The IOP Zoo refers to a general way to build SNARKs for various circuits, starting with a polynomial commitment scheme, a multilinear-IOP, or a vector commitment. Examples of IOPs include Sonic, Marlin, Plonk, Spartan, Clover, Hyperplonk, Stark, Breakdown, and Orion. These IOPs can be combined with appropriate functional commitment schemes to create SNARKs. The Fiat-Shamir transformation is then used to convert the interactive proof system into a non-interactive SNARK.
SNARKs in Practice
In practice, developers write their code in a domain-specific language, such as Circom or ZoKrates, instead of directly creating arithmetic circuits. A compiler then translates the code into a SNARK-friendly format, like a circuit or R1CS. In some cases, the code is compiled into EVM bytecode as input for the SNARK backend system. Finally, the SNARK backend prover takes the public statement and witness as input and produces the proof as output. The heavy computation occurs in this last step. Future lectures will explore snark DSLs and efficient multilinear interactive oracles, which, when combined with multilinear commitment schemes, can produce real-world SNARKs.
Conclusion:
Understanding the building blocks of SNARKs and the general framework for constructing them paves the way for practical applications in privacy-preserving technologies and various blockchain systems. By utilizing domain-specific languages, developers can efficiently create arithmetic circuits and leverage SNARK backends for proof generation. As research in this field progresses, we can expect more efficient and practical SNARKs to emerge, enabling a wide range of applications in the realms of cryptography and privacy.
P.S.
I believe that constructive feedback is essential for personal and professional growth, and I welcome any comments or thoughts you may have regarding my article. Your feedback will help me improve my writing and provide better content for you in the future.
If you found this article valuable, I encourage you to follow me on LinkedIn to stay updated on my latest posts. Your support and engagement mean a lot to me, and I am grateful for every like, comment, and share.
Thank you for your time, and I look forward to connecting with you.