How Mesa DEX works

Saša Milić
Nov 27, 2020 · 8 min read

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

Ring trades can best be explained with an image:

Ring trade between 3 tokens. Image from “An Exchange Protocol for the Decentralized Web

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:

  1. a price for token X, a price for token Y, a price for token Z, …
  2. 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:

Trading volume vs. trading surplus. Total trading surplus yields an exchange rate for which the area shaded in gray is maximized, whereas the total trading volume yields an exchange rate where the minimum of the solid and dotted line is maximal. In many cases, the two solutions coincide.

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?

The bonding curve for the API3 public distribution event.

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.

API3

Decentralized APIs for Web 3.0

Sign up for API3 Newsletter

By API3

Recently written articles by API3. Take a look.

By signing up, you will create a Medium account if you don’t already have one. Review our Privacy Policy for more information about our privacy practices.

Check your inbox
Medium sent you an email at to complete your subscription.

API3

Extending the capabilities of blockchain applications. API3 builds blockchain-native, decentralized APIs with DAO-governance and quantifiable security. Learn more: api3.org.

Saša Milić

Written by

Software Engineer, Data Scientist, Co-founder @ API3

API3

Extending the capabilities of blockchain applications. API3 builds blockchain-native, decentralized APIs with DAO-governance and quantifiable security. Learn more: api3.org.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store