一种基于最小费用流的最优链下通道网络路由方法

技术领域

本发明涉及区块链交易路由技术领域，具体地，涉及一种基于最小费用流的最优链下通道网络路由方法。

背景技术

链下通道网络(PCN:Payment Channel Network)，是目前使用最广泛的提高提升区块链系统性能的技术解决方案。区块链技术是近几年发展十分迅猛的一项技术，并随着各类加密货币的火热而被公众熟知。除了加密货币外，区块链技术也广泛应用于金融，供应链，法律，物流等各行各业，并被认为是构建下一代价值互联网的重要基础设施。但现有区块链系统依赖于全网的一致性共识协议来维持系统信用，这种工作方式导致其天然存在性能难题。比如区块链技术的代表比特币系统，其每秒理论上最多只能处理7笔交易，而在现实运行中只有3到4笔交易。作为对比，美国的Visa信用卡系统可以轻松实现每秒数千到数万笔交易。链下通道网络可以很好的解决区块链系统的性能难题，一个成熟完善的链下通道网络可以轻松支持每秒数百万笔交易。一个典型的链下通道网络主要有互相连通的链下通道及其节点构成。链下通道(Payment Channel)由两个区块链用户通过数字签名，智能合约等技术建立，支持双方进行多次交易而不必每次交易都提交至区块链上。请参阅图1，链下通道的整个生命周期有三个阶段：(1)通道建立；(2)链下流通；(3)链上结算。三个阶段中仅在通道的建立和结算阶段需要两次和链上进行交互，而大量的链下交易不需要代价高昂的链上操作，因此大大提高了链下通道两个参与节点间的交易能力，并降低了交易成本和延迟。链下通道仅仅只是在两个节点间进行交易，为了扩展交易能力和范围，请参阅图2，链下通道网络支持两个没有直接建立链下通道的节点通过中继节点进行交易，在合适的路由方法的帮助下，只要两个节点之间存在由链下通道构成的有向路径，即可完成交易。这里为了保证交易的正确性，链下通道网络使用哈希时间锁定合约(Hash Time-LockedContracts)技术来约束所有参与的节点。

整个链下通道网络的核心是其中的路由方法，路由方法按照某种原则(延迟，成本，通量)找到可用于交易的路径的集合，一个好的路由方法应该满足低延迟，低成本，高通量的要求。当前的路由方法主要分为两类，一类是单路径路由方法，另一类的多路径路由方法。单路径路由方法顾明思义只使用一条路径来完成交易，其中一个典型代表是Flare算法，其路由思想是选择几个节点作为全局信标节点，而所有普通节点维护着包含信标节点的路由表。在搜索路径时，由发送节点和接收节点同时通过路由表进行路径探索，当探索到共有的信标节点时便表示找到一条可达的候选路径。该方案的特点时路由方法简单，普通节点只需要维持一个局部路由表，能够以较小的带宽消耗保证路由方法的可靠性。但其也存在着中心化的倾向，在路由过程中较为依赖少数几个全局信标节点，对信标节点的存储，带宽有着较高的要求。并且信标节点也更容易受到DDoS攻击等，当信标节点瘫痪时容易造成整个网络的拥堵和瘫痪。与单路径路由方法不同，多路径路由方法将一笔交易拆分成多笔交易，并在多条路径上执行交易。这样做可以提高大额交易的成功率，降低每笔交易的路由负载，减轻通道阻塞情况。多路径路由方法的一个代表是Flash算法，其路由思想是利用交易请求在容量分布上具有长尾效应这一特点，针对大额交易和小额交易分布采取不同的路由策略。小额交易转移资产数量小，对路径要求低，因此Flash算法使用在过去已经建立的路由表中查找一条路径供其交易。而大额交易转移资产数量大，对路径要求高，单条路径通常能以满足要求，因此Flash算法使用改进的Edmonds-Karp最大流算法框架，使用广度优先搜索找到发送节点和接收节点之间的k条路径来完成交易。基于此策略，Flash算法大幅提升了大额交易的成功率。此外，还有一些其它路由方法具有自己的特色，如SilentWhispers路算法，其侧重在路由过程中实现隐私保护功能，把安全多方计算技术引入路由过程中，避免了在交易过程中产生信息泄露。但安全多方计算的引入也显著增加了寻径开销。当前存在的这些路由方法都可以看作是概率算法，这些算法并不会最求在某方面最优，或在某些目标上一定到达最优解，只是在当前探索得到的部分路径中选择一个较好的路径。

