A short primer on the zero-knowledge proofs (zkSNARKs) used in Telepathy.
We use the Circom programming language and the Groth16 proving system to generate our zkSNARKs. While a newer proof system (like PLONK arithmetization + KZG or FRI) would improve proving time, we believe Circom is the most production-ready zkSNARK stack today. In particular, Tornado Cash’s circuits are built on top of Circom and have been used for several years. Additionally, the on-chain verification cost of a Groth16 zkSNARK is the cheapest of all proving systems available today. All zero-knowledge proofs used in Telepathy are built with the aim of making it more gas-efficient to run an Ethereum Light Client on-chain. To properly understand the structure of the circuits, we recommend reading the sections on Sync Committees and Proof of Consensus. For more details, please refer to the source code itself.
To add a new block header to the Light Client, we must verify that at least two thirds of the sync committee has provided valid signatures for this block header. Thus, the bulk of the complexity inside this zkSNARK is actually involved in the verification of the specific signature scheme that Ethereum 2.0 validators use. In particular, Ethereum uses BLS12-381 signatures. Cryptographically speaking, verifying the sync committees signatures involves computing 512 elliptic curve adds over the BLS12-381 curve to get the sync committee aggregate public key, and a single elliptic curve pairing for the final BLS signature check. We also do a few other checks in the circuit, such as validating the Merkle proof for the Ethereum execution state root and checking the finality proof for the finalized block header.
One key detail about the Light Client contract is that it must know what the current sync committee is. While you could naively store all 512 public keys of these validators, this is extremely gas-inefficient, so a solution is to instead store a cryptographic commitment to the sync committee. Thankfully, the Ethereum Light Client protocol already provides such a commitment. Thus, we can pass this as an input to the Step circuit and unpack the commitment to get the public keys of the sync committee. Unfortunately, the hash function used to create this commitment (Sha256) is extremely expensive to compute inside zkSNARKs and unpacking this commitment every time we want to add a new block header can be prohibitively expensive in terms of proving time. For this reason, every 27 hours when there is a new sync committee, we unpack this commitment once and then compute a new commitment to the sync committee using a SNARK-friendly hash function known as Poseidon (within a zkSNARK). We store this SNARK-friendly commitment on-chain instead so that the Step circuit can very cheaply unpack the commitment inside its circuit. In short, the Rotate circuit maps the sync committee commitment from a SNARK-unfriendly to a SNARK-friendly one.
All benchmarks are performed on an r6a.8xlarge AWS instance which has 32 cores and 256GB of RAM.
As mentioned above, our circuits are currently using the Groth16 proving system. This proving system normally requires a process called a "trusted setup" that generates a public set of encrypted values (common reference string, aka CRS) that the circuit verifier uses to check for proof validity.
For Groth16, the trusted setup requires two phases. The first phase (referred to as "Powers of Tau") can be used for all circuits using Groth16 (and other proving system), and the second phase needs to be run for each circuit. Both of these phases have a 1 of N trust assumption, where the CRS is still secure as long as at least one of the participants is honest. For more details, please refer to this document.
For the first phase for both circuits, we used Hermez's powers of tau CRS. Specifically, we used their 227 CRS, which is the minimum sized one for our rotate circuit. The set of contributor public attestations for that CRS can be seen here.