Proof of Consensus Bridging between Ethereum and Gnosis Chain

Succinct is excited to announce the release of a gas efficient on-chain light client for Ethereum PoS, powered by succinct zero-knowledge proofs (zkSNARKs), allowing for arbitrary, trust-minimized cross-chain communication between Ethereum and Gnosis Chain.

Our demo proof of consensus token bridge between Goerli and Gnosis can be found at demo.succinct.xyz. This demo illustrates how an end-to-end bridge powered by a proof of consensus light client works. Our implementation of Ethereum proof of consensus is open source and available here.

Introduction

Gnosis Chain is an EVM chain using Ethereum 2.0 proof of stake (PoS) consensus that prioritizes the ability of individuals to become a validator on the network, while offering significantly more affordable blockspace to applications. Gnosis Chain has >100,000 validators and is the 2nd most decentralized chain in terms of validators. Applications on Gnosis Chain include projects like POAP, CirclesUBI, an experimental crypto-native video game, Dark Forest, but also DeFi blue chips like Uniswap, Curve and Sushi. Additionally, Gnosis Chain is home to 1500+ DAOs and offers extensive DAO tooling, including cross-chain governance.

The Gnosis Chain Omnibridge is a token bridge that allows for users to transfer funds from Ethereum to Gnosis Chain. Like most other bridges, the Ethereum - Gnosis bridge is controlled by a multisig, where members of the multisig watch for deposits on one chain and correspondingly sign off on withdrawals on the other. Although the vast majority of existing cross-chain bridges are based on this design, there is broad agreement in the blockchain space that multisig based bridges have several undesirable properties. Multisig architectures are centralized and censorable, place high trust assumptions on a small group of signers, and empirically are much less secure than the underlying blockchains they are bridging between. As the number of blockchains has grown in the past few years, it is important that they are able to interoperate in a trustless, decentralized and secure manner.

Gnosis is known for experimentation and pushing open-source public goods that benefit the entire Ethereum ecosystem--a notable example is the Gnosis SAFE which has become the canonical multisig wallet architecture. Members of the Gnosis team wanted to explore better designs for bridging that do not rely on centralized entities, which is how Succinct Labs and Gnosis started collaborating.

In our previous blog post, we outlined a vision for the end game of interoperability--proposing a design where zkSNARK technology enables succinct proofs of consensus, which can be used to power a trust-minimized bridge. Many of these ideas were born out of discussions with members of the Gnosis Chain team (Martin Köppelmann, Stefan George) and the former xDai team (Igor Barinov), and they deserve much of the credit. Five months ago, Gnosis DAO provided us with an extremely generous grant (GIP-57) to fund the R&D of such ideas and we are eternally grateful to them for funding such important work that was, at the time, quite risky and unproven. This grant funded our work on the demo proof of consensus bridge between Ethereum and Gnosis chain.

In the remainder of our blog post, we will dive into the technical details of our design, including the following:

• The Ethereum PoS light client protocol (the sync committee)
• Implementing SNARKs for Ethereum proof of consensus
• Using these succinct proofs to build a gas-efficient on-chain light client
• Creating a trust-minimized cross-chain bridge using a succinct on-chain light client

While our demo shows the feasibility of a SNARK-based approach for trust-minimized interoperability, there is a lot more work to be done before this can be used in production to secure real assets. At the end of this blog post, we provide a roadmap for productionizing this technology and are actively working with the core team at Gnosis Chain to build out a bridge betwen Ethereum and Gnosis Chain secured by this technology.

If you're interested in a high-level overview of this approach that goes into less technical detail, we recommend you check out our previous blog post.

Ethereum to Gnosis bridging powered by Proof of Consensus

We start with a high-level overview of proof of consensus bridging and explain how it leads to trust-minimized interoperability. This section reviews the "End Game" section of our previous blog post, with discussion specialized for Ethereum and Gnosis chain.

How to bridge trustlessly?

To communicate state between Ethereum and Gnosis Chain without a trusted intermediary, we can simply verify the consensus of the source chain in the execution environment of the target chain. This is the exact principle that light client nodes use to keep track of the state of a blockchain in a compute and storage-efficient manner.

Running an on-chain light client for Ethereum on Gnosis chain would allow for keeping track of Ethereum block headers on Gnosis (and vice-versa) without any additional trust assumptions, aside from trusting the economic security of the consensus of each participating chain. Once an on-chain light client can keep track of block headers of another chain, anyone can supply state proofs to prove any information (balances, storage, transactions, events) about the source chain in the context of the target chain. With this, building a cross-chain application, such as a token bridge becomes simple.

