PoA 2.0: Finality with One Bit

2022-06-17 21:07
Read: 5021


Block finality is an indispensable property for a modern blockchain system. It provides an absolute security guarantee for blocks (and therefore, all the transactions packed in them) that satisfy certain conditions. We, at the VeChain blockchain dev team, have been pursuing this property along the way to improving our consensus algorithm. 


To do that, instead of replacing the Proof-of-Authority (PoA) consensus with a completely new one, we have chosen the path of designing and implementing a finality gadget, named the Finality with One Bit (FOB) to allow us to run dual modes of consensus, namely, the Nakamoto and BFT consensus, at the same time. The advantages of the current design, proposed by VIP-220, are:

  • Achieving block finality
  • Maintaining the usability and robustness of our system by decoupling finality from the PoA process which allows the blockchain to grow in adverse environments
  • Introducing minimal complexity to the current PoA-based system, minimizing the potential risks caused by unknown design deficiency and implementation bug
  • Adding minimal extra information (one bit per block) for network communication so that we do not need to sacrifice system performance for achieving block finality 


Background

During our work on PoA 2.0, we have proposed two solutions to block finality, described in VIP-193 and VIP-220, respectively. The former is based on the research in [1] and contains two major components: a VRF-based random beacon generator scheme and a committee-based Hotstuff-like BFT algorithm. During our implementation of VIP-193, we successfully applied the random beacon generator scheme to the current system, resulting in a much better source of randomness. However, the complexity and redundancy brought by the BFT algorithm hestated us to merge it to the system. 


To reduce the complexity and redundancy to a satisfactory level, we collaborated with the researchers from UBC and sponsored their work on the view-less BFT via the VeChain Grant Program. The research resulted in the finality gadget, named the Finality with One Bit. The algorithm has been described in VIP-220 and is the replacement of the one proposed in VIP-193. We can now define PoA2.0 as the combination of the VRF-based random beacon generator scheme and FOB. The committee mechanism is an optional component that would accelerate the finality process. In the following paragraphs, we will focus on describing FOB.


Finality Gadget

For the Nakamoto consensus, there is always a non-zero probability (although it could be a tiny small number) that a transaction could be reverted due to double spending. This is usually fine for our daily uses but could be troublesome in some security sensitive use cases. On the other hand, we don't want to completely replace the Nakamoto consensus mechanism since it has already proven its usability and practicality in adverse network environments.  


Hence, "finality gadget" is then proposed. It is an add-on to the existing Nakamoto consensus that utilizes the information contained in the mined blocks to reach block finality. With a finality gadget, a transaction will first be confirmed by the Nakamoto consensus, and then be "finalized" by the gadget. Once it is "finalized", it is proven to be absolutely secure, that is, there is zero probability that the transaction could be reverted as long as the finality security assumption holds.


There are similarities between the finality gadget and the known BFT mechanism (e.g., PBFT, Tendermint, Hotstuff, etc.). However, the difference is that a finality gadget is a "gadget" or a component running upon the Nakamoto blockchain system, and therefore, will not replace the original Nakamoto consensus. Following this definition, a finality gadget should satisfy the below two conditions: the finalized block needs to be

  • a block on the original Nakamoto chain – Condition A
  • a confirmed block on the original Nakamoto chain – Condition B.

By confirmed, it means that the block is appended by a sufficient number of blocks. Consequently, we cannot simply run a BFT algorithm in parallel as a finality gadget as it fails in Condition A. Moreover, we cannot be satisfied by the Ebb-and-Flow protocols, which does not guarantee Condition B.


Finality with One Bit

FOB is our novel finality gadget inspired by the view-less BFT (VLBFT) [2]. The rest of this section will be used to describe VLBFT and FOB briefly.


