Using Convex Optimization for Optimal Routing and Arbitrage in Carbon

Carbon, routing, arbitrage and convex optimization

Carbon as a protocol is unique for two reasons: firstly it has uni-directional trading curves, ie curves that are either for buying or for selling, but in order to do both one has to use two linked curves. Secondly, and this is important here, every Carbon position is unique in the sense that traders have to route their trades to individual positions rather than having the AMM consolidate all positions into one (xy=k) or into buckets (Uniswap v3) to simplify routing.

For the Carbon system to be efficient we need to ensure that efficient routing and arbitrage mechanisms are available. The Carbon SDK does include a very efficient routing algorithm, but for efficienty reasons (it runs in the user’s browser) it only routes through the position of the desired pair, so it will miss instances where routing through other pairs would improve the price. Relatedly, we want to enable anyone to identify and profit from arbitrage opportunities both within different pairs on Carbon, and between Carbon and other exchanges. We are therefore working on — and I am describing here the first step to — a generic routing and arbitrage framework that works both within Carbon, and between Carbon and most popular other AMM models, notable constant product, constant sum, and leverage liquidity.

A big shoutout here goes to Guillermo Angeris, Tarun Chitra, Alex Evans, and Stephen Boyd for their paper “Optimal Routing for Constant Function Market Makers” as well as the associated code. We are using the convex optimization methodology they’ve outlined in their paper, and the code examples of how to use the cvxpy library were extremely helpful to get our code running quickly.

Scope of the problem addressed

In our work we want to look at two closely related problems

1. A trader wants to exchange TKN1 to TKN2 and is looking for the most efficient way of doing so; this could either be within Carbon positions only, or across the entire market
2. A trader wants to make a risk free gain by arbitraging either Carbon positions against each other, or arbitraging Carbon positions against each other and against the wider market.

It is easy to see that problem (2) is a sub-problem of problem (1) if we require that the input amount is zero TKN1, and we want to maximize the (positive) amount of TKN2 which is say ETH or USDC, or whichever other token we want to receive our arbitrage profits in.

This problem is addressed in three distinct steps

• Step 1. Identify the arbitrage opportunity, ie an unordered set of transactions that overall lead to the desired outcome
• Step 2. Construct a transaction from that arbitrage opportunity, ie a linear combination of executable trades
• Step 3. Execute it in a way that is safe with respect to MEV extraction

The focus in this article is on step 1, and before we start I want to briefly discuss steps 2 and 3 that we may address at a later stage. The issue that leads to differentiating between step 1 and step 2 is that you can only trade tokens that you actually have. In an ideal world we could do the following

1. Borrow sufficiently large amounts of all tokens involved
2. Execute all transactions, in arbitrary orders
3. Return the tokens borrowed in (1)

This may or may not be possible, but even if it is possible this will not be optimal unless the borrow happens at zero cost. Instead, the optimal transaction will go as follows

1. Take out a flash loan of [ETH or BNT] at the appropriate size
2. Sell [ETH or BNT] against [TKNa]
3. Sell [TKNa] against [TKNb]
4. …
5. Repay the flash loan

Here at every stage we ensure that we have sufficient tokens available to execute the transaction we want to execute, and at the same time we minimize the amount of upfront borrowing needed, or rather its cost.

Especially for pure arbitrage transaction — ie when we have zero inputs — it is then important to submit them through an MEV protected end point, otherwise we will be certain to be front run. Whether or not this is also necessary for bona fide trading transactions without too big an arbitrage component remains to be seen.

Levered liquidity and virtual tokens

We will discuss below how exactly to apply the methods described here to Carbon curves — here we assume that all AMMs are constant product AMMs the produce leverage using a virtual token mechanism.

The way this mechanism works as follows: the indifference curve of our AMM is a standard xy=k curve with some value k. Contrary to non-levered AMM however, the actual token holdings x1, y1 are below their theoretical values, ie we have (x1+xv) (y1+yv) = k where the quantities xv, yv correspond to the virtual token holdings of the AMM. Those virtual tokens are there for accounting purposes only, so they can not leave the AMM, meaning this levered AMM can only trade inside of a limited range of prices. This range is determined by the joint conditions x1≥0, y1≥0, and outside this range the AMM stops trading.

The chart below shows four different AMMs of this type that are arbitraged. We note that the AMMs where the state is in the interior of the range — ie x1>0, y1>0 rather than greater or equal — the dots lie in the straight line with the origin, indicating that they have the same price. For all other AMMs the state is as close as possible as they can get to this price, ie it is at the end of the range that is closes to the price.

Chart 1. Arbitraged curves.

Routing and arbitrage using convex optimization

In what follows I will treat convex optimization as a black box. For the theory of convex optimization I refer you to the paper quoted above, and the references therein. The Jupyter Notebook of the example implementation can be found in the resources section of the Carbon Simulator repo.

We are starting with a set of curves with arbitrageable states, ie contrary to the previous example the states correspond to different prices even if they are in the interior of the range, and therefore arbitrage gains can be created trading against them

Chart 2. Curves pre arbitrage

What we are looking for is a state like in Chart 1 where all those arbitrage gains have been taken.

What convex optimization — and especially the cvxpy optimization library — allows us to do is to

