Minimal Slashing Conditions. Last week Yoichi released a blog post… | by Vitalik Buterin

Note that plausible liveness is not the same thing as actual liveness; plausible liveness means that we theoretically can always finalize something, but it could always be the case that we just repeatedly get unlucky and never end up finalizing anything. To solve this problem, we need to come up with a proposal mechanism, and make sure that the proposal mechanism has the property that it actually does help us achieve liveness.

A proposal mechanism is a mechanism that proposes hashes, which the rest of the machinery with PREPARE and COMMIT messages then tries to finalize. The mechanism may well be faulty at times; it’s the job of the slashing conditions to ensure that even if the proposal mechanism is faulty, there are no safety failures and the protocol can finalize something once the proposal mechanism stops being faulty.

In many traditional Byzantine-fault-tolerant consensus algorithms, the proposal mechanism and the rest of the algorithm are closely tied together; in PBFT, every view (roughly equivalent to an epoch) is assigned a single validator, and that validator is free to propose whatever they want. The validator may misbehave by proposing nothing, proposing invalid hashes or proposing multiple hashes, but the other parts of the PBFT machinery ensure that such actions are not fatal, and the algorithm eventually switches over to the next epoch. Here, we can actually combine our slashing conditions with many different kinds of proposal mechanisms, as long as they satisfy a few conditions.

First of all, the proposal mechanism must propose one hash per epoch, and it must be a valid hash (validity conditions can be very complex; in Ethereum’s case it involves executing and verifying the execution of the entire Ethereum state transition function, as well as verifying data availability).

Second, the hashes must form a chain; that is, a hash submitted for epoch N must have a parent that was submitted for epoch N-1, a 2nd degree ancestor that was submitted for epoch N-2, etc.

Third, the hashes must be hashes that the slashing conditions do not prevent validators from finalizing. This is more subtle. Consider a situation where, in epoch 0 the proposal mechanism proposes a hash HASH0, then in epoch 1 the proposal mechanism proposes a hash HASH1 (a direct child of HASH0) and for whatever reason neither of these hashes reach enough prepares to get any commits. Then, the proposal mechanism (because of some temporary fault) proposes another hash HASH0' for epoch 0, and this gets 2/3 prepares and 1/2 commits.

Now, the proposal mechanism has two choices. One possibility is that it could propose HASH2(a direct child of HASH1), then HASH3 (a direct child of HASH2), and so on. However, the slashing conditions ensure that none of these hashes could get committed without 1/6 of validators being slashed. The other, and correct, possibility is that it should propose HASH1' (a direct child of HASH0'), with the expectation that that hash may never get finalized because perhaps its competitor HASH1 already got more than 1/3 prepares and so HASH1' can’t get the 2/3 that it needs, and then propose HASH2'(a direct child of HASH1'). HASH2' can get committed, and the mechanism can then continue proposing new hashes, each a child of the previous.

One immediate thought that some might have is: can we make a traditional proof-of-work blockchain, using the longest chain rule, be the proposal mechanism? Every 100th block could be a kind of checkpoint, where the hash of block N * 100 becomes a proposal for epoch N. But this is not guaranteed to work by itself, because in the situation above the proposal mechanism would try to propose HASH2 and not HASH1' , and so it would never end up finalizing any hashes (it’s not quite what we call getting “stuck”, as getting out of this situation does not require anyone to get slashed, but it does require getting the miners to collude to mine on the chain containing HASH0' even though the chain containing HASH1 is “longer” in the PoW sense). However, what we can do is use a traditional proof of work blockchain with a modified fork choice rule.

A fork choice rule is a function, evaluated by the client, that takes as input the set of blocks and other messages that have been produced, and outputs to the client what the “canonical chain” is. “Longest valid chain wins” is a simple fork choice rule and works well for PoW; Zohar and Sompolinsky’s GHOST is a more complicated example. We can define a fork choice rule that allows a blockchain to serve as the proposal mechanism for a consensus algorithm, and have the above properties, as follows:

1. Start off with HEAD being the genesis.
2. Find the valid descendant of HEAD that has 2/3 prepares and the largest number of commits
3. Set HEAD to equal that descendant and go back to step 2.
4. When step 2 can no longer find a descendant with 2/3 prepares and any commits, use the blockchain’s underlying fork choice rule (longest-chain, GHOST, whatever) to find the tip.

Note that in our example above, this would end up favoring HASH0' over HASH1 , so it has the right desired behavior. Note also that if there is a finalized chain, it always selects the finalized chain.