Two minimal scenarios where equivocation harms progress

[cason]

Equivocation is probably the most powerful artifice that can be used by Byzantine validators to harm the protocol.

There are two issues, https://github.com/informalsystems/malachite/issues/309 and https://github.com/informalsystems/malachite/issues/103 , describing scenarios and implications. But I feel that is still relevant to fully describe two scenarios where equivocation from at most f validators can harm Tendermint's liveneess.

Model

First, two main assumptions:

• The proposer of the rounds described is correct, in the sense that it does not double-propose. When this happens, more and more complex scenarios become feasible, but lets assume that proposer equivocation is complex and hard to achieve.
• Validators keep a single vote per sender for each height, round, and round step. While keeping all received votes, like assumed in the pseudo-code, would solve the problem, this is undesirable as it constitutes an attack surface.

We consider a minimal set of four validators A, B, C, and D:

• A is an asynchronous validator. It is correct but slow. Therefore, we cannot rely on it to receive messages before the associated timeouts expire while we are not past GST. We should assume it is likely to prevote and precommit nil mostly;
• B is a Byzantine validator, it can do whatever it wants;
• C and D are correct and synchronous validators, we rely on them for progress.

Overview

1. We have a correct validator, either C or D, that proposes a value X
2. C and D receive X, validate it and issue a prevote for id(X) at round 0
3. A times out in the propose step and prevote for nil

So, the initial scenario, only considering correct validators, is the following:

(1) Prevotes(H, 0) = [nil, ?, X, X]

Notice that B ultimately defines the fate of this round of consensus. If it prevotes id(X), we have a polka for X, which is likely to be the decision value. If it prevotes any other value, including nil, the round is doomed, as we can only see precommits for nil. But since B is Byzantine, it can just do both, producing two follow-up scenarios:

(1.a) Prevotes(H, 0) = [nil, X, X, X]
(1.b) Prevotes(H, 0) = [nil, nil, X, X]

Scenario 1.a can lead to progress, i.e. the decision of X in the round, with the following scenario in the precommit step:

(2) Precommits(H, 0) = [nil, ?, X, X]

Notice that we are still assuming that validator A is slow and precommits nil. This can be caused because it timeouts while in scenario (1), i.e., it does not receive the prevote from B, or because it did not even receive the proposal for X.

It is simple to see that scenario 2 has the same problem as scenario 1: the success or not of the round depends on the vote of the Byzantine validator B. Which can equivocate or can just omit itself. This is the basis for the two described scenarios.

Precommit equivocation

In this scenario, B does not need to equivocate in the prevote step, it can just prevote for id(X) and we get to scenario 1.a, then to scenario 2. At this point, B can literally define who is going to decide X and who is not, as follows:

(2.a) Precommits(H, 0) = [nil, X, X, X]
(2.b) Precommits(H, 0) = [nil, nil, X, X]

The correct validators that see scenario 2.a will decide X and move to round (H+1, 0). The correct validators that see scenario 2.b, or after a timeout still have scenario 2, will move to the next round (H, 1).

The problem is when no enough validators move to round (H, 1), namely, less than f validators. In this case, they are stuck in that round, since they will never receive 2f + 1 vote messages. The same applies, of course, if less than f validators move to the next height, where they will be stuck until at least one more correct validator joins the first round of height H+1.

This scenario, although tricky, should be addressed by a synchronization protocol. Once a correct validator has moved to height H+1, all correct validators should eventually learn the decision value X of height H, plus a Commit certificate for that value.

Prevote Equivocation and Hidden Lock

In the second scenario, the Byzantine validator does not want any validator to decide X in height H. So we should consider the scenarios 2 and 2.b. All validators move to round (H, 1). The problem, however, is what is the state they bring for this round, in terms of the locked and valid value. The equivocation here therefore occurs on the prevote step.

Starting from scenario 1, the Byzantine validator can produce at different validators scenarios 1.a and 1.b. Scenario 1.a means that that validator has probably locked on X at round 0, or at least has set X as valid value at round 0. In scenario 1.b, there is no locked or valid value in any correct validator, namely, they can accept any proposed value.

No, lets assume that:

1. C has seen scenario 1.a and has locked on X, which is also its valid value
2. D has seen scenario 1.b and has no locked or valid value

C is the next proposer

In this case, C will re-propose X, as it is a valid value. It will send a Proposal(H, 1, X, 0), notice that vr == 0.

This scenario is covered by line 28 of the pseudo-code. Validator D, however, has seen scenario 1.b. So it does not know a Polka for X in round 0. Even though it eventually receive the second prevote from B, by assumption it is not considered.

As a result, C will prevote for id(X), while D will prevote for nil. Even if A prevotes for id(X) we are back to a scenario very similar to 1, when is the Byzantine validator B that will decide whether the round can succeed or not.

D is the next proposer

In this case, D does have any know valid value and will propose a new value, say Y.

This scenario is covered by line 22 of the pseudo-code. Validator C is locked on round 0 and value X != Y. Therefore it has to prevote nil, while D will prevote for id(Y). Validator A can prevote for nil or for id(Y). But even in the latter case, we have a scenario where is the Byzantine validator B they will decide whether the round can succeed or not.

Summary

In summary, we are stuck. The only two validators that are correct and synchronous (C and D) have conflicting states. One of them is locked, while the other is not. One of them will always propose a value that the other will reject.

To form a prevote quorum, a Polka, we need 3 prevotes for the same value ID. Having a good vote from slow validator A is not enough. We need to rely on the votes of the Byzantine validator B, that can block the system forever.

How do we solve this problem? In the pseudo-code this is not a problem. Once we get past GST, every correct validator (A and D) will eventually see that there was a polka for X at round 0. But for that, specially in the case of validator D, it needs to "replace" the prevote from B at round 0 from the value it has stored, nil, by the value that validator C has seen, id(X).

Without the ability to override the existing vote set upon seeing a Polka certificate, we cannot solve this scenario.

[cason]

Ah, if you want to make it even funnier, starting from D is the next proposer section, consider the following:

A prevotes id(Y), D prevotes id(Y), and the Byzantine validator B prevotes id(Y) too but does not send this prevote to C. It instead send a nil prevote to C.

This means that D, and potentially also A, will lock on Y at round r > 0 while C will still be locked on X and round 0.

[josef-widder]

Thanks for sharing that. I think from the consensus state machine the situation is clear in this write-up. Could you please also say a bit about the attack surface of accepting all messages from Byzantine nodes?

[cason]

Ok, I will detail a little more the actually attack surface, thanks. :)