| fip | title | author | discussions-to | status | type | created | review-period-end | spec-sections |
|---|---|---|---|---|---|---|---|---|
0023 |
Break ties between tipsets of equal weight |
Sarah Azouvi (@sa8), Aayush Rajasekaran (@arajasek) |
Final |
Technical (Core) |
2021-09-07 |
2021-10-11 |
4.1.4.2 |
The general process by which nodes on the Filecoin network choose between two tipsets is by picking the heavier tipset based on a weight function (see here).
It is not an unlikely event for two tipsets to have the same weight. When this happens, we should have a simple rule to pick one of the tipsets as canonically "heavier" so as to achieve consensus faster. This FIP proposes such a rule.
Filecoin needs a rule to decide between forks of equal weight. Although not critical it would help block producers converge more easily towards a common chain. This means that when two forks with the same weight occur, all the block producers that have received both forks will mine on the same one. Without a tie-breaker they would randomly choose one and may extend the forks for longer.
Implementing such a rule will help the network achieve consensus faster. This has an immediate effect of reducing the number of orphaned blocks, which increases profits for block producers. More importantly, this FIP will reduce the time it takes the network to recover from slowdowns or outages, since nodes will achieve consensus faster.
For two tipsets with the same weight, we pick the tipset with the smallest winning Ticket. In the case where two Tipsets of equal weight have the same smallest Ticket, we compare the next smallest Ticket in the Tipset (and select the Tipset with the smaller one). This continues until one Tipset is selected. There are 2 interesting cases to consider:
- The tipsets are of unequal size: the larger tipset is almost always gonna be heavier in this case. In the virtually impossible event of a tie, we explicitly leave behaviour undefined.
- The tipsets are of equal size, but all the tickets are identical: This is only possible if a block producer has produced 2 different blocks with the same ticket. We explicitly leave behaviour undefined here too, since the producer will be heavily slashed for this.
Any solution that is both deterministic and non-biasable (i.e. an adversary may not make their chain more likely to be selected by the chain selection algorithm in the case of forks of equal weight) may work. The ElectionProof is unbiasable and hence is a good candidate for tie-breaker. Any deterministic rule other than minimum ticket would work just as well.
This FIP proposes a "soft" change that maintains full backward compatability. No new network version is needed.
The following test cases should be covered:
- two tipsets with different min tickets
- two tipsets with one min ticket the same
- two tipsets with several min tickets the same
- three heaviest heads
We should be confident that the proposed tiebreaking rule is unbiasable by adversarial block producers. That aside, this FIP is a strict improvement to network security.
No change to incentives.
No change to product considerations, except that increased overall stability is a net improvement.
TODO in each of the Filecoin implementations.
Copyright and related rights waived via CC0.