公开日为2021.08.06的中国发明申请：一种链下支付通道路由平衡方法中，旨在根据网络拓扑结构将网络分割成为层次区域结构，在交易发起时只需要寻找到目标的层次区域，在局部范围内完成路由表的查询，通过分级的策略帮助路由表的构建，借助通道平衡因子的影响，将通道失衡现象降低，提高路由方法的效率。但现有技术仍有一定的局限性。

发明内容

针对现有技术的局限，本发明提出一种基于最小费用流的最优链下通道网络路由方法，本发明采用的技术方案是：

一种基于最小费用流的最优链下通道网络路由方法，包括以下步骤：

S1，将待处理的交易请求所在的链下通道网络建模为有向图，将转账交易映射为所述有向图中的输入流量，以非递减的凹函数作为所述有向图中边的费用函数；

S2，获取所述交易请求的源点与汇点之间在所述有向图中的最大流；

S3，根据所述最大流以及交易请求，判断所述链下通道网络能否实现所述交易请求；若是则执行步骤S4，否则结束；

S4，根据所述最大流，获取所述交易请求的源点与汇点之间在所述有向图中的最小费用流；以所述最小费用流在所述链下通道网络对应的路由方案作为结果。

相较于现有技术，本发明通过对链下通道网络进行建模，把链下通道网络中的路由问题转变成络流问题；以凹函数作为边上的费用函数，通过求解两节点间的最大流和最小费用流，实现在链下通道网络中理论上费用最低的路由策略；在费用控制方面有明显优势，可以单独使用，也可以与其他路由策略相结合并降低其路由方案的费用。在确保网络拓扑结构相同，费用函数一致的情况下，本算法可找到总费用最低的路由方案。在各类参数环境下展现出较大的算法性能提升，并在实验仿真环境中表现出良好的鲁棒性和拓展性。

作为一种优选方案，所述有向图表示为G＝(V,E)，其中，V表示有向图G中节点的集合；各个节点v分别代表一个区块链账户，节点之间存在一个或多个链下通道；E表示网络G中边的集合；各条边e∈E分别代表链下通道网络中的一个链下通道，以容量函数u

进一步的，所述步骤S2包括以下过程：

初始化设置网络流f为空，流入所述汇点的流量Δ＝U

更进一步的，所述步骤S2中通过以下方式更新Δ和网络流f：

根据网络流f更新剩余网络G

在无法找到所述增广路径ΔAP后，设置Δ＝Δ/2。

更进一步的，所述步骤S2中通过以下方式更新剩余网络G

根据网络流f，计算在剩余网络G

以公式G

更新剩余网络G

更进一步的，所述步骤S2中通过重复以下过程直至消除剩余网络G

以l

选择其中一个能够增加最多流量的增流环，沿着该增流环增广流量，在该增流环上的一个节点上产生额外流量成为超额节点；更新网络流f，根据网络流f更新剩余网络G

更进一步的，所述增广路径ΔAP通过以下方式获得：

从所述汇点出发，根据流入汇点的流量，以费用作为边的权重，逆向计算出从所有其它节点出发到所述汇点最少需要的流量和对应的路径；在逆向计算得出的路径中，若满足所述源点或超额节点拥有发送Δ大小的金额到所述汇点所需的流量的条件，则以满足该条件的路径作为所述增广路径ΔAP。

