一种基于图流分割的区块链动态分片扩展方法

1.本发明属于区块链技术、分布式存储领域，更具体地指一种基于图流分割的区块链动态分片扩展方法。

背景技术：

2.区块链技术是基于点对点对等网络，但是较弱的可扩展性严重影响了区块链中性能提升。分片技术是一种实用的区块链横向扩展方案。通过将区块链网络划分为多个分片，不同分片之间并行的处理交易，可以提高系统的整体的交易吞吐量和处理速率；拜占庭共识通常需要多轮的消息传播和回送，其复杂度与网络中的节点数量呈指数上升的关系，每个分片内的节点数相比整体来说更少，能大幅度提升共识速度。
3.然而，分片的数量不是多多益善，在恶意节点概率相等的情况下，每个分片中的节点数量和安全性呈倒指数型关系。此外，在实际的系统中，节点不是稳定不变的，在节点动态进出的状态下，分片状态也不可能始终保持不变。分片状态的改变同时伴随了数据的复制和转移，并且我们希望互相交易频繁的节点更能够在同一分片中，以达到减少跨片交易和负载均衡的效果。
4.目前主流对于区块链分片中跨片交易的处理通常有客户端主动维护、基于trace标注、交易分裂等；其中最典型的就是以ethereum为代表的交易分裂方案，将一个交易的转移过程切割，分成发送和接受两个过程，并在不同的共识周期完成，但这种做法破坏了交易的原子性，目前还不成熟。

技术实现要素：

