0x73696d616f - Estimated prize draws in TieredLiquidityDistributor are off due to rounding down when calculating the sum, leading to incorrect prizes

[sherlock-admin2]

0x73696d616f

medium

Estimated prize draws in TieredLiquidityDistributor are off due to rounding down when calculating the sum, leading to incorrect prizes

Summary

Estimated prize draws in TieredLiquidityDistributor are off due to rounding down when calculating the expected prize count on each tier, leading to an incorrect next number of tiers and distribution of rewards.

Vulnerability Detail

ESTIMATED_PRIZES_PER_DRAW_FOR_5_TIERS and the other tiers are precomputed initially in TieredLiquidityDistributor::_sumTierPrizeCounts(). In here, it goes through all tiers and calculates the expected prize count per draw for each tier. However, when doing this calculation in TierCalculationLib.tierPrizeCountPerDraw(), uint32(uint256(unwrap(sd(int256(prizeCount(_tier))).mul(_odds))));, it rounds down the prize count of each tier. This will lead to an incorrect prize count calculation, for example:

grandPrizePeriodDraws == 8 days
numTiers == 5
prizeCount(tier 0) == 4**0 * 1 / 8 == 1 * 1 / 8 == 0.125 = 0
prizeCount(tier 1) == 4**1 * (1 / 8)^sqrt((1 + 1 - 3) / (1 - 3)) == 4 * 0.2298364718 ≃ 0.92 = 0
prizeCount(tier 2) == 4**2 * 1 == 16
prizeCount(tier 3) == 4**3 * 1 == 64
total = 80

However, if we multiply the prize counts by a constant and then divide the sum in the end, the total count would be 81 instead, getting an error of 1 / 81 ≃ 1.12 %

Impact

The estimated prize count will be off, which affects the calculation of the next number of tiers in PrizePool::computeNextNumberOfTiers(). This modifies the whole rewards distribution for the next draw.

Code Snippet

https://github.com/sherlock-audit/2024-05-pooltogether/blob/main/pt-v5-prize-pool/src/abstract/TieredLiquidityDistributor.sol#L574 https://github.com/sherlock-audit/2024-05-pooltogether/blob/main/pt-v5-prize-pool/src/libraries/TierCalculationLib.sol#L113-L115

Tool used

Manual Review

Vscode

Recommendation

Add some precision to the calculations by multiplying, for example, by 1e5 each count and then dividing the sum by 1e5. uint32(uint256(unwrap(sd(int256(prizeCount(_tier)*1e5)).mul(_odds)))); and return prizeCount / 1e5;.

[sherlock-admin3]

1 comment(s) were left on this issue during the judging contest.

infect3d commented:

rounding isn't an issue by itself it looks like a design choice

[nevillehuang]

Request PoC to facilitate discussion

Sponsor comments:

Quality assurance at best, rounding errors are perfectly acceptable here and have no significant impact

What is the maximum impact here?

[sherlock-admin4]

PoC requested from @0x73696d616f

Requests remaining: 3

[0x73696d616f]

Hi @nevillehuang, some context first: Rewards are assigned based on the max tier for a draw, starting at tier 4. So users can claim rewards on tiers 0, 1, 2, 3. Tier 5 has tiers 0, 1, 2, 3, 4. And so on. Each prize tier is claimed 4^t numbers of times for each user, where t is the tier. Each tier has certain odds of occuring, according to the formula here. The prize is distributed by awarding each tier pro-rata tierShares and canary tiers (the last 2) receive canaryShares. So, the more tiers, the more the total prize pool is distributed between tiers, decreasing the prize of each tier.

Now some specific example: When we go from max tier 4 to tier 5, the prize pool is dilluted to the new tier, decreasing the rewards for users for each tier (there are more shares). Going to tier 5 also means that there is 1 tier that has less odds of being claimed. Tier 1 is no longer awarded every draw. Thus, as we have dilluted the prize in the tiers, and added a tier with less odds of occuring, the total rewards expected are now less. This mechanism works to offset luck in the draw. If a certain draw is claimed too many times compared to the expected value, it will likely increase the max tier in the next draw, and decrease the expected rewards of the next draw.

And finally, the issue: The expected number of prizes collected on a certain max tier, ex 4, is calculated by summing the expected prizes collected on each tier (this is well explained in the issue). As the expected number will be off, the expected claim count will also be off. In the issue example, tier 5 has an incorrect expected value of 80 instead of 81. If the number of claimed prizes is 81, > 80, it will advance to tier 5. However, if the expected value was correctly calculated as 81, we would not advance to tier 5, but remain in tier 4. Consequently, the next draw will award less rewards, on average, than it should, as it incorrectly increased the max tier. Here is the calculation of the expected rewards being decreased for the next round, based on the numbers above:

prizePool == 1000
numShares = 100
canaryTierShares = 5

