Using Uniswap as an example, discuss the building blocks used for DEX router construction and analysis
overview
overview
The exchange of one asset for another is a fundamental concept in financial markets. In the cryptocurrency market, this usually happens where tokens or currencies are exchanged or traded with others. Uniswap is an automated liquidity protocol that facilitates this type of exchange. It uses pairs or pools (hereafter referred to as pairs), pool reserves of two assets, allowing users to exchange one asset for another.
Figure 1.0: Uniswap token A and B pools, and examples of swap and deposit interactions for liquidity providers (LPs) and traders. LPs receive pool tokens to provide liquidity.
What happens if the asset someone wants doesn't pair with the asset they want to trade? In this case, a series of swaps between multiple pairs to get the desired asset - used to facilitate this The pairs of transactions are called routes.
Figure 2.0: A route involving multiple pairs trading DAI in exchange for USDC.
image description
Figure 3.0: Multipath routing illustrated by Paraswap routers
image description
Figure 4.0: Multiple Routing
Slippage is the difference between the price one expects to pay for an asset and the amount actually paid, caused by factors such as price movements between when an order enters the market and when the trade is executed, or by low volume and liquidity .
Routers must take these factors into account to generate routes appropriate for the number of transactions. Also, as market conditions change frequently, affecting gas fees and pool liquidity, the resulting routes will also be dynamic, a route that is good now may not necessarily perform well an hour later or the next day.
The remainder of this article discusses the building blocks that can be used to build and analyze routers for the Uniswap V2 protocol and beyond.
first level title
data modeling
Note: The Graph protocol mentioned here is different from the Graph data type discussed in the next section. A graph protocol is an index of blockchain transactions for one or more smart contracts, while a graph data type refers to a data representation using mathematical graph theory.
Just as a map is used to navigate between points, a graph data type can be used to navigate available liquidity pairs to generate routes that can be evaluated to improve returns. When modeling a Uniswap pair, there are some implementation choices to make at the outset:
A pair, symbol, or asset identifier as a vertex or edge ?
Directed or Undirected?
Simple or multi-picture?
In order to make the above implementation choices, it is important to understand the properties of Uniswap pairs:
Each pair has a unique ID.
Each pair contains 2 tokens for the following data pairs: symbol, name, ID.
Token symbols are not unique - for example, the symbol BOND represents many different assets or different IDs.
Token names don't have to be unique either.
These properties of the Uniswap pair suggest using token IDs as vertices in the graph data type. It can be seen that the edges of the graph represent a unique pair of IDs. In this form, the graph can be undirected or directed, with each edge representing a pair of ID, token price, and reserve. However, the need to constantly update token prices and reserve information suggests that storing this data in a cache structure with appropriate real-time settings may be more efficient and scalable, especially for applications with real-time transactions, rather than static analysis.
Going forward, routing between Uniswap V2 and V3 protocol pairs is desirable. In this scenario, there may be multiple pairs of the same token ID. While it is possible to add an extra edge between a pair of IDs, another solution would be to group different pair IDs on the same edge, thus avoiding the performance cost of traversing the multigraph. Here is a partial example of the structure of a simple undirected graph of grouped pair IDs, where symbol IDs replace symbol names:
image description
Figure 5.0: Modeling a Uniswap V2 and V3 protocol pair in a simple undirected graph (note that the actual structure uses token IDs rather than token symbols, so it will be messy here).
Initially, depth-first search (DFS) has been shown to traverse graphs, generally with a depth limit of 4. An exception to this depth is the route from WETH where the number of connected nodes exceeds 30000. When a route departs from WETH, DFS is limited to 2 to reduce traversal time.
There are many tools for working with graph data types, including graph databases Neo4J and RedisGraph. These discussions are beyond the scope of this article, and the current project requirements can be met by the Javascript library Graphlib. However, if the routing problem scales to the scale of LinkedIn or other large networks, then the scale of the graph database described above meets these needs, trading off cost and development complexity.
constraint
WETH
DAI
USDC
USDT
COMP
MKR
Constraints are useful when computing routes in graph data structures. For example, they help identify routes that only traverse a limited number of pairs, or can be used to ignore pairs that contain certain assets.
Existing Uniswap V2 routing is primarily routing through six assets that can be compared to airport hubs. These six assets are:
These six assets are useful because they are commonly used, do not impose liquidity constraints when paired with other assets (i.e. they are not scarce, and do not compete with new, unproven cryptoassets pose the same risk). However, their use may pose efficiency problems, illustrated here:
"Uniswap does not route exchanges in a decentralized manner."
Using constraints, such as ignoring the 6 "pivot" assets mentioned above, can explore more efficient potential routing than the current Uniswap V2 interface provides to users. Constraints can also be extended to other criteria such as:
It is also worth noting that constraints are composable, that is, they can be combined so that routing can be limited to at most 2 pools with more than X liquidity each. The current data model splits data between graph data types and lookup tables, which means routing can be pruned when pair data is discovered both during graph traversal and afterward.
expand
first level title
expand
The extension mainly considers exposing a public API to the router in order to calculate routes based on current market data. Performance is a function of:
time to calculate route
The time required to calculate the impact of routing requests
The diagram below illustrates an initial system architecture with caches for most frequently requested routes and cache-pair data used to calculate the impact of routed requests. This architecture is very flexible and can be scaled horizontally in many ways. For example, fully duplicating the graph data structure and routing cache and the request aggregator and pair cache, or simply duplicating the caches and distributing routing requests between the caches.
Figure 6.0: Routing service architecture with scalable components, caching, and periodic updates.
Another potential scalability modification could be a full routing solution cache that takes into account routing requests and quantities; recently computed results can be reused if the quantity is within a certain tolerance. Depending on the user experience and the needs of the application, the most recently calculated result can also be used as an interim result while a more precise result is calculated for the user.
routing cache
The route cache consists of the results of the most frequently requested routes, with a time-to-live (TTL) related to the regular update frequency of the data source. For example, if a route between WETH and DAI was previously requested, the result of the graph traversal can be found in the route cache as an array of possible routes: [WETH -> USDC -> DAI, WETH -> WBTC -> DAI, ...]. Unlike pair data such as token prices and reserves, routing probabilities—especially the existence of pairs—change less, so the TTL for this cache is expected to be much larger than for the pair data cache. Additionally, the component can be extended to include heuristics for dead routes (i.e. expired or superseded token addresses or illiquid pairs).
first level title
paired data cache
Also, to improve user experience, pre-results based on old data may be presented when fetching and calculating updated data.
static analysis
first level title
When performing static analysis, there is no need for caching and bundling requests for data as shown in Figure 6.0. Static analysis is the calculation of transactions at a specific block time of the blockchain. It facilitates consistency and reproducibility of results for comparison. The initial scope of work to design a new router for Uniswap V2 was aided by static analysis, where a set of transactions can be evaluated at one block time and compared to existing routing algorithms or variants. If the underlying pair data changes, it is not clear whether the improvement or decline in trading results is due to algorithmic changes or pair liquidity and pricing.
data source
first level title
data source
Budget
Delay
Development effort and costs
Delay
data accuracy
Once the switch router design has been evaluated, this data source will prove unsuitable for route generation because real-time data needs to be competitive. In such scenarios, data directly from the current state of the blockchain is required, such as Ethereum nodes from Alchemy, Infura, or other sources.
future
future
The system outlined above provides the flexibility and scalability to analyze the performance of existing Uniswap systems, as well as build new systems on top of the protocol, including a full-fledged trading solution. Similar to Coinbase vs Coinbase Pro or Synthetix vs Kwenta, there are also some advanced features that are essential for professional traders, we have listed some below.
transaction generator
By using the constraint of avoiding the above 6 hub tokens, the system described in this paper can be used to examine alternative routing between certain tokens and their efficiency. This can be done periodically to build a heuristic-based list that existing systems/traders can use to improve the recommended routing of these pairs, or allow them to make other changes.
Cross-protocol routing
By adding graphs or alternately making the graph data structure a multigraph and adding additional data sources, the system can be extended to provide users with routing between assets across Uniswap V2 and V3 protocols. Depending on the goal, this can reduce slippage in transactions or manage decentralized liquidity.
cross layer routing
MEV
first level title
By combining routing solutions with MEV-proof technologies, such as Flashbots, this routing system can be used to protect large transactions from attacks. Heuristics or other inputs can determine whether a transaction is worth enough to represent such risk, and protective solutions can then be automatically incorporated into the transaction solutions proposed by the determined optimal route.
Low Latency Data Sourcing and Predictive Routing
Source：https://medium.com/@ValveFinance/building-blocks-for-dex-router-construction-analysis-acc03b9f15d8
This article comes from the decentralized financial community and is reproduced with authorization.
