Abstract
BNB Chain has built zkBNB, a zeroknowledge scalability L2 solution to provide efficient and cheap way for users to make transactions for token operations and builtin NFT marketplaces. zkBNB is utilizing zkSNARK protocol to verify the validity of L2 state and achieve immediate finality. Specifically, zkBNB utilizes Groth16 due to its lowest efficient verification cost compared to other protocols, besides it has been battletested and deployed by various popular projects.
Groth16 is designed to work with arithmetic circuits, and gnark is an amazing library for writing these circuit. Yet, one of the major limitation with gnark is how the the CRS parameters are generated. More precisely, they are generated in a trusted manner which requires users to trust that whoever generated these parameters will never abuse the secret randomness to generate valid fraudulent proofs.
Of course such assumption is very strong and not practical for deploying projects such as zkBnB. Hence, we developed the zkBNBSetup tool to generate Groth16 CRS in gnark following this MPC protocol. Also, as we all love open source code, we have contributed the MPC setup feature to gnark.
MPC Protocol Overview
Groth16 has a setup algorithm which produces proving key pk and verifying key vk. It is of paramount importance that the randomness used during the setup to be destoryed. Otherwise, with these randomness, a malicious prover can generate proofs for fraudlent statements that will pass the verification successfully. Therefore to distribute this trust, we utilize MPC protocol to run the setup algorithm between a group of participants such that the security of the generated keys are guaranteed as long as one of the participant did not collude with others. The setup protocol is split into two phases, first one is universal and the second one is circuitspecific.
Notation
We denote [M]_j as the output of protocol after participants P_1,..., P_j have contributed their shares. Also, [M]_0 denote the initial parameters and we use G_1\in \mathbb{G}_1 and G_2\in \mathbb{G}_2 as publicly known generators.
Phase 1 (Powers of Tau)
The output of this phase depends on a power n, and the final output will look like the following:
Initialization
We initialize the parameters using the generators G_1 and G_2 as the starting points:
Basically, we are just setting the values of \tau, \alpha, and \beta to one.
Contribution
For j \in [N] where N is the number of participants, the participant P_j does the following:

Sample toxic parameters \tau_j, \alpha_j, \beta_j

Update previous contribution:
 [\tau^i]_j := \tau^i_j [\tau^i]_{j1}, i\in [0, 2n2]
 [\alpha\tau^i]_j := \alpha_j\tau^i_j [\alpha\tau^i]_{j1}, i\in [0, n1]
 [\beta\tau^i]_j := \beta_j\tau^i_j [\beta\tau^i]_{j1}, i\in [0, n1]
 [\beta]_j := \beta_j [\beta]_{j1}

Output proofs of knowledge for \tau_j, \alpha_j, \beta_j based on previous contribution points [\tau_{j1}], [\alpha_{j1}], [\beta_{j1}]:
 \pi_{\tau, j} := \text{PoK}(\tau_{j1}, [\tau_{j1}])
 \pi_{\alpha, j} := \text{PoK}(\alpha_{j1}, [\alpha_{j1}])
 \pi_{\beta, j} := \text{PoK}(\beta_{j1}, [\beta_{j1}])
Verification

Verify proofs of knowledge for current contribution:
 \text{CheckPoK}(\pi_{\tau, j}, [\tau_{j}], [\tau_{j1}])
 \text{CheckPoK}(\pi_{\alpha, j}, [\alpha_{j}], [\alpha_{j1}])
 \text{CheckPoK}(\pi_{\beta, j}, [\beta_{j}], [\beta_{j1}])

Check consistent update of parameters using pairing:
 For i\in[0..2n1], \text{ CheckUpdate}([\tau^i]_j, [\tau^i]_{j1})
 For i\in[0..n1], \text{ CheckUpdate}([\alpha\tau^i]_j, [\alpha\tau^i]_{j1})
 For i\in[0..n1], \text{ CheckUpdate}([\beta\tau^i]_j, [\beta\tau^i]_{j1})
