MVP on-chain multi-token batch auctions

We have been working on various scaling solutions for batch auctions. To test the concept of batch auctions we want to start with a minimal viable product with that purely allows multi-token batch auctions. As a recap: a batch auction is different from a “normal order book exchange” aka “continuous double auction” in that orders are not executed continuously but only periodically (in batches) at a single clearing price per batch. In a multi-token batch auctions trades between n tokens can happen and it is possible to settle “ring-trades” (A->B, B->C and C-A) atomically.

Here is a rough specification:
Batches
1) Batches run for 5 minutes. The timestep of a block defines implicitly the current batch number
2) During the current batch (n), the previous batch (n-1) can be solved. The n-1 is finalized once n+1 started.

Deposit and Withdrawl
2) Any user can deposit tokens any time. A deposit needs to only increase the balance for the current batch and not for the previous one that is currently in "solution submission period". This is implemented with a "pending amount" that is only valid from block "current". If there is a write access to balance in a batch n+1 "pending amount" is summed into the regular balance.
3) A withdrawal can be requested anytime. An amount and a "withdrawal batch" needs to be specified. Withdrawal batch number needs to be >= current. If the amount is accessed any time at or after "withdrawal batch" the withdrawal amount is deducted from the amount.
3a) A withdrawal request can be directly canceled/ reduced as long it is in the future or current block. Otherwise, it needs to create a new deposit (amount still pending)
4) A withdrawal settlement can be made if n is > "withdrawal batch" (this can be done by any account)



Orders
5) Users can submit orders any time and specify from when till when they are valid. (can not be from previous batches)
6) Orders can be canceled by setting valid till to "n-1"

Solution Submission
7) A solution can be submitted any time for batch n-1
8) A solution can first change prices of tokens and after that settle trades at those prices.
9) If a solution is already submitted the previous solution will be rolled back if the new solution generates higher trade volume == overall fees

Executing a solution:
10) potentially rollback of the previous solution
11) set all prices of tokens touched denominated in the reference/fee token
For each order
12) check that prices (after fees) are honored. Execute order at clearing prices - fee
13) check that never a token is used that was not in the list of tokens that got a new price
13b) check that every token that was used also got a new price
14) update balances, reduce "volume left" of orders, store those deltas to enable rollback
15) track for each token the total "delta" (sum of sold and bought)
After order execution
16) Check that after all trades are executed deltas for all tokens = 0 and for fee token = claimed total fee
17) credit half the fee to solution submitter, burn half

Some implicit consequences of this specification.
a) No “islands”. All settled trades need to have a trading path to the fee token. This is because fees are taken in each token and the only way to create a valid solution is to trade all those surplusses into the fee token. If “island” would be allowed this auction could not serve as a price oracle because prices could be set arbitrarily by the solver.

b) Solution submissions are attackable by frontrunners and most so by miners. To reduce the “miner extractable value” and to create adoption incentives for the GNO community half of the fees are burned.

c) The number of trades that can be touched is implicitly limited by the block gas limit. We expect this number to be around 20-35.

d) Given a 0.1% total fee, a solver would get 0.05% of the fee. Given marginal gas costs of ~150k per trade and assuming a gas price of 10 GWEI this would mean a 0.0015ETH gas costs. To cover this for the solver the trade size needs to be at least 3 ETH.

e) A consequence of d) is that larger trades will be given preference. There might be pooling contracts where different users aggregate common trades (e.g market order to convert DAI to ETH) to create larger orders and increase overall efficiency.

Code here:

This exchange will be limited primarily in the number of orders that can be executed per/time.

One way to scale this could be to bundle orders from different users into the same order on the exchange.
E.g. specifically for market orders (where the limit price is not relevant) it would make sense to bundle all orders into one.

Implementation suggesting:
A contract for each relevant market order type (sell token; buy token) could exist that has an unlimited open order (unlimited in volume and time). People can deposit (sell token) into this contract and the contract would forward the sell token into the exchange. (deposit request)

STORAGE:
AUCTIONS[auctionidex] -> totalSellVolume; totalBuyVolume
SELLS[User] -> (auctionidex1, sell volume1), (auctionidex2, sell volume2)
BALANCES[User] -> amount_of_buytoken
pending_auction_index, pending_auction_index1
total_buy_amout

sell (amount)
   //if the last sell is cleared
   diff = buy token balance in exchange - total_buy_amout
   if (diff > 0):
       AUCTIONS[pending_auction_index] set totalBuyVolume to DIFF
       total_buy_amout += diff
   // settle previous sells of user
   // set new sell order

withdrawl ()
   // first checks as in sell the pending sells and tries to proceed them
   // deduct user amount, total amount and withdrawl from the exchange to the user.

There are a range of token sets that can be minted any time with a specific token and vice versa the set can be redeemed for the specific/collateral token. 2 examples are a) conditional tokens and b) options. In a) you input a collateral token and get different outcome token, in b) you deposit the underlying and you get an option and a “anti-option”.

To name a concrete example: There could be a prediction market denominated in DAI on wether or not Brexit happens at a specific point in time. 2 users on the dfusion would like to make a trade than can be matched. E.g. user 1 assumes the likelihood is >40% for Brexit and user 2 assumes the likelihood is >60% for not-Brexit. In this scenario user one would buy brexit-outcome-tokens for 0.4 DAI and user 2 would need to buy not-Brexit for 0.6 DAI. The issue is that those tokens do not exist on the exchange. One option would be that part of the settlement the solver would make use of the fact that on an external contract it can convert 1 DAI to 1 brexit and 1 no-brexit. However - an issue with that is that this would require all those contracts to be registered with the dfusion. It would also weaken the security of the dfusion since one malicious contract of this type could do significant damage to the system.

A solution can be a specific trader that acts as an - on demand converter.
The trader would be a smart contract that has a unlimited supply of brexit and no-brexit and is willing to sell at any time brexit and no-brexit for one dai. Vice versa they would always buy a DAI for a “complete set”. Outside of defusion users can use the outcome tokens against this contract to get the proper outcome tokens. Those can be generated with the DAI as needed.
In this usecase of conditional token the redemption might not even be needed. The contract might just be programmed to add a buy order of the winning outcome (buy the winning outcome for DAI).

The 1 requirement for dfusion would be to allow “basket trades”. Namely order that have multiple tokens on buy and or sell side.

This approach would also mean that trades against this account (which are essentially just conversions) would still be required to pay a fee.

It turns out that the optimization criteria is not easy to define.

In our first attempted we have been optimizing for overall trading volume. This however makes the solver create unnecessary long rings. Consider a situation with different stable coins (all worth a $) and several market makers willing to exchange all of them against each other with a small spread. If a trader comes in and places a market order/ set a low limit order to exchange one stable coin vs. another - the solver would create a solution that creates an as long as possible ring to maximize trading volume. Arguably those additional trades are unnecessary.

Here is a document describing the expected scenario and the expected behaviour in more detail including alternative optimization metrics that might lead to the expected behaviour. https://docs.google.com/document/d/1-Dk-tVMmCpvkyZgQlcze2JSOZHYpF18b3NRlNUdscvA/edit