Historically, this approach has been difficult because on-chain computation is quite expensive. From a gas perspective, it’s not feasible to run these on-chain light clients, because the validators in Ethereum PoS consensus use BLS signatures and the EVM does not (currently) have a precompile for the BLS12-381 curve used in these signatures. This renders a naive Solidity implementation of such a light client prohibitively expensive.

Proof of Consensus

Recent advances in zero-knowledge proof systems, which allow for succinctly verifiable computation, make this approach feasible today. Similar to how zkSNARKs are powering zkEVM teams to scale execution, verifiable compute can also scale verification of consensus. In particular, "proof of consensus" (defined in our previous blog post), is the idea of using zero-knowledge succinct proofs to generate a validity proof of the state of a chain according to its consensus protocol¹. This validity proof can be used to power a gas-efficient light client, which facilitates trust-minimized interoperability. We note that we don't actually use the zero-knowledge property of "zero-knowledge proofs", we are using the succinctness property for scaling.

Ethereum PoS Light Clients

Because Gnosis Chain is a chain using Ethereum PoS consensus, to implement the above ideas for Ethereum - Gnosis Chain bridging, we simply need to implement a succinctly verifiable light client for Ethereum PoS. We also want to note that our design works for cross-chain communication between any Ethereum PoS chains. In the future, if more chains start using Ethereum PoS consensus, then this method works to build trustless cross-chain communication between all such chains! We dive into the technical details of how we built all of this in the following section, starting with a detailed description of the Ethereum PoS light client protocol.

Implementing Proof of Consensus for Ethereum

At a high-level, we want to implement an Ethereum PoS light client in a smart contract. The "Sync Committee" is the Ethereum PoS specification for light clients, covered in detail in the following section.

The Altair hard-fork to the Ethereum beacon chain introduced the sync committee protocol to allow for very compute-efficient light clients. The sync committee is a group of 512 validators assigned randomly from the full set of Beacon chain validators according to the RANDAO. The sync committee rotates every 256 epochs (roughly once every 27 hours). It's important the group of validators in the sync committee rotates periodically for security reasons. An excellent technical spec of the sync committee and light client protocol can be found here, but we provide a more gentle introduction.

An honest validator chosen for sync committee participation is responsible for signing blocks that are in their view of the canonical chain (according to observed attestations and applying the fork-choice rule). For each block that the sync committee signs, one member of the sync committee subset is responsible for producing an aggregate BLS signature and bitmap of the participating committee members to produce a SyncAggregate container with this information, which gets gossiped at the p2p layer.

With these SyncAggregate containers, there are 3 types of updates that a beacon node implementing the light client spec produces:

• A LightClientOptimisticUpdate contains a block header that has not yet been finalized but is in the canonical chain (according to the LMD Ghost fork-choice algorithm) along with the corresponding SyncAggregate with the aggregate BLS signature and bitmap.
• A LightClientFinalityUpdate contains an attested header that the sync committee has signed along with a finalized header that has been finalized according to the Casper FFG finality gadget. The update contains a merkle proof of the finalized header in the attested header. (At a more technical level, the merkle inclusion proof is of the finalized_checkpoint) field in the BeaconState container).
• When the next sync committee is known (at least 1 epoch ahead of time) the light client receives a LightClientUpdate, which contains an attested header that the sync committee signs, along the next SyncCommittee and a merkle proof that the next sync committee is contained in the attested header. This is an inclusion proof of the next_sync_committee in the BeaconState container. -->

On Chain Succinct Light Client

Smart contract code for the light client is here: https://github.com/succinctlabs/eth-proof-of-consensus/tree/main/contracts/src/lightclient. It's important to note that this code is unaudited and not production ready. It is also quite unoptimized and we are actively working on gas-optimizing the smart contracts and improving the proving time.

A light client node keeps track of the block headers of the canonical chain, in a compute and storage efficient manner, and applies light client updates to update this view as the canonical chain progresses². The on-chain light client also must keep track of the set of validators in the sync committee, since we need to know this information for signature validation.

The on-chain light client recreates the light client spec in Solidity (code here). In particular, we implement the process_light_client_finality_update function inside the step function in our smart contract. Then, inside step, where we would typically verify an aggregate BLS signature, we instead replace it with verification of a single Groth16 zkSNARK to reduce gas costs.

