Originally published in Deeplink Labs Publication

The core concepts and motivation behind Eta X are explored in great detail in our previous article:

However, we will briefly summarize Eta X V1 for readers who are unfamiliar with our progress.

The growth of decentralized finance has led to an increase in the number of DEXs, which provide a trustless solution for trading crypto assets. Eta X stands out by offering a platform that is resilient to manipulation and provides the best possible trade routes as calculated by reverse engineering publicly available smart contracts and their respective AMM conservation functions, without engaging in any biased practices.

Eta X is a decentralized exchange (DEX) aggregator and smart order routing (SOR) tool developed by Deeplink that can help traders find the most profitable trade routes by considering factors such as price impact, liquidity, and gas fees. Eta X V1 uses a modified Djisktra algorithm to traverse and validate paths from the token being sold to the token being purchased.

To evaluate the profitability of each route, Eta X V1 uses reverse-engineered conservation functions from each exchange to calculate a minimum return and price impact percentage. The algorithm returns a list of recommended routes for a user in descending order of highest returns. While early versions of Eta X are simply analytics tools to inform traders, the ultimate goal of Eta X is to facilitate the execution of profitable trade opportunities via wallet and smart contract integration.

Eta X V1 proved to be an effective proof-of-concept, as such, we have since been expanding in several areas such as the inclusion of several new DEXs, optimizing data collection, order splitting, and mass query APIs.

One of the most noticeable improvements from Eta X V1.0 to V1.2 was the introduction of liquidity pool data caching. Early proof-of-concept iterations of Eta X were loaded down by ad-hoc GQL queries to subgraphs hosted by The Graph, this meant that a user’s query would trigger several queries on Eta X’s backend, essentially double-handling data retrieval. While this was fine for early testing purposes, Eta X is growing, and thus its data collection and caching functionality must mature along with it.

Previous Data Collection Method

Caching is a technique that involves storing frequently accessed data in a temporary storage location, such as in memory or on disk, to reduce the time and resources required to retrieve that data from its original source. In many cases, caching is significantly faster than ad hoc retrieval, which involves accessing data directly from its original source every time it is needed.

In the context of Eta X, caching can provide significant benefits by reducing the time and resources required to retrieve pool data from decentralized exchanges (DEXs). Since Eta X relies on up-to-date pool data to perform smart order routing, the speed at which this data can be accessed and processed is critical to both the application’s performance and user experience.

Eta X V2 and V3 now keep a running cache of all liquidity pools contained within each supported DEX in the backend. This way each time a user queries Eta X, the backend must only retrieve the relevant data via filtering it out of this pre-existing cache, rather than fetching it from third-party sources on the fly. This addition has removed Eta X’s greatest bottleneck, and has reduced data retrieval time down from a few seconds to less than one second, while still retaining comparable data granularity and currentness.

This is achieved by creating a hash map of all liquidity pools from supported DEXs to their respective relevant datapoints. Pool data is updated continuously and asynchronously by querying the relevant subgraphs for each DEX. The pools are refreshed periodically at a rate that is close to the limit of The Graph’s rate limiters, but still within the limits to ensure that the updates are successful. While this does mean that pools are no longer at the time of an end user’s request, the time difference between cache refreshes is negligible for the vast majority of use-cases. However, rest assured that we are working on even faster methods involving circumventing The Graph entirely, and leveraging direct on-chain queries and datasets provided by L3 Atom.

New Data Collection Method

In line with the aforementioned data filtering process that is triggered upon retrieving relevant liquidity pool data from the cache, we have also introduced the ability to filter the DEXs on which a user would like to identify trade routes across. The specific reasons why a user would like to limit their trades to a given exchange may vary from protocol loyalty to ease of integration, for instance, while one DEX may have fantastic liquidity, it may not be so easily integrated with your DApp as another. In the frontend GUI, a user can simply tick or untick the DEXs they wish to route through; when querying the API, a user can simply pass a list of strings including the DEXs they wish to include, an empty list indicates all DEXs shall be queried.

This filtering process is achieved by retrieving relevant liquidity pools by token ID from the greater hash map of liquidity pools. Pools are gathered in order of their most relevant metric for trade optimality, such as reserves or liquidity, and are merged into a smaller list of pools to be used in SOR for that particular user’s query. A DEX and its respective liquidity pools are included or excluded in this filtering process depending on whether or that DEX is selected in the user’s query.

You can try Eta X NonML V2 yourself at the following link:
https://etax.deeplink.network

The source code for Eta X can be found here:
https://github.com/Deeplink-Network/EtaX-V1

By: Jack Lodge

Originally published in Deeplink Labs Publication

The core concepts and motivation behind Eta X are explored in great detail in our previous article:

However, we will briefly summarize Eta X V1 for readers who are unfamiliar with our progress.

The growth of decentralized finance has led to an increase in the number of DEXs, which provide a trustless solution for trading crypto assets. Eta X stands out by offering a platform that is resilient to manipulation and provides the best possible trade routes as calculated by reverse engineering publicly available smart contracts and their respective AMM conservation functions, without engaging in any biased practices.

Eta X is a decentralized exchange (DEX) aggregator and smart order routing (SOR) tool developed by Deeplink that can help traders find the most profitable trade routes by considering factors such as price impact, liquidity, and gas fees. Eta X V1 uses a modified Djisktra algorithm to traverse and validate paths from the token being sold to the token being purchased.

To evaluate the profitability of each route, Eta X V1 uses reverse-engineered conservation functions from each exchange to calculate a minimum return and price impact percentage. The algorithm returns a list of recommended routes for a user in descending order of highest returns. While early versions of Eta X are simply analytics tools to inform traders, the ultimate goal of Eta X is to facilitate the execution of profitable trade opportunities via wallet and smart contract integration.

In addition to the Eta X user interface, we have also developed a public API endpoint through which users may integrate Eta X’s services directly into their own projects and introduces the ability to make queries en masse. The API currently has two endpoints:

Order Router

Order Router Split

Eta X API is a powerful tool that can revolutionize the way decentralized trading is integrated into various applications. But why is it so useful, and why should traders and developers care?

The Eta X APIs are designed to be easy to integrate into various applications, even for those who are not proficient in programming. The API documentation is interactive and provides users with easy-to-use tools to construct API calls and get results without writing any code. This can help to reduce the technical barriers to entry for decentralized trading and enable more people to access the benefits of DeFi.

By leveraging these APIs, traders and developers stand to benefit from accessing multiple DEXs and calculating the most profitable trade routes, traders can unlock new possibilities and increase their chances of making profitable trades. For instance, users can introduce the functionality of Eta X to a DApp for distribution, or incorporate its insights into their own trading tools.

The API is built on open-source smart order routing and DEX aggregator endpoints, which means that the results generated by Eta X API are transparent and explainable. This helps to ensure that traders can make informed decisions based on objective data and avoid any potential conflicts of interest or manipulation. As an open-source and community-driven project that reflects the needs and preferences of its users, developers can contribute to its development and make it even more powerful and versatile. This prospect is enhanced via user voting to determine which DEXs to support, making it a community-driven project that reflects the needs and preferences of its users.

In this video, we take a closer look at the API documentation for Deeplink’s Eta X project. The API documentation is interactive and allows users to easily construct API calls and get results without writing any code.

As shown in the demonstration, users can enter the queries they wish to make without needing any prior programming knowledge, the site will then generate shell commands or code snippets for NodeJS, Ruby, PHP, and Python. This is intended to provide both traders and developers with an easy way to integrate our services in a more lightweight way, as opposed to interacting with them via our own frontend interface.

The documentation and playground for Eta X’s API can be found here.

https://restapi.deeplink.network/reference/order_router-1

You can try the Eta X NonML V3 app yourself at the following link:
https://etax3.deeplink.network/

The source code for Eta X NonML V1 can be found here:
https://github.com/Deeplink-Network/EtaX-V1

Originally published in Deeplink Labs Publication

The core concepts and motivation behind Eta X are explored in great detail in our previous article:

However, we will briefly summarize Eta X V1 for readers who are unfamiliar with our progress.

Why is Eta X Important?

The growth of decentralized finance has led to an increase in the number of DEXs, which provide a trustless solution for trading crypto assets. Eta X stands out by offering a platform that is resilient to manipulation and provides the best possible trade routes as calculated by reverse engineering publicly available smart contracts and their respective AMM conservation functions, without engaging in any biased practices.

What is Eta X?

Eta X is a decentralized exchange (DEX) aggregator and smart order routing (SOR) tool developed by Deeplink that can help traders find the most profitable trade routes by considering factors such as price impact, liquidity, and gas fees. Eta X V1 uses a modified Djisktra algorithm to traverse and validate paths from the token being sold to the token being purchased.

To evaluate the profitability of each route, Eta X V1 uses reverse-engineered conservation functions from each exchange to calculate a minimum return and price impact percentage. The algorithm returns a list of recommended routes for a user in descending order of highest returns. While early versions of Eta X are simply analytics tools to inform traders, the ultimate goal of Eta X is to facilitate the execution of profitable trade opportunities via wallet and smart contract integration.

Order Splitting

One of the largest new features introduced to Eta X since our last publication is order splitting, a feature that facilitates trades that are larger than could be executed within a single pool or even single path of swaps across pools.

For example, if you wanted to exchange 7,500,000 AGIX (approximately $36,66,849.18 USD) for the maximum amount of AGIX, previous iterations of Eta X would suggest trading in whole quantities across Uniswap V3:

This trade route would incur an averaged 7.37% price impact, a gas fee of 0.00147753598 ETH (approximately $2.19 USD), and a total minimum return of 485,955 LINK (approximately $3,563,750.99 USD). Eta X however, can do better.

With our new order-splitting feature, Eta X will suggest breaking this trade into smaller trades. In effect, this mitigates the effects of price impact by making use of the distributed liquidity of DeFi.

By breaking the trade down into two smaller trades, we can now observe an average price impact of 5.47%, a cumulative gas fee of 0.00247769267 ETH (approximately $4.38 USD), and a total minimum return of 497,211 LINK (approximately $3,646,296.87 USD) — in this case, saving you $82,545.88 USD in value that would otherwise have been lost to price impact, and this is on top of the savings already made by the old version of the router.

How it Works

Essentially, Eta X takes the routes identified, and if any exceed a given price impact threshold of 10%, it will then calculate a maximum amount that can be put into the best route until the price impact threshold is reached, then it will repeat with the next, and so on. You can think of this as though the trade were being poured into a bucket, once that bucket fills, it begins to spill over into the next bucket, and so on, until the amount traded is distributed across as many buckets as needed.

The function works by starting at the end of the path (i.e., the pool containing the buy token) and calculating the amount of sell token that can be swapped in that pool without exceeding the maximum price impact limit. It then moves back to the previous pool in the path and calculates the amount of sell token needed to swap the amount calculated in the previous pool, as well as the amount of the sell token in the current pool required to not break the price impact limit. The minimum of these two values is taken as the maximum amount of sell token that can be swapped in the current pool without exceeding the price impact limit. This process is repeated until the start of the path (i.e., the pool containing the sell token) is reached.

The function uses the relevant constant product formula to calculate the expected price impact of swapping the sell token for the buy token in each pool. It also takes into account any adjustment needed for Sushiswap subgraphs.

