Whether or not an algo is fork-free or not is a bit of a red herring, because it all depends on whether or not clients listen to partial confirmations. For example, in PBFT, you can have a client with a rule like “if piece of data X has 10 more prepares than any conflicting piece of data, then I will show it as partially confirmed”; this then makes PBFT forkful. In Casper FFG, you can have a client that refuses to show any blocks until they are finalized, and this makes Casper FFG fork-free. In an important philosophical sense, any consensus algorithm where you can make intelligent guesses about what data will be finalized before finality technically happens is forkful; it’s just a question of whether or not clients show the forkfulness. And you can probably prove that the only non-fully-synchronous consensus algo that doesn’t have that property is a dictator.
Now that we have that established, the next step is to point out that a chain-based data structure is really convenient, for a few reasons:
- It allows us to merge different stages of confirmation for different pieces of data - for example, in Casper FFG, a vote for epoch N corresponds to a PBFT prepare for epoch N and a PBFT commit for epoch N-1. This double-duty reduces concrete finality latency by ~17% with no tradeoffs (as an average transaction needs to wait for 2.5 instead of 3 messaging rounds to finalize). In PoW, block N is an Mth confirmation for block N-M, for all M <= N; if this massive multi-duty function of blocks did not exist, every new PoW would have to separately mention what value it’s voting for in every previous height.
- It allows us to merge the concept of leader election rounds (PBFT “views”) and transaction sequencing rounds (PBFT “sequence numbers”).
- It allows us to merge proposals and prepare/commit messages, reducing overhead further.
I actually believe that a truly optimal version of Casper FFG could reduce finality latency by ~20% further with no tradeoffs except for algorithmic complexity, by taking full advantage of the fact that a reference to a block is also a reference to all of its ancestors. Casper CBC should be able to make this optimization and achieve total optimality in even its current form.