We have a mathematical proof that to tolerate
n malicious nodes, you need
2n + 1 good nodes. The full proof is found in G. Bracha and T. Rabin, Optimal Asynchronous Byzantine Agreement, TR#92-15, Computer Science Department, Hebrew University. It's also well known in the industry. It is not possible for an asynchronous system to provide both safety (the guarantee that all non-malicious nodes will eventually agree on what progress was made) and liveness (the ability to continue to make forward progress) with more than this number of malicious failures.
You can trivially ensure safety by simply making no forward progress at all. And you can trivially make forward progress unsafely by just letting each node do whatever they want. Neither of these modes of operation are useful.
Let's take a step back to make this answer more helpful:
Why do you need a distributed agreement algorithm at all? Well, you need one in cases where there is more than one way a system could validly make forward progress and you need all the participants in the system to agree on which one of them.
Consider a simple example: I have $10 in the bank, and I write two $10 checks, one to Alice and one to Bob. Either one alone is valid, but we can't let them both go through.
If we had a central authority, they could just clear whichever one they saw first. But what if we don't want a central authority or don't want a single point of failure? And what if we have potentially malicious participants?
Well, you could just sort the checks after representing them as binary data. But that's where the asynchronous component bites us. When do we sort them? Say I see both checks and sort them. How do I know that one second later I won't see a third check that sorts first? And maybe someone else already saw that one. Ouch!
So, we have the following requirements:
1) Our system is asynchronous.
2) Some participants may be malicious.
3) We want safety, that is, we do not want one honest participant honoring one check and one honest participant honoring the other.
4) We want liveness, that is, it's not fair just saying we never clear any checks. Sure, that's safe, but not useful. We want to be sure that we eventually agree on which checks to clear.
So, now the question arises -- how many dishonest partcipants can we tolerate in our asynchronous system and still guarantee both safety and liveness?
As a simple way to get the gist of the proof, though it is not rigorous:
Suppose we have
n nodes of which
h are honest and
d are dishonest. Obviously,
n = h + d. Now the system needs to come to consensus on which of two checks to clear.
Think about the case where all the honest nodes are evenly split about the two directions the system could make forward progress. The malicious nodes could tell all the honest nodes that they agree with them. That would give
h/2 + d nodes agreeing on each of two conflicting ways the system could make forward progress.
In this case, the honest nodes must not make forward progress or they will go in different directions, losing safety. Thus, the number of nodes required to agree before we can make forward progress must be greater than half the number of honest nodes plus the number of malicious nodes, or we lose safety.
If we call
t the threshold required to make forward progress, that gives us:
t > (h/2) + d. This is the requirement for safety.
But the malicious nodes could also fail to agree at all. So the number of nodes required to agree before we can make forward progress must be no more than the number of honest nodes or we lose liveness.
This gives us
t <= h. Or
h >= t. This is the condition for liveness.
Combining the two results, we get:
h >= t > (h/2) + d
h > (h/2) + d
(h/2) > d
d < (h/2)
Thus the number of faulty nodes we can tolerate is less than half the number of honest nodes. Thus we cannot tolerate 1/3 or more of the nodes being dishonest or we lose either safety or liveness.