This paper constructs a flexible and horizontally scalable routing system architecture through data modeling, which includes the cache for the most frequently requested routing and the cache pair data for calculating the impact of routing requests.
Original title: “Building Blocks for DEX Router Construction and Analysis”
Written by: Alex Carreira and Prabhaav Bhardwaj
The exchange of one asset for another is a basic concept in the financial market. In the cryptocurrency market, this situation usually occurs where tokens or currencies are exchanged or traded with others. Uniswap is an automatic liquidity agreement that facilitates this type of exchange. It uses pairs or pools (hereinafter referred to as pairs), a pool reserve of two assets, allowing users to exchange one asset for another.
Figure 1.0: Uniswap token A and B pools, and examples of swaps and deposit interactions between liquidity providers (LP) and traders. LP receives pool tokens to provide liquidity
What happens if the asset someone wants is not paired with the asset they want to trade? In this case, a series of swaps are made between multiple pairs to obtain the required asset-to facilitate this The pair of transactions is called a route.
Figure 2.0: A route involving multiple pairs of transactions DAI in exchange for USDC
A route is a route from one asset to another and consists of zero or more segments between pairs. If the number of transactions is large enough, or if the liquidity of a pair is low enough, a route can be formed from multiple routes to reduce slippage by absorbing more liquidity from other pairs.
Figure 3.0: Multipath routing illustrated by Paraswap router
Figure 4.0: Multiple routing
Slippage refers to the difference between the price that a person expects to pay for an asset and the amount actually paid, which is caused by factors such as price changes between the entry of an order into the market and the execution of a transaction, or low trading volume and liquidity .
Another thing to consider is the number of segments in the route. This will increase transaction costs in the form of gas fees for operations on the Ethereum blockchain. The more segments on a route, the higher the gas cost. Similarly, if there are multiple ways, as shown in Figure 3 and Figure 4 above, the gas cost will be higher.
The router must consider these factors to generate a route suitable for the number of transactions. In addition, because market conditions often change, affecting gas costs and pool liquidity, the generated route will also be dynamic. It is a good route now, and may not perform well in one hour or the next day.
The rest of this article will discuss the building blocks that can be used to build and analyze the Uniswap V2 protocol and later to build and analyze routers.
Data modeling
Note: The Graph protocol mentioned here is different from the Graph data type discussed in the next section. The graph protocol is an index of blockchain transactions of one or more smart contracts, and the graph data type refers to the data representation using mathematical graph theory.
Just as you use a map to navigate between points, you can use the graph data type to navigate the available liquidity pairs to generate routes that can be evaluated to improve returns. When modeling the Uniswap pair, some implementation choices need to be made from the beginning:
- Pairs, symbols or asset identifiers as vertices or edges?
- 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 the following data pairs 2 tokens: symbol, name, ID.
The token symbol is not unique-for example, the symbol BOND represents many different assets or different IDs.
The token name is not necessarily unique.
The token ID is unique and is the ERC-20 contract address of the token.
Uniswap recommends using token ID as the vertex in the graph data type for these attributes. 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, and each edge represents a pair of IDs, token prices, and reserves. However, the need to constantly update token prices and retain information indicates that storing this data in a cache structure with appropriate real-time settings may be more effective and scalable, especially for real-time trading applications, rather than static analysis.
In the future, routing between Uniswap V2 and V3 protocol pairs is desirable. In this scenario, there may be multiple pairs of the same token ID. Although it is possible to add additional edges between a pair of IDs, another solution is to group different pair IDs on the same edge to avoid the performance cost of traversing multiple graphs. The following is a partial example of the undirected simple graph structure of group-to-ID, where the symbol ID replaces the symbol name:
Figure 5.0: Modeling the Uniswap V2 and V3 protocol pair in an undirected simple graph (note that the actual structure uses token ID instead of token symbol, so it will be very troublesome here)
Initially, Depth First Search (DFS) has proven to be able to traverse the graph, and the depth is generally limited to 4. An exception to this depth is the route starting from WETH, where the number of connected nodes exceeds 30,000. When a route departs from WETH, DFS is limited to 2 to reduce the traversal time.
There are many tools for processing graph data types, including graph databases Neo4J and RedisGraph. These discussions are beyond the scope of this article. The current project requirements can be met by the Javascript library Graphlib. However, if the scale of the routing problem reaches the scale of LinkedIn or other large-scale networks, then the scale of the above-mentioned graph database will meet these needs, thereby weighing cost and development complexity.
constraint
Constraints are useful when calculating routes in graph data structures. For example, they can help determine routes that only traverse a limited number of pairs, or can be used to ignore routes that contain certain assets.
The existing Uniswap V2 routing is mainly routing through six assets, which can be compared to an airport hub. The six assets are:
WETH
DAI
USDC
USDT
COMP
MKR
These six assets are useful because they are commonly used. When they are paired with other assets, they do not impose liquidity restrictions (that is, they are not scarce and will not be combined with new, unproven crypto assets). Constitute the same risk). However, their use may cause efficiency problems, as explained here:
“Uniswap does not route exchanges in a decentralized way.”
Using constraints, such as ignoring the 6 “hub” assets mentioned above, can explore more effective potential routes than the current Uniswap V2 interface provides users. Constraints can also be extended to other standards, such as:
It is also worth noting that constraints are combinable, that is, they can be combined together so that routing can be limited to a maximum of 2 pools, each with a liquidity exceeding X. The current data model splits the data between the graph data type and the lookup table, which means that routes can be trimmed during and after graph traversal when data is found.
Expand
The expansion mainly considers exposing a public API to the router to calculate routes based on current market data. Performance is a function:
The following figure illustrates an initial system architecture, which contains the cache used for the most frequently requested routing and the cache pair data used to calculate the impact of routing requests. This architecture is very flexible and can be scaled horizontally in a variety of ways. For example, fully copy the graph data structure and routing cache, as well as the request aggregator and pair cache, or simply copy the cache and distribute routing requests among the caches.
Figure 6.0: A routing service architecture with extensible components, caching, and periodic updates.
Another potential scalability modification may be a complete routing solution cache that considers routing requests and quantity; if the quantity is within a certain tolerance, the most recently calculated result can be reused. According to user experience and application needs, the most recently calculated result can also be used as a temporary result to calculate a more accurate result for the user.
Route cache
The route cache is composed of the results of the most frequently requested routes, and its time-to-live (TTL) is related to the periodic update frequency of the data source. For example, if you have previously requested a route between WETH and DAI, you can find the result of the graph traversal in the route cache in the form of an array of possible routes: [WETH -> USDC -> DAI, WETH -> WBTC -> DAI, …]. Unlike pair data such as token prices and reserves, routing possibilities—especially the existence of a pair—change less, so the TTL of the cache is expected to be much larger than that of the data cache. In addition, this component can also be extended to include heuristics for dead routing (ie expired or replaced token addresses or non-current pairs).
Paired data cache
The paired data cache contains specific pairs of token prices and reserved data, making it easy to calculate the impact of using a specified number of routing requests. This data changes more frequently than the available routing options, and will have a TTL of approximately one Ethereum block (approximately 15 seconds).
When the requested data is not in the cache, these requests will be bundled together and obtained from the data source. Currently, it is a Uniswap subgraph in the Graph protocol (see the data source section below), which can contain up to 1000 pairs of data queries. The waiting time before sending the bundled data request will be adjusted according to the traffic-in a low-traffic scenario, it makes no sense for the user to wait until an additional request is made.
In addition, in order to improve user experience, when obtaining and calculating updated data, pre-results based on old data may be presented.
Static analysis
The routing performance will be evaluated by comparing the generated routes with the routes of existing Uniswap V2 routers. Specifically, by calculating the revenue of a given number of source tokens. For example, in a transaction from DAI to COMP, the performance of the router will be compared by calculating how much COMP has been received from 1 million DAI tokens and checking the same result obtained from the route suggested by the Uniswap V2 router. Performance will be measured based on a variety of different inputs, such as different initial numbers, different limits on search depth, etc.
When performing static analysis, the data caching and bundling request shown in Figure 6.0 is not required. Static analysis is the calculation of transactions within a specific block time of the blockchain. It contributes to the consistency and reproducibility of the results for comparison. The initial working range of the new router designed for Uniswap V2 is assisted by static analysis, in which a set of transactions can be evaluated at a block time and compared with existing routing algorithms or variants. If the underlying matching data changes, it is not clear whether the improvement or decline in trading results is due to a change in algorithm or matching liquidity and pricing.
data source
As the blockchain technology matures, a large number of services that provide current and historical data of the blockchain have emerged. The choice of data source involves the following considerations:
budget
Development work and cost
Delay
Accuracy of data
Development effort and costs can be reduced by using pre-digested or indexed data, as found in the many subgraphs of Graph Protocol.
For the design and implementation of the initial switching router, the Uniswap subgraph in Graph Protocol will be used. This data source provides excellent ease of use, can analyze past contract data, which would otherwise require more expensive archiving Ethereum nodes, and can update 1000 pairs of data in a single HTTP request without performing static analysis. The data latency in Graph Protocol is much lower than the previously mentioned solutions, and it can only win by directly running the Ethereum node or modeling the memory pool (or using services such as Blocknative). The latency of Graph Protocol is obviously around 1 block, which can be dynamically changed in some indexing scenarios. It is worth noting that when the index and mapping block prove to be invalid, the data can also be changed.
Once the switch router design is evaluated, this data source will prove to be unsuitable for generating routes, 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
The system outlined above provides flexibility and scalability to analyze the performance of the existing Uniswap system and build a new system on top of the protocol, including a mature trading solution. Similar to Coinbase vs Coinbase Pro or Synthetix vs Kwenta, there are also some advanced features that are essential to professional traders, we have listed some below.
Transaction generator
By avoiding the constraints of the above 6 hub tokens, the system described in this article can be used to check alternative routes 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 for these pairs or allow them to make other changes.
Cross-protocol routing
By adding graphics or alternately making the graphics data structure into multiple graphics and adding additional data sources, the system can be expanded to provide users with routing between assets across Uniswap V2 and V3 protocols. Depending on the goal, this can reduce slippage in transactions and can also manage decentralized liquidity.
Cross-layer routing
Similar to cross-protocol, routers can be extended to generate cross-layer routes. The promise of lower gas costs and improved transaction bandwidth shows that the layer2 solution will help define a large part of Ethereum’s future. The crossover between L2 and L1 assets presents a new routing challenge whose complexity exceeds protocol crossover. However, the same basic building blocks can generate solutions that allow cross-layer transactions, using upcoming protocols to achieve this goal, such as Hop Protocol, Nova, etc.
MEV
By combining routing solutions with technologies that prevent MEV, such as Flashbots, the routing system can be used to protect large transactions from attacks. Heuristics or other inputs can determine whether the value of a transaction is sufficient to represent this risk, and then the protective solution can be automatically incorporated into the transaction solution proposed by the determined optimal route.
Low-latency data sources and predictive routing
Although Graph Protocol data sources are convenient and fast, they usually have at least 1 block delay. For some trading applications, this may not be enough. In this regard, it can replace other data sources with better performance, either directly bind to an Ethereum node, or filter completed transactions of interest to update the data structure of the routing system. Furthermore, a limited description of the memory pool can be constructed, and similar transaction filtering can be applied to provide predicted routing results in known transaction states that have not been executed.
Source link: medium.com