Recall that the validator set of the sync committee rotates every 27 hours. On chain, we keep track of a commitment to the set of validators in the mapping syncCommitteeRootByPeriod. To update this mapping for the next period, we verify the merkle inclusion proof that the current validator set signs for the commitment for the next validator set. This computation happens inside the updateSyncCommittee function.

Unfortunately, the commitment the validators sign is an SSZ commitment (simple serialization, Eth PoS serialization format) that is quite SNARK unfriendly, as it uses the SHA-256 hash function. It takes ~70 million constraints in a Groth16 circuit to compute the serialization of 512 validator BLS public keys to its corresponding SSZ commitment. Because we don't want to do this for every single header verification proof (which happens every 6 minutes, i.e. once per epoch), we use an additional SNARK (the commitmentMappingProof argument) to provably map an SSZ commitment to a SNARK-friendly Poseidon commitment, that is stored in the mapping sszToPoseidon. For each BLS signature verification, we pass in the poseidon commitment of the sync committee validators as public input to ensure that the BLS signature we are verifying is from the correct public keys. Overall this approach (using 2 SNARKs) saves us 70M constraints on the BLS signature verification SNARK, which we must run for every update we wish to submit to the light client. The commitment mapping SNARK must only be run every sync committee period (roughly once every 27 hours).

zkSNARKs

Code for circuits is here: https://github.com/succinctlabs/eth-proof-of-consensus/tree/main/circuits.

To build a gas-efficient light client, we utilize two zkSNARKs as mentioned in the on-chain light client design above. We will now go into more details about how these zkSNARKs are constructed. Our circuits can be found here.

Toolchain

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.

Aggregated BLS Signature Verification

This circuit builds on top of work by our collaborators at 0xPARC who implemented computation of elliptic curve pairings in Circom. It runs every time we want to update the light client with a new block header. The pseudocode for the header verification circuit is below.

# zkSNARK pseudocode
def verifyHeaderSignatures():
    public input header
    public input publicKeysCommitment
    private input aggregateSignature
    private input participationBitmap
    private input publicKeys
    # PoseidonHash is a hash function cheap to compute inside zkSNARKs
    assert publicKeysCommitment == PoseidonHash(publicKeys)
    aggregatePublicKey = aggregate(participationBitmap, publicKeys)
    assert BLSSignatureVerify(header, aggregateSignature, aggregatePublicKey)
    return sum(participationBitmap) # num of validators who signed

The bulk of the circuit is 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. To optimize the gas costs of the on-chain light client, we only store on-chain a SNARK-friendly commitment to the current set of public keys that govern the sync committee (as opposed to storing all 512 public keys in smart contract storage, which would be quite expensive). This commitment is a public input to our circuit (publicKeysCommitment above). The SNARK-friendly commitment is not normally available in the block headers, so we use the zkSNARK described below to map the SSZ commitment that is normally available in the block header to a more SNARK-friendly commitment that uses the Poseidon hash function.

Sync Committee Commitment Mapping

The sync committee rotates approximately every 27 hours and the current set of validators signs a block header that contains a SSZ hash of the next sync committee's public keys. As previously mentioned, the SSZ hash is SNARK unfriendly as it uses SHA-256, making the number of constraints to compute this hash quite large. We created a circuit that takes in a signed block header and maps the nextSyncCommitteeRoot field (the SSZ hash of the next validator set) to a SNARK-friendly Poseidon hash of the validator set. The pseudocode for this circuit is below.

# zkSNARK pseudocode
def mapSSZToPoseidonCommitment():
    public input finalizedHeader # already validated in smart contract
    private input publicKeys
    private input aggregatePublicKey
    sszRootPublicKeys = SSZ(publicKeys, aggregatePublicKey)
    # SNARK-friendly commitment used in verifyHeaderSignatures
    poseidonRoot = PoseidonHash([publicKeys, aggregatePublicKey]) 
    assert finalizedHeader.nextSyncCommitteeRoot == sszRootPublicKeys
    return sszRootPublicKeys, poseidonRoot

We store this SNARK-friendly commitment on-chain and use it as an input to the BLS signature verifcation SNARK to ensure that the signature we are verifying is indeed from the sync committee validators. This circuit runs every 27 hours, for every sync committee rotation.

Proving Time Benchmarks

It is important to note that these benchmarks are preliminary figures that reflect unoptimized proving time and unoptimized smart contracts. We are actively working on reducing both proving time and gas-costs for our smart contracts.

Proving Time

In circom, witness generation and proving time are separated, and end to end proof generation time is their sum. We generate these proofs on an 32-core 3.1GHz, 256G RAM machine with 1TB hard drive on AWS.

