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

Unbounded O(n²) duplicate check in PuppyRaffle: enterRaffle permanently denies entry at scale

angmarwitchking

Root + Impact

enterRaffle checks for duplicate players with a nested loop that scans the entire players array — including everyone who entered in prior calls — on every entry.


Description

This is O(n^2) in the total number of players and re-validates previously checked pairs on every call, so the gas cost of entering grows quadratically with how full the raffle already is. Because the cost grows without bound, it eventually exceeds the maximum gas a block can hold, after which no entry transaction can be mined and permanently denying participation.

// The Duplicate Check
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:

Medium-High. Reached through normal growth (there is no maximum player cap) or forced deliberately: an attacker Sybil-fills the array with controlled addresses to push players.length past the threshold and lock out everyone after.

Impact:

High. Because enterRaffle's gas cost grows as O(n²), it exceeds any fixed block gas limit at a bounded number of players — demonstrated here crossing the ~60M absolute block max at roughly 200. Past that point, no entry can be included in any block, regardless of the prevailing gas limit, permanently denying participation.

Proof of Concept

Two equal batches of 100; the only difference is that the second runs against an already-populated array, isolating the quadratic growth:

The identical 100-player operation costs ~3.7× more against a half-full array, matching the O(n²) prediction (doubling players quadruples the pairwise comparisons). At ~200 players a single entry already exceeds the maximum block gas, so it cannot be mined.

// SPDX-License-Identifier: MIT
pragma solidity ^0.7.6;
pragma experimental ABIEncoderV2;
​
import {Test, console} from "forge-std/Test.sol";
import {PuppyRaffle} from "../src/PuppyRaffle.sol";
​
contract DoSTest is Test {
PuppyRaffle puppyRaffle;
uint256 entranceFee = 1e18;
address feeAddress = address(0x2);
uint256 duration = 1 days;
​
function setUp() public {
puppyRaffle = new PuppyRaffle(entranceFee, feeAddress, duration);
}
​
function test_denialOfServiceGasGrowth() public {
uint256 batchSize = 100;
​
// --- Batch 1: 100 players into an EMPTY raffle ---
address[] memory playersOne = new address[](batchSize);
for (uint256 i = 0; i < batchSize; i++) {
playersOne[i] = address(uint160(i + 1)); // addresses 1..100
}
uint256 gasStartOne = gasleft();
puppyRaffle.enterRaffle{value: entranceFee * batchSize}(playersOne);
uint256 gasUsedOne = gasStartOne - gasleft();
​
// --- Batch 2: another 100 players, now the array ALREADY holds 100 ---
address[] memory playersTwo = new address[](batchSize);
for (uint256 i = 0; i < batchSize; i++) {
playersTwo[i] = address(uint160(i + 1 + batchSize)); // addresses 101..200 (no overlap)
}
uint256 gasStartTwo = gasleft();
puppyRaffle.enterRaffle{value: entranceFee * batchSize}(playersTwo);
uint256 gasUsedTwo = gasStartTwo - gasleft();
​
emit log_named_uint("gas, first 100 ", gasUsedOne);
emit log_named_uint("gas, second 100", gasUsedTwo);
​
// identical operation, dramatically higher cost => scales with existing player count
assertGt(gasUsedTwo, gasUsedOne);
}
}
​
Gas Growth Output:
forge test --match-test test_denialOfServiceGasGrowth -vvvv
​
Ran 1 test for test/DoS.t.sol:PuppyRaffleReentrancyTest
[PASS] test_denialOfServiceGasGrowth() (gas: 113038541)
Logs:
gas, first 100 : 24026166
gas, second 100: 88976899

Recommended Mitigation

Replace the O(n²) scan with an O(1) mapping check:

mapping(address => bool) private s_hasEntered;
...
for (uint256 i = 0; i < newPlayers.length; i++) {
require(!s_hasEntered[newPlayers[i]], "PuppyRaffle: Duplicate player");
s_hasEntered[newPlayers[i]] = true;
players.push(newPlayers[i]);
}
Updates

Lead Judging Commences

ai-first-flight-judge Lead Judge about 1 hour 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!