5.本发明提供一种基于图流分割的区块链动态分片扩展方法，以解决现有区块链方案中效率不高，安全性挑战大，跨片交易多以跨片处理效率低等问题；本发明提高了区块链业务吞吐量，降低跨链比例，并在保证安全性的前提下尽可能地负载均衡。
6.为了解决上述技术问题，本发明的技术方案为：
7.一种基于图流分割的区块链动态分片扩展方法，所述动态分片扩展，即区块链根据当前网络状况动态更新分片状态；所述的图流分割是根据每一笔交易的输入方和输出方作为一条边的两端节点，所有产生的交易而形成的一个图数据流，依据图数据流分割算法，对整个交易状态图即区块链节点网络进行分割从而达到分片的目的；所述的方法是根据epoch(分代)周期来进行，每一个epoch周期包含了交易打包和状态更新过程，经过一个epoch，分片状态会根据交易图产生变化，达到负载均衡和降低安全风险的作用。具体的，包括如下步骤：
8.步骤一：节点通过运行哈希函数，计算出符合当前target的目标nonce值，并根据当前的分片数量进行取模运算，得到的结果就是该节点所属的分片的序号，节点需要发起一条准入交易，该交易被成功打包出块后，在下一个epoch该节点可以发起正式交易；
9.步骤二：交易过程中每个分片打包本分片交易池中的交易数据并出块，每个epoch
的第一个交易区块的前置为上一epoch的状态区块，整个系统的区块结构呈拓扑图状结构，每个epoch收敛于一个状态区块；
10.步骤三：执行图流分割算法
11.每个节点持续的从新产生的区块中读取交易信息并更新当前所有节点的状态图，当本epoch结束，状态图同时也会确定，交易信息作为图流分割算法的输入，所述交易信息包括状态图和交易的账户；
12.步骤四：在步骤三中将图状态与账户分割后，区块链系统对分割的结果达成共识，这个阶段的共识采用pbft算法，并生成一个状态区块，该状态区块作为当前所有分片的收敛区块，表示当前epoch的结束；
13.步骤五：当前epoch的状态区块达成共识后，相关联的分片根据区块内容进行状态转移后变更，以便开始新一轮的交易。
14.作为优选，所述节点包括普通节点和委员会节点，所述普通节点用于发起交易的节点，所述委员会节点则组成委员会，分别用于处理跨篇交易和分片状态重构的计算。
15.作为优选，所述步骤二中，所述拓扑图状结构中区块的排序的采用pbft共识算法，在一个epoch内产生的区块数量取决于当前的网络状态。
16.作为优选，所述步骤二中，对于跨片交易，通过委员会节点作为中介结合交易锁定和双重确认机制来确保跨片交易的原子性。
17.作为优选，所述委员会节点形成是通过质押指定数量的来获得被选举资格，其余节点可以投票选举出委员会，每个分片至少包含一个委员会成员。
18.作为优选，所述步骤二中，执行图流分割算法的依据是：分片之间的负载均衡、区块链系统的安全性、分片之间复制的通讯代价。
19.作为优选，采用hdrf-p图流分割算法，根据节点的度信息判断其关联的边分到哪个子图(子分片)中，分割的优化过程就是求交易图的最小割，最小割能够减少节点之间的通信代价，也能使得分布式系统中的多个和节点负载均衡，避免少数节点和分片负载过高导致过热。在根据交易流优化最优解的过程中，还要考虑边界条件，即安全性保证，每个分片的数量不能低于阈值，否则分片被操控就会产生安全性问题。
20.作为优选，所述hdrf-p算法是以hdrf图流分割算法为基础
21.算法的输入v1,v2n分别表示一条边的两个点，节点总数，由于hdrf算法需要给出划分数量，所以根据节点数以及pbft算法的安全性保证：
22.n＝3f+1
23.其中n表示节点总数，f表示拜占庭节点数量；
24.可以得到划分数量k，其中n表示节点总数，μ表示恶意节点的比例：
[0025][0026]
分配一条边时，为每个子图计算一个目标函数值，选择值最高的子图分配，其目标函数由两部分组成，
[0027]
第一部分
[0028]
的含义是两个或两个以上。
[0042]
在本发明的描述中，需要说明的是，除非另有明确的规定和限定，术语“安装”、“相连”、“连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通。对于本领域的普通技术人员而言，可以通过具体情况理解上述术语在本发明中的具体含义。
[0043]
本发明提供了一种基于图流分割算法的区块链动态分片扩展方法，如图1所示，该系统中分为普通节点和委员会节点，普通节点就是发起交易的节点，委员会节点则组成委员会，委员会的作用有两个，分别是处理跨篇交易和分片状态重构的计算。该系统以一个epoch为周期，每个周期会动态改变分片状态；在每一个epoch，包含委员会选举、交易打包(包含跨片交易)、图分割与分片状态转换。
[0044]
所述委员会选举，想要竞选成为委员会的节点，通过质押一定的来获取被选举权，其余普通节点通过选举选择委员会成员，委员会要求每个分片都至少包含一个委员会成员。
[0045]
所述交易打包也即分片中矿工对当前epoch的交易池中的交易排序并出块的过程，共识基于pbft算法，对于交易中的跨片交易，通过委员会节点生成证明并锁定，再将证明发送给另一个分片实现分步跨片。
[0046]
所述图分割，在所有分片中的交易打包过程中，所生成的已确认交易作为交易图的边产生图流输入，根据图流分割算法：交易过热的分片负载均衡到热度较低的分片，根据局部性原理，交易尽量保持在分片之内从而减少跨片交易，每个分片的节点数量不能低于安全性阈值。分割后，产生下一epoch的状态区块并广播给所有分片。
[0047]
所述状态转换，就是根据新的状态图进行状态更新，从而得到下一轮的分片状态以及委员会。
[0048]
具体地实施步骤如下所述：
[0049]
步骤一：节点通过运行pow算法，得到一个合法的nonce，并将该结果作为一条交易添加进交易池中，在本epoch出块时将准入信息打包，并在下一epoch生效，节点所属的分片根据nonce结果取模当前分片数量得到，此时节点方可正常进行交易行为。
[0050]
步骤二：想要竞选成为委员会成员的节点，通过质押指定数量的来获得被选举资格，其余节点可以投票选举出委员会，每个分片至少包含一个委员会成员。
[0051]
步骤三：每个分片有独立的交易池，以分片为单位进行出块操作，具体的，矿工对交易进行打包和排序，然后运行pbft共识算法对排序结果取得共识；每个epoch的第一个交易区块以状态区块为前置，既保持了区块链的线性结构，也提高了篡改的成本。
[0052]
对于跨篇交易，具体的，以交易：将第一个分片中的账户的钱转到第二个分片中的账户为例，分为以下三个步骤进行：
[0053]
交易输出方发起交易，若是跨片交易则将其路由到本分片中的委员会节点；
[0054]
交易输出方委员会节点生成一个签名，用于证明其账户中确实有可用的钱，同时将这笔钱锁定；
[0055]
交易输出方委员会节点将该证明路由到交易输入方的委员会节点，对签名进行验证，验证成功则完成交易，将本条跨片交易分别写入输入方和输出方的交易池中；若验证失
败，则说明交易输出方余额不足，则交易失败，回送失败信息给交易输出方委员会节点，执行解锁操作。
[0056]
步骤四：交易完成以后，把所有的交易作为图的边，账户作为点，就构成以一个交易图；这里我们需要把整个交易图分割成多个分片，采用hdrf-p图流分割算法，根据节点的度信息判断其关联的边分到哪个子图(子分片)中，分割的优化过程就是求交易图的最小割，最小割能够减少节点之间的通信代价，也能使得分布式系统中的多个和节点负载均衡，避免少数节点和分片负载过高导致过热。在根据交易流优化最优解的过程中，还要考虑边界条件，即安全性保证，每个分片的数量不能低于阈值，否则分片被操控就会产生安全性问题。
[0057]
完整的hdrf-p算法，如图2所示，该算法是基于hdrf图流分割算法改进，hdrf算法主要应用于大数据与分布式存储领域。
[0058]
算法的输入v1,v2n分别表示一条边的两个点，节点总数，由于hdrf算法需要给出划分数量，所以根据节点数以及pbft算法的安全性保证：
[0059]
n＝3f+1
[0060]
其中n表示节点总数，f表示拜占庭节点数量；
[0061]
可以得到划分数量k，其中n表示节点总数，μ表示恶意节点的比例：
[0062][0063]
分配一条边时，为每个子图计算一个目标函数值，选择值最高的子图分配，其目标函数由两部分组成，
[0064]
第一部分
[0065][0066]
为对该子图的大小的惩罚项，由一系数λ控制其权重；
[0067]
第二部分
[0068][0069]
表示的是该子图对两个点v1,v2的包含情况，若不包含任一个，则为0，若包含其中一个，则在区间(1，2)内，若两个都包含，则为最大值3，而当只包含其中之一时，根据的计算方式g(v1,i)，包含度数较低的点会具有更高的值，以此来实现优先分割高度数的点，
[0070]
此外在选择边所属的分割的中额外加入了一个约束：
[0071][0072]
该约束下在选择所述分割时优先保证安全性，其次考虑边的权重，这样限制了每个分割不能无限大，也不会过小，始终在pbft算法的安全性范围之内。
[0073]
步骤五：将网络分片后，需要系统对分片结果达成共识，系统运行pbft共识算法，分片结果作为共识内容，并生成一个状态区块，广播给所有分片；此区块既是当前epoch交易区块的收敛区块，同时作为下一epoch的前置区块，区块结构呈现动态伸缩的状态。
[0074]
步骤六：节点收到广播的分片后进行状态的转换，也就是分片的进行打散然后重
组，重复上述步骤。
[0075]
以上结合附图对本发明的实施方式作了详细说明，但本发明不限于所描述的实施方式。对于本领域的技术人员而言，在不脱离本发明原理和精神的情况下，对这些实施方式包括部件进行多种变化、修改、替换和变型，仍落入本发明的保护范围内。

