Shard block staggering for faster block times

One of the more interesting ideas that has been floating around Ethereum research circles for a while is the idea of staggering shard blocks. That is, instead of all shard proposers publishing blocks around the same time, some would publish blocks earlier in a slot and some would publish later. Ideally, any timespan of a few hundred milliseconds would have some proposer scheduled to publish a shard block during that timespan.

This can be combined with rollups to create a system where the "de-facto" block time can be reduced to far less than a single slot, perhaps to as little as one second. The way that this would work is that rollups could accept data from multiple shards, and process the data in sequence. Although on-chain calculation of the state would not happen until a few slots in the future, clients can predict the state by seeing what shard blocks are expected to get in and calculating the state themselves.

​

https://preview.redd.it/6w1xtk0agto61.png?width=1259&format=png&auto=webp&s=c28faa07b443ccd3ff07ac352930bfbb125f8547

In this diagram, "X: A -> B" means "rollup X declares that its pre-state hash is A and it's making a transition with post-state hash B". Blocks in green are blocks that get processed; blocks in grey are blocks that do not get processed because their pre-state hash is incorrect (eg. the A -> C block is incorrect because at that point the state hash had already changed to B). As mentioned above, this can all be computed on-chain retroactively, so there is no need for the chain itself to have sub-slot synchrony, but clients who are seeing shard blocks come in in real time can pre-compute what the final state will be.

There are two main challenge points:

1. How do we incentivize shard proposers to actually publish their shard proposals on time? This is tricky; there are many incentives driving shard proposers to publish earlier or later, and while we know that the optimal time to make a shard proposal is during that slot, it's harder to incentivize publication times on a more fine-grained basis. Options include (i) VDFs and (ii) adding rewards for both includer and includee if a shard block includes a hash of a shard block of an earlier shard, creating some incentive for publishing on schedule
2. How do we deal with missing proposers? If a proposer does not publish their shard block, then it would be uncertain until the end of the slot whether or not they will appear late and have a rollup batch that overrides earlier-seen rollup batches that are in sequentially later shards. If a rollup accepts data from N shards, and portion p of validators are offline, then there is a chance of ~p*N that users' experienced latency will increase from 12/N seconds to the entire rest of the slot (on average, 6 seconds, in the worst case, 12 seconds). One option is a fork choice rule mechanism: within each slot, choose the longest chain and not the sequentially earliest chain. However, this has other risks.

If we solve these challenges, however, then users of rollups on Ethereum could experience block times that are competitive with more centralized chains!