BEP-126(Draft): Introduce Fast Finality Mechanism

[Keefe]

BEP-126: Introduce Fast Finality Mechanism

1. Summary

This BEP introduces a fast finality mechanism on the BNB Smart Chain.

2. Abstract

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:

1. A block is proposed by a validator and propagated to other validators.
2. Validators use their BLS private key to sign for the block as a vote message.
3. Gather the votes from validators into a pool.
4. Aggregate the BLS signature if a block has gotten enough votes for finality from validators.
5. Set the block’s finality information into the finality field of the header while proposing a child block.
6. Validators and full nodes who received the child block with the block’s finality information can finalize the block.

The finality of a block can be achieved within one or two blocks in most cases, this is expected to reduce the chance of chain re-organization and stabilize the block producing further.

3. Status

This BEP is working in progress.

4. Motivation

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 wait until enough blocks have been produced to ensure a probabilistic finality. According to the whitepaper, with 21 validators, full nodes and validators can wait ⅔*21+1=15 blocks to ensure a relatively secure finality, it would be quite long time for some critical applications.

5. Specification

5.1 Fast Finality Mechanism

We assume that validators set are fixed and more than ½ validators are honest, the honest validators won’t violate these two rules:

1. Validators always vote once and only once on one height (Rule 1)
2. Validators always vote for the child of its previous vote within a predefined n blocks (Rule 2)

Once a full node sees ¾+ validators signed on one block, the block will be treated as finalized and never reverted. Otherwise, all the full nodes and validators can still wait until enough blocks have been produced to ensure the probabilistic finality. For BSC, with 21 validators, full nodes and validators can wait ⅔*21+1=15 blocks to ensure a relatively secure finality, in this case, the predefined n can be set to 15.

5.2 Theory Proof

5.2.1 Validators Set is Fixed

Proposition: A block is said to be in “finalized status” if it gets voted by more than ¾ validators. If more than ½ validators are honest and behave under the above Rule 1 and Rule 2, honest validators can only vote one chain into a finalized status if they vote within n block time, where n is the same predefined number in Rule2 above.

We can prove the above proposition by proving the assumption is impossible to happen:

Assumption: Honest validators under Rule 1 and Rule 2 can vote two blocks on two different chain forks into finalized within n block periods.

⇒ The worst case: out of total 2f+1 validators, f+1 are honest validators, while f are malicious validators.

⇒ Both Block A and B gets at least V=3*(2f+1)/4 + votes.

⇒ At least K= V-f honest validators vote for Block A, so does block B, where K = V-f > 3*(2f+1)/4 -f = f/2 + ¾ > f/2.

⇒ As K > f/2, and 2K > f, At least one honest validator voted for both Block A and Block B, and the distance between block A and B is smaller than n.

⇒ If block A and block B on the same height, above conclusion break Rule 1, if not, above conclusion break Rule 2.

Once the n blocks finality can be ensured by consensus protocol, then we have the conclusion: Honest validators always get the same finalized block.

5.2.2 Validators Set is Changed

Above mechanism needs a precondition that the validators set is fixed, this can be satisfied within an epoch, but validators will be reelected when epoch is over, so we should deal with the validators set change between different epochs.

As the Rule 2 can’t prohibit new validators’ vote on the first block of the epoch, we take the following rules to deal with this scene:

• New validators’ votes for the first n blocks of each epoch won’t be involved as valid finality votes, this will be ensured by consensus protocol.
• If the new validators number is less than ¼ validators, the fast finality works as normal, the first n blocks also have chance to get ¾+ votes.
• If the new validators number is more than ¼ validators, then the first block of the epoch has to wait until n blocks have been produced, this block has no chance to get fast finality, and the remaining first n-1 blocks may get finalized when the n+1 block gets ¾+ votes.

5.3 Longest Chain

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.

As the block voted by more than ¾ validators within n blocks is considered as ‘finalized’, it should be considered as the longest chain even though there are other chain forks with higher difficulty sum. This can be implemented by validators to drop any new chain forks that have non-finalized blocks at the same height.

This is expected to reduce the chance of chain re-organization and stabilize the block producing further.

5.4 Reward

In order to make the block get finalized faster, once the validators see the votes for the block are more than ¾ 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.

5.4.1 Reward Rules

• Validators whose vote is wrapped into the vote attestation can get reward
• The block get finalized within one block, within two blocks and others, their reward weight would be 8:4:1
• The reward will be paid by our system reward contract

5.5 Slash

