search

gnosis / dex-research

Collection of research papers written within Gnosis
90 stars 31 forks source link

Auction Resolution Timing #27

Open bh2smith opened 5 years ago

bh2smith commented 5 years ago

Summary of Auction Phases

Our batch auction proposal consists of three distinct phases

  1. Order collection: A fixed period of time when limit orders are being accepted.
  2. Solution Bidding: A fixed period of time when solvers may claim that they have a solution whose objective value is x. Later in this article we will briefly consider what might happen if it is allowed to bid on solutions with at least an objective value of x.
  3. Auction Settlement/Solution Revealing: A period of time for which the most optimal solution is to be provided in order to update the account account state as a result of auction execution.

At this time, it is fairly clear how order collection and solution bidding will work with the exception of mentioning that solution bids will consist of a single uintXX representing the claimed objective value. This issue will primarily discuss options for the second two phases.

General Setting

In the most generic setting, solution bids would passed (via transaction) to the contract in the form of a tuple (uint auctionId, uint128 objectiveValue, bytes32 stateHash) and be recorded/stored on the EVM in a MaxHeap - ordered by (objectiveValue, blockNumber, transactionIndex) in order for the contract to have O(1) access to the largest elements. The auction settlement period could then be specified as having fixed-finite time interval T where the i-th half interval is specially reserved to the i-th "best" bid. More concretely, that is,

The top element of the Heap (i.e. best bid) has from time 0 to T/2 to submit their full solution. If the expected bidder provides their solution within their dedicated time frame, then the state root is updated and the auction is considered settled. However, If no solution is provided, then the second best has from time T/2 to 3T/4 = T/2 + T/4 to submit their solution. This process could continue indefinitely in this fashion, but (if bonding prices are not high enough) could result in a spammed collection of false bids with no possibility for solution.

Rather than imposing unnecessarily high bonding on solution bids, we consider and adapted version of the above mechanism by opening up the last p percent of the interval T on a first-come-first-serve basis. This means that (depending on the choice of p) only the top N = floor(-log_2 p) bidders will have a reserved time interval for which their solution may be submitted. Such an approach could be interesting from a game-theoretic perspective when attempting to incentive competition amongst N solvers. Furthermore, with this approach, the contract would only ever have to keep track (i.e. remember/store) the best N solution bids. In the event that N is small (say < 10) one would not necessarily even need to use such an elaborate data-structure (the Heap) and it would suffices to use a simple insertion algorithm on a fixed-length array.

Proposed Implementation (N = 1)

Considering generic setting when N = 1 which, essentially, says that only the absolute best bidder will have exactly half of the auction settlement period to submit their full solution. If the solution is provided by the winning bidder during their reserved submission slot ([0, T/2]), then the state transition is applied and the auction is considered settled. However, if this is not the case, then anyone can submit a proposed new state root (along with objective value and a full solution) which the contract will set as its "tentative", or temporary, new state root. Such submissions will be collected over the remaining [T/2, T] time and submissions with higher objective value than the current tentative would take priority (i.e. overwrite the tentative state hash).

Notice that in the best (expected average) case where the winning bidder successfully provides their solution, the settlement would resolve in at most T/2 time. In the worst case, this would be exactly T since the free-for-all doesn't consider the auction settled until the clock has run out. In the best/average case, assuming a normally distributed response time would then be T/4.

One may wish to consider a mechanism encouraging the winning bidder to provide their solution rather than falling into the open-acceptance period and we must be careful to strongly discourage invalid transition proposals in either half of this phase.

Bids claiming objective value of at least x

The current structure of a solution proposition bid contains the essential values (auctionId, objectiveValue, stateHash) where stateHash is essentially a commitment to an already existing solution. Suppose, for a moment, that we remove the stateHash commitment and allow for bids claiming they "have" a solution with at least a certain objective value.

In this scenario (due to the nature of linear programming) one would be able to determine upper bounds for the objective value and make speculations (based on prior executions) about how close they could get to the upper bound within the given time-frame. By submitting such a hypothetical proposal, experienced solvers could get themselves ahead in the priority queue and potentially make themselves more likely to reap the benefits of having "won" the bid. Of course, this comes with the bidder's risk of over-speculating, being incapable of providing the acclaimed solution and resulting in a loss of bond. Furthermore, such an approach could incentivize experienced solvers to force each other to outbid themselves with hopes of having longer solving-time and expecting that their solution would win during the open-acceptance period.

It is unclear (to the author) at this moment, whether such a proposal would incur any "Protocol Risk", but would likely increase the average case (expected) settlement time to T as opposed the weak proposition of at most T/2.

josojo commented 5 years ago

Nice, write up.

I am strongly in keeping things simple and just implement the protocol for N=1. I think that the risks and uncertainties being attached to a proposal like "Bids claiming the objective value of at least x" are not worth the benefits. I would prefer that no solution provider is a gambler!

We might want to make the reward for providing a solution depended on the time within 0..T/2, as it is desirable that the protocol keeps on moving quickly.

bh2smith commented 5 years ago

I would prefer that no solution provider is a gambler!

Nice way to put it!