Polkadot series (2) -- detailed explanation of mixed consensus

{"type":"doc","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":" The author of this article "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Xia Liwei , Tao Yongxing  "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" From interesting chain technology data grid lab BitXHub The team , Mainly responsible for the research work related to the Interoperability Technology of blockchain ledger ."}]},{"type":"horizontalrule"},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":" Reading guide "},{"type":"text","text":"： This article is Polkadot Series article No 2 piece ,Polkadot A detailed explanation of the mixed consensus of . When speaking of Polkadot When the consensus of , The first reaction of many people is Polkadot There are a lot of consensus algorithms , There are a lot of new nouns , because Polkadot There are many consensus algorithms 、 Different function , A lot of people Polkadot The consensus algorithm used has a lot of questions , One of the most confusing is how to cooperate among different consensus algorithms , The next part of this paper is about Polkadot In depth analysis of the consensus ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":"center","origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"Polkadot There are three main types of consensus "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":"center","origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"NPOS, BABE, GRANDPA"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":"center","origin":null},"content":[{"type":"text","text":" Next, we will explain these three kinds of consensus one by one "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":"center","origin":null},"content":[{"type":"text","marks":[{"type":"size","attrs":{"size":22}},{"type":"strong"}],"text":"NPOS"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"size","attrs":{"size":16}},{"type":"strong"}],"text":" What is? NPOS Consensus "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" stay Polkadot in , The verifier on the relay chain needs to be assigned to each parallel chain , Provide them with blockchain verification capabilities , yes Polkadot Share part of security , Therefore, the verifier of the relay chain is responsible for Polkadot The security of multi chain system is very important ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" How to fairly and safely elect the verifier on the relay chain has become the first step to ensure the sharing security of the whole system , Is an indispensable step ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"NPOS( Nominated Proof of Stake) Consensus algorithm is used to elect the system to make it more secure , A more efficient set of verifiers . And in the traditional sense POS Compared with consensus ,NPOS The algorithm combines Polkadot Some characteristics of the chain's own architecture , Optimize accordingly ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Let's see below. NPOS How it works ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" In explanation NPOS Before , We need to review it first Polkadot Two important roles in ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"▲  The verifier "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The whole node of the relay chain , The relay chain assigns verifiers to different parallel chains through random grouping in the verifier pool . The verifier will accept the block from the collector and verify its validity , Then combined with the consensus algorithm to confirm the block submitted by the collector ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"▲  Nominee "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"Polkadot Middle digital currency DOT The holder of , It will choose the verifier that it trusts DOT pledge , And then share the benefits of the verifier ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"Polkadot The election model of "},{"type":"text","text":" It's based on these two roles . To be a verifier , You have to be a verifier first. The process of running an election , And in this election process “ voter ” It's the nominees ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" stay Polkadot In the design of , In theory, the number of nominees can be unlimited , If we can get more nominees to vote , So the more money you have to get involved in the election , The whole system is more secure ; And for the verifier , For the performance of blockchain , Not too much （ If all nodes can act as verifiers , That's the model bitcoin uses ）, The number of verifiers is a fixed value determined by the system , At this point, it is similar to POS Consensus is consensus ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"size","attrs":{"size":16}},{"type":"strong"}],"text":" The election model "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" To clarify the issue of elections ,Polkadot The problem of the set of election verifiers is abstracted as a mathematical election problem ："}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"▲ "},{"type":"text","marks":[{"type":"strong"}],"text":" problem ："},{"type":"text","text":"m Voters are right about n In the case of candidates , Choose the final t For the elected "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"（ notes ： The nominees can have any one , There are a limited number of verifiers ）"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The description of the problem is simple , But how to make the system more secure , There will be different strategies .Polkadot In the design philosophy of , Think the election strategy needs to meet the following “ The three principles ”："}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"Balance:"},{"type":"text","text":"  The proportion of verifiers at the time of block production is the same , So the strategy is Stake Distribution needs to be as even as possible , Keep the network safe ;"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"Support: "},{"type":"text","text":" The strategy needs to make as many Stake Money is involved . Because the nominator is only responsible for choosing which candidates to vote for , But for Stake It's not up to you to decide how much to assign to which verifier , This part is NPOS The algorithm is determined by calculation . This is also NPOS And ordinary POS There's a big difference in the consensus ;"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"Fair representation: "},{"type":"text","text":"Stake Verifiers with more nominees voting are more likely to appear in the verifier set ."}]},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Input ： Given , Where is Nominator aggregate , yes Validator The candidate pool , It's a collection of sides , It means that the nominator has voted for the candidate . At the same time, give the directional quantity , Each of the nominees has its own Stake Number , Is the size of the selected set of final verifiers ."}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"  Output ： Given the solution , Among them is the final choice Validator, The size is ,  It's how much the nominees allocate Stake To the end Validator."}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Limiting conditions ："}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"Balance: Given , Be able to give a  , Make the smallest "}]}]},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"Support: Given , Be able to give a  , Make the biggest of "}]}]}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"Fair representation: proportional justified representation(PJR) The rules "}]},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"  Any one , There won't be a subset of nominees , This leads to the following situation ："}]}]}]},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/62/62448720e97467a3327a77bfa0e9d495.jpeg","alt":null,"title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" In more popular terms, it is not allowed to appear ： There are some of the nominees stake More than the total staking The specific gravity of , And they support more than one person , But they support Validator But not more than ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The above problem is mathematically an optimization problem , Unfortunately, this election has proved mathematically to be NP Problem completely , We can't get the optimal solution in polynomial time ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" therefore Polkadot Give your own set of solutions , To get around this difficult problem ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"size","attrs":{"size":16}},{"type":"strong"}],"text":"NPOS technological process "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" In the mathematical model derived above , Because it is NP Problem completely , In other words, the computational time complexity of the optimal solution can not be determined in polynomial time ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"Polkadot A relatively feasible scheme is given ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Don't pursue the optimal solution , To reach the relative optimum NP It is difficult to give a feasible solution to a complete problem , But it is simple to verify the existing solution , Can be complete in polynomial time . So the part of verifying the feasible solution is on the chain ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"▲  The complete process is as follows ："}]},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/34/343212490a6a25b60e059bc7974e2883.png","alt":null,"title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" After the nominees have given their vote , Each candidate can give his own feasible solution to the above election problem ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" In the above set of feasible solutions , Compare alternatives with alternatives on the chain , According to the previous “ The three principles ” To compare these options , The best scheme is chosen as the final verifier election result , This completes a round of elections ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":"center","origin":null},"content":[{"type":"text","marks":[{"type":"size","attrs":{"size":22}},{"type":"strong"}],"text":"BABE"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"BABE The full name is Blind Assignment for Blockchain Extension,BABE It's an engine for making blocks , Be similar to Ourobros Praos, A kind of PoS The agreement .BABE The algorithm is based on slots Of ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" stay Polkadot Every one of them slot almost 6 Seconds of time ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Every slot In the time period BABE Will choose one leader Come and make a piece ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"BABE in leader The election of a random function （VRF） To achieve , At every slot Stage , Each node will be calculated by VRF Function to get a number , If this value is less than the predetermined threshold in the network , Then nodes will think that they are in this period of time leader, So the nodes start to block ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" It is worth noting that in the above process , because VRF Functions generate numbers randomly , So it may be caused in some slot There is no leader Or have multiple nodes work out their own VRF The value is less than the threshold, which results in multiple leader The situation of . We analyze two cases in turn ："}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" When there is no leader When it comes into being ,Polkadot According to the rules, who is leader, The order is predetermined ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" When there are more than one leader When ,Polkadot Allow multiple nodes to submit blocks , The final block is confirmed by GRANDPA To decide ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":"center","origin":null},"content":[{"type":"text","marks":[{"type":"size","attrs":{"size":22}},{"type":"strong"}],"text":"GRANDPA"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"GRANDPA It is used for block confirmation , In the second part of the article, we mentioned BABE Will be right Polkadot To make a block out of a deal , So these blocks are finally made by GRANDPA To determine the ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Like other PBFT The derivation algorithm is the same as ,GRANDPA The time complexity of "},{"type":"text","marks":[{"type":"italic"},{"type":"strong"}],"text":"O(n²)"},{"type":"text","text":". however Polkadot The reason why GRANDPA Because GRANDPA Not just one block at a time , It identifies several blocks at a time to confirm "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"italic"}],"text":"Idle(24peers),best:#664257(0x706c…76b7),finalized#664253"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"italic"}],"text":"(0xe4ab…4d2a)"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"italic"}],"text":"Imported#664258(0xee71…6321)"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"italic"}],"text":"Idle(24peers),best:#664258(0xee71…6321),finalized#664256"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"italic"}],"text":"(0x809a…a5d8)"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" It's on it Polkadot A log of the test network , You can see a confirmation block height from 664253 here we are 664256, therefore GRANDPA Three blocks have been identified at one time . In this way, it's better to confirm only one at a time ,GRANDPA Is more efficient than the others PBFT The derivation algorithm of is much higher ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong"}],"text":"▲ "},{"type":"text","text":" So let's talk about that "},{"type":"text","marks":[{"type":"strong"}],"text":"GRANDPA The specific process of "},{"type":"text","text":"："}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"1. A master node broadcasts the block height after the previous round of confirmation ;"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"2. Wait for the network to delay , Each node broadcasts the highest block they think can be confirmed （pre-vote）;"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"3. Each node pairs steps 2 The received block set is calculated , Figure out the highest block they think can be identified , And broadcast the results (pre-commit);"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"4. When the node receives enough pre-commit After the block can be confirmed, the message will be formed commit The news of , It is generally believed that it is greater than 2/3 It can be confirmed ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The above is GRANDPA Confirm the main flow of the block ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" What we need to worry about is the steps 2 Of pre-vote In the process, some malicious nodes may vote two blocks and broadcast them out , In this way, it is possible to produce chain bifurcation behavior ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"Polkadot In order to prevent this from happening, we use a method called "},{"type":"text","marks":[{"type":"strong"}],"text":"Account Safety"},{"type":"text","text":" The way ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" If there's something to fork out in the network commit Information ,Polkadot The node will immediately take Account Safety The mechanism of . Each node asks the other nodes what they see pre-vote The situation of , Nodes will respond to the messages they receive , In this way, it is easy to detect which malicious nodes have cast two blocks . In the end, these caught evil nodes will be kicked out of the consensus network , Never get into ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Let's go back to BABE, By combining BABE and GRANDPA We can see that when the block comes out Polkadot use BABE Block out , At this time, the nodes only need to send block information once , So the time complexity is just "},{"type":"text","marks":[{"type":"italic"},{"type":"strong"}],"text":"O(n)"},{"type":"text","text":", After the block is out, the nodes are used again GRANDPA Do block validation , At this time, because the nodes in the confirmation stage need to be confirmed twice to ensure the consistency of the result of the confirmation block , The time complexity is "},{"type":"text","marks":[{"type":"italic"},{"type":"strong"}],"text":"O(n²)"},{"type":"text","text":", However, due to multiple blocks to confirm at one time , So the hybrid consensus of the two is very efficient , Than ordinary PBFT Consensus is much more efficient ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":"center","origin":null},"content":[{"type":"text","marks":[{"type":"size","attrs":{"size":22}},{"type":"strong"}],"text":" Conclusion "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The above three are what we introduce to you Polkadot The consensus algorithm , You can see NPOS It's mainly to choose Polkadot The consensus node of ,BABE and GRANDPA Through mixing to efficiently block and confirm the blockchain ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" This mixed consensus is more than the traditional PBFT Consensus is faster , And on the basis of faster speed, there is no loss of security . It is worth learning from the blockchain consensus to separate the two phases of block out and block confirmation and use different algorithms ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Through these three algorithms ,Polkadot It can be said that, to a certain extent, it is efficient to achieve Polkadot The consensus algorithm of the upper blockchain ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" reference ："}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"[1] Ouroboros Praos: An adaptively-secure, semi-synchronous proof-of-stake blockchain Bernardo David , Peter Gaˇzi , Aggelos Kiayias November 14, 2017"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":"br"}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}}]}