BEP-126(Draft): Introduce Fast Finality Mechanism

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