Analysis | Pre-selection and pre-submission mechanisms for Byzantine fault-tolerant consensus

This article explores the advantages of the Byzantine consensus algorithm, and it is necessary to talk about an important aspect of the Byzantine consensus – the end of the block, that is, to ensure that a particular block will never be reversed.

Source|lisk official blog

Translation|First Class Warehouse Tracey

Proofreading | First Class Maggie

• Unlock Bitcoin for more apps, Miniscript yesterday, today and tomorrow!
• Technical Guide | Teach you to discuss Wasm contract development: (C++)
• Getting started with blockchain | Ethereum 2.0 terminology at a glance

Please reprint the preface information.

This article explores the advantages of the Byzantine consensus algorithm and explains an important aspect of the Byzantine consensus—the end of the block—that is, ensuring that a particular block is never reversed.

What are the main benefits of the Byzantine consensus?

Before delving into the advantages of the Byzantine consensus, take a quick look at the key functional improvements to the blockchain by the Byzantine consensus.

1. Security: If two-thirds of the active trustees in the network follow the agreement honestly, the two controversial blocks cannot be finalized on the blockchain.

2. Activity: Even if 1/3 of the active trustees are offline, the new block can still be finalized on the blockchain.

3. Accountability: If a trustee violates the consensus agreement, he/she will be responsible for his actions.

These are the three advanced features of the Byzantine consensus. It quickly recovers from the fork and quickly achieves blockchain termination. All three features require in-depth understanding, and if you are happy, you can learn about LIP and Byzantine consensus research papers. The focus of this article is to introduce the implementation details of Byzantium.

In the Byzantine consensus algorithm, each node not only maintains the blockchain, but also maintains other memory metadata to validate the blockchain according to algorithmic rules. Part of the memory metadata is also stored on the blockchain to prevent the memory dataset from being rebuilt when the node crashes. The additional attributes we add to the block are the height of the previous block forged by the trustee and the maximum pre-voting height for the forged block. At the same time, each node will pursue the final height, so in the case of restoring the blockchain, the blocks that have been terminated can no longer be reversed.

Support block democratic voting

In the Lisk ecosystem, voting is nothing new – voting is the foundation of any DPoS consensus algorithm. The LSK token holder can vote for the trustee, and then, based on the number of votes, the system selects the trustee with the highest ticket to forge a new round of blocks. Previously, the voting system was only used to vote for the trustee. After the Byzantine consensus algorithm was introduced, the voting system was no longer used only for voting. Each trustee will cast a vote for the block, except that the vote voted by the trustee is maintained and retained by each node itself. Only a few of the calculated attributes are posted on the web and are not posted to the entire voting book. Byzantine mathematical formulas and protocols ensure that each node votes correctly.

Consistent with the basic rules of other voting systems, the trustee can only vote once for a block of a certain height. Because there can be no two blocks at the same height, the trustee can only vote for one block. This process is called pre-voting, and the block that collects 2/3 of the votes is qualified to enter the next round of voting.

The second round of voting is called pre-submission. The rules are similar to the above. The trustee can pre-submit a block and can only submit it once. The block that gets 2/3 pre-voting reaches the qualified line. In the second round, obtaining 2/3 pre-submitted blocks is terminating. The block with the highest number of pre-commits is finally determined as the height of the blockchain. Blocks below the height of the final block will also be final and irreversible.

Some other rules:

1. If the trustee does not participate in this round of voting, no pre-voting or pre-submission can be made. The purpose is to prevent garbage voting. So when the trustee activates, we track the voting wheel.

2. A trustee cannot participate in 3 rounds of voting to improve overall system performance.

Example scenario 1 – 4 trustees forging at the same time

Suppose there are 4 active trustees in the network. To make each block final, at least 3 (greater than or equal to 2/3 principle) the trustee voted.

4 trustees are involved in forging

We simulate a data to better understand.

