BBFT consensus algorithm deep analysis 丨Bystack how to achieve a single side chain 20000+TPS

The consensus algorithm is a method for ensuring the consistency of node data state in a distributed system. The consensus algorithm in the blockchain is divided into two categories: PoW (workload proof) and PoS (professional proof). The first type of PoW mode is in the public chain project. The most widely used consensus algorithm used, Bitcoin's 10 years of operation has fully demonstrated the security and stability of POW. PoW's feature is to decentralize and security to the extreme, but at the expense of performance. For example, the peak TPS of Bitcoin is 3.87, and it takes 10 minutes for each transaction to be packaged into blocks. The peak TPS of the original chain is 36.32. It takes 2.5 minutes for each transaction to be packed into blocks. The second type of PoS mode is chosen by the algorithm to select the block consensus node, which is mostly used in the alliance chain and some new public chain projects that pursue high TPS. The PoS feature achieves optimal performance by supporting smaller out-of-block intervals, but at the expense of partial security and decentralization.

Bystack ^[1] is a blockchain BaaS platform based on the main sidechain architecture, which divides the blockchain into two layers, Layer1 and Layer2. Layer1 is both the main chain of the original chain, and the POW algorithm guarantees the highest level of asset security and decentralization. Layer 1's TPS problem is solved by transferring assets to Layer 2 through cross-chain technology. The side chain (ie Layer 2) uses the innovative BBFT ^[2] consensus algorithm to achieve a TPS of more than 20,000 in a single side chain, and multiple side chain combinations allow TPS to grow linearly.

TPS = number of block transactions * number of blocks confirmed per second without reaching node bandwidth and performance bottlenecks. Since the maximum number of transactions that a block can accommodate can be achieved by simply modifying the code parameters, increasing the number of blocks confirmed per second is a key way to improve TPS. For example, each block of the original chain can accommodate up to 5,500 transactions. In the main chain, the average TPS is 36.32 per block of 150 seconds. However, the above side chain will enter the final confirmation every second. Increasing the number of blocks to 5 can easily achieve TPS of more than 25,000.

• Sino-US game, bitcoin is the "key man"?
• What happens if everyone only buys Bitcoin and doesn't trade?
• 36,000 words white paper to challenge the real estate "Lemon Market" – Hangzhou "create the second generation" to prepare for the ant blockchain competition

DPoS problem

Traditional DPoS consensus algorithms such as EOS can fully support the block rate of 2 blocks per second, but there is a problem waiting for final confirmation. Because a conventional DPoS block is finally confirmed based on the fact that all super nodes have passed at least one sub-block after this block. This means that there are 21 super nodes, each of which has 6 blocks per round, with an average of 0.5 seconds per block. Then it takes 60 seconds for a block to get final confirmation.

BFT problem

BFT-based PoS because of the characteristics of BFT, all blocks can be quickly confirmed after output, but it is difficult to obtain a higher TPS. The reason is that each block of BFT is divided into three states, generated, pre-final state. Confirm the status with the final. The change in state relies on the collection of signatures from 2/3 nodes, and the efficiency of signature generation depends on the latency of the network. Suppose some super nodes are in the US, and some in China, the communication delay is about 200 milliseconds. That block requires a limit of at least 600 milliseconds from generation to final confirmation. Therefore, network delay becomes a bottleneck of high TPS in the BFT consensus algorithm.

DPOS BBFT consensus algorithm

Bystack's consensus algorithm is a new hybrid consensus algorithm based on the characteristics of DPoS and BBFT algorithms. The algorithm performs asynchronously with the BBFT signature to make the algorithm have both high TPS and fast final confirmation. In the BBFT consensus algorithm, all the network users vote to select n consensus nodes for block. The consensus section turns into a block node. When it becomes the consensus node of the block node, it will continuously output m blocks at a speed of s seconds. When the block is generated, it will be broadcast directly to the whole network, but the block node will not wait to acquire 2/3 other consensus node signatures but continue to make the next block based on the current block. At this point, the current block is already a legal block but no final confirmation is obtained, similar to the possibility that Bitcoin does 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. When a block gets more than 2/3 of the signature, it enters the final confirmation state.

