Shulou(Shulou.com)05/31 Report--

This article is to share with you about Bystack's high TPS consensus algorithm. The editor thinks it is very practical, so I share it with you to learn. I hope you can get something after reading this article.

Consensus algorithm is a method to ensure the state consistency of node data in distributed systems. Consensus algorithms in block chain can be divided into two categories: POW (workload proof) and POS (rights and interests proof). The first type of POW model is the most widely used consensus algorithm in public chain projects. The 10-year operation of Bitcoin has fully proved the security and stability of POW. The feature of POW is to maximize decentralization and security at the expense of performance. For example, the peak TPS of Bitcoin is 3.87. on average, it takes 10 minutes for each transaction to be packaged into blocks; the peak TPS of Bitcoin is 36.32, and it takes 2.5 minutes for each transaction to be packaged into blocks. The second type of POS mode is to select block consensus nodes through algorithms, which are mostly used in alliance chains and some new common chain projects in pursuit of high TPS. The feature of POS is to achieve optimal performance by supporting smaller outgoing block intervals, but at the expense of partial security and decentralization.

Bystack is a blockchain BaaS platform based on the main side chain architecture, which divides the blockchain into Layer1 and Layer2 layers.

Layer1 is better than the main chain of the original chain, and the POW algorithm ensures the highest level of asset security and decentralization. Layer1's TPS problem is solved by transferring assets to Layer2 through cross-chain technology.

The side chain (Layer2) uses an innovative BBFT consensus algorithm to make the TPS of a single side chain more than 20000, and the cooperation of multiple side chains can make the TPS grow linearly.

TPS = number of chunk transactions * number of chunks confirmed per second without reaching the bottleneck of node bandwidth and performance. Because the maximum number of transactions that a block can hold can be achieved by simply modifying the code parameters, increasing the number of confirmed chunks per second is the key way to improve TPS. For example, each block of the original chain can hold a maximum of about 5500 transactions, and the TPS is 36.32 on the main chain because of the POW feature of one block every 150s. However, on the side chain, if the number of blocks entering the final confirmation per second is increased to 5, the TPS can easily reach more than 25000.

The problem with DPOS

Traditional DPOS consensus algorithms such as EOS can fully support the outgoing speed of 2 blocks per second, but there is a problem waiting for final confirmation.

Because the final confirmation of a traditional DPOS block is based on the fact that all super nodes have issued at least one subblock after the block. This means that it is assumed that there are 21 super nodes, each node has 6 blocks per round, and the average time for each block is 0.5 seconds. Then it takes 60 seconds for a block to get final confirmation.

The problem with BFT

BFT-based POS because of the characteristics of BFT, all blocks can be quickly confirmed after output, but it is difficult to obtain high TPS.

The reason is that each block of BFT is divided into three states, generation, pre-final status and final confirmation status.

The change of state depends on the collection of signatures of 2max and 3 nodes, and the efficiency of signatures depends on the delay of the network. Suppose that some of the super nodes are in the United States and some in China, then the communication delay is about 200 milliseconds.

It takes a limit of at least 600 milliseconds from generation to final confirmation of that block. Therefore, in the consensus algorithm of BFT, network delay has become the bottleneck of high TPS.

DPOS BBFT consensus algorithm

Bystack consensus algorithm is a new hybrid consensus algorithm based on the characteristics of DPOS and BBFT algorithm.

Through the asynchronous mode of outgoing block and BBFT signature, the algorithm has the characteristics of high TPS and fast final confirmation at the same time. In the BBFT consensus algorithm, n consensus nodes are selected by the users of the whole network. The consensus node turns into the outgoing block node, and when the consensus node becomes the outgoing block node, it will continuously out m blocks at the speed of one block in s seconds. When the block is generated, it will be broadcast directly to the whole network.

However, the outgoing block node does not wait for the signature of the other consensus node of 2Accord 3, but continues to produce the next block based on the current block. At this time, the current block is already a legal block but has not been finally confirmed, similar to the possibility that Bitcoin did not get 6 blocks to confirm that there is a rollback. When other consensus nodes receive the block and pass the verification, the block will be signed and broadcast to the whole network, and when a block gets more than 2 big 3 signatures, it will enter the final confirmation state.

TPS

The core point of achieving high TPS is that each consensus node has m blocks in succession. Because when there is only one block per node, then the next consensus node needs to wait for the block from the previous consensus node, so we need to consider the problem caused by a network delay. If the outgoing block interval is set to be less than the network delay, there is a high probability that the consensus node will not receive the bifurcation state caused by the previous block when it leaves the block. However, when m is set to a slightly larger number, the tps can be raised to the limit of bandwidth and node performance.