Once the maximum amount of sell token that can be swapped in the path without exceeding the price impact limit is determined, the function returns this amount as the maximum sell amount for the order. If the maximum sell amount is less than the total sell amount, the order is split into multiple smaller orders and this process is repeated until the entire sell amount is swapped through the path.

Additional DEX Support

In the Time since our last publication we have expanded Eta X’s DEX aggregation functionality to include:

The addition of Uniswap V3 and Curve in particular ( the two top DEXs by volume according to CoinGecko) has expanded the effectiveness of Eta X’s SOR capabilities dramatically, by enabling the inclusion of some of DeFi’s most liquid pools.

DEX Community Suggestions

Deeplink’s R&D team is vigilantly searching for the most opportune DEXs to include within the scope of Eta X, dYdX, and Hashflow being targets of interest to us right now. However, we would like to invite you, the community, to have a say in what DEXs you would like to see included in Eta X. As such, we have included a community submissions box for DEX suggestions in which a user can vote on a set of contenders from a list of considerations, or suggest a completely new DEX by entering its name or a contract address such as its deployer or factory contract.

To use this feature, simply click the ‘+ Add New’ button located under the tickboxes for DEX filtering.

You can try the Eta X NonML V3 app yourself at the following link:
https://etax3.deeplink.network/

The source code for Eta X NonML V1 can be found here:
https://github.com/Deeplink-Network/EtaX-V1

Originally published in Deeplink Labs Publication

· Eta X V1 Recap
· Why is Eta X Important?
∘ What is Eta X?
∘ DEX Community Suggestions
∘ Why is Community-driven DEX Expansion Important?
· Try It Out Yourself

The core concepts and motivation behind Eta X are explored in great detail in our previous article:

However, we will briefly summarize Eta X V1 for readers who are unfamiliar with our progress.

The growth of decentralized finance has led to an increase in the number of DEXs, which provide a trustless solution for trading crypto assets. Eta X stands out by offering a platform that is resilient to manipulation and provides the best possible trade routes as calculated by reverse engineering publicly available smart contracts and their respective AMM conservation functions, without engaging in any biased practices.

What is Eta X?

Eta X is a decentralized exchange (DEX) aggregator and smart order routing (SOR) tool developed by Deeplink that can help traders find the most profitable trade routes by considering factors such as price impact, liquidity, and gas fees. Eta X V1 uses a modified Dijkstra algorithm to traverse and validate paths from the token being sold to the token being purchased.

To evaluate the profitability of each route, Eta X V1 uses reverse-engineered conservation functions from each exchange to calculate a minimum return and price impact percentage. The algorithm returns a list of recommended routes for a user in descending order of highest returns. While early versions of Eta X are simply analytics tools to inform traders, the ultimate goal of Eta X is to facilitate the execution of profitable trade opportunities via wallet and smart contract integration.

DEX Community Suggestions

Deeplink’s R&D team is vigilantly searching for the most opportune DEXs to include within the scope of Eta X, dYdX, and Hashflow being targets of interest to us right now. However, we would like to invite you, the community, to have a say in what DEXs you would like to see included in Eta X. As such, we have included a community submissions box for DEX suggestions in which a user can vote on a set of contenders from a list of considerations, or suggest a completely new DEX by entering its name or a contract address such as its deployer or factory contract.

Why is Community-driven DEX Expansion Important?

With hundreds of DEXs currently available and more popping up each day, it can be challenging for users to navigate and access the liquidity they need. This is one of the biggest draws of DEX aggregators and smart order routers, tools that enable you to compare and route orders across multiple DEXs seamlessly.

With so many DEXs out there, some thought is required when selecting which ones to support. Traditionally, these decisions are made internally by the aggregator’s team or management, generally based on factors such as liquidity, volume, demand, and ease of integration. However, this approach can be subjective, centralized, and biased toward certain projects or stakeholders.

To address this, we are embracing a community-driven approach to expanding our ensemble of supported DEXs by inviting you to vote on which to add next. We believe that by democratizing the decision-making process we are enabling greater transparency, inclusivity, and fairness to the ecosystem — we want to hear your thoughts, and your favorite DEXs based on your own research, experience, and priorities.

Furthermore, this is in strong alignment with Eta X’s core value of agnosticism, we intend to foster a platform free of bias, completely free of the hidden mechanisms laced into other aggregators. In the true spirit of Web 3, we wish to embrace the wider community and to foster innovation, competition, and diversity from across this decentralized ecosystem to bring you the best opportunities for liquidity, pricing, and efficiency.

You can try the Eta X NonML V3 app yourself at the following link:
https://etax3.deeplink.network/

Don’t forget to vote on your DEX of choice! To use this feature, simply click the ‘+ Add New’ button located under the tickboxes for DEX filtering, and vote for your selection either from the list of our favorites or by entering your own by typing in its name or pasting a relevant contract address.

The source code for Eta X NonML V3 can be found here:
https://github.com/Deeplink-Network/EtaX-V1

Originally published at https://medium.com on April 4, 2023.

Original post could be found here

Contents

· Contents
· Introduction
· What is Eta X?
· Why is Eta X Important for Crypto’s Future?
· How Does Eta X Work?
∘ On-chain Data Collection
∘ Liquidity Pools and Swap-hops as Bidirectional Network Graphs
∘ Pathfinding Algorithms for Order Routing
∘ Price Impact Calculation and Route Selection
· Future Work
∘ Expanding DEX Support
∘ Data Collection Optimization
∘ Order Splitting
∘ Larger Graphs and More Powerful Pathfinding Algorithms
∘ Predictive Analytics
∘ Order Execution
· References

Introduction

This article outlines Deeplink’s latest project, Eta X. This version of Eta X is a proof of concept intended to demonstrate our smart order routing techniques but can be used analytically to inform a user of optimal trade paths, and can even highlight arbitrage opportunities across pools and exchanges. Some preliminary reading on the subjects discussed below can be found in our Medium publications:

• Smart Order Routing: A Comprehensive Guide
• Pathfinding Algorithms for DEX Aggregation and Smart Order Routing
• Machine Learning Applications in DEX Aggregation and Smart Order Routing

What is Eta X?

Eta X is an open-source initiative to build an agnostic decentralized exchange (DEX) aggregator and price discovery engine/smart order router (SOR). It has been designed from first principles to be universal, scalable, and unbiased via an adaptable method of reverse engineering the conservation functions employed in the automated market maker (AMM) algorithms of DEX liquidity pools.

A live demonstration of Eta X V1 can be found here:

EtaX v1

Eta X is an open-source initiative to build an agnostic price discovery engine, smart order router (SOR) framework for…

etax.deeplink.network

The source code can be found here:

GitHub — Deeplink-Network/EtaX-V1

You can’t perform that action at this time. You signed in with another tab or window. You signed out in another tab or…

github.com

Why is Eta X Important for Crypto’s Future?

As decentralized finance (DeFi) grows, so does the number of exchanges on which blockchain-based assets can be traded. DEXs are seeing more and more adoption as the community trends towards trustless solutions in light of a string of centralized sources of fraud throughout the crypto ecosystem in recent years. In alignment with the philosophy of blockchains, DEXs address this issue by providing platforms that are resilient to manipulation by malicious insiders via distributed systems, algorithmic market making, open-source code review, and the Darwinian-esque selection of trustworthy and useful tools by the free market.

A DEX aggregator is a service that brings liquidity pools from multiple DEXs together in one platform and is generally packaged with some form of SOR. These aggregators can be compared analogously with services from other industries such as Google Flights or Digg. However, (much like many aggregators in other industries) DEX aggregators are generally not agnostic and have built-in biases that reward certain parties involved. This often takes the form of routing orders through liquidity pools which have reward schemes set up in favor of the protocol doing the routing, or via agreements with DEXs who wish to have more volume through their pools (which is proportional to revenue from fees).

Eta X strives to provide entirely unbiased DEX aggregation and SOR by abstaining entirely from engaging in such practices. Eta X will always provide the best possible routes as calculated by reverse engineering publicly available smart contracts and their respective AMM conservation functions.

How Does Eta X Work?

At its core, Eta X V1 is a pathfinding algorithm that uses AMM conservation functions to identify the best prices for exchanging one crypto asset for another by trading across a selection of routes across DEXs. Conservation functions are the largest factor in determining the profitability of trading within a given liquidity pool, to surmise, the conservation function determines the percentage by which you will change the price of the assets in the pool when you make a trade in it, this percentage change incurs a loss on your end. This iteration of the service is primarily designed around the XYK conservation function but has been designed with modularity and scalability in mind, and other functions such as constant mean product are being integrated presently.

On-chain Data Collection

Version 1 of Eta X relies on subgraphs provided by The Graph, an indexing protocol for querying blockchain networks (Ethereum, in this case). Currently, the service queries Uniswap V2 and SushiSwap, as they are similar in design and both use the XYK conservation function.

A user inputs two crypto assets, one which they wish to sell, and one which they wish to buy, along with the amount that they wish to sell. Queries are then sent which find pools that correspond to the relevant permutations of the two given assets, these permutations can be seen in the table below, where pools contain token0 and token1, and we are selling token A for token B:

Table 1: Token Query Permutations

These tokens are queried and sorted for values such as liquidity in USD or reserves in USD, as these are generally a somewhat decent indicator of their resistance to price impact and volatility-induced slippage. It is worth noting that Not Token A: Not Token B and Not Token B: Not Token A are not included but likely will be in future iterations, as they were found to increase query times without generally providing better paths. It may be the case that some set theory principles may be employed to collect pools that are not a given token but are also selected from the list of ‘not given tokens’ retrieved in queries 1 and 3, however, this complexity would also increase query times — further testing is required to evaluate the effectiveness of these approaches.

Liquidity Pools and Swap-hops as Bidirectional Network Graphs

One of the best ways to negate losses to price impact is to distribute your order across liquidity pools. This can be accomplished either by breaking your order down into smaller parts and trading smaller amounts through multiple pools, by using intermediate pools to bridge a trade across multiple pools (sometimes called swap-hops), or a combination of both.

Swap -hops are best understood by a real-world example, swapping UNI for LINK can be done directly in one pool if such a pool exists on the given exchange. Assuming this pool exists, it may have low liquidity, which would result in large losses to price impact — low liquidity/reserves can also be indicative of volatility, a primary factor in losses to slippage. If there exist at least two pools containing at least one of the two given assets, a swap-hop can potentially facilitate a trade route that is less susceptible to both price impact and slippage. For example, WETH-UNI and WETH-LINK pools could be used to make a trade as follows:

1. Sell UNI for WETH in the first pool
2. Take that WETH and sell it for LINK in the second pool

In this case, if we were to swap 1,000 UNI ($6256) for LINK directly in the Uniswap UNI-LINK pool we would incur a 9.7% loss to price impact, receiving 87 LINK and paying 0.0007 ETH in gas fees. Whereas the route traversing UNI-WETH → WETH-LINK across Uniswap pools only incurs a 0.075% price impact, receiving 97.5 LINK and paying 0.0014 ETH in gas fees. In this real-world scenario, Eta X has saved the user $68.86 worth of UNI.

In order to find these swap-hop routes, Eta X creates a bidirectional network graph of relevant liquidity pools, where each node in the graph represents a liquidity pool. Each pool is then connected to any other pool with one or more assets in common, for example, a DAI-USDC pool would connect to a DAI-WETH pool, but not a WETH-UNI pool. This is explained in more depth in our article on pathfinding for SOR, the following graph depicts the graph derived from a set of pools queried from a USDC and WETH trade query, pools in this visualization are sized by their total locked value (TVL, a strong indicator of resistance to price impact and slippage):

