Currently, when referring to the QGB repo from a Go project, it gets the v1.0.3 which is too old. We should create a new tag v1.1.0 which refers to the latest master.

Summary

#4 proposed including a tuple root. An alternative would simple be including the data root. Investigate and document final decision.

Problem Definition

Proposal

For Admin Use

• [ ] Not duplicate issue
• [ ] Appropriate labels applied
• [ ] Appropriate contributors tagged
• [ ] Contributor assigned/self-assigned

Fixes #104

Technically this might not even be necessary from a functional point of view; it's simply adding a constructor field for the initial height, which will be overwritten on the first update anyways. The nonce check was already <= instead of == +1.

Documentation was updated though to make it clearer.

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 👇

Since we're a one way bridge, we might be able to remove the BRIDGE_ID that is normally used to prevent replay attacks. We should further investigate the consequences of removing it.

Adds a publicly callable interface for downstream contracts to query the QGB contract for attestations.

Depends on #32

Tests will be done in a future PR.

Currently, the QGB contract, when submitting valsets, creates the following checkpoint: https://github.com/celestiaorg/quantum-gravity-bridge/blob/210a1fbb9a9fc3165a038d8cedfba177c67a5726/src/QuantumGravityBridge.sol#L275

The issue, is that the checkpoint is calculated using the currentNonce which is the latest eventNonce, and will never match the submitted one.

Example: We relay the following attestations:

• Nonce 1 : Valset 1
• Nonce 2 : DC
• Nonce 3 : DC
• Nonce 4 : Valset 2

When submitting the Valset 1 with Nonce = 1, the checkpoint will be calculated using Nonce = 1. However, when submitting Valset 2 with Nonce = 4, the checkpoint, which the contract will check against, will be created using Nonce = 3, resulting in a wrong checkpoint.

The solution would be to keep a LastValsetNonce variable stored in the contract, so that when submitting the new checkpoint, it can be used to generate the validator set hash correctly.

@adlerjohn @evan-forbes

Main contract: https://github.com/celestiaorg/quantum-gravity-bridge/blob/adlerjohn/contract_mods/ethereum/solidity/contracts/QuantumGravityBridge.sol

Original main contract: https://github.com/celestiaorg/quantum-gravity-bridge/blob/b5ba246f23f89c43adf764e2e3f804b4a9f3beb0/solidity/contracts/Peggy.sol

Description

This is an attempt to fix: https://github.com/celestiaorg/quantum-gravity-bridge/pull/124/checks?check_run_id=7962233579

~~strict and commit_message aren't supported keys for actions.merge (ref https://docs.mergify.com/actions/merge/). It looks possible to use commit_message_template to achieve something similar to the previous commit_message config if desired.~~

When I regenerate the wrapper, it gives me different BINs. @adlerjohn please take a look when you have time. The compiler that I used is:

Version: 0.8.4+commit.c7e474f2.Linux.g++

#9 will mock what is sent to the contract. PayForMessage txs must be extracted from each Celestia block and replace the mock logic so that real data can be sent to the contract.

Currently, NMT implementation only verifies NMT proof for a single key: https://github.com/celestiaorg/quantum-gravity-bridge/blob/f38d30b67b8e0ee4df8819809946f4cc0dcada67/src/lib/tree/namespace/NamespaceMerkleTree.sol#L20-L30

We will need to add support for NMT multiproof to benefit from compact proofs, and be compatible with the NMT proofs generated on Celestia-app side.

Currently, the QGB smart contract only provides a verification method to verify a data root inclusion proof in a data root tuple root: https://github.com/celestiaorg/quantum-gravity-bridge/blob/f38d30b67b8e0ee4df8819809946f4cc0dcada67/src/QuantumGravityBridge.sol#L373-L391

To verify that a share was posted on Celestia on the EVM chain, we will need extra methods to verify the following:

• [ ] Shares NMT inclusion proof to rows
• [ ] Rows merkle proof to data root

As per the discussion in https://github.com/celestiaorg/quantum-gravity-bridge/pull/106#issuecomment-1087539242 , we need to add the following workflow to require PRs to have a minimum of 1 label.

The QGB relies on validators signing commitments to erasure block data over a range of blocks. For the MVP, we are using an identical block range for each DataCommitment. This range of blocks will likely need to be significantly more dynamic to accommodate different rollups.

• How can we do this in an efficient way?
• Does it matter if ranges overlap?
• How will this affect slashing?
• Will the rollup batch producers need to ask the celestia validators to sign commitments over custom ranges? If so, what should that look like?
• Do any changes need to be made to the contracts?