Technical guide to ZkBNB parameters generation using MPC

Zero Knowledge
1

Abstract

BNB Chain has built zkBNB, a zero-knowledge scalability L2 solution to provide efficient and cheap way for users to make transactions for token operations and built-in 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 battle-tested 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 zkBNB-Setup 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 circuit-specific.

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:

[\tau] := (\tau^0, \tau^1, ... \tau^{2n-1})\cdot G_1\\ [\alpha\tau] := \alpha(\tau^0, \tau^1, ... \tau^{n-1})\cdot G_1\\ [\beta\tau] := \beta(\tau^0, \tau^1, ... \tau^{n-1})\cdot G_1\\ [\beta] := \beta \cdot G_2

Initialization

We initialize the parameters using the generators G_1 and G_2 as the starting points:

[\tau^i]_0 := G_1, i\in [0..2n-2]\\ [\alpha\tau^i]_0 := G_1, i\in [0..n-1]\\ [\beta\tau^i]_0 := G_1, i\in [0..n-1]\\ [\beta] := G_2

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:

  1. Sample toxic parameters \tau_j, \alpha_j, \beta_j

  2. Update previous contribution:

    1. [\tau^i]_j := \tau^i_j [\tau^i]_{j-1}, i\in [0, 2n-2]
    2. [\alpha\tau^i]_j := \alpha_j\tau^i_j [\alpha\tau^i]_{j-1}, i\in [0, n-1]
    3. [\beta\tau^i]_j := \beta_j\tau^i_j [\beta\tau^i]_{j-1}, i\in [0, n-1]
    4. [\beta]_j := \beta_j [\beta]_{j-1}

  3. Output proofs of knowledge for \tau_j, \alpha_j, \beta_j based on previous contribution points [\tau_{j-1}], [\alpha_{j-1}], [\beta_{j-1}]:

    1. \pi_{\tau, j} := \text{PoK}(\tau_{j-1}, [\tau_{j-1}])
    2. \pi_{\alpha, j} := \text{PoK}(\alpha_{j-1}, [\alpha_{j-1}])
    3. \pi_{\beta, j} := \text{PoK}(\beta_{j-1}, [\beta_{j-1}])

Verification

  1. Verify proofs of knowledge for current contribution:

    1. \text{CheckPoK}(\pi_{\tau, j}, [\tau_{j}], [\tau_{j-1}])
    2. \text{CheckPoK}(\pi_{\alpha, j}, [\alpha_{j}], [\alpha_{j-1}])
    3. \text{CheckPoK}(\pi_{\beta, j}, [\beta_{j}], [\beta_{j-1}])

  2. Check consistent update of parameters using pairing:

    1. For i\in[0..2n-1], \text{ CheckUpdate}([\tau^i]_j, [\tau^i]_{j-1})
    2. For i\in[0..n-1], \text{ CheckUpdate}([\alpha\tau^i]_j, [\alpha\tau^i]_{j-1})
    3. For i\in[0..n-1], \text{ CheckUpdate}([\beta\tau^i]_j, [\beta\tau^i]_{j-1})

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:

L_i(X) = \beta\cdot A_i(X) + \alpha\cdot B_i(X) + C_i(X)

Obviously, we can compute L_i but using the parameters from phase 1. Then, contributors use MPC protocol to generate

L :=\delta^{-1}\cdot(L_p(\tau), L_{p+1}(\tau), ..., L_{m-1}(\tau))\cdot G_1\\ [\delta] := (\delta\cdot G_1, \delta\cdot G_2)

where p is the number of public input wires and m is the total number of wires.

