This content originally appeared on Level Up Coding - Medium and was authored by Henrique Centieiro
In any blockchain, there’s an ongoing war between good and evil! Good nodes want to keep the true state of the blockchain but bad actors want to make fraudulent transactions! Solving the Byzantine General’s Problem allows us to win the fight against evil nodes and even tolerate them!
This article is part of a series of articles where I talk about other consensus mechanisms. You can check the links below after you finish reading about PBFT ⚔
- What’s Proof of Elapsed Time
- Bitcoin Proof of Work — The Only Article You Will Ever Have to Read
- Proof of Stake — What is and how does it work?
- Proof of Importance Consensus Mechanism
- Delegated Proof of Stake
- Proof of Burn
Let’s go to war!
A blockchain is like a constant war between good nodes and evil nodes. Being a distributed network with dozens, hundreds or sometimes thousands of nodes need to agree on the current state of the blockchain and make sure the good nodes win over the evil nodes. That’s what we call consensus achievement.
However, reaching consensus in a distributed system in a safe and efficient way it’s not an easy task.
Just like in a war, how can we make a network of independent nodes agree on a decision or a piece of data if some of the nodes can eventually fail or act dishonestly? How can the good nodes win over the evil, fraudulent or faulty nodes?
This is the fundamental question of the Byzantine General’s Problem! A problem that has been bothering mathematicians for thousands of years (yeah, the problem was officially published only in 1988) and it was finally solved in 1999!
What the heck is this Practical Byzantine Fault-tolerant consensus thing?
PBFT tries to solve the Byzantine General’s problem! But why do the Generals have a problem?
The Byzantine Generals Problem is a hypothetical situation where a number of generals leading their Byzantine army need to decide if they attack or retreat from the city they are surrounding.
The Generals are situated in different locations surrounding the target city, meaning that they are far away from each other.
They can only conquer the city if they all attack at the same time and no one retreats. To ensure the operation’s success, the Generals need to reach a consensus! They need to either attack or retreat altogether. They need to reach a consensus!
Each General will vote on whether to attack or retreat. After voting, they cannot change their mind. Additionally, all Generals need to agree on the same decision and execute it in coordination.
But there’s a problem! They need to communicate with horse messengers that carry the information between the generals. One of the problems is that the messenger can be a traitor or be killed halfway. One of the messengers can also change his mind or chicken out, which would compromise the entire army. How can we solve this issue?
This is why the Byzantine General’s need to have a consensus mechanism to ensure that everyone is on the same page.
In the context of a blockchain network, the potential traitors may be the nodes, and the messengers may be the potentially corrupted communication channels between them. This problem was solved in 1999 by the PBFT algorithm, developed by two computer scientists, Miguel Castro and Barbara Liskov. PBFT can also be used in other distributed systems other than blockchains, such as peer-to-peer networks and IoT networks.
The PBFT enables decentralized systems to be resilient to failures and allows systems with multiple participants to work in consensus. PBFT systems are resilient, i.e. fault-tolerant, to nodes that are malicious or fail to communicate properly with the other nodes. PBFT can secure systems with multiple nodes and add some resiliency and fault tolerance. They are BFT — Byzantine Fault Tolerant — meaning that they tolerate a percentage of nodes failing (for example 1/3).
The Byzantine General’s problems:
- The communication channel may not be trusted
- The message could be altered or replaced
- Messenger can be killed
- Messenger can be delayed
The solution:
- Consensus algorithm that it’s immune to the lack of trust
- Consensus mechanisms such as PBFT, PoW and PoS are Byzantine Fault Tolerant
- The “good” generals must have more power in the network than the faulty ones
- Cryptography integration to create consensus and data immutability
Bitcoin’s Proof of Work is considered one of the most genius solutions for the Byzantines Generals Problem and one of the most secure consensus mechanisms.
In Bitcoin and other proof of work blockchains, when General Andrew wants to send a message to General Big Daddy, he can take the message, and add a nonce, producing a certain unique hash. Then, he can send this to Big Daddy. Even if the messenger tries to change the message (men in the middle attack), he would have to change the hash of this message and the other messages sent by the other generals. This would require too much work, making it infeasible to make this attack.
Once General Big Daddy receives the message from General Andrew, he can easily verify that the message was not altered, and he will reply “I agree” to the group, adding a nonce and a hash for the others to see that the message is legitimate. The other generals will do the same and reach a consensus. Everyone has to perform this proof of work, making it hard for an attacker (insider or outsider attack) to change the generals’ consensus.
If one of the generals decides to retreat instead of attacking, that decision will not bother the consensus because all the other 3 generals keep the consensus. This is why these consensus mechanisms are called “fault-tolerant” because they tolerate a number of nodes’ failure. Once the generals reach a consensus, they can attack Rapture and conquer the city (or in this case, they agree on a new block in the blockchain)!
Blockchains that don’t have proof of work also apply Byzantine Fault Tolerant mechanisms. Hyperledger Sawtooth, for example, uses PBFT — Practical Byzantine Fault Tolerance.
We saw that Byzantine fault-tolerant systems are distributed systems that can tolerate faulty nodes to some extend. In PBFT, if f is the number of faulty nodes, then 2f + 1 non-faulty nodes are required to reach consensus.
Let’s look at how PBFT algorithms are resilient. Assume the following
n = total of nodes
f = number of faulty nodes
PBFT can tolerate up to f = (n-1) / 3
Or n — f = (2n + 1) /3
A high-level and slightly simplified illustration of the PBFT algorithm:
- Request: a client, in this case, our General Andrew, sends a message/request to one of the peer nodes — General Big Daddy
- Pre-prepare: both Andrew and Big Daddy multicast the message to the other nodes, sometimes also called replicas in PBFT (generals Sophia and Elizabeth)
- Prepare and Commit: the replicas execute the request and send a reply to the other nodes
- Reply: the client waits for n + 1 replies from the generals with the same result. This will result in a positive consensus
Voilà, the consensus is reached and the Byzantines General’s problem solved! Consensus reached! Let’s conquer Rapture!
? Follow me and also check my ? blockchain courses:
? The First-Ever Dogecoin Course
? Fintech, Cloud and Cybersecurity Course
?? Unblockchain Course — The Brain-Friendly Blockchain Course
Let’s talk about war! The Practical Byzantine Fault-tolerant Consensus was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Henrique Centieiro
Henrique Centieiro | Sciencx (2021-06-01T13:44:46+00:00) Let’s talk about war! The Practical Byzantine Fault-tolerant Consensus. Retrieved from https://www.scien.cx/2021/06/01/lets-talk-about-war-the-practical-byzantine-fault-tolerant-consensus/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.