针对去中心化交易所中代币路由的线图方法的扩展研究
Yu Zhang
BDLT, IfI Department, University of Zurich, Zurich, Switzerland
Claudio J. Tessone
BDLT, IfI Department, University of Zurich, Zurich, Switzerland
zhangyu@ifi.uzh.ch
--------------------------------------------------------------------------------
摘要
摘要—去中心化交易所（DEX）是去中心化金融（DeFi）生态系统的关键组成部分，每日促成价值数十亿美元的代币交易。然而，这些交易中有相当一部分是次优的，即通过其他交易路径本可以获得更多的目标代币。这种低效率凸显了从实践和学术角度研究代币路由的紧迫性和重要性。Zhang等人（2025）提出了一种针对单一DEX场景的基于线图的线性方法，该方法不仅在实际应用中具有相关性，在理论研究中也同样重要。然而，DEX中的实际交易环境要复杂得多，这要求对原始的线图方法进行扩展。本文提出了对原始线图方法的三项主要扩展。第一项扩展引入了广度优先搜索（BFS）的链接遍历规则，以降低计算复杂度和平均执行时间，同时保持该方法的盈利能力。第二项扩展引入了路径拆分，将一笔大额交易拆分为几笔等额的小额交易，以减轻价格滑点的影响。这种方法通常能为交易者带来更高的平均利润，但代价是计算复杂度的增加。第三项扩展将原方法（仅限于单一DEX）推广到更复杂的DEX聚合器场景。这三项基础扩展也为衍生出更多增强功能提供了基础。通过使用来自Uniswap V2和Sushiswap V2的真实流动性池储备数据进行实证分析，我们证明了这三项扩展在计算效率和识别更有利可图的交易路径方面均保持有效。
关键词
关键词—去中心化交易所，代币路由，线图方法，线性路由，路径拆分，深度优先搜索，广度优先搜索。
--------------------------------------------------------------------------------
1. 引言
2009年推出的比特币区块链是支持加密货币支付最成功的平台之一。继其问世之后，数百个新的区块链平台涌现，其中以太坊因其对智能合约的支持而脱颖而出。智能合约本质上是部署在区块链上的一段自执行代码。此功能使用户能够在区块链生态系统内定义自定义操作，包括创建新代币、代币交换、质押、清算、借贷以及发行稳定币等。因此，许多传统金融系统中的功能现在都可以在支持智能合约的区块链上实现。经过大约十年的发展，这一技术演进催生了去中心化金融（DeFi）领域。在DeFi中，去中心化交易所（DEX）扮演着至关重要的角色，以类似于传统外汇市场的方式促进代币交易和交换。
去中心化交易所（DEX）利用自动做市商（AMM）机制，无需中介即可促进点对点的代币交易。在DEX中，流动性提供者按比例存入代币，从而维持着大量的代币交易对——即流动性池。任何用户都可以成为流动性提供者。交易者通过与这些流动性池交互，可以将一种代币兑换为另一种，其兑换率由预定义的AMM函数自动确定，例如恒定乘积做市商（CPMM）模型。在该模型下，交易前后池中两种代币的储备量乘积保持不变。与传统的中心化外汇市场（由于流动性深度巨大，汇率基本恒定）不同，DEX会受到价格滑点的影响，这是优化交易路径中的一个关键因素。这种滑点主要源于两个因素：DEX池中相对较浅的流动性，以及AMM模型的机制（如CPMM规则），该机制内在地将价格与池中代币的储备比例联系起来。
在去中心化交易所（DEX）中，兑换给定代币对可能存在多种交易路径，这可能导致价格差异和随之而来的套利机会。尽管一些研究已经探讨了DEX内的套利机制，但这些平台的主要功能仍然是促进代币交换——即将一种代币转换为另一种。因此，设计能够识别最优交易路径的算法，对于寻求最大化回报的从业者和研究算法效率及市场行为的研究人员而言，都是一个相当重要的课题。最优交易路径被定义为用给定数量的源代币换取最大可能数量的目标代币的交易序列。为了解决这个问题，[1]提出了一种针对单一DEX场景的线图方法，专门用于解决线性路由问题。线性路由指通过一系列连续的流动性池进行代币交换的过程，其中每笔交易都在单一路径上紧随前一笔交易。然而，该方法仅限于单一DEX，且未考虑路径拆分或DEX聚合器等复杂场景。本文旨在通过提出三项具体扩展来增强原始线图方法的实际适用性：(1) 引入广度优先搜索（BFS）遍历规则以提升计算效率；(2) 开发路径拆分算法以缓解价格滑点；(3) 将该方法泛化至DEX聚合器环境。
本文的其余部分安排如下：第二节回顾了去中心化交易所（DEX）中代币路由的相关工作。第三节描述了本研究中使用的数据并回顾了基础方法。第四节介绍了我们提出的方法扩展并报告了相应的实验结果。最后，第五节对本文进行总结。
2. 相关工作
理解现有的代币路由算法格局具有重要的战略意义，因为这为本文的贡献提供了背景。本节将对当前方法进行批判性回顾，以明确本研究的定位。
一些研究已经探讨了去中心化交易所（DEX）中的代币路由问题。[2] 提出了一个基于凸优化的框架，用于解决DEX中的套利和交易路由问题。在此基础上，[3] 系统地开发了一种基于优化的方法来解决套利最大化问题，该方法也可以扩展到Uniswap V2等平台中的交易路由场景。最近，[4] 将[3]中提出的基于凸优化的路由方法扩展至Uniswap V4，以适应其诸如“钩子”（hooks）等新功能。然而，正如[1]所指出的，基于凸优化的路由方法计算复杂度高。此外，其产生的代币路由路径在现实世界应用中通常不切实际。这主要是因为，如其工作附录中的实验所示，最优路径往往涉及几乎所有可用的流动性池，这使得在实时交易环境中实施变得不可行。
在实践中，Uniswap等去中心化交易所主要采用深度优先搜索（DFS）算法来识别代币路由路径。尽管DFS算法的特点是计算复杂度低，但其产生的路由路径的盈利能力通常有限，这一点已由[1]指出。为了解决现有代币路由算法的各自优势与局限，[1] 提出了基于线图的路由方法。该方法实现了比DFS更高的盈利水平，但仍低于基于凸优化的方法。在计算复杂度方面，它处于一个中间地带——低于基于凸优化的方法，但高于DFS。
这一分析凸显了线图方法是在计算效率和盈利能力之间的一种权衡，平衡了DFS和基于凸优化方法的两个极端。因此，对这种平衡的方法进行扩展是一项有价值的研究工作。在详细介绍这些扩展之前，有必要先描述本研究使用的数据并回顾其所基于的基础方法。
3. 数据与方法回顾
本节将为后续的分析奠定基础，首先描述所使用的实证数据，然后简要回顾作为后续扩展基础的原始线图路由方法。
3.1 数据描述
本研究使用了来自Uniswap V2和Sushiswap V2的流动性池储备数据。Sushiswap V2在代币交易中采用了与Uniswap V2相同的AMM函数。基于DEX中的流动性池，我们构建了一个代币图，其中节点代表单个代币，边对应于包含其端点相应代币的流动性池。在对线图方法的每项扩展进行的实验评估中，所生成的图大约包含一百个代币和四百条有向边。
3.2 线图路由方法回顾
本节我们简要回顾[1]中在单一DEX情况下开发的基于线图的线性路由方法。其核心逻辑可以概括为以下步骤：
1. 构建有向代币图 G(V,E,R)：利用代币的流动性池数据构建有向代币图G。其中V是代币集合，E是代币流动性池集合，R是流动性池的代币储备集合。每条有向边 (vi, vj) 表示一个单向流动性池，意味着用户只能将 vi 交易为 vj，反之则不行。
2. 构建线图 L(G)：基于代币图G构建其线图L(G)。在L(G)中，G的每条有向边都成为一个新的顶点。例如，G中的有向边 (vi, vj) 成为L(G)中的顶点 (vi, vj)，并存储相应的流动性储备信息。当一个顶点的最后一个代币恰好是另一个顶点的第一个代币时，它们之间便形成有向链接。例如，顶点 (vi, vj) 可以连接到顶点 (vj, vl)。
3. 迭代算法：算法从一个代表源代币的起始顶点开始。它以迭代方式遍历L(G)中的链接。在[1]的原始方法中，每个链接是随机选择进行迭代的。在每次迭代中，算法计算给定输入所能获得的最大目标代币数量。如果在某个顶点的迭代中发现了一条更有利可图的路径，算法就会更新该顶点的交易路径和目标代币数量。
4. 停止条件：当L(G)中所有顶点的目标代币数量不再增加时，迭代过程停止。
[1]的研究发现，与Uniswap V2使用的深度优先搜索（DFS）方法相比，这种线图方法能让用户获得更多的目标代币，且两种方法的交易路径长度相当。下一节将详细介绍我们对这一基础方法的新扩展。
4. 线图方法的扩展与实证分析
尽管原始的线图方法提供了一个坚实的基础，但其实用性受到一定限制。本节将详细介绍三项独特的扩展，旨在解决其在计算效率、价格滑点和跨多个DEX适用性方面的局限性。
4.1 扩展一：用于提升计算效率的广度优先搜索（BFS）遍历规则
原始方法中的随机链接选择可能效率低下，因为它可能会遍历输入代币数量为零的链接，从而导致计算资源的浪费。为了解决这个问题，我们提出了广度优先搜索（BFS）链接遍历规则。该规则定义了一种特定的、非随机的链接遍历顺序，以确保每次迭代都是“有效的”，即交易的输入代币数量非零。
算法 1：BFS链接遍历顺序算法
问题设定: 返回线图 L(G) 的链接遍历顺序。 输入: 源代币 src，线图 L(G) 输出: edgeorder，链接遍历顺序列表。
函数 生成BF遍历顺序(src, L(G)):
queue ← [src] // 初始化队列，从源代币src开始
edgeorder ← [] // 初始化链接顺序列表
当 L(G) 中仍有边时:
对于 queue 中的每个元素 q:
neigh ← 获取 q 在 L(G) 中的邻居
如果 neigh 不为空:
对于 neigh 中的每个邻居 n:
如果 边 (q, n) 不在 edgeorder 中:
将 (q, n) 添加到 edgeorder
从 L(G) 中移除边 (q, n)
结束 如果
结束 对于
结束 如果
结束 对于
结束 当
返回 edgeorder
为了评估这一扩展的效果，我们进行了实证分析。
* 效率分析：图1显示，与原始方法相比，BFS规则显著减少了链接迭代的轮数。例如，在一个包含约一百个代币的图中，平均迭代轮数从17轮减少到11轮，这极大地提升了计算效率。
* 性能分析：图2展示了平均运行时间的减少。代表BFS方法的红线始终位于代表原始方法的蓝线之下。拟合结果显示，计算复杂度是图规模的多项式函数。
* 复杂度来源：这种多项式复杂度的根源在于，如图3所示，线图中的链接数量随原始代币图中代币数量的增加而呈多项式增长。
* 盈利能力分析：图4的结果表明，BFS扩展不仅提高了效率，还保持甚至略微增强了盈利能力。
综上所述，BFS遍历规则在不牺牲盈利能力的前提下，显著优化了算法的计算性能。接下来，我们将探讨旨在解决价格滑点问题的第二项扩展。
4.2 扩展二：用于缓解价格滑点的路径拆分算法
DEX中使用的CPMM模型导致交易规模越大，价格滑点越严重。原始的线性路由方法并未考虑这一点。为解决此问题，我们提出了路径拆分算法。该策略是将一笔大额交易拆分为多笔等额的小额交易，并按顺序执行。每完成一笔小额交易后，相关流动性池的储备金信息会得到更新，然后为下一笔小额交易重新计算最优路径。
算法 2：单一DEX中的路径拆分算法
问题设定: 在单一DEX中，用 ϵ1 单位的源代币 v1 购买最大数量的目标代币 vN。 输入: 线图 L(G)，ϵ1 单位的源代币 v1 输出: 最大数量的目标代币 vn，路径集合 P。
函数 路径拆分(L(G), ϵ1, v1):
K ← 拆分数量
vn ← 0
P ← 空的路径集合
对于 k 从 1 到 K:
// 使用原始线图方法计算当前子交易的最优路径
(T, TP) ← 调用基于线图的方法([1])，输入为 (ϵ1/K)
vn ← vn + T
将 TP 添加到 P
根据 TP 更新相关流动性池的储备金
结束 对于
对 P 进行重排序以使其成为可执行路径
返回 vn, P
显而易见，该方法会增加计算复杂度，其增长与拆分次数呈线性关系。然而，这种计算成本的增加带来了显著的收益。图5的实证结果量化了盈利能力的提升。例如，对于一笔10,000美元的输入，使用2023年的数据，在约20%的情况下，交易者的利润可以增加超过20%。这证明了路径拆分在缓解价格滑点和提高交易回报方面的有效性。接下来，我们将讨论最后一项扩展，它将我们的方法从单一DEX环境推广到更广泛的DEX聚合器场景。
4.3 扩展三：针对DEX聚合器的泛化算法
原始方法及其前两项扩展都局限于单一DEX，而现实世界的交易常常通过DEX聚合器跨多个平台进行。为了解决这一局限，我们将线图方法扩展到了多DEX环境。关键步骤是构建一个**“集成”线图**，该图保留了不同DEX（例如DEX1和DEX2）上给定代币对的所有可用流动性池。构建此集成图的过程包括三个步骤：
1. 为每个DEX构建其各自的代币图和流动性池，并用上标区分来源。
2. 为每个DEX的代币图构建相应的线图。
3. 通过在不同DEX的线图顶点之间建立新的链接，将它们整合成一个更大的线图。
这种集成方法不可避免地会增加计算复杂度。集成线图包含更多的链接（数量约为 n² · EL(G)，其中 n 是DEX的数量），因此比单一DEX场景需要更高的计算资源。
* 性能对比（vs. 单一DEX）：图6显示，DEX聚合器设置下的平均运行时间更高。然而，图7表明这种权衡是值得的，因为聚合器场景下的盈利能力“高得多”，这是由于可用的交易路径更多。
* 性能对比（vs. DFS）：图8证明，即使在更复杂的聚合器环境中，线图方法仍然显著优于标准的DFS算法。对于10,000美元的输入，在约60%的情况下，其表现可以比DFS好约5倍。
* 集成BFS规则：图9的结果显示，第一项扩展中的BFS规则同样适用于此。在聚合器设置中使用BFS遍历规则，其盈利能力高于在单一DEX中使用原始随机遍历方法。
这项泛化扩展极大地提升了线图方法的实际应用价值，使其能够在一个更真实、更复杂的交易环境中发现高利润的交易机会。
5. 结论
本文的核心目标是扩展[1]中提出的线图路由方法，以增强其在复杂交易环境中的实用性。我们重点研究了三项关键扩展：引入BFS链接遍历规则、开发路径拆分算法以及将其泛化至DEX聚合器场景。
我们的实证分析得出了以下关键结论：
* BFS遍历规则显著提升了计算效率，同时没有牺牲盈利能力。
* 路径拆分算法通过有效缓解价格滑点，大幅提高了交易的最终盈利。
* DEX聚合器泛化使得该方法能够发掘比单一DEX路由高得多的利润，因为它利用了更广泛的流动性来源。
在代币路由算法的整体格局中，线图方法及其扩展占据了一个战略性的中间地带。它在计算效率上优于复杂的凸优化方法，而在盈利能力上则远胜于简单的DFS算法，从而实现了一种有效的平衡。
在去中心化交易所中，高效的代币路由对交易者至关重要，直接影响其交易结果和盈利能力。因此，这一课题值得进一步深入研究。未来的工作方向可以包括在DEX聚合器环境中应用路径拆分算法，如附录中所述。
参考文献
[1] Y. Zhang, Y. Li, and C. Tessone, “A line graph-based framework for identifying optimal routing paths in decentralized exchanges,” arXiv preprint arXiv:2504.15809, 2025.
[2] V. Danos, H. E. Khalloufi, and J. Prat, “Global order routing on exchange networks,” in Financial Cryptography and Data Security. FC 2021 International Workshops: CoDecFin, DeFi, VOTING, and WTSC, Virtual Event, March 5, 2021, Revised Selected Papers 25. Springer, 2021, pp. 207–226.
[3] G. Angeris, A. Evans, T. Chitra, and S. Boyd, “Optimal routing for constant function market makers,” in Proceedings of the 23rd ACM Conference on Economics and Computation, 2022, pp. 115–128.
[4] T. Chitra, K. Kulkarni, and K. Srinivasan, “Optimal routing in the presence of hooks: Three case studies,” arXiv preprint arXiv:2502.02059, 2025.
[5] Y. Zhang, T. Yan, J. Lin, B. Kraner, and C. J. Tessone, “An improved algorithm to identify more arbitrage opportunities on decentralized ex-changes,” in 2024 IEEE International Conference on Blockchain and Cryptocurrency (ICBC). IEEE, 2024, pp. 1–7.
附录
A. DEX聚合器中的路径拆分算法
算法 3：DEX聚合器中的路径拆分算法
问题设定: 在DEX聚合器中，用 ϵ1 单位的源代币 v1 购买最大数量的目标代币 vN。 输入: ϵ1 单位的源代币 v1 输出: 最大数量的目标代币 vn，路径集合 P。
函数 聚合器路径拆分(ϵ1, v1):
K ← 拆分数量
vn ← 0
P ← 空的路径集合
对于 k 从 1 到 K:
// 在聚合器环境中使用线图方法计算当前子交易的最优路径
(T, TP) ← 调用基于线图的聚合器方法，输入为 (ϵ1/K)
vn ← vn + T
将 TP 添加到 P
根据 TP 更新相关代币图中的储备金信息
结束 对于
对 P 进行重排序以使其成为可执行路径
返回 vn, P