本发明还包括以下内容：

一种基于最小费用流的最优链下通道网络路由系统，包括依序连接的网络建模模块、最大流获取模块、判断模块以及最小费用流获取模块；其中：

所述网络建模模块用于将待处理的交易请求所在的链下通道网络建模为有向图，将转账交易映射为所述有向图中的输入流量，以非递减的凹函数作为所述有向图中边的费用函数；

所述最大流获取模块用于获取所述交易请求的源点与汇点之间在所述有向图中的最大流；

所述判断模块用于根据所述最大流以及交易请求，判断所述链下通道网络能否实现所述交易请求；若是则转向所述最小费用流获取模块，否则结束；

所述最小费用流获取模块用于根据所述最大流，获取所述交易请求的源点与汇点之间在所述有向图中的最小费用流；以所述最小费用流在所述链下通道网络对应的路由方案作为结果。

一种存储介质，其上储存有计算机程序，所述计算机程序被处理器执行时实现如前述的基于最小费用流的最优链下通道网络路由方法的步骤。

一种计算机设备，包括存储介质、处理器以及储存在所述存储介质中并可被所述处理器执行的计算机程序，所述计算机程序被处理器执行时实现如前述的基于最小费用流的最优链下通道网络路由方法的步骤。

附图说明

图1为链下通道的示例图；

图2为链下通道网络的示例图；

图3为本发明实施例提供的一种基于最小费用流的最优链下通道网络路由方法的步骤示意图；

图4为本发明实施例增流换环的示例图；

图5为本发明实施例增广路径的示例图；

图6至11为本发明实施例具体示例的求解过程；

图12为本发明实施例提供的一种基于最小费用流的最优链下通道网络路由系统的示意图。

具体实施方式

附图仅用于示例性说明，不能理解为对本专利的限制；

应当明确，所描述的实施例仅仅是本申请实施例一部分实施例，而不是全部的实施例。基于本申请实施例中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其它实施例，都属于本申请实施例保护的范围。

在本申请实施例使用的术语是仅仅出于描述特定实施例的目的，而非旨在限制本申请实施例。在本申请实施例和所附权利要求书中所使用的单数形式的“一种”、“所述”和“该”也旨在包括多数形式，除非上下文清楚地表示其他含义。还应当理解，本文中使用的术语“和/或”是指并包含一个或多个相关联的列出项目的任何或所有可能组合。

下面的描述涉及附图时，除非另有表示，不同附图中的相同数字表示相同或相似的要素。以下示例性实施例中所描述的实施方式并不代表与本申请相一致的所有实施方式。相反，它们仅是如所附权利要求书中所详述的、本申请的一些方面相一致的装置和方法的例子。在本申请的描述中，需要理解的是，术语“第一”、“第二”、“第三”等仅用于区别类似的对象，而不必用于描述特定的顺序或先后次序，也不能理解为指示或暗示相对重要性。对于本领域的普通技术人员而言，可以根据具体情况理解上述术语在本申请中的具体含义。

此外，在本申请的描述中，除非另有说明，“多个”是指两个或两个以上。“和/或”，描述关联对象的关联关系，表示可以存在三种关系，例如，A和/或B，可以表示：单独存在A，同时存在A和B，单独存在B这三种情况。字符“/”一般表示前后关联对象是一种“或”的关系。以下结合附图和实施例对本发明做进一步的阐述。

为了解决现有技术的局限性，本实施例提供了一种技术方案，下面结合附图和实施例对本发明的技术方案做进一步的说明。

实施例1

请参阅图1，一种基于最小费用流的最优链下通道网络路由方法，包括以下步骤：

S1，将待处理的交易请求所在的链下通道网络建模为有向图，将转账交易映射为所述有向图中的输入流量，以非递减的凹函数作为所述有向图中边的费用函数；

S2，获取所述交易请求的源点与汇点之间在所述有向图中的最大流；

