Summary
The duplicates check makes the gas cost to entry exponentially higher for every new participant to the point of millions of gas for players number 100 and 101.
Vulnerability Details
The double loop used to check the duplicates condition generates extreme gas costs for each new player that joins the raffle:
for (uint256 i = 0; i < players.length - 1; i++) {
for (uint256 j = i + 1; j < players.length; j++) {
require(players[i] != players[j], "PuppyRaffle: Duplicate player");
}
PoC
Please make the following modifications to PuppyRaffleTest.t.sol:
define the following addresses in state variables section:
address randomPlayer = makeAddr("You did not wake up today to be mediocre.");
address mAlice = makeAddr("We are what we repeatedly do. Excellence then is not an act but a habit.");
define the following function:
function addHundred() internal {
address[] memory newPlayers = new address[](100);
for (uint256 i = 1; i < 101; i++) {
address randomPlayer = address(i);
newPlayers[i - 1] = randomPlayer;
}
puppyRaffle.enterRaffle{value: entranceFee * 100}(newPlayers);
}
call the new function in setUp:
function setUp() public {
puppyRaffle = new PuppyRaffle(
entranceFee,
feeAddress,
duration
);
++ addHundred();
}
copy the following test:
function testPlayers100and101() public {
address[] memory players = new address[](2);
players[0] = randomPlayer;
players[1] = mAlice;
puppyRaffle.enterRaffle{value: entranceFee * 2}(players);
assertEq(puppyRaffle.players(100), randomPlayer);
assertEq(puppyRaffle.players(101), mAlice);
}
run with forge test --mt testPlayers100and101
Result:
Running 1 test for test/PuppyRaffleTest.t.sol:PuppyRaffleTest
[PASS] testPlayers100and101() (gas: 4368276)
Test result: ok. 1 passed; 0 failed; 0 skipped; finished in 30.51ms
In today's prices gas: 4368276 = approx $1507.96
forge test --mt testPlayers100and101 --gas-report
Running 1 test for test/PuppyRaffleTest.t.sol:PuppyRaffleTest
[PASS] testPlayers100and101() (gas: 4373736)
Test result: ok. 1 passed; 0 failed; 0 skipped; finished in 32.95ms
| src/PuppyRaffle.sol:PuppyRaffle contract | | | | | |
|------------------------------------------|-----------------|---------|---------|---------|---------|
| Deployment Cost | Deployment Size | | | | |
| 3229550 | 14458 | | | | |
| Function Name | min | avg | median | max | # calls |
| enterRaffle | 4346208 | 5287120 | 5287120 | 6228032 | 2 |
| players | 702 | 702 | 702 | 702 | 2 |
If we modify the addHundred function to add 150 instead of 100, adjust the checks, then we call again a function that adds 2 new players, the gas cost is over $3k.
Running 1 test for test/PuppyRaffleTest.t.sol:PuppyRaffleTest
[PASS] testPlayers100and101() (gas: 9470045)
Test result: ok. 1 passed; 0 failed; 0 skipped; finished in 64.48ms
Impact
The gas costs to join the raffle for the players that join towards the end are unjustifiably higher compared to the first joiners. It get's super expensive really fast, up to the point it reaches the gas block limit.
Tools Used
Manual review, foundry tests
Recommendations
The approach undertaken has a time complexity of O(n^2). This can be done in O(n) as follows:
++ mapping(address => bool) private activePlayers;
function enterRaffle(address[] memory newPlayers) public payable {
require(msg.value == entranceFee * newPlayers.length, "PuppyRaffle: Must send enough to enter raffle");
for (uint256 i = 0; i < newPlayers.length; i++) {
-- players.push(newPlayers[i]);
-- }
-- // Check for duplicates
-- for (uint256 i = 0; i < players.length - 1; i++) {
-- for (uint256 j = i + 1; j < players.length; j++) {
-- require(players[i] != players[j], "PuppyRaffle: Duplicate player");
-- }
-- }
++ address player = newPlayers[i];
++ // Check if the player already entered
++ require(!activePlayers[player], "PuppyRaffle: Player already registered");
++ // Set player active
++ activePlayers[player] = true;
++ players.push(player);
++ }
emit RaffleEnter(newPlayers);
}
We keep both the old players array and the new activePlayers because we are still going to use the players array for selecting a winner or finding the players index, but we need the mapping to ensure a faster and less resource intensive duplication check. Other parts of the code should be updated to reflect the new activePlayers mapping, for example there should be a delete activePlayers in selectWinner function.
