Out of Gas Error in QuickSort Function Implementation in Math Library

[c4-bot-9]

Lines of code

https://github.com/code-423n4/2024-04-panoptic/blob/main/contracts/libraries/Math.sol#L753

Vulnerability details

Impact

Out of Gas error which would have significant implications for contract on Ethereum mainnet or the related contracts in general. In the context of the quickSort function in Math Library, this Error could potentially cause the function to fail if the input array is large or in a worst-case order. This is due to the high computational complexity of the QuickSort algorithm (O(n^2) in the worst case), which could exceed the block gas limit. As a result, the transaction would fail, leading to a loss of the gas used in the transaction and disrupting the operation of the contract and causing Denial of Service.

Proof of Concept

function quickSort(int256[] memory arr, int256 left, int256 right) internal pure {
        unchecked {
            int256 i = left;
            int256 j = right;
            if (i == j) return;
            int256 pivot = arr[uint256(left + (right - left) / 2)];
            while (i < j) {
                while (arr[uint256(i)] < pivot) i++;
                while (pivot < arr[uint256(j)]) j--;
                if (i <= j) {
                    (arr[uint256(i)], arr[uint256(j)]) = (arr[uint256(j)], arr[uint256(i)]);
                    i++;
                    j--;
                }
            }
            if (left < j) quickSort(arr, left, j);
            if (i < right) quickSort(arr, i, right);
        }
    }

The function provided above is the quickSort(...) function in the Math.sol contract. Considering an array of size n in reverse order, the quickSort function would take quadratic time to sort this array due to the pivot selection method. Given the gas limit per block in Ethereum, this could lead to a situation where the gas required for the transaction exceeds the block gas limit, causing the transaction to fail.

Tools Used

Manual Review

Recommended Mitigation Steps

To address the “Out of Gas” vulnerability in the quickSort function, the primary mitigation strategy would be to optimize the sorting algorithm. The QuickSort algorithm, while efficient in many cases, has a worst-case time complexity of O(n^2), which can lead to high gas consumption in Ethereum transactions. Therefore, it is recommended to use a more efficient sorting algorithm with better worst-case time complexity. Algorithms such as MergeSort or HeapSort could be considered as they offer a worst-case time complexity of O(n log n), which is more efficient than QuickSort. By optimizing the sorting algorithm, the function can significantly reduce its gas consumption, thereby mitigating the risk of exceeding the Ethereum block gas limit.

Assessed type

Loop

[Picodes]

In the absence of credible scenario, this falls within GAS to me. The report focuses on optimizing the algorithm but considering the gas cost of reading in memory and doing basic operations I doubt it'd have that much of an impact.

[c4-judge]

Picodes changed the severity to QA (Quality Assurance)