硬核丨一份关于支付网络中路由问题的全面研究

加密谷Live · 公众号 · · 2020-10-18 19:41

正文

区块链因 Layer 1 的交易吞吐量上限而常被诟病， 离线支付网络 （off-chain payment channel network，PCN，下文统称「支付网络」）提供了一种「线下支付+线上结算」的解决方案，为区块链世界的支付（及其泛化成的各类交互）赋予了几乎无限的交易吞吐量。因而，支付网络成为了当前最为热门的区块链研究与工程实践方向之一。

经过多年国际学者与工程的发展，支付网络的若干子研究方向已有了大量的论文研究和工程实践，已经不易遍历阅读和详尽了解。然而，当前阶段对于这一重要的研究方向，虽然多数区块链领域的人士对其基本思想有所了解，但对其最新进展具有较全面追踪的国内极客与学者还不多。

本综述系列面向对这一领域具有兴趣的极客和学者，剖析若干子方向，归纳最新研究进展、提出笔者的思考。作者是 热爱研究的 Nervos 小伙伴 Shor ，现为 上海交通大学博士 。

本文中，我们默认读者具备了对于支付网络（ off-chain payment network）的基本了解。在部分描述中，我们会将支付网络看作一张图论意义上的图（ graph），每个参与者看作一个节点（ vertex），每个支付通道看作一条图上的边（ edge）。所以下文中笔者会不自觉地用「图」来指代一个支付网络，用「节点」来指代一个参与者，「边」字来指代一个支付通道。

路由，即一个需要在支付网络上发送交易的人和交易接收者与图上其他节点共同互动而决定支付路径的过程。 当然，严格而言，这不一定是一条路径，而可能是一系列路径组成的一个有向无环图（ directed acyclic graph, DAG），由于其他学者似乎尚未对此范畴采用新名词，因而笔者将此系列路径的总和命名为 transaction pattern 。

基于网络流的路由协议

用一个网络流模型刻画支付网路的整体状态具有以下优势：首先，网络流准确刻画了各支付通道的总额度、余量，使用现有的最大流算法可以找到两点之间可以达到的最大支付总额，并且高效地找出一组可行路径。接下来，笔者简要介绍一下网络流问题。

Hint ：「基于网络流的路由协议」是笔者所拟的名称，其在大多数文献中对应的词组是 Source Routing 。其原因是这一类路由的过程得由源节点本地完成，其过程中默认源节点掌握了整张支付网络的拓扑结构，并且可以动态探测（ probe）任意支付通道中的余量。然而，所有已有的 Source Routing 方案都是基于最大流算法的，所以笔者大胆地改换了称呼，以便读者理解（另一大原因是笔者在研究展望部分将提出一种并非 source routing 范畴的基于网络流的路由协议）。

网络流问题简介

我们用网络流模型中的一个 残量网络 （ residual network）表述一个支付网路的整体状态（ configurati on），其本质是一个四元祖，其中是节点集合，每个节点代表一个支付网络中的参与节点，是边集，每条边代表了一个支付通道, 表示各边的残余通量。结合支付网路的应用需要，我们不同于网络流传统地增加表示各通道建立之时确立的最大通量（ , ）。

最大流是在网络流模型上的一族线性规划问题。其中从到的单源单汇最大流问题（

）是：

这个基于线性规划的严谨定义并不方便观众们理解。笔者画了以下的图片来帮助读者理解最大流问题的定义。下图中，到的最大流为单位。

倘若把到的单位的额度全部用尽，并不只一种方案，其中一种「增广」方案使用后如下图。

此时，到的最大流依旧为单位，不过方案唯一。如果恰好把单位流量用完，则全图残量网络如下。

常用的最大流算法包括预留推进算法（ HLPP）和一类基于增广路定理的最大流算法，其中包括了 Edmonds-Karp 算法以及他的衍生算法如 ISAP 算法和 Dinic 算法。

