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

`RankedChoice::_isInArray()` can use merkle proofs instead of array looping, which can reduce chance Denial-of-Service attacks and lead to more efficient code and lower gas usage.

blaze

Description

Looping through the entire array to find if an element exists is gas inefficient as traversing an array in O(n) time complexity.

Impact

RankedChoice::_isInArray() function is used inside all external functions and even recursively in RankedChoice::selectPresident() function. This can easily lead to Denial-of-Service attacks for large array inputs in its parent functions.

Proof of concept

Add below snippet to RankedChoiceTest.t.sol and run the test case.

function testDoSForLargeCandidatesList() public {
uint256 CANDIDATES_COUNT = 10;
for (uint256 i = 0; i < CANDIDATES_COUNT; i++) {
orderedCandidates.push(address(uint160(i)));
}
​
for (uint256 i = 0; i < 1; i++) {
vm.prank(voters[i]);
rankedChoice.rankCandidates(orderedCandidates);
}
​
vm.warp(block.timestamp + rankedChoice.getDuration()+1);
rankedChoice.selectPresident();
​
uint256 initialGas1 = gasleft();
​
uint256 LESS_VOTERS_COUNT = voters.length - 50;
for (uint256 i = 0; i < LESS_VOTERS_COUNT; i++) {
vm.prank(voters[i]);
rankedChoice.rankCandidates(orderedCandidates);
}
​
vm.warp(block.timestamp + rankedChoice.getDuration()+1);
rankedChoice.selectPresident();
​
uint256 finalGas1 = gasleft();
uint256 gasUsed1 = initialGas1 - finalGas1;
​
console.log("Gas used for less voters: ", gasUsed1);
​
uint256 MORE_VOTERS_COUNT = voters.length;
for (uint256 i = 0; i < MORE_VOTERS_COUNT; i++) {
vm.prank(voters[i]);
rankedChoice.rankCandidates(orderedCandidates);
}
​
vm.warp(block.timestamp + rankedChoice.getDuration()+1);
rankedChoice.selectPresident();
​
uint256 finalGas2 = gasleft();
uint256 gasUsed2 = finalGas1 - finalGas2;
​
console.log("Gas used for more voters: ", gasUsed2);
​
assert(gasUsed2 > gasUsed1);
}
forge test --mt testDoSForLargeCandidatesList -vvv
# Gas used for less voters: 16721386
# Gas used for more voters: 32283120

Recommended Mitigation

Merkle proofs provide an efficient way to verify if an element exists in some collection of data, which in our case is a large array input. For example, below snippet can be implemented where MerkleProof is a library that exposes verify function that takes array of merkle proofs, the merkle root and the leaf data which can be hash of voter address.

if (!MerkleProof.verify(merkleProof, i_merkleRoot, leaf)) {
revert RankedChoice__InvalidMerkleProof();
}

Tools used

  • Foundry

Updates

Lead Judging Commences

inallhonesty Lead Judge 12 months ago
Submission Judgement Published
Invalidated
Reason: Non-acceptable severity

Support

FAQs

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