As-fast-as-possible shard chains with notarization

Sharding
1

The following is an example for a structure that could be used to enable fast shard chain collations.

Background:

  • Proof of Activity: hybrid proof of work and proof of stake where for a block to be valid to build on top of, >=M out of a randomly selected N PoS validators need to vote on it.
  • Sequential proof of work, specifically this latest protocol by Bram Cohen

Consider a PoA-like model where a collation can be made by a proposer, and then for it to be eligible for the next proposer to build on top of, the collation needs to be approved by at least 4 of a random sample of 7 notaries. The randomness is sourced from (i) a recent main chain block hash, and (ii) a hash preimage revealed by the proposer. For any collation, there is an infinite sequence of proposers that can make collations on top of it; that is, for every integer x >= 0, there is a proposer P[x]. For a proposal by proposer P[x] to be valid, it must contain sequential proof of work with difficulty factor D * x; D is adjusted via an on-chain game, targeting toward five seconds.

The intention is that collations on shards would normally come as fast as network latency, in a graph like this:

%5Bcollation%5D%20%3C-%20%5Bnotarization%5D%2C%5Bcollation%5D%20%3C-%20%5Bnotarization%20%5D%2C%5Bcollation%5D%20%3C-%20%5Bnotarization%20%20%5D%2C%5Bcollation%5D%20%3C-%20%5Bnotarization%20%20%20%5D%2C%5Bnotarization%5D%20%3C-%20%5Bcollation%20%5D%2C%5Bnotarization%20%5D%20%3C-%20%5Bcollation%20%5D%2C%5Bnotarization%20%20%5D%20%3C-%20%5Bcollation%20%5D%2C%5Bnotarization%20%20%20%5D%20%3C-%20%5Bcollation%20%5D%2C%5Bcollation%20%5D%20%3C-%20%5B%20notarization%5D%2C%5Bcollation%20%5D%20%3C-%20%5B%20notarization%20%5D%2C%5Bcollation%20%5D%20%3C-%20%5B%20notarization%20%20%5D%2C%5Bcollation%20%5D%20%3C-%20%5B%20notarization%20%20%20%5D%2C%5B%20notarization%5D%20%3C-%20%5Bcollation%20%20%5D%2C%5B%20notarization%20%5D%20%3C-%20%5Bcollation%20%20%5D%2C%5B%20notarization%20%20%5D%20%3C-%20%5Bcollation%20%20%5D%2C%5B%20notarization%20%20%20%5D%20%3C-%20%5Bcollation%20%20%5D561×788

And if at any point proposer 0 for the next collation is missing, then the chain would stop for ~5 seconds, at which point proposer 1 would be able to make a collation.

The notarizations would serve three purposes:

  • Directly notarizing the collations they are building on top of
  • Being a de-facto committee approving the shard chain (the main chain meta-committee would listen to the longest chain in this mechanism)
  • Being Casper votes in the main-chain Casper FFG cycle
3 Likes
2

Interesting! I read up to p. 12 of the first paper, it has interesting implications for incentivization, e.g. with EIP-908. One question that naturally arises is how to get fast shard chain collations in the context of full PoS with Casper CBC. You need another randomness source.