The Byzantine Generals Problem, also called Byzantine Fault, is a condition of distributed computing systems, developed to describe a situation of consistency and integrity, in which, in order to avoid a catastrophic failure of the system, the actors must agree on a concerted strategy, but knowing that some of these actors might not be trustworthy.
In a Byzantine Failure, a component such as a server may appear to be failing and working inconsistently, but not detectable by detection systems, making it difficult for other components to declare that it has failed to exclude it from the network. Byzantine Fault Tolerance (BFT) is the resistance of a computer system to such conditions.
The Byzantine Generals Problem was posed by the American computer scientist Robert Shostak in the late 1970s, and then developed in 1982 in collaboration with Leslie Lamport and Marshall Pease at the scientific and technological research center SRI International.
The Statement of the Problem
The Generals of a Byzantine army surround an enemy city. They position themselves with their respective troops in the surroundings, at a certain distance from each other, and cannot decide whether to order an attack or a retreat. Coordination is necessary for the war plan, otherwise they are very likely to lose the battle.
High military officials suspect that there is at least one traitor among them, which makes it difficult to make a decision together.
A general could send a message to the others announcing that he is going to attack, when in fact he intends to order a withdrawal, and cause the rest to fail.
But how to agree?
The problem is to find an algorithm that guarantees that the loyal Generals reach an agreement, and are the coordinated majority.
It is shown that, using only messages, this problem is solvable if, and only if, more than two-thirds of the Generals are loyal. For example, the problem arises when a single traitor can confuse two loyal Generals out of a total of six, that is, half of the generals, explained the aforementioned authors in their study.
The solution to this simple expression is problematic, and to solve it, the researchers offered a series of equations and algorithms that are transmitted through a system of “inviolable” messages, that is, encrypted.
The Blockchain Byzantine Generals Problem
Flaws are virtually inevitable within any distributed computing system. Let’s say there is a power outage and nodes suddenly go offline, or there is a malicious actor who wants to cause damage to the system. Can the network continue to function normally and continue to support reliable communications? Or does the entire system suddenly stop working or become vulnerable to attack?
On a moderately secure network, something as simple as a few nodes going offline has no noticeable impact on the network. The ability to defend against these scenarios is known as Byzantine Fault Tolerance. Networks that can handle more Byzantine Faults are considered to have a higher tolerance, meaning they are more secure than those that cannot handle them.
The ledger is distributed on a blockchain network, with a number of computers (nodes) around the world, which are instantly updated with each block, so that each interested party can trust the transactions recorded on that network.
Thus, the idea is that each Byzantine General (each node) has the complete copy of the plans of each of his colleagues (the ledger in the blockchain), then there would be practically zero margin for Byzantine Faults, the product of betrayal.
When everyone agrees that they have the same result, then the nodes validate a block. Even if someone wanted to introduce wrong information —and this is where the Byzantine Generals Problem comes in— he will not be able to do it, because everyone has the same information, and considers it the truth, and that leads to consensus. This is a BFT system, and it is achieved with the consensus algorithm that runs in each of the nodes of the network that stores all the ledger information.
The typical consequence of a system that is not tolerant to the Byzantine Fault is a fork in the blockchain. If a system is fault tolerant, it means that despite the existence of faults (in this case malicious nodes) the success of the system will be possible, of course, as long as these faults are not “too many”.
Solving the Byzantine Generals Problem with Proof of Work and Proof of Stake
Proof of Work (PoW) pioneered blockchain technology, and Proof of Stake (PoS) is an alternative, post-creation consensus algorithm.
PoS was first implemented by PeerCoin and Nxt in 2012 and 2013, respectively, and aims to avoid some of the perceived weaknesses of PoW, most notably hardware cost and power consumption.
In the PoW protocol, new transactions and the issuance of cryptocurrencies are settled on the ledger through mining, where miners compete with computational power to forge each block.
On the other hand, in PoS, the validator nodes are chosen randomly, but with more “luck” for the nodes that have the greater amount of delegation assigned, and thus the pool operators compete to attract new delegators with their cryptocurrency funds, sharing with them the rewards of each forged block.
PoW generates an excessive incentive, in which the miners, the only participants in the consensus, take the issuance of the cryptocurrencies and the transaction fees of each block. They have the scheme “the winner takes all”.
Instead of expensive mining equipment, PoS validators don’t need anything more than a standard computer, an internet connection and keeping the delegation active with strategies.
Like PoW, PoS solves the Byzantine Generals Problem, though by different means. Tolerance to Byzantine Fault is determined in the algorithm.
PoS empowers the distributed and uncoordinated “Generals” (the producer nodes) to agree, based on the consensus algorithm, which for Cardano is Ouroboros, despite the fact that the communication is not instantaneous and potentially contradictory signals are sent:
- Generals become validators by depositing their goods.
- The preset algorithm selects a General to become a validator for the next block.
- The protocol then chooses another General to become validator, referencing the previous block to form a growing chain. As a result, it is clear that most of the Generals contribute to forging and validating the longest chain, and the densest in blocks.
- The Generals know that as fast as each block is created under the PoS consensus algorithm, after a period of time, they will be able to tell if enough Generals are working on the same chain.
This solves the Byzantine Generals Problem in a more efficient and environmentally friendly way, eradicating the high power and hardware costs associated with PoW. In doing so, it also removes the economies of scale that larger miners in PoW, concentrated in large mining farms, benefit from.
PoS gives all users the opportunity to receive a reward, which is proportional to their funds.
While PoW miners can dispose of mined cryptocurrencies immediately, for example to pay their high costs, PoS incentivizes validators to leave their funds at the node, for use in network consensus, and thus have a better chance of being elected as block producers. Moreover, keeping validation rewards is feasible, since they do not have to pay high node maintenance costs, as in PoW.
Not Everything is Positive in PoS
Although PoS is theoretically more democratic, since it gives all users the same opportunity to participate in the network consensus (directly or by delegating), and avoids the problems of economies of scale that PoW suffers, tends to create a certain concentration, where the big ones get bigger and the little ones get more and more diluted in the participation. This problem is known as Plutocracy, which is the rule of a minority with greater power. The wealthy have “better luck”.
As these large interests accumulate, they are likely to collude rather than compete.
This concentration of participation also means the formation of a scenario in which a 51% attack is possible, when the consensus is dominated by malicious actors. You can read my article on this topic, at the end (1).
For the 51% attack, in PoW, an attacker needs to buy enough mining equipment to gain hash-power to take over the network. In PoS an attacker would have to buy 51% of the total delegated currency.
Proponents of the PoS protocol argue that the network could fork in the event of an attack, thus destroying the amount delegated by the attacker. However, this largely depends on whether the forked network can survive the loss of trust that an attack would bring.
Many PoS networks also require validators to hold a generally significant amount of blockchain cryptocurrency locked on the node, prevailing stakepools with large sums of money, typically institutions, with a similar impact to mining farms in PoW, leading to greater centralization.
This is not the case with Cardano, which does not require a minimum pledge, and which also has an insignificant impact on the slot leader draw. The negative consequence of this is that “skinless in-game” actors are introduced, who are the validators who have nothing to lose.
The mitigation of these problems in PoS can be addressed with changes in the parameters of the consensus protocol, encouraging honest participation, where, for example, a relationship between the amount delegated and the required pledge could be established, so that the leverage is maintained in Not exaggerated values, that is to say that the amount of the pledge is not less than a certain value with respect to the delegation, and thus there can be “skin in the game”.
(1) The Trend Continues as Blockchains Increasingly Under Attack
Excelente explicación, muchas gracias