硬核丨一份关于支付网络中路由问题的全面研究摘要：区块链因Layer1的交易吞

摘要：区块链因 Layer 1 的交易吞吐量上限而常被诟病，离线支付网络（off-chain payment channel network ， PCN）提供了一种「线下支付+线上结算」的解决方案。
文章插图
区块链因 Layer 1 的交易吞吐量上限而常被诟病，离线支付网络（off-chain payment channel network ， PCN ，下文统称「支付网络」）提供了一种「线下支付+线上结算」的解决方案，为区块链世界的支付（及其泛化成的各类交互）赋予了几乎无限的交易吞吐量。因而，支付网络成为了当前最为热门的区块链研究与工程实践方向之一。
经过多年国际学者与工程的发展，支付网络的若干子研究方向已有了大量的论文研究和工程实践，已经不易遍历阅读和详尽了解。然而，当前阶段对于这一重要的研究方向，虽然多数区块链领域的人士对其基本思想有所了解，但对其最新进展具有较全面追踪的国内极客与学者还不多。
本综述系列面向对这一领域具有兴趣的极客和学者，剖析若干子方向，归纳最新研究进展、提出笔者的思考。作者是热爱研究的 Nervos 小伙伴 Shor ，现为上海交通大学博士。
文章插图
本文中，我们默认读者具备了对于支付网络（off-chain payment network）的基本了解。在部分描述中，我们会将支付网络看作一张图论意义上的图（graph），每个参与者看作一个节点（vertex），每个支付通道看作一条图上的边（edge）。所以下文中笔者会不自觉地用「图」来指代一个支付网络，用「节点」来指代一个参与者，「边」字来指代一个支付通道。
路由，即一个需要在支付网络上发送交易的人和交易接收者与图上其他节点共同互动而决定支付路径的过程。当然，严格而言，这不一定是一条路径，而可能是一系列路径组成的一个有向无环图（directed acyclic graph, DAG），由于其他学者似乎尚未对此范畴采用新名词，因而笔者将此系列路径的总和命名为 transaction pattern 。
1 基于网络流的路由协议
用一个网络流模型刻画支付网路的整体状态具有以下优势：首先，网络流准确刻画了各支付通道的总额度、余量，使用现有的最大流算法可以找到两点之间可以达到的最大支付总额，并且高效地找出一组可行路径。接下来，笔者简要介绍一下网络流问题。
Hint：「基于网络流的路由协议」是笔者所拟的名称，其在大多数文献中对应的词组是 Source Routing 。其原因是这一类路由的过程得由源节点本地完成，其过程中默认源节点掌握了整张支付网络的拓扑结构，并且可以动态探测（probe）任意支付通道中的余量。然而，所有已有的Source Routing方案都是基于最大流算法的，所以笔者大胆地改换了称呼，以便读者理解（另一大原因是笔者在研究展望部分将提出一种并非 source routing 范畴的基于网络流的路由协议）。网络流问题简介
我们用网络流模型中的一个残量网络（residual network）表述一个支付网路的整体状态（configuration），其本质是一个四元祖，其中是节点集合，每个节点代表一个支付网络中的参与节点，是边集，每条边代表了一个支付通道, 表示各边的残余通量。结合支付网路的应用需要，我们不同于网络流传统地增加表示各通道建立之时确立的最大通量（, ）。
最大流是在网络流模型上的一族线性规划问题。
文章插图
这个基于线性规划的严谨定义并不方便观众们理解。笔者画了以下的图片来帮助读者理解最大流问题的定义。下图中，到的最大流为单位。
文章插图
倘若把到的单位的额度全部用尽，并不只一种方案，其中一种「增广」方案使用后如下图。
文章插图
此时，到的最大流依旧为单位，不过方案唯一。如果恰好把单位流量用完，则全图残量网络如下。
文章插图
常用的最大流算法包括预留推进算法（HLPP）和一类基于增广路定理的最大流算法，其中包括了 Edmonds-Karp 算法以及他的衍生算法如 ISAP 算法和 Dinic 算法。