Types of PoS Algorithms.
There are two main types of PoS algorithms. The first type is Byzantine Fault Tolerance or BFT. With BFT, users holding a stake do not get to create a block right away and the process has multiple steps to it with several rounds. During the first round, the algorithm chooses a participant who proposes a vote and then other participants need to vote on whether they agree with the proposal. This is similar to a democratic process in which a party comes up with a suggestion and then voters decide whether they agree with the suggestion or not.
Byzantine Fault PoS
The name of this type of PoS algorithm comes from a problem known in computer science as Byzantine General’s Problem.
The problem is the following: generals planning a battle need to agree whether to attack or not based on the information they have. The issue is that the information in their possession may be coming from their loyal soldiers or it may be coming from spies and the generals do not always know for sure who is loyal and who is a spy.
Leslie Lamport and Robert Shostak have studied this problem in their 1982 paper that has the same name, “The Byzantine Generals Problem.”
In the paper, they pointed out how the problem is the same as the issue that many computer networks are having when it comes to the security of the network. This is the exact same problem that many proof-of-stake blockchain networks are trying to effectively solve today.
The issue is being able to tell a malicious player from a legitimate user or node on the network. A malicious user on a network, be it a regular computer network like the ones that have existed for decades or a blockchain network, may be sending different signals to different other members of the network. Even a user acting in good faith may be sending various signals and be making an honest mistake or have malfunctioning hardware. The goal of the remaining users on the network is to be able to make decisions about how the network should be moving forward.
The Byzantine Fault Tolerance problem is one of the hardest problems in computer science because it has two layers to it. The first layer is that users on the network need to find a way to agree what to do and make a decision. However, there is also a second layer, which is determining what is going on with the network and which components of the network are working properly, which components are malfunctioning and which components are potentially under attack.
In their paper, Lamport and Shostak show that the generals can only come with a decision about how to move forward if more than 2/3 of the generals (or users on a blockchain network participating in making decisions) are loyal.
Here are several examples that explain this in simple language. Let’s say there is a network of 3 generals. Two thirds in this case would mean two and more than two thirds would mean three. According to Lamport and Shostak, on such a network the generals would only be able to make a decision if all three of them are loyal. If even one of them is not loyal and is a spy, then the spy then the spy can send message A to general 1 and message B to general 2. Now there is no way for general 1 and general 2 to agree because their messages are different. The only way for them to agree would be to consult general 3, but for this to work they would absolutely need to know that general 3 is not a spy, which is not possible if the number of loyal generals is not more than two thirds.
The second type of PoS algorithms is chain-based PoS. Chain-based PoS algorithms are simpler than Byzantine Fault tolerance ones. A chain-based PoS is similar to a system in which participants agree that whoever the system chooses gets to decide on a block. The chosen party gets to make a decision and in chain-based PoS there is no subsequent voting on the decision of the chosen party. The only condition is that the block that the chosen user creates mentions one or several of the previous blocks so that the new block of the blockchain is connected to the previous blocks similarly to how blocks on the Bitcoin blockchain connect to each other via hashes.