-
Notifications
You must be signed in to change notification settings - Fork 15
04 First Principles Hand Waving
A vital part of the Groth16 zk-SNARKs protocol is the Trusted Setup ceremony. It's a necessary step that involves the creation of parameters that underpin this flavor of zk-SNARK. This process includes the generation and disposal of a so-called "toxic waste", which if not properly disposed of, could compromise the system's security.
Note that while this explanation aims to provide a fundamental understanding, implementing this system requires extensive knowledge in cryptography and careful consideration of all security implications.
zk-SNARKs stem from the field of cryptography. The fundamental idea is for a prover to convince a verifier of a particular statement's truthfulness, without disclosing anything except the validity of the statement.
In zk-SNARKs, the interaction between the prover and verifier is condensed into a single message - the proof. This proof can be checked by anyone for its validity. The term zk-SNARK stands for "Zero-Knowledge Succinct Non-Interactive ARguments of Knowledge":
- Succinct: The proof is compact, and verification is efficient.
- Non-Interactive: The proof consists of a single message, and verification does not require back-and-forth communication.
- ARguments: The proof system is computationally sound, i.e., a dishonest prover can only convince the verifier of a false statement by breaching the underlying cryptographic assumption (typically some variant of the discrete logarithm problem).
- Knowledge: The prover possesses a witness or solution to the instance of the problem.
The Trusted Setup is an essential procedure that generates the parameters used in the zk-SNARK system. It's deemed "trusted" since it involves the creation of an initial secret element, often dubbed the "toxic waste", which must be discarded for the system's security.
For Groth16, the Trusted Setup yields two sets of public parameters: the proving key (pk) and the verification key (vk).
- Proving key (pk): Used by the prover to construct a proof.
- Verification key (vk): Used by the verifier to confirm the proof's validity.
The creation of these parameters necessitates the generation of an initial "toxic waste" 's', which must be securely discarded after the parameters are computed.
In Groth16, the parameter creation process involves the encoding of certain polynomials and their evaluations at a secret point on elliptic curves. This operation requires a pairing-friendly elliptic curve (we support BN254 at the moment).
For a circuit C with n gates, the setup generates:
- Proving key (pk): Encoded polynomials
a(s),b(s),c(s)in G1, the encoded evaluation of the QAP at the secret point s in G2, and modifications to Powers if Tau based Phase2 Ceremony. Wherea(s),b(s),c(s)are the polynomials encoding the circuit, z(t) is a "target polynomial" that has roots at the secret s values, and h(t) is a polynomial that encapsulates all the constraints of the problem. - Verification key (vk): Encoded evaluation of the QAP at the secret point s in G1, and (G1(alpha), G2(beta)). In addition to these, we also have verification elements for each public input. Let's denote the i-th public input as x_i. The corresponding element in the verification key, vk_xi, is an encoded value of a polynomial that represents the i-th public input in the circuit. Specifically, this is the encoding of the polynomial at the secret point s.
The purpose of these additional elements is to allow the verifier to check computations involving both the public inputs and the private witness. The encoding ensures that the proof must correctly incorporate the public inputs x_i in order to pass the verification check.
To create a proof π for a statement x and witness w, the prover must do a few transformations after representing the computation to reduce the problem.
In an R1CS, we represent the computation as a system of equations, where each equation ensures that the multiplication of two variables equals a third. The set of all equations can be represented in the form of a matrix. Each row corresponds to an equation, and each column corresponds to a variable. By convention, the first element is 1, followed by the public inputs and can be written as (w⋅A)∘(w⋅B)=w⋅C
This is the process of finding a polynomial that passes through a given set of points. In the context of zk-SNARKs, we take the values of each wire in the R1CS for each gate and find a polynomial that passes through these points. The polynomial is constructed such that it equals the value of the wire at the corresponding gate and zero at all other gates.
The R1CS representation can be converted into a QAP. The goal of this conversion is to create a representation that allows us to check the computations in a more efficient manner, taking advantage of the algebraic properties of polynomials. This is done through a process called "Lagrange interpolation". A QAP consists of three polynomials A(t), B(t), and C(t) that represent the left, right, and output wires of the R1CS, respectively. This represents the problem in a polynomial form a(t) * b(t) - c(t)=h(t)⋅z(t). Here, z(t) is a "target polynomial" that has roots at the secret s values, and h(t) is a polynomial that encapsulates all the constraints of the problem calculated by dividing the polynomial (a(t) * b(t) - c(t)) by z(t). This step ensures that the original constraints of the problem are satisfied if and only if a(t)*b(t) - c(t) = h(t)*z(t) equals zero when evaluated.
Once we have the QAP, we can generate the proof π = (π_a, π_b, π_a, π_c) . These components of the proof serve as a cryptographic commitment to the values of the wires at each gate, without revealing the actual values. The pairings used to construct these proofs allow for efficient verification, while preserving the zero-knowledge property of the system. The proof is valid if the following equation holds in the target group of the pairing:
e(π_a, π_b) = e(π_c, G) * e(π_h, G * Z(t))
This equation effectively checks the consistency of the computed values A, B, and C against the encoded values in the verification key. If they match, the proof verifies the statement without revealing the private inputs or any additional information.
Groth16 zk-SNARKs work based on the principle of Quadratic Arithmetic Programs (QAPs). A QAP is a particular way to represent a program that can be checked more efficiently. The process of turning a program into a QAP involves expressing the program as a series of polynomials such that the polynomials satisfy certain properties at a specific point.
Once we have the polynomials A(s), B(s), and C(s) which encode the circuit, and H(s) which is the polynomial that evaluates to zero at the roots, we can construct the proof using pairings.
Consider the following:
We have the equation A(s)*B(s) - C(s) = H(s)*Z(s), where Z(s) is a zero-testing polynomial. This holds if and only if the prover correctly evaluated the circuit.
If we evaluate the equation at a secret point s which is a root of the polynomial Z(s), the right-hand side H(s)*Z(s) will be zero, which means A(s)*B(s) = C(s)!
We have to prove this in the exponent which brings us to the pairing check.
In the Groth16 scheme, a proof π for a statement x (which are the public inputs) and a witness w (which are the private inputs) is valid if the following equation holds in the target group of the pairing:
e(π_a, π_b) = e(π_c, G) * e(π_h, G * Z(t))
If the verification equation holds, the prover has correctly computed the circuit with both public and private inputs, demonstrating the knowledge of a solution to the given QAP instance. The pairing check, therefore, ends up checking A(s) * B(s) - C(s) = H(s) * Z(s) in the exponent, upholding the integrity of the system.
Sans some handwaving for simplification to make the math look nice, this constitutes a good mathematical basis for the inner workings of Groth16 based SNARKs.