04 First Principles Hand Waving

A key part of Groth16 zk-SNARKs is the Trusted Setup process. It's a crucial step that involves the generation of parameters that are required for the zk-SNARK system to function. This process often involves the creation and destruction of a "toxic waste," which if mishandled, could compromise the security of the whole system. Please note this explanation has been heavily simplified to provide a conceptual understanding, implementing this system requires extensive knowledge in cryptography and careful consideration of all security implications.

First Principles: zk-SNARKs in a Nutshell

zk-SNARKs are based on a concept in cryptography called "interactive proof systems." The idea is that a prover wants to convince a verifier that a certain statement is true, without revealing anything other than the veracity of the statement.

In a zk-SNARK, the interaction between the prover and verifier is "compiled" into a single message (the proof) and any third party can check the validity of the proof. The term zk-SNARK stands for "Zero-Knowledge Succinct Non-Interactive ARguments of Knowledge":

• Zero-Knowledge: The verifier learns nothing but the validity of the statement. Succinct: The proof size is small and verification is efficient.
• Non-Interactive: The proof is a single message, and verification doesn't require back-and-forth communication.
• ARguments: The proof system is computationally sound, meaning a cheating prover can convince the verifier of a false statement only by breaking the cryptographic assumption (usually some form of discrete logarithm assumption).
• Knowledge: The prover knows a witness or solution to the problem instance.

Detailed Explanation: The Trusted Setup

The Trusted Setup is a critical process that generates the parameters used in the zk-SNARK system. The Setup is "trusted" because it involves the creation of an initial piece of information, often referred to as the "toxic waste," which must be destroyed for the system's security.

For Groth16, the Trusted Setup generates 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 verify a proof.

The construction of the parameters involves creating an initial instance of the toxic waste "s," which must be securely deleted after the generation of the parameters.

In Groth16, the generation of the parameters involves computing certain pairings on elliptic curves. Given the nature of the operation, it requires a pairing-friendly elliptic curve.

For a circuit C with n gates, the setup generates:

• Proving key (pk): {H^(alpha^i), H^(alpha^i * s), H^(alpha^i * s^2)} for i=0 to n, and {G^(alpha^i), G^(alpha^i * s), G^(alpha^i * s^2)} for i=0 to n, where H and G are generators of groups G1 and G2 respectively, alpha is a fixed generator of the multiplicative group of a finite field, and s is the "toxic waste".
• Verification key (vk): (G^alpha, H^alpha, H^(alpha * s^n)).

To create a proof π for a statement x and witness w, the prover constructs:

• A = ∑_{i=0}^{n} (w_i * pk_i) in G1.
• B = ∑_{i=0}^{n} (w_i * pk_{n+i}) in G2.
• C = ∑_{i=0}^{n} (w_i * pk_{2n+i}) in G1.

The proof π = (A, B, C) is a valid proof if the following equation holds in the target group of the pairing:

• e(A, vk_1) * e(B, vk_2) = e(C, vk_3).

These are the mathematical foundations of the Trusted Setup in the Groth16 zk-SNARKs system. It's crucial to destroy the "toxic waste" s after the setup to maintain the integrity and security of the system.