Why does simple 3-way majority voting not solve Byzantine faults?

user_3943173 0
Viewed 506

I have been reading many papers recently about Byzantine fault tolerance. There is a common proof that 3m+1 computers are needed to handle m Byzantine faults. The general proof goes something like this:

There are three "generals": A, B, and C. Suppose the generals communicate like this, where C is a "traitor":

A --> B "Attack", A --> C "Attack"
B --> A "Attack", B --> C "Attack"
C --> A "Attack", C --> B "Retreat"

A receives "Attack" from both sources, and will attack.
B receives "Attack" from A but "Retreat" from C and doesn't know what to do.
C is a traitor, so his action could be anything.

Therefore, we can't guarantee that a majority of the actors will reach consensus.

I sort of understand that proof, but it seems to miss a major point. Don't A, B, and C also do their own internal calculation of what to do? Since A & B are the "loyal" generals here, it would seem that the "correct" action is to attack. Isn't B allowed to factor in his own calculation in deciding what to do? In that case, he could easily break the tie between the conflicting A&C inputs and decide to attack. Then, both A & B attack, and we solve the problem. Is this a different problem than the classic Byzantine Generals problem?

multiple-processes distributed-system fault-tolerance distributed-computing
3 Answers

It is common to assume that loyal generals will give you the same answer given the same question. I.e., that A and B will both return either "attack" or "retreat". But that's not the case on BFT scenarios. On a BFT, each loyal general is seeing a different part of the problem and thus can give a different answer. So, a loyal general can say "attack" while another loyal can say "retreat".

A good use case is the altitude sensors of an airplane. Each one can give you a different answer because they "see" different data (they are all located on different places, being influenced by different factors).

To quote the original paper (Lamport, 1982):

The use of majority voting to achieve reliability is based upon the assumption that all the nonfaulty processors will produce the same output. This is true so long as they all use the same input. However, any single input datum comes from a single physical component -- for example, from some other circuit in the reliable computer, or from some radar site in the missile defense system -- and a malfunctioning component can give different values to different processors.

A voting system doesn't work here because a faulty component can trick the loyal generals by sending conflicting information to them. In other words, C (malice) can send "attack" to B and "retreat" to A.

Let's say B (loyal) says "retreat" (everything else is the same):

A --> B "Attack",  A --> C "Attack"
B --> A "Retreat", B --> C "Retreat"
C --> A "Attack",  C --> B "Retreat"

In this example, they shouldn't do anything (because they disagree), but A will attack and B will retreat. The honest nodes think they reached agreement, but they didn't. In this case, the traitor C was sucessfuly able to trick the honests A and B generals.

On a side note, if you are in a scenario where the honest components are expected to give you the same answer, then a voting system can be used (as Lamport himself suggests in his paper). For example, you can use it on a RAID system, where each node has the same data - all you need to do is to use what the majority returns as the actual data.

user_17729900
Related