The math and the papers

The bot's central problem is small to state. Given a cycle of pools, how much of the starting token should we put in so that the profit is as large as it can be? This page collects the reading that led to the answer and the derivation. It follows the answer from my own first attempt, which was in the right ballpark, to the answer in the cyclic arbitrage paper (Cyclic Arbitrage in Decentralized Exchanges, listed below), which made it exact, and then from Uniswap V2 to V3.

Reading list

• Cyclic Arbitrage in Decentralized Exchanges

  Y. Wang, Y. Chen, H. Wu et al. · 2021 (arXiv 2105.02784, v3 Jan 2022)

  Studied closely. It is the source of the idea that a chain of pools can be collapsed into one virtual pool with a closed-form optimal trade. The bot's `Path` class cites it.

• Uniswap v3 Core

  H. Adams, N. Zinsmeister, M. Salem, R. Keefer, D. Robinson · 2021

  With the v3-core contracts, the source for the off-chain V3 swap reimplementation.

• Liquidity Math in Uniswap V3

  A. Elsts · 2021

  Companion reference for V3 liquidity and tick math.

• An Analysis of Uniswap Markets

  G. Angeris, H.-T. Kao, R. Chiang, C. Noyes, T. Chitra · 2019 (arXiv 1911.03380)

  Background on constant-product market behavior.

Reference code and documentation:

• Uniswap v2-core
• Uniswap v3-core
• dYdX Solo Margin (flash loans on Ethereum)
• DODO flash loans (BNB Chain and Polygon)
• Flashbots documentation (bundles and relays)

The two-pool case: my first answer

Before I found the cyclic arbitrage paper, I worked the two-pool problem out on paper myself. The idea is simple. Two pools quote the same pair at different prices, so I buy the token where it is priced low and sell it into the other pool, where it is priced high. Each trade moves the price against me, so the profit peaks at the trade size where the two pools quote the same price again.

Setting it up

Call the token I start with, and get back at the end, $A$. Call the token in the middle $B$. Two pools trade this pair:

• The first pool holds $i_1$ of $A$ and $o_1$ of $B$.
• The second pool holds $i_2$ of $B$ and $o_2$ of $A$.

The names come from my notes. The letter $i$ is what goes into a pool when I trade, and $o$ is what comes out. I will carry one example through every step: the first pool holds 250 $A$ and 1,000 $B$, and the second holds 500 $B$ and 2,000 $A$.

Step 1: the price of $B$. The price of one $B$ in a pool is the amount of $A$ in the pool divided by the amount of $B$. In the first pool that is $i_1 / o_1 = 250 / 1{,}000 = 0.25$. In the second pool it is $o_2 / i_2 = 2{,}000 / 500 = 4$. So $B$ is priced low in the first pool and high in the second. I buy it in the first pool and sell it in the second.

Step 2: the rule a pool follows. When I trade, a pool's two reserves change, but the two reserves multiplied together stay the same. Ignoring the fee for now, call that number $k$:

Step 3: buy $x$ of $B$ from the first pool. The pool now has $o_1 - x$ of $B$. Its two reserves must still multiply to $k_1$, so:

Divide both sides by $(o_1 - x)$ to get the amount of $A$ the pool holds afterwards:

In the example, buying $x = 500$ leaves 500 $B$ in the pool, so it holds $250{,}000 / 500 = 500$ $A$. It started with 250, so I paid in 250.

Step 4: sell the same $x$ into the second pool. That pool now has $i_2 + x$ of $B$, and by the same reasoning it holds $k_2 / (i_2 + x)$ of $A$. In the example it has 1,000 $B$ and $1{,}000{,}000 / 1{,}000 = 1{,}000$ $A$. It started with 2,000, so I took out 1,000. I paid in 250 and got back 1,000.

Step 5: the new prices. The price is $A$ divided by $B$ again. Dividing a fraction by something puts that something in the bottom a second time, so:

In the example both come out to 1 (500 divided by 500, and 1,000 divided by 1,000).

Step 6: the best trade is where the two prices meet. While $B$ is still priced lower in the first pool, buying a little more still makes money. If it has become priced lower in the second pool, I bought too much. So the best $x$ makes the two prices equal:

Solving for x

Step 7: take the square root of both sides. The square root of a fraction is the square root of the top over the square root of the bottom, and the square root of something squared is the something itself. So:

Step 8: multiply across. Multiply both sides by $(o_1 - x)$ and by $(i_2 + x)$:

Step 9: open the brackets.

Step 10: gather the $x$ terms on the left. Add $\sqrt{k_2}\,x$ to both sides and subtract $\sqrt{k_1}\,i_2$ from both sides:

Step 11: pull out the common $x$.

