zk-SNARK

Zero Knowledge Succinct Non-interactive Argument of Knowledge (zk-SNARK)

Zk-SNARKs are specifically zero-knowledge proofs that are:

• Succinct: meaning they can be verified in the matter of milliseconds with a proof length of a few hundred bytes.

• Non-interactive: refers to fact that the prover can send a single message to the verifier, without having many back-and-forth interactions.

Apart from these 3 requirements for zkp, completeness, soundness, and zero-knowledge, zk-SNARK adds few more for efficiency for the proving system.

A notable advantage of zkSNARK's is their relatively small proof sizes and constant-time verification.

Groth16

Groth16 is a proving scheme, which is widely-used, efficient ZK-SNARK protocol developed by Jens Groth in 2016 that minimizes proof size and verification time. It is a circuit-specific preprocessing general-purpose zk-SNARK construction. It has become a de-facto standard used in several blockchain projects due to the constant size of its proof, and its appealing verifier time.

Although, Groth16 required circuit-specific trusted setup, we decided not to go with Plonk because proof generation time in Plonk was very high (sometime in minutes) for our custom circuit. Moreover, proofs are shorter in Groth16 hence better performance and less Gas consumption (?).

BN128 elliptic curve

Groth16 need to be instantiated with an elliptic curve. To work with Groth16 curves must be:

1. Be secure, for proof soundness

2. Be pairing-friendly, for proof verification

3. Have a highly 2-adic subgroup order, for efficient proof generation.

We had four objectives while choosing the curve,

• a) Proofs generation should be fast (should generate proofs in seconds and not in minutes)

• b) Proofs should be decently secure (we are "okay" with 128bit security)

• c) Proofs should be compatible (proofs generated should be compatible with Ethereum as well as Cosmwasm contracts)

• d) Proofs must be cost effective (should consume less gas)

We decided to go with BN128 since its fast and is natively supported in Ethereum 1.0, which provides precompiled contracts for efficient pairing operations on this curve. As far as Cosmwasm is concerned, we had to use 3rd party libraries to give support for BN128 based proofs since Cosmwasm do not natively support this curve (yet).

The BN254 curve belongs to the BN family and is colloquially called BN128 in reference to the nominal security of the curve, or BN254 in reference to the bit-length of the relevant prime field. So not to be confused, they both are same.

Trusted Setup

Setting up the ZK-SNARK protocol requires the creation of a Universal Common Reference String (CRS). Also described as public parameters, the CRS enables secure communication between provers and verifiers. This CRS must be generated in advance by a trusted party. But the security of a system based on zkSNARKs largely boils down to how the CRS was generated. Doing so without compromising the ideals of privacy-preserving blockchain-based systems: (security and decentralization) is very important. The generation of public parameters for zkSNARKs is called the “setup ceremony” because of its importance and the need for multiple independent parties to contribute to the process.

The preferred technique for setup ceremonies has been multi-party computation (MPC). Setup ceremony MPC schemes are interactive protocols involving multiple parties who contribute randomness to iteratively construct the CRS. A typical ceremony consists of N number of players, the coordinator, and the verifier. The MPC protocols are always of a round-robin nature, where a player Pi receives a single message from player Pi-1.Payer Pi adds their input to accumulated randomness before passing it onto Player Pi+1. In the end, the final result is the CRS.

BGM17 MPC Protocol, Ref: https://zkproof.org/2021/06/30/setup-ceremonies/

The CRS is generated in two phases:

• The first phase (phase-1) referred to as “Powers of Tau”, produces generic setup parameters that can be used for all circuits of the scheme, up to a given size. This ceremony is perpetual — that is, there is no limit to the number of participants required, and any zk-SNARK project can pick any point of the ceremony to begin their circuit-specific second phase (phase-2).

• The second phase (phase-2) converts the output of the "Powers of Tau" phase (phase-1) into an NP-relation-specific (circuit-specific) CRS.

How does PoT (phase-1) ceremony works?

• Each participant will receive a challenge file.

• They must generate a response file in a secure and honest manner.

As long as one participant discards the toxic waste after this process, the entire ceremony can be trusted.

We did not run our own PoT phase-1 ceremony, instead we used Ptau files (of power 19 or 512 max constraints) for BN128 curve with 54 contributions from iden3 here.

You might be wondering what exactly is this max-constraints?

• The Power of Tau setup generates a series of powers of a secret value, τ, up to a specific limit, say τ^N . This maximum power N directly determines the maximum number of constraints that can be supported in circuits using these parameters.

• If the setup phase generates up to τ^N, it means that the final setup parameters can support up to N constraints in the ZK-SNARK circuit.

• iden3 ceremonies have gone as high as τ^2^28, which allows for up to 268 million constraints.

• Higher values of 𝑁 increase the computational load of the setup ceremony but offer more flexibility for complex circuits in the future.

and why did we choose 512 as our max constraints?

Choosing the power N depends on circuits and its completxity. For example, for our custom KYC circuits we needed minimum power 19 to put in perspective zk-rollups may need millions of constraints hence they need to use higher power value.