1. When a block is added to the blockchain, check the following information: the block height forged by the trustee, the highest block with more than 2/3 of the votes on the chain, and the last time the trustee participated Vote round.

2. The Trustee checks the previous pre-voting status and pre-submits those blocks with 2/3 votes. As a result of the Byzantine Consensus Rules, a trustee cannot pre-submit a block twice. And for performance reasons, we will not continue to perform these pre-submissions in the last two rounds of the chain's current height.

3. The trustee pre-votes all blocks. According to the rules, the trustee cannot only pre-vote to a block at a time. And you can pre-voting in the time you are activated. And for performance reasons, we will not continue to perform these pre-submissions in the last two rounds of the chain's current height.

4. As shown, the first block in the chain has three pre-commitments at height 6. This means that the block is terminated and can never be reversed.

5. The remaining blocks in the chain are obviously applied to the chain before, and these blocks can be reversed to solve the network fork problem.

6. The number of blocks with 2/3 votes is rising before the pre-submission. Blocks with more pre-voting are expected to receive more pre-submissions and are more likely to be finalized.

But the terminology is not for a single block, but for a specific block height. If a block is finalized at a height of 7, it means that the block below it is also finalized. The summativeness is not in order, but varies according to the list of trustees (the list of trustees determines the forging order). It is possible that several blocks have not been finalized, and new blocks have been identified. In this case, all the blocks that are lower than the current finalization are finalized.

Example Scenario 2 – 4 Trustees Missed Slots

Suppose there are four trustees, but this time the trustee missed the slot, and as a result, the chain could not smoothly determine the block, and there was a gap between the terminated blocks.

4 trustees are missing slots

Looking at the data simulation of the above figure, it can be seen that the first block determined by the height is 6 and the block chain height is 11. This happens because the trustee lost the slot and was unable to pre-vote and pre-submit the previous block. Since the height 6 is final, all blocks below 6 in height are finally confirmed.

Example Scenario 3 – 5 trustees have been replaced

Suppose the five trustees are forging, but after the third round, the five trustees were replaced by other trustees.

5 trustees have been replaced

The most important concern in this simulation is how the final height maintains growth between height 1 and height 15. The final height between the height 15 and the height 30 stops growing. The trustee is still voting for the new block, and the consensus rule stipulates that the trustee cannot pre-submit the block at this stage because the trustee has not been activated, and the original block has not been pre-submitted. This is expected, because the end-to-end growth of the network is more than 2/3 of the trustees to reach a consensus on a certain block. Otherwise, the network continues to grow, but the block is not finalized.

Example Scenario 4 – 11 trustees, one of whom is replaced

Example 4 is more similar to the real network situation. The list of trustees has not changed in several rounds of voting. Only a few trustees have changed their positions. We also simulated the data and increased the number of trustees, resulting in an incredible set of results.

11 trustees, one was replaced

In Example 4, it can be seen that the network terminating height stops growing until the height 33, followed by the time when the four blocks are suspended, and then starts to grow again. This situation is more similar to a real network.

Why do you want to perform these simulations?

You may be wondering why we are doing these data-intensive model experiments? Because the Byzantine consensus has been recorded. Yes, but it is difficult to understand the logic of the Byzantine consensus, and it is easy to have problems in the process of implementation. The above data simulation allows us to understand more clearly the data flow and visualize the Byzantine consensus in different network scenarios.

At the same time, data simulation can help us test the Byzantine implementation, not only to make the implementation more complete, but also to give us the inspiration to expand and add more test scenarios.

This article only introduces the tip of the iceberg of the Byzantine Consensus LIP, namely the pre-voting and pre-submission sections. The Byzantine LIP has a lot of content, such as the fork selection rule and the fork recovery mechanism, which is the completeness of the Byzantine consensus.

Original: https://blog.lisk.io/exploring-pre-votes-and-pre-commits-for-byzantine-fault-tolerance-consensus-bft-8aabd9e148a9

Source: https://first.vip/shareNews?id=2111&uid=1

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