Step 12: divide both sides by the bracket.

Check it with the example. The square roots are $\sqrt{k_1} = 500$ and $\sqrt{k_2} = 1{,}000$, so $x = (1{,}000 \cdot 1{,}000 - 500 \cdot 500) / (500 + 1{,}000) = 750{,}000 / 1{,}500 = 500$. That is the trade from step 3.

What I pay in

Step 13: what I pay in. From step 3, what I pay in is the change in the first pool's $A$ reserve:

To get this in terms of the reserves alone, I need to replace $x$. I do it in three parts: simplify $o_1 - x$, use it to simplify the fraction, then subtract $i_1$.

Step 14: simplify $o_1 - x$. From step 12, $x$ is a fraction. Call its top $N$ and its bottom $D$:

So I want $o_1 - N/D$. You cannot subtract a fraction from a whole number directly. It works like $3 - 1/2$: write the 3 as $6/2$ first, and then $6/2 - 1/2 = 5/2$.

14a. Give $o_1$ the same bottom. Multiplying the top and bottom by $D$ changes nothing, because $D / D = 1$:

14b. Subtract. The bottoms match now, so only the tops combine:

14c. Write out the top. First, $o_1 D = o_1\sqrt{k_1} + o_1\sqrt{k_2}$. Then subtract all of $N$. The minus sign applies to both parts of $N$, so both signs flip:

14d. Cancel. $o_1\sqrt{k_2}$ and $-\sqrt{k_2}\,o_1$ are the same amount with opposite signs, so they cancel and leave:

14e. Factor. Both parts contain $\sqrt{k_1}$, so pull it out:

Check it with the example, where $\sqrt{k_1} = 500$, $\sqrt{k_2} = 1{,}000$ and $D = 1{,}500$. The bottom is 1,500. The top is $500 \cdot (1{,}000 + 500) = 750{,}000$. The fraction is $750{,}000 / 1{,}500 = 500$, which matches $o_1 - x = 1{,}000 - 500$.

Step 15: use it in the fraction. Now divide $k_1$ by that result. Dividing by a fraction means multiplying by its flip:

15a. Cancel one $\sqrt{k_1}$. Write $k_1 = \sqrt{k_1} \cdot \sqrt{k_1}$. One of them cancels with the $\sqrt{k_1}$ on the bottom:

15b. Open the bracket. $\sqrt{k_1} \cdot \sqrt{k_1} = k_1$ and $\sqrt{k_1} \cdot \sqrt{k_2} = \sqrt{k_1 k_2}$:

In the example this is $(250{,}000 + 500{,}000) / 1{,}500 = 500$, the $A$ the pool holds afterwards, as in step 3.

Step 16: subtract $i_1$. This is another fraction minus a whole number. Give $i_1$ the bottom $(o_1 + i_2)$:

Step 17: cancel and finish. Since $k_1 = i_1 o_1$, the terms $k_1$ and $-i_1 o_1$ cancel. Also $\sqrt{k_1 k_2} = \sqrt{i_1 o_1 i_2 o_2}$. That leaves:

In the example that is $(500{,}000 - 125{,}000) / 1{,}500 = 250$, the 250 I paid in at step 3.

What my notes had

The steps above are the tidy version, worked out afterwards. My scratch notes were messier. I set up the equal-price condition with the fee in it, boxed the equation, and pencilled the optimal amount in below it. With $r_1$ and $r_2$ the fee factors (0.997) on the input of each pool, the pencilled line reads:

It is close, but not exact. For the example it gives 251.25, and the true best input is 250.25. The profit differs only in the fourth decimal place, 747.7432 against 747.7462, so the trade was nearly as good. With a fee, the profit peaks where the marginal prices, fee included, balance, and that is not quite where the reserve ratios are equal.

What the first bot did

The notes were not what ran. The function that turned them into code is calculateAmountToBuy in zzz-the-josh-bot, and it was a rougher implementation. It did not take the square root. It multiplied the equal-price condition out instead, which gives a quadratic:

The function then worked out both of its roots and kept whichever was in range:

This is where the edge cases came from. Squaring adds a second, false root, the one where the two prices are equal and opposite. So the code had to handle every combination: both roots negative, both in range, both zero, both too large. It also divides by $k_2 - k_1$, so two pools with the same constant broke it, and the code stopped there with a TODO. The square-root form from the steps above has one root and no such division. On 20,000 random pairs of pools it matches one of the code's two roots every time, and it still works when $k_1 = k_2$.

The fee was not in this formula at all. The router's getAmountIn added it afterwards, when the trade was priced. So the first bot was in the right ballpark, and no more than that. The cyclic arbitrage paper is what made it exact.

What the cyclic arbitrage paper added: a virtual pool

