[Feature] Rollover Orders

[fleupold]

In order to lower transaction costs for market makers, we need a way to post an order that will be automatically rolled over into subsequent batches (unless filled).

There a bunch of ways to achieve this. The goal of this issue is to capture the different solutions and pros & cons.

@josojo @bh2smith @twalth3r to subscribe.

[fleupold]

Rollover Counter

One possible solution was to include a "rollover counter" on each order, that - if non zero - indicates how many times the order should be carried over unless completely matched.

struct Order {
  uint16 account;
  uint8 buyToken;
  uint8 sellToken;
  uint32 buyAmount;
  uint32 sellAmount;
  **uint24 rolloverCount;**
}

The auction settlement data would then also include a new "starting hash" which would be the hash of all non-fully matched orders whose rollover counter was > 0 (with order.rolloverCount=-1 in the new hash). At the moment each batch starts with a rolling hash of 0x0. The correct computation of this new starting hash could be challenged in the same way as every other aspect of the solution.

function applyAuction(
        uint slot,
        bytes32 _currStateRoot,
        bytes32 _newStateRoot,
        bytes32 _currOrderHash,
        bytes memory pricesAndVolumes,
        **bytes32 _newStartingHash**
        **uint16 _newStartingOrderCount**
)

We would collect the order fee for all potential batches (assuming maximum rollover) at the time of placement and could potentially "reimburse" excess fee in case the order is matched early.

Discussion

One drawback of this approach is that it "locks" the order collection process until the full solution is posted. More specifically, the smart contract cannot know how many slots are available in the next batch before the full solution is posted (as potentially all orders could be rolled over). One possible heuristic would be to use the upper bound (assuming all orders with rollover count > 0, will roll over) until a solution is proposed and then adjust the number of vacant spots later.

Another concern is that an attacker could potentially completely fill the order book with nonsense orders and large rollover counts, thus clogging the exchange.

On the other hand one can argue that an appropriate fee model should prevent this from happening.

However, more complex fee models (such as an adaptive function that increases with relation to remaining slots) are hard to implement in this model. At the time of order placement it is hard to foresee how crowded future batches will be and thus it will be hard to price the order in advance. To implement such mechanism, we would need to deduct fees as part of the auction settlement step (and kill an order if the fee can no longer be paid). That would increase the number of transactions that have to be performed as part of the settlement step and thus likely affect scalability.

[fleupold]

Reserved Accounts

Another possible solution was to "reserve" part of each batch for "professional accounts". Each account would pay rent and in turn be guaranteed a fixed amount of slots (e.g. 10) in each batch.

Inside the smart contract we would store a separate hash for each reserved batch:

struct PendingBatch {
  uint16 nonReservedOrderCount;      // Number of orders (limited to 500)
  bytes32 nonReservedOrderHash;      // Rolling shaHash of non reserved orders
  **bytes32[50] reservedOrderHashes; // Each hash is sha256(o_1, ..., o_10) **
  ...
}

The allocation of which account occupies which reserved slot could be stored in another BiMap and be tied to a rent paid per hour, day or similar. Reserved account holders could also submit orders of other accounts as part of their reserved slots (against a fee and certain trust assumptions).

At any in the order collection period could the owner of a reserved account override the hash (and thus cancel or update orders) by posting a new batch of 10 orders:

function placeSellOrderBatch(bytes memory orderData) {
  // TODO check that order length and signatures
  uint16 accountId = publicKeyToReservedAccountMap(msg.sender);
  pendingBatches.last.reservedOrderHashes[accountId] = sha256(orderData);
  emit SellOrderBatch(auctionIndex, accountId, orderData);
}

Such a transaction would cost ~60k gas.

Each solution would include the "combined order hash" of all non reserved orders, appended by all reserved orders. The correct computation of this combined hash could be challenged like any other aspect of the solution.

When a new PendingBatch is created we could copy the previous reservedOrderHashes and thus rollover the orders of the "professional accounts".

If a trader doesn't want to carry over an order (e.g. because it was filled), the reserved account holder would have to update their reservedOrderHashes before the order collection period ends for this batch (3 minutes).

Discussion

By splitting the batch into a reserved and non-reserved portion and only allowing the reserved portion to roll over orders, we lower the risk of clogging the exchange. Moreover the allocation of reserved slots is another way to generate fees. The fee mechanism for reserved accounts could be easily made adaptive and depend on demand.

However, automatically rolling over orders (even when they are matched) might be inconvenient for reserved account holders. They would be required to observe solutions and update their standing orders in case it was matched and they are no longer willing to trade. On the other hand, we'd expect these accounts to be taken by professional traders (e.g. market makers) which will observe the system and update their orders frequently. Moreover, we could consider adding "recalculation logic" for these orders to the settlement logic, which would only rollover an order if it wasn't fulfilled. Yet, doing this for 50 slots might significantly increase the size of the solution data and significantly increase complexity of the challenge game. At least initially, we should try to avoid that logic.

Another drawback is the increased gas cost (~250k) when creating a new PendingBatch. This is because we are now storing 50 more hashes on chain (one per reserved account). So far the first trader to place an order in a new batch would also create it (as it wasn't that expensive). However, with this much gas we would likely have to create the new batch as part of the solution submission (and thus cover it with part of the solution reward)

[josojo]

Very good write up!

Yeah, the conclusion I am drawing from your write up is that no matter which way we are going, the complexity will increase dramatically :( Let's keep our eyes open for other solutions as well