TPS

The core point of achieving high TPS is that each consensus node continuously has m blocks. Because when each node only has one block, then the next consensus node out of the block needs to wait for the block from the previous consensus node. Here, we need to consider the problem caused by a network delay. If the block interval is set to be less than the network delay, there will be a high probability that the consensus node does not receive the previous block at the time of the block. But when m is set to a slightly larger number, TPS can be raised to the limit of bandwidth and node performance. Assume that when m=20, when the next consensus node is out of block, because the network delay does not receive the last block but receives the previous 19 blocks, the node will pick up after the 19th block of the previous round. The blockchain will enter the instantaneous fork state but will be unified in the whole network state after 2 blocks according to the longest chain principle. Although the TPS of one block is lost, it is guaranteed that the block interval is smaller than the high block rate in the case of network delay.

Asynchronous BFT

In the design of BBFT, the block is generated in parallel with the BFT signature of the consensus node to offset the impact of collecting BFT signatures on the outbound efficiency due to network delay. However, unlike the classic BFT algorithm, the pre-final state and the final confirmation of the three states, BBFT according to the characteristics of the blockchain transformation, the algorithm has only one final confirmation state. But two additional restrictions have been added: the first is that when a consensus node signs two different blocks of the same height, both fraud occurs; the second is when one consensus node pairs two different blocks at the same time. Signing is both fraudulent. Modification in this way reduces the number of communications between consensus nodes, thereby reducing the time it takes for the block to get final confirmation. At the same time, BBFT also has two blocks: direct confirmation and indirect confirmation. The first type directly confirms that the block has obtained more than 2/3 of the consensus node signature. The second indirect acknowledgment is that a block does not get 2/3 of the consensus node signature, but its sub-block obtains more than 2/3 of the consensus node's signature, and BBFT considers that the block has obtained the final acknowledgment status indirectly.

Disaster tolerance

1. Support only the single consensus node to survive, support the entire network to the next round of consensus node replacement, but the block rate will drop to 1/n of the normal situation. Users can change the voting to replace the super node during this period. The network returns to normal state in the next round of consensus node replacement.

2. Supporting 1/3 of the consensus nodes in the case of evil, the network operates normally. When more than 1/3 of the consensus nodes make bad blocks, they will not be able to enter the final confirmation function for a long time until the network runs to the next round of consensus nodes to be replaced. When more than 1/2 of the consensus nodes do evil, the malicious node will control the network.

BBFT consensus block scenario analysis

The following case assumes that n = 5, m = 3, s = 1, block height = 100, timestamp = 1557148900, it is the turn of consensus node 3 to prepare the first block

Perfect state

1. Node 3 has a height of 101, the timestamp is 155714890 block A, and broadcasts to the whole network 2. Block A gets more than 2/3 of the node confirmation, and enters the final confirmation state 3. The node height of node 3 is 102. The timestamp is 155,714,891 block B, broadcast to the whole network 4. Block B gets more than 2/3 of the node confirmation, enters the final confirmation state 5. The node has a height of 103, the timestamp is 155,714,892 block C, broadcast to The entire network 6. Block C gets more than 2/3 of the node confirmation, enters the final confirmation state. 7. Node 4 successfully receives the blocks A, B, C and is in the final state, continuing to continue on the basis of this chain. 8. Node 4 has a height of 104, and the timestamp is 155,714,893 block D, broadcast to the whole network ============================= ================================================================================================

Ideal state

