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

区块链因 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),其本质是一个四元祖

这个基于线性规划的严谨界说并不利便观众们明了。笔者画了以下的图片来辅助读者明了最大流问题的界说。下图中是s1到t1的最大流为10单元。

倘若把s1到t1的10单元的额度所有用尽,并不只一种方案,其中一种「增广」方案使用后如下图。

此时,s2到t2的最大流依旧为10单元,不外方案唯一。若是恰好把 单元流量用完,则全图残量网络如下。

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

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

2、基于灯塔节点的路由协议

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

然后,为了提供一定的额度隐私性并增添支付乐成的概率,每一笔支付的额度被分为|L|份,每一份由差别的灯塔节点协助完成传输。对于不分片的情形,我们以为|L|=1。 而灯塔协助传输的方式则是凭据自己的视野为这笔金额放置一条通道,并通过与这些通道上的节点通讯获取这个通道上可以通过的最大额度。

早期方式

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

双向BFS寻找最短路径


图嵌入

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

SilentWhispers 与 SpeedyMurmurs

,

欧博开户网址

欢迎进入欧博开户网址(Allbet Gaming):www.aLLbetgame.us,欧博网址开放会员注册、代理开户、电脑客户端下载、苹果安卓下载等业务。

,

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

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 图的大前提不会建立。总而言之,笔者以为,一个对未来支付网络拓扑结构的研究,于今至关主要,是若干支付网络更多研究生长的大前提。

References

1. Malavolta et al. SilentWhispers: Enforcing Security and Privacy in Decentralized Credit Networks. NDSS 2017

2. Roos et al. Settling Payments Fast and Private: Efficient Decentralized Routing for Path-Based Transactions. NDSS 2018

3. Sivaraman et al. Routing Cryptocurrency with the Spider Network. HotNets 2018

4. Peng Wang, Hong Xu, Xin Jin, and Tao Wang. Flash: Efficient Dynamic Routing for Offchain Networks. CoNEXT 2019

5. Joseph Poon and Thaddeus Dryja. The bitcoin lightning network: Scalable off-chain instant payments. https://lightning.network/lightning-network-paper.pdf. 2016

6. Raiden network. http://raiden.networkwork/.

7. Giovanni Di Stasi, Stefano Avallone, Roberto Canonico, and Giorgio Ventre. Routing payments on the lightning network. iThings/GreenCom/CPSCom 2018

8. Lewis Gudgeon, Pedro Moreno-Sanchez, Stefanie Roos, PatrickMcCorry, and Arthur Ger- vais. SoK: Layer-Two Blockchain Protocols. FC 2020

发表评论
sunbet声明:该文看法仅代表作者自己,与本平台无关。请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
用户名: 验证码:点击我更换图片

您可能还会对下面的文章感兴趣: