Shungy
commented
2 years ago Duplicate: https://github.com/code-423n4/2022-09-artgobblers-findings/issues/125 Also same submission by the warden but without any elaboration: https://github.com/code-423n4/2022-09-artgobblers-findings/issues/71
GalloDaSballo
Lines of code
https://github.com/code-423n4/2022-09-artgobblers/blob/d2087c5a8a6a4f1b9784520e7fe75afa3a9cbdbe/src/ArtGobblers.sol#L576-L685
Vulnerability details
Impact
Sophisticated users to beat assumed minting odds by minting when odds are deterministically better than average
Proof of Concept
The Knuth shuffle is implemented correctly but the deterministic nature of the the shuffle would allows users to mint when odds were better and avoid minting when odds are worse. Take the following example:
Assume we have 10 tokens each with different point values
4 with a value of 1 3 with a value of 2 3 with a value of 3
For each pull the expected value = sum(total value available) / sum(# of tokens available)
For the first pull this expected value is:
4 x 1 + 3 x 2 + 3 x 3 / 10 = 13 / 10 = 1.3
Imagine the first pull yields a token with a value of 1. That token is now excluded changing the expected value of the next pull:
3 x 1 + 3 x 2 + 3 x 3 / 9 = 12 / 9 = 1.33
Depending on the past values that have already been pulled the expected value will be different. A sophisticated user could easily monitor the current expected value and only mint when the expected value is higher than average, choosing not to mint when it is worse than average. This strategy applied throughout the entirety of the mint would allows these users to gain an edge over regular users.
Tools Used
Manual Review
Recommended Mitigation Steps
This vulnerability is a result of the deterministic nature of a Knuth shuffle. Truly unbiased odds are impossible with any deterministic implementation regardless of how random the input is. The expected value across all pulls will perfectly reflect the desire odds but each individual pull does not guarantee it and sophisticated users can abuse this. This risk should either be accepted or a non-deterministic approach should be used.