High Gas Consumption and Potential DoS Risk in MaxHeap Solidity Contract

[c4-bot-5]

Lines of code

https://github.com/code-423n4/2023-12-revolutionprotocol/blob/main/packages/revolution/src/CultureIndex.sol#L322 https://github.com/code-423n4/2023-12-revolutionprotocol/blob/main/packages/revolution/src/MaxHeap.sol#L132-L151

Vulnerability details

Impact

The MaxHeap contract, as currently implemented, poses a significant risk in terms of gas consumption and potential Denial of Service (DoS) attacks. The primary issue arises when the heap grows so large that the values of items are minimally different from each other. In such a scenario, updating an item's value could result in numerous swaps to maintain the heap's max-heap property, leading to excessive gas costs.

This issue is particularly acute for users with high voting power in the context of the voting mechanism that interacts with the MaxHeap.

https://github.com/code-423n4/2023-12-revolutionprotocol/blob/main/packages/revolution/src/CultureIndex.sol#L322

        maxHeap.updateValue(pieceId, totalWeight);

As the heap size increases and the differences between item values decrease, the cost of maintaining the heap structure becomes prohibitively high. This can lead to a scenario where significant voters are effectively unable to participate due to gas limitations, resulting in a de facto DoS condition.

Voters have no other options except to:

• wait for an opportune time hoping the heap structure has changed such that it would not make their voting running out of gas.
• delegate a portion of their votes to different account(s) and submit multiple votes from there.

This could significantly disrupt the normal functioning of the contract and the associated voting mechanism. If left unaddressed, it could lead to increased costs for users, restricted participation, and potential manipulation of the voting process by those willing to pay higher gas fees.

Proof of Concept

The issue is inherent in the design and implementation of the MaxHeap contract.

https://github.com/code-423n4/2023-12-revolutionprotocol/blob/main/packages/revolution/src/MaxHeap.sol#L132-L151

    /// @notice Update the value of an existing item in the heap
    /// @param itemId The item ID whose vote count needs to be updated
    /// @param newValue The new value for the item
    /// @dev This function adjusts the heap to maintain the max-heap property after updating the vote count
    function updateValue(uint256 itemId, uint256 newValue) public onlyAdmin {
        uint256 position = positionMapping[itemId];
        uint256 oldValue = valueMapping[itemId];

        // Update the value in the valueMapping
        valueMapping[itemId] = newValue;

        // Decide whether to perform upwards or downwards heapify
        if (newValue > oldValue) {
            // Upwards heapify
            while (position != 0 && valueMapping[heap[position]] > valueMapping[heap[parent(position)]]) {
                swap(position, parent(position));
                position = parent(position);
            }
        } else if (newValue < oldValue) maxHeapify(position); // Downwards heapify
    }

Specifically, the updateValue function above is designed to adjust an item's position in the heap to maintain the max-heap property. In a scenario where the heap is large and the value differences between items are minimal, this function will result in a high number of swaps in the while loop or maxHeapify() in the else clause.

https://github.com/code-423n4/2023-12-revolutionprotocol/blob/main/packages/revolution/src/MaxHeap.sol#L83-L113

    /// @notice Swap two nodes in the heap
    /// @param fpos The position of the first node
    /// @param spos The position of the second node
    function swap(uint256 fpos, uint256 spos) private {
        (heap[fpos], heap[spos]) = (heap[spos], heap[fpos]);
        (positionMapping[heap[fpos]], positionMapping[heap[spos]]) = (fpos, spos);
    }

    /// @notice Reheapify the heap starting at a given position
    /// @dev This ensures that the heap property is maintained
    /// @param pos The starting position for the heapify operation
    function maxHeapify(uint256 pos) internal {
        uint256 left = 2 * pos + 1;
        uint256 right = 2 * pos + 2;

        uint256 posValue = valueMapping[heap[pos]];
        uint256 leftValue = valueMapping[heap[left]];
        uint256 rightValue = valueMapping[heap[right]];

        if (pos >= (size / 2) && pos <= size) return;

        if (posValue < leftValue || posValue < rightValue) {
            if (leftValue > rightValue) {
                swap(pos, left);
                maxHeapify(left);
            } else {
                swap(pos, right);
                maxHeapify(right);
            }
        }
    }

Each swap operation involves multiple state changes, including updating mappings for heap positions and item values. These state changes are gas-intensive operations in the Ethereum Virtual Machine (EVM). The problem is exacerbated as the heap grows in size, leading to an increased number of swaps and, consequently, higher gas costs.

Tools Used

Manual

Recommended Mitigation Steps

1. Heap Size Limit: Implementing a limit on the size of the heap can help manage the gas costs. Once the limit is reached, new items can only be added if they have a higher value than a minimum value in the heap. This would require users with certain voting weight to create a new piece.

2. Gas Optimization: Review and optimize the smart contract code for gas efficiency. This can include minimizing state changes and optimizing the logic in the maxHeapify and updateValue functions.

3. Alternative Data Structures: Consider using different data structures that might be more gas-efficient for your specific use case, like a sorted list or a balanced binary tree.

4. Off-Chain Calculations: For applications where immediate on-chain sorting is not critical, you could move some of the heap management off-chain and only update the on-chain data periodically or under certain conditions.

5. Gas Refund Mechanism: Implement a mechanism to refund gas for users who contribute significantly to the maintenance of the heap structure.

Assessed type

DoS

[c4-pre-sort]

raymondfam marked the issue as sufficient quality report

[c4-pre-sort]

raymondfam marked the issue as duplicate of #111

[c4-pre-sort]

raymondfam marked the issue as duplicate of #519

[c4-pre-sort]

raymondfam marked the issue as duplicate of #15

[c4-judge]

MarioPoneder changed the severity to QA (Quality Assurance)

[c4-judge]

MarioPoneder marked the issue as grade-b