Multi-votes for long forks

[rphmeier]

GRANDPA currently has difficulties with dealing with large forks because all vote-blocks have to be seen. That would mean that the underlying node might have to synchronize two long forks, each of millions of blocks in the case of a long network partition.

The way it works is that if I have a fork of length 1000, where the blocks in that fork are given by F(number), I cast a vote with targets at F(1000), F(500), F(250), F(125), F(64),... basically just bisecting recursively until we reach some bottom boundary (probably around 32).

When we calculate the GHOST based on votes, we just use the earliest block possible out of all the votes, and don't synchronize to the fork further than we have to. This ensures that all nodes only have to sync to the longest fork. It makes vote size log2(n) in the length of the unfinalized chain being voted on.

If nodes cast these kinds of multi-votes where they actually are including blocks from different forks, that's an equivocation, but our equivocation-counting rules make it so this doesn't change the GHOST-ancestor.

There are some difficulties in proving these kinds of equivocations but we think it's possible without too much effort. The idea in principle is that if there is a long network split then sum(len(fork_a), len(fork_b), ..., len(fork_n)) <= len(hypothetical_unsplit_chain), so it's not actually "bloaty" to include all chains' headers on the "winning" fork if you look at block in space/time as opposed to space/block.

[rphmeier]

Main caveat is that block production systems might change block authors before finality, and probably only to sets which are completely online on that fork. So even though we can assume initially that the sum of the fork growth rates is ~1, eventually the sum of those rates will approach n_forks.