// tier 4
totalShares = 210
tierValue = 1000*100/210 = 476
canaryValue = 1000*5/210 = 24

476*0.125 + 476*1 + 24 = 560

// tier 5
totalShares = 310
tierValue = 1000*100/310 = 323
canaryValue = 1000*5/310 = 16

323*0.125 + 323*0.23 + 323*1 + 16 = 454

[trmid]

The existing algorithm returns the expected number of tiers based on claims. The calculation informs the rest of the system on the number of tiers. As long as the tiers can go up and down based on the network conditions, there is no unexpected consequence of the calculation rounding down.

[MiloTruck]

Escalate

I believe this issue should be low severity as there is barely any impact.

This mechanism works to offset luck in the draw. If a certain draw is claimed too many times compared to the expected value, it will likely increase the max tier in the next draw, and decrease the expected rewards of the next draw.

This is only partially true. The primary purpose of increasing/decreasing the number of tiers based on the number of prizes claimed is to adapt to fluctuating gas prices due to network congestion. When gas prices are cheap, more prizes will be claimed than the expected amount. The pool adapts to this by moving up one tier, thereby decreasing the rewards per prize as it will still be profitable to claim prizes with low gas costs. The converse is also true for when gas prices are expensive.

ESTIMATED_PRIZES_PER_DRAW_FOR_5_TIERS and the other values are an approximation of the expected number of prizes claimed; they don't have to be the exact values calculated. As long as they are roughly around their exact values, which they are in this case, the number of tiers will still increase/decrease to adapt to changing gas prices.

I believe this is what the sponsor means by "As long as the tiers can go up and down based on the network conditions, there is no unexpected consequence".

The estimated prize count will be off, which affects the calculation of the next number of tiers in PrizePool::computeNextNumberOfTiers(). This modifies the whole rewards distribution for the next draw.

This is an over-exaggeration of the impact. There is no "correct" rewards distribution for the next draw based on the number of prizes claimed - as long as the rewards distribution scales to accommodate fluctuating gas prices, the mechanism has fulfilled its purpose and there is no issue.

[sherlock-admin3]

Escalate

I believe this issue should be low severity as there is barely any impact.

This mechanism works to offset luck in the draw. If a certain draw is claimed too many times compared to the expected value, it will likely increase the max tier in the next draw, and decrease the expected rewards of the next draw.

This is only partially true. The primary purpose of increasing/decreasing the number of tiers based on the number of prizes claimed is to adapt to fluctuating gas prices due to network congestion. When gas prices are cheap, more prizes will be claimed than the expected amount. The pool adapts to this by moving up one tier, thereby decreasing the rewards per prize as it will still be profitable to claim prizes with low gas costs. The converse is also true for when gas prices are expensive.

ESTIMATED_PRIZES_PER_DRAW_FOR_5_TIERS and the other values are an approximation of the expected number of prizes claimed; they don't have to be the exact values calculated. As long as they are roughly around their exact values, which they are in this case, the number of tiers will still increase/decrease to adapt to changing gas prices.

I believe this is what the sponsor means by "As long as the tiers can go up and down based on the network conditions, there is no unexpected consequence".

The estimated prize count will be off, which affects the calculation of the next number of tiers in PrizePool::computeNextNumberOfTiers(). This modifies the whole rewards distribution for the next draw.

This is an over-exaggeration of the impact. There is no "correct" rewards distribution for the next draw based on the number of prizes claimed - as long as the rewards distribution scales to accommodate fluctuating gas prices, the mechanism has fulfilled its purpose and there is no issue.

You've created a valid escalation!

To remove the escalation from consideration: Delete your comment.

You may delete or edit your escalation comment anytime before the 48-hour escalation window closes. After that, the escalation becomes final.

[0x73696d616f]

@MiloTruck there is a correct expected number of prizes, based on the odds and prize count for each tier, and this issue proves it will be off due to rounding down, when it could be fixed (at least partially, not rounding down more than 1 unit). The comments are the source of truth, and the expected number is off

/// @notice Computes the expected number of prizes for a given number of tiers.

The mentioned impact is true.

So unless a comment in the code or readme information is found that says rounding down more than 1 unit is okay, this issue is valid.

[WangSecurity]

As long as they are roughly around their exact values, which they are in this case, the number of tiers will still increase/decrease to adapt to changing gas prices

So in the example by @0x73696d616f if the expected number is 81, but the actual one is 80, the number of tiers can still increase/decrease based on gas conditions?

If the number of claimed prizes is 81, > 80, it will advance to tier 5. However, if the expected value was correctly calculated as 81, we would not advance to tier 5, but remain in tier 4.

Not sure if I understand it correctly, if expected is 80 and actual is 81, we increase to tier 5. If expected is 81 and actual is 81, we remain tier 4?

[0x73696d616f]

