Geekly Articles each Day
📜 ⬆️ ⬇️

Analysis of the consensus algorithm in Tendermint

tendermint_logo


This article describes the BCA consensus algorithm (Byzantine Consensus Algorithm) used in Tendermint. Developed on the basis of the DLS protocol, it does not require any "active" mining, as in Proof-of-Work, and can ensure the safe operation of the network with at least 2/3 + (strictly more than two thirds) "honest" network participants. Below is a story about how this algorithm is implemented in Tendermint, shows the statistics of its work and simulates the behavior of the algorithm on a small network of five participants.


Table of contents



Introduction


Since the advent of Bitcoin, enormous work has been done on its Proof-of-Work to find new consensus algorithms. All has undergone to revision:



At the moment, it seems to us, there are not many projects with potentially interesting solutions for these problems. First of all, this is of course the Delegated-Proof-of-Stake family (BitShares, EOS, Lisk). In addition, there is NEM with Proof-of-Importance and declared 4000 TPS (we will definitely tell about how this is possible in one of the following articles). The tangle created in IOTA deserves some attention. But in this article we would like to focus on the BCA algorithm and its implementation in the Tendermint project.


Validators


First of all, you need to talk about those who support the network in working condition (that is, it participates in building consensus). Unlike the same Proof-of-Work or Proof-of-Stake, where anyone can become a miner at any time, in the BCA only the so-called validators can take part in the formation of the blockchain.


How a regular network participant becomes a validator depends on the specific implementation. In the simplest case, validators are declared in the genesis block and in the future their list does not change (the main thing is that the initial list of design validators is strictly less than 1/3!). In the same Tendermint, you can easily implement a rotation of validators. To do this, it is enough to indicate in the protocol a special transaction that will be sent by the participant if he wants to "run". In addition, it is possible, like within the same Lisk, to enter a vote for candidates or to select them according to some existing parameters.


In the implementation of Tendermint, for any block you can always get an accurate list of validators *. They are identified by their public keys, and in the voting process they sign with the corresponding private keys messages sent to other validators and regular members of the network. Thus, you can always determine the author of a voice and be sure that no one “from the side” can take part in building a consensus.



* The initial list is specified in the genesis file; Transactions that change the list of validators are the same transactions as any others, which means they are also saved in the blockchain and are available to all network members to get the current list of validators.


Simple scheme


Let's start with an abstract description of what happens in the algorithm, at the time of searching for block N.


NewHeight -> (Propose -> Prevote -> Precommit)+ -> Commit -> NewHeight ->...

Propose - some proposer * offers its version of the block to the height N.


Prevote - at this step, each of the validators gives their "estimated opinion" to the block. In the simplest case, the validator will send a message like "Received block <block hash> to the network, I agree with everything".


Precommit - after some time allocated to the Prevote step, each validator checks how many Prevote messages have accumulated from other participants. If there are Precommit + of the total number of validators, then the validator sends a transaction to Precommit .


Three steps in parentheses (Propose -> Prevote -> Precommit) - this is the so-called round . Its essence is that there are many cases where for some reason it was not possible to find a new unit. For example, the selected proposer could be offline or could offer a deliberately incorrect block (this case is described in detail below).


In this case, two changes are made to the consensus building process:



The following is an illustration of the entire process from the official Tendermint documentation:


alogorithm



* It is important to note that the proposer are selected by the round-robin algorithm from the list of validators in proportion to their weight **. This gives two interesting properties: first of all, we need determinism (each network participant should be able to uniquely know which of the validators will become a proposer in this round). But at the same time, we have a pseudo-random choice, which will allow to negate the attacks associated with the previously known sequence of proposer-s in the selection process.


** What weight is - to decide the protocol developer. In the simplest case, you can give all validators the same weight, that is, the choice of proposer will be uniform.


Algorithm steps


In this section, I illustrated the work of the algorithm "on the fingers" in two cases - when there is something wrong with the proposed block and when everything is fine with it. Of course, there are many more branches and cases that can be invented, but these two are basic and, having understood them, you can independently model the behavior of the algorithm in the remaining cases.


Malicious proposer


For a complete understanding of the algorithm, I propose to parse its work on the "real" network. First, let's set the network itself:



So, let's start creating the #X block. The first step is the Propose step, with a duration of t seconds, during which the proposer must create a block and “scatter” it over the network, and it is extremely important that other validators have time to get this block.


propose


We now turn to Prevote . Now, the main task of validators is to check the block and decide whether they "agree" with it or not. In this case, B , C , D , E will send Prevote nil message over the network - it means that none of them agree with the proposed block. For greater realism, suppose that E has a bad Internet and has not received anything at all in t seconds. A (proposer also participates in the voting!) Prevote send Prevote , in an attempt to maintain its incorrect block. For greater realism, let E have a bad Internet as usual and he did not receive any new messages from A , B , C , D at all .


prevote_start


Then the messages received in the Prevote step for each validator are as follows:


prevote_end


Let me explain that E has a bad Internet and other participants do not have time to receive messages from him at all.


Remained the final step of the round - Precommit . B , C , D , E will Precommit nil message to the Precommit nil network (because the number of Prevote messages in each of them is less than Prevote + the number of validators). Let's look at the collected Precommit messages for each validator:


precommit_end


Obviously, there are no validators that would collect Precommit + Precommit messages, which means, according to the scheme above, this round will be completed without creating a new height block #X . Important note - in each block there should be these same Precommit messages and, obviously, there should be at least Precommit +. Therefore, even if A wants to scatter a “false” block over the network, then it will not have the necessary number of messages signed by Precommit , which means that any participant will instantly notice a trick.


Optimal scenario


As you already understood, in the round described above, it was not possible to create a new block. This means that before the start of the next round, the other validator will be chosen by the proposer (let it be B ) and the length of the steps is slightly increased in order to level the effect of a slow connection. So in this round, the validator E will no longer stand aside because of the bad Internet, but will fully participate.


Again, we start with the Propose step, and this time the block is completely valid and managed to reach all validators. Therefore, I suggest that you immediately switch to the Prevote step and see what the list of Prevote messages look like for each validator. For more interest, let's assume that A is still malicious, so this time it will try to prevent the creation of the block.


prevote_end_optimal


It can be seen that all validators have enough Prevote messages to send Precommit messages. Again, for the sake of interest, suppose that A sends a message to Precommit nil , although this is formally wrong on his part.


precommit_end_o


In any case, we see that this did not create problems for other participants and they have Precommit + Precommit messages in order to create a new block.


Conclusion


I hope that the article was useful to you, since you have read it to this point :) A few more words about the Tendermint - in the near future we will publish at least three articles about this wonderful technology. The first will be some overview of the whole project and its capabilities. And in the second, the process of creating your blockchain (no ICO, we promise!) On the Tendermint + Python 3 bundle will be demonstrated in as much detail as possible.


Links



')

Source: https://habr.com/ru/post/350012/

More articles:


All Articles