S3，根据所述最大流以及交易请求，判断所述链下通道网络能否实现所述交易请求；若是则执行步骤S4，否则结束；

S4，根据所述最大流，获取所述交易请求的源点与汇点之间在所述有向图中的最小费用流；以所述最小费用流在所述链下通道网络对应的路由方案作为结果。

相较于现有技术，本发明通过对链下通道网络进行建模，把链下通道网络中的路由问题转变成络流问题；以凹函数作为边上的费用函数，通过求解两节点间的最大流和最小费用流，实现在链下通道网络中理论上费用最低的路由策略；在费用控制方面有明显优势，可以单独使用，也可以与其他路由策略相结合并降低其路由方案的费用。在确保网络拓扑结构相同，费用函数一致的情况下，本算法可找到总费用最低的路由方案。在各类参数环境下展现出较大的算法性能提升，并在实验仿真环境中表现出良好的鲁棒性和拓展性。

作为一种优选实施例，所述有向图表示为G＝(V,E)，其中，V表示有向图G中节点的集合；各个节点v分别代表一个区块链账户，节点之间存在一个或多个链下通道；E表示网络G中边的集合；各条边e∈E分别代表链下通道网络中的一个链下通道，以容量函数u

具体的，所述容量函数u

对于一个交易请求三元组(s,t,a)，其中s是交易的发起节点，也称为源点；t是交易的接收节点，也称为汇点；a是源点s希望通过链下通道网络支付给汇点t的交易金额。对于这样一个交易请求，本实施首先判断当前的链下通道网络能否实现该交易，即先确定从源点到汇点之间能够转账的最大金额；在进行数学建模后，把转账交易映射成在网络中输入流量，这样即可将寻找最大转账金额的问题抽象成在链下通道网络中寻找一个从源点到汇点之间的最大流(Maximum Flow)问题，将寻找一个费用最低的路由方案抽象成了在链下通道网络中寻找一个从源点到汇点之间的最小费用流(Minimum Cost Flow)问题。本实施例用f表示网络流，用G

∑

一个网络流f是可行流当且仅当其满足如下容量限制：

本实施例用c(f)表示一个网络流的总费用，其定义如下

c(f)＝∑

本实施例把在链下通道网络中寻找一笔交易理论上费用最小的路由方案映射成在图中求解一个最小费用流，形式化的描述为

其中F

进一步的，所述步骤S2包括以下过程：

初始化设置网络流f为空，流入所述汇点的流量Δ＝U

更进一步的，所述步骤S2中通过以下方式更新Δ和网络流f：

根据网络流f更新剩余网络G

在无法找到所述增广路径ΔAP后，设置Δ＝Δ/2。

具体的，所述增广路径ΔAP的示例可参阅图5。图5中字母u表示边的容量，字母f表示边上的流量；沿着增广路径(s→1→4→t)注入流量，使4单位流量流入节点t。

更进一步的，所述步骤S2中通过以下方式更新剩余网络G

根据网络流f，计算在剩余网络G

以公式G

更新剩余网络G

具体的，本实施例的剩余网络在原图的基础上增加了反向边；若增加反向边上的流量，便意味着在原图中减小对应正向边上的流量。这样在剩余网络中就有了回退之前某些操作的可能性。本实施以所述代价函数体现出被节点收取的费用与流量的大小相关，并且在剩余网络上的费用加上原网络上的费用与把两者流量想加后在原网络上收取的费用相等。

而因为费用函数的存在，在剩余网络G

因此，更进一步的，所述步骤S2中通过重复以下过程直至消除剩余网络G

以l

选择其中一个能够增加最多流量的增流环，沿着该增流环增广流量，在该增流环上的一个节点上产生额外流量成为超额节点；更新网络流f，根据网络流f更新剩余网络G

具体的，在所述步骤S3中，如果f的值大于等于a，则说明存在从源点s到汇点t且转账交易金额为从源点s到汇点a的路由方案。那么，只要减小f的值直到其等于a为止，此时f是一个符合要求即转账金额恰好为a的网络流，但f并不一定是费用最小的网络流。本实施例通过在所述步骤S4中在G

