search

code-423n4 / 2024-02-ai-arena-findings

4 stars 3 forks source link

Unfair assignment of points in RankedBattle.sol #649

Closed c4-bot-9 closed 8 months ago

c4-bot-9 commented 8 months ago

Lines of code

https://github.com/code-423n4/2024-02-ai-arena/blob/cd1a0e6d1b40168657d1aaee8223dc050e15f8cc/src/RankedBattle.sol#L424-L499

Vulnerability details

Impact

Fighters with the same ELO, stake, mergingPortion and amount of wins and losses during a round, but with different win-loss patterns will earn different amounts of NRN from the RankedBattle contract when the round ends and the NRN rewards get distributed.

Proof of Concept

Given some values for ELO, stake and mergingPortion, the amount of points to add or remove should always be the same, but sometimes aren't in the case of losing. If the amount of points to remove is greater than the current amount, which could happen when using $mergingPortion>0$, then points are reset to zero since it's not possible to hold negative points.

Why is this a problem? Let's say fighter A and B have the same ELO=1600, stakingFactor=1 and use the same mergingPortion=25. For simplicity let's also assume that the ELO doesn't change after a fight (at least significantly). Given these values, winning adds 1200 points in the RankedBattle contract, while losing removes 1600 points. Both fighters win 2 battles and lose 1 battle in the current round in the following way:

If 2000 NRN are being distributed in this round, fighter A would get 1200 NRN and fighter B would get 800 NRN, even if both fighters had the same performance and settings.

Add the following two tests to RankedBattle.t.sol to see this behavior:

function testWinLossPatternsWWL() public {
    address player = vm.addr(3);
    _mintFromMergingPool(player);
    uint8 tokenId = 0;
    _fundUserWith4kNeuronByTreasury(player);
    vm.prank(player);
    _rankedBattleContract.stakeNRN(1 * 10 ** 18, tokenId);
    assertEq(_rankedBattleContract.amountStaked(0), 1 * 10 ** 18);

    vm.prank(address(_GAME_SERVER_ADDRESS));
    _rankedBattleContract.updateBattleRecord(tokenId, 25, 0, 1600, false);
    vm.prank(address(_GAME_SERVER_ADDRESS));
    _rankedBattleContract.updateBattleRecord(tokenId, 25, 0, 1600, false);
    vm.prank(address(_GAME_SERVER_ADDRESS));
    _rankedBattleContract.updateBattleRecord(tokenId, 25, 2, 1600, false);

    assertEq(_rankedBattleContract.accumulatedPointsPerFighter(0, 0) == 800, true);
}

function testWinLossPatternsWLW() public {
    address player = vm.addr(3);
    _mintFromMergingPool(player);
    uint8 tokenId = 0;
    _fundUserWith4kNeuronByTreasury(player);
    vm.prank(player);
    _rankedBattleContract.stakeNRN(1 * 10 ** 18, tokenId);
    assertEq(_rankedBattleContract.amountStaked(0), 1 * 10 ** 18);

    vm.prank(address(_GAME_SERVER_ADDRESS));
    _rankedBattleContract.updateBattleRecord(tokenId, 25, 0, 1600, false);
    vm.prank(address(_GAME_SERVER_ADDRESS));
    _rankedBattleContract.updateBattleRecord(tokenId, 25, 2, 1600, false);
    vm.prank(address(_GAME_SERVER_ADDRESS));
    _rankedBattleContract.updateBattleRecord(tokenId, 25, 0, 1600, false);

    assertEq(_rankedBattleContract.accumulatedPointsPerFighter(0, 0) == 1200, true);
}

Tools Used

Manual Review

Recommended Mitigation Steps

Make the assignment of points independent of the win-loss pattern for a given round.

Assessed type

Other

c4-pre-sort commented 8 months ago

raymondfam marked the issue as insufficient quality report

c4-pre-sort commented 8 months ago

raymondfam marked the issue as duplicate of #177

c4-judge commented 8 months ago

HickupHH3 marked the issue as unsatisfactory: Invalid

fnanni-0 commented 7 months ago

@HickupHH3 I think the validity of this issue should be reconsidered. From the docs it seems clear that the amount of NRN rewarded is a function of "Your NFT’s performance in the current round of competition", among other variables. In addition, "When a Challenger NFT reaches 0 Points, further losses will result in their stake being placed in a new mode called “at risk”".

Taking this into account and what I deem a robust design, I don't find reasonable to tolerate scenarios in which players with equivalent performances are rewarded different amounts of NRN, which is a consequence of not correctly penalizing losses in edge cases. In the example I described in the Proof of Concept, there are 400 losing points unaccounted when Fighter A loses its second battle. IMO the correct behavior should be to remove the 1200 points and to put at risk stake proportionate to the unaccounted points (i.e. curStakeAtRisk * 400 / 1600).

HickupHH3 commented 7 months ago

Again, similar reasoning to #609 that this is a recommendation on the points mechanism.

fnanni-0 commented 7 months ago

@HickupHH3 Thanks for the reply. I just want to add one comment.

The root cause of #729 strikes me as the same as the one pointed at in my report: in some scenarios, depending on win-loss pattern and context, the potential amount of points to lose is disproportionate to the amount of points to win thanks to how point losses are capped at zero, which leads to unfair assignment of points. As I also explained in the Impact section, this affects the amount of NRN a player can earn, which in my opinion represents a loss of expected funds, not just a flawed design, making it a medium issue as well.

