-
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, and encoded evaluation of the QAP at the secret point s in G2: {A_i(s), B_i(s), C_i(s)} for i=0 to n and H^(s^(-d)), where A_i, B_i, C_i are the polynomials encoding the circuit, H and G are generators of groups G1 and G2 respectively, s is the "toxic waste", and d is the degree of the QAP.
- Verification key (vk): Encoded evaluation of the QAP at the secret point s in G1, and G^(alpha * s^(-d)): (A(s), B(s), C(s), G^(alpha * s^(-d))). 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 constructs:
- A = e(g, g)^(alpha * s * a) * H^(s^(-z)), where e denotes the bilinear pairing, g is the generator of G1, a is the evaluation of the A polynomial at s, and z is the output of the zero testing polynomial evaluated at s.
- B = e(g, g)^(beta * s * b), where b is the evaluation of the B polynomial at s.
- C = e(g, g)^(gamma * s * c), where gamma is a different fixed generator of the multiplicative group of the finite field, and c is the evaluation of the C polynomial at s.
The proof π = (A, B, C) is valid if the following equation holds in the target group of the pairing:
- e(A, vk_1) * e(B, vk_2) = e(C, vk_3).
More precisely, the prover takes into account the influence of both the public inputs and the private witness:
- e(π_A, vk_1) * e(π_B, vk_2) = e(π_C, vk_3) * e(g, vk_x1)^(x1) * e(g, vk_x2)^(x2) * ... * e(g, vk_xm)^(xm)
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 witness w 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, vk_3) * e(g, vk_x1)^(x1) * e(g, vk_x2)^(x2) * ... * e(g, vk_xm)^(xm)
Where:
π_A = e(g, g)^(alpha * s * a) * H^(s^(-z)) π_B = e(g, g)^(beta * s * b) π_C = e(g, g)^(gamma * s * c) The left-hand side of the equation e(π_A, π_B) = e(g, g)^(alpha * beta * s^2 * a * b) because of the bilinearity property of the pairing function. The right-hand side e(π_C, vk_3) * e(g, vk_x1)^(x1) * e(g, vk_x2)^(x2) * ... * e(g, vk_xm)^(xm) = e(g, g)^(gamma * s * c + alpha * s * (x1+x2+...+xm)).
For the equation to hold true, we must have alpha * beta * s^2 * a * b = gamma * s * c + alpha * s * (x1+x2+...+xm), which reduces to a * b = c + (x1+x2+...+xm)/s, which is equivalent to our original assertion that A(s)*B(s) = C(s) + H(s)*Z(s) when H(s) evaluates to zero at the roots.
Thus, 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, this constitutes the mathematical basis of the Trusted Setup in the Groth16 zk-SNARK system.