1. Node 3 has a height of 101, and the timestamp is 155,714,890 block A, broadcast to the entire network.
2. Node 3 has a height of 102 and a timestamp of 155,714,891 blocks B, which is broadcast to the entire network.
3. Block A gets more than 2/3 of the node confirmation and enters the final confirmation state.
4. Node 3 has a height of 103, and the timestamp is 155,714,892 block C, which is broadcast to the entire network.
5. Block B gets more than 2/3 of the node confirmation and enters the final confirmation state.
6. Node 4 successfully received blocks A, B, C but only A, B is in the final confirmation state, and continues to block out on the basis of this chain.
7. Node 4 has a height of 104 and a timestamp of 155714893 block D, which is broadcast to the entire network.
8. Block C gets more than 2/3 of the node confirmation and enters the final confirmation state.

=========================================================== == Achieve second-level final confirmation, no rollback occurs, but due to the collection of consensus nodes to confirm the signature of the block, resulting in a final confirmation delay. However, since all the blocks have been successfully passed to the next block consensus node, it does not affect the block.

Outgoing consensus node abnormal state

1. The timestamp is 155714890, no new block is generated
2. The timestamp is 155,714,891, no new block is generated
3. The timestamp is 155714892, no new block is generated
4. Node 4 has not received any blocks, and the height of the exit is 101 after the mining. The time stamp is 155714893 Block A broadcasts to the whole network.
5. Block A gets more than 2/3 of the node confirmation and enters the final confirmation state.

=========================================================== == Achieve second level final confirmation, no rollback occurs, because the consensus node down machine causes no nodes to be out of the network within 3 seconds. The effect is to slow down the speed of the whole network. When a single node long-term down machine needs to wait for the next vote, re-select a new round of consensus nodes to repair.

Network delay exception 1

1. Node 3 has a height of 101, and the timestamp is 155,714,890 block A, broadcast to the entire network.
2. Block A gets more than 2/3 of the node confirmation and enters the final confirmation state.
3. Node 3 has a height of 102 and a timestamp of 155,714,891 blocks B, which is broadcast to the entire network.
4. Block B gets more than 2/3 of the node confirmation and enters the final confirmation state.
5. Node 3 has a height of 103, and the timestamp is 155,714,892 block C, which is broadcast to the entire network.
6. Block C gets more than 2/3 of the node confirmation and enters the final confirmation state.
7. Node 4 successfully received block A, B but block C was not received due to delay
8. Node 4 has a height of 103, and the timestamp is 155714893 block D, which is broadcast to the entire network.
9. Since 2/3 of the consensus nodes have finally confirmed block C, D cannot get final confirmation.
10. Node 4 receives the final confirmation information of blocks C and C, rolls back block D, and switches the chain to block C.
11. Node 4 has a height of 104, and the timestamp is 155,714,894 block E, broadcast to the entire network.
12. Block E gets more than 2/3 of the node confirmation and enters the final confirmation state.

=========================================================== == reaches the second level and finally confirms that there is a rollback that occurs in all nodes that have not received block C. The effect is to slow down the block speed of 1 block.

Network delay exception 2

1. Node 3 has a height of 101, and the timestamp is 155,714,890 block A, broadcast to the entire network.
2. Block A gets more than 2/3 of the node confirmation and enters the final confirmation state.
3. Node 3 has a height of 102 and a timestamp of 155,714,891 blocks B, which is broadcast to the entire network.
4. Block B gets more than 2/3 of the node confirmation and enters the final confirmation state.
5. Node 3 has a height of 103, and the timestamp is 155,714,892 block C, which is broadcast to the entire network.
6. Node 4 successfully received block A, B but block C was not received due to delay
7. Node 4 has a height of 103, and the timestamp is 155714893 block D, which is broadcast to the entire network.
8. Block D gets more than 2/3 of the node confirmation and enters the final confirmation state.
9. Node 3 receives the final confirmation message for blocks D and D, rolls back block C, and switches the chain to block D.
10. Node 4 has a height of 104, and the timestamp is 155,714,894 block E, broadcast to the entire network.
11. Block E gets more than 2/3 of the node confirmation and enters the final confirmation state.