Most existing BFT algorithms, including PBFT, Tendermint, and Hotstuff, achieve consensus with concepts of view and lock. A view can be roughly considered as a new round of consensus process. Nodes will start the consensus process in the current view and lock to the view, that is, not responding to other views. By design, if they cannot reach a consensus in the current view, nodes will have to trigger a view change process, unlock themselves and enter into a new view. The view change process is often expensive, significantly deteriorating system performance.


VLBFT does not use this paradigm. It utilizes the underlying blockchain to provide liveness and does not force all nodes to be in the same view to join the consensus process and lock to it. To mine a new block, the block proposer needs to collect votes from the supermajority (more than 2/3 of the consensus nodes) and put them in the block header to propose a valid block. Due to the nature of Nakamoto consensus, there could be multiple valid block proposers in a round. In that case, honest nodes will vote for all of them, instead of locking to only one of them as in the case of a view-based algorithm.


Alongside with each vote, nodes not only show agreement on the newly proposed block, but also give an extra bit of information of whether it has voted for multiple blocks in the previous rounds. If yes, it casts a "Wit" (stands for Witness) vote. Otherwise, it casts a "Com" (stands for Commit) vote. The block proposer then collects these votes to propose a valid block. If it is able to collect "Com" votes from the supermajority, then the parent block of this block will reach consensus. 


The view-less and blockchain-drive liveness nature of VLBFT makes it a perfect foundation for a finality gadget. We thus propose FOB using the essence of VLBFT. Firstly, we define the first block of every L blocks as checkpoints (CPs). A CP is called justified if it is appended by blocks signed by more than two third of the Authority Masternodes (AMs) in the CP. We then define the CP height of a block by the number of justified CP before this block. In each block, the block proposer will give their opinions on whether they have proposed blocks for multiple CPs in the previous CP height. If not, they add one bit of "Com" vote in their proposed block. Otherwise, they vote "Wit" in their proposed block. In FOB, there is no separate vote collecting process. Instead, the votes are cast alongside the appending blocks. Then, if "Com" votes are collected from more than two third of AMs in the same CP height, the CP from the previous height is finalized. Note that the “Com” and “Wit” vote can be represented by one bit and that is why we name our finality gadget the Finality with One Bit. 


How is FOB compared to other finality gadget designs?

We have already mentioned some desired properties (both Condition A and B) in FOB. Moreover, FOB is simple by design and adds minimal redundancy to the existing PoA-based Thor protocol.


Note that most existing finality gadget designs do not satisfy Condition B, which we consider a necessity for finality gadgets. It is because without Condition B, a finality gadget could rollback what the original Nakamoto consensus has confirmed, making the original consensus algorithm rather meaningless. On the contrary, FOB is one of its kind that satisfies Condition B.


Finality gadgets like Casper and Grandpa introduce a separate voting mechanism, in which the nodes vote for the checkpoints and broadcast them like transactions. In such systems, votes will be collected by the block proposers and therefore, requires an extra incentive mechanism to guarantee the honesty of all parties. It is unfortunate that neither Casper nor Grandpa has implemented it. On the other hand, this is not an issue in FOB as votes are directly cast in blocks with only an extra bit.


Last but not least, most existing finality gadgets follow the view-based paradigm of BFT algorithms. Nodes will have to lock themselves to a view until consensus is reached or they will be unlocked by the view-change process to avoid being deadlocked. The lock could result in a lengthy recovery period in case when the network suffers from a major failure and then returns to normal. On the other hand, in FOB, nodes are implicitly locked, i.e, they could vote by appending blocks for multiple forks. In fact, they are only "locked" to the "Wit" vote if they have done so in the previous CP height. As a result, FOB could recover from network failure as soon as the network returns to normal and the underlying blockchain is fork-free.


References

[1] Zhijie Ren and Peter Zhou (2020) SURFACE: A Practical Blockchain Consensus Algorithm for Real-World Networks, arXiv:2002.07565v3.

[2] Jianyu Niu and Chen Feng. Leaderless Byzantine fault tolerant consensus. arXiv:2012.01636.


RECOMMENDED