Handling forks and building canonical chain in EthereumLightClient

[gupadhyaya]

Currently EthereumLightClient simply accepts all valid forks. It needs to maintain the forks and make a fork-choice rule to accept only longest chain and maintain a canonical chain from which the proofs are verified.

[brucdarc]

I've done some thinking about how this could be implemented, and I'll share a design I came up with.

All heads of current forks are stored in a mapping. When a new block comes in, if its previous block is not a head of a current fork, that block is added to current forks.

There is a function callable by anyone where if a certain head of a current fork is more than say 100 (or any value) less than the highest block height fork head, that fork head can be removed from the mapping

Also the current highest block height fork head is stored

Whenever a block is added to the current fork heads mapping, a check is done to see if its height is greater than the current highest fork head. If so it replaces the current highest fork head.

We can also determine how verified block are by how far they are from the current fork head's block height.

[brucdarc]

The work of determining which fork headers can be removed because they are more than 100 behind the greatest can be offloaded to off chain programs to save gas. The contract just requires that the ones to remove are greater than 100, it does not have to find them. Task should be pretty trivial from an off chain program that does not need to pay gas, and also any address can be allowed to call this function

[brucdarc]

Also this operation of trimming old forks can use the solidity delete to refund gas, which if the function is cheap enough to net the user gas could be an incentive for people to just do this. This would require more testing of how the gas numbers actually work out, since making a contract call is a min of 21000 gas. Maybe a bulk remove old head function would be good, but it would have to be build into the bridge contract. Then in theory though I think a user doing the task of cleaning old headers should net positive gas given that they remove enough old fork heads

[brucdarc]

Although I am now realizing that since ELC runs on harmony, the gas is way less important. I think the general concept still stands though

[gupadhyaya]

great points. could you also refer to near's rainbow bridge approach: https://github.com/aurora-is-near/rainbow-bridge/blob/master/contracts/near/eth-client/src/lib.rs?

[brucdarc]

So one thing I've found already, it seems they keep a "best chain" and best header hash sort of similar to this.

One important difference here though is that they seem to be using total difficulty instead of block height, which seems like a better metric for canonical chain

[brucdarc]

Also the rainbow bridge implementation does not track all ongoing forks directly, it instead loops and completely replaces a data structure containing all blocks header hashes in the canonical chain. We could store the headers to all currently existing forks if we think there might be some benefit to it, or just store the canonical header hash. It would put a bit more of a storage burden on the contract to keep track of all forks, but it is entirely possible if we think having that information on chain would be beneficial.

And since I am assuming we would like fast lookup to determine if a block is in the canonical chain, we will need to retrace every time a new fork overtakes the canonical chain.

[brucdarc]

https://eth2.incessant.ink/zh-cn/book/03__eth1/06__fork-choice-rule.html. Eth currently uses total difficulty as the fork choice rule, so that is the correct implementation