Examining Pre-Votes and Pre-Commits for the Byzantine Fault Tolerance Consensus (BFT) Mechanism

One of the most important pieces of research completed for the Lisk blockchain this year was the new Byzantine Fault Tolerance (BFT) consensus system. We have already covered the benefits of this consensus algorithm for the Lisk protocol in this blog post.

Ahead of its implementation in Lisk SDK 3.0.0, I want to focus one key aspect of the BFT consensus — the process of computing block finality i.e. a guarantee that a particular block is never reverted.

What are the Main Benefits of BFT?

Before we dive deep into this topic, let’s quickly go through basic key features that BFT improves on the blockchain.

1. Safety: If more than ⅔ of the active delegates in the network follow the protocol honestly, two conflicting blocks can never be finalized on the chain.

2. Liveness: Even if ⅓ of the active delegates go offline, new blocks can still be finalized on the network.

3. Accountability: If a delegate violates the protocol, he/she will be held accountable for it.

These are the three high-level values BFT provides to the protocol. As an effect it tries to recover from forks as quickly as possible to grow the network chain with better finality. Each of these features require more extensive understanding. If you want, you can also explore the proposal itself or the research paper accompanying it. Here we will focus more on the implementation details.

With the BFT consensus, each node does not only maintain the blockchain. It also maintains additional metadata in memory to validate and verify blocks, according to the rules defined by the algorithm. This information will also be partially persisted on the blockchain itself, to make sure that a node can rebuild this in-memory dataset if it crashes.

One of the properties we additionally persist to the blockchain for every block is the height at which a delegate has previously forged and maximum pre-voted height at the time of forging that block.

Along with this, each node will persist the finalized height, so in the case of chain recovery the already finalized blocks can’t be reverted.

Let’s dive into the topic for the day — voting for the blocks by the delegates.

Vote Democracy for Blocks

Voting is not anything new in the Lisk Ecosystem — it’s the backbone of any Delegated Proof of Stake (DPoS) consensus algorithm. LSK token holders can vote for delegates, then, based on their votes, the system chooses the top delegates which are eligible to forge new blocks for a particular round. Previously, the voting system was used only to vote for delegates. With the introduction of BFT, this concept expands.

Now, each delegate will cast a vote for each block, the only difference is these votes will be maintained and kept by individual nodes to themselves. Only few computed attributes will be shared with the network, and not with the whole voting ledger. The mathematical formulas and protocol checks in the system will ensure each node casts the votes appropriately.

Like in any voting system, the basic rule is that you, as a delegate, can cast your vote only once for a block at a particular height. Since two blocks can’t exist at the same height, you can actually cast vote once for each block. This process is called pre-voting. The blocks which will collect more than ⅔ of all votes (majority) are eligible for the next round of voting.

The second round of voting is called pre-committing, and the rule is the same — one delegate can pre-commit one block, only once, for the blocks which are qualified (already got more than ⅔ of all pre-votes). So during the second round, the block which got more than ⅔ of pre-commits will be considered finalized. The highest block finalized will be considered as the finalized height for the chain. All the blocks with height below finalized block will be also considered as final and cannot be reverted, in any case.

There are some other rules as well:

1. A delegate can’t pre-vote and pre-commit the blocks for the round in which they were not active. This happens in order to avoid spam votes. So we need to keep track of the round when the delegate became active.

2. A delegate can’t pre-vote and pre-commit more than two rounds behind, to improve the performance of the whole system.

Example Scenario #1 — Four Delegates, All Forging

To better understand this concept, let’s take one small example. Say we have four active delegates in the network.To finalize any block — at least ⅔ (or three delegates) must agree.

You can also download the data file

Let’s run through a data simulation to understand this more.

1. While applying a block to the chain, the following information needs to be checked: the height at which the delegate previously forged, the highest height in the blockchain which already got ⅔ votes, as well as the round in which the delegate was active last time.

2. The delegate checks the states of previous pre-votes and make pre-commits to all blocks which have ⅔ votes so far. Considering the rule, that delegate can’t pre-commit the same block twice. The delegate also can’t pre-commit the blocks for the time when they were not active. Additionally, for performance reasons we don’t perform these pre-commits for more than two rounds behind from the current height of the chain.

3. At every block, the delegate will pre-vote for all blocks. Considering the rules that the delegate can’t pre-vote twice the same block. And the delegate can’t pre-vote the blocks for the time when they were not actively forging. Also, for performance reasons, we don’t perform these pre-commits for more than two rounds behind from the current height of the chain.

4. So as you can see in the diagram, the first block in the chain got three pre-commits at height 6. This means that the block is finalized and will never be reverted.

5. Rest of the blocks in the chain are obviously applied to the chain. These can be reverted in order to resolve forks in the network.

6. You may notice the blocks with ⅔ votes are increasing ahead of the pre-commits. The blocks which have more pre-votes are expected to have more pre-commits and yet more chances to be finalized.

There is one important fact to remember — finality is not considered for an individual block, but rather for a particular block height. If a block at height 7 is finalized, that means all blocks beneath it are also finalized. The finality is not always sequentially incremented, due to changes in the delegate list (the list that determines the forging order. This means that there are chances that a few blocks don’t get finalized, but then some next blocks will be finalized earlier. In that case, all previous blocks, with height lower than the blocks that just got finalized, will be considered finalized as well.

Example Scenario #2 — Four Delegates, Missing Slots

To understand this pre-voting and pre-committing flow further, let’s take an example simulation with the same four delegates, but this time delegates start missing their slots. This results in the chain finality not increasing smoothly and instead having gaps between finalized blocks.

You can also download the data file.

Please see the image above to have a column reference. In this data simulation, you will notice that first block finalized was at height 6, when the chain was at height 11. This happened because delegates were missing the slots and were not able to pre-vote and pre-commit on previous blocks. But since height 6 is finalized, so all blocks before that height will also be considered finalized.

Example Scenario #3 — Five Delegates, All Switching

Now let’s take another example where five delegates are forging but after the third round, they are all replaced by other delegates.

You can download the data file

The key fact to notice in this simulation is how the finalized height grows continuously from height 1 to height 15. It then stay stagnant from height 15 till 30. At every block, delegates were still voting for new blocks, but due to the rule that delegate can’t pre-commit any block for the period when it was not active, they didn’t pre-commit the old blocks. This is an expected behavior, because the network should increase the finalized height only if there is a consensus of at least ⅔ delegates for a certain block. Otherwise, the network will grow but no blocks will be considered finalized.

Example Scenario #4 — Eleven Delegates, One Delegate Switch

This use case is more similar to a real network, where delegate lists stay consistent for a few rounds and afterwards only few delegates switch their positions. We are also increasing the number of delegates in this data simulation, which produces a mind boggling set of numbers.

You can download data file

In this example, we can see the finality in this network grows sequentially until height 33 and then it stops for a while (four blocks). The finality then starts growing again. This behavior is more close to the actual real-life network.

Why Do We Go Through These Simulations?

You may be wondering why we got through and developed all those data-intensive simulations, even though the logic is already documented. Yes, it is, but the understanding the logical part is complex and can cause mistakes during the implementation. These data simulations gave us a clear understanding of the data flow and also visualize how BFT consensus will behave on a network in various circumstances.

Along with this, these data simulations helps us to write the tests for our implementation, which not only makes the implementation sound, but also gave us the way to extend and add more test scenarios.

If you want to explore the implementation — feel free to look into this code on our GitHub repository. Also, don’t forget to look at the tests as well.

We hope these data simulations will also help you get a better better understanding of the BFT consensus proposal. To iterate again, this article only covers one aspect of the BFT LIP, which is pre-voting and pre-commits. There is a lot more in the LIP, e.g. Fork Choice Rules and Fork Recovery Mechanism, which together will make a Byzantine Fault Tolerance consensus complete.

Lisk is on a mission to enable you to create decentralized, efficient, and transparent blockchain applications. Join us:

• Lisk Discord
• SDK Page and Newsletter
• Lisk Research
• Twitter