Phase 2
In Groth16, circuits are represented in R1CS which then get transformed into three vectors of polynomials A_i, B_i, C_i. These polynomials are used to compute L_i where:
Obviously, we can compute L_i but using the parameters from phase 1. Then, contributors use MPC protocol to generate
where p is the number of public input wires and m is the total number of wires.
Preprocessing
In this step, we convert the monomial powers of [\tau] using Number Theortic Transfrom (NTT) into Lagrange basis so that we can make efficient polynomial operations. This process is deterministic and doesn’t involve any randomness or secrets. Hence, anyone can make it and it can be verified publicly.
Initialization
Given the circuit R1CS, we convert it into QAP which gives us three sets of polynomials of n1 degree A_i, B_i, C_i, i\in [0..m1] where m is the number of wires, and the vanishing polynomial Z of degree n2. Likewise, this step is deterministic and can be publicly verified easily. So a coordinator does the following:
 Evaluate L_i(\tau) using Lagrange basis of [\tau] from the preprocessing step
 Evaluate Z using monomial powers of [\tau]
 Initialize [\delta] to G_1 and G_2
Contribution
For j \in [N] where N is the number of participants, the participant P_j does the following:

Sample toxic parameters \delta_j

Update previous contribution:
 L_j := \delta^{1}_j(L_{j1})
 Z_j := \delta^{1}_j(Z_{j1})
 [\delta]_j := \delta_j[\delta_{j1}]

Output proofs of knowledge for \delta_j based on previous contribution point [\delta_{j1}]:
 \pi_{\tau, j} := \text{PoK}(\tau_{j1}, [\tau_{j1}])
 \pi_{\alpha, j} := \text{PoK}(\alpha_{j1}, [\alpha_{j1}])
 \pi_{\beta, j} := \text{PoK}(\beta_{j1}, [\beta_{j1}])
Verification
 Verify proofs of knowledge for current contribution:
 \text{CheckPoK}(\pi_{\delta, j}, [\delta_{j}], [\delta_{j1}])
 Check consistent update of parameters using pairing:
 For i\in[p..m1], \text{ CheckUpdate}(L_j, L_{j1})
 For i\in[0..n1], \text{ CheckUpdate}(Z_j, Z_{j1})
Note that n above denotes the next power of 2 that is larger than or equal to the circuit constraints number
Keys Extraction
After phase 2 is completed, we can extract the proving key pk:
where Z_x is the vanishing polynomial. The verification key vk scales linearly with the number of public inputs p:
How zkBNBSetup Works
Participants
 Coordinator is responsible for initializing, coordinating and verifying contributions.
 Contributors are chosen sequentially by the coordinator to contribute randomness to CRS. More importantly, contributors are requested to attest their contributions to the ceremony (e.g. social media announcement).
Phase 1
Note Value between <>
are arguments replaced by actual values during the setup
 Coordinator run the command
zkbnbsetup p1n <p> <output.ph1>
.
Contribution
This is a sequential process that will be repeated for each contributor.
 The coordinator sends the latest
*.ph1
file to the current contributor  The contributor run the command
zkbnbsetup p1c <input.ph1> <output.ph1>
.  Upon successful contribution, the program will output contribution hash which must be attested to
 The contributor sends the output file back to the coordinator
 The coordinator verifies the file by running
zkbnbsetup p1v <output.ph1>
.  Upon successful verification, the coordinator asks the contributor to attest their contribution.
Security Note It is important for the coordinator to keep track of the contribution hashes output by zkbnbsetup p1v
to determine whether the user has maliciously replaced previous contributions or reinitiated one on its own
Phase 2
Depending on the R1CS file, the coordinator run one of the following commands:
 Regular R1CS:
zkbnbsetup p2n <lastPhase1Contribution.ph1> <r1cs> <initialPhase2Contribution.ph2>
.  Parted R1CS:
zkbnbsetup p2np <phase1Path> <r1csPath> <outputPhase2> <#constraints> <#nbR1C> <batchSize>
Contribution
This process is similar to phase 1, except we use commands p2c
and p2v
This is a sequential process that will be repeated for each contributor.
 The coordinator sends the latest
*.ph2
file to the current contributor  The contributor run the command
zkbnbsetup p2c <input.ph2> <output.ph2>
.  Upon successful contribution, the program will output contribution hash which must be attested to
 The contributor sends the output file back to the coordinator
 The coordinator verifies the file by running
zkbnbsetup p2v <output.ph2> <initialPhase2Contribution.ph2>
.  Upon successful verification, the coordinator asks the contributor to attest their contribution.
Security Note It is important for the coordinator to keep track of the contribution hashes output by zkbnbsetup p2v
to determine whether the user has maliciously replaced previous contributions or reinitiated one on its own
Keys Extraction
At the end of the ceremony, the coordinator runs zkbnbsetup keys <lastPhase2Contribution.ph2>
which will output Groth16 bn254 curve pk
and vk
files