5.5.1 Slash Rules

• The validator who violates the two 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 remaining submitters that submit malicious evidence of the validators won’t get any reward.

6. License

The content is licensed under CC0.

[Keefe]

Fast Finality Mechanism Analysis

1. Mechanism

1.1 Validator vote rules

For BSC, validator number v is 21, the predefined n is ½*v+1 = 11, the vote rules can be described as follows.

1. Validators always vote once and only once on one height (Rule 1)
2. Validators always vote for the child of its previous vote within a predefined n blocks. (Rule 2)

1.2 Aggregate Votes for Attestation

1. When validators producing blocks, if they see one unfinalized nearest ancestor block gathered ¾*v+ votes from valid validators, they should aggregate these votes as an attestation for the ancestor block. We call this ancestor block as the attested block in this document.
2. The distance height between the attested block and current block should no larger than ¼*v when aggregating the votes.
3. The distance height between the attested block and finalized block should no larger than ¼*v when aggregating the votes.
4. When validators are changed after one epoch, the newly joined validators’ votes for the first n blocks will be regarded as invalid.

1.3 Longest Chain

Under the validators vote rules, we can be sure no more than one fork will include attestation at the same time. So our longest chain rule can be described as follows.

1. The fork that includes the higher attested block is considered as the longest chain.
2. When there are no attested blocks in all forks, fall back to compare the sum of the “Difficulty” field.

1.4 Finality Rule

There are two steps to fast finalize a block, the first step we call justify, the second step we call finalize.

1. Once a block has an attestation in its header, the attested block is justified.
2. Then the last justified block by the current attested block is finalized.
3. The attestation can be inherited, if the block has no new attestation, it will inherit its parent block’s attestation.

If a block can’t be fast finalized, it will be finalized by n blocks finality rule. We can have the conclusion that the fork finalized by fast finality wouldn’t longer than n blocks, we will discuss this further in the next section.

2.Scenario Analysis

2.1 No Forks

The reward mechanism will encourage the validators to assemble the attestation into header as early as possible, which makes the block get finalized in two blocks in most cases.

2.2 Increase on justified fork

The following picture describes the fast finality processing when forks exist, we can divide this processing into several steps.

1. Before blockC, there is no attestation in both blockA and blockA1’s fork, the blockA’s fork and blockA1’s fork can keep on increasing.
2. Once the node receives blockC, blockA is justified. The node should produce blocks based on blockA fork, but it can keep on receiving blockA1 fork’s child blocks.
3. Once the node receives blockE, blockC is justified and blockA is finalized. The node should produce blocks based on blockC fork, it can keep on receiving blockC2 fork’s blocks, but it can’t receive blockA1 fork’s blocks anymore.

We can try to illustrate why blockA can be finalized:

1. Once a node receives blockE, it means blockC has been justified, the blockC can be justified means there are more than ¾*v validators have received blockC and voted for blockC.
2. Because these validators received blockC, these ¾*v+ validators have justified blockA, so they should produce blocks based on blockA fork after they have received blockC.
3. Which means after the blockC height, there are no more than ¼*v validators can produce blocks based on blockA1 fork.
4. The distance between blockC and blockX should be no larger than ¼v, so the blockA1 fork’s max length should be no larger than ½v, and because the majority validators are mining on the blockA fork, so the blockA1 fork will be given up.

Because the distance between blockC and blockX should be no larger than ¼v, and the distance between blockC and blockE should be no larger than ¼v, so the distance between blockX and blockE should no larger than ½*v, then we can have the conclusion:

A fork is finalized by fast finality, its length should be no larger than ½*v blocks, otherwise it should be finalized by n blocks finality.

2.3 Increase on non-justified fork

Because of network delay and node distribution etc. reasons, different nodes may have different perspectives for forks. For example, the node1 may have the fork perspective like the upper part of the following picture, the node2 may have the fork perspective like the lower part of the following picture.

The node2 has received blockA, but didn’t receive its attestation, so the blockA in node2 can’t get justified, the node2 increased its fork bases on blockA1.

The node1 has received blockA and its attestation, so node1 should produce blocks based on blockA after receiving the blockC, but there are no more blocks to justify blockC or its child blocks, so the blockA can’t be finalized. Once the blockA1 has been finalized after n blocks, the node1 will change to increase based on blockA1, the blockA fork will be given up.

From this scenario, we can illustrate why we need two steps to finalize a block. If we just use one step, different nodes may get different finalized blocks due to different fork perspectives.

