What happens in the trusted setup phase of the Groth16 protocol

The Groth16 Protocol

Groth16, probably the most wide-used zk-SNARK (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge) on blockchains, was introduced by Jens Groth at Eurocrypt 2016 (that’s why it is named groth16). The paper, entitled `On the Size of Pairing-Based Non-interactive Arguments`, could be on eprint/2016/260.

Groth16 is based on R1CS (Rank One Constraint Systems) arithmetization. While its proof consists of only 3 elliptic curve poinsts, defined in the base filed G1, the verification is also fast with only 3 pairing computations. Think if you implement the protocol with the BN curve for 128-bit security level, the total size of 3 points in the proofs is about 200 bytes (3 x 2 x 254 bits, each point represented by two 254-bit finite field elements).

The below table was shown in the lecture ZKP MOOC Lecture 2: Overview of Modern SNARK Constructions comparing Groth16 to other zk-SNARKs.

The zk-SNARK protocols often require a trusted setup to generate a CRS (Common Reference String), proving and verification keys for the prover and verifier, respectively. Compared to other protocols, Groth16 protocol requires a trusted setup per circuit, that means, if you implement a new circuit, you must execute another trusted setup. Otherwise, it offers a smaller proof size and faster verification, and these features probably make this protocol more popular as it will consume less gas cost on the Ethereum blockchain. Groth16 is suitable for applications generating many proofs for the same circuit and performance is crucial.

This article will discuss the two setup phases of the Groth16 protocol.

Gorth16 Setup Protocol

The trusted setup of the Groth16 protocol can be found on page #17 of his paper. It is as the below picture:

Universal Setup

Assume that you are working with a group of points of order p on an elliptic curve E defined over a finite field F_q, and its generator G, i.e., [p]G = O. This phase of setup will generate a random number tau and its powers [tau⁰]G, [tau¹]G, [tau²]G, …, [tau^d]G. These values could be used for any circuit. You should remember that $p$ and $q$ are two distinct primes. For example, many practical ZKP systems use the BN254 curve, in which:

E : y² = x³ + 3,

q = 21888242871839275222246405745257275088696311157297823662689037894645226208583,

and

p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

The below simple Python code demonstrates this phase 1 setup.

def generate_powers_of_tau(tau, degree, point):
  return [multiply(point, int(tau ** i)) for i in range(degree + 1)]

Trusted setup

Phase 1: setup for all circuits

# 1. Get a random value tau
tau = random.randint(1, p)
# 2. Calculate tau*G1, tauˆ2*G1, …, tauˆd*G1
powers_of_tau_for_G1 = generate_powers_of_tau(tau, d, G1)
# Calculate tau*G2, tauˆ2*G2, …, tauˆd*G2
powers_of_tau_for_G2 = generate_powers_of_tau(tau, d, G2)

As we are working with asymmetric pairing, we need to generate powers of tau for both points G1 and G2. The former is a generator in the base field F_q and the latter is the generator in the extension field F_{q^k}, where k is the embedding degree of the elliptic curve E. For BN254 curve, k = 12. You must be familiar with pairing-friendly elliptic curves to understand that concept and to know why we need powers of tau in both fields. Generally speaking, a (Ate) pairing e(Q, P) takes two points as parameters and returns an element in the extension field F_{q^k}, where Q and P are multiple of G2 and G1, respectively. A complete introduction of such curves could be found in the paper A Taxonomy of pairing-friendly elliptic curves by Freeman, Scott, and Teske.

The degree d is the maximum degree of a polynomial that this powers of tau ceremony of a ZKP system will support for circuits. This number is equivalent to the maximum number of constraints of circuits. For example, snarkjs support a circuit with up to 2^{28} (≈256 million) constraints, so d could be any number smaller than or equal to 2^{28}.

Important: tau must be discarded after this setup phase to prevent dishonest provers from inventing fake ZK proofs without using the knowledge about the witness. Given powers of tau [tau]Gi, [tau²]Gi, …, [tau^d]Gi, for i = 1, 2, an adversary could not recover the value of tau unless he could solve the discrete logarithm problem, believed a NP-Complete problem, and hence infeasible to solve with the classical computers.

Circuit-Specific Setup

At this phase, assume you are working on a computation problem and converted it into an R1CS system that can be encoded as:

Lw ∙ Rw = Ow,

where L, R, and O are matrices with n rows (equal to the number of constraints) and m columns (equal to the length of the witness), and w is the witness vector. To understand step-by-step how to convert a computation problem to an R1CS system, the best online resource I found is The Rareskills Book of Zero Knowledge.

At the phase 2 setup per circuit, the trusted server generates random value alpha, beta that will be used to prevent a potential cheating prover from making up three curve points of proof A, B, and C:

alpha = random.randint(1, p)
beta = random.randint(1, p)
alpha_G1 = multiply(G1, int(alpha)) # alpha*G1
beta_G1 = multiply(G1, int(beta)) # beta*G1
beta_G2 = multiply(G2, int(beta)) # beta*G2

The trusted server also generates random $\gamma$ and $\delta$ to prevent dishonest prover from forgeries with public inputs to generate a false proof:

gamma = random.randint(1, p)
gamma_G2 = multiply(G2, int(gamma)) # gamma*G2
gamma_inv = 1 / GFp(gamma) # should be defined in a finite field GF(p)
delta = random.randint(1, p)
delta_G1 = multiply(G1, int(delta)) # delta*G1
delta_G2 = multiply(G2, int(delta)) # delta*G2
delta_inv = 1 / GFp(delta)p

Finally, trusted server compute powers of $\tau$ for public and private inputs

