全国首单电商平台数字人民币消费在京东诞生
12月11日20时00分02秒,全国首单电商平台数字人民币消费诞生,苏州的一位消费者在京东商城成功下单。
继上一次关于支付网络中路由问题的周全研究之后,热爱研究的 Nervos 小伙伴 Shor 对通道网络中的再平衡(Rebalancing)算法又做了详细的研究。
本文中,我们会先容通道网络(Channel Network,CN)中的 Rebalance 问题。首先我们将先容问题的界说和现有的解决算法。之后,我们会针对这一问题,先容需要的图论基础和建模方式。最后,我们提供一种算法加速思绪。(本文默认读者具备对于通道网络的知识。)
支付网络中的 Rebalance 问题简介 我们把一个支付网络看作一个无向图,每个图中的节点代表一个 PID,每条边代表一个支付通道,其中每条边在两头节点各有一个存量。注重:我们默认每个(双向)支付通道内部总存量守恒,即由 A,B 组成的通道中,若是 A 有余额 50,B 有余额 80,B 在向 A 支付 10 元后,A 有余额 60,B 有余额 70。
有时,由于网络拓扑结构等缘故原由,一个支付通道的一个偏向总比另一个偏向「更受欢迎」,在此情形下,各个通道的有限总存量都被「聚积」到一侧,或者说「受欢迎偏向」的流量就此耗尽了。因此,支付网络会频仍泛起通道流量耗尽,不得不再次「上链」打开新通道的情形。再平衡(rebalancing)手艺通过以下方式试图缓解这一问题。
例如下图中, 我们思量一个由四条边组成的回路,他们主流偏向的 10 单元余量都已经耗尽。
其中每个箭头
示意一个毗邻了 A 与 B 的无向通道,其中 A 方存量是 a,B 方存量是 b。值得注重的是,箭头偏向代表了主流偏向,因而我们画成了一个有向图,不外最新基于 RbR 的支付通道都是双向的。Revive 通过一个来自全局 leader 的协调(本文中,我们不予思量这个 leader 是若何实现的),完成一个 rebalance 事情。例如,可以协调 B 向 A 转账 5 个单元,协调 A 向 C 转账 5 个单元,协调 C 向 D 转账 5 个单元,协调 D 向 B 转账 5 个单元,使得全图结构如下图所示。其本质上是找到一个「回路」,并在这个回路上让所有通道一起逆着主流偏向回流、抵回一些流量。
当我们提及 Rebalance 时,到底在试图解决哪些问题? 笔者以为,要害需要解决两个问题:
第一个问题是已知全图求调剂方案的问题(将在之后着重先容)。
第二个问题是协议问题:有谁来实现上述的运算历程?若是是以个体实体节点(leader)完成,若何让他们即时收取到一部分图的实时信息并作出 rebalance 决议?若何规避他们作恶?若是是以一种去中央化的方式实现,又若何使信息网络、运算和实行三个环节成为可能?若何让网络节点介入并遵照我们想要设定的规则?
本文中,我们先抛开第二个问题,专注于第一个问题。
支付网络中现有的 rebalancing 问题可以被这样抽象描绘:
给定一个支付网络,寻找足够多的回路,最大化可以调整的流量。无疑这是个线性规划问题。
现有的思绪(即 Revive 事情的思绪)是直接解这一个线性规划问题。然则,直接求解这个线性规划问题的价值是异常昂贵的(对于当前支付网络规模而言尚可,但对于一个具有成百万上亿节点的未来设想支付网络不可行)。最新的线性规划算法理论复杂度为 O(M^w),其中 M 为变量和约束条件个数,w 是一个略小于 3 的常数。对于当前具有万级别节点的支付网络而言这个复杂度可以接受,不外我们以为这个复杂度对于未来具有百万上亿级别节点的支付网络来说,高了一些。但也没高太多!倘若能把复杂度稍微优化下去一些,就可以接受了。
接下来,我们将给出我们的解决思绪。不外在此之前,我们先先容一些需要的基础知识。
需要的准备知识 图论基础(强连通分量)
对于一个有向图,一个强连通分量指一个随便两点之间可以相互由图上有向边访达的子图。一个极大强连通分量是一个增添任何一个其它节点后就不具备强连通分量性子的子图。例如上图中,我们可以用灰色区域勾勒出它的四个极大强连通分量。
我们可以观察到以下方面:
极大强连通分量对任何一个有向图的所有节点完成了一个 partition。
任何一个回路只会存在在同一个极大强连通分量内。
存在一个极高效的 O(N) 算法求出任一有向图的所有极大强连通分量(详细算法本文中不赘述)。
其中 N 是全网节点数目。
将每个极大强连通分量看作一个整体,用边毗邻所有有访达关系的分量并缩点后,我们获得了一个有向无环图。
详细优化设施 接下来,我们先容详细算法。
首先,我们对原支付网络图做一个简化幻化,将每一个双向通道变换为从存量多的一方指向存量少的一方的有向边,边的容量是两头存量差的一半。例如下图中,我们将上图变换为下图。
于是,我们将寻找回路问题转化成了寻找有向图环路的问题。有向图的每一条边代表了一个为了让原图的对应通道加倍平衡需要回流流量的一个「势能」。每一个环路可以被看作一个回流方案。在举行强连通分量缩点后,我们只需要通过现有线性规划解每一个极大强连通分量内部的 rebalance 问题。
其解决方案便已晴朗:只需要求解出这个有向图的所有极大强连通分量,并且在每一个极大强连通分量中通过通例的线性规划,求得一个最优的调剂方案。由于我们以为每个回路并不会跨两个差别的极大强连通分量,以是我们以为这个方式求出的就是全局的最优调剂方案。
这里实在有个小问题:这真的是个等价转换吗?实事求是地说并不是(虽然乍看是的)。有可能会泛起最优全局调剂方案中有回路横跨两个极大强连通分量的情形,由于有可能会泛起「需要为了多数人苦一苦少数人」(「需要让少数边加倍不平衡来让更多边变得更平衡」)能获得更优解的可能性。不外笔者暂时以为这种误差是值得的。况且,涉及到现实落地,兴许那些少数人并不会接受这样的调剂。
仔细的读者们应该发现了本文中的两个没有注释清晰的问题:
1. 到底优化了若干? 这个问题,本质上在问未来的大规模支付网络会有若干个极大强连通分量,分量越多,优化效果就越显著。本质上这个问题是未来大规模支付网络的拓扑结构是怎么样的。可以预期的是,若是绝大多数群众节点的度数只有 4 度左右,极大强连通分量的期望数目是关于网络节点数目以一种低于线性的速率增进的。 2. 上文中的(伪)等价转化牺牲了若干? 实在,这两个问题本质上都在问:未来的大规模通道网络的拓扑结构究竟是怎么样的?笔者以为,这个问题不只笔者回覆不了,生怕也没有人能准确回覆的了。这一点笔者已经在之前的文章「一份关于支付网络中路由问题的周全研究」中给出了注释。
加入新手交流群:每天早盘分析、币种行情分析
添加助理微信,一对一专业指导:chengqing930520
上一篇:项目分析的有用度与复杂度关系,以Cover举例加入新手交流群:每天早盘分析、币种行情分析,添加助理微信
一对一专业指导:chengqing930520
最新资讯