Triangular Arbitrage With Crypto DEX’s: Part Two
What do graphs have to do with crypto!?
It’s been a while since my last update, I’ve had a lot going on, and I ripped out the entire arbitrage bot to make it work a lot more efficiently. This update is going to cover a lot, so I’ll probably have to make 3 parts. This part will be the nitty and gritty detail of how to make something like this work at scale.
Recap
In the last part I discussed getting the pools from the DEX, Tinyman in this case and getting the quotes of each asset into a matrix. I would then compute each permutation of the assets and follow the path using the matrix to get the quotes, i.e
Path (0, 31566704, 312769) Close to Profit!First Swap Quote: SwapQuote(swap_type='fixed-input', amount_in=ALGO('20'), amount_out=USDC('14.394919'), swap_fees=ALGO('0.06'), slippage=0.01)Second Swap Quote: SwapQuote(swap_type='fixed-input', amount_in=USDC('14.25097'), amount_out=USDt('14.260552'), swap_fees=USDC('0.042752'), slippage=0.01)Third Swap Quote: SwapQuote(swap_type='fixed-input', amount_in=USDt('14.117947'), amount_out=ALGO('19.402954'), swap_fees=USDt('0.042353'), slippage=0.01)Final Amount Of ALGO('19.208925')
The issue here is that collecting the pools was done via a paginated API, and for Tinyman, you can get 10 pools per request for 575 pools! That’s 58 requests and then I had to request again to the Algorand blockchain for the pool object, i.e 58 * 2 requests, 116. If each network request took 1 second that’s 2 minutes and I haven’t even got the quotes yet!
The matrix lookup was at worst cubic time, in Big O that’s O(n³) which wasn’t going to scale.
Asynchronous Fetching
When I first started this project, it was more a proof of concept and I didn’t ecpect to make money, but now I’ve deployed it, I needed faster lookups meaning I had to go async. If you haven’t messed around with async python, you’re missing out. This is a great video on the topic https://www.youtube.com/watch?v=2IW-ZEui4h4
Basically, I could make all of my 58 HTTP requests at the same time. I then use a multiprocessing pool to call the blockchain and retrieve the pool object.
I’ve replicated this behaviour for both AlgoFi and PactFi, two other DEX’s on Algorand. I then get the quotes using the same multiprocessing trick as I do to get the pool objects.
Graph Theory and Arbitrage
Now I could put these all into a matrix, I could convert my 2D Matrix to 3D where the third dimension would be the exchange. Instead of doing that, this seemed more like a graph problem, instead of doing a matrix lookup, I traverse a path that saves on multiple matrix lookups.
Visualising it as a graph
There is no better way to explain this than with a visualisation, so here are the AlgoFi and PactFi swaps on the graph (Tinyman is a bit too big..)
The PactFi edges are in red, and the AlgoFi edges are blue. You can see which pools are available by their connections.
I can also click on an edge and an asset. I’ll talk about the weights soon.
Arbitrage as a Graph Problem
So I’ve now got a graph of all the exchanges, assets, and quotes. I need to find arbitrage opportunities. This section will not go into detail and therefore some familiarisation with graph theory is needed.
The problem boils down to finding somewhere in the graph, where I traverse X edges, I will end up with more of my source node than when I started. For example, if I started with 1 ALGO, I need to find a path where I get greater than 1 ALGO after traversal. I need to find positive loops, these are loops where the cost of the path keeps increasing the more you traverse it.
As you can see above, each time we follow this cycle, we are increasing our starting weight, i.e out amount in. This is a positive loop.
Enter Bellman-Ford
Unfortunately, there isn’t an algorithm to detect positive loops, a positive loop would never be found for shortest path problems because you’re trying to decrease the cost or minimise the weight. Another problem is none of the shortest path algorithms multiply the weights, instead it’s addition.
Luckily, we can use some math tricks to help us. Bellman-Ford is an algorithm to find the shortest path between a source and a target, given X weight per edge. It does this by adding the weights of a path to get a total path weight. Bellman-Ford can detect negative loops, making it great for our use case. It detects negative loops by finding paths that tend towards minus infinity, while we’re looking for paths that tend to infinity. Bellman Ford does this because if a loop tends towards minus infinity, the shortest path can never be found, it will just keep traversing the loop.
So, using those maths tricks, we can change our current method for finding arbitrage (which is multiplying by each exchange rate) to using addition, which is what Bellman-Ford uses. Take the example below of an arbitrage opportunity.
If we Ln (Natural Log) each exchange rate we can change it to be ln(a) + ln(b) + ln(c)
Then, if we multiply each log by -1, we are now using negative loops to work out if there is an arbitrage opportunity.
You can see that when we traverse this cycle, we are getting closer to negative infinity, which is exactly what we’re trying to detect to signal arbitrage.
Bellman-Ford’s execution time is O(V*E) where V is vertices and E is edges. A lot faster than our matrix lookups previously.
Final Product
To bring this all together, the current flow is as follows.
The output looks a bit like this
Found a winning Cycle… (404044168, 0, 404044168) via [<Exchange.ALGOFI: 2>, <Exchange.TINYMAN: 1>] with profit 0.19299999999999962The code will then create the transactions and fire away. There is some more work here — a better way to do this would be to take out a flash loan on AlgoFi and use that to increase the initial amount of investment and get higher returns. This will be for the next part!
Join Coinmonks Telegram group and learn about crypto trading and investing
