Submitted by IllIllI, also found by Trust
The README states If two users place bids at the same price but with different quantities, the queue will pull from the bid with a higher quantity first, but the data-structure used for implementing this logic, is not used properly and essentially has its data corrupted when a large bid that is the current minimum bid, is split into two parts, so that a more favorable price can be used for a fraction of the large bid. The underlying issue is that one of the tree nodes is modified, without re-shuffling that nodes location in the tree.
The minimum bid as told by the priority queue will be wrong, leading to the wrong bids being allowed to withdraw their funds, and being kicked out of the fraction of bids that are used to buy the NFT.
The priority queue using a binary tree within an array to efficiently navigate and find the current minimum based on a node and its children. The sorting of the nodes in the tree is based, in part, on the quantity in the case where two bids have the same price:
https://github.com/code-423n4/2022-12-tessera/blob/f37a11407da2af844bbfe868e1422e3665a5f8e4/src/lib/MinPriorityQueue.sol#L111-L122
The algorithm of the binary tree only works when the nodes are properly sorted. The sorting is corrupted when a node is modified, without removing it from the tree and re-inserting it:
https://github.com/code-423n4/2022-12-tessera/blob/f37a11407da2af844bbfe868e1422e3665a5f8e4/src/modules/GroupBuy.sol#L299-L319
Lets say that the tree looks like this:
If A is modified so that q (quantity) goes from 10 to 5, B should now be at the root of the tree, since it has the larger size, and would be considered the smaller node. When another node is added, say, F:(p:100,q:6), the algorithm will see that F has a larger size than A, and so A will be popped out as the min, even though B should have been. All nodes that are under B (which may be a lot of the nodes if they all entered at the same price/quantity) essentially become invisible under various scenarios, which means the users that own those bids will not be able to withdraw their funds, even if they really are the lowest bid that deserves to be pushed out of the queue. Note that the swimming up that is done for F will not re-shuffle B since, according to the algorithm, F will start as a child of C, and B is not in the list of parent nodes of C.
When modifying nodes of the tree, remove them first, then re-add them after modification.
stevennevins (Tessera) confirmed and mitigated:
