# 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](https://github.com/ethereum/consensus-specs/blob/dev/specs/altair/sync-protocol.md). This consists of 512 validators rotating every ~27 hours (256 epochs), (see [here](https://eth2book.info/altair/part3/config/preset#sync-committee)), 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](https://github.com/ethereum/consensus-specs/blob/dev/specs/altair/sync-protocol.md)
* Vitalik has an older annotated light client [spec](https://github.com/ethereum/annotated-spec/blob/master/altair/sync-protocol.md) that differs slightly
* Pull request on light client [network protocol](https://github.com/ethereum/consensus-specs/blob/723192f3ebb688c66f8dadb2f568edcf29320452/specs/altair/sync-protocol.md) with [discussion](https://github.com/ethereum/consensus-specs/pull/2802)
* Ben Edgington's annotated Eth2 [spec](https://eth2book.info/altair/)
* Vitalik's annotated Eth2 [spec](https://github.com/ethereum/annotated-spec/blob/master/phase0/beacon-chain.md)

## 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](https://github.com/ethereum/consensus-specs/blob/dev/specs/altair/sync-protocol.md).

- 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:
1. **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)` $= \lfloor \log_2(105) \rfloor = 6$.
2. **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)` $=\lfloor \log_2(55) \rfloor = 5$.
3. **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](https://eth2book.info/altair/annotated-spec#synccommittee). 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](https://eips.ethereum.org/EIPS/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 $\mathbb G_1, \mathbb G_2$ point format. For now this puts us in the ballpark of `26M` constraints.

### Execution

ZK Light Client:
1. Write a solidity smart contract which implements the ETH2 light client spec with the expensive parts computed off-chain via a zkSNARK.
2. Design a zkSNARK which verifies the aggregated BLS signature and verifies the Merkle tree inclusion proofs with Simple Serialization.
3. 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:
1. 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.
3. 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