GPv2 Objective Criterion

In a previous thread we outlined a path to decentralized solution submission for Gnosis Protocol v2 based on a competition between permissionless parties (so called solvers).

One of the key questions for this competition is what is a desirable metric that solvers should aim to maximize for. This thread is meant to spark discussion around this topic.

GPv2’s main value proposition is to allow traders to capture their trade utility/surplus (which is the difference between their personal valuation of tokens as expressed in the limit price and the fair market price of these tokens) instead of giving it away as MEV to miners or arbitrageurs.

As such, simply maximizing the sum of all individual utility is an intuitive candidate for an objective criterion. However, as we have seen in GPv1, simply maximizing the sum of all surplus is prone to manipulation where bad actors can “claim” a very high utility for wash trading fake tokens only they control in order to outbid real utility of other benign traders.

Apart from maximizing utility, envy freeness is a desirable criterion for solutions. In an envy-free settlement, given the prices reported in the solution, each trader is “happy” with the outcome of the auction (in the context of an exchange economy envy free settlements lead to a Walrasian Equilibrium).

Concretely, for every order in the system, if the reported exchange rate between the affected tokens is better (from the trader’s perspective) than their limit price, the order is fully executed. If the reported price is worse than their limit price, the order is not executed at all. If the limit price is equal to the token price, the trader is indifferent about trading and so any partial fillment is acceptable. In a two dimensional orderbook (like the one used in Gnosis Auction) this is commonly referred to as “matching supply and demand”. Gnosis Protocol works on multi-dimensional order books, as such finding equilibrium prices is significantly more difficult.

In GPv1, we referred to the envy as “disregarded utility”, which was non-zero if a trader would have been happy to trade more given the reported prices, but their order was not traded fully. We discounted the sum of disregarded utility of all “touched” (traded) orders in a solution - since these are the only orders the smart contract saw - from the objective value. However, this ignored disregarded utility from orders that were not traded (potentially ignored on purpose by a malicious solver). For more background information on GPv1’s objective criterion you can watch our talk at EthCC3

With GPv2 we are moving more logic off-chain. Off-chain we can compute disregarded utility over all orders in the current orderbook and could enforce envy-freeness on the solution. While this could not be ensured on chain, the protocol can ask DAO members to verify that solutions fulfill whatever criterion we agree on off-chain and vote to penalize solvers that misbehave (cf. phase 2 of road to decentralization).

Enforcing disregarded utility to be 0 has another challenge: As block space is limited, so is the maximum number of trades that can be matched in a single settlement.

Even though GPv2 will be able to handle significantly more trades per batch than GPv1 (in the order of 100 vs 30) it is still possible to create pathological batches in which the “perfect” solution would require more than 100 trades.

We see potentially two options to address this:

  1. Before solving, split batches into small enough sub batches (according to some sorting rule) so that each batch in itself will at most contain 100 trades. Then require disregarded utility to be 0 and maximize total utility
  2. Instead of enforcing disregarded utility to be 0, we optimize for an approximate equilibrium where the solution for which the price vector would have to be relaxed by the smallest ε in order to make each individual trader envy-free wins. For a large enough ε, there will always be some solution in which less than 100 orders are traded.

In 2) the competition could either be to minimize ε or have some form of weighting between a small ε and a large total utility.

Another thing to consider is the execution cost of a settlement (in terms of gas). While a slightly better price may be achieved by integrating e.g. many different AMMs in the solution, doing so might incur a difference in transaction cost that is much larger than the gained surplus for the user. We are therefore wondering if total surplus should be discounted by the total execution cost of the settlement?

Lastly, the utility of each individual trade is computed either in units of sell token or buy token of the trade, leading to a vector of utilities (one dimension per token). In order to derive a single value which solvers can compare against one another, the utility vector has to be normalized into a common base currency (e.g. the native token).
Since each solution might assign fundamentally different prices to the traded tokens, normalization should not be based on the “new” price vector, but instead on some “last known price”. Initially we suggest to use the most liquid base liquidity (as defined by the DAO and implemented by the orderbook’s price estimation API - for now this is the Balancer/uniswap price at the block the competition is kicked off).

