0LNetworkCommunity / libra-framework

9 stars 33 forks source link

PoF issue with equal bids for lowest, and set sizes equal to bidders #251

Closed 0o-de-lally closed 3 months ago

0o-de-lally commented 5 months ago

Problem

Currently, there is no mechanism to promote bid competition among validators for the seats auction in Proof of Fee. All eligible validators eventually enter the validator set regardless of their bid amount.

Current Snapshot/Context

In epoch 90, we had 16 validators in the set with the same minimum bid of 1%. Without a competition mechanism, there is no reason for them to change their bids.

Initially Proposed Approach in this Issue

Starting with 40 available seats, remove x seats, where x is a random number between 0 and 4 (10% of 40). With this approach, the number of available seats will tend to decrease over epochs. This is because the number only increases by one if all nodes behave well, and there is a 1/5 chance that x will be zero.

Alternative Approach

To provoke competition among validators when the validator set surpasses the boot-up threshold of 20 compliant validators, the validator set size will be defined by the minimum value between:

  1. Musical Chairs suggestion, and
  2. 90% of qualified bidders

This percentage is experimental and may be adjusted after observing real-world performance. It could also be dynamic, based on another function or randomized within a range, as initially proposed.

Impact on Current Seats Auction

Assuming all 36 validators are compliant in the current epoch and remain the same qualified bidders, we should expect the size for the next epoch to be 33, leaving out the 3 validators with the lowest bids.

If multiple validators have the same lowest bid amount, they will be randomly picked by shuffling their positions after sorting by bid.

Example: The last 3 validators (0x1, 0x2, 0x3) have the lowest bid of 1%, and 2 will be out of the set according to the new rule above. We will shuffle their positions (0x3, 0x1, 0x2) to ensure fairness when picking the one to be in the validator set.

Advantages of the Alternative Approach

soaresa commented 4 months ago

Problem

Currently, there is no mechanism to promote bid competition among validators for the seats auction in Proof of Fee. All eligible validators eventually enter the validator set regardless of their bid amount.

Current Snapshot/Context

In epoch 90, we had 16 validators in the set with the same minimum bid of 1%. Without a competition mechanism, there is no reason for them to change their bids.

Initially Proposed Approach in this Issue

Starting with 40 available seats, remove x seats, where x is a random number between 0 and 4 (10% of 40). With this approach, the number of available seats will tend to decrease over epochs. This is because the number only increases by one if all nodes behave well, and there is a 1/5 chance that x will be zero.

Alternative Approach

To provoke competition among validators when the validator set surpasses the boot-up threshold of 20 compliant validators, the validator set size will be defined by the minimum value between:

  1. Musical Chairs suggestion, and
  2. 90% of qualified bidders

This percentage is experimental and may be adjusted after observing real-world performance. It could also be dynamic, based on another function or randomized within a range, as initially proposed.

Impact on Current Seats Auction

Assuming all 36 validators are compliant in the current epoch and remain the same qualified bidders, we should expect the size for the next epoch to be 33, leaving out the 3 validators with the lowest bids.

If multiple validators have the same lowest bid amount, they will be randomly picked by shuffling their positions after sorting by bid.

Example: The last 3 validators (0x1, 0x2, 0x3) have the lowest bid of 1%, and 2 will be out of the set according to the new rule above. We will shuffle their positions (0x3, 0x1, 0x2) to ensure fairness when picking the one to be in the validator set.

Advantages of the Alternative Approach

0o-de-lally commented 4 months ago

TODO: deduplicate bubble sort and make own module.