I don't understand why #729 is considered a medium issue and #649 just a recommendation. Shouldn't both be either a recommendation or medium issues? Maybe even duplicates given that the root cause is the same?

HickupHH3 commented 7 months ago

729 hasn't been confirmed as an issue yet, this will be reviewed together with it.

d3e4 commented 7 months ago

@HickupHH3 @fnanni-0 The impact here is that the amount of points distributed depends on the win-loss pattern. One imagines the final tally of a user should be binomially distributed, with an expectation of zero. But because of the effect reported here the expectation is slightly positive. However, it is not the absolute number of points of a user that ultimately matter, but the share of the final total number of points distributed in a round (either directly or into the merging pool (#609)). No user is more likely than any other to end up with a more advantageous win-loss pattern, so this effect imparts no unfairness, since the win-loss pattern cannot be influenced. The expected advantage is indeed 0 (but the variance is slightly increased). Thus the impact described here is not an issue.

This comment applies to both #609 and #649. The merging pool is simply a different destination for the points, and the root cause is the same.

Note that the exploit where the stake is massively increased is not at all mentioned either in #609 or #649. Therefore this should not be considered a duplicate of #729/#1967.

fnanni-0 commented 7 months ago

@d3e4 That’s a good insight, and I agree to some extent, but not being able to influence the win-loss pattern shouldn’t be enough to disregard this issue.

Rounds happen every 2 weeks. At each round there will be fighters that by chance, because of WL pattern, get more points than others and there will be fighters that will get the same advantage/disadvantage a few rounds in a row. Of course in the long run this evens out, but the context will be different. The price of NRN, the amount and quality of players, the raffled NFT features and value, etc. changes over time. Someone who gets very lucky in his first couple of rounds could decide to take the profits and exit the game. I don’t think it makes sense to arbitrarily decide to analyze what the expected distribution of points could be over lots of rounds assuming everything else stays constant.

I cannot see how this could be the intended design of the game and not an issue, as it randomly creates unfairness at each round. Take the setup of my PoC and add a few extra battles and the effect gets a bit amplified, not reduced. WWWWLLL = 0 points, WWWLWLL = 0 points, WWWLLWL = 0 points, WWLWLWL = 0 points, but WLWLWLW = 1200 points.

All of this can be fixed by handling points differently, for example always accounting for all the points lost as I explained in this comment

d3e4 commented 7 months ago

@fnanni-0 Actually, I think this perhaps has a (barely?) valid Medium impact after all. I don't seem to find any agreement with your comment, however. So let me first exclude what could be an impact from what I can glean from your comment.

The amplification you point out could in principle make this an issue. If the distribution is significantly altered because of this issue, then users might feel cheated. One would expect that the outcome for a specific user in a round is fairly normally distributed. So let's see what the new distribution will be.

Wins are counted in points, while losses are counted in stake put at risk. We can just rescale such that a win is $+1$ and a loss is $-1$. Then without this issue (e.g. with the fix I have suggested) the accumulating wins and losses is a random walk. The final sum, i.e. the "profit" at the end of the round, is then essentially binomially distributed. More precisely, when on the positive side the $+1$ and $-1$ would slightly vary because of the ELO-factor, but when on the negative side they are exact because stake is always put at risk or reclaimed based on the initial stake (we assume the user doesn't change his stake).

The issue you point out is that when crossing from positive to negative up to one loss is discounted. It turns out that the number of these crossings is distributed essentially like a folded binomial distribution (the absolute value of the final sum, but "scale" the range from $[0,n]$ to $[0,n/4]$). For $n = 1000$ matches in a round the mean of this distribution is $6.0563$ and the variance $22.7905$ (compare with the variance of the number of wins which is $250$). The skewness however is $0.9881$. The sum of these distributions, i.e. the result of this issue, is very close to the original binomial distribution but with a new mean of $6.0563$ and only slightly higher variance $272.7905$. The skewness is minimal at $0.0239$. A graph to illustrate it wouldn't help. It is almost indistinguishable from a normal distribution.

My conclusion from this (based on how the issue has been discussed so far) is that the only significant impact is the increased mean. And as already argued this is not an issue except through the exploit described in #1967/#729/#457. The way you can think of this is that the wins and losses are first counted as you suggest they should be, but then, when the round is finished, we award everyone an additional prize distributed as the half binormal distribution described above. This leads us to something that actually could be somewhat of an impact.

The increased mean (of about $6$ for $1000$ rounds) depends on how many rounds are played. This might vary per player. However, it only increases by the square root. It tend towards $\sqrt{\frac{n}{8\pi}}$. Roughly $4, 6, 9$ for $500, 1000, 2000$ rounds, respectively. Thus players who get to play more matches unfairly earn slightly more.

This of course critically depends on how much the number of matches varies among players. The impact is an additional expected $2$ units for a player who gets to play $1000 matches rather than only $500$. Compare this to the standard deviation of $16$ over $1000$ matches, so I think it is significant. The only way I see this happening is if some player is particularly popular to initiate matches against (I would think the batteries will be far more expensive than the extra $2$ winnings).

The root cause is the same as #1967 so this must be considered a duplicate. Impact is at most Medium, while I think #1967 should be High, which suggest a partial-30, so since the aspect about a varying number of matches was not really mentioned in the original report it seems fairer to round this down to a partial-25.

Edit: I forgot to consider that going from negative to positive is similarly capped so these wins will be penalised the same and the mean would actually remain $0$, which eliminates the impact.