Pathfinding Algorithms for Order Routing

Network graphs are an optimal representation of data for pathfinding optimization, as such, representing liquidity pools in this fashion opens our system up to the many well-established pathfinding algorithms of graph theory. While the number of DEXs factored into calculations are limited to single digits, simple-yet-effective pathfinding algorithms such as Bellman-Ford suffice in negligible runtime. Despite the O(V3) time complexity for our near V2 worst-case scenario, the graphs are small enough to negate this impact.

However, simply implementing the Bellman-Ford algorithm in its original form raises some issues with path validity. For example, while the traditional Bellman-Ford algorithm may see a path selling USDC for WETH along the route of pools USDC-DAI → USDC-LINK → LINK-WETH as valid, it is not actually valid for our purposes, as this path represents the following sequence of swaps:

1. Sell USDC for DAI in the USDC-DAI pool
2. Take that DAI and sell it in the USDC-LINK pool — here we see our issue, this pool does not accept DAI

Therefore, we have to include some extra checks to ensure path validity. In this system, a path is valid if the token being sold in the current pool must exist in the next pool, and if the final output token is the token being purchased. A single node is also considered a valid path if it contains both of the assets involved in the swap.

The algorithm for this process is as follows:

1. Enter the first node with the asset being sold
2. Take the partner asset of that node to the next node, if the partner symbol does not exist in that node, the path is invalid
3. Repeat this until reaching the final node, if the final output asset is not the asset being purchased, the path is invalid

Price Impact Calculation and Route Selection

Now that we have created a graph and a modified Bellman-Ford algorithm to traverse and validate paths from the token being sold to the token being bought, we need to evaluate the profitability of each path identified. While there are certainly other factors that contribute to the profitability of an order route, price impact, slippage, and gas fees are two of the most important. As such, for each exchange, we have reverse-engineered the AMM conservation function to calculate a minimum return and price impact percentage and grab gas fee estimates directly from the Ethereum network.

For DEXs using the XYK conservation in their pools such as Uniswap V2 and SushiSwap V2, assets are priced via the following equation:

Where x is the reserves of token0, y is the reserves of token1 and k is a constant. Let’s say we want to swap token x for token y, we can use the following equations to determine the impacted price, minimum return, and price impact percentage:

Where x_new is the new reserve of token x after depositing x_input, y_new is the new reserve of token y after adjusting to maintain the constant k, r_min is the minimum amount of token y returned from the swap, p_y, and p_y_new are the prices of token y before and after the swap respectively, and P is the price impact percentage.

Using these equations our pathfinding algorithm is modified further to calculate the price impact of each swap in each route. These calculations are done after the simple paths are calculated, so as to avoid calculating price impact for invalid routes, which means that even though we are doubling over the small list of valid routes, we are not wasting computations on price impact calculations for the many invalid routes.

These routes are then sorted by returns and a list of recommended routes is returned to a user in descending order of highest returns.

Future Work

Having proven the concept and effectiveness of SOR by price impact-based pathfinding techniques, development on Eta X can be further improved along several verticals.

Expanding DEX Support

One of the most obvious ways to extend the capabilities of Eta X is to simply include more DEXs. The system has been designed such that doing so is a relatively streamlined and modular process, however, some work is required to reverse engineer the ever-increasingly complex conservation functions of emerging DeFi protocols. SushiSwap is a fork of Uniswap and has been seamlessly integrated with Eta X as of now, Balancer is next on the roadmap on account of its popularity and solid subgraph support.

Price impact calculation algorithms have already been written for Balancer’s multi-asset pools, which use a constant mean product conservation function, as opposed to the standard constant product conservation function devised by Uniswap. While the change may appear inconsequential at first glance, there are some major differences in the calculation of price impact. Balancer’s pools are kept in correct ratios by the following equation:

Where V is a constant, Bt is the balance of token t, and Wt is the proportional weight of that token in the pool. Balancer pools can hold up to 8 tokens in a liquidity pool, where each token is assigned a weight from 0–100. For example, a pool containing:

• 200 WETH with a weight of 60
• 100,000 USDC with a weight of 20
• 100,000 DAI with a weight of 20

The constant V is given by:

The amount of tokens received in a Balancer pool swap is given by the following formula:

Where A_O is the amount of token being swapped out of the pool, A_i is the amount of token 1 in, Bi is the balance of token being swapped into the pool, s is the swap fee of the pool, Wi is the weight of the token being swapped in, and WO is the weight of the token being swapped out.

Community Suggestions

While we will be working to add the most popular and useful exchanges through our own vetting method, we would like to invite the community to suggest their own additions to Eta X’s DEX pool. To achieve this, Eta X V2 will include a DEX suggestion form where users can import a DEX and request its addition to Eta X.

Data Collection Optimization

As powerful as The Graph is, it is not without some latency limitations. Fetching pool data is by far the biggest bottleneck in the current iteration of the system, constituting up to 80% of the runtime per query in worst-case scenarios. In response to this, we are looking into tighter integration with L3 Atom for faster and more reliable feeds by grabbing data directly from Ethereum via Infura and deriving the relevant values manually. Additionally, we may also be able to squeeze more out of The Graph by either migrating over to their decentralized subgraphs or by hosting our own subgraphs.

Additionally, caching methods may improve the latency of the current implementation by querying large sums of pool data periodically and retrieving this data per user input, as opposed to the current PoC method of querying subgraphs with each user input.

Order Splitting

Order splitting is a crucial piece of SOR, and will be a major area of focus for Eta X V2. Order splitting involves breaking an order down into smaller parts to be distributed across multiple pools or routes. This concept is currently in the research stage of development, in which we are exploring options such as dynamic algorithms for splitting orders by liquidity, total value locked (TVL), and other such factors. We are also exploring the possibility of leveraging deep reinforcement learning (DRL) for order splitting purposes, in this process, a DRL agent would be tasked with splitting orders using the algorithms of Eta X in such a way that maximizes returns. This can be done off-chain in such a way that does not require any actual crypto to be transferred, thanks to the use of price-impact calculations. However, this may miss some important caveats of volatility and slippage, factors that may need to be considered as parameters in our model.

Larger Graphs and More Powerful Pathfinding Algorithms

As we add DEXs to the search space of routes, the number of nodes in a given graph will expand rapidly. This may mean that dynamic algorithms such as Bellman-Ford will begin to struggle to find paths within a reasonable timeframe. In this case, we may need to employ algorithms more suited to large graphs. The intricacies of pathfinding algorithms for this problem are explored in more depth in this article. While still an example of dynamic programming, the Floyd-Warshall algorithm is particularly effective for worst-case scenarios of v2 graphs, where Bellman-Ford takes is O(v3) for each node, Floyd-Warshall is O(v3) for the entire graph.

Another promising approach would be the inclusion of heuristic algorithms such as ant colony optimization or genetic algorithms, both of which are particularly effective at finding near-optimal paths through large graphs.

Predictive Analytics

While price impact calculations go a long way in estimating the profitability of an order route, we will likely want to factor in other datapoints to account for potential slippage losses to volatility. This may be an area in which complex data collection and machine learning could benefit the system greatly. For instance, we may be able to attribute risk scores to pools by assessing their liquidity and volume over time, this may even allow us to identify malicious or faulty pools (which most certainly do exist on many DEXs).

Were models to be trained via historical datapoints, it may even be possible to predict data somewhat ahead of time by using Ethereum’s mempool data to retrieve transaction information before they are processed by the blockchain and their target smart contracts.

Order Execution

Early iterations of Eta X are intended to demonstrate the methodology and capabilities of the SOR algorithms designed in-house by Deeplink, while also being an analytical tool through which users can identify trade opportunities. Later stages of Eta X are intended to facilitate the execution of these trade opportunities via wallet and smart contract integration.

References

• https://github.com/graphprotocol/research/blob/master/papers/whitepaper/the-graph-whitepaper.pdf
• https://balancer.fi/whitepaper.pdf
• https://uniswap.org/whitepaper.pdf
• https://docs.sushi.com/

Background of the project

DeepBrew is blockchain-native adaptation of the classic ‘The Beer Game’, a macroeconomic supply chain scenario, to demonstrate a proof of concept to Deeplink’s core vision — combining off-chain machine learning into on-chain environments e.g. smart contracts.

The research project aimed at progressing the synthesis of machine learning and blockchain technologies. In particular DeepBrew involves the augmentation of Ethereum smart contracts with deep reinforcement learning agency to enable intelligence and dynamism beyond the scope of traditional contracts while still maintaining the decentralization and security aspects of the EVM. Later in this article, you will be able to see the methodologies and the workflow we have used to execute the off-to-on-chain reinforcement learning systems.

In this article and thesis, we initially talked about bringing machine learning systems in smart contracts and the blockchain. We shared how the game runs entirely off-chain, and exists as a set of Python scripts which interface with a private Ethereum testnet via Web3.py (the ERC20 BEER token however is deployed as a Solidity smart contract to the testnet).

The last version was done so by creating an API which broadcasts the model’s outputs, and an oracle, which takes these outputs for use in Solidity contracts.

This game functions by displaying Beer game deep learning training results and interactions between on-chain and off-chain and does not have any commercial application or utility.

Live Performance

Watch the game unfold on the Goerli Ethereum testnet in real-time, as agents swap BEER for CASH tokens in accordance with instructions from the deep reinforcement learning environment and model keeper script.

Link to DeepBrew Demo page

You will also be able to observe the game’s transactions pulled directly from the Goerli ledger.

Architecture

DeepBrew has been devised to provide a dynamic optimisation problem involving transactions and the management of complex systems. A soft actor-critic deep reinforcement learning algorithm is then trained against rule-based agents. Finally, variables from this model and environment are passed on to prompt the execution of an Ethereum smart contract via an oracle, demonstrating an intelligent ‘on-chain agent’.

The following architecture outlines the framework for connecting off-chain machine learning to on-chain smart contract execution.

Deep Reinforcement Learning Model (Soft Actor-critic)

The selected model for optimizing The Beer Game is a relatively lightweight soft actor critic deep Q-learning model, a type of reinforcement learning model which builds on the traditional Q-learning actor-critic framework of policy adjustment via Q-functions by making two estimates for Q-values in an effeort to avoid overvaluing rewards. The model is separated into an actor and critic, the actor makes actions in the space, and the critic evaluates the effectiveness of those actions. This is done via clipped double Q-learning which takes the minimum of two Q-value estimates using the following function:

On-chain Machine Learning Workflow

This project was undertaken largely in order to develop a methodology for the implementation of more practical off-to-on-chain reinforcement learning systems. This workflow can be broken down into following steps:

1. Recreate your Web3 problem as accurately as possible in a local testnet such as Ganache

• Local testnets are recommended for this stage as they run dramatically faster than public testnets, and have admin functionality
• This may be less daunting of a task than it sounds, as the code on which Web3 ecosystem reside is publicly available

2. Convert this problem into a reinforcement learning environment

• OpenAI’s Gym class is a good starting point

3. Train a reinforcement learning model to optimize your problem

4. Deploy your system onto a public testnet such as Goerli for bugtesting purposes