2.4 Increase on max difficulty fork

When there are no attested blocks in all forks, fall back to the original mechanism, the block will be finalized by n blocks finality.

3.Modifications for Code Level

There are some notable changes:

1. The attestation would be inserted into the block header’s extra field.
2. The attestation info would be stored in the consensus snapshot, and need to modify consensus snapshot structure.
3. The chain level finality info would be stored in the database.
4. The longest chain rule would be modified.
5. The attestation assembling rules would be written into parlia consensus.

[Keefe]

BEP-126: Introduce Fast Finality Mechanism (Updated)

• BEP-126: Introduce Fast Finality Mechanism
  • 1. Summary
  • 2. Abstract
  • 3. Status
  • 4. Motivation
  • 5. Specification
  • 6. License

1. Summary

This BEP introduces a fast finality mechanism on the BNB Smart Chain.

2. Abstract

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:

1. A block is proposed by a validator and propagated to other validators.
2. Validators use their BLS private key to sign for the block as a vote message.
3. Gather the votes from validators into a pool.
4. Aggregate the BLS signature if its direct parent block has gotten enough votes when proposing a new block.
5. Set the aggregated vote attestation into the extra field of the new block’s header.
6. Validators and full nodes who received the new block with the direct parent block’s attestation can justify the direct parent block.
7. 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.

3. Status

This BEP is working in progress.

4. Motivation

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+1=15 blocks
to ensure a relatively secure finality, it would be quite long time for some critical applications.

5. Specification

5.1 Fast Finality Mechanism

We introduce a vote mechanism to reach fast finality, the whole mechanism includes several rules in vote and consensus.

5.1.1 Validator Vote Rules

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.

1. A validator must not publish two distinct votes for the same height. (Rule 1)
2. A validator must not vote within the span of its other votes . (Rule 2)
3. 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:

1. h(t1) == h(t2) is not allowed. (Rule 1)
2. h(s1) < h(s2) < h(t2) < h(t1) is not allowed. (Rule 2)

5.1.2 Aggregate Votes Rules

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:

1. 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.

5.1.3 Finality Rules

There are two steps to finalize a block, the first step we call justify, the second step we call finalize.

1. 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 vote justified, or
• (3) the height distance between this block and the current header is longer than ⅔*v, and there is no block vote justified,
  we call this block naturally justified.

2. A block is called finalized if

• (1) it is the root, or
• (2) it is vote justified and its direct child is vote justified.

5.1.4 Longest Chain

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 based on the finalized block, so the fork including the
highest finalized 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 finalized 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.

1. The fork that includes the higher finalized block is considered as the longest chain.
2. When the finalized block is the same, fall back to compare the sum of the “Difficulty” field.

5.1.5 Validator Liveness

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+1=15, this can protect the chain from getting increased
in a malicious fork.

5.2 Theory Proof

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 more than ⅓*v 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:

1. If s1 → t1 and s2 → t2 are distinct super majority links, then h(t1) != h(t2).
2. 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:

3. there exists at most one super majority link s → t with h(t) == n.
4. there exists at most one vote justified block with height n.

With these four properties in hand, we move to the main theorems.

5.2.1 Accountable Safety

Theorem 1 (Accountable Safety). Two blocks in different forks cannot both be finalized.

Let Am (with vote justified Am+1, meaning h(Am) + 1 == h(Am+1)) and Bn (with vote justified direct child Bn+1, meaning
h(Bn) + 1 == h(Bn+1)) be distinct finalized blocks as following figure. 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 vote 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. If the super
majority link’s source h(Bj-1) is naturally justified, and if h(Bj-1) >= h(Am), because of the probabilistic finality,
we won’t let the Am+1 block insert to the chain, so this won’t happen; if h(Bj-1) < h(Am), this violates the vote Rule 2.

5.2.2 Plausible Liveness

Theorem 2 (Plausible Liveness). Super majority links can always be added to produce new finalized blocks, provided there exist children extending the finalized chain.

We have two kinds of justified block: vote justified and naturally justified block, with the justified block grow, the
validators can always start new round voting without violating any vote rules, then we know there always will be new
vote justified blocks, and once one of its direct child block has been vote justified, this block can be finalized without
violating any vote rules.

5.3 Reward

In order to make the block get finalized faster, once the validators see the votes for the block are more than 2/3 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.

5.3.1 Reward Rules

• 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

5.4 Slash

5.4.1 Slash Rules

• 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.

6. License

The content is licensed under CC0.