更进一步的，所述增广路径ΔAP通过以下方式获得：

从所述汇点出发，根据流入汇点的流量，以费用作为边的权重，逆向计算出从所有其它节点出发到所述汇点最少需要的流量和对应的路径；在逆向计算得出的路径中，若满足所述源点或超额节点拥有发送Δ大小的金额到所述汇点所需的流量的条件，则以满足该条件的路径作为所述增广路径ΔAP。

接下来将结合具体的案例对本实施方案作进一步的阐释，以图6的网络拓扑为例，展示求解从源点s到汇点t的最大流(即所述步骤S2)和最小费用流(即所述步骤S4)的过程。图6中字母u表示边的容量，字母f表示边上的流量；在初始状态下，所有边上的流量值均为0。

假设交易请求三元组为(s,t,12.6)，各条边上的费用函数分别为：

所述步骤S2具体求解过程如下：

初始化f为空，设置初始Δ＝U

第一轮更新：首先消除所有增流环，此时网络中不存在增流环，因此没有做任何改变；更新G

第二轮更新：首先消除所有增流环，此时网络中不存在增流环，因此没有做任何改变。更新G

第三轮更新：首先消除所有增流环，找到增流环＝(t→4→1→2→t)，沿着该增流环增广流量，如图9所示：沿着增流环(t→4→1→2→t)注入流量，2.4单位流量从节点t流出，3单位流量流入节点t。更新G

所述步骤S4具体求解过程如下：

消除所有增流环(费用负环)，由于已经不存在费用负环，所述步骤S4结束。当前所求即为最小费用流，如图11所示。

图11中，字母u表示边的容量，字母f表示边上的流量。图11为实施例1所求的最小费用流，其对应着费用最低的路由方案：即节点s发送10单位加密货币给节点1，节点s发送10单位加密货币给节点3。节点1发送3.5单位加密货币给节点2，节点1发送4.8单位加密货币给节点4，节点1收取1.7单位加密货币作为费用。节点2发送3单位加密货币给节点t，节点2收取0.5单位加密货币作为费用。节点3发送8单位加密货币给节点4，节点3收取2单位加密货币作为费用。节点4发送9.6单位加密货币给节点t，节点4收取3.2单位加密货币作为费用。节点t最终收到12.6单位加密货币。

实施例2

请参阅图12，一种基于最小费用流的最优链下通道网络路由系统，包括依序连接的网络建模模块1、最大流获取模块2、判断模块3以及最小费用流获取模块4；其中：

所述网络建模模块1用于将待处理的交易请求所在的链下通道网络建模为有向图，将转账交易映射为所述有向图中的输入流量，以非递减的凹函数作为所述有向图中边的费用函数；

所述最大流获取模块2用于获取所述交易请求的源点与汇点之间在所述有向图中的最大流；

所述判断模块3用于根据所述最大流以及交易请求，判断所述链下通道网络能否实现所述交易请求；若是则转向所述最小费用流获取模块4，否则结束；

所述最小费用流获取模块4用于根据所述最大流，获取所述交易请求的源点与汇点之间在所述有向图中的最小费用流；以所述最小费用流在所述链下通道网络对应的路由方案作为结果。

实施例3

一种存储介质，其上储存有计算机程序，所述计算机程序被处理器执行时实现如实施例1所述的基于最小费用流的最优链下通道网络路由方法的步骤。

实施例4

一种计算机设备，包括存储介质、处理器以及储存在所述存储介质中并可被所述处理器执行的计算机程序，所述计算机程序被处理器执行时实现如实施例1所述的基于最小费用流的最优链下通道网络路由方法的步骤。

显然，本发明的上述实施例仅仅是为清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动。这里无需也无法对所有的实施方式予以穷举。凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明权利要求的保护范围之内。