BEP: 126 Title: Fast Finality Mechanism Status: Draft Type: Standards Created: 2021-12-20 Discussions(optional): https://forum.bnbchain.org/t/bep-126-draft-introduce-fast-finality-mechanism/123/3
This BEP introduces a fast finality mechanism on the BNB Smart Chain.
BEP-126 Proposal describes a fast finality mechanism to finalize a block, once the block has been finalized, it won't be reverted forever.
It takes several steps to finalize a block:
- A block is proposed by a validator and propagated to other validators.
- Validators use their BLS private key to sign for the block as a vote message.
- Gather the votes from validators into a pool.
- Aggregate the BLS signature if its direct parent block has gotten enough votes when proposing a new block.
- Set the aggregated vote attestation into the extra field of the new block's header.
- Validators and full nodes who received the new block with the direct parent block's attestation can justify the direct parent block.
- If there are two continuous blocks have been justified, then the previous one is finalized.
The finality of a block can be achieved within two blocks in most cases, this is expected to reduce the chance of chain re-organization and stabilize the block producing further.
Finality is critical for blockchain security, once the block is finalized, it would not be reverted anymore. The fast finality feature is very useful, users can make sure they get the accurate information from the latest finalized block, then they can decide what to do next instantly.
Currently, on BNB Smart chain, all the full nodes and validators need to wait until enough blocks have been produced to ensure a probabilistic finality. For BSC, with 21 validators, full nodes and validators can wait 2/3*21=14 blocks to ensure a relatively secure finality, it would be quite long time for some critical applications.
We introduce a vote mechanism to reach fast finality, the whole mechanism includes several rules in vote and consensus.
Validators can vote for blocks if they think that block should be in the canonical chain, and once their votes have been wrapped into the header, they will get rewards. At the same time, they should obey the vote rules, the vote rules can be described as follows.
- A validator must not publish two distinct votes for the same height. (Rule 1)
- A validator must not vote within the span of its other votes . (Rule 2)
- Validators always vote for their canonical chain’s latest block. (Rule 3)
Define the following notation:
- s : the block hash of the latest justified block in the longest chain(the “source”)
- t : the expected longest chain head block hash that is a descendent of s (the “target”)
- h(s): the height of block s
- h(t): the height of block t
- <v, s, t, h(s), h(t)> : validator v’s vote message
- a -> b : super majority link that ⅔*v+ validators have voted with source a and target b
The Rule 1 and Rule 2 can be described as for any two votes:
- h(t1) == h(t2) is not allowed. (Rule 1)
- h(s1) < h(s2) < h(t2) < h(t1) is not allowed. (Rule 2)
The valid vote messages should be saved to the block header, before that the miner should first aggregate these votes, the rules for aggregating votes can be described as follows:
- When validators mining blocks, if they see its direct parent block has gathered ⅔*v+ votes from valid validators, they should aggregate these votes as an attestation for the parent block. We call this direct parent block as the attested block. We assume 1 block time is totally enough for validators to receive a block, vote for the block and propagate the vote to other validators.
There are two steps to finalize a block, the first step we call justify, the second step we call finalize.
- A block is called justified if
- (1) it is the root, or
- (2) there exists attestation for this block in its direct child’s header, we call this block justified.
- A block is called finalized if
- (1) it is the root, or
- (2) it is justified and its direct child is justified.
In the Parlia and Clique consensus, the validators will rely on the sum of the “Difficulty” field to compare and confirm which chain is the longest to pick as the ancestor.
While introducing this finality mechanism, the chain should grow under new fork choice rule: the fork including the highest justified block should be considered as the longest chain even though there are other chain forks with higher difficulty sum. If there is no new block that can be justified during some time, the chain can grow with the previous longest chain rule, which can make the chain remain original probabilistic finality.
The new longest chain rule can be described as follows.
- The fork that includes the higher justified block is considered as the longest chain.
- When the justified block is the same, fall back to compare the sum of the “Difficulty” field.
In the current Parlia consensus, the validator liveness is ½*v+1=11, which means when there are more than 11 validators online, the chain can get increased continuously.
In this design, we should change the liveness from ½v+1=11 to ⅔v=14, this can protect the chain from getting increased in a malicious fork.
Assume the malicious validators are less than ⅓v, honest validators are more than ⅔v, honest validators always behave under the above rules, the vote can be propagated to all validators within one block time, then we can prove this fast finality mechanism has accountable safety and plausible liveness.
Accountable safety means that two blocks in different forks cannot both be finalized unless ⅓*v or more validators violate the voting rules.
Plausible liveness means that, regardless of any previous events, if ⅔*v+ validators follow the mechanism, then it’s always possible to finalize a new block without any validator violating the vote rules.
Under the assumption that less than ⅓*v validators violate the vote rules, we have the following properties:
- If s1 -> t1 and s2 -> t2 are distinct super majority links, then h(t1) != h(t2).
- If s1 -> t1 and s2 -> t2 are distinct super majority links, then the inequality h(s1) < h(s2) < h(t2) < h(t1) cannot hold.
From these two properties, we can immediately see that, for any height n:
- there exists at most one super majority link s -> t with h(t) == n.
- there exists at most one justified block with height n.
With these four properties in hand, we move to the main theorems.
Theorem 1 (Accountable Safety). Two blocks in different forks cannot both be finalized.
Let Am (with justified Am+1, meaning h(Am) + 1 == h(Am+1)) and Bn (with justified direct child Bn+1, meaning h(Bn) + 1 == h(Bn+1)) be distinct finalized blocks. Now suppose Am and Bn are on different forks, and without loss of generality h(Am) < h(Bn) (If h(Am) == h(Bn) it is clear that at least one honest validator violated Rule 1).
Bn is finalized, so there must exist a super majority link R -> B1, …, Bi - > Bi+1, …, Bn -> Bn+1. We know no super majority link’s target h(Bi) equals either h(Am) or h(Am+1), because that violates property 4.
Let j be the lowest integer such that the super majority link’s target h(Bj) > h(Am+1). If the super majority link’s source is justified , we have h(Bj-1) < h(Am+1), and h(Am) = h(Am+1)-1, so h(Bj-1) < h(Am); this implies that the existence of a super majority link Am -> Am+1 within the span of Bj-1 -> Bj, this violates the vote Rule 2.
Theorem 2 (Plausible Liveness). Super majority links can always be added to produce new finalized blocks, provided there exist children extending the finalized chain.
With the justified block growing, the validators can always start new round voting without violating any vote rules, then we know there always will be new justified blocks, and once one of its direct child block has been justified, this block can be finalized without violating any vote rules.
In order to make the block get finalized faster, once the validators see the votes for the block are 2/3 or more validators, these votes will be wrapped and the reward will be distributed to these wrapped voted validators, the remained validators who didn’t vote for the block or vote later won’t get reward.
- Validators whose vote is wrapped into the vote attestation can get reward
- The reward will be paid by our system reward contract and distributed at the end of the epoch
- The validator who violates the first two vote rules will be slashed
- The evidence can be submitted by anyone, whenever someone sees the malicious behavior, he can submit the evidence to a designed system contract
- Once the evidence has been proved valid, the malicious validator will be put into jail, the submitter can get part of the rewards from our system reward contract.
- Once the malicious validator has been put into jail, the later submitters that submit malicious evidence of the validators won’t get any reward.
There are two well-known attacks against proof-of stake system: long range revisions and catastrophic crashes, these attacks are also existed after implementing this BEP.
The content is licensed under CC0.