Safety Under Dynamic Validator Sets | by Vitalik Buterin

On Mar 4, 2017

Another immediate instinct that one might have is “in order to maintain continuity, we should wait for validator set A to finalize validator set B, and then let validator set B take the torch from there”. To see how this works, consider the following toy algorithm:

Every block must contain the hash of the validator set of the next block
For a block to be valid, it must point to a valid parent block, as well as proof (eg. a sufficient number of COMMITs with the same sequence number) that the parent block was finalized. That is, finality must happen for every block.

Note that here consensus happens between blocks, ie. there’s a pattern of “create block 1, finalize block 1, create block 2, finalize block 2 …”, unlike our other algorithms where new blocks are being produced even while consensus on older blocks may still be finishing. In order for there to be a fork in this scheme, there must be some initial block height at which the blocks diverged, and so we can use our proof of accountable safety to show that at least 1/3 of the validators at that block height can be slashed.

Graphical proof that if every block is finalized, and every block contains a commitment to the next validator set, then if two conflicting blocks are finalized that implies a conflict within a single validator set, which can then be used to slash offending validators.

However, if we try to apply this to the “interwoven consensus” model where proposing new blocks and finalizing existing blocks happen in parallel, as is the case with our latest versions of Casper, then there is a challenge. Because there is not a 100% probability that consensus will be achieved in any single epoch, we cannot simply allow a block in epoch N to determine the validator set for epoch N + 1; if epoch N ends up not finalizing, and there are two competing candidates for epoch N, then you run the risk of later finalizing two conflicting chains with disjoint validator sets.

Well how about we solve this problem by having epoch N * 50 determine the validator set for epoch (N + 1) * 50, and hoping that you always finalize at least one epoch every fifty. However, this also leads to a problem:

So if we want interwoven consensus, what do we do instead? First of all, note that the state transition function does have some partial knowledge about whether or not a given block was finalized: if a block was finalized, then the evidence can be submitted into the chain in time for the next block or it might not, but if a block was not finalized, then the evidence can definitely not be submitted. We can think of this as a “yes or maybe” oracle on finality.

Let’s take advantage of this. If the oracle says maybe, we don’t change the validator set; if it says yes, we do.

Unfortunately, things aren’t quite so simple.

The problem here is that we don’t immediately have consensus on whether or not there was consensus, and so one can make a child of a parent with two different validator sets.

Credit: Source link