← 返回 PaperDaily
大模型与智能体
西北大学联手Chaincode Labs，搞定比特币交易最优排序
比特币矿工每天面对海量待确认交易，怎样在依赖关系和费用之间找到最优排序？这不仅仅是性能优化，更关系到区块网络的去中心化。西北大学与Chaincode Labs共同提出SFL（生成树线性化）算法，将经典的数学规划思路落地成可直接在交易依赖图上迭代合并分裂的高效操作。在真实mempool数据上，SFL比传统GGT参数化流方法快2-3倍，且具备了“随时可中断”的a
龙哥读论文
发布于 2026-09-05 00:31:11
阅读 4
查看原文
原论文信息如下：
一、比特币交易排序的数学本质
在比特币的世界里，矿工们每天都在做一道极其烧脑的数学题：面对内存池（mempool）中成百上千笔待确认交易，每一笔都有不同的依赖关系、大小（即权重 weight）和手续费（fee），究竟按照什么顺序打包进区块才能让自己赚得最多？这听起来像是一个简单的排序问题，但实际上，它是运筹学中一个经典的NP难问题。
先看一个简单的例子：假如交易A是交易B的父交易（即B需要花费A的输出），那么B就不能在A之前被打包。这种依赖关系构成了一个有向无环图（DAG, Directed Acyclic Graph）。每笔交易都有其费用率（fee rate），就是手续费除以大小。直观上，矿工当然希望先打包费用率高的交易，但依赖关系往往不允许这么做。比如一个费用率很高的子交易，必须先打包一个费用率很低的父交易，这就拉低了整体收益。
论文将这个问题形式化为 Mempool Linearization Chunk
这里有一个非常关键的数学定义：Closure
这个问题的抽象模型，对应运筹学中的经典问题——单机非抢占式调度问题 (1|prec|ΣwjCj)
为了量化线性化的优劣，论文还引入了一个非常优雅的指标：累计手续费-大小曲线下的面积（AUC, Area Under the Curve）
为了更直观地理解，论文中给出了一个经典的例子，展示了在同一个交易依赖图中，存在不同大小的最优闭包：
从数学上把问题定义清楚了，接下来的问题就是：怎么快速算出这个最优线性化？
二、生成树线性化：从单纯形思想到实用算法
问题明确之后，论文提出了三种解法思路：线性规划（LP, Linear Programming）、GGT参数化最大流算法，以及他们自己的杀手锏——生成树线性化（SFL, Spanning Forest Linearization）
先说说LP。论文巧妙地将“寻找最大费用率闭包”这一整数规划问题，松弛成了一个线性规划，并且严谨证明了这个松弛不会丢失最优解。换句话说，对于这个问题，整数规划的最优解和线性规划的最优解是一样的，这就是所谓的“完全单模性”（total unimodularity）。这让矿工可以直接用成熟的LP求解器（如单纯形法）来解决问题。但LP的问题是：不保证找到的闭包是不是“最小”的。在矿工看来，找到费用率最优的闭包还不够好，他们还需要这个闭包尽可能小，以便更精细地填充区块的剩余空间，获取更高收益。解决这个问题需要两步法，增加额外计算。
而SFL的思路则完全不同。它不依赖复杂的数学规划，而是直接在交易依赖图上进行迭代式的“分解-合并”操作。
SFL的核心思想来源于单纯形法中的基可行解结构。在单纯形法中，每个顶点（即基可行解）都是由一组基变量构成的，它们对应一个生成树结构。SFL巧妙地把这个思想映射到了交易依赖图上。它始终维护一个当前的线性化方案，这个方案由一系列chunk组成。然后，算法会反复进行两种基本操作：
1. 合并（Merge）
2. 分裂（Split）
通过反复进行这两个操作，SFL不断“提纯”每个chunk的费用率，直到整个序列变得不可再优化，即达到最优。这个过程不需要求解复杂的线性规划，只需要在图上做局部搜索，因此速度极快。
SFL的惊艳之处在于，它是一个 Anytime Algorithm
图2：SFL算法的核心循环示意图。算法维护一个chunk序列，并在每一次迭代中，从依赖图的随机位置开始，尝试通过合并和分裂操作来改善整个线性化方案。
三、理论保证：最优性、收敛性与随机鲁棒性
一个好算法不仅要跑得快，还要有坚实的理论支撑。SFL的几个重要性质值得细细品味。
收敛性
随机鲁棒性
Anytime 最优性
四、实验对比：SFL在真实数据上速度翻倍
理论再好，也得在代码和数据面前说话。论文作者基于Bitcoin Core的源码搭建了测试环境，在合成数据和真实世界的数据上，将SFL与基于GGT参数化最大流算法以及线性规划求解器（使用OR-Tools）进行了严苛的对比测试。
先看一组在真实Bitcoin内存池数据上的表现。论文直接从Bitcoin Core的GitHub仓库中提取了历史内存池快照，模拟了140个具有复杂依赖关系的交易集群。结果显示，SFL在绝大多数情况下都能碾压对手，尤其是在大型集群上。
图3：在真实Bitcoin Core数据上，不同规模交易集群运行各种线性化算法的耗时对比。SFL算法（图中蓝色折线）在集群规模越大时，速度优势越明显。
从图3可以清晰地看到，对于包含64笔交易的集群，执行“从随机起始点到区块最大容量以内”这部分操作，SFL的耗时几乎是GGT算法的一半。而在小规模集群（如10笔交易以内）上，两者差距不大，但SFL依然更快。值得注意的是，在针对更大规模集群的“全部线性化”任务中，SFL的优势进一步放大，GGT算法在某些集群上的耗时飙升到了接近SFL的3倍。
接下来，论文还对合成数据集的全部线性化耗时进行了对比。数据集包括了随机生成的各种拓扑结构的交易依赖图（如随机图、星型图、链式图等）。
图4：在不同类型和规模的合成交易集群上，SFL与GGT全部线性化耗时的对比。SFL在所有数据集上都大幅领先。
图4的数据非常直观。在包含100笔交易的大型集群上，SFL全部线性化耗时甚至不到GGT的1/2。在几十笔交易的小集群上，GGT方法耗时约是SFL的2到4倍。GGT方法虽然也是一个多项式时间算法，但它的常数因子明显比SFL高。SFL的“图遍历+随机扰动+局部merge/split”策略，其计算量主要集中在图的遍历上，而GGT需要执行多次最小割计算，复杂度相对较高。
除了运行速度，论文还对比了线性化质量。所有算法在数据集上都能得出最优解（由LP验证），因此速度才是核心比拼点。SFL在这个维度上，取得了压倒性的胜利。Bitcoin Core社区选择合并SFL而非其他复杂算法，正是因为它能在确保最优性的前提下，实现极致的运行效率。这一结果也印证了作者之前基于PaperDaily数据库初步判断：在主流方法中，SFL是目前工程落地性价比最高的选择。
五、局限与展望：稠密图下的性能权衡
论文在实验部分也坦诚地指出了SFL的一个“软肋”：在 稠密图（dense graphs）
不过，论文也指出，在真实的Bitcoin交易池中，绝大多数的交易依赖图都是 稀疏图（sparse graphs）
此外，SFL目前的实现专注于静态优化，即在算法启动时给一个固定的交易快照。未来的研究可以探索如何让SFL更好地 增量式更新
龙迷三问
闭包（Closure）在SFL算法中具体扮演什么角色？
SFL和GGT（Gallo-Grigoriadis-Tarjan）算法的根本区别是什么？
论文中提到的“Anytime Algorithm”到底有什么实际好处？
如果你还有哪些想要了解的，欢迎在评论区留言或者讨论~
龙哥点评 论文创新性分数： ★★★★✰
论文将经典的调度问题与单纯形法基解结构巧妙结合，生成了SFL这种新颖、高效的图算法。虽非开天辟地，但在比特币这个特定领域是一个非常原创和实用的解决方案。实验合理度： ★★★★✰
实验设计严谨，同时覆盖了合成数据和真实数据，对比了LP、GGT等多种方法，并在Bitcoin Core的真实代码环境下进行了基准测试，结果令人信服。对稠密图的性能缺陷也进行了说明，体现了科研诚实性。学术研究价值： ★★★★★
虽然直接受比特币领域启发，但其将图论、组合优化和Anytime算法思想深度融合的范式，对于其他存在复杂依赖关系且需要频繁重新排序的调度问题（如云计算任务调度、供应链管理）都有很高的借鉴意义。稳定性： ★★★★★
已被合并到Bitcoin Core主代码库（PR #32545），并经过了大量生产环境的测试。算法在绝大多数交易场景下都能稳定、快速地输出最优解，鲁棒性极高。适应性以及泛化能力： ★★★✰✰
主要针对比特币mempool场景设计，其核心思想虽可推广，但算法对稀疏图依赖较强，在稠密图（如某些DeFi协议生成的复杂交易链）上效率会下降，泛化到其他系统需针对性调整。硬件需求及成本： ★★★★★
SFL是一种CPU算法，直接在依赖图上进行遍历和操作，无需昂贵的GPU或专用硬件。其轻量级特性使得即使是性能较低的服务器也能在毫秒级内完成优化，运行成本极低。复现难度： ★★★★★
代码已经合入Bitcoin Core，任何人可以直接从官方开源仓库下载并编译使用。论文中的伪代码和核心逻辑描述清晰，复现难度低。产品化成熟度： ★★★★★
产品化成熟度极高，它已经是Bitcoin Core 0.21版本之后的重要组件。这是一个少见的从论文直接到核心生产环境的案例。可能的问题： 论文对稠密图下的性能瓶颈描述得比较简略。或许未来可以结合GGT或LP的确定性，设计一个“混合算法”：在稀疏图上用SFL，在稠密图上回退到更慢但更普适的方法，代码中可能已经隐含这种策略，但论文里没细说。
[1] M. Mollakhani, P. Wuille, and D. Guo. Bitcoin mempool linearization. arXiv:2607.23787, 2026. [2] G. Gallo, M. D. Grigoriadis, and R. E. Tarjan. A fast parametric maximum flow algorithm. SIAM Journal on Computing, 18(1):30–55, 1989. [3] J. B. Sidney. Decomposition algorithms for single-machine sequencing with precedence relations. Operations Research, 23(2):283–298, 1975. [4] J. K. Lenstra and A. H. G. Rinnooy Kan. Complexity of scheduling under precedence constraints. Operations Research, 26(1):22–35, 1978. *本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～ 想了解更多原文细节的小伙伴，可以点击 "阅读原文"， 查看更多原论文细节哦！