=========================================================== == Achieve second level final confirmation, there is a rollback occurring in all nodes of the identity block C, the effect is to slow down the block speed of 1 block

Network delay exception 3

1. Node 3 has a height of 101, and the timestamp is 155,714,890 block A, broadcast to the entire network.
2. Block A gets more than 2/3 of the node confirmation and enters the final confirmation state.
3. Node 3 has a height of 102 and a timestamp of 155,714,891 blocks B, which is broadcast to the entire network.
4. Block B gets more than 2/3 of the node confirmation and enters the final confirmation state.
5. Node 3 has a height of 103, and the timestamp is 155,714,892 block C, which is broadcast to the entire network.
6. Node 4 successfully received block A, B but block C was not received due to delay
7. Node 4 has a height of 103, and the timestamp is 155714893 block D, which is broadcast to the entire network.
8. Block D gets more than 2/3 of the node confirmation and enters the final confirmation state.
9. Node 3 receives the final confirmation message for blocks D and D, rolls back block C, and switches the chain to block D.
10. Node 4 has a height of 104, and the timestamp is 155,714,894 block E, broadcast to the entire network.
11. Block E gets more than 2/3 of the node confirmation and enters the final confirmation state.

=========================================================== == Achieve second level final confirmation, there is a rollback occurring in all nodes of the identity block C, the effect is to slow down the block speed of 1 block

Network delay exception 4

1. Node 3 has a height of 101, and the timestamp is 155,714,890 block A, broadcast to the entire network.
2. Block A gets more than 2/3 of the node confirmation and enters the final confirmation state.
3. Node 3 has a height of 102 and a timestamp of 155,714,891 blocks B, which is broadcast to the entire network.
4. Block B gets more than 2/3 of the node confirmation and enters the final confirmation state.
5. Node 3 has a height of 103, and the timestamp is 155,714,892 block C, which is broadcast to the entire network.
6. Node 4 successfully received block A, B but block C was not received due to delay
7. Node 4 has a height of 103, and the timestamp is 155714893 block D, which is broadcast to the entire network.
8. Blocks C and D each receive 50% of the consensus node votes, and the network enters the fork state.
9. Node 4 has a height of 104, and the timestamp is 155,714,894 block E, broadcast to the entire network.
10. Block E gets more than 2/3 of the node confirmation and enters the final confirmation state.
11. The node 4 has a height of 105 and the timestamp is 155714895 block E, which is broadcast to the whole network.

=========================================================== == Achieve second-level final confirmation (extreme case minute probability is similar to Bitcoin rollback 6 block), there is a rollback in all nodes of the identity block C, the effect is to slow down 1 block Blocking speed. The limit state of this abnormal situation is about 50% of the computing power of each station in the two chains and continuous competition occurs until the chain with a slight consensus has entered the final confirmation state.

The impact of parameters on the network

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

2. The number of consecutive blocks out of each node is a method to ensure high-speed block-out in consideration of network delay. When the number of consecutive blocks is sufficient, the block time can theoretically reach the millisecond level. The core point is that when the next block consensus node has network delay, the last 3 blocks are not received, but the previous m-3 areas have been received, and the block can continue to be released on the basis of m-3. However, if the m is too large, the single consensus node will not be blocked for a long time.

3. The block interval time is the guarantee of high TPS on the bright surface. In theory, when the block interval is 200 milliseconds, the TPS of Bytom can reach 25000. However, too small a setting of s may lead to an extension of the final confirmation time of the block.

1.Bystack white paper "The world's first multi-sided architecture BUXTO model BaaS platform " ↵

2. " BBFT: a Hierarchical Byzantine Fault Tolerant Consensus Algorithm " ↵

We will continue to update Blocking; if you have any questions or suggestions, please contact us!