这些算法都具有极高的最坏情况下的理论复杂度，和往往远低于理论复杂度的可观运行效率。例如，考虑一张有节点条边的流量图，Edmonds-Karp 算法的理论计算复杂度高达，Dinic 算法的理论计算复杂度高达，而他们在正常的稀疏随机图上的执行效率很高，普通 CPU 可以在百毫秒内求出千量节点的最大流。

不难发现，对于大额支付，我们可以通过最大流算法得到两节点之间的最大可能支付额度。如果支付金额小于这个额度，我们也就通过最大流算法确立了一个支付方案。

基于灯塔节点的路由协议

基于灯塔 （landmark）节点的路由协议的总体思路如下。首先，每个节点都有资格成为灯塔节点，每个节点都有权利选择让哪些灯塔节点来协助路由。这个大前提基本保证了路由方案的去中心化特性不被打破。

然后，为了提供一定的额度隐私性并增加支付成功的概率，每一笔支付的额度被分为份，每一份由不同的灯塔节点协助完成传输。对于不分片的情况，我们认为。而灯塔协助传输的方式则是根据自己的视野为这笔金额安排一条通道，并通过与这些通道上的节点通讯获取这个通道上可以通过的最大额度。

早期方法

基于 Landmark 的路由协议思路来自于计算机网络领域的研究。其中的常见组件如下。

双向BFS寻找最短路径

熟悉算法的读者了解，在无边权的有向图上，从单源出发的广度优先搜索（Breath-First Search, BFS）序列性质保证：BFS 树中各节点到源节点的路径，即该节点到源节点的最短路径或最短路径之一。每一个 Landmark 节点维护两棵以自己为源节点的 BFS 树，一棵基于 PCN 图，一棵基于将所有通道方向反转后的 PCN 图。当然，对于无向图而言，这两棵树是一致的。由此，对于一个从到的路由需要，先在中找到到 landmark 节点的路径，再在中找到 landmark 节点到的路径。这两个路径拼接起来，就得到了从到的一条最短路径。

图嵌入

树基图嵌入 （tree-based graph embedding）让每个灯塔节点把所有的视图内的节点视为一棵树，树上的每条边对应了一条支付通道。这样，可以用一种类似 Trie 树的方式，为每个节点用从根节点到该节点的路径编号。例如下图中，节点的标号即为，节点的标号即为，节点的标号即为。当然，我们只是在用二叉树举例，现实实现中这是一颗多叉树，此时的编码范围就不再是与之间。对于叉树而言，编码范围就成了至。

通过这样的编码方式，可以高效地确定两个节点之间的一条路径——即从付款节点到两节点的最近公共祖先（lowest common ancestor, LCA）的唯一路径拼接上从 LCA 到收款节点的唯一路径。

SilentWhispers 与 SpeedyMurmurs

SilentWhisper 的协议本身并不考虑支付网路的动态性，文章中的方案没有考虑额度分片，因而一次支付仅利用个灯塔节点。当然，这个方案可以被扩展到的分片支付方案，不过这个方案的通讯复杂度随着支付所用灯塔节点的数量平方线性增长。假设现需要处理一笔从到的支付，总金额为。支付者将支付金额分为份，第的路由交由协助完成。对于每一个 ( )：

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

SpeedyMurmurs 直接采用了分片支付的方案。 除此以外，与 SilentWhispers 的一大不同是，SpeedyMurmurs 中灯塔节点利用树基图嵌入的方式提供支付路径，其出发点针对 SilentWhispers（1）双向 BFS 树在动态网络环境下维护的困难性，（2）即使是拓扑距离非常靠近的两个节点间路由也要经过 Landmark 节点，（3）以及极差可并发性的问题。

每一个 Landmark 都根据现有支付通道维护一棵以自己为根节点的叉树。并以此维护对每个视野中节点的编号。假设现需要处理一笔从到的支付，总金额为，利用个灯塔节点 ( )。支付者将支付金额分为

硬核丨一份关于支付网络中路由问题的全面研究

正文

网络流问题简介

早期方法

SilentWhispers 与 SpeedyMurmurs

请到「今天看啥」查看全文