2 Likes

Hi guys, finally having time to join the conversation.

Bringing my background from finance, I can share these thoughts:

Enforcing 0 disregarded utility is key. If you can do that you can compare solver solutions with a lot more objectivity.

So when it comes to the 2 options proposed, I’m strongly in the camp of the splitting batches. While this is not a perfect solution, I think Gnosis as a whole can never fully run on the main chain, and all of those issues are temporary until you can move the entire dex into a rollup, be it optimistic or (eventually) zk. Those things should end the number of trades restriction and in my opinion should be a long term focus.

Anyway, since those things are still into the future (hopefully not too long future), we got to focus on what’s at hand so I vote for batch splitting.

When it comes gas and computing prices according to gas, I think they absolutely have to be included in the effective price. If a trader uses uniswap to trade 0.1 ETH for dai (imagine nominal price of ETH is 2500 dai) and he gets 200 dai after swap fees, chain fees etc, his effective sell price was 2000. I don’t care what nominal price says. He Had 0.1 ETH and now he has 200 DAI. That’s it. That’s the price, that’s what matters. Whether the money went to LPs on the dex, arbitrageurs, main chain fees or whatever does not matter. That’s what needs to be maximized. How much of one asset he gets for the other after all is said and done. Saying that he sold at 2500 but only got 200 because of fees, while technically correct, misses the entire point of the trade.

So yes, we absolutely need to take chain fees into account when considering trades. We need to understand them not as some external factor to be ignored, but as a price changing event, just like slippage.

The narrative that GP protocol must sell is not “better prices than uniswap”, but “more bang for your buck”. It sounds like the same but isn’t, because the first ignore a bunch of fees and we should not.

2 Likes

Do you have suggestions how batches could be split? If we just order by “first seen timestamp” there might be ordering consensus issues in a decentralized environment and fixed batch sizes would allow adversaries to spam with orders in order to isolate “juicy” orders into a single batch.

That makes a lot of sense. Maybe we need to rethink our separation of “sellAmount” and “feeAmount” (the fee the solver can take from an order is capped by the latter).

Thanks @CryptoOrca for the suggestions!

I absolutely agree that this would make a lot of sense! One obstacle that we are facing is the fact that orders can be specified to be fill-or-kill, meaning that they must either be fully matched, or remain untouched. Now, imagine there are two such orders:

  • sell 2 ETH for DAI for at least 3300 DAI per ETH
  • buy 1 ETH for DAI for at most 3500 DAI per ETH

If partial matching was allowed, both orders can trade 1 ETH for 3300 DAI, thereby matching 50% of the first order and generating no disregarded utility. However, when each order is only allowed to be fully matched, no price admits a trade, thus every price incurs disregarded utility for at least one of the traders.

In our current approach, we treat this issue by only enforcing zero disregarded utility for selected orders, but we would be very happy to hear other thoughts about it!

Hi Tom, I was thinking about the problems regarding @fleupold points (batch splitting), but your questions makes me wonder why do we have fill or kill orders? They indeed screw over 0 disregard utility, or at least their own utility has to be treated differently since they explicitly ask to miss on better prices under certain conditions. They also have the problem that if midway a settlement an order is canceled (or uniswap move prices), fill or kill orders might make the solution completely invalid instead of only partially fillable. This is a huuuuuuuuge problem when batching splitting since once you get one batch through you can never revert it.

Unless you have pretty good reasons to allow fill or kill as an option, I would get rid of it. But if you do have good reasons, it’s utility has to be always 0 (and it’s impact on other users utility) unless there’s enough trades on their side for them to take part. In practice would be like treating their order price as completely out of range (buying for 0/selling for infinity) until enough volume accrues on their side to fill their order, at which point their utility can be computed normally. In your example, there’s no trade because for the amounts available for trading he is not selling at 3300, he is selling at infinity. It’s a little bit like his order only shows up on the calculation once the volume reaches his threshold. I think that’s actually the best way of thinking of it. Fill or kill are not orders that exist now in the order book, they are orders that are triggered, kind of like stops. But instead of prices, their trigger is available volume under a certain price range (in your example 2 ETH above 3300 DAI).

