-
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, alpha is a fixed generator of the multiplicative group of a finite field, 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))).
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).
Sans some handwaving for simplification, this constitutes the mathematical basis of the Trusted Setup in the Groth16 zk-SNARK system.