• Sending transactions on a public blockchain is more involved than on a local one
• This will also give you a sense for the real-world execution speeds you can expect

5. Once this model performs satisfactorily, leverage transfer learning techniques to deploy your model onto the mainnet

• Transfer learning allows the model to begin training from where the prototypes left off, rather than deploying a randomly acting agent onto the mainnet with real funds
• It is strongly advised that safety measures such as spending limits are put in place to keep the model from doing anything extreme

Applications and future work

The applications of this technique are broad in scope, and can be applied to any problem in which dynamism and intelligence would benefit a Web3-based use-case. Some examples of these applications include but are not limited to:

• DeFi Capital Efficiency
• On-chain Algorithms
• On-chain Credit Scores
• Artificially Intelligent Smart Order Routing
• DEX Aggregation

What’s next?

Stay tuned for ETA X V1.

Eta X is an open-source initiative to build an agnostic decentralized exchange (DEX) aggregator and price discovery engine/smart order router (SOR). It has been designed from first principles to be universal, scalable, and unbiased via an adaptable method of reverse engineering the conservation functions employed in the automated market maker (AMM) algorithms of DEX liquidity pools.

by Jack Lodge

This paper proposes the first steps towards on-chain artificial intelligence, a layer 2 solution which demonstrates the potential of on-chain deep reinforcement learning is presented, along with the methodology behind its implementation.

This project acts as a demonstration of this technology, and to develop a framework on which more complex technologies can be built. While an undoubtably revolutionary technology, smart contracts are not without limitations. Contrary to their name, they are rigid, and for the most part, not capable of intelligent execution at the same levels which their off-chain counterparts enable. The potential for smart contracts is currently hindered by these limitations, the prospect of decentralized finance (DeFi), and many other intricate use cases in the spaces of Industry 4.0 and Web 3.0 require solutions of rapidly increasing complexity.

The introduction of artificial intelligence into the execution of on-chain environments will be a key development in bringing these technologies further into the mainstream. This is an ongoing project and is thus subject to change, should superior approaches to any of the following sections be identified along the way.

Google Drive: Sign-in

Originally posted at Deeplink Labs Publication

· Introduction
∘ What is Pathfinding?
· Glossary
∘ Smart Order Routing
∘ DEX Aggregation
∘ Graphs
∘ Weighted Graphs
∘ Directed Graphs
∘ Temporal Graphs
∘ Graph Traversal
· Metrics and Nuances of Pathfinding Algorithms
∘ Informed vs. Uninformed Algorithms
∘ Completeness
∘ Termination
∘ Admissibility
∘ Big O Notation
· Common Pathfinding Algorithms
∘ Rapidly-exploring Random Trees
∘ Greedy Algorithms
∘ Dynamic Algorithms
· Heuristic Algorithms
· Representing Smart Order Routing for DEX Aggregation as a Pathfinding Problem
· References

Introduction

This article outlines the ongoing research Deeplink is undertaking regarding the framing of both smart order routing and DEX aggregation as pathfinding problems. A brief overview of what pathfinding is and some common techniques are provided, along with a detailed explanation of how this field of study applies to these problems, and finally, a collection of related works are investigated.

What is Pathfinding?

Pathfinding is the computational field of identifying the shortest route between two points. Pathfinding algorithms are used across many industries and applications including search engines, video games, GPS navigation software, and robotics, to name a few.

One of the simplest examples to consider is a GPS route optimization algorithm in which nodes are landmarks or destinations, and edges are the paths between those locations, weighted by the physical distances, a pathfinding algorithm could find the shortest route through these locations from one location to another by traversing the edges in such a way that minimizes the total weight traversed.

Another example, reminiscent of Euler’s Königsberg Bridges problem, can be found in infrastructure planning such as logistics, motorway, or railway design. For instance, when designing complex systems such as a metro, it is important to minimize redundant travel in the layout of the train lines in order to avoid congestion and slow journeys. One fundamental approach to doing this is to use pathfinding algorithms to identify the shortest Euler path between all relevant metro stations, in other words, the shortest path which visits each station at least once. A system of stations can also be broken down into discrete lines, each of which can have its own shortest Euler path. This can be seen in the following representation courtesy of Paragon Routing, a pathfinding and route optimization software provider.

Glossary

In previous articles we have outlined both smart order routing and DEX aggregation in some depth, to fully grasp the necessity for pathfinding algorithms in enhancing these spaces, we recommend reading those articles. However, a brief summary of each will also be provided here, along with a few important preliminary concepts.

Smart Order Routing

Smart order routing (SOR) is an automated process in which orders on exchanges are handled with the intent of attaining the most desirable path across trading venues. In a DEX, this generally takes the form of finding the optimal path of swaps across a set of liquidity pools in order to take advantage of the liquidity depth of those pools, and mitigate the effects of fragmented liquidity. The primary cause for concern regarding this liquidity fragmentation being negative slippage, losses incurred on account of a change in spot price in the time between an order being placed and executed.

DEX Aggregation

A DEX is a trading venue consisting of a set of liquidity pools that facilitate the exchange of assets without a central authority or the need for users to forfeit custody over their assets. DEXs are prone to the aforementioned issues of liquidity fragmentation as their asset pairs are segmented into liquidity pools, and as more and more venues arise, the overall market liquidity becomes more and more thinly spread.

DEX aggregators expose traders to more liquidity than any one DEX could provide by aggregating and connecting the services of multiple DEXs. A DEX aggregator can be thought of analogously to services like Expedia or Google Flights, which aggregate offerings from numerous airlines into one comparative service, giving users access to the best possible options for their needs.

Graphs

In computer science, pathfinding is most commonly represented using graphs-sets of connected nodes. In a graph, nodes can be thought of as places, computers, people, etc. depending on the application, while the connecting edges can be thought of as whatever relates those nodes to one another, e.g. an edge connecting two nodes representative of cities may be representative of a highway, or an edge connecting two asset pools may represent a swap between those two pools.

It is worth noting that there are many other representations of spaces which can be used in pathfinding, such as grids, 2D or 3D spaces, or even more abstract data structures such as octrees and quadtrees. However, graphs are the most widely used and most easily related to our use case.

Weighted Graphs

Graph edges can also be weighted, attributing values to the connections between nodes. For instance, the weight in the two cities example may be the physical distance between the cities, or in the asset pools example, the weight may indicate the fees incurred by making that swap.

Directed Graphs

Additionally, graphs can be directed, that is, some or all edges can only be traversed in one direction. That is, a node can point to another node without that node pointing back to it. For example, if the only path between points A and B is a unidirectional road, that would be a directed edge connecting those two nodes.

However, some nodes may still be traveled to from one another in a directed graph, this is represented by two arrows pointing from each node to the other. Furthermore, nodes can also point at themselves, indicating that it is a valid move to travel from that node to itself — this is known as a loop.

Temporal Graphs

Temporal graphs represent nodes and connections which change over time. For example, a node may only be accessible temporarily, or the weight of an edge may not be constant over time. Temporal graphs are a relatively recent development in graph theory, and can dramatically increase the complexity of tasks such as graph traversal. Temporal graphs are somewhat of an emerging field and are quite complex in nature, for further reading on the topic, here is a good resource that explores them in depths beyond the scope of this article.

Graph Traversal

When representing spaces as graphs, pathfinding can be represented as graph traversals. This often involves finding the shortest path to connect two or more points, by using the least edges, or by accumulating the least weight along the paths connecting those nodes. Alternatively, graph traversal can find a path that visits each node in a graph in such a way that similarly minimizes the cost of doing so.

Metrics and Nuances of Pathfinding Algorithms

The following section outlines some terms and concepts which are useful in understanding the effectiveness or applicability of a given pathfinding algorithm.

Informed vs. Uninformed Algorithms

Informed algorithms (such as greedy search) have some information regarding their own goal, provided by the function which is used to estimate the closeness of its current state to its goal state (destination node, in our case).

Conversely, uninformed algorithms (such as depth-first and breadth-first search) do not have information regarding their own goal.

Completeness

A pathfinding algorithm is considered complete if it is guaranteed to complete execution, i.e. it will not get stuck running forever.

Termination

A pathfinding algorithm can have one or more termination conditions, requirements by which it will cease execution, such as finding the solution if it exists.

Admissibility

A pathfinding algorithm is admissible if an optimal solution is guaranteed to be found, provided enough time, memory, and computation are provided.

Big O Notation

Big O notation is the standard mathematical notation for describing the behavior of a function or algorithm as a limit when a relevant variable approaches a specific value such as infinity. It is used to express the efficiency of the algorithm, for example, we can say that the Bellman-Ford equation takes O(VE) time, meaning that we can expect a given graph with V vertices (nodes) and E edges to be solved by the Bellman-Ford algorithm in V*E steps.

Common Pathfinding Algorithms

Pathfinding algorithms can largely be divided into one of three main categories, dynamic, greedy, or heuristic. This section will outline the differences between these approaches and provide some famous examples of each.

Rapidly-exploring Random Trees

Rapidly exploring random tree (RRT) can be either greedy or dynamic depending on how the specific implementation is tweaked. RRT search is useful for exploring high-dimensional spaces, particularly, it is used to find open-loop trajectories in nonlinear systems. As such, it may be useful in the event that simple graphs do not adequately represent the complexity of the system at hand. RRT achieves its traversal by extending random branches into the largest unexplored regions of a given space; given enough time, it will give a relatively optimal path to the desired location. It can also be useful when the exact location of the goal object is not known. It is an industry-standard algorithm for pathfinding and route optimization in autonomous vehicles and robotics, as can be seen in this demonstration created by the author of this article:

RRT SLAM (simultaneous localization and mapping) Demonstration, source: Jack Ryan Lodge

The blue lines on the right-hand window depict the branches of the robot’s RRT-based pathfinding algorithm as it explores the building.

Greedy Algorithms

A greedy algorithm is one that builds a solution piece by piece, at each step it chooses the option which yields the most immediate benefits, in other words, the ‘greedy’ option. With greedy algorithms, there is no guarantee that an optimal solution will ever be found, though they are generally more efficient regarding memory usage and time complexity than their counterparts.

Djikstra

Djikstra’s algorithm is a simple yet effective greedy algorithm for finding the shortest path between one node and all other nodes in a graph, or it can be used to give the shortest distance between any two given nodes. It essentially calculates the distance of each node one-by-one from a given source node, updating a list of shortest paths each time a longer path is undercut. Many other algorithms have built on this concept but retain the principle of iteratively searching for near-optimal paths and replacing them once better ones are identified until the most optimal path is found.

A*

A* builds on Djikstra’s algorithm by introducing a heuristic function that can be used to prioritize nodes, in other words, it is an informed algorithm. Heuristics can dramatically improve the performance of A* if the problem facilitates such an optimal heuristic, and the heuristic is optimally designed. Similarly to Djikstra’s algorithm, A* begins at a source node, it then aims to create a path to a destination with the smallest possible cost by creating and minimizing a tree of paths between source and destination nodes until the terminal criteria are reached — The shortest of these paths is then selected.

Dynamic Algorithms

When solving parts of a problem (sub-problems), dynamic algorithms store the solutions to those sub-problems along the way then make decisions at each step based on the current situation and the solution to previously solved sub-problems when calculating for optimal solutions. Unlike greedy algorithms, dynamic algorithms are guaranteed to find optimal solutions (if one exists). However, as a trade-off, they are generally more taxing in terms of both memory and time complexity than greedy algorithms.

