President Elector

Summary

Due to Duplicate Check in RankedChoice::selectPresident Function

Vulnerability Details

The nested loops in `selectPresident()` create significant efficiency problems. They result in high gas costs, poor scalability, and potential block gas limit issues as the number of voters or candidates increases. The function's performance degrades quadratically, making it impractical for larger elections. Redundant array checks further exacerbate these issues, necessitating optimization for better gas efficiency and scalability. The `_isInArray` check might be performed multiple times for the same candidate across different voters.

Impact

1. **Gas Costs:** Nested loops can be extremely gas-intensive, especially if the number of voters or candidates is large. This could make the function prohibitively expensive to call.

2. **Block Gas Limit:** If the number of voters or candidates is very large, the function might exceed the block gas limit, making it impossible to execute.

3. **Scalability:** As the number of voters or candidates increases, the function's performance will degrade quadratically.

4. **Redundant Checks:** The `_isInArray` check is performed for each candidate of each voter, which is inefficient if many voters have ranked the same candidates.

**Proof of Concept:**

We demonstrate this vulnerability using a test function that compares the gas cost of `selectPresident()` with different numbers of voters:

:br- With 24 voters: 804,206 gas

- With 100 voters: 1,069,226 gas

:br<details>

<summary>PoC</summary>

:brPlace the following test into `RankedChoiceTest.t.sol`:

:br```javascript

function testDenialOfService() public {

assert(rankedChoice.getCurrentPresident() != candidates[0]);

orderedCandidates = [candidates[0], candidates[1], candidates[2]];

uint256 startingIndex = 0;

uint256 endingIndex = 24;

for (uint256 i = startingIndex; i < endingIndex; i++) {

vm.prank(voters[i]);

rankedChoice.rankCandidates(orderedCandidates);

}

:brvm.warp(block.timestamp + rankedChoice.getDuration());

:bruint256 gasStart = gasleft();

rankedChoice.selectPresident();

uint256 gasEnd = gasleft();

uint256 gasUsedFirst = (gasStart - gasEnd);

console.log("Gas cost of the first voters:", gasUsedFirst);

:brstartingIndex = endingIndex + 1;

endingIndex = 100;

orderedCandidates = [candidates[3], candidates[1], candidates[4]];

for (uint256 i = startingIndex; i < endingIndex; i++) {

vm.prank(voters[i]);

rankedChoice.rankCandidates(orderedCandidates);

}

vm.warp(block.timestamp + rankedChoice.getDuration() + 1);

uint256 gasStartSecond = gasleft();

rankedChoice.selectPresident();

uint256 gasEndSecond = gasleft();

uint256 gasUsedSecond = (gasStartSecond - gasEndSecond);

console.log("Gas cost of the second voters:", gasUsedSecond);

}

```

</details>

Tools Used

Manual review

Recommendations

1. Use a Mapping for Candidate Tracking: Instead of using `_isInArray`, use a mapping to track which candidates have been added. This reduces the complexity from O(n^2) to O(n).

```diff

// ...(existing code)

:br+ mapping(address => bool) memory candidateSet;

for (uint256 i = 0; i < VOTERS.length; i++) {

address[] memory orderedCandidates = s_rankings[VOTERS[i]][

s_voteNumber

];

for (uint256 j = 0; j < orderedCandidates.length; j++) {

+ if (!candidateSet[orderedCandidates[j]]) {

+ candidateSet[orderedCandidates[j]] = true;

- if (!_isInArray(s_candidateList, orderedCandidates[j])) {

s_candidateList.push(orderedCandidates[j]);

}

}

}

// ...(existing code)

```

2. Consider implementing a batching mechanism to process voters in smaller groups across multiple transactions.

3. Evaluate alternative voting mechanisms that may be more gas-efficient for large numbers of voters.