Casper FFG with one message type, and simpler fork choice rule


#22

In the dynamic validator setting, when can the validator set change?

Currently, I’m verifying a version where validator sets can change between a finalized block and its finalizing child.


#23

The validator set increments between a checkpoint C and its child if, in the context of the child, the parent of C was finalized by a supermajority link between the parent of C and C.


#24

“in the context of the child” - the evidence that the finalization occurred was included in the blockchain between C and the child.


#25

Your description involves: a parent of C, C and C’s child.

Here “parent” and “child” are about supermajority links, not about previous block links, I guess.


#26

Between the parent of C and C, since the finalization occurs, they are connected by both a supermajority link and a previous-block link. I think I got it.


#27

Maybe we need to consider if votes have hit the Casper contract on each checkpoint.

For the purpose of accountable safety, I can just say, after a checkpoint is finalized by a child C, justification links sourcing C might increment the validator sets.


#28

Here “parent” and “child” are about supermajority links, not about previous block links, I guess.

They are about checkpoint links.

I can just say, after a checkpoint is finalized by a child C, justification links sourcing C might increment the validator sets.

Yes. That sounds right.


#29

Then I was mistaken. Now it sounds like this: when a block is produced with its previous block being a finalizing child, the validator sets of the new block is already incremented. Of course, all this happens in a view containing enough votes for the finalization. For now I focus on a single view, and prove that fork implies enough slashing.


#30

when a block is produced with its previous block being a finalizing child, the validator sets of the new block is already incremented

s/block/checkpoint/g, but looks correct to me.


#31

Let’s consider checkpoints A (at epoch e), B (at eoch e + 1) and C (at epoch e + 10). Let’s say there are supermajority votes A->B, B->C and A->C. Let’s say A does not finalize any checkpoint at epoch e - 1.

With these votes, B finalizes A. So C has new validator sets.

Now which one sounds correct?

i) votes that do not originate from a finalizing child can only connect checkpoints with the same validator sets, so a supermajority vote A->C is impossible.
ii) votes can connect checkpoints with different validator sets, not dependent on any other votes.
iii) votes A->C are ignored until the finalizing situation involving B is recognized.

EDIT: changed i) a bit.


#32

I’d say a supermajority link A->C can happen, but it must be carried out by the new validator set, not the old one. That is, it’s the dynasty of the target, not of the source, that matters.

If that causes problems, then of course the only approach would be that for any descendants of B, only supermajority votes emanating from B are allowed.


#33

Here, who should be slashed, or what kind of rules are missing? Checkpoints at the same height in the picture are at the same epoch.


#34

It’s not possible for two distinct child validator sets Z and Z’ to appear that way. This is because during dynasty n, dynasty n+1 is already picked, so both children would have to be Z. Then the (Z, Y) line on the left and the (W, Z) on the right would conflict, leading to Z getting slashed.


#35

That seems to work. I’ll associate a chosen next validator set in each checkpoint.


#36

A slightly modified example suggests that the validator sets need to be incremented whenever they can. Otherwise, stale validator sets can do bad:


#37

Lets consider a hypothetical situation where there is a network split for one hour and there is a temporary fork into two equal size independent networks. In each of these networks validators will do voting for competing checkpoints. None of these checkpoints will be justified, since there will be not enough voting power for a supermajority vote.

Then after the network is fully connected back again, validators will have no way to revoke the votes. So there will be a large gap of one hour with no supermajority links, and the easiest way to bridge this gap would be to form a very long supermajority link that goes over the gap.

I am a bit confused on how this link would be formed. After the network is back fully connected, the validators need to go way back in time to one of the last justified checkpoints before the network split, and vote for a link that crosses the gap. It is not clear to me how this algorithm would work exactly, because, the validators do not per se know if there was a network split, and that the network is back again. The target of the gap-crossing supermajority link would have to be after the split, and since validators do not know when did the split end, they could only try randomly, which seems like a lot of chaos to me.

During the split, the validators would presumably keep trying, so after the network is reconnected there would be lots of competing minority links that have no chance to become supermajority links and originate from the same justified checkpoint that was justified just before the split.

Note that PoW handles this situation gracefully - after the network is back to normal, the trees are merged, and the strongest wins.


#38

Suppose you have a checkpoint C, which is the last justified checkpoint. Then, there is a split, and there are children D1, D2 of C, then children E1 of D1 and E2 of D2. D1, D2, E1, E2 all get <50% votes on them so none get finalized. Then the spit resolves. Suppose F1 (child of E1) appears first. Then, it will be possible to make a vote with source C and target F1, and all validators will by default try to do this. This allows F1 to become justified, and then possibly finalized in the next epoch.


#40

Vitalik - thank you, understood :slight_smile:

'Now, finalization has one additional condition—c is finalized only if the votes for the supermajority link c → c
, as well as all of the supermajority links recursively justifying c, are included in the block chain before the child of c"

Since votes are stored in blockchain blocks, and since blocks is formed and suggested by PoW miners, PoW miners will have authority to include particular votes in a block, and potentially delay other votes.

It seems that in this case PoW miners will have significant power over validators. In particular, if validators are penalized for voting late, and incentivized for voting early, PoW miners could censor out votes of some validators and speed up votes of other validators. If a PoW miner is a validator, she will make sure her votes are given a preferential treatment. So one may end up having situation, where large PoW miner pools will constitute the majority of validators, since they will be able to tweak the system their way.

I hope I understood the whitepaper correctly, sorry for a possible confusion :slight_smile:


#41

Who should be slashed here for what reason?

The problem is the ambiguity whether or not “Block B” is a finalizing child. Depending on this, the further history diverges.


#42

So first of all, the diagram as drawn cannot work, because you have two supermajority links both containing X that go to block B, which would get slashed under NO_DBL_VOTE. However, what you can have is, if you remove the arrow from B’s grandparent to B, then the supermajority link between B and B’s parent would get detected by B’s direct left child, but not B’s direct right child. Then, the right child has validator sets XY and the left child is still at XX, and that scenario can happen.

I believe the solution to this is that if you have a supermajority link that spans two dynasties, then it’s the dynasty of the source, not the target, that determines which validators need to form the link. In that case, because the left child and right child still overlap with X, and so the next finalizing link on the left and right branches will both have to contain X, so X would get slashed.