Bellman-Ford

The Bellman-Ford algorithm serves essentially the same purpose as Djikstra’s algorithm and A*, and is often considered the best of the three approaches. It can be slower, but is more versatile, as it can handle graphs with mixed signed weights (positive and negative). It does this by introducing a relaxation equation which essentially uses relative distances between nodes via the triangle inequality theorem to calculate the distance of between nodes by comparing that distance with other known distances.

Heuristic Algorithms

Heuristic algorithms are designed to solve a specific decision problem quickly and efficiently by sacrificing some optimality and/or completeness. They are best used as approaches to problems to which there is no known way to reach an optimal solution in a reasonable amount of time or computational effort. They provide no guarantee of optimality but can find near-optimal, or local maxima/minima solutions for problems that remain intractable to greedy or dynamic algorithms. The most famous and immediately recognizable example of this would be the artificial neural networks found in deep learning models for artificial intelligence.

Ant Colony Optimization

Ant colony optimization algorithms aim to find paths through graphs in a multi-agent approach. Artificial ant agents perform local search algorithms and leave behind digital pheromones for their peers, together, the cumulative pheromone trails left behind by the entire collection of artificial ant agents will often find optimal or near-optimal paths, even in extremely large or complex spaces.

Genetic Algorithms

Genetic algorithms are based on biological natural selection, the underlying process behind evolution. A population of agents are generated which perform a set of actions corresponding to their ‘genetics’, a set of traits unique to each individual, these agents have defined goals and metrics of success. The more successful an agent is in achieving the desired result, the more likely its genes are to be copied into the next generation. In the context of pathfinding, this generally involves agents who traverse the given graph with the lowest energy spent, or most resources acquired passing their genes on to the next generation.

Representing Smart Order Routing for DEX Aggregation as a Pathfinding Problem

In order to understand why pathfinding is a useful concept when devising DEX aggregator SOR algorithms, it is important to remember that a DEX, and consequently a DEX aggregator, is essentially a collection of liquidity pools. These pools act as a point between a pair of assets at which they can be swapped. The following outlines an example in which a DEX is depicted as a graph, over which a pathfinding algorithm is run in order to make a saving on a trade.

DISCLAIMER: THIS IS A HYPOTHETICAL, DEMONSTRATIVE EXAMPLE OF HOW SOR CAN BE TREATED AS A PATHFINDING PROBLEM

We can consider this sea of liquidity pools as a graph, in which the pools are nodes, and the possible swaps between them are edges. We can continue this and consider it as a weighted graph, where the weights may represent the profitability or viability of swapping between two pools. For example, consider the following fictional, relatively DAI-centric DEX consisting of 6 liquidity pools (ETH-WBTC, DAI-WBTC, ETH-DAI, DAI-USDT, DAI-FTM, USDT-FTM).

Immediately we can see that there does exist a pool such that our swap could be completed, the ETH-DAI pool, however, let’s explore why this may not be the best approach. At each of these nodes, one of the listed tokens can be swapped for the other, in either direction. This means that after swapping at one pool, the other asset is now possessed, as such, after trading with a pool, the new asset can be traded with any pools which also contain that asset. We will demonstrate this relationship by created a directed graph of potential swap sequences.

Now let’s consider a scenario in which a trader wishes to swap 100 ETH for as much DAI as possible. We will mark any pools containing ETH as green source nodes at which the path begins, and any pools containing DAI as orange destination nodes at which the path can end, blue nodes denote pools that are neither sources nor destinations.

Note that the ETH-DAI pool is a gradient of green and orange, as the path can both begin and end here. Additionally, source nodes have gained a loop that connects this node to itself, this helps in both illustrating the fact that this is also a potential path (representative of the initial swap required to enter the graph), and in the calculations of our pathfinding algorithms.

Next, we assign weights to the edges connecting the nodes. We can think of this as the expected slippage percentage of trading in the pool being pointed at, and we can assume that this is calculated via a variety of metrics that factor in liquidity concentration, liquidity spread, volatility, etc. — you can read more about what causes slippage in our article on smart order routing. It may be the case that these edges require machine learning techniques in order to calculate, some techniques for doing so are explored in our article on machine learning techniques for DEX aggregation and SOR, but for the purposes of this explanation, the numbers have been arbitrarily selected.

Note that the swapping of WBTC for DAI is assigned a negative weight, indicating a potential for a 0.2% profit via arbitrage. It is also worth mentioning that algorithms such as Djikstra’s would not be able to handle situations such as this, due to their inability to traverse multi-signed graphs.

We can see that the simplest trade would be to simply use one pool, exchanging ETH for DAI directly, incurring a 5% loss to slippage (5 ETH, or $10,274.31 USD as of the time of this article’s writing). However, let’s examine our other source node, the ETH-WBTC pool, by identifying the shortest paths between it and all other pools. Any of the previously discussed pathfinding algorithms could handle this task, but in this demonstration we will arbitrarily do so by running the Bellman-Ford algorithm over the graph, starting at the ETH-WBTC pool.

Green edges indicate the routes from the ETH-WBTC node to all other nodes in the graph. The numbers in the nodes indicate the cost (accumulative percentage losses to slippage) to reach those nodes. Here we can see that by taking advantage of the arbitrage opportunity when trading WBTC for DAI, we can mitigate some of our losses to slippage. Let’s assume our algorithm selects a 70–30 split, transacting 70 ETH first in the ETH-WBTC, then trading that WBTC for DAI, and 70 ETH directly in the ETH-DAI pool.

0.3*0.5 + 0.7(0.1–0.02) = 0.206%

This indicates a saving of 4.79%, or approximately $9,857.24 USD when compared to the simple method of only using one pool. Remembering that these values were arbitrarily selected and that real DEXs stand to lose even more to slippage (see a real example in our article on DEX aggregators).

Furthermore, this approach is merely demonstrative as to how SOR can be thought of as a pathfinding problem, far more complex pathfinding approaches would likely be required, and would likely yield far more impressive results. One reason for the necessity of incorporating more complex pathfinding techniques is the sheer size of graphs relating to a large DEX aggregator. Our example used a hypothetical DEX with only 7 liquidity pools, Real DEXs and DEX aggregators may be dealing with thousands of nodes, which may result in an exponentially large number of edges. To traverse such graphs with perfect optimality is intractable in the timescales required for a usable service. As such, it may be the case that algorithms that specialize in near optimality (such as ACO or genetic algorithms) may be required in order to keep pace with the complexity requirements.

Additionally, it may be the case that the construction of the graph and its edges is a more complicated task than traversing the graph once created. Selecting valid pools, deciding whether to split orders along with the size and number of those splits, assigning weights

References

1. Harinder Kaur Sidhu, University of Windsor, “Performance Evaluation of Pathfinding Algorithms”, https://downloads.hindawi.com/journals/complexity/2021/5511802.pdf, 2021

Originally posted at Deeplink Labs Publication

· Introduction
∘ Smart Order Routing
∘ DEX Aggregation
∘ Artificial Intelligence, Machine Learning, and Deep Learning
∘ Deep Reinforcement Learning
· How Can Machine Learning Improve Smart Order Routers and DEX Aggregators?
∘ Slippage
∘ Liquidity Concentration
∘ Liquidity Volatility
∘ Liquidity Distribution
· Deep Reinforcement Learning for Smart Order Routers and DEX Aggregators
∘ On-chain Agents
∘ Amalgamating Web 3 and Machine Learning
· Related Work
∘ Reinforcement Learning for Optimization Problems
∘ Genetic Algorithms for Smart Order Routing and Automated Trading
· References

Introduction

This article explores Deeplink’s ongoing research towards machine learning approaches and applications in both smart order routing and DEX aggregation. A brief overview of preliminary concepts is provided, along with a detailed explanation of how this field of study applies to the problems at hand, and finally, a collection of related works are investigated.

In previous articles we have outlined both smart order routing and DEX aggregation in some depth, to fully grasp the necessity for pathfinding algorithms in enhancing these spaces, we recommend reading those articles. However, a brief summary of each will also be provided here, along with a few important preliminary concepts.

Smart Order Routing

Smart order routing (SOR) is an automated process in which orders on exchanges are handled with the intent of attaining the most desirable path across trading venues. In a DEX, this generally takes the form of finding the optimal path of swaps across a set of liquidity pools in order to take advantage of the liquidity depth of those pools and mitigate the effects of fragmented liquidity. The primary cause for concern regarding this liquidity fragmentation is negative slippage, losses incurred on account of a change in spot price in the time between an order being placed and executed.

DEX Aggregation

A DEX is a trading venue consisting of a set of liquidity pools that facilitate the exchange of assets without a central authority or the need for users to forfeit custody over their assets. DEXs are prone to the aforementioned issues of liquidity fragmentation as their asset pairs are segmented into liquidity pools, and as more and more venues arise, the overall market liquidity becomes more and more thinly spread.

DEX aggregators expose traders to more liquidity than any one DEX could provide by aggregating and connecting the services of multiple DEXs. A DEX aggregator can be thought of analogously to services like Expedia or Google Flights, which aggregate offerings from numerous airlines into one comparative service, giving users access to the best possible options for their needs.

Artificial Intelligence, Machine Learning, and Deep Learning

Artificial intelligence refers to intelligence demonstrated by machines, a sentiment in which intelligence refers to the decision-making capabilities generally associated with biological intelligence. Machine learning is a subset of artificial intelligence which refers to algorithms that are able to ‘learn’. Deep learning is a subset of machine learning originating from the McCulloch-Pitts neuron and Rosenblatt’s perceptron, which models the way in which biological neurons process information.

Deep Reinforcement Learning

Deep reinforcement learning (DRL) builds on the foundations of deep learning by further introducing aspects from biology and psychology via the introduction of reinforcement learning techniques. DRL agents learn to solve problems or make predictions by attempting to maximize a cumulative reward, akin to an incentive and penalty model. An example reward function for a DRL agent learning to play the game Snake might reward the agent for closing the distance between the snake’s head and apple, and penalize the agent for crashing into itself or walls.

How Can Machine Learning Improve Smart Order Routers and DEX Aggregators?

In DEX aggregation and SOR, liquidity is key. Allowing your algorithms to make deep correlations between liquidity concentration, distribution, and volatility will allow your systems to outperform those which do not consider these factors in such depth.

Machine learning techniques are used broadly across the traditional finance sectors, and it is only a natural progression that these beneficial applications should eventually see their way into DeFi. Machine learning is often used in traditional SOR to assess and identify factors pertaining to liquidity and volatility in order to ascertain the opportunistic routes, pricing, and order sizing — we believe that many of these practices are directly translatable to DEX aggregation and SOR.

By introducing liquidity indicators via the high speed, high granularity data feeds provided by L3 Atom, machine learning models can identify complex correlations between these factors at dimensionalities beyond the capabilities of human traders, and can use these correlations to outperform services that lack such depth of insight. One major area which stands to benefit from this technology is the avoidance of slippage.

Slippage

The nuances and causes of slippage are explored in more depth in our article on smart order routing, but in essence, slippage is the difference between expected and actual price execution when placing an order on a trading venue. This generally occurs when the asset’s price changes in between the time of placing an order, and the time that that order is executed. Slippage can be positive or negative, meaning that the price difference can either be of benefit or detriment to the margins of the trader in question. However, negative slippage is generally what is meant when the term is mentioned.