But then we still have the issue of forcing them to be batched first (joining on Felix point about multiple batches here) since they can never be left half filled.

Now regarding batch ordering and disregarded utility, the more I think about it the more I’m concerned about order cancelling. What prevents me today from running a bot that signs offline orders on cowswap and when I see a transaction in the mempool calling the contract settlement I move the tokens from my account using higher gas causing the solution to not be executable anymore (the order I signed becomes no longer valid because the tokens are not there anymore) and forcing the contract to revert to the previous state and therefore never finishing an auction? Because all attack vectors I see on batch splitting are some sort of variation of that.

Ok building on our conversations on discord, if we assume that order cancelling is a not a big deal (it happens infrequently mid batches and mostly by accident), then batch ordering is not a super big deal. If all batches execute, the order don’t matter.

To reduce disregarded utility once a batch fails, I think we should ask solvers to order them by utility, but ultimately let him create the batches at his will. Other considerations like gas fees are in play when deciding on particular order matching. Then the contract execute the batches themselves by ordering them by utility, so in a scenario where a batch fails the overall solution loses as little utility as possible.

For example, imagine each batch contains at maximum one trade and the solved price is 1 ETH = 3500 DAI.

The orders for this solutions are:

Trader T1: Buys 1 ETH for 4000
Trader T2: Buys 0.5 ETH for 3600
Trader T3 : Buys 0.5 ETH for 3500

Trader T1’: Sells 1.5 ETH for 3500
Trader T2’: Sells 0.5 ETH for 3000

One possible batching created by the solver is:

T1 matches T1’ for 1 ETH (batch 1)

T3 matches T1’ for 0.5 ETH (batch 2)

T2 matches T2’ for 0.5 ETH (batch 3)

In this case, the batches would be ordered as

batch 1 -> batch 3 -> batch 2
because batch 3 has more utility than batch 2.

But the Solver could have proposed this set of batches instead:

T1 matches T2’ for 0.5 ETH
T1 matches T1’ for 0.5 ETH
T2 matches T1’ for 0.5 ETH
T3 matches T1’ for 0.5 ETH

This batching uses 4 batches instead of 3, and would be ordered by batch 1 -> batch 2 -> batch 3 -> batch 4.

I think it should be up to the solver to choose how the batching is done (once again, it impact gas costs of the solution, like above).

Then back to the goal of the forum post, the objective criterion (assuming we are enforcing 0 disregarded utility in the solution), is first volume traded (no need to explain), then number of batches (the smaller the number the higher the chance we are actually enforcing 0 disregarded utility) then finally distance to last price (when multiple prices are acceptable the one that changes prices the least).

Need to some extra thinking on the attack vectors of the batch splitting beyond the obvious we discussed already (since here batching number is taking precedence over price distance to last, it might be opening a new can of worms)

In order to achieve comparability between different solutions we need to split orders into batches before we know their matching (so that a constraint like “no disregarded utility” can be required by all solvers). If solvers can split orders into batches as they like, they could isolate orders they don’t like (e.g. the ones which would incur disregarded utility in their solution) and not solve them.

I was thinking that when enforcing 0 disregarded utility, we assume all batches will be able to execute. As if it were a single batch.

This way we can enforce that the solution has 0 disregarded utility and with the information at hand it should be executable, but we can’t enforce that the solution will actually in practice execute properly (we can never enforce that because of the order cancellation issue).

That’s what I was thinking, so we can compare solutions under the assumption that they will execute.

But yes, this opens an attack vector where a solver match an order against an account he controls and cancels the match before that particular batch that contains that pair executes. That’s the targeted attack, I agree. That’s why order cancelling is the issue.