1. optimize a target function
2. subject to a number of constraints
3. provided (1) and (2) fulfil certain “convexity” conditions

In what follows I will ignore (3) and just posit that the problem does indeed fulfil those conditions, otherwise cvxpy will warn us, and I will focus on (1) and (2).

Angeris et al discuss the generic case of a non-linear utility, but our problem is is much simpler: we choose one specific token, and we either want to receive as much as possible of this token, or we want to put in as little as possible. Throughout the calculations we consider all changes from the point of view of the AMM, do negative numbers are outflows, and positive numbers are inflows. Optimization however happens from the point of view of the trader, and it is easy to see that in both cases the problem is a minimization problem

• Paying into the AMM, the trader prefers a smaller (positive) amount to a bigger one
• Receiving from the AMM, the traders prefers a smaller (negative, therefore bigger in absolute value) amount to a bigger one

The interesting part of course is not the target function, but the constraints. Those constraints are three-fold:

1. constraints linked to the invariant curves
2. constraints linked to the AMM leverage, and
3. constraints linked to the self-financing conditions

I will take those items in turns. The first one, about invariant curves, is essentially xy=k, except that xy=k is not a convex constraint, therefore not admissible under convex optimization. However, it is well known from linear optimization theory — and Angeris et all show it for this specific case — that the optimum value is always attained on the boundary, therefore we can use the constraint xy≥k instead

Figure 1. Code for curve constraints

Technically it is also important that we do not use the standard xy=k invariant function but the equivalent one where we apply a square root on both sides, so xy becomes a geometric mean, and k becomes kbar after taking the square root.

Secondly, the leverage constraints ensure that the AMMs can not pay out more tokens than they possess. Keeping in mind that flows are considered from the point of view of the AMM this means that the flows dx, dy must be bounded from below by a negative number, where this number corresponds to the actual token holdings of the AMM.

Figure 2. Code for leverage constraints

Finally we have our self financing constraints. Those apply to all tokens except for the token that is used in the objective function. In the arbitrage case this means that all dx,dy that correspond to a specific token must sum up to zero. In the trading case they must sum up to the (positive) amount we want to pay in or the (negative) amount that we want to take out. In any case, if we have N tokens, then we have N-1 constraints.

Figure 3. Code for self-financing constraints

The code for the objective function is essentially the same as for the self-financing constraints, except that it is wrapped in a cp.Minimize rather than being a constraint equation

Figure 4. Code for the objective function

Once we have set up our objective function and constraints, all we have to do is to feed this data into the solver

Figure 5. Code for running the solver

The solver then spits out not only the optimized value, but more importantly the vectors dx, dy that determine the trades that lead to this optimal value. The chart below shows the (arbitrageable) starting positions of one pair (stars) and where the states end up after optimization (circles).

Chart 3. Curves pre and post arbitrage

Summary and outlook

I have shown above how to optimally route through an arbitrary number of levered virtual token positions, and I have asserted that any Carbon or Uniswap state can be described by those (this asserting is discussed in the Appendix just below). This algorithm is blazingly fast — for hundreds of positions it has no meaningful delay, and even for 1,000s or 10,000s it is very quick.

The analysis above omitted two things: fees and gas. Fees are in principle easily included, provided they are percentage fees, as all they do is shift the price. The only problem is that the direction of the shift depends on the direction of the trade, so the process needs run twice: in the first run we determine in which direction a specific curve trades [only for non-Carbon curves of course; Carbon curves only ever trade in one direction and have no fees] and before the second run we shift the prices by the fee amount in accordance with the trading direction in obtained in the first run.

Gas is somewhat more complex as with a constant per-AMM-used fee we leave the realm of convex optimization. We will write more about this in due course, and Angeris et al has a brief discussion on this topic, but essentially the trick is to identify the “dust” positions whose inclusion costs more in gas than it brings in term of slippage reduction. This may be an iterative process, even though heuristics and some smart construction of the algorithm should allow for restricting the calculation to 2–3 iterations.

APPENDIX: The virtual token view of Carbon and Uniswap curves

Carbon curves

In our whitepaper, in equations 2.13–2.18, we give the virtual token curve that is associated with a Carbon curve. They key formula in this context is 2.16 which gives the virtual pool constant kappa as

Equation A1. Virtual pool constant kappa

Note that the numerator can also be written as x0 y0 where x0,y0 are the the special coordinates of the pivot point of the Carbon curve that are for example defined in formulas A.22, A.23

Equation A2. Pool parameter y0

Here yint is the y-intercept, ie the curve capacity aka the amount of tokens available for sale on the curve if the curve is full, and Gamma is the leverage factor also appearing in the equation for kappa. The equation for x0 is the same, except that it uses the x-intercept which corresponds to the amount of tokens the curve receives when all tokens on y are sold. Therefore, the effective curve price P0=y0/x0.

Our CarbonOrderUI class — the class the describes a single Carbon order — has a property as_cpc that returns a ConstantProduceCurve object that can be used in the optimization algorithm.

Uniswap v3 curves

Uniswap v3 curves are composed of curvelets where each curvelet corresponds to a single bucket between two prices, and whose width depends on the tick size. At the moment, Uniswap v3 are most easily represented by the corresponding CarbonOrderUI object.