The paper closes both gaps: the fee goes inside the formula, and the answer is exact for any number of pools, not only two.

Wang et al. set the problem up with their own notation, which I use from here. $a_{i,j}$ is the reserve of token $A_i$ in the pool that pairs it with $A_j$. The fee factors are $r_1$ on a pool's input and $r_2$ on its output, so on Uniswap V2 $r_1 = 0.997$ and $r_2 = 1$. A swap of $\delta_a$ of $A$ for $\delta_b$ of $B$ in a pool with reserves $a$ and $b$ obeys $ab = (a + \delta_a r_1)(b - \delta_b / r_2)$, which solves to:

Their insight is that a whole chain of pools can be replaced by one virtual pool. For a cycle $A_1 \to A_2 \to \dots \to A_n \to A_1$, fold the first $n - 1$ pools into a virtual pool with reserves $a'_{1,n}$ and $a'_{n,1}$. This is their Algorithm 1. Start with $a'_{1,n} = a_{1,2}$ and $a'_{n,1} = a_{2,1}$, then for each next pool $i = 2, \dots, n - 1$:

The closing pool, between $A_n$ and $A_1$, then merges with the virtual pool into a single pool with reserves:

The whole cycle now behaves like one trade through a pool with reserves $a$ and $a'$. Its output is $r_1 r_2\, a'\, \delta / (a + r_1 \delta)$, so the profit is that minus $\delta$. It starts at zero, climbs, peaks and falls, and at the peak its slope is zero, which gives the optimal input:

A profit exists only when the slope at $\delta = 0$ is positive, which is the same as the product of the exchange rates around the cycle, net of fees, being greater than one. That is the test isValueExtractable runs before any real work.

For two pools, $n = 2$ and the virtual pool is just the first pool. My symbols map onto the cyclic arbitrage paper's as $i_1 = a'_{1,2}$, $o_1 = a'_{2,1}$, $i_2 = a_{2,1}$ and $o_2 = a_{1,2}$, and the paper's answer becomes:

Without a fee this is identical to what I found on my own. With the fee it has the same denominator, and one extra factor of $r_1 r_2$ on the square root. That factor is the part my equal-price shortcut missed.

The example from my notes, a first pool of 250 and 1,000 and a second pool of 500 and 2,000, comes out as follows. With no fee, $a$ is 83.33 and $a'$ is 1,333.33, so the best input is $\sqrt{111{,}111} - 83.33 = 250$, for a profit of 750. With the 0.3% fee, $a$ is 83.50 and $a'$ is 1,331.997, and the best input moves to 250.25, for a profit of 747.75. A brute-force search over every input size lands on the same numbers.

For a path of more pools, fold in one pool at a time with the two update rules above. A three-pool example agrees with brute force too, to the hundredth.

How the code followed

The three bots show the same arc as the notes, from a close approximation to the exact answer.

The Java implementation of this step is Path.calculateOptimalTradingVolume in jam-bot, and the method that decides whether a path is worth evaluating at all is isValueExtractable in the same class.

Uniswap V3: concentrated liquidity

V3 changes the curve. Liquidity is provided inside price ranges, so within one range a pool behaves like a V2 pool with larger virtual reserves, and the moment the price leaves the range the behavior changes. The optimizer therefore works in steps: solve as if the current range lasts forever, check whether the answer crosses the next initialized tick, and if it does, swap exactly up to that tick, update the pool's state, and solve again. Repeat until the answer stays inside a range.

The off-chain code has to match the contract exactly, because the contract is the final judge of every trade. The V3 swap math was therefore ported to integer arithmetic in Java, about 1,100 lines written in five commits between May 17th and June 3rd, 2023, the day the V3 executor went on chain. Pseudo-code for the swap loop (the SwapState and StepComputations structures) was transcribed by hand before any of it was written as code.

What we did not get to

The multi-pool version of the problem: instead of one path at a time, look at every pool of a token pair at once and find the single price at which all of them are in balance. It is a convex optimization problem, and the scratch notes call it "a graphable line". We worked out the idea and never built it.

These notes sketch it as a graph. Price levels run up a vertical axis, swaps from the bottom are stacked against swaps from the top, and the trade that joins the two lines is the answer.

The research that formalises it is where we would start if we picked the project up again:

• G. Angeris, A. Agrawal, A. Evans, T. Chitra and S. Boyd, Constant Function Market Makers: Multi-Asset Trades via Convex Optimization (2021). Shows that choosing a trade across many assets and pools is a convex optimization problem.
• G. Angeris, T. Chitra, A. Evans and S. Boyd, Optimal Routing for Constant Function Market Makers (2022). Routes an order across a network of pools, with finding an arbitrage as a special case.