def generate_powers_of_tau_for_inputs(powers_of_tau, d, m, L_mat, R_mat, O_mat, alpha, beta, ell, gamma_inv, delta_inv):
  taus_for_public_inputs = []
  taus_for_private_inputs = []
  # require degree + 1 points to interpolate a polynomial of degree d
  xs = Fp(np.array([i + 1 for i in range(d + 1)]))
  # Each i-th col of matrices L, R, and W will be converted to a polynomial U_i(x), V_i(x) and W_i(x)
  for i in range(m):
    # U_i(x) = interpolate the i-th column of matrix L
    poly_Ui = galois.lagrange_poly(xs, L_mat[:, i])
    # Perform a random shift by multiplying the poly with a random factor beta
    beta_Ui = poly_Ui * beta # multiply U with beta
    # V_i(x) = interpolate the i-th column of matrix R
    poly_Vi = galois.lagrange_poly(xs, R_mat[:, i])
    # Perform a random shift by multiplying the poly with a random factor alpha
    alpha_Vi = poly_Vi * alpha
    # W_i(x) = interpolate the i-th column of matrix W
    poly_Wi = galois.lagrange_poly(xs, O_mat[:, i])
    sum_poly = beta_Ui + alpha_Vi + poly_Wi
    if i < ell:
      taus_for_public_inputs.append(inner_product(powers_of_tau, (sum_poly.coeffs[::-1]) * gamma_inv))
    else:
      taus_for_private_inputs.append(inner_product(powers_of_tau, (sum_poly.coeffs[::-1]) * delta_inv))
  
  return taus_for_public_inputs, taus_for_private_inputs
  
taus_for_public_inputs, taus_for_private_inputs = \
  generate_powers_of_tau_for_inputs(powers_of_tau_for_G1, d, m, L, R, O, alpha, beta, ell, gamma_inv, delta_inv)

Trusted Setup in practical ZKP systems

As mentioned above, the value of tau must be kept secret, it thus is risky if only a single entity to generate it. Practical ZKP systems usually implement an MPC (Multi-Party Computation) protocol for powers of tau. As there are many available online articles on this topic, I won’t talk more about this here. If you want to understand more, go to the following links:

1. Announcing the Perpetual Powers of Tau Ceremony to benefit all zk-SNARK projects.

2. Setup Ceremonies

3. The Design of the Ceremony

Groth16 setup by snarkjs

Let’s see how snarkjs perform the trusted setup phase for the Groth16 protocol:

You may need to install snarkjs first

npm install -g snarkjs@latest

snarkjs is a javascript library that can generate ZK proofs and verify them. Inputs for snarkjs to generate proofs are r1cs files that could be generated from circom.

Start a new powers of tau ceremony

```sh

snarkjs ptn bn128 8 pot08_0000.ptau

or,

snarkjs powersoftau new bn128 8 pot08_0000.ptau

Parameters:

- bn128: BN curve at 128-bit security level

- 8: powers of 2 indicating the maximum number of permitted constraints, i.e., this ceremony result will allow circuits with maximum 2⁸ constraints

- pot08_0000.ptau: output file

This command takes as input an elliptic curve (snarkjs supports bn128 and bls12–381), a number smaller than 28 (as snarkjs supports up to 2^{28} constraints only), and will output a transcript, i.e., powers of tau, individually generated by yourself.

Contribute to the ceremony

snarkjs ptc pot08_0000.ptau pot08_0001.ptau - name="First contribution"

or,

snarkjs powersoftau contribute pot08_0000.ptau pot08_0001.ptau - name="First contribution"

Parameters:

- pot08_0000.ptau: input file that is the transcript so far

- pot08_0001.ptau: output a new transcript containing all challenges and responses that have been taken contribution so far

- — name=”First contribution”: a note as you want

As mentioned earlier, a powers of tau ceremony should be a multi-party computation protocol, that is, contributed by several contributors. This command takes as input an individual contribution, then includes it with other contributions so far to return a new transcript.

Per circuit setup

After having lists of powers of tau, you are now going to setup a transcript for a specific circuit you have.

Phase 2 preparation

snarkjs pt2 pot08_0001.ptau pot08_final.ptau

or,

snarkjs powersoftau prepare phase2 pot08_0001.ptau pot08_final.ptau

Parameters:

- pot08_0001.ptau: input file that is the transcript so far

- pot08_final.ptau: output a new transcript adding alpha and beta values

This step setups random values $\alpha$ and $\beta$ to prevent a dishonest prover from cheating as discussed above.

Setup proving and verification keys

Assume that you implemented a circuit and compiled it to get a _r1cs_ file. If not, Circom can help with that. These links will guide you on how to write and compile a circuit.

Assume your circuit is compiled into a r1cs file and named circuit.r1cs. Use the below command to generate proving and verification keys for this circuit.

snarkjs g16s circuit.r1cs pot08_final.ptau circuit_0000.zkey

or,

snarkjs groth16 setup circuit.r1cs pot08_final.ptau circuit_0000.zkey

This command generates the reference `zkey` without phase 2 contributions. You then need to contribute to phase 2 of the ceremony:

snarkjs zkc circuit_0000.zkey circuit_0001.zkey - name="1st Contributor Name"

or,

snarkjs zkey contribute circuit_0000.zkey circuit_0001.zkey - name="1st Contributor Name"

Finally, you export the verification key, making it accessible to verifiers:

snarkjs zkev circuit_0001.zkey verification_key.json

or,

snarkjs zkey export verificationkey circuit_0001.zkey verification_key.json

Closing

This tutorial discussed the trusted setup phase in the Groth’16 Zero-Knowledge Proof protocol. Some `Python` code just demonstrated the setup process. You can find the full implementation of the Groth16 protocol on this repo. Hope you find it fun and useful!