Pre-processing

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 n-1 degree A_i, B_i, C_i, i\in [0..m-1] where m is the number of wires, and the vanishing polynomial Z of degree n-2. Likewise, this step is deterministic and can be publicly verified easily. So a coordinator does the following:

  1. Evaluate L_i(\tau) using Lagrange basis of [\tau] from the pre-processing step
  2. Evaluate Z using monomial powers of [\tau]
  3. 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:

  1. Sample toxic parameters \delta_j

  2. Update previous contribution:

    1. L_j := \delta^{-1}_j(L_{j-1})
    2. Z_j := \delta^{-1}_j(Z_{j-1})
    3. [\delta]_j := \delta_j[\delta_{j-1}]

  3. Output proofs of knowledge for \delta_j based on previous contribution point [\delta_{j-1}]:

    1. \pi_{\tau, j} := \text{PoK}(\tau_{j-1}, [\tau_{j-1}])
    2. \pi_{\alpha, j} := \text{PoK}(\alpha_{j-1}, [\alpha_{j-1}])
    3. \pi_{\beta, j} := \text{PoK}(\beta_{j-1}, [\beta_{j-1}])

Verification

  1. Verify proofs of knowledge for current contribution:
    1. \text{CheckPoK}(\pi_{\delta, j}, [\delta_{j}], [\delta_{j-1}])
  2. Check consistent update of parameters using pairing:
    1. For i\in[p..m-1], \text{ CheckUpdate}(L_j, L_{j-1})
    2. For i\in[0..n-1], \text{ CheckUpdate}(Z_j, Z_{j-1})
      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:

(\alpha, \beta, \delta)\cdot G_1\\ (\beta, \delta)\cdot G_2\\ \delta^{-1}\cdot(\tau^0, \tau^1,..., \tau^{n-1})\cdot Z_x(\tau)\cdot G_1\\ \delta^{-1}\cdot(L_p(\tau), L_{p+1}(\tau),..., L_{m-1}(\tau))\cdot G_1\\ (A_0(\tau), A_1(\tau), ..., A_{m-1}(\tau))\cdot \beta\cdot G_1\\ (B_0(\tau), B_1(\tau), ..., B_{m-1}(\tau))\cdot \alpha\cdot G_1\\ (B_0(\tau), B_1(\tau), ..., B_{m-1}(\tau))\cdot G_2\\

where Z_x is the vanishing polynomial. The verification key vk scales linearly with the number of public inputs p:

(\alpha, \beta, \delta)\cdot G_1\\ (\beta, \delta)\cdot G_2\\ (L_0(\tau), L_{1}(\tau),..., L_{p-1}(\tau))\cdot G_1\\

How zkBNB-Setup Works

Participants

  1. Coordinator is responsible for initializing, coordinating and verifying contributions.
  2. 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

  1. Coordinator run the command zkbnb-setup p1n <p> <output.ph1>.

Contribution

This is a sequential process that will be repeated for each contributor.

  1. The coordinator sends the latest *.ph1 file to the current contributor
  2. The contributor run the command zkbnb-setup p1c <input.ph1> <output.ph1>.
  3. Upon successful contribution, the program will output contribution hash which must be attested to
  4. The contributor sends the output file back to the coordinator
  5. The coordinator verifies the file by running zkbnb-setup p1v <output.ph1>.
  6. 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 zkbnb-setup p1v to determine whether the user has maliciously replaced previous contributions or re-initiated one on its own

Phase 2

Depending on the R1CS file, the coordinator run one of the following commands:

  1. Regular R1CS: zkbnb-setup p2n <lastPhase1Contribution.ph1> <r1cs> <initialPhase2Contribution.ph2>.
  2. Parted R1CS: zkbnb-setup 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.

  1. The coordinator sends the latest *.ph2 file to the current contributor
  2. The contributor run the command zkbnb-setup p2c <input.ph2> <output.ph2>.
  3. Upon successful contribution, the program will output contribution hash which must be attested to
  4. The contributor sends the output file back to the coordinator
  5. The coordinator verifies the file by running zkbnb-setup p2v <output.ph2> <initialPhase2Contribution.ph2>.
  6. 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 zkbnb-setup p2v to determine whether the user has maliciously replaced previous contributions or re-initiated one on its own

Keys Extraction

At the end of the ceremony, the coordinator runs zkbnb-setup keys <lastPhase2Contribution.ph2> which will output Groth16 bn254 curve pk and vk files

1 Like