Implement a tie breaker for forks of equal weight

[sa8]

Problem

The tie-breaker described in the spec for EC has never been implemented. Although not critical it would help miners converge more easily towards a common chain. This means that when two forks with the same weight occur all the miners that have received both forks will mine on the same one. Without a tie-breaker they would (randomly?) mine on both and may extend the forks for longer.

Proposed solution

For two tipsets of the same weight we choose the one with the smallest electionProof. In the case where two Tipsets of equal weight have the same min Election proof, the miner will compare the next smallest Election proof in the Tipset (and select the Tipset with the next smaller proof). This continues until one Tipset is selected.

Other solutions

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 would work just as fine.

Draft FIP here: https://docs.google.com/document/d/1VHm_0rh9XCcjJsrnpbLtbFpLNRmOgkEoNTNlt0NHiOQ/edit?usp=sharing

[sa8]

This solution was part of the specs but was never implemented.

[momack2]

@sa8 - what is the current chance of getting a tie?

[sa8]

@momack2 I don't know, I'll need to ask Sentinel to check. I think that "small" forks happen quite often but don't have numbers.

[steven004]

@sa8 - what is the current chance of getting a tie?

An example how a fork could get a tie:

Let's suppose the network power keeps the same in certain time across several heights, when there is a network issue, perhaps propagation delay of something, there are 3 blocks at height n, A1, A2, A3 (all valid and with the same parents), and 3 blocks at height n+1, B1, B2, B3, B4, B5, but like the following:

  (A1 + A2) <- (B1, B2, B3)
  (A1 + A2 + A3) <- (B4, B5) 

And then, at height n+2, it will be found that the two tipsets (B1, B2, B3) and (B4, B5) have the same weight. It's a tie.

@momack2

[steven004]

A proposal of solution

To compare the ticket value is one way to do it, but it looks a little complicated. Another way is to revise the weight algorithm which is already complex, to add in a bias, like adding the height number into the calculation.

w[r] = original_w[r] + block_num * (height % H)

H might be 2^8 or something.

[sa8]

@steven004 I think it's quite obvious for everyone what a tie looks like... the question is given current network conditions how often this happens.

[steven004]

@steven004 I think it's quite obvious for everyone what a tie looks like... the question is given current network conditions how often this happens.

I would think it's hard to get an answer, since it depends on a lot of things, network quality, number of miners, chain syncing performance, etc. What we could see is: the better the networker running, the less chance to get a tie.
For me, I found twice in test network when I simply check chain status for perhaps 1000 heights, but, the test net was not runnig as good as the mainnet.

What I propose is to reduce the chance to almost 0, no matter how well the network is running.

[arajasek]

@sa8 FIP PR opened here: #156.

I added a higher priority rule for equal-weight tipsets of unequal sizes (choose the bigger tipset). Please let me know if you think that makes sense.

[sa8]

Thanks for the heads up @arajasek!
Could you share some intuition why we want to prioritize bigger tipsets?

[arajasek]

@sa8 I don't think we necessarily want to prioritize bigger tipsets, this just felt cleaner to me in the unequal size case. Otherwise, we keep comparing the tickets until we reach the end of the smaller tipset (assuming they are all equal tickets) and then based on the spec, it's unclear to me what we should do.

[kaitlin-beegle]

This is now FIP0023!