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

Gas Inefficiency: O(n²) Duplicate Check

muzammilmohammed678

Root + Impact

Description

  • * The `enterRaffle()` function uses nested loops to check for duplicate players in the array. The duplicate check compares every pair of players in the array, resulting in O(n²) time complexity.

    * As the number of players grows, the gas cost for entering the raffle increases quadratically. With 100 players, the function performs 4,950 comparisons. With 1,000 players, it performs 499,500 comparisons, potentially exceeding gas limits.

    ```solidity:85:90:src/PuppyRaffle.sol

    // 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");

    }

    }

    ```


Risk

Likelihood:

  • * This occurs on every call to `enterRaffle()` as the array grows larger

    * Early entrants cause later entrants to pay exponentially higher gas fees

    * With sufficient players, the function may exceed block gas limits, making the contract unusable

Impact:

  • * Unfair gas costs for later entrants compared to early entrants

    * Potential DoS attack vector - early attacker can make contract unusable

    * Contract becomes economically unviable as gas costs become prohibitive

    * Poor user experience with high transaction costs

Proof of Concept

```solidity
// Scenario: 100 players already in array
// New entrant with 1 player must check:
// Comparisons = 100 * 101 / 2 = 5,050 comparisons
// Gas cost: ~5,050 * ~100 gas = ~505,000 gas just for duplicate check
​
// Scenario: 1,000 players already in array
// Comparisons = 1,000 * 1,001 / 2 = 500,500 comparisons
// Gas cost: ~500,500 * ~100 gas = ~50,050,000 gas
// This exceeds typical block gas limits!
```

Recommended Mitigation

```diff
+ mapping(address => bool) public hasEntered;
​
function enterRaffle(address[] memory newPlayers) public payable {
require(msg.value == entranceFee * newPlayers.length, "PuppyRaffle: Must send enough to enter raffle");
+
+ // Check for duplicates in new batch and against existing players
+ for (uint256 i = 0; i < newPlayers.length; i++) {
+ require(!hasEntered[newPlayers[i]], "PuppyRaffle: Duplicate player");
+ require(newPlayers[i] != address(0), "PuppyRaffle: Cannot enter with zero address");
+ }
+
for (uint256 i = 0; i < newPlayers.length; i++) {
+ hasEntered[newPlayers[i]] = true;
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");
- }
- }
emit RaffleEnter(newPlayers);
}
+
+ // Reset mapping when raffle ends
+ function selectWinner() external {
+ // ... existing code ...
+ delete players;
+ // Reset hasEntered mapping for all players
+ for (uint256 i = 0; i < players.length; i++) {
+ if (players[i] != address(0)) {
+ hasEntered[players[i]] = false;
+ }
+ }
+ // ... rest of function
+ }
```
​
This reduces duplicate checking from O(n²) to O(n) per entry, making gas costs linear instead of quadratic.
Updates

Lead Judging Commences

ai-first-flight-judge Lead Judge 16 days 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!