To advance we need actual >= expected, because if actual < expected it returns 4. And it also impacts the gas adaptation mechanism because the expected value is off.

[MiloTruck]

So in the example by @0x73696d616f if the expected number is 81, but the actual one is 80, the number of tiers can still increase/decrease based on gas conditions?

@WangSecurity My point is that the number of tiers will only need one more claim to increase, and there isn't really a difference between 80 claims VS 81 claims.

There's a reason why the sponsor chose to dispute, and I believe it's because as long as the number of tiers increases at some point, regardless of at 80 or 81, the number of tiers will still increase/decrease based on gas conditions.

[0x73696d616f]

it was not said anywhere that it is okay for the expected number to be off, so the hierarchy of truth holds and the 2 mentioned impacts are correct. The point is that the difference exceeds small amounts, as is the case in this issue, where the shutdown still "works", but not in the right draw.

[MiloTruck]

it was not said anywhere that it is okay for the expected number to be off, so the hierarchy of truth holds and the 2 mentioned impacts are correct. The point is that the difference exceeds small amounts, as is the case in this issue, where the shutdown still "works", but not in the right draw.

I don't see how #28 is relevant here, it's a completely different issue.

Essentially it boils down to whether you believe the difference between 80 vs 81 claims is significant enough such that it affects the mechanism's ability to increase/decrease tiers according to gas prices. You believe the difference is significant while I (and I believe the sponsor?) don't. Will leave it to the judges to decide though, ultimately it's not up to us.

[InfectedIsm]

https://github.com/sherlock-audit/2024-05-pooltogether-judging/issues/95#issuecomment-2164066705

If the number of claimed prizes is 81, > 80, it will advance to tier 5. However, if the expected value was correctly calculated as 81, we would not advance to tier 5, but remain in tier 4.

So, this simply shift the tier advancement to number of prize > 80 rather than 81 due to rounding in computation (which again isn't an issue, it can even sometimes used purposefully) The formula that the devs have chosen is arbitrary, as much as how they decided to implement it. They could have gone for any other formula to decide the limit of the tier expansion, which would have given another limit, could have been t^5 + 1 or t ^2 * 2 + t^4, the main idea is to expand/contract the number of tier based by measuring how far from the expected odds of winning we are.

[0x73696d616f]

The formula they picked is not arbitrary, it's the exact expected number of claims given that each prize has certain odds and claim count. It will be off due to rounding down.

[WangSecurity]

The primary purpose of increasing/decreasing the number of tiers based on the number of prizes claimed is to adapt to fluctuating gas prices due to network congestion. When gas prices are cheap, more prizes will be claimed than the expected amount. The pool adapts to this by moving up one tier, thereby decreasing the rewards per prize as it will still be profitable to claim prizes with low gas costs

But in that case, if the expected number is off (not the one that should be due to rounding down), then the system won't adapt to fluctuating gas prices correctly and won't move up one tier when it needs to. Or it's wrong?

I see that the rounding down is only by 1, but still in the edge case, expressed in the report, it lead to the protocol behaving in the incorrect way.

Please tell me where I'm wrong.

And is it said anywhere that this expected number doesn't have to be the exact one?

And a bit more info, sponsors setting "sponsor confirmed/disputed" and "won't/will fix" labels doesn't affect the final decision.

[0x73696d616f]

@WangSecurity it will take 1 less claim than supposed to advance to the next tier, so the gas mechanism will not work as expected, you're right.

I could not find any mention that the expected number can be off and as the error exceeds small amounts, it's valid.

[WangSecurity]

With that, I agree that it's a valid issue cause if the expected number is incorrect, then the protocol cannot correctly adapt to gas prices, hence, won't expand tiers correctly, when it should.

Planning to reject the escalation and leave the issue as it is.

[Hash01011122]

I agree with @MiloTruck and @InfectedIsm reasoning, this issue should be informational.

There's no impact of this issue as pointed out by sponsors:

The existing algorithm returns the expected number of tiers based on claims. The calculation informs the rest of the system on the number of tiers. As long as the tiers can go up and down based on the network conditions, there is no unexpected consequence of the calculation rounding down.

[0x73696d616f]

@Hash01011122 there is impact in the rewards distribution, and it was not documented that it's fine for the expected number to be incorrect.

[Hash01011122]

@0x73696d616f with all due respect, I don't see this as a valid issue.

[0x73696d616f]

The reason you provided is based on information that was added post contest (that this is an acceptable bug), which has no weight.

[WangSecurity]

I still stand by my point stated above that in fact has impact and leads to the protocol adapting to gas prices incorrectly. The decision remains the same, planning to reject the escalation and leave the issue as it is.

[WangSecurity]

Result: Medium Unique

[sherlock-admin4]

Escalations have been resolved successfully!

Escalation status:

• MiloTruck: rejected