Array.sol:: Inefficient Array Operations

[c4-bot-5]

Lines of code

https://github.com/reserve-protocol/protocol/blob/master/contracts/libraries/Array.sol#L9-L17

Vulnerability details

Impact

The contract Array.sol uses two functions to check if an array of ERC20 token addresses has unique values.

The first function utilizes a nested loop to check each address with every other address in the array.

This results in quadratic time complexity (O(n^2)), which may cause inefficient execution with large arrays and may even risk exceeding Ethereum block gas limit.

The second function assumes the input array to be sorted in ascending order and checks for uniqueness in linear time (O(n)).

While this is more efficient in comparison to the first function, it brings an additional constraint that the array should be in a sorted state before checking for uniqueness.

If the ordering of elements in the array is disrupted or isn't sorted in the first place, the function may not serve its purpose correctly.

Proof of Concept

Inefficient array checking code:

https://github.com/reserve-protocol/protocol/blob/master/contracts/libraries/Array.sol#L9-L17

function allUnique(IERC20[] memory arr) internal pure returns (bool) {
    uint256 arrLen = arr.length;
    for (uint256 i = 1; i < arrLen; ++i) {
        for (uint256 j = 0; j < i; ++j) {
            if (arr[i] == arr[j]) return false;
        }
    }
    return true;
}  

Array checking with sorted input assumption:

https://github.com/reserve-protocol/protocol/blob/master/contracts/libraries/Array.sol#L21-L27

function sortedAndAllUnique(IERC20[] memory arr) internal pure returns (bool) {
    uint256 arrLen = arr.length;
    for (uint256 i = 1; i < arrLen; ++i) {
        // Here it's assumed that the array is already sorted in ascending order
        if (uint160(address(arr[i])) <= uint160(address(arr[i - 1]))) return false;
    }
    return true;
} 

Tools Used

Manual Review

Recommended Mitigation Steps

To improve the efficiency of array operations, consider using a mapping or set-like data structure to check for uniqueness.

This would reduce the time complexity to O(1) for adding and checking elements.

For already sorted arrays, it might be useful to implement a binary search algorithm or hash table for checking elements, resulting in efficient execution.

Additionally, if array ordering is important for the application, consider implementing a function to sort the array before checking with the sortedAndAllUnique function or specify in the function comments that it requires an ordered array as input.

Assessed type

Invalid Validation