[tracking] EVM light client bridge vs Gravity Bridge

[adlerjohn]

Problem Statement

Various rollups on EVM L1s may have a need for using Celestia as a DA layer, while keeping fraud/validity proof verification in the EVM. To that end, two concrete possibilities exist: the Gravity bridge and a native EVM light client. This issue summarizes how each will work, any changes necessary for our usecase, and pros and cons.

Gravity Bridge

The Gravity bridge is a project initiated in the Cosmos ecosystem: https://github.com/cosmos/gravity-bridge. Various forks (maybe as many as a dozen at this point) exist of this protocol, with minor changes. Non-exhaustively

1. https://github.com/PeggyJV/gravity-bridge (Rust off-chain code)
2. https://github.com/InjectiveLabs/peggo (Go off-chain code)

Method of Operation

The Gravity bridge has two components: an on-chain component written in Solidity and an off-chain component (the orchestrator) written in Rust (Peggy) or Go (Injective). A high-level explanation of the Solidity contracts can be found here.

The orchestrator runs alongside a Tendermint node (potentially as an SDK module) that causes validators (i.e. block producers) to, in addition to regular Tendermint votes, also sign EVM-compatible messages that mirror:

1. validator set changes, and
2. arbitrary events in blocks.

Specifically, messages are signed in accordance with ERC-191. These signatures are batched and sent to an on-chain contract. The contract keeps track of the validator set as it changes, and verifies that the arbitrary events are signed off by a supermajority of voting power.

Updates to the validator set must occur every time

1. The validator set changes too much (currently, 5% is recommended, though this parameter may be tweaked up to 33% I think), or
2. No other updates have occurred within the unbonding window. For safety, probably 1/2 the unbonding window should be used here.

To update the contract's view of the validator set, updateValset is called. The orchestrator will construct an EVM-compatible transaction with batched signatures here. The contract will simply verify that:

1. The provided previous validator set matches the known hash of the validator set, and
2. A supermajority of the previous validator set has voted correctly for the new validator set.

Then update its saved validator set hash.

I estimate this operation is ~500k gas each time. As an example, Ethereum is an EVM-compatible chain and at its current gas prices this would cost ~$400. It would be prohibitive to update the validator set every block, hence the above threshold of 5%. With only occasional updates, this cost should end up not being too significant.

Batches of arbitrary messages are submitted to the EVM chain with submitBatch. This requires verification of the current validator set and a supermajority of signatures. Note that arbitrary messages does not necessarily imply single blocks; properly implemented, a single batch of arbitrary messages can be made across as many blocks as can fit in the gas limit.

Required Changes

1. Numerous gas optimizations can and should be made. Just as an example of how immature the implementation is: when updating the validator set, the new validator set is provided. But this is actually not needed under an honest majority assumption; a commitment to the new validator set is sufficient.
2. The submitBatch function only works for transfers of fungible tokens across the bridge. This will have to be modified for our purposes, namely a list of (block height, namespace ID, message commitment) tuples.
3. The orchestrator exists mostly as a separate module for now. It will have to be fully integrated into either the SDK or the node software directly.
4. An audit of the contracts will be required.
5. NMT proof verification and share parsing (but not Celestia tx parsing) is required, since the commitment is identical to the one in the PayForMessage tx. As such, a protobuf codec is not needed.

Pros

1. A majority of the of the code already exists. This will probably be the fastest option.
2. Potential for Cosmos branding and association.

Cons

1. Realistically, there is 0% chance of being able to upstream changes, barring us owning the canonical implementation of Gravity bridge. This is because there is no specification or reference implemention of the Gravity bridge protocol, so a dozen projects each have their own completely independent fork, with more popping up. This will have to be developed in isolation of the broader Cosmos ecosystem solely for our purposes.
2. Cost of verifying signatures for each message batch is non-trivial. Verifying 50 signatures would be ~200k gas, while simply posting them would be ~50k.
3. Requires validators to run a module that introduces a logic dependence on the EVM, and EIP-191. In addition, this will requires computational overhead in the form of each validator needing to run a full node for the EVM chain (or trust a centralized service provider to provide them confirmation of transaction inclusion and effect).
4. One of the key requirements for PoS is accountability: being able to identify which validators of a dishonest majority were in fact dishonest, and burning their stake with social coordination. Validators that submit a bad batch or validator set update to the EVM chain must be penalized, otherwise the bridge isn't making and honest-but-accountable-majority assumption (good), but an honest-and-unaccountable-majority assumption (bad). To that end, non-validator nodes must also be able to understand the EVM and EIP-191 in order to be able to understand that the validator submitted something they should not have, and penalize them.
5. A separate instance of the Gravity bridge module is required to handle each chain that is bridged to. This is not yet implemented properly, but even if it were, it would be onerous in a future where potentially many chains would leverage Celestia as a DA service.