Let's say that when masking 20

When the next consensus node comes out of the block, because the network delay did not receive the last block but received the previous 19 blocks, the node will be connected to the 19th block in the previous round. The block chain will enter the instantaneous bifurcation state, but the whole network state will be unified after two blocks according to the longest chain principle. Although the TPS of 1 block was lost

However, it ensures a high blocking rate when the outgoing block interval is less than the network delay.

Asynchronous BFT

In the design of BBFT, the outgoing block and the BFT signature of the consensus node are carried out in parallel to counteract the impact of the network delay in collecting BFT signatures on the efficiency of the outgoing block. But unlike the classical BFT algorithm, there are three states: pre-final state and final confirmation.

BBFT modifies the algorithm according to the characteristics of the block chain so that the algorithm has only one final confirmation state.

But two additional restrictions are added: the first is that fraud occurs when a consensus node signs two different blocks of the same height; the second is that fraud occurs when a consensus node signs two different blocks at the same time. Through the transformation in this way, the number of communications between consensus nodes is reduced, thus reducing the time it takes for the block to obtain final confirmation. At the same time, there are two kinds of block confirmation in BBFT: direct confirmation and indirect confirmation. The first method directly confirms that the existing block has obtained a consensus node signature of more than 2gam3. The second indirect confirmation is that a block does not get the consensus node signature of 2Mab 3, but its sub-block gets the signature of more than 2gamma 3 consensus node, and BBFT will think that the block indirectly obtains the status of final confirmation.

Disaster tolerance and fault tolerance

It supports the operation of the whole network when only a single consensus node is alive to the next round of consensus node replacement, but the block speed will decrease to 1 of the normal situation.

During this period, the user can change the vote to replace the super node, and the network will return to normal in the next round of consensus node replacement.

The network works normally when the consensus node supporting 1x3 does evil, and when the consensus node doing evil block of more than 1x3 will not be able to enter the final confirmation function for a long time until the network runs to the next round of consensus node is replaced. When more than 1 + 2 consensus nodes do evil, the malicious nodes will control the network.

Scenario Analysis of BBFT consensus Block

The following example assumes that n = 5, m = 3, s = 1, block height = 100, timestamp = 1557148900

It's time for consensus Node 3 to prepare the first block.

Perfect state

Node 3 has an exit height of 101and a timestamp of 155714890 block A, broadcast to the whole network

Block An is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

3. The exit height of Node 3 is 102and the timestamp is 155714891 Block B, broadcast to the whole network.

Block B is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

5. Node 3 exit height is 103, timestamp is 155714892 block C, broadcast to the whole network

Block C is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

Node 4 successfully receives blocks A, B, C and is in the final state, and continues to go out continuously on the basis of this chain.

The exit height of Node 4 is 104and the timestamp is 155714893 Block D, broadcast to the whole network.

When the millisecond final confirmation is reached, no rollback occurs, only when the network latency is low and the consensus node is stable.

Ideal state

Node 3 has an exit height of 101and a timestamp of 155714890 block A, broadcast to the whole network

Node 3 has an exit height of 102and a timestamp of 155714891 block B, broadcast to the whole network.

Block An is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

4. No. 3 node exit height is 103, timestamp is 155714892 block C, broadcast to the whole network

Block B is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

Node 4 successfully received blocks A, B, C, but only A

B is in the final confirmation state and continues to block continuously on the basis of this chain.

The exit height of Node 4 is 104and the timestamp is 155714893 Block D, broadcast to the whole network.

Block C is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

The final confirmation is reached in seconds, and no rollback occurs, but the final confirmation is delayed due to the collection of the confirmation signature of the consensus node to the block.

However, since all blocks have been successfully passed to the next outgoing consensus node, the outgoing block will not be affected.

Outbound consensus node abnormal state

Timestamp is 155714890, no new blocks are generated

Timestamp is 155714891, no new blocks are generated

Timestamp is 155714892, no new blocks are generated

Node 4 did not receive any blocks, and the height after mining was 101.

The timestamp is 155714893 block A broadcast to the whole network

Block An is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

The final confirmation is reached in seconds, and no rollback occurs. Due to the consensus node downmachine, there are no nodes out of the block within 3 seconds. The impact is to slow down the block speed of the whole network, when the single node long-term downmachine needs to wait for the next vote, re-elect a new round of consensus nodes can be repaired.

Network delay exception 1

Node 3 has an exit height of 101and a timestamp of 155714890 block A, broadcast to the whole network

Block An is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

3. The exit height of Node 3 is 102and the timestamp is 155714891 Block B, broadcast to the whole network.

Block B is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

5. Node 3 exit height is 103, timestamp is 155714892 block C, broadcast to the whole network

