4

I've noticed many protocols using validators like Casper, Tendermint, EOS require 2/3 of nodes (weighted) as the quorum requirement.

What's the reasoning for using this seemingly arbitrary number? Why not 51%?

3
  • Actually, not an arbitrary number, but its based on the 33% (1/3) theory of Byzantine fault tolerance.
    – shonjs
    Feb 11, 2018 at 10:35
  • 1
    More information here
    – shonjs
    Feb 11, 2018 at 10:50
  • 1
    @1sn0s: +1 - definitely worth adding as a proper answer :-) Feb 21, 2018 at 20:46

2 Answers 2

3

Actually, not an arbitrary number, but its based on the 33% (1/3) theory of Byzantine fault tolerance. More information and better context here

Suppose we have a traitorous Commander A, and two Lieutenants, B and C: when A tells B to attack and C to retreat, and B and C send messages to each other, forwarding A's message, neither B nor C can figure out who is the traitor, since it is not necessarily A—another Lieutenant could have forged the message purportedly from A. It can be shown that if n is the number of generals in total, and t is the number of traitors in that n, then there are solutions to the problem only when n > 3t and the communication is synchronous (bounded delay). More about Byzantine fault tolerance.

2

In Byzantine Fault Tolerance, we have two things:

  • We have n parties out of which <= f can be faulty (Byzantine). We need that n > 3f <=> n >= 3f + 1. For where this comes from, see this paper or this Medium post.
  • To reach a quorum ("majority") we need >= 2f+1 votes.
    • My simplified intuition for where this comes from is the following example: f votes are malicious, f+1 honest votes for output "0" and f honest votes for output "1" (so 3f+1 in total). The malicious parties send "0" to all the honest parties that are voting "0" and "1" to all the honest parties that are voting "1". If an honest party would terminate having seen only <= 2f votes, some parties might wrongly/prematurely terminate with output "1".
    • See also the Practical Byzantine Fault Tolerance paper where the 2f+1 also shows up when waiting for messages.

Combining the two:

2*f + 1 = 2*((n-1)/3) + 1 = 2/3n - 2/3 + 1 = 2/3n + 1/3

Thus we need at least 2f + 1 ≈ 2/3n + 1 votes for a quorum. (Round up to +1 since a third of a vote doesn't work. Rounding down would not be enough.)

So to answer your question: the 2/3 comes from the 2f+1 and the n=3f+1. Simply having >n/2 (i.e. 51%) is not enough in the presence of Byzantine faults.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.