Arbitrary Message Passing & Token Bridge

Below is a diagram showing the arbitrary message passing, light client and bridge system architecture. We walk-through the components in the following paragraphs.

Using our light client, one can pass arbitrary messages between any two Ethereum PoS chains, such as Ethereum and Gnosis Chain. In our demo (demo.succinct.xyz), we have a simple bridge deposit contract that users can deposit "Succincts" into that passes a message to our arbitrary message bridge (AMB), which stores this message in its storage. A light client operator is responsible for taking sync committee attestations, generating a SNARK proof for valid BLS signature verification, and submitting a light client update to the Gnosis Chain smart contract.

On Gnosis Chain, after the Ethereum block in which the deposit transaction was included is finalized (generally 2 epochs, ~12 minutes) and the light client has been updated with a block of height greater than or equal to this block, our relayer automatically submits an executeMessage transaction to the Gnosis AMB. The executeMessage transaction contains a merkle storage proof against a slot that a light client has been updated with. During executeMessage, the AMB uses the light client to get the Ethereum state root for the requested slot and verifies the merkle storage proof showing that the message has been sent on the AMB on the other side. Then the AMB calls the recieving smart contract with the calldata specified in the message.

Discussion of Bridge Designs

Security Analysis

The sync committee protocol has light client security, and not the security of full Ethereum consensus. In particular, the sync committee only has a randomly chosen subset of 512 of Ethereum's validators. However, assuming 2/3 of Ethereum's validator set is honest, there is a vanishing probability that 2/3 of the sync committee is dishonest (using statistical concentration bounds). Another consideration is that the sync committee validators do not get slashed for double-signing blocks for the same slot. Thus the trust assumption on the sync committee validators is one of honesty, not economic security based on slashability. The sync committee spec mentions bridges as a potential application and other cross-chain communication protocols, such as IBC, also have light-client security as a core trust-assumption; nonetheless it is important to distinguish between the security of full Ethereum consensus and the sync committee protocol. While light client security is less than full Ethereum consensus, a bridge based on the security of the sync committee has far fewer trust assumptions than a bridge based on a multisig.

Comparisons

Today, most bridges are controlled by centralized multisigs that watch one chain for deposits and correspondingly sign off on withdrawals/minting on another chain. This places an incredible amount of trust on the operators of the multisig to act honestly. In contrast, our design is permissionless, because anyone can generate proofs to operate the light client and anyone can relay the messages from one chain to another. Because of this, our design is also in theory uncensorable and much more decentralized than a multisig approach. Because our approach simply involves verifying the source chain's consensus, this proof-based approach has no additional trust assumptions beyond trusting the consensus of the two interacting chains.

Some downsides of our approach are that verifying SNARK proofs and updating the light client takes more gas than verifying signatures from a multisig. Additionally, our method has extra latency for proof generation time (although we believe this can be reduced to be negligible). Finally, zkSNARKs are a relatively new and complex technology, and must be carefully audited before their production use to make sure there are no missing constraints (to ensure forging a proof is impossible). We are working on designing adequate guardrails for thoughtfully deploying this technology.

Roadmap

While our proof of concept and demo show how zkSNARK technology and proof of consensus are feasible today, there remains a significant amount of work before using our current system in production. We are collaborating very closely with the Gnosis Chain team to take our existing work, audit it, and make it production ready (with the appropriate guardrails) to build a trust-minimized bridge between Ethereum and Gnosis Chain.

We are also quite actively working on proof of consensus implementations for other blockchains, as well as deploying our existing Ethereum light client implementation to these blockchains.

Thank You

We would like to thank GnosisDAO for an extremely generous grant to fund the R&D behind this work and for being much of the originating source behind the ideas in this project. We would also like to thank 0xPARC for grant funding and supporting us from the beginning, including providing us with an amazing community of friends and collaborators whose work we were able to heavily rely on.

Thank you to Jonathan Wang, Yi Sun, gubsheep, Friederike Ernst, Martin Koeppelmann, Stefan George, Igor Barinov, Kirill Fedoseev, Kobi Gurkan for helping us throughout this work and supporting us in every way.

Footnotes

1. Celo's Plumo protocol is based on a similar idea, with a slightly different use-case of enabling compute efficient light clients on mobile devices. 
2. For our on-chain light client, since it's being used for cross-chain communication, we focus on keeping track of finalized headers, as we only want state to be communicated from one chain to another upon finalization. Thus, our on-chain light client does not process optimistic updates.