Machine learning techniques can be employed to provide predictive insight towards price movements, volatility, and liquidity indicators, all of which play major roles in slippage, and in avoiding it. The following sections outline some areas which can be factored into machine learning-driven predictive analytics and agent-based decision-making algorithms to provide users with the most optimal trades.

Liquidity Concentration

In the context of DEXs, liquidity concentration refers to the available liquidity within a given liquidity pool. Due to the nature of AMMs in DEXs, slippage due to placing large orders is often even more of an issue than in other types of venues, as the liquidity concentration of DEX liquidity pools is generally on the smaller side relative to other sources of liquidity. When swapping tokens in a DEX, you are essentially adding one asset to the liquidity pool while simultaneously removing another, the AMM conservation function then automatically rebalances the ratio of these two tokens. This means that trades in pools with small liquidity, and conservation functions can overcompensate and cause dramatic price swings as the proportional ratio will be more affected — conducive to major slippage. This can be thought of analogously as the fluid displacement of a boat (an order) in a body of water (a liquidity pool); a dingy in a river will virtually have no impact on the water level, but a yacht in a pool certainly will.

Liquidity concentration primarily gives us information on the potential slippage within a single pool. Factoring in the liquidity concentration of individual pools when aggregating and routing through a sea of venues is a crucial element in facilitating optimal trade opportunities. The introduction of this data to machine learning models can open avenues for routing which are beyond the naked eye’s ability to comprehend the implications of liquidity depth. This is similar in concept to Balancer’s smart order routing technique of linearizing spot prices in liquidity pools in order to estimate the change in spot price resulting from an order being placed, predictions which are then used in selecting the optimal set of pools to route through. A more detailed breakdown of how this works can be found in our article on automated market makers.

Liquidity Volatility

With the concept of liquidity concentration in mind, we can generalize that larger liquidity pools tend to be less volatile than smaller ones, as each individual trade makes less of an impact on the pool’s overall liquidity. However, liquidity concentration is only one factor of a pool’s volatility (in both price and liquidity). Volatility metrics are a broadly studied econometric subject with much of their own nuance, a pool’s volatility is tied to its liquidity depth, the price volatility of its underlying assets, its volume, its reputability, and many more external and internal factors. Due to its unwieldy and complex nature, volatility is also a topic to which machine learning is particularly suited.

Research such as this research article published in Hindawi Complexity in 2021, ‘Forecasting Volatility of Stock Index: Deep Learning Model with Likelihood-Based Loss Function‘, which employed long short-term memory (LSTM) deep learning techniques to predict the volatility of stock indices. In this project, Fang Jia and Boli Yang fed historical volatility data points into their deep learning models and compared their performance against a popular traditional econometrics model known as autoregressive moving average and generalized conditional heteroscedasticity (ARMA-GARCH).

The models created were likelihood-based loss LSTM and deep neural networks (DNN), and mean squared error (MSE) LSTM and DNN (four models in total, compared against ARMA-GARCH). The likelihood-loss LSTM outperformed ARMA-GARCH along with the other deep learning models.

These techniques can be adapted to fit the DEX aggregation and SOR problem by creating a volatility prediction LSTM model which uses historical data on the volatility of individual pools. This data would essentially be a time series mapping of orders to their respective impact on the market over time within a given pool, creating a continuous historical record of that pool’s volatility in response to orders — data which can be used to estimate the impact a given order would have on the pool’s liquidity, and the potential slippage it may incur. This can also be augmented with historical price movement data to provide the model with a broader view of the system.

Once trained, the model could then predictively assess a pool’s volatility by running over recent transaction data, but can also tap into unfilled transactions by accessing the blockchain’s mempool — a ledger in which blockchain transactions wait before being processed as transactions and permanently appended to the chain.

Liquidity Distribution

If liquidity concentration can be thought of as a body of water, liquidity distribution can be thought of as a system of bodies of water connected by rivers and streams. A user may want to take a bird’s eye view of these individual bodies of water (liquidity pools) and consider them as a network, before deciding which one would best fit their boat (order). It may even be the case that their boat is too big for any of the pools, and would be best broken down into smaller boats and placed across several.

In other words, liquidity distribution gives us insight into potential slippage across a network of liquidity pools. In the context of a DEX (and even moreso in a DEX aggregator), it is not hard to see why this information would be of great value when routing orders.

Liquidity distribution is key whenever large transactions are involved, particularly when the number of assets involved is above a threshold where orders in such quantities would immensely disrupt a pool, or may even be larger than the entire liquidity of that pool. In such cases, it would be best for both the trader and the ecosystem at large to disperse that order across multiple channels, so as not to bring the supply chain to a grinding halt — as this would certainly cause a price movement that would almost certainly incur unfavorable slippage on that trader’s end, and could cascade into larger negative impacts across the network.

Deep Reinforcement Learning for Smart Order Routers and DEX Aggregators

Using machine learning models to generate predictive metrics for use in more traditional algorithmic approaches has proven to be quite an effective solution, for instance, such models could be used in order to generate the weights connecting liquidity pool nodes as described in our article on pathfinding algorithms for DEX aggregators and SOR.

On-chain Agents

It may be the case that the use of agent-based machine learning techniques such as deep reinforcement learning allows models to form that interpret and react to correlated variables in ways that we may fail to detect as humans. In essence, an on-chain agent is a blockchain-native computational agent, capable of processing data, learning, and carrying out actions such as transacting on the blockchain.

Amalgamating Web 3 and Machine Learning

Bringing deep reinforcement learning execution to blockchains is an area of great interest to Deeplink, and has been the subject of direct research for some time now. Stay tuned to our publication channels for an update on a project centered on exactly such techniques.

Reinforcement learning agents require an environment in which to act. As such, in order to facilitate on-chain agents, we must first convert our Web 3 problem into a reinforcement learning comparable environment. The most popular way of converting any given problem into a reinforcement learning environment is via the use of OpenAI’s Gym API, a reinforcement learning class framework for Python. This involves breaking the given problem into iterable steps which can be represented by the following Python functions:

__init__(self)

• Used to establish the variables used for reinforcement learning, namely, the observation space (the space of all possible observations an agent can make about this environment) and the action space (the space of all possible actions an agent can make in this environment).

step(self, action)

• This is called once every ‘step’ of the environment, in the case of a game, this may be one frame or one turn.

reset(self)

• This both starts the environment on its first run and resets it once an episode has concluded.

In the context of Web 3 problems such as DEX aggregation and SOR, this can be a relatively complex process, not only must the scenario be translated into discrete, iterable steps, it must Web 3 connectivity must be natively built into the environment itself. Essentially, this process can be thought of as building a DApp for your reinforcement learning environment, a DApp that either transacts directly on its own via Web3.py/Web3.js, or which acts more as a keeper for smart contracts, instructing them to transact via TX variables or oracle integration. This script may also need to read data from the blockchain such as balances, transaction hashes, etc., all of which can also be handled via the use of the Web 3 libraries.

It is also likely that in use cases such as DEX aggregation and SOR, model training is best to be done in simulated environments, rather than on live exchanges with real assets. This can be done on private, command line test nets such as Ganache, or on live test nets such as Rinkeby or Goerli. The benefit of private testnets is the ability to control funds without needing to request testnet funds via a faucet, however, this may limit capabilities somewhat, as private test nets such as Ganache are incompatible with oracle functionality. Additionally, if the acquisition of testnet funds via faucets is an issue for your project, it may be a suitable workaround to deploy representative ERC20 (or other) tokens as stand-ins for testing purposes.

DApps can then be built on top of that test net which simulates the scenario which you wish to optimize, generally, this will be built into the reinforcement learning environment script, but may be external to that — in which case, the environment script can simply fetch data from the script running the simulations. For instance, it is likely that a proper backtesting engine (a paper trading, simulated exchange, which may or may not use real data from the exchange/s it is mirroring) would be required to properly train and test a DEX aggregation and SOR deep reinforcement learning agent. Backtesting engines can be more complex than simply APIs which read from an exchange, for instance, it may be wise to incorporate functionality such that the agent’s own orders incur an impact on the market itself. One way of approaching this is to aggregate real market orders which add up to the agent’s order and to consider those as the agent’s order in that time period.

Related Work

In addition to domain-specific conceptual research on the ways in which machine learning can be applied to our specific problem, Deeplink is also conducting an extensive literature review into cutting-edge machine learning techniques that may be leveraged for our purposes. In this section written by Priyanka Pursani Israni, some of our more interesting findings are explored.

Reinforcement Learning for Optimization Problems

Various studies have utilized reinforcement learning for optimization problems like game development, network optimization, etc. NVIDIA (Roy et al., 2021) has unveiled a new technique that makes use of artificial intelligence to construct circuits that are more effective, quicker, and smaller. The result is an increased level of functionality with each new generation of chips. It shows that Deep Reinforcement Learning can teach AI how to build these circuits from scratch. Figure 2 depicts the architecture of the proposed approach while fig.3. shows that the proposed method Prefix RL outperforms other state-of-the-art techniques.

The authors came up with MLGO1 (Perolat et al., 2021), a framework for systematically adding ML techniques to an industrial compiler called LLVM. For demonstration purposes, the description of how and why the machine learning models are used in place of heuristics to improve LLVM’s in lining-for-size optimization is presented. When compared to state-of-the-art LLVM -Oz, the lining-for-size model was trained using two different ML algorithms: Policy Gradient and Evolution Strategies. After months of active development, the same model, trained on a single corpus, generalizes well to a variety of real-world targets as well as to the same set of targets. This trained model property is useful for deploying ML techniques in real-world settings.

The researchers of DeepMind have proposed DeepNash (Perolat et al., 2022), an autonomous agent capable of mastering the game of Stratego with imperfect information, has been proposed by DeepMind researchers. It can play the game at a level comparable to that of a human expert. To learn Stratego on its own, DeepNash employs a model-free, deep reinforcement learning approach that does not rely on search. By directly modifying the underlying multi-agent learning dynamics, the Regularised Nash Dynamics (R-NaD) algorithm, a core component of DeepNash, converges to an approximate Nash equilibrium rather than “cycling” around it. On the Gravon games platform, where it faced off against human Stratego experts, DeepNash achieved a yearly (2022) and all-time top-3 rank, outclassing the state-of-the-art AI methods currently in use. The overview of the stratego and the proposed algorithm is given in fig. 4.

In the proposed research (Humphreys et al., 2022), the team develops a semiparametric model-based agent that can forecast future policies and values based on future behavior in a specific state. They also incorporate a retrieval mechanism that allows the model to draw on data from a sizable dataset to help inform their predictions. The authors examined this strategy in Go, a difficult game where the large combinatorial state space favors generalization over direct matching to previous experiences. Moreover, they used fast approximate nearest neighbor techniques to retrieve useful information from a dataset containing tens of millions of states used in expert demonstrations. This is a compelling demonstration of the value of large-scale retrieval in RL agents, as paying attention to it significantly improves prediction accuracy and game-play performance compared to simply using these demonstrations as training trajectories.

