Byzantine Fault Tolerance - NEO Consensus Mechanism Simplified

The Byzantine Generals' Problem

On July 5th 1982, Leslie Lamport (initial LaTeX developer, Microsoft Researcher and winner of the 2013 Turing Award), Robert Shostak and Marshall Pease published a paper named The Byzantine Generals' Problem.

The group devised a thought experiment for an abstract agreement problem.

They imagined that several divisions of the Byzantine army are camped outside an enemy city, each division commanded by its own general. The generals can communicate with one another only by messenger. After observing the enemy, they must decide upon a common plan of action.

In its simplest form, the generals must only decide whether to attack or retreat. Some generals may prefer to attack, while others prefer to retreat. The important thing is that every general agrees on a common decision, for a half hearted attack by a few generals would be worse than a coordinated attack or a coordinated retreat.

Since it's impossible to know which generals are traitors trying to prevent the loyal generals from reaching agreement, the generals must have an algorithm to guarantee that all loyal generals decide upon the same plan of action and that a small number of traitors cannot cause the loyal generals to adopt a bad plan.

The Traitorous General
If nine generals are voting, four of whom support attacking while four others are in favor of retreat, the ninth general (traitorous general) may send a vote of retreat to those generals in favor of retreat, and a vote of attack to the rest. Those who received a retreat vote from the ninth general will retreat, while the rest will attack.

The Traitorous Messenger
To make matters worse, the generals are physically separated and have to send their votes via messengers who may fail to deliver votes or may forge false votes (traitorous messenger).

What is Byzantine Failure?
The typical mapping of this story onto computer systems is that the computers are the generals and their digital communication system links are the messengers.

Simply put, a Byzantine Fault is a fault that presents different symptoms to different observers. Similarly, a Byzantine Failure is the loss of a system component due to a Byzantine Fault in a distributed system that requires consensus.

So it stands to reason that the objective of a Byzantine Fault Tolerant system is to be able to defend against Byzantine failures.

A correctly implemented Byzantine Fault Tolerant system should be able to still provide service, assuming that the majority of the components are still healthy.

Achieving Byzantine Fault Tolerance
Several system architectures were designed that implement Byzantine Fault Tolerance. Implementations are very specific to their use case. Nonetheless, there are 2 prominent solutions that these systems may end up implementing:

Unforgeable message signatures. This may be achieved by using Public-Key Cryptography.

Atomic Broadcasts. If the message system is such that the command is transmitted
simultaneously to all participants, then A cannot send a different message to C and B.

These solutions are not mutually exclusive, so systems that need to be highly byzantine fault tolerant usually end up implementing a variation which includes both.