This article describes the Byzantine Consensus Algorithm (BCA) used in Tendermint. Based on the DLS protocol, it does not require any ‘active’ mining as in Proof-of-Work and can assure safe functioning of the network if it has at least 2/3+ (strictly more than two-thirds) of ‘honest’ network participants. Below you will find the description of this algorithm as implemented within Tendermint, the statistics of its functioning and the simulation of the algorithm for a small five-member network.
Table of contents
- Simple scheme
- Algorithm steps
- Malicious proposer
- Optimal scenario
Since the apparition of the bitcoin with its Proof-of-Work, colossal efforts have been made to find new consensus algorithms. Everything was reviewed:
- network bandwidth (hard to speak about bitcoin-Visa rivalry, having just 7 TPS vs. 4,000 TPS);
- network scaling (for instance, the data sharding problem);
- resistance to a whole new class of attacks typical for blockchain networks.
Currently, it seems to us that there are not so many projects with potentially interesting solutions to these problems. First of all, this is the Delegated-Proof-of-Stake family (BitShares, EOS, Lisk). There is also NEM with its Proof-of-Importance that claims of 4,000 TPS (in one of next articles we will surely tell about how it is possible). Tangle, created by IOTA, also deserves some attention. But in this article, we would like to give special attention to the BCA and its implementation in the Tendermint project.
We should start by telling about those who keep the network running (i. e. participate in building consensus). Unlike the aforementioned Proof-of-Work or Proof-of-Stake where anybody can become a miner at any given moment, within the BCA only the co-called validators can participate in forming the blockchain.
How does a common member of the network become a validator? It depends on a concrete implementation. In the simplest case, the validators are announced in the genesis block and their list does not change anymore (the most important is to have strictly less than one-third of Byzantine validators in the primary list!) In the case of Tendermint, a rotation of validators can easily be organised. It is enough to mark in the protocol a specific transaction that a member of the network would send in the case he or she wished to run for validator. Additionally, voting for candidates can be introduced, as in Lisk, or they can be chosen according to predetermined parametres. In the Tendermint implementation, an exact list of validators can be obtained for every block*. They are identified by their public keys, and during the voting process they use their private keys to sign messages sent to other validators or ordinary members of the network. Thus, it is always possible to identify the author of one or another vote and make sure that no outsider would participate in building consensus.
*The primary list of validators is contained in the genesis file; transactions that modify the list of validators are no different from other transactions, therefore they are also preserved in the blockchain and available to all the participants of the network when they wish to receive the current list of validators.
Let us start with an abstract description of what happens in the algorithm during the search for the N block.
NewHeight -> (Propose -> Prevote -> Precommit)+ -> Commit -> NewHeight ->...
Propose – a proposer* proposes his or her version of block at the N height.
Prevote – on this stage, each of the validators gives his or her assessment of the block. In the simplest case, the validator will send to the network a message “Received the block , agree with everything”.
Precommit – after some time, allocated for the Prevote step, every validator verifies how many Prevote messages from other participants he already received. It their number amounts to more than two-thirds of the total number of validators, the validator sends a Precommit transaction.
Three steps in the brackets (Propose -> Prevote -> Precommit) form a round. It is needed because in many cases for some reason the new block was impossible to find. For instance, the chosen proposer could be offline or could knowingly propose an incorrect block (this case is described in detail below).
In such a case, two changes are made in the process of building consensus:
- A new proposer is chosen.
- Every step has some duration (nominally, the Prevote step lasts for 5 seconds, then all the participants switch to a Precommit. As there is a high probability of problems because of weak connection (for instance, the proposer has a weak Internet connection, he did not have the time to download the block and distribute it to the network), the duration of every step increases by a certain constant.
Below you can see the illustration of the whole process from the official documents of Tendermint:
* It is important to mention that the proposers are selected by the robin-robin algorithm from the list of validators in proportion to their weight**. This is a reason of two interesting features: first of all, the determinancy we require (every member of the network should have the opportunity to know clearly which validator would become a proposer in the current round). At the same time, we have a pseudorandom choice that would allow to wind down the attacks related to the fact that the sequence of proposers is known in advance.
** It is up to the developer of the protocol to decide what is the weight. In the simplest case, each validator can be given similar weight, making the selection of proposers even.
In this section, we illustrated the functioning of the algorithm in layman’s terms in two cases – when something is wrong with the proposed block and when everything is all right. Of course, one can invent many more different possibilities and cases but these two are the principal ones and, if we understand them, we can ourselves simulate the functioning of the algorithm in other cases.
To fully understand the functioning of the algorithm, we propose to analyze its work in a ‘real’ network. To start with, let us designate the network itself:
- There are five validators: A, B, C, D, E (as you already understood, the total number of network members has no influence, in the case of BCA only the number of validators is important).
- The validator A is selected as a proposer. Moreover, I suggest making A the Byzantine validator to watch the functioning of the network at the moment when they try to compromise it.
- Every stage lasts t seconds; the work of the algorithm starts at the T time point.
Let us start creating the #X block. The first step, Propose, is t seconds long. During this time, the proposer should create a block and distribute it to the network, and it is very important to assure that other validators had the time to receive this block.
Now let us move to the Prevote step. Now the principal task of validators is to verify the block and decide if the ‘agree’ with it or not. In the latter case, B, C, D and E will share the message Prevote nil with the network, meaning that none of them agrees with the proposed block. To be more realistic, let us assume that E has a weak Internet connection and he did not receive anything during the t seconds. A (proposer also participates in voting) will send
Prevote , trying to support his incorrect block. To be more realistic, let us assume that E has a weak Internet connection and he did not receive any new messages from A, B, C, D.
In this case, the messages received at the Prevote stage look as following:
(E has a weak Internet connection and other participants do not manage to receive his messages).
The last step of the round, Precommit , is ahead. B, C, D, and E will send the message Precommit nil tо the network (because each of them has less than two-thirds of Prevote messages from the total number of validators. Let us examine the collected Precommit messages for every validator:
Evidently, there is no validator that collected more than two-thirds of Precommit messages, and, therefore, according to the diagram above, this round will finish without a creation of a new block of #X height. Important notice: every block should have these Precommit messages and their number should be at least more than two-thirds of total. So even if A decides to distribute a ‘false’ block in the network, he will not have a necessary amount of signed Precommit messages, and, therefore, every participant will immediately see that something is wrong.
As you have already understood, in the round described above a new block was not created. It means that before the beginning of the next round the proposer will select another validator (let it be B) and the length of steps will slightly increase to level the effects of slow connection. It means that the validator E would not stand aside because of his weak Internet connection anymore and will fully participate in this round.
Again, we start with the Propose step. Now, the block is perfectly valid and had the time to reach all the validators. So let us switch immediately to the Prevote step and watch the lists of Prevote messages collected by each validator. To make it more interesting, let us assume that A is still malicious and will now try to hamper the block creation.
It can be seen that each validator has enough Prevote messages to send a Precommit message. To make it more interesting, let us assume that A will send the Precommit nil message though it is formally incorrect for him.
In any case, we see that it did not cause any problems to other participants and they have more than two-thirds of Precommit messages to create a new block.
I hope that you found the article useful, seeing you have read it as far as here 🙂 Now few more words about Tendermint: in the nearest future, we will publish at least three articles about this wonderful technology. The first will be a kind of overview of the whole project and its capacities. As for the second, it would show in maximum detail the process of creation of one’s own blockchain (no ICO, we promise!) on the base of the connection Tendermint + Python 3.