The AI economist (Zheng et al., 2022) introduced by Salesforce AI is a Reinforcement Learning (RL) system that outperforms Alternative Tax Systems by learning dynamic tax policies to maximize equality and productivity in simulated economies. The AI Economist significantly outperforms baselines in improving both utilitarian social welfare and the trade-off between equality and productivity in spatiotemporal economies. It does this even though new ways of avoiding taxes are coming up. It also takes into account new specialization of labor, interactions between agents, and changes in behavior. The findings prove that a two-level, deep RL approach to economics is complementary to economic theory and paves the way for an AI-based strategy to design and comprehend economic policy.

Genetic Algorithms for Smart Order Routing and Automated Trading

The research reviewed in this section focuses on genetic algorithms and machine learning techniques for automated trading, in contrast to the use of reinforcement learning for general optimization problem proposed above.

(Xu, 2015) has proposed a continuous-time, partial equilibrium model on the optimal strategies of HFTs without any learning or manipulative ingredients to rationalize the pinging activities that were observed in the data. By analyzing past message traffic, the author can reconstruct limit order books and provide a characterization of the optimal strategies employed by HFT when my model is solved using a viscosity metric. The model’s implications on pinging activities are then compared to the data. The result shows that pinging is not always a way to trick people and can be seen as a part of HFTs’ dynamic trading strategies.

(Liu, 2015) has proposed a Shortfall (IS) strategy using an agent-based simulation technique. The author focused to create an artificial stock market to analyze the optimal execution strategies. Mechanisms for order formation, market clearing, and information dissemination are also developed for that market. The methods utilized are genetic algorithms for numerical optimization.

(Xu and Carruthers,2018) have proposed the machine learning methods like Random forest regressor, gradient boosting regressor, multilayer perceptron regressor, and logistic regression for placing aggressive orders (orders intended to be filled immediately) by minimizing client transaction fees and achieving the best price from a transaction. Also, the proposed method determines the appropriate venue for an aggressive order. Moreover, to make a decision ensemble voting i.e., to combine all four ML models are employed. The data is collected from their trading systems which include level II data for all on-the-run US Treasury bonds from multiple venues in 2017.

(Kearns & Nevmyvaka, 2013) has introduced the advantages and disadvantages of a machine learning approach to HFT and market microstructure. The authors have also taken into account the issues of pure execution across time and space, as well as the challenges of forecasting profitable shifts in strategy. They also discussed ML approaches for smart order routing in dark pools and reinforcement learning for optimized trade execution. From the study, the authors concluded that the ML techniques cannot give better optimization due to their black box nature but if focused on feature engineering and fine-tuning the hyperparameters then it’s good to go for ML methods.

References

1. Sarker, I, “.Deep Cybersecurity: A Comprehensive Overview from Neural Network and Deep Learning Perspective.,” SN Computer Science. 2. 10.1007/s42979–021–00535–6. , 2021.
2. Roy, R., Raiman, J., Kant, N., Elkin, I., Kirby, R., Siu, M., … & Catanzaro, B. (2021, December). Prefixrl: Optimization of parallel prefix circuits using deep reinforcement learning. In 2021 58th ACM/IEEE Design Automation Conference (DAC) (pp. 853–858). IEEE.
3. Trofin, M., Qian, Y., Brevdo, E., Lin, Z., Choromanski, K., & Li, D. (2021). Mlgo: a machine learning guided compiler optimizations framework. arXiv preprint arXiv:2101.04808.
4. Perolat, J., de Vylder, B., Hennes, D., Tarassov, E., Strub, F., de Boer, V., … & Tuyls, K. (2022). Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning. arXiv preprint arXiv:2206.15378.
5. Humphreys, P. C., Guez, A., Tieleman, O., Sifre, L., Weber, T., & Lillicrap, T. (2022). Large-Scale Retrieval for Reinforcement Learning. arXiv preprint arXiv:2206.05314.\
6. Zheng, S., Trott, A., Srinivasa, S., Parkes, D. C., & Socher, R. (2022). The AI Economist: Taxation policy design via two-level deep multiagent reinforcement learning. Science advances, 8(18), eabk2607.
7. Xu, J. (2015, November). Optimal strategies of high frequency traders. In AFA 2015 Boston Meetings Paper.
8. Liu, C. (2015). Optimal Execution Strategies: A Computational Finance Approach (Master’s thesis, University of Waterloo).
9. Renyuan Xu, Isaac Carruthers, “Machine Learning for Limit-Order Routing in Cash Treasury”. Published on June 2018 by Quantitative Brokers.
10. Kearns, M., & Nevmyvaka, Y. (2013). Machine learning for market microstructure and high frequency trading. High Frequency Trading: New Realities for Traders, Markets, and Regulators.
11. Hindawi, Complexity, Fang Jia, Boli Yang, “Forecasting Volatility of Stock Index: Deep Learning Model with Likelihood-Based Loss Function”, 2022 https://downloads.hindawi.com/journals/complexity/2021/5511802.pdf
12. OpenAI Gym, OpenAI, “gym”, https://github.com/openai/gym, 2022

Originally posted at Deeplink Labs Publication

Contents

· Contents
· Introduction
· What Are Smart Order Routers?
· Why Do We Need Smart Order Routers?
∘ Slippage
∘ Scarce Liquidity
∘ Fragmented Liquidity
∘ Market Volatility and Price Inconsistencies
· Nuances of Smart Order Routing
∘ What is a Route in the Stock Market?
∘ What is a Route in Crypto?
· Existing Solutions
∘ Uniswap Auto Router
∘ SFOX Smart Routing and Net-Price Routing
∘ 1Inch Pathfinder
∘ Balancer Smart Order Router
· References

Introduction

This article is intended to instill the reader with a basic understanding of what smart order routing is in both the traditional finance and cryptocurrency spaces. Additionally, the ‘whys’ and ‘hows’ are explored, along with some existing standout solutions in crypto.

What Are Smart Order Routers?

The phrase ‘smart order router’ can be broken down into its constituent parts for some insight into its meaning. ‘Smart’ refers to the intelligence involved in rapid and optimal decision making, an ‘order’ is some type of instruction given with the expectation that that action will be taken, and ‘routing’ refers to setting a course aimed at reaching a final destination.

In online trading, smart order routing (SOR) is an automated process for handling orders with the intent of attaining the most desirable path across trading venues. SOR algorithms do so by following a set of rules which primarily factor liquidity into calculations intended to identify the best way of executing a given trade. In general, SORs seek liquidity.

Originating from the equities market, SOR was conceived in response to the fractured liquidity caused by the ever-increasing number of electronic trading venues and platforms. Now prevalent in all areas of electronic trading, SOR takes advantage of this fragmented liquidity by finding optimal routes for orders across venues trading a number of assets in different amounts at different prices in order to minimize losses.

Although the terms are sometimes incorrectly interchanged, SORs are not trading algorithms, SORs only consider where an order is directed, and at what price. Trading algorithms on the other hand tend to deal with the ‘what’ and ‘when’ of placing orders.

Why Do We Need Smart Order Routers?

The primary objective of SOR is to provide traders with optimal chances of price improvements and occasionally even identify opportunities in which the trader stands to profit from trade imbalances. They do so by following algorithmic procedures informed by liquidity and volatility data, automatically identifying the best orders to place across venues, given the desired swap. Some routers will be entirely automated and built into the execution of trading bots, while others will require manual input and serve more as a tool to human traders.

Slippage

To understand why SOR is a necessity in the world of electronic trading, it is important to first understand the concept of slippage. Slippage refers to the difference between the expected and actual prices of a trade, it occurs in all forms of markets and is particularly problematic in times of high volatility.

Slippage generally occurs when the bid/ask spread (the difference between the highest price a buyer is willing to pay and the lowest price a seller is willing to accept) changes between the time an order is requested and the time that the order is executed. These changes in asset price can be self-induced when placing orders of significant magnitude, as your own alteration to the supply and demand cycle can alter the price before the trade executes due to keen-eyed traders and algorithms observing your order’s placement. Slippage can also occur when there is insufficient volume at the given price point to sustain the current bid/ask spread, i.e. when there are not enough buyers and/or sellers at the given levels.

Slippage can be positive in scenarios where the expected and actual prices of an asset benefit the trader in question, yielding a profit in cases such as the bid price increasing in short trades. However, slippage is more often negative, incurring a loss in the events such as the ask price increasing in long trades. The following hypothetical example taken from Investopedia may help in understanding the mechanics of negative slippage:

• A given bid/ask price is $183.50/$183.57 on a broker interface
• A market order for 100 shares is placed, intending to be filled at $183.53
• In the time between placing the order and the order’s execution, the bid/ask spread lifts to $183.54/183.57
• This incurs a $0.04 per share or $4 total negative slippage for the 100-share trade

For a more tangible and crypto-centric example of slippage, see section 2.1 of our article on DEX aggregators.

SOR primarily aims to avoid incurring slippage losses by identifying liquidity and volatility factors across a number of sources and may also include differing order types such as limit or market orders, and more complex timed strategies such as trailing stop orders. In doing so, a SOR algorithm carves out a ‘route’ between buyer and seller, a route that may span multiple venues in order to take advantage of those venues’ liquidity depth and volatility metrics.

Scarce Liquidity

Cryptocurrency market venues often suffer from liquidity scarcity, rendering large transactions either impossible or infeasible due to the various losses incurred. This is largely due to the issue explored in the next section but is also a symptom of the relatively small market cap of cryptocurrencies relative to traditional markets.

Fragmented Liquidity

As previously mentioned, SORs both take advantage of and aim to mend the problem of fragmented liquidity, an issue facing the various cryptocurrency spaces as the number of trading venues continues to increase. Liquidity within venues is generally somewhat endemic to that ecosystem, meaning that the liquidity of one asset in that venue is separated from the liquidity of that asset in other venues. This can dramatically reduce the readily available liquidity of any given asset, unless tools are used to bridge these venues in an intelligent manner, such as via the implementation of SOR.

Market Volatility and Price Inconsistencies

Cryptocurrencies are not generally known for their stability (barring non-algorithmic stablecoin examples). Volatile assets are extremely prone to slippage, combined with inconsistent asset pricing across venues, SOR offers a lot of value in the way of both loss mitigation and in the potential for arbitrage opportunities.

Nuances of Smart Order Routing

SORs come in many forms specialized to their own ecosystems and objectives. Generally speaking, the goal is to find the best route for an order; but this can mean different things in different use cases. SORs may break orders up, spreading orders across venues, they may favor fill speed rate over fill price or vice versa. Additionally, more advanced techniques such as dark pools (private exchanges on which transactions are not made public, useful in the aforementioned cases in which your own large order would noticeably affect the market) may be leveraged in cases where extremely large orders are being placed, with the intent of minimizing immediate market reaction; or they can be configured to optimize dynamic ratio indicators such as volume-weighted average price (VWAP) or time-weighted average price (TWAP).

What is a Route in the Stock Market?

In traditional markets, an order placed through a broker will be passed on to market makers or order flow agreement partners for execution. The broker is the middleman in this arrangement and facilitates the routes through which your order can be connected with its counterpart offer/s, often through order flow arrangements with third-party liquidity providers known as market makers.

Orders placed through electronic communication networks (ECN) are able to cut out the middleman broker, routing trades directly. ECNs use order books that automatically match buyers to sellers via algorithms that are generally centered on best price execution.

What is a Route in Crypto?

