DittoETH
Ditto
DeFiFoundryOracle
55,000 USDC
View results
Previous Next
Submission Details
Severity: medium
Valid

Order creation can run out of gas since relying on previous order matchtype

hash

Vulnerability Details

If the hint order id has been reused and the previous order type is matched the current code iterates from the head of the linked list under the assumption that since the previous order has been matched it must have been at the top of the orderbook which would mean the new order with a similar price would also be somewhere near the top of the orderbook.

function findOrderHintId(
mapping(address => mapping(uint16 => STypes.Order)) storage orders,
address asset,
MTypes.OrderHint[] memory orderHintArray
) internal returns (uint16 hintId) {
​
// more code
​
// @audit if a reused order's prevOrderType is matched, returns HEAD
​
if (hintOrderType == O.Cancelled || hintOrderType == O.Matched) {
emit Events.FindOrderHintId(0);
continue;
} else if (
orders[asset][orderHint.hintId].creationTime == orderHint.creationTime
) {
emit Events.FindOrderHintId(1);
return orderHint.hintId;
} else if (orders[asset][orderHint.hintId].prevOrderType == O.Matched) {
//@dev If hint was prev matched, it means that the hint was close to HEAD and therefore is reasonable to use HEAD
emit Events.FindOrderHintId(2);
return Constants.HEAD;
}

https://github.com/Cyfrin/2023-09-ditto/blob/a93b4276420a092913f43169a353a6198d3c21b9/contracts/libraries/LibOrders.sol#L927-L947

But it is possible that the initial order was cancelled and the id reused multiple times with the previous order being close to the market price resulting in a match. This can lead to a possible exhaustion of gas if the user's order has a price far from the top of the orderbook.

Example scenario

  1. Current state of bids in orderbook:

    1. Top bid 2000

    2. Total bids 1000

    3. Bids ids are from 100 to 999. No order is cancelled and reusable.

  2. A user wants to bid at 1700 which would be the 800th order pricewise.

  3. User calls createBid passing in [799,798] for the orderHintArray.

  4. The following tx's occur in the same block before the user's createBid call in the following order.

    1. Order id 799 gets cancelled.

    2. Another user creates a limit order at 2001 which now has order id 799 since it is reused.

    3. A market/new limit ask order fills the bid.

    4. Another user creates a limit order at price 1800.

  5. In createBid when finding the hint id, the condition prevOrderType == O.Matched will pass and the hintId returned will be the HEAD.

  6. The loop starts to check for the price match from HEAD and exhausts gas before iterating over 800 bids.

Impact

Order creation can run out-of-gas on particular flow

Test Code

Add the following change in test/AskSellOrders.t.sol and run

diff --git a/test/AskSellOrders.t.sol b/test/AskSellOrders.t.sol
index 4e8a4a9..264ea32 100644
--- a/test/AskSellOrders.t.sol
+++ b/test/AskSellOrders.t.sol
@@ -8,7 +8,7 @@ import {Errors} from "contracts/libraries/Errors.sol";
import {STypes, MTypes, O} from "contracts/libraries/DataTypes.sol";
import {OBFixture} from "test/utils/OBFixture.sol";
-// import {console} from "contracts/libraries/console.sol";
+import {console} from "contracts/libraries/console.sol";
contract SellOrdersTest is OBFixture {
using U256 for uint256;
@@ -59,6 +59,49 @@ contract SellOrdersTest is OBFixture {
assertEq(asks[0].price, DEFAULT_PRICE);
}
+ function testPossibleOutOfGasInLoopDueToHighIterations() public {
+ for (uint256 i = 0; i < 1000; i++) {
+ fundLimitAskOpt(DEFAULT_PRICE, DEFAULT_AMOUNT, sender);
+ }
+
+ // a new order at the bottom of the order book
+ fundLimitAskOpt(HIGHER_PRICE, DEFAULT_AMOUNT, sender);
+ assertTrue(getAsks()[1000].price == HIGHER_PRICE);
+ assertTrue(getAsks()[1000].ercAmount == DEFAULT_AMOUNT);
+
+ // user wants to create an order at HIGHER_PRICE
+ MTypes.OrderHint[] memory orderHintArray =
+ diamond.getHintArray(asset, HIGHER_PRICE, O.LimitAsk);
+ uint16 targetOrderId = orderHintArray[0].hintId;
+ assertTrue(targetOrderId == getAsks()[1000].id);
+
+ // the target order gets cancelled
+ vm.prank(sender);
+ cancelAsk(targetOrderId);
+
+ // a person creates a limit ask which reuses the cancelled order id
+ fundLimitAskOpt(LOWER_PRICE, DEFAULT_AMOUNT, sender);
+ assertTrue(getAsks()[0].id == targetOrderId);
+
+ // a bid matches the targetId
+ fundLimitBid(LOWER_PRICE, DEFAULT_AMOUNT, receiver);
+
+ // another person creates a limit ask which reuses the matched order id
+ fundLimitAskOpt(LOWER_PRICE, DEFAULT_AMOUNT, sender);
+ assertTrue(getAsks()[0].id == targetOrderId);
+
+ // the tx of the user goes through
+ depositUsd(sender, DEFAULT_AMOUNT);
+ vm.prank(sender);
+ uint256 gasStart = gasleft();
+ diamond.createAsk(
+ asset, HIGHER_PRICE, DEFAULT_AMOUNT, Constants.LIMIT_ORDER, orderHintArray
+ );
+ uint256 gasUsed = gasStart - gasleft();
+ assertGt(gasUsed, 2_000_000);
+ console.log(gasUsed);
+ }
+
function testAddingLimitSellAskUsdGreaterThanBidUsd() public {
fundLimitBidOpt(DEFAULT_PRICE, DEFAULT_AMOUNT, receiver);
fundLimitAskOpt(DEFAULT_PRICE, DEFAULT_AMOUNT * 2, sender);

Recommendations

I think the probability of the above scenario is higher than that of multiple user's cancelling their orders. Hence moving to the next hint order as soon as the current hint order has been found to be reused could be better and will cost less gas on error.

Updates

Lead Judging Commences

0xnevi Lead Judge
almost 2 years ago
0xnevi Lead Judge almost 2 years ago
Submission Judgement Published
Validated
Assigned finding tags:

finding-525

Support

FAQs

Can't find an answer? Chat with us on Discord, Twitter or Linkedin.