One of the most important pieces of research completed for the Lisk blockchain this year was the . We have already covered the benefits of this consensus algorithm for the Lisk protocol . new Byzantine Fault Tolerance (BFT) consensus system 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. If more than ⅔ of the active delegates in the network follow the protocol honestly, two conflicting blocks can never be finalized on the chain. Safety: 2. Even if ⅓ of the active delegates go offline, new blocks can still be finalized on the network. Liveness: 3. If a delegate violates the protocol, he/she will be held accountable for it. Accountability: 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 itself or the accompanying it. Here we will focus more on the implementation details. proposal research paper 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 and . height at which a delegate has previously forged maximum pre-voted height at the time of forging that block Along with this, each node will persist the , so in the case of chain recovery the already finalized blocks can’t be reverted. finalized height 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 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. Delegated Proof of Stake (DPoS) 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 . The blocks which will collect more than ⅔ of all votes (majority) are eligible for the next round of voting. pre-voting The second round of voting is called , 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 . The highest block finalized will be considered as the for the chain. All the blocks with height below finalized block will be also considered as and , in any case. pre-committing finalized finalized height final cannot be reverted 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 . This means that the block is finalized and will never be reverted. height 6 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 , but rather for a . If a block at 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. individual block particular block height height 7 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 , when the chain was at . This happened because delegates were missing the slots and were not able to pre-vote and pre-commit on previous blocks. But since is finalized, so all blocks before that height will also be considered finalized. height 6 height 11 height 6 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 to . It then stay stagnant from till . 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. height 1 height 15 height 15 30 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 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. height 33 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. eel free to Also, don’t forget to as well. If you want to explore the implementation — f look into this code on our GitHub repository . look at the tests 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 and . There is a lot more in the , e.g. and , which together will make a Byzantine Fault Tolerance consensus complete. pre-voting pre-commits LIP Fork Choice Rules Fork Recovery Mechanism 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

Flow

Chain

Lisk

Twitter

Encoding  Base128 Varints, Explained

Read My Stories

Too Long; Didn't Read

Download free Tech Leaders Productivity Report!

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

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Encoding Base128 Varints, Explained

(1/100) Crypto Countdown: Golem

A Research Report on the Trader $JOE DeFi Platform

07/03/2018: Biggest Stories in the Cryptosphere

05/02/2018: Biggest Stories in the Cryptosphere

Encoding Base128 Varints, Explained

(1/100) Crypto Countdown: Golem

A Research Report on the Trader $JOE DeFi Platform

07/03/2018: Biggest Stories in the Cryptosphere

05/02/2018: Biggest Stories in the Cryptosphere

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps