`MaxHeap.extractMax` function doesn't return the element that reached maximum value first in some cases

[c4-bot-8]

Lines of code

https://github.com/code-423n4/2023-12-revolutionprotocol/blob/d42cc62b873a1b2b44f57310f9d4bbfdd875e8d6/packages/revolution/src/MaxHeap.sol#L136-L151 https://github.com/code-423n4/2023-12-revolutionprotocol/blob/d42cc62b873a1b2b44f57310f9d4bbfdd875e8d6/packages/revolution/src/MaxHeap.sol#L156-L164

Vulnerability details

Impact

• Revolution protocol is meant to enable users from adding their art pieces to be voted on and auctioned if the piece passes voting quorum, then the auction proceeds are distributed between the relevant parties (the creators and the protocol).

• The entry point for users is to add their art piece by calling CulturalIndex.createPiece function with the art piece metadat and an array of creators addresses, and each added art piece is going to be added to a MaxHeap data structure (saved in the MaxHeap contract) where pieces are arranged as a nodes of parents and children, where the top of the tree is the art pieces with the highest votes and the corresponding childs of that parent is of pieces with lower votes, and with each vote; the MaxHeap rearrange the values to preserve the max heap characteristics.

• When the art piece got votes >= quorum votes; it's dropped by the AuctionHouse to be auctioned by the AuctionHouse contract, this process requires the MaxHeap to extract the top voted art piece to be auctioned.

• The process of dropping the top voted art piece is not automatic; meaning that it waits anyone to call AuctionHouse.settleCurrentAndCreateNewAuction function to start the process.

• But it was noticed that if there's three art pieces with an equal number of votes, and this number is the highest votes number, then it's assumed that the first art piece that reached this number is the one to be dropped and auctioned first, then the second one that reached the maximum votes then the third one,.. but it was noticed that the behaviour of MaxHeap.extractMax doesn't work as intended:

  • it will return the first art piece that reached this highest value.
  • then, it will return the last art piece that reached this highest value ignoring the piece that reached this value before it, see the attached proof of concept and the explained scenario in the section below.

Proof of Concept

Code Instances:

MaxHeap.updateValue function

    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
    }

MaxHeap.extractMax function

    function extractMax() external onlyAdmin returns (uint256, uint256) {
        require(size > 0, "Heap is empty");

        uint256 popped = heap[0];
        heap[0] = heap[--size];
        maxHeapify(0);

        return (popped, valueMapping[popped]);
    }

Foundry PoC:

1. Add this testDoesItWorkCorrectly test inside the MaxHeapTestSuite test contract that resides in the MaxHeap.t.sol test file which is located in the following directory packages/revolution/test/max-heap/MaxHeap.t.sol :

   ├── MaxHeap.t.sol
   │   ├── MaxHeapTestSuite
   │       ├── testDoesItWorkCorrectly

    function testDoesItWorkCorrectly() public {
        uint256 highestVotes = 10;

        //1. two art pieces are added:
        vm.stopPrank();
        vm.startPrank(address(cultureIndex));
        maxHeap.insert(1, 0);
        maxHeap.insert(2, 0);
        vm.warp(block.timestamp + 2 hours);

        //2. the first art piece got highestVotes:
        maxHeap.updateValue(1, 10);

        //3. then another 3 art pieces are added:
        maxHeap.insert(3, 0);
        maxHeap.insert(4, 0);
        maxHeap.insert(5, 0);
        vm.warp(block.timestamp + 2 hours);

        //4. the fourth and the fifth art piece got highestVotes with 2-hours apart:
        maxHeap.updateValue(4, 10);
        vm.warp(block.timestamp + 2 hours);
        maxHeap.updateValue(5, 10);

        //5. extracting the highest voted piece that's going to be called by the `CulturIndex.dropTopVotedPiece`, and it will be the first piece:
        (uint256 pieceId, uint256 pieceVotes) = maxHeap.extractMax();
        assertEq(pieceId, 1);

        //6. then extracting the second highest voted piece that's going to be called by the `CulturIndex.dropTopVotedPiece`:
        (pieceId, pieceVotes) = maxHeap.extractMax();

        //7. so as can be noticed: it extracted the fifth piece instead of the fourth piece, while it should extract the fourth piece because it reached the highest votes before the fifth piece:
        assertFalse(pieceId == 4);
        assertEq(pieceId, 5);
        console.log("extracted pieceId is : ", pieceId);
        console.log("extracted pieceVotes is : ", pieceVotes);
        vm.stopPrank();
    }

2. Explained scenario:

   1. two pieces are added: 1 and 2.
   2. piece#1 got the highest votes.
   3. then another three pieces are added.
   4. piece#4 got the highest votes.
   5. then after some time; piece#5 got the highest votes.
   6. maxHeap.extractMax function is called, where it extracted the maximum piece which is piece#1.
   7. then maxHeap.extractMax function is called again to extract the next maximum piece: it's supposed to extract piece#4 as it was the first piece to reach the highest votes before piece#5; but it extracted piece#5 instead.

3. Test result:

$ FOUNDRY_PROFILE=dev forge test --match-test testDoesItWorkCorrectly -vvv
Running 1 test for test/max-heap/Updates.t.sol:MaxHeapUpdateTestSuite
[PASS] testDoesItWorkCorrectly() (gas: 349055)
Logs:
  pieceId is :  5
  pieceVotes is :  10

Test result: ok. 1 passed; 0 failed; 0 skipped; finished in 18.58ms

Tools Used

Manual Review.

Recommended Mitigation Steps

Update MaxHeap.extractMax function to handle this case.

Assessed type

Context

[c4-pre-sort]

raymondfam marked the issue as sufficient quality report

[c4-pre-sort]

raymondfam marked the issue as duplicate of #266

[c4-pre-sort]

raymondfam marked the issue as not a duplicate

[c4-pre-sort]

raymondfam marked the issue as primary issue

[c4-pre-sort]

raymondfam marked the issue as high quality report

[rocketman-21]

same issue as other maxheap issues

[c4-sponsor]

rocketman-21 (sponsor) confirmed

[c4-sponsor]

rocketman-21 (sponsor) disputed

[rocketman-21]

actually upon further inspection this is how it should function

time that the pieces were inserted has no weight to the order in which they are extracted

just because pieceId 4 and 5 both have 10 votes, the MaxHeap does not guarantee that the 4th will be extracted first even if it reached 10 votes first.

[c4-judge]

MarioPoneder changed the severity to QA (Quality Assurance)

[MarioPoneder]

See comment on previous primary issue: https://github.com/code-423n4/2023-12-revolutionprotocol-findings/issues/266#issuecomment-1879666356

[c4-judge]

MarioPoneder marked the issue as grade-b

[DevHals]

Hi @MarioPoneder,

as per your comment on issue 266; this one has a runnable PoC to clearly identify what is wrong with the MaxHeap.extractMax function and how it introduces unfair auctions for art-pieces as some might reach top-voted before other pieces but will not be auctioned first (and might never get the chance to be auctioned)!

I kindly ask you to take a second look and re-evaluate this issue,

Thanks!

[MarioPoneder]

Thank you for your comment!

This is an edge-case of 2 or more art prices getting the same votes, see also #582. Furthermore, MaxHeap is not designed to respect insertion order, only the votes.
Nevertheless this is a valid feature suggestion and therefore QA seems appropriate.