FIP-0023 Source

TitleBreak ties between tipsets of equal weight
AuthorSarah Azouvi, Aayush Rajasekaran
Discussions-Tohttps://github.com/filecoin-project/FIPs/issues/22
StatusFinal
Review period ends2021-10-11
TypeTechnical (Core)
Created2021-09-07

Spec Sections

FIP-0023: Break ties between tipsets of equal weight

Simple Summary

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.

Abstract

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.

Change Motivation

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.

Specification

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.

Design Rationale

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.

Backwards Compatibility

This FIP proposes a “soft” change that maintains full backward compatability. No new network version is needed.

Test Cases

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

Security Considerations

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.

Incentive Considerations

No change to incentives.

Product Considerations

No change to product considerations, except that increased overall stability is a net improvement.

Implementation

TODO in each of the Filecoin implementations.

Copyright and related rights waived via CC0.

Citation

Please cite this document as:

Sarah Azouvi, Aayush Rajasekaran, "FIP-0023: Break ties between tipsets of equal weight," Filecoin Improvement Proposals, no. 0023, September 2021. [Online serial]. Available: https://fips.filecoin.io/fips/fip-0023.