Inherent bias in selection of winner towards vaults with a higher total supply

[code423n4]

Lines of code

https://github.com/GenerationSoftware/pt-v5-prize-pool/blob/4bc8a12b857856828c018510b5500d722b79ca3a/src/libraries/TierCalculationLib.sol#L91-L97

Vulnerability details

Impact

Inherence bias in modulo in generating random numbers will result in users using vaults with a higher total supply being more likely to win compared to users using a vaults with a lower total supply.

Proof of Concept

Using modulo to generate random numbers have an inherent bias. To better illustrate this bias, we can generate the number of occurence for the random number x that is only slightly bigger than modulo y. In the below example, x = 255, and y = 107 is used.

As we can see in this example, modulo introduces a bias in the first 42 numbers. This is due to how smaller numbers can show up more times than their bigger counterparts. But we must note that this bias is reduced the bigger the difference in the x and y value.

Now in our case, we are using x = _userSpecificRandomNumber and y = _vaultTwabTotalSupply. _userSpecificRandomNumber is the keccak256 output hence can be understood as uniformly distributed over the range of uint256. _vaultTwabTotalSupply, on the other hand is a number much smaller than this as it is the total supply of vault's balance in 18 decimals. This bias may be considered too small to matter in our case if we are only concerned for a single random number.

However, we are checking for a range of numbers, or more specifically the user who is deemed a "winner" is one whose random number fall below the winning zone. This means that a range of numbers matter depending on the size of the zone. The zone is calculated as _userTwab * _vaultContributionFraction * _tierOdds. This zone can be huge depending on various factors such as the tier we are in. In this case, the bias introduced in the modulo operator are biased towards smaller numbers and the severity is bolstered by the fact that in our current implementations of selecting winners, we are only interested in smaller numbers since we want them to fall below the zone.

The end result is that vaults with a higher total supply, hence more bias towards producing smaller numbers, have a higher odds of being a winner compared to that of a vault with a smaller total supply.

Tools Used

Manual Review

Recommended Mitigation Steps

Consider using other forms of random number generation that does not favour vaults of different supply.

Assessed type

Math

[asselstine]

Ah! We have a mitigation for modulo bias here: Uniform Random Number

We will apply it!

[c4-sponsor]

asselstine marked the issue as sponsor confirmed

[Picodes]

Let's place ourselves in a case where a user as a chance 1 / 1e6 of winning, meaning his winning zone is ~ 1 / 1e6 the _vaultTwabTotalSupply. For the bias to be significant let's say we want the probability of being in that zone to be increased by 1e-6, then we need roughly the modulo bias to be increased by 1e-6.

Then we need the _vaultTwabTotalSupply to be of the order of magnitude 2^250, in order for the bias toward the first values to be significant.

Overall unless I am missing something I think we can reasonably consider this bias to be not significant and downgrade this report to low severity.

[c4-judge]

Picodes changed the severity to QA (Quality Assurance)

[c4-judge]

Picodes marked the issue as grade-a