How Mesa DEX works
EDIT: I’ve written a Part 2 (“The Mesa DEX Exploit”) to this article that addresses the exploit that occurred during the API3 public token distribution event. I also amend some things mentioned in this article and include my updated thoughts on Mesa/Gnosis Protocol.
The API3 public token distribution will take place on Mesa DEX. There have been a lot of questions about how Mesa / Gnosis Protocol works and this article is meant to address that.
TL;DR
- If you bid $X and the total demand (for tokens at price ≤ $X) is less than the supply, then it is extremely probable you are guaranteed your bid (at price $X or lower). That is, you’ll never overpay the price you set in the auction. Note: your settled trade could be your entire order size or less.
- Otherwise, the result is non-deterministic. You may or may not win your bid. Having an order size of at least the recommended minimum may increase your chances in this case. This is to make sure solvers are sufficiently incentivized (i.e. does the 0.1% fee they make off of including your order outweigh the gas costs of including your order?)
- Keep in mind: supply and demand still applies. Lower-priced buy orders outnumber higher-priced buy orders — there is more demand for cheaper tokens. So, the lower your buy bid, the more competition you will have to fill your order. Think about it like this: when you increase your bid, you are essentially paying to increase your chances of having your order filled.
Note about this blog post: the full documentation for how Gnosis Protocol works (which Mesa is built on) can be found in the whitepaper and the technical documentation. Since these resources already exist, this article will be much more high-level, intended for a more casual reader. Namely, I will avoid using mathematical notation wherever possible opting for more high-level and intuitive explanations. If you want to get into more granular detail, I would suggest just reading the aforementioned texts.
The Gnosis Protocol
Mesa is an Open Source interface for Gnosis Protocol— a decentralized exchange (DEX) maintained, owned, and hosted by the DXdao.
The main features of the Gnosis protocol are:
- ring trades (to pool and maximize liquidity)
- batched auctions (to prevent front-running)
- non-custodial accounts (for full decentralization)
Ring trades
Unlike traditional markets, where most liquidity is available in a dominant asset (e.g. USD), blockchain markets suffer from a highly fragmented liquidity space among a wide range of low liquidity assets … Having a fragmented token space with pairwise auctions leads to thin order books and high slippage.¹
Ring trades can best be explained with an image:
Normally, in most exchanges (even decentralized ones), the protocols only allow for pairwise trades. That is, you can sell token A for token B if and only if someone is willing to sell token B for token A. In that case, the trade in the image above would not be possible.
I should make note: a typical solution to the limitations of pairwise trades is to exchange one of the tokens to a reference token that is more readily traded. E.g. Uniswap uses ETH as a reference pool: “Since all [ERC20] tokens share ETH as a common pair, it is used as an intermediary asset for direct trading between any ERC20 ⇄ ERC20 pair.”² The Gnosis Protocol researchers would argue this is not ideal since it requires a decent sized liquidity on all ETH-ERC20 pairs and cannot leverage liquidity between other pairs.
Without getting into mathematical details and nuances, the image above is sufficient to show why ring trades increase liquidity: in the example above, ring trading allows trades to occur, whereas pairwise trading doesn’t.
Batched auctions
In the Gnosis Protocol, auctions don’t occur continuously (block-by-block); instead, orders are batched and auctions are executed every 5 minutes.
Here are the steps in a single batch auction:
- Users place limit sell orders on-chain at any time.
- Every 5 minutes, a batch auction runs.
- At the start of an auction, all currently open orders on the protocol are considered.
- For each auction, an open competition to submit order settlement solutions by solvers takes place. See the section “Off-chain solvers” below.
- The protocol selects the ring trade order settlement solution that maximizes trader welfare. See the “Off-chain solvers” section below that explains these terms.
- All matched orders are settled on-chain and filled.
Non-custodial accounts
This simply means that the exchange doesn’t have custody of your wallet; you are in control of your private keys.
Off-chain solvers
Off-chain solvers are a very central part of the Gnosis Protocol and cause arguably the most confusion. Each batch of orders must be settled in the best possible way. This leads to a series of questions:
- What is a valid solution to a batch auction?
- What do we mean when we say orders must be settled in the best possible way? That is, what is our objective function?
- Why can’t this be done on-chain?
Constraints for a valid solution
A solution provided by a solver specifies token prices and orders to be executed. That is, a solver returns a solution of the form:
- a price for token X, a price for token Y, a price for token Z, …
- Alice’s order for x amount of token X, Bob’s order for y amount of token Y, Carmen’s order for z amount of token Z, …
That is the format of a solution. A solution must also satisfy the following constraints.
For every order, we require:
- max sell amount is not exceeded (you don’t sell more than you specified)
- limit price is not exceeded (you are guaranteed to not purchase over the amount you specified)
- token conservation (the total amount sold of token X is equal the the total amount bought of token X)
- price coherence (e.g. if token ABC has a price of x in DEF tokens, then token DEF has a price of 1/x in ABC tokens).
- arbitrage-freeness (there are no arbitrage opportunities within in the orders in the batch)
There is also another more mathematical constraint called exchange rate normalization; I’ll just refer you to their whitepaper for the formal definition.
Importantly: a single solution is only allowed to settle up to 30 orders. This is because, after this point, it become quite difficult to come up with a good solution in the 4 minutes that the solvers are given.
Objective function: maximizing trader welfare
Now, after the solutions offered by solvers are checked for validity (by checking the above constraints), one solution must be selected as the “best”. Here, in the Gnosis Protocol, best is defined as the solution that maximizes trader welfare defined as the total trading surplus, which:
yields a fairer solution in the sense that the tokens are distributed to the traders who value them the most, i.e., to those offering the best limit prices
I’ll exclude the formal definition of total trading surplus, but I think this image from the Gnosis Protocol paper [1] illustrates it well enough:
The off-chain solvers attempt to satisfy orders that maximize the area (shown above) across all possible pairs.
Crowdsourcing NP-hardness
Now, the really interesting part!
Coming up with the best solution that satisfies the constraints above and has the maximum trading surplus is an NP-hard problem. Informally, this means that the best known algorithm for solving this kind of problem would take so long to run (we’re talking years) making the solution intractable.
However, since this problem is also NP-complete — solutions can be verified and checked in a reasonable about of time. So, quite ingeniously, the Gnosis Protocol essentially crowdsources the solution to this problem (of finding the best set of orders to execute in a given batch). A bunch of off-chain “solvers” work on coming up with the best solution each batch — using heuristical approaches— and they are rewarded for winning. (In case of a tie, the first submitted solution is awarded.)
This also answers why it’s difficult to say which orders will be included and which ones won’t. You cannot predict which orders will get filled. If you could, it wouldn’t be an NP-hard problem. An amazing by-product of this is that there are no foolproof strategies to getting your order executed on this DEX; if there were, it wouldn’t be an NP-hard problem.
Fees
The protocol levies a fee of 0.1% on the volume of an executed trade.
Why this is important: the solvers must pay gas for every included order. So, in order to profit (i.e. be sufficiently incentivized) by including a given order, solvers must make more in fees than they lose in gas prices. More formally, if the total value of an order O is $x, the solver would require 0.1% of $x to be greater than the gas fees of including O in their solution.
In short, it may not be economically viable for smaller orders to be filled by solvers on Gnosis Protocol. Hence, Mesa recommends a minimum order of 1,600 USDC. Again, this isn’t deterministic, since it depends on gas prices at the time of auction.
How this applies to a token distribution on Mesa
Now, how does this apply to a public token distribution on Mesa with a bonding curve?
This is simple: just imagine the bonding curve representing sell orders. That is, in the bonding curve above, this would mean sell orders for: 110,000 API3 tokens for $0.30, 220,000 API3 tokens for $0.37, etc.
Note: the ring trades I discussed previously don’t really apply here (I included them above for completeness, since they’re otherwise a very central feature of the Gnosis Protocol.)
Another note: there’s also a step where orders are encrypted (so users can’t see the other orders in a batch). This is rather irrelevant for the conversation here, so I’ll just refer you to Section 4.2 in their whitepaper.
Conclusion
The benefits
- full decentralization
- elimination of front-running
- relatively hard to “game” (due to non-deterministic outcomes from heuristic approaches to solving an NP-hard problem)
- prevents fragmented liquidity (although this doesn’t apply as much to a token distribution event)
The trade-offs
- There is a minimal order size to incentivize off-chain solvers to include an order (although, this doesn’t mean chances increase linearly with larger order sizes past this minimum).
- Solvers can only include max 30 orders in their solutions. This means, when batches are full, solvers tend to prefer larger orders.
- There are also some more theoretical considerations; I’ll refer you to Section 3.2 in “An Exchange Protocol for the Decentralized Web”.
Final note: the API3 public distribution event will take place November 30th, 2020 on Mesa.
