Puppy Raffle
AI First Flight #1
Beginner FriendlyFoundrySolidityNFT
EXP
View results
Previous Next
Submission Details
Severity: medium
Valid

O(n^2) duplicate check in `PuppyRaffle::enterRaffle` prices out and eventually blocks all new entrants

verdoolaegelouis

Root + Impact

Root cause: PuppyRaffle::enterRaffle re-scans the whole players array with a nested loop on every entry, so the duplicate check costs O(n²) gas in the number of entrants.

Impact: entry cost grows quadratically until a new entry exceeds the block gas limit, closing the raffle to further participants. An attacker can force that state cheaply and deliberately.

Description

  • Entering should cost roughly the same for every participant, and the raffle should stay open for the whole duration.

  • The duplicate check compares every pair in players, including all entries from previous calls, on each new entry. With n players already in the array, adding k more costs on the order of (n+k)² comparisons. Early entrants pay almost nothing; late ones pay orders of magnitude more, and past a few thousand entries no entry fits in a block.

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; i++) {
@> for (uint256 j = i + 1; j < players.length; j++) {
@> require(players[i] != players[j], "PuppyRaffle: Duplicate player");
}
}
emit RaffleEnter(newPlayers);
}

Risk

Likelihood:

  • Happens under ordinary use as soon as a raffle becomes popular — no attacker needed for the unfairness, only for the denial of service.

  • An attacker enters a large batch of addresses they control in one transaction. They pay the entrance fees, but they can reclaim them through refund, and the array never shrinks because refund only blanks slots.

Impact:

  • Later participants are priced out and eventually cannot enter at all: the raffle is denied to everyone but the early entrants.

  • Combined with the predictable draw, an attacker who fills the array and then refunds keeps the field small and their own odds high while honest users are locked out.

Proof of Concept

Gas cost for entering the same number of players, measured before and after the array is already populated:

function test_entryCostGrowsQuadratically() public {
address[] memory first = new address[](100);
for (uint256 i = 0; i < 100; i++) first[i] = address(uint160(1000 + i));
uint256 g0 = gasleft();
puppyRaffle.enterRaffle{value: 100 ether}(first);
uint256 costFirst = g0 - gasleft();
​
address[] memory second = new address[](100);
for (uint256 i = 0; i < 100; i++) second[i] = address(uint160(5000 + i));
uint256 g1 = gasleft();
puppyRaffle.enterRaffle{value: 100 ether}(second);
uint256 costSecond = g1 - gasleft();
​
// the second batch of the same size costs several times more
assertGt(costSecond, costFirst * 2);
}

Control — a single entry into an empty raffle is cheap, confirming the cost comes from the array size and not from the entry itself:

function test_firstEntryIsCheap() public {
address[] memory p = new address[](1);
p[0] = address(uint160(1));
uint256 g = gasleft();
puppyRaffle.enterRaffle{value: 1 ether}(p);
assertLt(g - gasleft(), 100_000);
}

Recommended Mitigation

Replace the pairwise scan with a mapping keyed by player and round, so the check is O(1) per entrant:

+ mapping(address => uint256) public lastRoundEntered;
+ uint256 public roundId;
​
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++) {
+ require(lastRoundEntered[newPlayers[i]] != roundId + 1, "PuppyRaffle: Duplicate player");
+ lastRoundEntered[newPlayers[i]] = roundId + 1;
players.push(newPlayers[i]);
}
-
- // Check for duplicates
- for (uint256 i = 0; i < players.length; i++) {
- for (uint256 j = i + 1; j < players.length; j++) {
- require(players[i] != players[j], "PuppyRaffle: Duplicate player");
- }
- }
emit RaffleEnter(newPlayers);
}

selectWinner then increments roundId, which invalidates the previous round's entries without clearing the mapping.

Updates

Lead Judging Commences

ai-first-flight-judge Lead Judge about 3 hours ago
Submission Judgement Published
Validated
Assigned finding tags:

[M-01] `PuppyRaffle: enterRaffle` Use of gas extensive duplicate check leads to Denial of Service, making subsequent participants to spend much more gas than prev ones to enter

## Description `enterRaffle` function uses gas inefficient duplicate check that causes leads to Denial of Service, making subsequent participants to spend much more gas than previous users to enter. ## Vulnerability Details In the `enterRaffle` function, to check duplicates, it loops through the `players` array. As the `player` array grows, it will make more checks, which leads the later user to pay more gas than the earlier one. More users in the Raffle, more checks a user have to make leads to pay more gas. ## Impact As the arrays grows significantly over time, it will make the function unusable due to block gas limit. This is not a fair approach and lead to bad user experience. ## POC In existing test suit, add this test to see the difference b/w gas for users. once added run `forge test --match-test testEnterRaffleIsGasInefficient -vvvvv` in terminal. you will be able to see logs in terminal. ```solidity function testEnterRaffleIsGasInefficient() public { vm.startPrank(owner); vm.txGasPrice(1); /// First we enter 100 participants uint256 firstBatch = 100; address[] memory firstBatchPlayers = new address[](firstBatch); for(uint256 i = 0; i < firstBatchPlayers; i++) { firstBatch[i] = address(i); } uint256 gasStart = gasleft(); puppyRaffle.enterRaffle{value: entranceFee * firstBatch}(firstBatchPlayers); uint256 gasEnd = gasleft(); uint256 gasUsedForFirstBatch = (gasStart - gasEnd) * txPrice; console.log("Gas cost of the first 100 partipants is:", gasUsedForFirstBatch); /// Now we enter 100 more participants uint256 secondBatch = 200; address[] memory secondBatchPlayers = new address[](secondBatch); for(uint256 i = 100; i < secondBatchPlayers; i++) { secondBatch[i] = address(i); } gasStart = gasleft(); puppyRaffle.enterRaffle{value: entranceFee * secondBatch}(secondBatchPlayers); gasEnd = gasleft(); uint256 gasUsedForSecondBatch = (gasStart - gasEnd) * txPrice; console.log("Gas cost of the next 100 participant is:", gasUsedForSecondBatch); vm.stopPrank(owner); } ``` ## Recommendations Here are some of recommendations, any one of that can be used to mitigate this risk. 1. User a mapping to check duplicates. For this approach you to declare a variable `uint256 raffleID`, that way each raffle will have unique id. Add a mapping from player address to raffle id to keep of users for particular round. ```diff + uint256 public raffleID; + mapping (address => uint256) public usersToRaffleId; . . 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]); + usersToRaffleId[newPlayers[i]] = true; } // Check for duplicates + for (uint256 i = 0; i < newPlayers.length; i++){ + require(usersToRaffleId[i] != raffleID, "PuppyRaffle: Already a participant"); - 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"); - } } emit RaffleEnter(newPlayers); } . . . function selectWinner() external { //Existing code + raffleID = raffleID + 1; } ``` 2. Allow duplicates participants, As technically you can't stop people participants more than once. As players can use new address to enter. ```solidity 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]); } emit RaffleEnter(newPlayers); } ```

Support

FAQs

Can't find an answer? Chat with us on Discord, Twitter or Linkedin.

Give us feedback!