# 聚合器揭秘 — — 问题分析与模型建立 **Published by:** [Dr. DODO is Researching](https://paragraph.com/@dr-dodo-is-researching/) **Published on:** 2022-03-22 **URL:** https://paragraph.com/@dr-dodo-is-researching/dOlyrVLyGYNVfJdQlpym ## Content 在 DeFi 中，很重要的一点是**“如何为用户寻找最优报价”**。目前市场中有很多 DeFi 协议，不同的协议有自己独特的算法，其流动性源相对独立，使得对于相同的币种，不同的池子会有不同的报价。DEX 通过设计自己的算法、吸引 LP 以期获得更好的报价，如 1inch、0x 等聚合器则选择了另一条路：通过搜索不同池子构成的路径，在 gas 可控的情况下，为用户寻找最优的报价。 随着市场发展，1inch、0x 等聚合器也会有自己独有的报价源，balancer、uniswap V3 等 DEX 也会将用户的一笔交易拆分到多路径中完成，区别在于 DEX 的聚合算法仅基于自己的报价池，而聚合器则充分利用了 DeFi 的可组合性，不仅接入自己的池子，也会接入其他 DEX 的池子，最大化的利用全链的流动性源，以期为用户提供最好的报价。 **DODO 一直致力于为用户提供最好的交易体验，除了发展自己的 PMM 池子，DODO 也独立开发了自己的聚合算法。**DODO 的聚合算法并非 Uniswap 等 DEX 内部的拆单路由算法，而是类似 1inch、0x 一样的聚合算法。不仅会接入 DODO 自己的池子，也会接入其他 DEX 的池子，以更好地利用流动性。 这篇文章将分为两部分，本篇将先介绍聚合问题的模型建立，下篇会介绍 DODO 自己的聚合器算法并分析聚合器工程设计上的难点。 1. 建模介绍与解法分析 对一个问题进行合理的建模是解决一个问题的良好开端。首先考虑一个最简单的问题：线性路由。 1.1 线性路由 线性路由指在寻找交易路径的过程中，一交易对只经过一个池子，在此基础上寻找目标token报价最优的路径。例如用户需要交易 ETH-USDC，线性路由所找到的最优路径为 ETH-USDT-USDC，而非[A-C-B]+[A-D-B]（即A资产不会拆分为两部分选择不同的路）最终的路径只经过两个池子；这两个池子可能来自不同协议，例如，ETH-USDT 是 Uniswap V3 的池子，USDT-USDC 是 Curve V1 的池子。这种路由模型也是 Uniswap V2、Pancake 等 DEX 使用的路由模型，不同的是他们的流动性源仅为自己的交易所，即 Uniswap V2 路由只会经过 Uniswap V2 的池子，Pancake 的路由只会经过 Pancake 的池子。 图2：红色方框标明的部分即为路由路径 我们约定，用户需要卖出的 token 为 fromToken，期望买入的 token 为 toToken，对于任意池子，定义 baseToken 为卖出 token，quoteToken 为买入 token，则可以对于路由路径，第一个池子的baseToken 一定为 fromToken，最后一个池的 quoteToken 一定为 toToken。如图所示： 可以将其直接归纳为一个最值问题：设有 n 种不同资产，共有 k 种不同的池子，每个池子所交换的代币数量可以用一组函数表示： 由于所有的 3-token 或多 token 池均可用双 token 池表示，函数可进一步简写为： 其中 ai 表示第 i 种资产的数量，aj 表示第 j 种资产的数量，k 表示池子编号。设用户 fromToken 数量为 af，最终能得到的 toToken 数量 at, 中途交换的代币集为： 经过 m−1 个池子，记池子为： 则： 如能求出以上问题的解，即能求出最优路径。 该建模还是太抽象，借助图论，我们可以构建另一种模型。将币种看为节点，baseToken 为 i、quoteToken 为 j 的池子可以构建两条边，从 i 到 j 的边 ρⁱʲᵏ，从 j 到 i 的边 ρʲⁱᵏ, 边权重设为 a0 除以该池子换取的 quoteToken 数量 aj，α₀/αⱼ 则可建立以下含多重边与环的有向图，如下所示： 则可以将问题归结为，从原点 F，即 fromToken，寻找一条路径，使得到达 toToken 时，权重最小。 乍一看是一个非常简单的最短路问题，也有许多成熟的算法可供参考。但与普通的最短路问题不同的是，寻找下一条边时，下一条边的权重与节点的前序路径有关，因此，在进入队列优化路径时，节点是带状态的，必须实时维护每个节点的状态，使得后序节点所记录的路径长度与前序节点的状态匹配。且在该问题中，最后所求的“最小权重”，计算方法并不是将路径上的所有边的权重加和，而是仅计算 toToken 节点的入度权重。这个特性使得传统的最短路算法完全不适用。 当节点比较少时，比较直观的想法是直接采用 dfs 搜索，遍历每一条路径，得到最终 toToken 的价格，选取最优的一条路径为用户兑换。Uniswap V2 的 route 即采用该种方法寻找最优路径，第一版的 Uniswap V3 路由也是该方式，但与 V2 不同的是，V2 可以直接通过链下计算得到价格，V3 的价格是读合约数据计算所得，因此在 V3 的前端中，会先通过遍历找出所有的 path，再 multicall 调用 quoter 合约直接拿到计算结果。 图5：Uniswap V2 路由算法源代码 该模型不太适用于 BFS，如果按照边进行 BFS（即按照池子进行 BFS），需要同步维护该状态未选用的池子，下一步只能在未选用的池子中进行拓展，这样与dfs的复杂度没有区别，反而大大增大了记录所需的空间成本；而如果按照节点进行 BFS 拓展，则会遇到一个致命问题：因为此时节点是可以重复遍历的，不满足 BFS 条件。 同样由于有后效性，暂时没有想到在 DFS 中剪枝的规则，退而求其次的方法为对池子规模等做预处理排序，在进入 DFS 前删去一些池子，但删池子并不是全无风险的，可能对最优性造成影响。 应用 DFS 算法，一定能保证得到当前图从 fromToken 到 toToken 的最优路径，时间复杂度与层数有关，万幸的是，出于保证 gas 合理的考虑，递归层数不会超过 4，则时间复杂度为 O(l³), l 为总边数。 1.2 拆单路由 考虑复杂的问题，选取最优报价路径，又称拆单路由。寻找交易路径的过程中，一交易对可能经过不同的池子，用户的资金按最优比例配置到不同池子进行兑换，以使得目标token报价最优。同样以交易 ETH-USDC 为例，交易路径所经过的币种仍为 ETH-USDT-USDC，ETH 与 USDT 交易对可能经过两个池子，用户 30% 的 ETH 通过 Uniswap V3 兑换成 USDT，70% 的 ETH 通过 DODO V2 兑换成 USDT，进行下一交易对 USDT - USDC 兑换时，初始的 USDT 是以上两部分 USDT 所得的加和，再以此寻找 USDT-USDC 的最优拆分。 最优报价路径中可按照路径数额占比，将完整的 fromAmount 分成不同路径，或不同池子进行交易。按照划分时最小的比例单位不同，可以在原图中定义一个流网络。设 fromAmount 最大分为 n份，可建立一个超级源点，超级源点到 fromToken 节点的流量上限为n，剩余的边流量上限均为正无穷。a0 除以该池子换取的 quoteToken 数量 aj，α₀/αⱼ 作为边的费用 cⁱʲᵏ，运用如上所述的简化方法，k 池中仅包含 i，j 两种 token，可简化表示为 cʲᵏ。则问题转化为在该图中寻找最小费用最大流。 特殊的是，费用是动态的。具体而言，为了保持节点的出度和入度相等，我们可以认为在经过节点时，流不会增加或减少（均为原amount的x%），仅仅影响费用大小。因为边的费用和 baseToken 的 amount 有关，amount 又和路径有关。因此，每条边的费用 w 可定义为： 其中 cⁱʲᵏ 为，baseToken为 i，quoteToken为 j，池子编号为 k 的路径费用，是 wⁱᵏ 的函数，该函数即为池子的报价函数。u 为从 0 到 i 的路径。而 wⁱᵏ 定义为节点i中，会走k路径的流量。则有： wⁱ 为 i 的节点流量。 又因为实际影响 quoteToken 数量的因素仅为 baseToken 的数量。可以进一步将 cⁱʲᵏ 简化为： 其中 cᵢₗ 为节点 i 的入度费用，ι∈ ∑ [1,…,q]，q 为入度边数。 为了解决划分比例的问题，一种常见思路为，将可能的流量拆成 n 份，进而将 Pⁱʲᵏ 边拆成 n 份。流量等分 n 份，记为 wⁱᵏ=1,2…n， 其中要求： 其对应边 P’ⁱʲᵏ，0