Exonum consensus: how it works
Exonum TM is our open framework for creating private blockchains. Today we will tell how his consensus algorithm works.
Image: Bitfury
Before turning to the story of how the Exonum TM consensus algorithm works, let's talk about why we need these algorithms in blockchains altogether.
Blockchain is a distributed system without a central administrator. To agree on the order of blocks (and, accordingly, transactions) network participants use special consensus algorithms. The task of consensus is to help the peer-to-peer nodes to come to a common opinion about what its new state should be - that is, choose the next block in the blockchain chain.
This is necessary in order to protect the blockchain and the information stored in it from being substituted. For example, the blockchain on the basis of Exonum TM , implemented for Russian Railways, records information about operations with details for cars and trains. Knowing that consensus ensures the accuracy of the data in the block, the company can follow the route of spare parts from the supplier and timely detect forgery. More about this and other cases, we will continue.
Speaking of consensus, one of the first to come to mind is the Bitcoin-blockchain with its proof-of-work (PoW) algorithm. It requires the participants (miners) to perform complex mathematical operations for the selection of the block hash and the expenditure of computing system resources. Thus, the participants of the Bitcoin network support its work by investing their own material resources. Under such conditions, unfair online activity becomes unprofitable and costly.
But despite the fact that Bitcoin is considered the most reliable of the existing distributed systems, its consensus cannot solve the problem of Byzantine node behavior . By Byzantine behavior, we understand malicious activity that could disrupt the operation of the consensus algorithm. Such activities also include situations where nodes lose contact with the network or go offline.
Back in the mid-80s, it was proved that, in order to ensure the sustainability of a distributed system, it must work under partial synchronism. In this case, the algorithm of consensus must have the following criteria:
For a distributed network with a known number of participants, the most optimal consensus model is BFT ( byzantine fault tolerance ). It satisfies the requirements of partial synchronization of nodes and is able to maintain a stable network even if a third of its members are compromised. For these reasons, it is the BFT model that formed the basis of the Exonum TM consensus algorithm .
There are three types of nodes in the Exonum blockchain: validators, auditors and light clients. The first ones check the validity of transactions in new blocks, and the second - distribute the load on the network and control the work of validators. As for light clients, they only provide network members with the opportunity to send transactions to the blockchain. Light clients and auditors are not directly involved in the consensus algorithm, so we will not talk about them within the framework of this material.
The task of validators is to vote for the inclusion of new blocks in the blockchain. As we said above, the Exonum TM network can function stably even if a third of all the nodes are Byzantine. Accordingly, to achieve consensus, the block must approve 2/3 of the blockchain network nodes. And this statement can be confirmed mathematically.
Suppose that there are h honest honest and f Byzantine nodes (faulty) in the network. Then the total number of validators can be represented as N = h + f. All validators vote for one of the two presented blocks, while they collect the votes of other participants and decide on the winner based on the threshold rule.
At the end of the vote, each validator independently decides which of the two candidates has won. However, validators may not decide who to vote for, if too few validators send their votes to the rest. This can happen if Byzantine knots begin to send votes for different candidates to honest members of the network, trying to confuse them.
To rule out such a situation, two conditions must be met:
As a result, we obtain the following chain of inequalities: h> 2f, α> 2/3, and N ≥ 3f + 1. It follows that to confirm the block of transactions, it must receive two thirds of the validators.
Next, let's talk about how the validators vote in the Exonum-blockchain. In general, the scheme is as follows:
The process of reaching a consensus begins with the fact that the main node - it is selected by a separate algorithm and changes regularly - forms a list of transactions that must be added to the blockchain (makes up the proposal ). This list is then broadcast throughout the network to the validator nodes.
Validators check the received message for correspondence to the serialization format. If any errors are fixed, the node completely ignores the received message. For example, the suggestion to add a block in the middle of a blockchain or re-record an already existing transaction will be ignored. If everything is in order, then the voting stage begins - the validator nodes vote to add the block to the blockchain, broadcasting the prevote message.
The node, whose offer has received two thirds of the approval from validators, is automatically blocked. This state is called proof-of-lock . The site loses the ability to vote for the proposals of other validators and cannot change its proposal .
After the required number of votes from validators is dialed, the main node enters the approved transactions into a block and transmits a special message - precommit . It contains a hash of the updated state of the blockchain and indicates that the node is ready to add the proposed block to the chain. At that moment, when most validators respond with a similar precommit message (with the same hash), the block is added to the blockchain. Consensus is reached, and the procedure is repeated for each subsequent block.
To improve the stability of the system, the validators periodically exchange two more messages - Request and Block . The first is generated if the nodes lack any transaction data. The second is needed to transfer information about a block of transactions to a node that is behind in time (for example, turned off), to synchronize the work of the entire network.
To evaluate the consensus possibilities, we checked the work of the blockchain on the basis of two configurations: in one data center and several geographically distributed data centers. During tests, the TPS parameter — the number of transactions per second — was estimated for different numbers of validators. Next, we present graphs of network performance changes in blockchains for working with cryptocurrencies (black graph) and timestamps - timestamping (blue graph).
TPS as a function of the number of validators in the case of a single data center
TPS as a function of the number of validators in the case of multiple data centers
On average, the Exonum blockchain was able to process from 2 to 13 thousand transactions per second, depending on the network configuration.
The Exonum TM framework is used today in a variety of projects. Last summer, together with Technoprom, we created a special marketplace for Russian Railways. In the Exonum-blockchain, operations with details for trains and the data sheets of each car are recorded. This makes it possible to track the movement of all parts from official suppliers and detect forgeries.
We also launched an educational blockchain project based on Synergy University. The registry registers and stores all information about student performance: grades, exam results and diplomas. According to our colleagues, this approach eliminates the possibility of making changes to the documents on education and helps to save on their archiving and certification.
Even on the basis of Exonum TM we have implemented a series of pilot projects that accelerate the development and release of software. Our partners from the engineering organization Aricent tested the framework for six months. The blockchain approach to software development has increased programmer productivity and error correction.
We started another project together with a group of medical companies. Including with a startup Insillico, where they apply deep training to search for new drugs. Exonum will be the core of the ecosystem for sharing patient data. The system will simplify clinical trials, as well as help with the analysis of medical records and DNA of patients. As a result, doctors will be able to more quickly diagnose diseases and prescribe a more effective treatment.
We hope that our blockchain will find application in other tasks and in other industries. We are currently working to integrate Exonum TM into systems for voting, auctions and digital rights management. Demo some solutions are on the official site .
Image: Bitfury
Why do we need consensus algorithms
Before turning to the story of how the Exonum TM consensus algorithm works, let's talk about why we need these algorithms in blockchains altogether.
Blockchain is a distributed system without a central administrator. To agree on the order of blocks (and, accordingly, transactions) network participants use special consensus algorithms. The task of consensus is to help the peer-to-peer nodes to come to a common opinion about what its new state should be - that is, choose the next block in the blockchain chain.
This is necessary in order to protect the blockchain and the information stored in it from being substituted. For example, the blockchain on the basis of Exonum TM , implemented for Russian Railways, records information about operations with details for cars and trains. Knowing that consensus ensures the accuracy of the data in the block, the company can follow the route of spare parts from the supplier and timely detect forgery. More about this and other cases, we will continue.
What tasks we solved, creating an algorithm of consensus Exonum
Speaking of consensus, one of the first to come to mind is the Bitcoin-blockchain with its proof-of-work (PoW) algorithm. It requires the participants (miners) to perform complex mathematical operations for the selection of the block hash and the expenditure of computing system resources. Thus, the participants of the Bitcoin network support its work by investing their own material resources. Under such conditions, unfair online activity becomes unprofitable and costly.
But despite the fact that Bitcoin is considered the most reliable of the existing distributed systems, its consensus cannot solve the problem of Byzantine node behavior . By Byzantine behavior, we understand malicious activity that could disrupt the operation of the consensus algorithm. Such activities also include situations where nodes lose contact with the network or go offline.
Back in the mid-80s, it was proved that, in order to ensure the sustainability of a distributed system, it must work under partial synchronism. In this case, the algorithm of consensus must have the following criteria:
- Liveness - should be able to take a new block at any time.
- Consistency - the transaction database on all nodes of the network must be identical.
- Censorship resistance - the nodes should not give preference to any transactions or ignore them.
For a distributed network with a known number of participants, the most optimal consensus model is BFT ( byzantine fault tolerance ). It satisfies the requirements of partial synchronization of nodes and is able to maintain a stable network even if a third of its members are compromised. For these reasons, it is the BFT model that formed the basis of the Exonum TM consensus algorithm .
How the Exonum Consensus Algorithm Works
There are three types of nodes in the Exonum blockchain: validators, auditors and light clients. The first ones check the validity of transactions in new blocks, and the second - distribute the load on the network and control the work of validators. As for light clients, they only provide network members with the opportunity to send transactions to the blockchain. Light clients and auditors are not directly involved in the consensus algorithm, so we will not talk about them within the framework of this material.
The task of validators is to vote for the inclusion of new blocks in the blockchain. As we said above, the Exonum TM network can function stably even if a third of all the nodes are Byzantine. Accordingly, to achieve consensus, the block must approve 2/3 of the blockchain network nodes. And this statement can be confirmed mathematically.
Suppose that there are h honest honest and f Byzantine nodes (faulty) in the network. Then the total number of validators can be represented as N = h + f. All validators vote for one of the two presented blocks, while they collect the votes of other participants and decide on the winner based on the threshold rule.
It says: the number of votes for the winner must be greater than or equal to α * N , where α is a number in the range from 0 to 1. Thus, an absolute majority of votes is achieved for α> 1/2.
At the end of the vote, each validator independently decides which of the two candidates has won. However, validators may not decide who to vote for, if too few validators send their votes to the rest. This can happen if Byzantine knots begin to send votes for different candidates to honest members of the network, trying to confuse them.
To rule out such a situation, two conditions must be met:
- Honest validators should be able to make a choice without the participation of Byzantine knots. This condition is determined by the liveness property, which we talked about above. Mathematically, it is expressed by the following inequality: h ≥ α * N.
- A candidate voted for by a minority of honest validators cannot overcome the threshold in α * N. This is dictated by the consistency criterion. The condition is expressed as: [h / 2] + f <α * N, where [h / 2] is the integer part of the number h / 2.
As a result, we obtain the following chain of inequalities: h> 2f, α> 2/3, and N ≥ 3f + 1. It follows that to confirm the block of transactions, it must receive two thirds of the validators.
Next, let's talk about how the validators vote in the Exonum-blockchain. In general, the scheme is as follows:
The process of reaching a consensus begins with the fact that the main node - it is selected by a separate algorithm and changes regularly - forms a list of transactions that must be added to the blockchain (makes up the proposal ). This list is then broadcast throughout the network to the validator nodes.
Validators check the received message for correspondence to the serialization format. If any errors are fixed, the node completely ignores the received message. For example, the suggestion to add a block in the middle of a blockchain or re-record an already existing transaction will be ignored. If everything is in order, then the voting stage begins - the validator nodes vote to add the block to the blockchain, broadcasting the prevote message.
The node, whose offer has received two thirds of the approval from validators, is automatically blocked. This state is called proof-of-lock . The site loses the ability to vote for the proposals of other validators and cannot change its proposal .
After the required number of votes from validators is dialed, the main node enters the approved transactions into a block and transmits a special message - precommit . It contains a hash of the updated state of the blockchain and indicates that the node is ready to add the proposed block to the chain. At that moment, when most validators respond with a similar precommit message (with the same hash), the block is added to the blockchain. Consensus is reached, and the procedure is repeated for each subsequent block.
To improve the stability of the system, the validators periodically exchange two more messages - Request and Block . The first is generated if the nodes lack any transaction data. The second is needed to transfer information about a block of transactions to a node that is behind in time (for example, turned off), to synchronize the work of the entire network.
To evaluate the consensus possibilities, we checked the work of the blockchain on the basis of two configurations: in one data center and several geographically distributed data centers. During tests, the TPS parameter — the number of transactions per second — was estimated for different numbers of validators. Next, we present graphs of network performance changes in blockchains for working with cryptocurrencies (black graph) and timestamps - timestamping (blue graph).
TPS as a function of the number of validators in the case of a single data center
TPS as a function of the number of validators in the case of multiple data centers
On average, the Exonum blockchain was able to process from 2 to 13 thousand transactions per second, depending on the network configuration.
Where is Exonum already used?
The Exonum TM framework is used today in a variety of projects. Last summer, together with Technoprom, we created a special marketplace for Russian Railways. In the Exonum-blockchain, operations with details for trains and the data sheets of each car are recorded. This makes it possible to track the movement of all parts from official suppliers and detect forgeries.
We also launched an educational blockchain project based on Synergy University. The registry registers and stores all information about student performance: grades, exam results and diplomas. According to our colleagues, this approach eliminates the possibility of making changes to the documents on education and helps to save on their archiving and certification.
Even on the basis of Exonum TM we have implemented a series of pilot projects that accelerate the development and release of software. Our partners from the engineering organization Aricent tested the framework for six months. The blockchain approach to software development has increased programmer productivity and error correction.
We started another project together with a group of medical companies. Including with a startup Insillico, where they apply deep training to search for new drugs. Exonum will be the core of the ecosystem for sharing patient data. The system will simplify clinical trials, as well as help with the analysis of medical records and DNA of patients. As a result, doctors will be able to more quickly diagnose diseases and prescribe a more effective treatment.
We hope that our blockchain will find application in other tasks and in other industries. We are currently working to integrate Exonum TM into systems for voting, auctions and digital rights management. Demo some solutions are on the official site .
Source: https://habr.com/ru/post/440586/