ZK Beacon Chain Light Client Spec (Gnosis Chain version)

Gnosis Chain is a canary chain for eth2. Gnosis would like to implement a ZK-based light client for the beacon chain consensus (on Gnosis Chain), which can be validated either by an off-chain user or an EVM smart contract (for use in bridges). Since beacon chain uses BLS12-381, there are currently no Eth precompiles and using ZK helps overcome high gas costs.

Implementing a ZK-based light client would involve generating a SNARK of attestations of a sync committee. This consists of 512 validators rotating every ~27 hours (256 epochs), (see here), so the latency requirements are minimal. (Although if the light client followed updates more closely it would have to process more headers and signatures during that 27 hour period.)

Resources

Official light client spec
- Vitalik has an older annotated light client spec that differs slightly
- Pull request on light client network protocol with discussion
Ben Edgington's annotated Eth2 spec
Vitalik's annotated Eth2 spec

Sync committees

Sync committees are chosen ever 256 epochs (~27 hours) consisting of 512 validators. The sync committee signs every block.

The BeaconBlockState contains block_roots and state_roots for the past SLOTS_PER_HISTORICAL_ROOT = 256 * 32 = 8192 slots, which is the sync committee period.

Background on light client

High level overview

Say light client has finalized block header in slot N. This is in sync committee period X = N // 8192. From the current header we know the sync committess in periods [X, X + 1].

The light client receives an attested header in slot M.
The period M // 8192 needs to be in [X, X + 1] so that we can validate the attested header using sync committee signatures.
Given a valid attested header, we can verify a finalized block in some slot N' in [M - 8192, M - 1].
We make the new finalized block in slot N' the updated light client stored block header.
If the period N' // 8192 = X + 1, then we update the stored sync committees in periods [X + 1, X + 2].

This means a new finalized block needs to be realized within a single period = 256 epochs = 8192 slots.

Spec details

Using official light client spec.

A light client receives some initial snapshot from a trusted source.
It then receives LightClientUpdate containers and must update its tracked BeaconBlockHeader according to this information. This is received either via p2p network or client-server setup.
It maintains its state in an object LightClientStore

The crux of the light client update is validate_light_client_update, which must validate an instance update of LightClientUpdate.

Slightly confusingly, LightClientUpdate contains attested_header and finalized_header fields. (The best guess reasoning is that attested_header is newer than finalized_header?) If the update is valid, update.finalized_header becomes the new snapshot header.

The main steps of the validation are:

Verify Merkle branch of header - Merkle proof of inclusion of update.finalized_header in the state of update.attested_header (BeaconState has a finalized_checkpoint field).
- Path length is floorlog2(FINALIZED_ROOT_INDEX)
  $= ⌊ \log_{2} (105) ⌋ = 6$ .
Verify Merkle branch of sync committee - Merkle proof of inclusion of next_sync_committee in the state of update.finalized_header.
- Path length is floorlog2(NEXT_SYNC_COMMITTEE_INDEX)
  $= ⌊ \log_{2} (55) ⌋ = 5$ .
Verify BLS signature - Verify the aggregate BLS signature over all participants in the sync committee (provided as a bit vector) of update.attested_header

The reasoning is:

We have stored sync committee info from previous snapshot
We trust update.attested_header because we verified it was signed (attested) by some fraction of the sync committee.
We trust update.finalized_header since it's in the state of update.attested_header
We can update sync committee info because it's in the state of update.finalized_header

The update validation can also be run without update.finalized_header where Step 1 is skipped and Step 2 is done with update.attested_header instead. This is to keep a running "best valid update", which is the current verified update.attested_header with the most sync committee participants. This best valid update is used in case a sync period elapses with no finalized checkpoint.

Sync Committee Aggregation

class SyncCommittee(Container):
    pubkeys: Vector[BLSPubkey, SYNC_COMMITTEE_SIZE]
    aggregate_pubkey: BLSPubkey

It seems we need to aggregate SYNC_COMMITTEE_SIZE = 512 pubkeys for the aggregate signatures. In the non-ZK setting there is an optimization available:

SyncCommittee contains aggregate_pubkey as the elliptic curve sum of all the pubkeys of validators on the sync committee. This means that we only need to subtract from aggregate_pubkey the pubkeys of people in the committee that did not sign. So if we have a 90% participation rate, then we only need to subtract 51 pubkeys, instead of adding 461.
This only needs to be done once per sync committee period (256 epochs = ~27 hours)
Due to the nature of ZK circuits, this optimization is unlikely to help in ZK.

