A general framework of overhead and finality time in sharding, and a proposal

[jamesray1]

Don’t read this comment! I need to read some of the linked to posts, recursively if need be. I’m mostly just summarizing/rehashing what you said for understanding.

@vbuterin

Collations get produced (via some mechanism)
Some set (“committee”) of MM randomly sampled notaries verifies the data availability of the collations, and somehow votes that the collations are available.

So without collators, having notaries and proposers instead, one way for these two to work in more detail is:

@vbuterin

First of all, let us switch from forking to a model where collation proposal and notarization are separate functions; that is, every period, a collation header gets proposed, but then a separate set of notaries engages in voting to finalize them. Collation proposers could, for instance, be randomly sampled from a set that exists within a particular shard, thereby allowing them to hold the state of that shard, and removing the need for collator-proposer games. Let us also switch from a forking-as-voting model to an explicit model: every period, kk notaries are selected per shard, and these notaries must attempt to download the last \frac{M}{k} collations and deliver a verdict on the availability of each through a bitfield (ie. a string like 11110111001111111011101). After a collation is created, after p periods, there would be p∗k votes on the collation, delivering evidence of partial confirmation. This allows us to move away from one unit of voting per period per shard, and instead opens up the full parameter space between k=1 (similar to the 1.1 forkful model) and k=M (a collation gets ratified within one round, and ratification is done before the next collation is created).

Notarizations can be cryptoeconomic: you get more rewards by voting 1 on more collations that ultimately get accepted, but if you vote for a collation you are responsible for providing any specific chunk of the collation body is challenged, and if you can’t do that you lose your deposit.

@vbuterin

Collation proposers could, for instance, be randomly sampled from a set that exists within a particular shard, thereby allowing them to hold the state of that shard, and removing the need for collator-proposer games.

Yes, this is something that occurred to me, I think I touched on it in the P1SS spec comments. it would be good to reduce complexity.

@vbuterin

deliver a verdict on the availability of each through a bitfield (ie. a string like 11110111001111111011101)

Then later you have:

@vbuterin

During the last period, the notary would submit a signature that contains that notary’s opinion on every collation within that range as a bitfield.

So it sounds like each bit in the bitfield represents a collation. It would be interesting to develop that, but it seems not too hard to implement.

@vbuterin

However, there is a clever way to improve security of this scheme against semi-adaptive adversaries: instead of checking availability vertically across a range of period numbers on one shard, notaries check diagonally, checking a collation from a different shard in each period. The randomness that determines which shard a notary checks during each period can be delayed until that period, achieving zero lookahead transparency, making the scheme secure under honest majority except for all but the most adaptive adversaries who can launch attacks on specific nodes within a single period.

To summarize, in this kind of diagonal scheme, a notary would be called upon during period p, and required to verify a collation from some shard during every period from p to p+\frac{M}{k}. During the last period, the notary would submit a signature that contains that notary’s opinion on every collation within that range as a bitfield.

Sounds good. It would add more complexity to implementation, e.g. the source of the randomness, notaries being registered in each shard, listening to the SMC during every period to see what shard they’re assigned to, downloading the collation for that period, somehow verifies the data availability e.g. with Reid Solomon codes, ‘submits a signature on the collation at the end of the lookahead periods that contains that notary’s opinion on every collation within that range as a bitfield’ (presumably this opinion could be a boolean where true = valid and available and false is otherwise).

Presumably multiple notaries are assigned to every shard in every period, so that there are multiple confirmations, where they then would randomly shuffle between all shards, and don’t need to store the state of any shard. They don’t need to store the state so you would not need to have a separate registry of notaries for each shard, but would still have that scheme for proposers, where proposers can store the state of the ones they’re registered in. Or perhaps you don’t need to have multiple notaries for each shard for each period, but you would increase the time to internal finality for votes to accumulate over a longer period before “the main chain validator verifies the votes, and may also verify a data availability proof”.

In the mean time with phase 1, it seems that we still need to have a collator-proposer game, or a viable model. (There’s a reasonable critique of the collator-proposer game here: Exploring the proposer/collator split - #21 by vbuterin) This model seemingly won’t work with phase 1 since we have no execution, so we can’t couple with the main chain, which does have execution; and more importantly because proposers need to know whether transactions are valid by executing them.