技术特征：

1.一种基于图流分割的区块链动态分片扩展方法，其特征在于，包括如下步骤：步骤一：节点通过运行哈希函数，计算出符合当前target的目标nonce值，并根据当前的分片数量进行取模运算，得到的结果就是该节点所属的分片的序号，节点需要发起一条准入交易，该交易被成功打包出块后，在下一个epoch该节点可以发起正式交易；步骤二：交易过程中每个分片打包本分片交易池中的交易数据并出块，每个epoch的第一个交易区块的前置为上一epoch的状态区块，整个系统的区块结构呈拓扑图状结构，每个epoch收敛于一个状态区块；步骤三：执行图流分割算法每个节点持续的从新产生的区块中读取交易信息并更新当前所有节点的状态图，当本epoch结束，状态图同时也会确定，交易信息作为图流分割算法的输入，所述交易信息包括状态图和交易的账户；步骤四：在步骤三中将图状态与账户分割后，区块链系统对分割的结果达成共识，这个阶段的共识采用pbft算法，并生成一个状态区块，该状态区块作为当前所有分片的收敛区块，表示当前epoch的结束；步骤五：当前epoch的状态区块达成共识后，相关联的分片根据区块内容进行状态转移后变更，以便开始新一轮的交易。2.根据权利要求1所述的基于图流分割的区块链动态分片扩展方法，其特征在于，所述节点包括普通节点和委员会节点，所述普通节点用于发起交易的节点，所述委员会节点则组成委员会，分别用于处理跨篇交易和分片状态重构的计算。3.根据权利要求1所述的基于图流分割的区块链动态分片扩展方法，其特征在于，所述步骤二中，所述拓扑图状结构中区块的排序的采用pbft共识算法，在一个epoch内产生的区块数量取决于当前的网络状态。4.根据权利要求2所述的基于图流分割的区块链动态分片扩展方法，其特征在于，所述步骤二中，对于跨片交易，通过委员会节点作为中介结合交易锁定和双重确认机制来确保跨片交易的原子性。5.根据权利要求4所述的基于图流分割的区块链动态分片扩展方法，其特征在于，所述委员会节点形成是通过质押指定数量的来获得被选举资格，其余节点可以投票选举出委员会，每个分片至少包含一个委员会成员。6.根据权利要求1所述的基于图流分割的区块链动态分片扩展方法，其特征在于，所述步骤二中，执行图流分割算法的依据是：分片之间的负载均衡、区块链系统的安全性、分片之间复制的通讯代价。7.根据权利要求1所述的基于图流分割的区块链动态分片扩展方法，其特征在于，采用hdrf-p图流分割算法，根据节点的度信息判断其关联的边分到哪个子图中，分割的优化过程就是求交易图的最小割，最小割能够减少节点之间的通信代价，也能使得分布式系统中的多个和节点负载均衡，避免少数节点和分片负载过高导致过热，在根据交易流优化最优解的过程中，还要考虑边界条件，即安全性保证，每个分片的数量不能低于阈值，否则分片被操控就会产生安全性问题。8.根据权利要求7所述的基于图流分割的区块链动态分片扩展方法，其特征在于，所述hdrf-p算法是以hdrf图流分割算法为基础
算法的输入v1,v2n分别表示一条边的两个点，节点总数，由于hdrf算法需要给出划分数量，所以根据节点数以及pbft算法的安全性保证：n＝3f+1其中n表示节点总数，f表示拜占庭节点数量；可以得到划分数量k，其中n表示节点总数，μ表示恶意节点的比例：分配一条边时，为每个子图计算一个目标函数值，选择值最高的子图分配，其目标函数由两部分组成，第一部分为对该子图的大小的惩罚项，由一系数λ控制其权重；第二部分表示的是该子图对两个点v1,v2的包含情况，若不包含任一个，则为0，若包含其中一个，则在区间(1，2)内，若两个都包含，则为最大值3，而当只包含其中之一时，根据的计算方式g(v1,i)，包含度数较低的点会具有更高的值，以此来实现优先分割高度数的点，此外在选择边所属的分割的中额外加入了一个约束：

技术总结

本发明公开了一种基于图流分割的区块链动态分片扩展方法，所述动态分片扩展，即区块链根据当前网络状况动态更新分片状态；所述的图流分割是根据每一笔交易的输入方和输出方作为一条边的两端节点，所有产生的交易而形成的一个图数据流，依据图数据流分割算法，对整个交易状态图即区块链节点网络进行分割从而达到分片的目的；所述的方法是根据epoch(分代)周期来进行，每一个epoch周期包含了交易打包和状态更新过程，经过一个epoch，分片状态会根据交易图产生变化，以解决现有区块链方案中效率不高，安全性挑战大，跨片交易多以跨片处理效率低等问题；本发明提高了区块链业务吞吐量，降低跨链比例，并在保证安全性的前提下尽可能地负载均衡。可能地负载均衡。可能地负载均衡。