In crypto, a SOR generally searches for the most efficient route to swap tokens for another token type. SOR for centralized exchanges (CEX) is comparable to the SOR techniques used in ECN, as CEXs similarly use order books, and routing consists of matching buyers to sellers across the order book in accordance with some algorithmically optimized goal.

However, in the case of decentralized exchanges (DEX), SOR deviates somewhat in functionality from its traditional market counterpart. A more comprehensive definition of DEXs can be found in this article, but they are essentially exchanges that do away with third-party authority, enabling users to exchange assets with one another without the need to forfeit custody of their assets. This is made possible by liquidity pool smart contracts, pools of (generally two types of) tokens that users can swap for one another which use conservation functions such as the XYK model in order to algorithmically price assets — these functions are often referred to as automated market makers (AMM), as they effectively fill the same role as traditional market makers by buying and selling assets to facilitate market swaps, only they do so algorithmically. In its simplest form, a user wishing to swap token A for token B will deposit token A into an A:B liquidity pool, receiving the appropriate amount of token B in return.

DEXs are however by no means impervious to the aforementioned issues of liquidity scarcity, liquidity fragmentation, and market volatility, and as such, are susceptible to slippage all the same. In fact, in many cases these factors are amplified within the current state of DEXs, as liquidity pools are many in number, fragmenting liquidity and leaving only small amounts for each pool; furthermore, liquidity issues tend to cause price fluctuations on account of the pool’s conservation functions acting to quickly rebalance the pool’s asset ratio.

Due to the nature of AMMs in DEXs, slippage due to placing large orders is often even more of an issue than in other types of venues, as the liquidity concentration of DEX liquidity pools is generally on the smaller side relative to other sources of liquidity. When swapping tokens in a DEX, you are essentially adding one asset to the liquidity pool while simultaneously removing another, the AMM conservation function then automatically rebalances the ratio of these two tokens. This means that trades in pools with small liquidity, conservation functions can overcompensate and cause dramatic price swings as the proportional ratio will be more affected — conducive to major slippage. This can be thought of analogously as the fluid displacement of a boat (an order) in a body of water (a liquidity pool); a dingy in a river will virtually have no impact on the water level, but a yacht in a pool certainly will.

With all of these factors in play, it is generally infeasible to execute large trades in DEXs without incurring large losses to slippage. To combat these effects, DEX SORs can scour across various liquidity pools in order to find swaps with the most optimal price for the user. Additionally, they may also take advantage of the liquidity depth of several pools rather than simply relying on the available liquidity of a single pool, potentially even making use of any profitable arbitrage opportunities along the way.

Existing Solutions

There are a number of existing approaches toward SOR in crypto offered by various groups, in this section, we will examine a few of them.

Uniswap Auto Router

Uniswap’s automated liquidity protocol allows users to swap one asset for another. To facilitate this, they have implemented an auto-router that makes a series of swaps across multiple pairs (the ‘route’) to attain the desired asset in the event of a trader creating an order for an asset that is not included in the pair pool they are trading through.

The route from one asset to another may consist of segments (points at which tokens are exchanged for other tokens along the way) between pairs. Though each segment will contribute to the overall cost of the trade in the form of gas fees.

In the event of a large order being placed or low liquidity in the pair pool, routes may also consist of multiple paths. By hedging routes, orders are protected against a singular point of loss to slippage. Introducing multiple paths will also increase the gas fees required to complete the trade as each path adds at least one additional transaction.

Routes can be split across up to seven routes, which enables a trader to take advantage of the liquidity depth of different pools. The following diagram depicts a scenario where a trader saves $134,689 on account of the Auto Router’s splitting function.

The Auto Router also factors gas fees into its calculations for cost efficiency — small trades will execute with minimal hops to reduce the computations which incur gas fees. This can be seen in the following example where the net cost is reduced by 10% by not making an additional trade along the route.

The Auto Router comes complete with a user interface through which a trader can view the path of their trade before execution.

In an analysis of 4,429 on-chain swaps from June 1, 2021, Uniswap claims the Auto Router improved pricing on 13.97% of all trades and 36.84% on trades between the top ten tokens by TVL.

As of mid-December, 2021, Uniswap updated its Auto Router by introducing the following improvements:

Uniswap V2 and V3 Support

The Auto Router now further improves trade prices by routing trades across all Uniswap pools, including V2 and V3 pools, while optimizing gas fees in the process — meaning that traders need not consider which version of Uniswap they are using.

Layer 2 Network Support

All Uniswap Layer 2 networks are now supported by the Auto Router, this includes Optimistic Ethereum and Arbitrum. The intent is to combine the trade pricing efficiency of the Auto Router with the low gas fees associated with Layer 2 networks.

Gas Aware Route Splitting Across V2 and V3

Trades can now be split across both V2 and V3 liquidity pools to find the best price across both, improvements brought about by the introduction of a SwapRouter smart contract. To save gas fees, old router prices are compared against new router prices, and the lower of the two is selected.

Real-Time Gas Estimates

Gas fees may now be estimated via the application’s interface, allowing traders to further gauge the profitability of a swap.

Smarter Auto Slippage

Gas estimates are incorporated into slippage calculations to automatically set slippage based on the trader’s expected gas cost and trade size. For smaller trades, slippage tolerance is adjusted to improve the odds of a trade successfully executing, in order to avoid situations where the gas fees involved with failed trades require additional transactions — and thus, higher gas fees.

In this update, Uniswap also introduced a number of developer tools:

Auto Router npm Package

The Auto Router has been packaged onto the npm registry, allowing developers to quickly and easily import it into their projects.

SwapRouter02.sol Contract

The SwapRouter contract is fully open source and can be viewed on the project’s public GitHub repository.

Swap and Add

The router contract now offers atomic swap-and-add functionality, allowing liquidity provision of only one of the assets in a pool, or any ratio of the two assets (as opposed to the traditional requirement of offering a set ratio of both assets in a pool as liquidity provision).

Oracle Slippage

Auto Router allows a limit to be set on the relative price impact of trades as measured against V3 oracles, rather than only measuring against on-chain liquidity. For example: “a user swapping ETH for USDC could specify that their swap can only execute within one percentage point of the five-minute ETH/USDC time-weighted average price”.

SFOX Smart Routing and Net-Price Routing

SFOX approaches SOR with its Smart Routing algorithm, which handles orders in such a way that aims to take the best opportunity throughout a range of different trading venues.

In 2020, SFOX improved upon its Smart Routing solution by introducing its new Net-Price Routing (NPR), which touts a supposed 28% average saving on trading fees. NPR aims to address issues relating to uneven fees in crypto, and the fact that many smart order routers calculate using the gross prices of assets. NPR finds the route to execute a trade that yields the best net price, factoring fees in.

1Inch Pathfinder

1inch’s Pathfinder API includes a price discovery and routing algorithm which they use for identifying optimal paths for token swaps across liquidity pools over a number of exchanges. In particular, it is designed to take advantage of market depth to bridge between source and destination tokens when performing swaps, while considering other factors such as gas fees.

“Thanks to improved quotes, 1inch offers, for instance, a rate for 1 sBTC-sUSD that’s better than Uniswap’s offer by almost 98%.”

Balancer Smart Order Router

Balancer’s SOR solution is an “off-chain linear optimization of routing orders across pools for best price execution”. It takes an amount of input tokens and desired tokens to trade them for, then returns a list of pools and amounts that should be traded to maximize the amount of returned tokens. The tool is available for free as an npm package for use by developers who aim to implement order routing across pools.

Balancer sees SOR as an optimization problem where the aim is to find the path through a set of Balancer Pools with the highest net yield after gas costs. The algorithm adds pools to a trading set until there are no pools left where the net gain from trading with the pool would exceed the gas cost.

The current Balancer SOR runs off-chain but is EVM-tractable by design in preparation for a future on-chain release. In order to achieve EVM-tractability, the function used to calculate the spot price of a Balancer pool has been linearized — this is also useful in adjusting for the post-trade spot price change and slippage.

We can expect the price to increase after trading due to slippage, the larger the trade, the larger the resultant change in the spot price. This linearized approximation of the spot price is exactly that, an estimate, the following diagram shows the real (non-linear) spot price after a trade compared with the linearized approximation.

As the spot prices of all Balancer Pools are linearized, Balancer interpolates prices and amounts to simplify their optimization problem. Imagine three Balancer Pools containing the token which is being traded, the estimated prices (EP) interest are defined as sets of prices under the following conditions:

1. There is a pool with exactly that initial spot price

OR

1. The spot prices of two pools ‘cross’ at that price

An Example SOR Optimization Problem

For the following walkthrough, Balancer considers only Pools 1 and 2 for their explanation.

“Let A be the amount of token in (Ai) to be traded on pool 1 such that its price increases from EP1 (initial spot price of pool 1) to EP2 (initial spot price of pool 2). The SOR’s solution for any amount of tokens lower than A is simply: “trade the entire amount with pool 1.”

When the amount traded is greater than A, SOR will start including pool 2 in the solution, as not doing so would mean the trader is trading some amount (Ai — A) for a higher price than they could with pool 2.

The solution for trading an amount B + C can be found by interpolating the trades that result in EP2 and EP3. By trading C with pool 1 and B with pool 2, both pools end at the same price (Final Price) which means that the best solution was found.”

Essentially, the algorithm predicts spot prices in pools as a function of the amount to be traded, identifies price points of interest, and aims to find swaps with pools that yield greater returns depending on the amount the trader actually trades.

References

1. “Introducing the Auto Router”, Uniswap Protocol, Sep. 16, 2021. https://uniswap.org/blog/auto-router (accessed Sep. 19, 2022).
2. “Auto Router V2”, Uniswap Protocol, Dec. 16, 2021. https://uniswap.org/blog/auto-router-v2 (accessed Sep. 19, 2022).
3. “Smart Order Router.” https://balancer.gitbook.io/balancer/smart-contracts/sor (accessed Sep. 19, 2022).
4. “Better Prices, Lower Fees: Announcing Net-Price Routing by SFOX”, SFOX, Feb. 05, 2020. https://www.sfox.com/blog/sfox-pricing-crypto-trading-net-price-routing/ (accessed Sep. 19, 2022).
5. “Introducing 1inch v2 — DeFi’s fastest and most advanced aggregation protocol”, 1inch Network, Nov. 6, 2020, https://blog.1inch.io/introducing-1inch-v2-defis-fastest-and-most-advanced-aggregation-protocol-c42573dc3f85 (accessed Sep. 19, 2022).
6. “Slippage”, Investopedia, May. 10, 2021, https://www.investopedia.com/terms/s/slippage.asp (accessed Sep. 19, 2022).
7. “Slippage”, Babypips, https://www.babypips.com/forexpedia/slippage (accessed Sep. 19, 2022).
8. “Smart Order Routing (SOR)”, Babypips, https://www.babypips.com/forexpedia/sor (accessed Sep. 19, 2022).
9. “Understanding the XYK model of pooled liquidity”, Ryan Tian, Jan. 2, 2020, https://medium.com/phoenix-finance/understanding-the-xyk-model-of-pooled-liquidity-7340fdc20d9c (accessed Sep. 19, 2022).
10. “Smart Order Routing — the Force behind a Balanced Market”, Seauake, Jul. 7, 2020, https://www.seaquake.io/blog/smart-order-routing-the-force-behind-a-balanced-market/ (accessed Sep. 19, 2022).