Block C is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

Node 4 successfully received Block A, B, but Block C was not received due to delay.

Node 4 exit height is 103, timestamp is 155714893 block D, broadcast to the whole network

Because the consensus node of 2p3 has finally confirmed block C, D can not get the final confirmation.

Node 4 receives the final confirmation of blocks C and C, rolls back Block D, and switches the chain to Block C.

Node 4 has an exit height of 104and a timestamp of 155714894 block E, broadcast to the whole network.

Block E is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

When it reaches the second level, it is finally confirmed that a rollback occurs in all nodes that do not receive block C, which slows down the outgoing speed of 1 block.

Network delay exception 2

Node 3 has an exit height of 101and a timestamp of 155714890 block A, broadcast to the whole network

Block An is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

3. The exit height of Node 3 is 102and the timestamp is 155714891 Block B, broadcast to the whole network.

Block B is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

5. Node 3 exit height is 103, timestamp is 155714892 block C, broadcast to the whole network

Node 4 successfully received Block A, B, but Block C was not received due to delay.

Node 4 exit height is 103, timestamp is 155714893 block D, broadcast to the whole network

Block D is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

Node 3 receives the final confirmation of blocks D and D, rolls back Block C, and switches the chain to Block D.

Node 4 has an exit height of 104and a timestamp of 155714894 block E, broadcast to the whole network.

Block E is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

When it reaches the second level, it is finally confirmed that a rollback occurs in all nodes that identify block C, which slows down the outgoing speed of 1 block.

Network delay exception 3

Node 3 has an exit height of 101and a timestamp of 155714890 block A, broadcast to the whole network

Block An is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

3. The exit height of Node 3 is 102and the timestamp is 155714891 Block B, broadcast to the whole network.

Block B is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

5. Node 3 exit height is 103, timestamp is 155714892 block C, broadcast to the whole network

Node 4 successfully received Block A, B, but Block C was not received due to delay.

Node 4 exit height is 103, timestamp is 155714893 block D, broadcast to the whole network

Block D is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

Node 3 receives the final confirmation of blocks D and D, rolls back Block C, and switches the chain to Block D.

Node 4 has an exit height of 104and a timestamp of 155714894 block E, broadcast to the whole network.

Block E is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

When it reaches the second level, it is finally confirmed that a rollback occurs in all nodes that identify block C, which slows down the outgoing speed of 1 block.

Network delay exception 4

Node 3 has an exit height of 101and a timestamp of 155714890 block A, broadcast to the whole network

Block An is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

3. The exit height of Node 3 is 102and the timestamp is 155714891 Block B, broadcast to the whole network.

Block B is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

5. Node 3 exit height is 103, timestamp is 155714892 block C, broadcast to the whole network

Node 4 successfully received Block A, B, but Block C was not received due to delay.

Node 4 exit height is 103, timestamp is 155714893 block D, broadcast to the whole network

Block C and D each get 50% consensus node vote, and the network enters a bifurcation state.

Node 4 has an exit height of 104and a timestamp of 155714894 block E, broadcast to the whole network.

Block E is confirmed by more than 2 stroke 3 nodes and enters the final confirmation state.

The exit height of Node 4 is 105, and the timestamp is 155714895 Block E, broadcast to the whole network.

When the final confirmation is reached in seconds (in extreme cases, the probability of a minute occurrence is about the same as that of Bitcoin rollback 6 blocks), a rollback occurs in all nodes that identify block C, resulting in a slowdown in the outgoing speed of 1 block.

The limit state of this anomaly is that the two chains have about 50% of each station's computing power and continue to compete until the chain with a slight consensus advantage enters the final confirmation state.

Influence of parameters on network

1.

The number of consensus nodes actually represents the fault tolerance rate of the blockchain network, and the larger n is, the smaller the impact of single point of failure on the network is. However, the increase of the number of n will lead to an increase in the number of block signatures required by BFT, which will consume more resources and delay the time required for the block to enter the final confirmation state.

two。

The number of consecutive blocks per node is a way to ensure high-speed block output while taking into account the network delay.

When the number of continuous blocks is sufficient, the block time can reach the level of milliseconds in theory. The core point is that when the next outgoing consensus node has network delay and does not receive the last three blocks, but the previous three blocks have been received, you can continue to block on the basis of Mmur3. However, there is no block for a long time when excessive m leads to the failure of a single consensus node.

3.

The block interval time is obviously the guarantee of high tps, and theoretically, the tps of Bytom can reach 25000 when the block interval is 200ms. However, the too small s setting may lead to the extension of the final confirmation time of the block.

This is what Bystack's high-TPS consensus algorithm looks like. The editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.