EVM Light Client Bridge

The EVM light client bridge (this repo) is a Celestia light client written in Solidity. It accepts new blocks headers as they are in Celestia, and follows the chain of block headers under an honest majority assumption.

Method of Operation

The EVM light client bridge has two components: an on-chain component written in Solidity and an off-chain component (which we'll call the orchestrator), yet to be written.

The on-chain contract will accept new Celestia block headers in protobuf, along with addition metadata, such as the validator set (diff). It can then update its view of the validator set similar to the Gravity bridge. Again, the actual updating of the validator set is only required when a threshold of the voting power changes.

To parse the protobuf-encoded header, the following libraries implement deterministic protobuf:

1. https://github.com/celestiaorg/protobuf3-solidity
2. https://github.com/celestiaorg/protobuf3-solidity-lib

The final piece of the puzzle is that verification of the header and signatures must be done optimistically, by making the header chain an optimistic rollup. This is necessary since parsing protobuf every time would be too expensive. This would significantly reduce gas costs vs the Gravity bridge: verifying 50 signatures would be ~200k gas, while simply posting them would be ~50k. This similarly applies to processing messages. In other words, gas costs can be reduced by somewhere around a factor of 4 with an optimistic EVM light client bridge vs the Gravity bridge.

Required Changes

Significant changes are required.

1. Actually use protobuf to encoding/decode headers, etc. Library is implemented but is unused.
2. NMT proof verification, transaction and share parsing, etc.
3. Optimistic verification and rollbacks. This is one of the easier things to implement on this list, since the author is moderately familiar with how optimistic rollups work.
4. Off-chain orchestrator will have to be implemented, but significant portions of the Gravity bridge can be re-used.
5. Gas optimizations for the protobuf library.
6. An audit of the contracts will be required.

Pros

1. Since the contract accepts Celestia block headers directly, there is no need for validators to run any separate module. In addition, validators do not even need to run anything that connects to another chain in any ways. A single relayer can be tasked with posting all updates to the relevant EVM chain(s).
2. There is no logical dependence on the EVM or EIP-191. The bridge operates under an honest-but-accountable-majority assumption.
3. With optimistic verification, gas costs can be reduced significantly vs the Gravity bridge.
4. Potential to maintain potentially widely-used optimistic Tendermint light client bridge and reference implementation of deterministic protobuf codec Solidity library.

Cons

1. Large parts of the Solidity code are missing, including actually using the protobuf codec, NMT proof verification, transaction and share parsing, etc.
2. An orchestrator will have to be implemented to actually send transactions to Ethereum. The Gravity orchestrator can be re-used mostly.
3. With optimistic verification, a delay is required to finalize the submitted block headers. This may be unacceptable for zk rollup projects, but is fine for optimistic rollups.

Discussion

Don't forget to like, comment, and subscribe 👇

[liamsi]

An audit of the contracts will be required.

How come an audit is only necessary in the gravity bridge case but not for the EVM Light Client case?

I think we should expand more on the required changes so we can properly estimate the amount of time both would take. My intuition is that the gravity bridge changes are less involved and a matter of a few weeks max? While the evm client work is rather months not weeks? Is that about right?

But before that we should clarify if the lack of accountability a show-stopper for using the gravity bridge.

[adlerjohn]

How come an audit is only necessary in the gravity bridge case but not for the EVM Light Client case?

Oh, an audit would be necessary for both, I just forgot the add it for the latter.

is that the gravity bridge changes are less involved and a matter of a few weeks max?

About right, yes.

But before that we should clarify if the lack of accountability a show-stopper for using the gravity bridge.

It is not IMO.

[adlerjohn]

Decision is to modify the Gravity bridge as above.

[jtremback]

Numerous gas optimizations can and should be made. Just as an example of how immature the implementation is: when updating the validator set, the new validator set is provided. But this is actually not needed under an honest majority assumption; a commitment to the new validator set is sufficient.

@adlerjohn What's your recommendation here? checkpoint = hash(hash(_newValidators, _newPowers), _newValsetNonce, state_gravityId) to avoid passing the long _newValidators, _newPowers arrays as arguments?

[adlerjohn]

You can see the proposed changes here: https://github.com/celestiaorg/quantum-gravity-bridge/blob/efbf88d43dc9403e4d02f62bbf319788cf8ec10d/ethereum/solidity/contracts/QuantumGravityBridge.sol#L240-L289