Lecture
This material will help you understand the tasks that the protocols under consideration solve, their areas of application, the specifics of their design and use, and will also let you assess the prospects for their development and implementation in decentralized ledger systems.
Note that a decentralized network applies the principle of redundancy, which is based on the fact that nodes can do the same work. For a centralized network this is, naturally, inefficient, but for a decentralized one it is a mandatory condition. Let us move on to the basic requirements.
Protocols must ensure reliable operation for users in fairly harsh conditions while satisfying minimum requirements. The main ones are listed below.
No central trusted party. The network consists of equal peer nodes. If an attacker or a third party tries to disable a certain number of nodes, the network will continue to operate normally as long as honest participants control an overwhelming majority of the network's nodes.
Honest participants do not know which nodes are controlled by attackers. It is assumed that other nodes may fail at arbitrary moments or behave arbitrarily, including being coordinated by attackers to carry out an attack on the network. Again, honest participants do not know which nodes are honest and which are faulty or unreliable.
It is assumed that the network is deliberately unreliable. Some messages may be delivered with a serious delay, while others may be lost in the network and never delivered at all. It is under such conditions that decentralized consensus must continue to function normally: all honest nodes must arrive at the same state of the database of confirmed transactions.
Protocols must be fully formal. There must be no additional human involvement and no additional data is required. All honest nodes must arrive at the same decision by strictly following the algorithm executed by a computer.
In addition, there are certain assumptions under which the protocol guarantees correct operation. Honest nodes must make up the majority of all participants: more than ½ or ⅔ of their total number. However, the time to reach a decision is not limited. The limit may apply to the number of steps needed to reach a decision, but not to time.
First of all, this applies to cryptocurrencies: Bitcoin uses the Nakamoto algorithm, Ethereum uses a simplified version of GHOST, Bitshares implements Delegated PoS, and so on.
It should be noted that the community that supports a particular digital currency is not always large and decentralized. There are a number of other digital currencies that are centralized. However, this does not mean that a consensus mechanism will not be needed. For example, Ripple uses a BFT protocol in a centralized environment.
Consensus protocols are used in highly reliable computing systems. They can be used for access to distributed databases when building clusters, and they are also necessarily used in critical technical systems: these may be control systems for aircraft equipment, control systems for nuclear reactors, as well as space technologies.
On February 6, 2018, the Falcon Heavy was launched. It was interesting to watch it and to read the technical reviews. But it was no less interesting to read about which agreement algorithms the team uses. The engineers were forced to use simple electronics of the kind sold in ordinary stores, which does not work entirely reliably in the harsh conditions of space. Therefore they apply multiple redundancy in their work, and reaching consensus is necessary in this case.
Cryptocurrencies operate in peer-to-peer networks. In these networks, messages or transactions are passed between network participants at arbitrary moments in time. Suppose the network has participants located in the USA and participants located in Australia. Participants in America will see payments sent from the USA earlier than payments sent from Australia. This happens because of the considerable delay, by computer standards, in delivering a message from one continent to another. The situation will be similar for Australians, because they will see payments from Australia earlier than payments from the USA.
The situation described above means that different network participants will see different final states of the transaction database at the same moment in time. Since transactions arrive from users to validators at different times, a protocol is needed that allows every node, regardless of its location, to obtain all transactions in the same order.
Two approaches are mainly used to operate cryptocurrency ledger systems: PoW, which is the most widespread, and PoS, which has been actively developing recently.
In PoW, an additional amount of work is performed, which currently consists in finding a preimage of a hash function. In effect, this artificially slows down the network in order to ensure security. To carry out a malicious action, an attacker would have to perform the necessary amount of work. This requires colossal energy expenditure and makes attacks not very efficient. This approach provides reliability of the network's operation. However, the need to perform such a resource-intensive task limits the throughput of a network that operates under this protocol. Yet scientists continue to work on the PoW approach and to propose alternative schemes, as well as other resource-intensive tasks besides finding a hash function preimage. An algorithm based on proof-of-space-and-time was recently proposed.
PoS makes it possible to provide higher network throughput and does not require excessive electricity costs, as PoW does. However, PoS requires more serious analysis when designing and implementing a cryptocurrency.
In PoS-based ledger systems, it is assumed that users who own a large number of coins have no incentive to carry out attacks. In a PoW-based ledger system, an entrepreneur invests money in equipment and pays for electricity, and then carries out a successful attack on the system, so he will lose his investment in mining. PoS uses a different approach: if it is assumed that an attacker has invested in specific coins whose value he is interested in, then in the case of a successful attack on the system he will lose his investment, because the coins will be devalued. Therefore, honestly following the protocol is considered the most profitable strategy.
Safety – the ability of a ledger system to preserve its basic operating principles and the interests of honest participants under any malicious influence.
Finality – a property indicating that an adopted decision or confirmed data cannot be reversed.
Liveness – a property that guarantees that if all honest participants want to add a record to the shared database, it will eventually be added there.
Persistence – the ability of a ledger system to keep the final state of its database unchanged even after all of its validators have failed.
Permissioned – indicates a restriction, that is, the need to obtain permission to take part in a given process.
Permissionless – means free access to take part in a given process.
Ouroboros is a PoS-based protocol that provides consensus among the validators of transactions in the Cardano digital currency. Moreover, the algorithm itself is the first provably secure one among all PoS alternatives.
First, let us consider a simpler variant, oriented toward static stake, in which the existing distribution of coins is assumed not to change.
There is a genesis block, and users form new transactions, but these do not significantly affect the distribution.
The genesis block contains data with a random value, which is used to select the validators. They make it possible to issue a block at a particular moment in time. A validator that has received such a right collects transactions, receiving them from another validator, checks their correctness, and issues a block to the network. If it sees several chains, it chooses the longest of them and attaches the block to it.
In the static stake setting, we can use this approach for a certain period of time, but afterward the stake distribution among different users may change. In other words, part of the money passes from some users to others, and the probability of being given the right to select a block needs to be adjusted.
Note: static stake implies that for a certain period of time a validator's stake is considered unchanged. During this time the validator may take part in decision-making and make payments, but the number of coins in its stake, and therefore the weight of its vote, will remain unchanged until the next period of time.
In the case of dynamic stake, time is divided into slots, and slots are divided into epochs. The duration of one epoch is approximately equal to one day. This ratio is chosen because the distribution of coins cannot change significantly within this period of time.
When an epoch ends, the current distribution of coins among the users is fixed. In addition, a new random value is generated to guarantee that in the next epoch the users who receive the right to generate blocks will indeed be chosen randomly, in proportion to the number of coins they hold.
This protects against so-called grinding attacks, in which a particular user can try out various block variants and various random values in order to form the chain in which he can maximize his profit. Cryptocurrencies based on first-generation PoS protocols, such as Peercoin and NXT, are potentially vulnerable to such attacks.
The creators of this algorithm solved the problems listed above. The validators run a special protocol among themselves, called MPC (multi-party computation), which makes it possible to generate randomness jointly. This protocol is also provably secure, and it is based on long-known approaches.
The Ouroboros protocol remains secure provided that the majority of validators in the system are honest. If the honest participants who work on issuing blocks control more than 50% of the coins in the system, the protocol can be considered secure.
An incentive (motivation) mechanism for honest behavior has been developed. Using game theory, it has been proven that a validator gains the maximum benefit when it follows the rules of the protocol. Any participation in attacks not only fails to increase a participant's profit, but in some cases may even reduce it. Therefore, the most profitable strategy for a validator is to follow the rules of the protocol honestly.
The throughput of the ledger system will be limited only by network synchronization delays. This protocol provides high energy efficiency compared with proof-of-work, since mining farms are not needed. Today an ordinary personal computer is enough to collect transactions and issue blocks. In the future, these computations could even be performed on an ordinary smartphone.
The limitations of the Ouroboros protocol include the fact that the first version of the protocol is synchronous. This means that messages between participants must be delivered within a bounded period of time. If longer delays than those assumed in the rules appear in the network, security may be reduced. Nevertheless, the use of the next version of the protocol, Ouroboros Praos, is already planned. It guarantees full security even when network delays increase.
Let us consider the method of reaching consensus that underlies Bitcoin. Some of the blocks generated by honest users are still discarded – these are the so-called orphan blocks. These blocks are generated in parallel with the main chain, but most of the network decides that this chain should not be continued, and the blocks are discarded.
When there are few such blocks, this is not a problem. However, if there are many of them, the network does not have time to synchronize, and it turns out that part of the computing power of the network's honest users is wasted. This means that an attacker now has to compete not for 51% of the network's computing power, but in effect for a smaller percentage. If this value is 20%, then an attacker with 20% of the computing power and a long message delivery delay in the network can carry out a double-spending attack.
That is why Bitcoin sets an interval of 10 minutes between mined blocks. Thanks to this, the network has time to synchronize clearly, and the probability of such blocks appearing decreases. If it becomes necessary to increase the network's throughput by increasing the frequency of block creation, a different solution will be needed.
The first such solution was the PoW protocol GHOST. A simplified version of it is used in the Ethereum platform.
In this case, an attacker can extend his chain (shown in red in the figure) and make it the longest, but it will not be the winning one. Honest users will keep following the chain that they were building before.
In this case the honest users may have two chains. The longest one (1B-2D-3F-4C-5B) will be shorter than the attacker's chain. The distinctive feature of GHOST is that the algorithm is guided not by the longest chain, but by the number of blocks in the tree formed by the current chain. It takes into account not only the length of the chain itself, but also the blocks at its different heights. Thus, the result is not a linear chain but a tree. The number of blocks contained in it is taken into account.
If we look at the chain 1B-2C-3D-4B, we can see the accompanying blocks 3E and 3C. In terms of the number of blocks and the work expended, this chain has the greatest difficulty, and it is the one that will be accepted as the main chain. Honest users will continue to regard it as the main one despite the attacker's attempts to attack the network. Under traditional Nakamoto consensus such an attack would succeed, but for GHOST it poses no threat.
Nevertheless, a drawback of GHOST remains the fact that some blocks are still lost. In this case, the chain 2D-3F-4C-5B will still be discarded. Consequently, the problem of discarding the blocks of honest users remains open.
To increase the frequency of block creation and to solve the problem of discarding honest users' blocks, two more PoW protocols were proposed: SPECTRE and PHANTOM.
They use not even a tree structure, but a so-called directed acyclic graph (DAG). In this case a validator includes in the header of its block pointers to the blocks that are not yet referenced by other validators, at least in the state of the network that it sees at the current moment, and sends the block onward.
As a result, a structure is obtained that includes absolutely all the blocks that the validators see at the current moment. Here the mining power of honest users is not lost at all. Moreover, high network throughput and a high level of security are ensured. An advantage of this approach is that the system is truly decentralized.
Let us compare the features of the Bitcoin network and a network that works using the SPECTRE and PHANTOM protocols. Looking at the current state of the Bitcoin network, great importance should be attached to mining pools. In modern Bitcoin, 144 blocks are produced per day. This is exactly the figure obtained by dividing the number of minutes in a day by 10. It may well happen that a validator has bought equipment and paid for electricity for a long time, but has never managed to generate a block, and in the meantime the equipment has become obsolete and there is no longer any point in using it. To avoid this situation, enterprising validators join together in mining pools. Most mining pools have a leader (a company or organization), which pushes modern Bitcoin toward centralization of the validation of new transactions.
In the case of SPECTRE and PHANTOM, mining pools are not needed at all. If we draw a parallel with the modern Bitcoin network, each user of a network that uses the SPECTRE and PHANTOM protocols has a chance to issue one block per day. Thus, the need for mining pools disappears entirely, and we arrive at a truly decentralized network.
So, the SPECTRE and PHANTOM protocols provide a high level of decentralization and high network throughput, but they require a large amount of information to be stored.
The next type of protocols in use is the BFT (Byzantine Fault Tolerance) protocols.
The name originates from a humorous description of the problem that was made in the 1980s during the development of a protocol for highly reliable systems. An example was given about Byzantine generals who are organizing an attack on some city. The generals' task was to reach a single decision. But it had to be taken into account that there are several traitors among them. The traitors could behave in an arbitrary way and, moreover, they could influence the transmission of messages between the honest generals, for whom it is important either to attack the city simultaneously or to retreat simultaneously. If some of the honest generals retreat, the enemy will defeat the army piece by piece. Therefore, they had to reach a coordinated decision. The problem was posed in this way in the original paper, which is where the name of this consensus algorithm comes from.
BFT protocols assume interaction among equal network nodes. It is assumed that there is a certain number of adversaries who can act in a coordinated manner. They are unknown to the honest participants. Failures and delays are possible in the network, that is, some messages may be lost and others may arrive with a long delay. However, a limit is imposed on the number of steps within which all honest validators must reach a common decision. In the example problem there are two options: attack or retreat.
It is assumed that honest nodes make up more than ⅔ of the participants. BFT protocols are guaranteed to arrive at a common decision that cannot be reversed in the future. For non-BFT protocols, the probability of a decision being reversed decreases exponentially but is not zero.
Bitcoin and other modern, widely used cryptocurrencies are based on non-BFT protocols. For Bitcoin there is a nonzero, though negligibly small, probability that an alternative chain exists, extending, for example, from the previous month, from the previous year, or even from the Genesis block. The probability of the current chain being reversed decreases exponentially, but it exists. In the case of a BFT protocol, a decision that has been made cannot be reversed.
The first protocol to be applied in practice was called Practical BFT. It was proposed in 1999. Its operation is fairly simple. A client contacts a server, which it chooses as the leader. The leader passes these messages on to the other servers. After that, the servers tell one another that certain messages have arrived and need to be entered into the shared database. Each of the validators must confirm that it has received confirmation from ⅔ of the other participants.
When a validator has received confirmation from ⅔ of the other participants that a message is to be included in its copy of the database, the message is entered into that validator's local copy.
The protocol is energy efficient and provides high throughput and fast transaction confirmation, but, unfortunately, it works only for a small number of validators. If a cluster, file system, or cloud is designed on the basis of this protocol, it works efficiently, but if we begin to use a large number of nodes, the number of messages grows rapidly and the load on the network increases enormously. In the latter case the protocol works inefficiently, especially when the network has delays, drops messages, and so on.
In addition, the basic variant assumes the presence of a leader, which can become a point of DoS attack that an attacker could use to halt the operation of the ledger system.
HoneyBadger BFT has established itself well and was developed as an improved version of one of the existing algorithms. It uses a number of features, including cryptographic protection of all messages transmitted over the network. Transactions are decrypted only after a certain agreement on them has been reached. HoneyBadger consists of two protocols: RBC (Reliable Broadcast) and BA (Byzantine Agreement).
The RBC protocol is used to deliver messages across the network. This protocol finishes its work only after it receives confirmation that at least ⅔ of the honest validators have received the required set of messages. After that, the validators move on to the BA protocol and to agreement on the transactions themselves, which are then sent to the network.
This protocol provides reliable cryptographic protection. It works well in networks with poor data transmission quality, where transmitted messages are dropped and their delivery is delayed, as well as in networks with serious malicious interference. There is no leader here. The protocol suffers when scaled up significantly: with hundreds of validator nodes it still works normally, but with several thousand it already puts too heavy a load on the network and transaction confirmation time increases greatly. In a fully decentralized ledger network with thousands of validators, the protocol becomes rather ineffective.
Further development resulted in the Algorand and Hashgraph protocols.
The Algorand protocol was proposed in 2017. It uses the same BFT approach, but is designed so that a subcommittee is chosen at random from among all participants, and this subcommittee performs the confirmation of transactions. Moreover, this confirmation takes place in several stages, and a different subcommittee is chosen for each of them.
The protocol guarantees, with a probability close to one, that a subcommittee is honest if more than ⅔ of the network participants are honest, that is, each subcommittee will also have ⅔ honest participants. There is no leader here, and therefore no point for a denial-of-service (DoS) attack. This protocol provides high throughput of the ledger system, fast transaction confirmation, and protection against adaptive corruption.
It is assumed that an attacker can choose an arbitrary validator and declare that it is the one working in his interests. The attacker can choose the nodes that will work for him (for correct operation it is a necessary condition that more than ⅔ of the participants remain honest). Even under such conditions the protocol remains secure.
Since this is a BFT protocol, in any case it provides the properties of safety and persistence. Its other properties will depend on delays in data transmission over the communication channels.
If this protocol operates in a problematic network, there is a liveness threat, which is that new transactions may not receive confirmation. If excessively long delays appear in the network, or the attacker gains the ability to drop whichever messages he needs to drop to achieve his goal, this will not affect old (already confirmed) transactions in any way. He will not be able to reverse them. The point is that he will be able to block precisely the acceptance of new transactions.
The Hashgraph protocol is a recent solution with very good properties. Each validator collects its own transactions, randomly chooses another participant, and sends it data about its own transactions as well as the information that other nodes reported to it when they connected to it.
So, the operation is very simple: a validator "listens," receives all the messages that come to it, and then randomly chooses another participant and sends it all the transactions together with its own.
Hashgraph guarantees that within a finite number of steps, that is, rounds of the protocol, all nodes arrive at a single decision. The protocol works fast and scales well. It requires more traffic than Algorand, but at the same time is very efficient. Hashgraph provides the properties of safety and liveness, that is, the addition of new transactions and the arrival at a single decision. It works even in a fully asynchronous network, where messages may be delayed for a very long time or dropped altogether.
In addition, there is no leader in the network, which allows an attacker to disable the nodes that happen to interest him, and he may be able to force them to work in accordance with his intentions. However, as long as ⅔ of the users remain honest, the protocol provides a high level of security.
Let us sum up the BFT protocols. They provide very high throughput and allow validators to reach agreement on the state of transactions within a fixed number of steps. These properties allow them to be used successfully in cryptocurrencies. The protocol operates reliably even in unreliable networks, provided that more than ⅔ of the validators of the ledger system are honest. Protocols such as Algorand and Hashgraph maintain high throughput, and a truly large number of validators can work in them.
At the same time, they have a very serious drawback: in their current state of development, the protocols are designed for so-called permissioned ledger systems. In other words, they are designed without taking into account the incentive for validators to work honestly in the network itself. It is assumed that such incentives lie outside the scope of the protocol. Rewards for block creation and the various strategies of user behavior are not considered.
To deploy such protocols in permissionless ledger systems, researchers will need to do serious work. In this respect, a wide field of research remains open to them, both from the game-theory standpoint and from the standpoint of designing a reward system for validators, and so on.
Distributed Lab prepared this article based on the material of a video lecture by Roman Oleynikov.
– Is it possible to introduce a radically new consensus protocol in the near future, and are there any developments?
Indeed, consensus protocols are currently under active development. We discussed some of them today: Algorand and Hashgraph among the BFT protocols, as well as Ouroboros, a protocol based on PoS consensus. The PHANTOM protocol was presented in early 2018. These are new protocols with new principles.
– How does Ouroboros ensure that the list of nodes entitled to form a block in particular time intervals is the same for all nodes?
The question is related to the grinding attacks mentioned above. Ouroboros provides the properties of persistence and liveness: if a transaction has been included at a certain moment in time and has received confirmation, it can no longer be reversed or removed, since the probability of replacing this block tends to zero. In other words, the developers believe that a transaction cannot disappear from the shared database, since it is available to anyone who wants it.
Thanks to the persistence property, all network nodes form the same set of transactions in their local copy of the database. Potential validators send transactions with their own randomness, which is initially hidden, and at the moment the MPC protocol completes, everyone can compute the resulting randomness. All users have an agreed transaction history, so all nodes obtain the same list of actual validators. It is impossible to manipulate the randomness here, because the MPC protocol provides properties such that no participant can obtain this randomness until everyone has put it into the blockchain. Only after that is the randomness revealed. Even if someone does not want to reveal his randomness, the protocol itself guarantees that this data will be revealed. Everyone has the same view of the history and of the randomness. Even if at least one potential validator has "thrown" a truly random value into the blockchain (one is enough), the resulting randomness will be unpredictable.
– In which book can I read about the consensus algorithms discussed in this chapter?
Unfortunately, there are no such books yet. There are only individual scientific papers and articles. You can look at the papers on PHANTOM, SPECTRE, and Ouroboros. You can look at the website where these papers can be found by title.
– Why issue so many blocks in PHANTOM and SPECTRE if there is not such a large number of transactions? Most blocks will be empty or contain few transactions.
PHANTOM and SPECTRE are aimed precisely at scaling. In Bitcoin there have been situations more than once where transactions with a low fee could remain unconfirmed in the network for even several months. PHANTOM and SPECTRE guarantee that all transactions will be included in blocks and that the network's throughput will be increased. These protocols can handle tens of thousands of transactions per second, with each one receiving confirmation. In other words, they can provide very low transaction costs in the network itself. If there are no transactions, then it is indeed possible to issue empty blocks.
– How and by whom is the leader server chosen in BFT?
It depends on the specific protocol. In PBFT, an individual user chooses a leader server that will handle his transaction. In Algorand or Hashgraph there is no leader at all.
– What happens in PBFT if the initial request reaches a compromised node?
In this case the compromised (or non-functioning) node may fail to process it. If the user picks the node to contact at random, and two thirds of the nodes are honest, then after a few attempts the transaction will, with high probability, be confirmed.
– Is it correct to say that Algorand is something like DPoS (Delegated Proof-of-stake)?
No, that is not quite correct. Delegated Proof-of-stake implies that users must choose a validator and delegate their voting right to it. Here, nodes are selected to confirm transactions genuinely at random. If we look far into the future and consider ways of building a cryptocurrency on Algorand, then it will indeed be necessary to develop delegation options, but the protocol itself does not need delegation to work.
– Which of the protocols listed are not yet in use but are considered promising for the future?
SPECTRE and PHANTOM are truly promising protocols. And the developers of SPECTRE are working on launching a new digital currency.
The foundation of Distributed Ledger Technology (DLT) is the consensus protocol. Interestingly, mathematicians and engineers have been developing distributed networks and consensus protocols for decades, but it was only with the appearance of the Bitcoin project that this technology made a significant leap forward. This step made it possible to create an entirely new type of application. Let us look at the most popular consensus algorithm variants today.
What is consensus? Broadly defined, consensus is an agreement that satisfies each of the parties involved. It is the key to democracy and decentralization in general, and to distributed ledger technology in particular. Take Bitcoin: even though Satoshi Nakamoto is its mysterious founder, he has no power over the community. Bitcoin, like the blockchain, is fully transparent and open, and every node is equal in this network.
In the narrow sense that we apply to cryptography, consensus is a decision-making procedure. Its purpose is to ensure that all participants in the network agree on their current state after new information, a data block, or a batch of transactions has been added. In other words, the consensus protocol guarantees that the chain is valid and gives incentives to remain an honest participant. It is an important structure for preventing a situation in which a single party controls the entire system, and it ensures that everyone follows the rules of the network.
A protocol is a set of rules.
Protocols help to:
A protocol is the sum of:
Let us look at some of these protocols.
Principle: a solution is hard to find but easy to verify.
Performance: low.
DLT environment: public blockchain.
Finality: probabilistic.
Usage examples: Bitcoin, Ethereum, Litecoin.
The Bitcoin blockchain is perhaps the most copied blockchain. Numerous nodes confirm transactions in accordance with the PoW consensus algorithm. To add a new block, a participant must prove that they have performed a certain amount of work. To be precise, they solve a very difficult problem of finding a hash that satisfies certain rules. The first one lucky enough to find the right combination gets the opportunity to add a block to the chain.
As a result, participation in PoW entails the expenditure of computing resources, but the advantage is that it can be implemented in an environment where participants do not trust each other at all. Anyone can join the network, since it is a permissionless blockchain. And although the scalability of peer-to-peer networks is high, transaction speed remains low.
Another problem is the motivation of network participants — they usually join to get rich rather than to maintain fairness. The reduction of mining rewards over time and low fees in the future could seriously affect the security of the network.
Principle: the network trusts a validator who stakes their own resources as collateral for the right to create blocks: the larger the stake, the higher the probability that the network will allow the block to be created.
Performance: high.
DLT environment: public/private blockchain.
Finality: probabilistic.
Usage examples: NXT, Tezos, soon Ethereum.
The Ethereum mainnet is Turing-complete and runs on the PoW protocol. However, the project plans to switch to a more efficient protocol known as Proof-of-Stake (PoS).
The technical feature of PoS is the absence of complex and unnecessary computations. Instead of competing with one another, network participants stake their crypto assets, such as ether (Ether) in Ethereum, and wait to be selected to create a new block.
But in practice this algorithm is also good because the motivation of network participants is radically different from PoW. Here participants are interested in security, since they themselves own the system's coins. The algorithm selects a single validator based on the stake it holds. Therefore, if a participant holds a 5% stake, it will also validate 5% of transactions. The idea is that the larger the validator's stake in the underlying cryptocurrency, the less interest it has in manipulating the validation process.
As with the PoW algorithm, transaction finality in PoS is probabilistic. Although transactions are relatively fast compared with transactions on the Bitcoin network, tokens are still required for this. Moreover, skeptics point to the fact that validators with large stakes will be chosen more often and, consequently, will receive even more tokens: the rich get richer.
Principle: participants delegate the production of new blocks to a small, fixed number of elected validators. Competition is high, but very profitable.
Performance: high.
DLT environment: public/private blockchain.
Finality: probabilistic.
Usage examples: EOS, BitShares.
Meanwhile, developers proposed an alternative economic incentive called Delegated Proof-of-Stake (DPoS) (delegated proof of stake). By reducing the number of validators, it makes it possible to create blocks at high speed and to process more transactions per second than other consensus algorithms. During voting, coin holders elect the transaction validators who will form blocks. The weight of each vote is determined by the amount of the voter's assets. Coin holders can vote for candidates at any time. This gives the network high resilience: if most of the block producers fail, the community will immediately vote to replace them.
New blocks are generated every 1-2 seconds. This protocol is not only faster but also fairer, since the "delegated" validator later shares tokens with its voters. Nevertheless, the confirmation of finished blocks still rests on the shoulders of all the other network participants. Daniel Larimer developed DPoS in 2014. He first used it in his BitShares project, and later in Steemit and EOS. Larimer assumed that DPoS validators would have a strong incentive to stay honest and to offer the fastest and best service. After all, it would be foolish to hack a network that pays you well. And if you stop doing the job well, there are always other participants ready to take your place as a validator.
So far we have talked about public blockchains, which operate in a public environment and aim at decentralization. What about private enterprises on the blockchain? What changes if participants know a little more about one another, or are even known from the very start of the network (for example, different divisions of the same company)? In such cases the consensus algorithm can be optimized and much higher throughput achieved. In fact, speed increases 10-fold, from hundreds to thousands of transactions per second, which is excellent for corporate realities.
It is important to note that protocols "tolerant to the Byzantine problem" (BFT) are a characteristic that a distributed system either has or does not have. However, in the context of our categorization, BFT denotes a new class of protocols that does not require tokens for voting, as in the PoW or PoS algorithms. In addition, it allows a block to be signed even if 1/3 of the participants fail or act maliciously. BFT also addresses system failures and communication delays.
Principle: pre-selected "trusted" participants maintain consensus even if 1/3 of them fail or are malicious.
Performance: very high.
DLT environment: public/private blockchain.
Finality: immediate.
Usage examples: NEO, TON.
This algorithm refers to the old Byzantine Generals Problem, based on a real historical event. Using the analogy, the protocol does not care if a "general" falls ill or sabotages his colleagues. The system will keep working even when a node goes offline. Thus the BFT consensus protocol seems to be a salvation from the imperfections of PoW and PoS, but given thousands of validators, it will still struggle with the speed problem. That is why developers proposed a delegated BFT model — DBFT.
The predefined validators in this consensus protocol allow it to get significantly ahead of other protocols. Compare Ethereum with 15-20 transactions per second and NEO with almost 10,000 TPS. It is genuinely convenient to have a few known actors who verify transactions before releasing them to other nodes. If a validator "leaks", participants can delegate a new node. It is worth noting that although this protocol is designed for a public environment, it is more centralized.
Note: since NEO runs on the PoS DBFT protocol, network members not only delegate validators but also receive the native GAS token as part of their validator's share.
Principle: a simple and fast implementation of the BFT algorithm for private networks.
Performance: high.
DLT environment: private permissioned blockchain.
Finality: immediate.
Usage examples: Hyperledger, Chain.
If you need a scalable and fast, but private, blockchain, this protocol is for you. The PBFT protocol is very similar to DBFT, especially in its more centralized nature. The only difference is that the former has a simpler implementation and often operates in a private environment with known participants. Which is very practical, isn't it?
When a validator receives a message, it must decide whether to believe it or not. To do so, it performs its own checks and then polls all the other nodes in turn as to whether, in their opinion, the transaction is valid. If ⅔ of the participants are in favor of the transaction, the node accepts it and passes its decision on to the network for the other validators. Thus consensus is reached on the basis of the confirmation provided by all the validators.
PBFT is efficient in low-latency systems, but is very sensitive to the number of validators and to bandwidth, since one message generates many other requests and checks. It is well suited to a private environment where a heavy load is not required, but a large number of transactions is needed. PBFT guarantees the finality of transaction decisions in the network, since a decision is made by an absolute majority at every moment in time.
You may also have heard of the Sieve protocol, which is an improved version of PBFT. Its distinguishing feature is that it can handle non-deterministic algorithms and their results, that is, those that have several ways of processing the same input data. In the BFT world there are also protocols such as Cross Fault Tolerance (XFT — a simplified PBFT), Paxos and Raft. The last two are especially resilient to system failures and are called Crash Fault Tolerant (CFT).
Principle: blocks are validated if they are signed by a specific quorum of signers.
Performance: high.
DLT environment: public or private permissionless blockchain.
Finality: immediate.
Usage examples: Stellar, Ripple.
Federated Byzantine Agreement (FBA) requires neither permission nor a pre-known set of participants, unlike PBFT and other BFT variations. FBA allows anyone to join the network. Transactions in this protocol are validated by a fixed number of participants, who are selected from among those currently online.
Notably, under the FBA rules there are Gateways (gateways) and Market-Makers (market makers), which ensure the honesty and liquidity of the network. The former act as traditional banks, holding financial assets and creating their equivalent in virtual tokens. The latter maintain accounts with numerous gateways and in several currencies at once.
The researcher Sergey Popov carried out a thought experiment: what if we could avoid blocks altogether?
Principle: there are no fixed blocks, and transactions are confirmed in random order, scaling linearly.
Performance: high.
DLT environment: public permissioned non-blockchain.
Finality: probabilistic.
Usage examples: IOTA, ByteBall.
The main problem with the blockchain is its synchronous nature. Blockchains cannot be parallel. You can change the size or frequency of blocks, as well as the participants who validate them, but in the end the entire history of events is locked into a strictly linear sequence. As an alternative, Directed Acyclic Graph (DAG) technology is asynchronous, which gives the competitive advantage of simultaneous events.
The protocol in such systems requires participants, in order to add one block of transactions, to confirm several previous ones. It follows that "the more new transactions there are, the faster old ones are validated." Although this implies ultra-high speeds for the network, DAG is slower at smaller scales.
Principle: nodes communicate at random using the "gossip about gossip" protocol and agree on consensus after a certain round of communication.
Performance: very high.
DLT environment: private permissioned non-blockchain.
Finality: depends on the round.
Usage examples: HashGraph.
The developers of this protocol claim that the blockchain is an outdated system. As a replacement, they also advocate the DAG concept. However, the key difference of HashGraph is the "gossip about gossip" protocol, in which a node receives a set of timestamped transactions that another node "knows" about. For such an algorithm to work, all participants in the network must be known. As a result of synchronization, each node stores all the information and the history of how that information was received by all nodes of the network. As soon as a node sees in its history that a particular message has already been received and verified by the majority, there is no doubt that it is valid.
However, there are certain limitations. First, there is little evidence of practical implementation at large scale, especially compared with working blockchain projects. Second, HashGraph technology is patented, and acquiring a license costs money. This also leads to the third issue: the lack of a strong community (such as those associated with open-source projects). Such a community can verify the reliability of the protocol, its vulnerability to hackers, and compatibility problems.
Note: the project was recently updated and renamed Hedera Hashgraph. Some of its developments are now available on GitHub.
As if that were not enough, people have developed the technology and their imagination even further. More and more blockchain researchers and developers are experimenting with new consensus models for various business tasks.
Principle: a hybrid of PoW and PoS.
Performance: low.
DLT environment: public permissionless blockchain.
Finality: probabilistic.
Usage examples: Decred.
Proof-of-Activity (PoA) combines the PoW and PoS protocols, which means that participants can both mine and stake in order to validate blocks. Thus the PoA protocol provides a balance between miners and ordinary network participants.
Principle: beacons are used to detect a node in a synchronized state and then timestamp its presence.
Performance: medium.
DLT environment: public permissionless blockchain.
Finality: immediate.
Usage examples: FOAM, Platin.
Proof-of-Location (PoL) allows users to claim a specific GPS location and thereby authenticate themselves in the network. Interestingly, the protocol relies on BFT beacons, which record geolocation and time markers on the blockchain, which prevents failures and fraud in the system.
Principle: like PoS, but with additional properties that affect your rating.
Performance: high.
DLT environment: public permissionless blockchain.
Finality: probabilistic.
Usage examples: NEM.
The Proof-of-Importance (PoI) (proof of importance) consensus algorithm acts almost like PoS, but includes three components:
Although the first parameter plays an important role in the rating for validating transactions, the second and third parameters are fairly weak, yet still help establish the "importance" of an account. The smaller the amount of tokens, the stronger the influence of the other parameters.
Consequently, an account that stakes hundreds of thousands of tokens can raise its significance coefficient by almost a factor of 3 thanks to its activity and constant presence in the network. On the other hand, this makes no difference for those who hold hundreds of millions of tokens in their account.
Principle: blocks are created in a trusted environment with equal periods.
Performance: medium.
DLT environment: private blockchain, permissioned and permissionless.
Finality: probabilistic.
Usage examples: Intel.
The chip maker Intel kept pace and developed its own blockchain called IntelLedger. IntelLedger's consensus algorithm is called Proof-of-Elapsed-Time (PoET), or "proof of elapsed time." Today it is present in one of the Hyperledger products.
This system is similar to Proof-of-Work but consumes far less electricity. Instead of participants solving a cryptographic puzzle, the algorithm runs in a Trusted Execution Environment (Trusted Execution Environment, TEE), such as Intel Software Guard Extensions (SGX). The PoET protocol also ensures that blocks are created randomly, but without any required work.
As its solution, Intel offers a guaranteed waiting time according to the TEE. According to the company, the PoET algorithm can be scaled to thousands of nodes and will work correctly on any Intel processor that supports SGX. However, isn't the blockchain supposed to help us avoid third parties rather than rely on them?
Consensus protocols are an integral part of distributed systems. First of all, they help achieve fairness and avoid system failures when one of the participants — a node — goes down. Second, a decentralized environment requires a solution that helps move forward and change the shared state, even in an environment where no one trusts anyone. Certain rules help achieve "consensus."
We have reviewed the most popular protocols, which are already used in dozens of projects. There are many other, more exotic protocols, such as Cross Fault Tolerance (XFT), Paxos, Sieve, Raft, Proof-of-Stake-Time (PoST) and Proof-of-Brain (PoB), which we simply could not fit into this article but will definitely describe in future publications. If you have questions, leave comments under the article.
продолжение следует...
Часть 1 Consensus Protocols in Decentralized Environments and the Byzantine Generals Problem
Comments