链得得|硬核丨一份关于支付网络中路由问题的全面研究( 三 )

首先，通过双向 BFS 寻找到和到的最短路径，
随后，通过与路径上各个节点的通讯，确定可以在这条路径上通过的支付金额数量，即这条路径上的最小余量。这一步可以通过安全多方计算（secure multiparty computation, MPC）来完成以保证隐私性。

SpeedyMurmurs 直接采用了分片支付的方案。除此以外，与 SilentWhispers 的一大不同是， SpeedyMurmurs 中灯塔节点利用树基图嵌入的方式提供支付路径，其出发点针对 SilentWhispers（1）双向 BFS 树在动态网络环境下维护的困难性，（2）即使是拓扑距离非常靠近的两个节点间路由也要经过 Landmark 节点，（3）以及极差可并发性的问题。每一个 Landmark 都根据现有支付通道维护一棵以自己为根节点的叉树。并以此维护对每个视野中节点的编号。假设现需要处理一笔从到的支付，总金额为，利用个灯塔节点 ( ) 。支付者将支付金额分为份，第的路由交由协助完成。对于每一个( ) ，通过两个节点的编号寻找的树上到的树上路径，完成对应的支付。3 基于数据网络方法的路由协议由于以上的路由方案都没有充分考虑实际支付网路的动态性。所以部分来自计算机网络背景的学者提出了将数据网络中的路由办法直接用到支付网络中的若干方案。由于数据网络的路由理论已经在计算机网路领域非常成熟，这一类方案具有较高的可靠性。动态性也给这类方案提供了非常可观的效率。其中最为经典的是 Spider 协议。Spider 将支付网络类比为数据传输层，使用数据网络的方法进行动态路由。为了和数据网络的模型匹配，在此方案中，我们依旧假设所有的通道都是双向的。类似于数据网络中的数据包，每一笔交易被拆分为若干金额包通过不同路径寻路。每个金额包被直接通过支付网路通道传输并最终抵达收款者，其转发过程中的节点都锁定了相应额度。在完成了寻路后，根据各个金额包的转发路径完成最终支付。然而，支付网路和数据网络的一大区别在于通量限制的存在。因此，每个通道都会对应一个队列（pending list）保存所有还没能以当前通量完成传输的金额包。只有当有足够的通量从通道的另一侧传来（等价于本方向的余量增加），这个队列中的金额包才能继续传输。值得注意的是，虽然我们用一个金额包的传输过程来描述动态路由过程，其实质是一个寻路与锁定的过程，倘若不加注意会把这个路由过程误以为是支付过程。4 混合路由协议通过对 Ripple 和 Bitcoin 支付网络的实际分析，最新的调研（Flash的论文中）发现：

支付网路有必要支持大额交易（这一点曾经被质疑过）；
大额交易需要更加侧重支付成功率，小额交易应该更加注重效率。

本文插图

基于这一发现， Flash 协议用基于最大流的路由方案来完成大额金额的支付，用基于数据网络的路由方法进行小额金额的支付。由此，大额交易的支付成功率和小额交易的效率得以两全。各类路由方案的对比与分析笔者在以上表格 Tab.1 中，列举了各类非混合路由协议的优势与劣势。由于难以量化，具有一定的主观色彩。 5 未来研究展望接下来，笔者提出若干研究展望，并在文末提出这方面科研中可能遇到的问题。 ? 熟悉「基于增广路的最大流算法」的朋友们应该了解，这类算法都需要为每条边配备上一条「反向边」用来描述一种算法中需要用到的回流。而我们可以惊讶地发现，这种回流正好对应地刻画了双向支付通道中从另一个方向的额度冲抵。因而增广路定理保证了哪怕在支付网络上无规则地「增广」，最后也一定会完成任一笔不超过最大流额度的支付。这样，我们就得到了一种完全「动态」的基于最大流的路由算法。这一点似乎并未被现有文献提及。当然，对于绝大多数小额交易，用这个算法太过于杀鸡用牛刀了。但笔者相信对于早期支付网络中遇到的巨额交易，这个思路会派的上用处。 ? 可以用「最小费用最大流」来取代底层最大流，使得有多种选项时算法可以挑出一组长度最短、总过路费最少的路径方案。学过一种「最小费用最大流」算法的朋友此时应该能明白笔者的寓意，在此不再展开。 ? 通过支付网络相关智能合约代码的重构，或者通过另类 landmark 节点的设立，「指导」参与节点建边，以系统性地改进网络的拓扑结构。笔者曾对可能由各个 landmark 引向的结构做过不少畅想，其中包括基于 hypercube、以 landmark 为根的平衡树、以 landmark 为根的 link-cut-tree 等等。如想在这一方向（支付网络中的路由问题）深入科研，尤其如果在以缩短平均跳数（hop）为目的，可能存在两大问题：第一个问题实事求是地，当前的支付方案在当前的支付网络规模中已经做得够好了。根据 SpeedyMurmurs 论文中的实验数据，其已经可以在鼎盛时期的 Ripple 网络中达到平均 2 到 4 跳数（hop）的水准。在此之上再做优化又能如何呢？更优美且能在未来百千万、上亿规模支付网络中取得更好结果的算法，在当前支付网络下兴许反而因为较大的「常数」而并不能取得一个更好的结果。当然，基础研究是要面向未来大规模支付网络的未来的，但面向未来的研究得要在大规模的网络上进行模拟实验才能具有公信力。接下来笔者来阐述一下大规模支付网络的拓扑结构的模拟是如何不可为的。第二个问题难以进行合理的模拟实验。首先，实事求是地说，当前阶段的现实网络中的多数参与者尚且是少数极客精英和资本，其拓扑结构肯定和未来的真实网络大相径庭。其次，笔者认为社交网络中的若干模型并不能真实反应支付网络未来之拓扑结构，例如，笔者并不觉得社交网路中常用的「Watts 图」可以刻画好未来的这个网络，因为大多数节点不会去建很多条边使得图的 density 达到出现 small-world phenomenon 的 threshold ， Watts 图的大前提不会成立。总而言之，笔者认为，一个对未来支付网络拓扑结构的研究，于今至关重要，是若干支付网络更多研究发展的大前提。