Originally Published on March 6, 2017

With the advent of a standard for defining cryptocurrencies in Ethereum comes the possibility of building a decentralized currency exchange into the blockchain. This exchange could be used as both an incorruptible liquidity provider for token markets and a source of token pricing information. My colleagues at Gnosis and I teamed up to build this exchange.

Making an Automated Market Maker

Given the nature of an Ethereum contract, we had to come up with an automated market maker. These market makers are often useful in settings like prediction markets, where their pricing of options reflects the market’s belief in a statement prior to its resolution. For example, suppose that Alice and Bob are both running for election in Chandlerton. An automated market maker could make a prediction market for the outcome of the election, pricing the shares for A and B accordingly so that they reflect the market’s evaluation of the election, and so that when the election in C resolves, the market maker, if not profitable, at worst sustains a limited loss from payouts for A and B.

However, unlike a prediction market, which can provide a virtually unlimited amount of option shares that have a standardized price (e.g. from $0.01-$1.00 corresponding to belief in outcome odds), an exchange only has a finite supply of tokens to trade, all of which may be priced arbitrarily against each other. Just consider the exchange rate of BTC and USD, which has ballooned from 1 USD/BTC to 1000 USD/BTC in its history. These conditions mean that the market maker for a decentralized exchange has to behave differently from a market maker for prediction markets.

An Example

Let’s say our exchange market maker’s name is Dexter.

Dexter has 100 Pennycoin (PNY) and 100 Icecreamcoin (ICM). We will call these assets Dexter’s liquidity pool. Dexter needs this to provide liquidity to the PNY-ICM exchange he’s handling.

Alice wants to buy some ICM from Dexter with her PNY. Dexter quotes a price for ICM in terms of PNY. Since he wants to keep some PNY and ICM no matter what, the more ICM Alice is buying, the more PNY Dexter will want to charge per ICM so Alice doesn’t empty Dexter’s liquidity pool of ICM. Because of this, the price of ICM should go towards infinity as the ICM in the liquidity pool goes to zero.

Here is a potential price function of ICM, where q is the quantity of a particular asset held in Dexter’s liquidity pool:

This function displays the desired divergence property, but it isn’t immediately obvious how to actually price ICM with this function. Furthermore, a problem remains: how can Dexter be assured that he can continue trading PNY and ICM indefinitely with this method?

Invariants, and Where To Find Them

What Dexter wants is an invariant: some abstract quantity which permits him to trade and doesn’t change as Dexter performs the trades. This quantity should depend on the parameters which can change: namely Dexter’s liquidity pool. Also, it may be good if this invariant quantity displays special behaviors for when the quantity of ICM or PNY goes to zero.

Here’s a simple one that could work:

Let’s give that a shot! Suppose Dexter still has 100 ICM and 100 PNY. That means our invariant is

Alice says “Yo Dexter, I got 50 PNY. How much ICM will you give me for that?”

Dexter thinks to himself, if p is the amount of PNY Alice is giving me for ICM, then I can figure out i, the amount of ICM I should give her while keeping the invariant the same with this equation:

Some algebra later…

And Dexter tells Alice “I’ll give you 33 ICM for 50 PNY.”

What Does Alice Want?

Alice has some ICM and PNY. One might suppose she assigns a value to these things. Maybe she likes having ICM twice as much as she likes having PNY. We can model this situation: let’s give each PNY Alice is holding one Alicepoint and each ICM she is holding two Alicepoints. Go ask Alice: her modus operandi is to maximize these Alicepoints.

Let’s say Dexter has 100 ICM and 100 PNY in his liquidity pool again. Alice wants to maximize those Alicepoints, and she’s got a whole bunch of PNY. Alice wants to know p, the amount of PNY she should trade with Dexter for ICM so that her net Alicepoint score is most increased. We see that the change in Alicepoints A due to the trade can be expressed as

Let’s plug in the values from the liquidity pool and plot this thing:

We can see here that the gain in Alice points achieves a max around 40 PNY somewhere. Applying a little calculus and solving

helps us find exactly how much PNY she should trade:

and how much ICM she should expect from Dexter:

So Alice trades 41 PNY for 29 ICM with Dexter and absconds with her acquisition. Where does this leave Dexter?

Well, he now has 141 PNY and 71 ICM. Thanks to some favorable rounding, the invariant has actually increased by 11 for Dexter, but if there wasn’t any rounding, Dexter would be at 141.421 PNY and 70.710 ICM… that is, he seems to have twice as many PNY as he does ICM now. This is no coincidence, and a little algebra will show that

In fact, for the preceding argument, even the factor 2 can be generalized to any number greater than zero. That is to say, when Alice seeks to maximize her value trading with Dexter, Dexter learns how Alice values the assets being traded.

Another Perspective

As mentioned earlier, Dexter must have a liquidity pool which satisfies

Another way to say this is that if Dexter has q_P PNY tokens in his liquidity pool, he must have q_I ICM tokens, where the following relationship is satisfied:

If we take q_P to be a parameter, then the above doubles as a cost function for ICM in terms of PNY, that is, i, the amount of ICM Dexter parts with when given p PNY such that

satisfies

As we take p → 0, we get a familiar looking marginal price function

In Alice’s case, after her trade with Dexter, this marginal price function reports that the price of ICM is 2 PNY, expressing exactly Alice’s 2x preference for ICM. If Alice bought any more ICM, she would have raised the marginal price, causing her to pay more than 2 PNY per unit ICM, and thus causing a net loss in Alicepoints. This is another reason why Dexter ended up with a liquidity pool reflecting Alice’s preferences.

Generalizations

The invariant perspective yields a couple of natural generalizations for this market maker. One such generalization extends the market maker to work for n tokens simultaneously. Simply change the invariant to the following:

This is a straightforward multivariate version of the two token situation. One may parameterize this class of market maker further by introducing powers:

However, these generalizations introduce considerable complexity to the model and thus present difficulties for implementation in an on-chain contract.

Technical Details in Giving Robots Money

We at Gnosis are building a decentralized exchange as an Ethereum contract. It accepts any ERC20 token pair and will provide the aforementioned exchange service between these tokens. Anybody can make an exchange which automatically trades between an arbitrary pair of tokens if they provide it with a liquidity pool of these tokens.

We chose not to generalize the model to multiple-token exchanges:

1. While theoretically the calculations will work, there is a finite amount of memory that may be practically manipulated. Bignum arithmetic is both complex and potentially resource hungry.

2. The simpler this is, the easier it will be to conduct a comprehensive security audit of the code, and the more likely it will be secure.

3. Bots will be incentivized to conduct arbitrage between market pairs, causing prices to converge to the multiple token scenario anyway.

4. Allowing arbitrary tokens to enter existing exchanges will incentivize hackers to create tokens solely for the purpose of draining the exchange’s liquidity pool.

This decentralized exchange can also serve as a price oracle native to the Ethereum blockchain. In fact, recall that the price of one token in terms of another may be expressed as a ratio of the quantities in the liquidity pool!

Using this data raw, however, can leave contracts prone to manipulation. Somebody with enough resources can make a large trade on the exchange, thus changing the liquidity pools to reflect some price, doing something with those contracts (but now with the manipulated price), and trading back on the exchange.

To solve this problem, we use a low-resource kernel smoother to smooth out the price data. The smoother simply moves the price to the new value over the course of a day. In the time in between, the price manipulator would risk losing considerable assets from exchange participants moving the price point back towards the true market value.

Fin

Keep your eyes peeled for the launch of our decentralized exchange, and thank you for reading!