Comparison with other bridge architectures

With BLS12-381 precompile

If EIP 2537 is implemented, then with precompiles of field-to-curve and pairing, gas cost of a single BLS signature is 75000 + 43000*2 + 65000 = 226K gas (at 1 gas = 20 gwei this is 0.00452 ETH).

We would still need to aggregate the public keys of the sync committee, which would take another 512 * 500 = 256K gas. Plus gas costs of merkle proofs.

[todo] Call data costs are probably a bit higher than ZK version with private inputs as well.

However given this is only done every 27 hours, with precompiles it still seems better to implement the light client purely on-chain without ZK since it does not require a trusted setup or remote proving servers, which decrease security.

ZK Roadmap

Merkle proof

This should not dominate the constraints but does require writing circuits for Merkle proofs, which use Simple Serialization (SSZ) and SHA-256 (should already exist). This should be easier than zkAttestor since SSZ is simpler than RLP.

Aggregate BLS signature verification

We need to elliptic curve add 512 pubkeys and then verify one BLS signature. Unfortunately due to the way ZK circuits handle 'if' statements, there is unlikely to be an optimization to reduce the number of additions based on committee participation rate.

For BLS12-381, EllipticCurveAdd is currently 11.8K constraints. Note that this circuit performs both EllipticCurveAddUnequal and EllipticCurveDouble since we don't know which addition equation to use each time. There is potential for this to be optimized.

At first pass, the aggregation of pubkeys will take 512 * 11.8K = ~6M constraints. BLS signature verification (with hash to curve and subgroup checks) is 19.2M constraints. We can ignore the subgroup check on pubkeys since this can be done once upon addition of each new validator – this saves 789K constraints. There is some additional overhead that we need to deserialize pubkeys and signatures into

G_{1}, G_{2}

point format. For now this puts us in the ballpark of 26M constraints.

Execution

ZK Light Client:

Write a solidity smart contract which implements the ETH2 light client spec with the expensive parts computed off-chain via a zkSNARK.
Design a zkSNARK which verifies the aggregated BLS signature and verifies the Merkle tree inclusion proofs with Simple Serialization.
Build an operator node implementation that receives block headers and the sync committees' attestations from the beacon chain. It will then process this information and pass it on as input to the ZKP and then submit it to the smart contract.

Bridge:

When users want to w/d assets from the bridge, lock up tokens on Gnosis and make a Merkle root proof of the tokens being locked. Once the light client has been updated, generate the Merkle proof and submit it to the ETH1.
Verify the merkle root proof in a bridge contract and allow users to withdraw.

Notes:

This design requires no zkSNARK recursion and only 1 trusted setup.
The circuit size will be ~26M constraints.
Not clear what to do if no finalized checkpoint is reached during the sync period - can probably make circuit that does a dummy Merkle proof when no update.finalized_header is present. This requires trusting the oracle to collect the best valid header in some way.
The frequency at which the operator node wants to update the light client can be configured. A fixed cost of ~0.008 ETH at 40 gwei will be required for every update. Updating block X does not require for blocks [..., X-1] to be already existing in the light client.

Data Availability

The point is this is censureship resistant because anyone can generate a proof and send it to the ZK light client smart contract

Limited by proof generation which requires special machine and large zkey file

Martin Köppelmann

2022/06/23 13:36:59

### Data Availability The point is this is censureship resistant because anyone can generate a proof and send it to the ZK light client smart contract - Limited by pr

Trying to asses the practical consequences of those 3 options for a ABM/token bridge. Option 1) would mean that bridging messages/tokens from GC to Ethereum could take up to 27h. One would need for a new ZK verified checkpoint (block) and then one could provide a Merkel proof that a previous blockhash was part of the chain and that within that block a specific event happened. (Edited)

2022/06/23 13:44:06

### Data Availability The point is this is censureship resistant because anyone can generate a proof and send it to the ZK light client smart contract - Limited by proof generation which requires s

Is there an option to still use the simpler model1 but still allow intermediate states? So e.g. any finalized state on GC can be submitted to Ethereum as long as it is signed by the sync committee? (Edited)