# Intro to DEX Arbitrage: Algorithms & Math - Aleksei Babenkov | Cerera

- Channel: [ETH Belgrade Community](https://streameth.org/eth-belgrade-community)
- Date: 2024-10-07
- Duration: 28:05
- Topics: People & Blogs
- Watch: https://streameth.org/watch/yt-42E0PFKTF3Y
- YouTube: https://www.youtube.com/watch?v=42E0PFKTF3Y

## Transcript

um doberan good day everyone um my name is Alexia I'm happy to be here and uh today I'm going to share some insights on topic I'm passionate about which is decentralized decentralized finance math and algorithms but before let me tell you a bit about myself so I've been working in machine learning data science for over eight years in several Russian companies so in Maxima telom I led a team of Max machine learning researchers sorry uh however my biggest professional growth happened at Avita which is by the way the largest classified as website in the world there I trained some machine learning models to make search better and recently I made a big career change I left aita to focus fully on on quantitative research quantitative sorry uh and together with a team of like-minded people we create high frequency trading robots and explore Advanced algo trading today I'm going to give you some building blocks for the System trading system for dexus and this system is going either to make your money or lose it all unfortunately I cannot provide you any guarantees but let's start so have you ever wondered how prices on different exchanges match not so long ago while being while being a good engineer I was not so knowledgeable in finance and so I used to think that there is some magical process that synchronizes prices across exchanges however the reality is a bit different and it's called Arbitrage well this is a very basic natureal law of Economics when something is cheaper on one exchange and the more expensive on the other arbitror buys on the cheaper exchange and sells on the more expensive Market essentially pushing the prices closer together and leveling them off so this is the beauty of Economics it balances itself and arbitra play The crucial role in many financial markets because they provide liquidity and enhance Market stability in general so um the design of many online and offline exchanges intentionally includes their presence to fulfill this control um and now let's discuss how we can apply this concept to decentralized exchanges but before we need to discuss some key challenge with traditional centralized exchange Arbitrage strategies and this is non atomicity you see when you are performing an Arbitrage trade on a classical centralized exchange you need to perform several separate steps and and um this is a risk because you may face uh a problem of partial execution where you can buy on one exchange but cannot sell on another because like the price has changed or the order book is empty or you face some unexpected Network delay and this happens all the time on centralized exchanges and this is why classical Arbitrage is risky and this is why we need be to be creative and we need better strategies uh now let's revisit what a de is and um I will focus specifically on Unis sw2 and some of you might Wonder Isn't Unis sw2 like outdated and less effective and while it's true it's also true that there are a lots of forks of Unis swap2 still being used right now and what's more important for us that Unis swap V2 is very simple and we can like grasp General concept on Unis P2 and then I will like explain you how we can extrapolate this knowledge to more complex dexes so basically unlike centralized exchanges Unis swap2 uses automated Market maker concept and uh um liquidity pool model and liquidity pool is just a collection of funds provided by the users and users uh known as liquidity providers those liquidity providers uh deposit some pair of assets into the pool and get liquidity tokens in return and at any time they can redeem this redeem the tokens for the pair of underly assets plus some portion of trading fees um Unis V2 uses the constant product formula which is XY equal K the product of quantities of the assets inside the pool equals con constant which is like um this formula ensures that the balance is present in the pool so when a user wants to swap one asset for another they interact with a smart contract which calculates the exchange rate based on the reserves and then swap adjusts these reserves and swap like process ensures that this constant product formula holds so in practice Dex can be seen as the collection of such pools which is just smart contracts or to put it simply just classes and solidity language for me is the same and uh now and now we can State the main advantage of Dex Arbitrage which is atomicity so we can illustrate this concept on this like solidity code but I will explain you um we can see that we have here an Arbitrage contract with Arbitrage function defined and what's happening here that we before doing any transaction we check our balance before then we perform some swaps like we swap usdt for we and we for usdt back and after we check our balance again and in the end in the last line if our balance after the transaction is not greater than the balance before the whole transaction reverts and we pay the gas only the gas meaning that this means that our risk is limited to only gas fees which is small predictable amount compared to the trade size and the profit and this is what makes Dex Arbitrage like low risky strategy compared to classical Arbitrage okay and now let us the like review the general architecture of the system that exploits this price differences and so our system interacts with a global P2P blockchain Network and Nar system itself is a trading server which runs two separate processes one of them is a blockchain node and the other is a price discrepancy detector we can also call it the strategy so uh the blockchain node keeps our system updated um with the latest state of the global blockchain Network it pushes latest State changes and transaction data while the price discrepancy detector is like a lightweight program is written it's written in some fast language like C++ or rust we prefer rust by the way and uh for each and every one piece of data piece of information the this program must calculate optimal Arbitrage transactions and send them back and it must do it so fast that these transactions will be included in the next block um so the key challenge here is that we we perform heavy calculations there this is the CPU bound program we need to calculate the price like a million times per second and this means that um we cannot do this on chain in solidity we must move this uh calculations to our application site and this means that we need to port to copy the price calculation logic from deess to our application and this is a big challenge because like for UNIS swap V2 this is a very simple logic four lines of code maybe uh and for UNIS swap V3 and similar it's like about 1,000 lines of code and our team has spent few months just porting this logic to our application site um okay and now let's discuss the core component of Unis 2 I call it pricing function this is just my interpretation but this is like get amount out function which calculates the amount of output tokens depending on the input tokens you can see the formula in the top of the slide and um this function has one important property which is nonlinearity meaning that as you increase input amount you get your average price becomes worse uh and this means that you get less output for each additional unit of input and this is very important because this is done on purpose this Behavior emulates some uh price impact behavior that you can see on the centralized exchanges like on centralized ex changes when you place a large order it moves the market price here we don't have orders but we need to like copy this Behavior somehow if this is like the emulation we can see this as emulation of price impact um okay and now let's discuss how we can check if we can profit from two Unis two payers how we can determine this let's assume we have two Unis swapy two payers with given reserves and and we want to check if we can profit from like swap from usdt to West and from west to usdt back on two different payers and in order to do this we need to construct a profit function which is just a difference between amount of tokens we get in the end and the amount of tokens we have before the transaction and plus the gas fees but let's assume this is a small constant compared to the amount and the profit Let's ignore it for now now so this is just the difference between the tokens we have after and before just two nested get amount TOS first for the first Swap and the second for the second Swap and um we need to notice here that this expression it depends on a so in order to prove that we have a profitable Arbitrage opportunity we need to find a such that profit of a is greater than zero this difference must be greater than zero and in order I want I suggest to approach this problem by looking at the graphs so here in the left part of the slide we have the plot for get amount out function applied twice so this is the dependence between the input amount of tokens and the output amount of tokens after two swaps and the right uh plot is the graph for profit function Which derived from the left plot by subtracting the initial amount and the initial amount is this red line so we can see that this is somehow similar to 45 degree clockwise rotation and the maximal profit the point of maximal profit here shown as a Red Cross and let's pause for a second and think what we have discovered as we increase our input amount our profit grows up until some point and then it starts to decrease and this basically means that at this this exact point the prices became equal so as we increase our input amount we push the prices closer together then at some point they're equal and they they they become to diverge and this means that we're losing money and we um also we can calculate this using formulas you don't need to understand them actually just knowing about their existence would be helpful but we can like take our profit function which is this and find its derivative and solve solve the equation der if equals to zero and find this formula which is this amount and the point of maximal profit um so are we done here like we can apply this formula and the problem is solved not quite let me explain why but before this let us introduce the notion of a path a path is just a sequence of swaps we've seen already an example of such path before on the previous slides here there there is another example like um we swap from usdt to BTC and then from BTC to usdt back this is two swap path and so we want our path to consist of uh various Dex protocols like we want to buy on Unis P2 and sell on Unis P3 because statistically Arbitrage opportunities appear more often on such paths but the bad news is that the price calculation Logic for this dexes is much more complex and it cannot be expressed in the simple formulas and the good news is we can walk around this and because we can assume some fundamental economic property for each Dex which is the price impact meaning that the shape of the curve of the pricing function we seen for UNIS P2 will be similar for these dexes which means that our reasoning about the existence of single maximum is still valid which means that we can solve this problem numerically and the algorithm that's going to solve this problem is called Golden section search you can ignore ignore the code for now because we have a beautiful animation that illustrates his principles but like golden section search at GSS is similar to binary search you might be familiar with it iteratively discards a part of search space narrowing the range which contains the true point and the great thing about it it converges very fast logarithmically and uh what also great about it is that you can set the Precision you want where you want to stop and in practice we use a Precision of few dollars here and uh it converges at maximum at 20 to 30 iterations so now we have finally we have a un IAL formal Criterion to check if we can profit from a given Arbitrage path but do you remember that we said let's assume we have a path how do we get those paths in the first place and let's remember that the classical definition of Arbitrage is the cycle on the graph of tokens and payers here is the example so uh this is just the loop and and the any Arbitrage pass is just the sequence of those tokens and arrows payers which starts and ends in the same node and in order to calculate these paths we can like apply plenty of algorithms but we used the most primitive simple DFS which is like uh checking iteratively uh all the neighbors recursively and this is the example of how it can be implemented but as always you don't need to dive into it uh so what we need to understand here is that this is a very heavy computation exponential in complexity but the good news is the that graph structure uh don't change frequently we can compute it rarely like once per day or once per hour will be enough and finally we've arrived at the point where we can bundle together all the components into the generalized in the single Arbitrage algorithm which is the following first before running the main Loop we need to compute the paths uh using DFS and keep them updated and then the main Loop starts which is we need to First receive a price update or state update like the new piece of data then we need to iterate through all paths and calculate the optimal amounts for them using formula if it's Unis swap P2 or GSS if it's not Unis swap P2 then we select one or more optimal paths and send the transactions by calling ourr contract and then we repeat the process but let's now discuss why all of this won't work at least it won't work in um as is vanilla setup and that's the main reason is uh you are not the only Arbitrage on the network and all other Market participants they know the same things they know how to calculate paths they know how to calculate amounts and some of them even have some unique infrastructural advantages like they have partnership with validators and if you will fight with them for the single opportunity for the same opportunity with high probability they will win and you will lose um so our Edge lies in being just smarter we need to tune our framework somehow and to be creative and that's where the real art begins but unfortunately this art falls out of the scope of the introductory talk but I will like give you some ideas and research directions in the next slide in the next slides let's first discuss performance considerations because our search space is enormous if we will try to uh calculate all the paths for the large blockchain like binance smart chain you will get around like 10 billions of paths and this is very large number we need to reduce it somehow so the basic techniques are you must limit cycle lengths you must limit algorithm runtime and we can be more smart for example we can calculate the upper Bound for our profit function that does not depend on a and using this we can like discard unpromising paths very quickly uh we can apply some manual rules that will discard some paths uh using historical statistics for example liquidity statistics and uh activity recent activity statistics and uh since I am a machine learning expert I would naturally suggest to use machine learning here we can apply some high performance models and try to predict something like the existence of Arbitrage opportunity given such update and uh we can rank prioritize these paths using the output of this model um and so far we haven't discussed what happens when multiple Traders submit their transactions that going to exploit one opportunity and um basically obviously one of them wins and the rest are getting reverted and they pay the gas but what determines the winner and this depends on the network you're trading on and uh I would categorize classify these networks into three main types first of them is uh networks like TS evm where you cannot set the gas price or gas tips so the speed is the key and this is just the rest whoever first submits the transaction wins on the other hand we have more traditional networks that operate under more traditional rules where something that I call gas auction takes place so you just say you just um set the bid and you like pay for your priority so the highest bid wins and among this networks we have uh subset which operates under slightly different rules because of the existence of flash Bots and MF Builders uh which allow which allow the revers to be free so you don't need to pay for your revers which means that that uh this shifts the risk reward ratio for such networks even more and um this leads to very aggressive bidding and because of this we prefer not to trade on such networks but as you can see most of the N networks require you to place a bid in order to participate in gas auction and here's some typical strategies we can use for this uh we can start from the most simple one which is just play a constant or place a multiple of Base gas price or place a percentage of your expected profit or what which is more smart you can place a multiple of your competitor's bit because you need to out beit them you can like uh monitor their bits and place the bits that depend on their bits um and since I'm a machine learning expert I would naturally advise to use machine learning here we can try to predict uh winning bits using machine learning models or we can what which is more smart we can try to predict the probability of winning and we can then adjust our bits using this probability and we can select the more promising paths to um using this probability uh and the last thing I want to State here is that we don't even need our own money to perform Dex Arbitrage because we have flesh loans and the flesh loan is just an ability to borrow large amount of crypto provided that you will repay this loan into the same inside the same transaction and um this means that we can perform high volume trades even um without having large amount of capital in our account and this is what makes Dex Arbitrage not only low risk strategy but like lower Capital requirement strategy and speaking of our finial results after some careful consideration we decided not to disclose most of them but you can see that even on such small moderate liquidity Network we've managed to convert $5 Into 5K do which is 1,000x multiplier and this is basically it that's all I wanted to say in conclusion I want to say that like de Arbitrage is hard but it's possible for for individuals not large companies to do and I'm open to any questions you might [Music] [Applause] have do we have questions yes okay you yeah thanks for talk I have a quick one so uh do you consider some specific uh uh types of liquidity pools for example you Arbitrage only on high liquidity pools like V fuse DC stable pools or it's not something you consider you just uh to someone else something else to to to to pick the pool you will Arbitrage well um we take this into account when uh just by solving this optimization problems like because we select the more promising paths using some rules but as I I said um we cannot like brute force all this space and we need to uh restrict this like reduce this search space somehow and this where we can apply uh we take we can take liquidity into account because when we we need to Traverse more promising paths uh at first and here we can rank them using like liquidity statistics or because like high liquid pools uh the Arbitrage opportunity disappear more often on high liquid liquid pools highly liquid pools this is the answer yes yeah you mentioned um BSC is a chain with uh lots lots of pools and capital and in your uh table where you showed your results there was no BC are you recommending to just avoid no I mentioned uh that we prefer not to trade on sorry on such networks because uh because of aggressive beaing it's our choice thank you anyone else yeah you um how important is uh gas optimization in the Arbitrage contract well it's important um on some networks it's even more important to optimize not the gas but the C data size because it's called cost more than the gas and I know the examples of contracts where guys like uh in instead of passing just the arguments to the function they passed just row you 256 just bytes and then inside the contract they sliced it back into this variables so this is important and in some cases it's even more important it's important to optimize the amount of gas you pay in case of revert obviously thank you and we have time for one more yep uh yeah I'm just very curious about like the the probability function right um like do you um do you just take like normal distribution or do you have like any kind of proprietary method you can just take any gradient boosting library and train machine learning model to predict this probability well that's what I suggest here at least um what's cool about this that you can optimize your gas bids using the same model because your model you can like um pass the gas bid you want to set as the feature to this model and you can then optimize the gas just by maximizing this probability so uh to be short I suggest not to model this in closed form using formulas but I suggest to model this probability as a machine learning model oh so it's more of like a heris right than like like like a mathematical Foundation all this right in some sense all machine learning models is heris yes are heuristics great thank you so much anyone else uh I guess that's it thank you very much once again