一种动态分层的高效PBFT算法的制作方法

一种动态分层的高效pbft算法
技术领域：
：1.本发明涉及区块链
技术领域：
：，尤其是一种动态分层的高效pbft算法。
背景技术：
：：2.近些年，区块链技术在许多领域都是研究的热点，尤其是互联网金融领域更是将区块链技术广泛深刻地应用。一切涉及到中心化账本技术的领域都有可能存在区块链的应用前景，可以说区块链是一种既有效率又值得信任的分布式账本技术。去中心化、不可篡改以及具有较高的安全性是区块链的显著特点。3.在区块链系统中，共识算法用于解决去中心化多方互信的问题。目前，联盟链大多采用的是pbft算法，pbft（practicalbyzantinefaulttolerance）算法是一个能够容忍拜占庭错误的分布式系统共识算法，pbft算法采用密码学算法保证节点之间的消息传送是不可篡改的，按照少数服从多数原则，由主节点提交消息其他共识节点进行验证和确认，pbft算法能容忍f个拜占庭节点（恶意节点），为了保障整个区块链网络可以正常运转，需要有2f 1个正常节点，系统的总节点数为。也就是说，pbft算法可以容忍小于1/3个无效或者恶意节点。其优点在于可以容忍任何类型的错误，消息验证和记账由多人协同完成。但是，pbft算法受其时间复杂度的影响，当区块链网络中节点数量较多的时候，系统的共识效率急剧下降，由此可以看出传统的pbft算法并不能满足实际应用场景中节点数量较多的区块链系统；当恶意节点当选为主节点导致共识失败时，传统的pbft算法只是进行视图切换的方式来解决，恶意节点仍然存在于区块链系统中并且仍然有当选为主节点的可能，从而影响共识效率。技术实现要素：4.一种动态分层的高效pbft算法，包括如下步骤：步骤1：根据节点网络的状况、可靠性和节点的系统性能在节点加入联盟链时对节点进行审核，确定代理节点和普通节点；步骤2：根据随机平均分组算法进行节点的分组，以选取的代理节点为各组的主节点，当系统中由于全局或者组内拜占庭节点数量较多需要重新分组时，则重新选择信任度高的节点作为代理节点进行重新分组；步骤3：在组内实施简化的pbft算法，将组内共识的结果传到组内的代理节点，代理节点负责收集和验证组内的共识结果，并代表各个组参与全局的pbft算法。5.上述的一种动态分层的高效pbft算法，所述步骤2中代理节点根据节点的积分高低进行选举，积分高的节点会优先被选举为组内代理节点，其余节点负责投票。6.上述的一种动态分层的高效pbft算法，所述节点的积分是由节点积分制度实时计算节点的积分。7.上述的一种动态分层的高效pbft算法，所述节点积分制度具体为：将节点的积分状态标记为great、good、normal、bad，相应的分值为2、1、0、‑1，节点刚加入区块链时状态为good，此时节点有竞选代理节点、投票和参与共识的权利，节点积分状态为great时为候补代理节点或代理节点，节点积分状态为normal时只能进行投票和同步区块，可以参与共识，不能参与代理节点的竞选，节点积分状态为bad时禁止投票，禁止参与共识和竞选代理节点。8.上述的一种动态分层的高效pbft算法，所述节点积分制度的具体积分增减制度为：普通节点选举的代理节点出块成功且成功同步区块，则普通节点积分 1；若普通节点选择的代理节点被验证为拜占庭节点，则选举节点积分‑1，被选举节点积分‑2；若节点是代理节点且成功出块则积分 2；若代理节点出块失败则积分‑2。9.上述的一种动态分层的高效pbft算法，所述步骤2系统通过节点审查员对拜占庭节点进行审核判断和处理，将拜占庭节点拉进黑名单，并将拜占庭节点放到拜占庭节点组中。10.上述的一种动态分层的高效pbft算法，所述节点审查员管理所有节点信息，管理节点的动态进出，并且维护一个记录节点身份信息的nit表，且所有节点完全信任节点审查员维护的nit表中的信息。11.上述的一种动态分层的高效pbft算法，每个节点在本地维护一个nit表，并实时的与其他节点的nit表进行同步。12.上述的一种动态分层的高效pbft算法，所示步骤3在组内实施简化的pbft算法的具体步骤包括：步骤3.1：请求阶段：向分布式系统中的全局主节点p发送请求，请求形式如下所示，其中：request为消息名称包括消息内容m以及消息摘要d，o为请求的具体操作，t为请求时客户端追加的时间，c为客户端标识，θ是节点审查员的nit表；步骤3.2：全局预准备阶段：全局的主节点p为请求request分配一个序号n，全局的主节点p向系统中所有节点广播global‑pre‑prepare的消息，并将m附加到所有活跃的代理节点中，将消息m附加到其日志中，并启动计时器t1，消息形式如下所示，其中m是消息内容，v是发送m的视图编号，d是消息摘要，t是发送global‑pre‑prepare消息的时间，θ是主节点的本地nit表，σp是节点p的签名；；步骤3.3：向组织内的代理节点回复一个local‑prepare消息，并将消息添加到它的日志中，消息形式如下，其中m是消息内容，v是发送m的视图编号，n是全局的主节点p为请求request分配的序号，d是消息摘要，t代表发送local‑prepare消息的时间，θ是主节点的本地nit表，i是节点的节点号，σi是节点i的签名；步骤3.4：代理节点接收到来自不同的活跃的节点的2f 1正确local‑prepare消息后，它将发送消息给组织内所有活跃的节点，消息形式如下所示，其中，ψ表示代理节点接收到的2f 1正确local‑prepare消息集，v表示发送m的视图编号，θ是主节点的本地nit表，c‑t代表发送local‑prepare‑confirm消息的时间，σp是节点p的签名，组织内其他节点收到消息后对签名进行校验，并检查v、θ是否正确，验证通过节点i进入local‑commit；；步骤3.5：节点i进入本地提交local‑commit阶段，消息被发送到代理节点，消息形式如下所示，其中，v表示发送m的视图编号，n是全局的主节点p为请求request分配的序号，d是消息摘要，θ是主节点的本地nit表，i是节点的节点号，σi是节点i的签名；步骤3.6：代理节点接收2f 1的local‑commit信息后对消息进行验证，当代理节点接收到来自不同的活跃的节点的2f 1正确local‑commit消息后，代理节点发送消息是对所有活动备份的多播，消息形式如下所示，其中ψ是一组2f 1正确的local‑commit消息，v表示发送m的视图编号，n是全局的主节点p为请求request分配的序号，d是消息摘要，θ是主节点的本地nit表，c‑t是local‑commit‑confirm消息的发送时间，i是节点的节点号，σp是节点p的签名；步骤3.7：组织内节点收到主代理节点发送的local‑commit‑confirm消息后，如果对local‑commit‑confirm消息验证成功，则执行请求local‑reply并回复给代理节点。附图说明13.下面结合附图和实施例对本发明进一步说明。14.图1为本发明dhe‑pbft算法流程图；图2为nit表示意图；图3为节点转换示意图；图4为随机平均分组算法示意图；图5为组内共识和组件共识示意图；图6为相同节点数量不同分组时间复杂度对比图；图7为相同分组不同节点数量时间复杂度对比图；图8为dhe‑pbft算法与pbft算法共识时延对比图。具体实施方式15.为使本领域技术人员更好的理解本发明的技术方案，下面结合附图和具体实施方式对本发明作详细说明。16.需要说明的是，本发明中公开的一种动态分层的高效pbft算法重新命名为dhe‑pbft算法，而本发明中的提到的pbft算法表示传统的pbft算法。17.本实施例dhe‑pbft算法中，假设存在一个异步分布式系统，其中节点通过网络相互连接。系统中的节点分为三类：代理节点、候补节点、普通节点和节点审查员。18.代理节点：在网络初选阶段，由系统选取的几个可靠的、网络状态稳定的节点，主要是查看此节点出现宕机的情况和响应时间，在进行代理节点选择时会事先进行节点的网络状况测试，发送相同的消息到各个节点上，并且查看各个节点的响应时间和宕机(失联)次数，优先选举响应时间短并且没有宕机的节点当选为代理节点。在经过了几轮共识之后，如果这几个代理节点出现拜占庭错误或者是宕机，这时相应的组内将进行代理节点的选举。代理节点的积分较高，可以代表当前组织参与全局的pbft共识，生成区块，并且将信息传到组内节点，让组内进行区块信息的同步。19.候选节点：在参与代理节点的竞选中未被选举成为代理节点的积分高的节点，当代理节点出现拜占庭错误的时候，会优先从候选节点中直接选择成为代理节点。20.普通节点：具有投票和被投票的权利，可以参与代理节点的竞选(积分低于一定阈值的普通节点不能进行代理节点的竞选)，同步代理节点共识成功的块，参与组内共识(简化的pbft算法)。21.节点审查员(node‑examiner):管理所有副本的信息，管理节点的动态进出，并且维护一个记录节点身份信息的列表nit(nodeinformationtable,nit)，nit中存储的信息有：节点id、ip地址、公钥、节点状态(活跃、失联、邪恶)、属于哪个分组(g1、g2……)、积分数量、当前是否是主节点、节点身份(代理节点、候选节点、拜占庭节点或者普通节点)。所有节点完全信任节点审查员中记的身份信息，然而，为了避免对节点审查员安全的过度依赖，每个副本都会在本地维护一个nit表，实时的与其他节点的nit表进行同步。nit表如图2所示。22.本实施例高效pbft算法，如图1所示，包括如下步骤：步骤1：系统根据节点网络的状况、可靠性和节点的系统性能在节点加入联盟链时对节点进行审核，确定代理节点和普通节点；步骤2：随机平均分组以选取的代理种子节点为各组的主节点，根据随机平均分组算法进行节点的分组。当系统中由于共识故障(全局或者组内拜占庭节点数量较多时)需要重新分组的时候，则重新选择信任度高的节点当选为代理种子节点，进行重新分组，为了保证区块链系统的稳定，其中，f是系统内拜占庭节点的数量，组内的节点数量也应该满足。23.随机平均分组算法，如图4所示，procedurerandom(n,m)//procedurerandom是随机平均分组算法的函数，n和m是此随机平均分组算法中的两个参数，其中n是系统中所有结点的个数，m是分组数量；当区块链中的分组数量m大于等于4组并且每个组中的节点数量大于等于4个节点时，可以进行随机平均分组算法，执行for循环语句，否则执行else语句：分组m的数量不满足pbft共识算法，组内节点数量(n/m) 1不满足pbft共识算法；当区块链中的分组数量m大于等于4组并且每个组中的节点数量大于等于4个节点时执行for循环语句，其中i是分组编号(i=1,2……m)，g[i]表示第i组中的节点数量，当i不等于m时，g[i]=(n/m) 1；当i等于m时，g[m]=n‑(m‑1)[(n/m) 1](此结果是将剩余节点全部放入到最后一组中)，至此随机平均分组算法完成。[0024]节点的信任度由节点的积分决定，节点的积分制度实时计算节点的积分，将节点积分分为great、good、normal和bad四级，不同等级的节点有不同的权力和职责，可以完成相应的工作，我们将节点的积分状态标记为：great、good、normal、bad相应的分值2、1、0、‑1，great：有成为代理节点的可能，最差也是候补代理节点，当本组中参与全局共识的代理节点出现拜占庭错误的时候，组内会首先从候补代理节点中选择下一任代理节点，good：节点刚加入区块链时的状态时good，节点有竞选代理节点、给其他竞选代理节点的节点进行投票和参与共识的权力；normal：节点只能进行投票和同步区块，可以参与共识,不能参与代理节点的竞选；bad：节点禁止投票、参与代理节点的竞选和参与共识和投票。[0025]节点积分的增减规则：（1）当普通节点i选举的代理节点j，节点j出块成功，节点i自身验证消息成功，并且成功的同步区块则普通节点i积分加1（节点的积分最多就是2）；（2）如果节点i选择的代理节点j被验证是拜占庭节点，那么选举节点i积分‑1，被选举节点j积分‑2；（3）如果节点i是代理节点并且成功出块则节点i积分加2。(代理节点出块成功积分增加翻倍的原因，代理节点成功出块显然是正常的节点，防止选择到组内的拜占庭节点，因此将此节点分值提升，提升了此节点被选为代理节点的几率)；（4）如果代理节点i出块失败则积分‑2，同时相应的组选择候补节点j代替相应组的代理节点i；（5）当节点i积分等于0时，节点i只能投票和同步区块，不能参与竞选代理节点；（6）当节点i积分是‑1时，节点被禁止参与共识、禁止投票、禁止参与代理节点的竞选。[0026]各个节点的转换图如图3所示，其中a是代理节点（great），b是普通节点（great，good，normal），c是候补节点（great，good），d是拜占庭节点（bad）。[0027]系统的分组过程具体为：利用节点审查员首先检验要加入节点的网络状况和稳定性，并将其基本信息写入到nit表中(如图2)，由于联盟链的特性，随机分组会使得区块链网络难以维护，并且随机分组之后每个组内成员数量不同，其出现拜占庭错误的概率也难以预测，因此在本实施例中将采用ca机制进行网络节点的审查，并且选定n个网络稳定可靠的代理种子节点为初始的代理节点，例如：表nit中的nodeidentity中的proxynode就是代理节点，然后采用随机平均分组算法将其余的节点平均随机的分配到各个组中，通过随机平均分组算法可以知道每个组中允许储存的最大节点数量，当节点数量达到最大值的时候，会禁止其节点加入本组。将每个组的节点信息添加进nit表中，区块链网络中每个节点本地都会维护一个nit表，各个组的代理节点和其他节点可以根据nit表互相了解，根据表nit中的group就能够知道节点属于哪个分组。在共识过程中各组可能会出现的拜占庭节点，节点审查员会定期清理区块链网络，将低于一定阈值的节点(拜占庭节点)踢出网络，这样会造成分组内的节点数量小于稳定值，这样就会触发重新分组。[0028]当发生数图转换的时候，节点会根据nit表中的group的值，将相应组的拜占庭节点替换掉，依次选择nit表中nodeidentity中的candidatenode的节点作为新的代理节点，这样选择积分高的可信的节点做为代理节点，可以有效地减少拜占庭错误，减少视图切换的次数，提高共识效率。[0029]步骤3：在组内实施简化的pbft算法，将组内共识的结果传到组内的代理节点，代理节点负责收集和验证组内的共识结果，并代表各个组参与全局的pbft算法。组内实施简化的pbft算法的具体步骤如下：request：客户端向分布式系统中的全局的主节点p发送请求，请求形式如下所示，其中：request为消息名称(包含消息内容m，以及消息摘要d)，o为请求的具体操作，t为请求时客户端追加的时间，c为客户端标识，θ是node‑examiner的nit表，客户端节点通过查看nit表将request的消息发送到的“当前是否是全局主节点”中为yes的节点上，然后请求结束。[0030]global‑pre‑prepare：global‑pre‑prepare阶段，全局的主节点p为请求request分配一个序号n，全局的主节点p向系统中所有节点广播global‑pre‑prepare的消息，并将m附加到所有活跃的代理节点中，将消息m附加到其日志中，并启动计时器t1，消息形式如下所示，其中m是消息内容，v是发送m的视图编号，d是消息摘要，t是发送global‑pre‑prepare消息的时间，θ是主节点的本地nit表，σp是节点p的签名。[0031]所有的节点接收global‑pre‑prepare消息，并且检查global‑pre‑prepare消息中的签名是正确的，global‑pre‑prepare在视图v中，并且验证节点本地的nit与globalpre‑prepare消息中的nit相同，它没有接受带有相同v、θ和n但包含不同的消息摘要d的global‑pre‑prepare消息，global‑pre‑prepare消息中的序列号n介于低水位线h和高水位线h之间。h和h的定义与pbft中的定义相同。[0032]local‑prepare：当所有节点都接受global‑pre‑prepare消息时，组织内的节点i将进入local‑prepare阶段，向组织内的代理节点回复一个local‑prepare消息，并将消息添加到它的日志中。消息形式如下，其中m是消息内容，v是发送m的视图编号，n是全局的主节点p为请求request分配的序号，d是消息摘要，t代表发送local‑prepare消息的时间，θ是主节点的本地nit表，i是节点的节点号，σi是节点i的签名。[0033]local‑prepare‑confirm:当代理节点从组织内其他节点接收local‑prepare消息时，执行local‑prepare消息验证。当代理节点接收到来自不同的活跃的节点的2f 1正确local‑prepare消息后，它将发送消息给组织内所有活跃的节点，消息形式如下所示，其中，ψ表示代理节点接收到的2f 1正确local‑prepare消息集，v表示发送m的视图编号，θ是主节点的本地nit表，c‑t代表发送local‑prepare‑confirm消息的时间，σp是节点p的签名。[0034]。[0035]组织内其他节点收到local‑prepare‑confirm消息后，对签名进行校验，并检查v、θ是否正确。然后，查看中代理节点接收到的2f 1正确local‑prepare消息集，当验证通过时节点i进入local‑commitphase。[0036]local‑commit：localcommitphase的方案类似于本地准备阶段localpreparephase。采用了相同的优化思想，节点i进入本地提交local‑commitphase阶段，消息被发送到代理节点，消息形式如下所示，其中，v表示发送m的视图编号，n是全局的主节点p为请求request分配的序号，d是消息摘要，θ是主节点的本地nit表，i是节点的节点号，σi是节点i的签名。[0037]local‑commit‑confirm:代理节点接收2f 1的local‑commit信息后(其中一个是由主节点生成)对消息进行验证，当代理节点接收到来自不同的活跃的节点的2f 1正确local‑commit消息后，代理节点发送消息是对所有活动备份的多播，消息形式如下所示，其中ψ是一组2f 1正确的local‑commit消息，v表示发送m的视图编号，n是全局的主节点p为请求request分配的序号，d是消息摘要，θ是主节点的本地nit表，c‑t是local‑commit‑confirm消息的发送时间，i是节点的节点号，σp是节点p的签名。[0038]组织内节点收到主代理节点发送的local‑commit‑confirm消息后，如果对local‑commit‑confirm消息验证成功，则执行请求local‑reply并回复给代理节点，组内共识结束。[0039]然后由组内的代理节点执行全局共识，全局共识采用的是传统的pbft算法，这里就不在详述，组内共识和组间共识如图5所示。[0040]针对本实施例提出的dhe‑pbft算法，进行了仿真实验，通过golang实现pbft和dhe‑pbft算法，使用不同的通信端口代替大量节点，节点之间的交互使用tcp协议，模拟分布式系统共识过程。环境中包含rsa信息加解密过程和网络信息传递延迟，实验环境：系统:ubuntu20.04,cpu:inteli7‑11370h3.30ghz4核，内存16g，硬盘pcl‑e512g固态硬盘，golang版本：go1.16。[0041]安全性分析：在dhe‑pbft算法中全局共识采用的是传统的pbft算法的过程，因此全局共识的算法是安全的，组内是对传统的pbft算法的prepare和commit阶段进行优化，这两个阶段的优化是在这两个阶段内部执行的，节点还需要接收2f 1正确的消息才能达到各阶段的共识，因此，它不影响原pbft方案的安全性和活性。同时还提升了系统的共识效率。[0042]通信复杂度分析：传统的pbft算法的各个阶段n个节点的时间复杂度和总共的时间复杂度，pre‑prepare阶段是n‑1，prepare阶段是(n‑1)(n‑1)，commit阶段是n(n‑1)，总共的通信次数是2n(n‑1)。[0043]改进后的pbft算法的各阶段时间复杂度和总共的时间复杂度，假设系统中由n个节点，分成m个组，每组n/m个节点(当每组节点相同时)，global‑pre‑prepare阶段n‑1，local‑pre‑prepare阶段n/m‑1，local‑prepare阶段n/m‑1，local‑prepare‑confirm阶段n/m‑1，local‑commit阶段n/m‑1，local‑commit‑confirm阶段n/m‑1，local‑reply阶段n/m‑1,global‑prepare阶段(m‑1)(m‑1)，global‑commit阶段m(m‑1)，总共的时间复杂度是。[0044]相同节点数量不同分组情况下的通信复杂度对比，如图6，横轴为节点数量和时间复杂度，纵轴为时间复杂度。从图6中可以看出当节点数量不变的情况下，pbft算法的通信复杂度保持稳定，并且通信复杂度很高，dhe‑pbft算法的时间复杂度随着分组的不同而变化，在分为5组每组20个结点的时候通信复杂度最低，由此可见分组方式的不同也会影响共识算法的效率。[0045]当分组数量确定，节点数量不同时，如图7所示，横轴为节点数量和分组情况，纵轴为时间复杂度，将节点平均分成5组，当节点数量逐渐增大的时候，pbft算法的时间复杂度急剧增加，而dhe‑pbft算法的时间复杂度总体趋于稳定。[0046]本实施例还进行了dhe‑pbft算法共识时延实验：共识时延是指从交易提交到交易完成之间所消耗的时间，是衡量共识算法运行速度的重要指标，较低的共识时延使得交易可以快速得到确认，区块链安全性更高，同时也能变得更为实用。测试的共识时延为区块完成一次共识过程的时间，用公式定义时延为：其中delaytime表示时延，finishtime表示区块确认完成的时间，starttime表示提案开始的时间。为了验证dhe‑pbft算法在实际应用中低时延的特点，将dhe‑pbft算法与原始pbft算法进行对比，对比结果如图8所示，图8横轴为不同节点数量分为4组的分组方式，纵轴为共识时延，当客户端发送交易请求时pbft算法和dhe‑pbft算法在完成交易的情况下的共识时延，可以看出pbft随着节点数量增加，共识时间迅速增加，而本文dhe‑pbft共识由于分组分层，在分组数固定的情况下，组间共识时间基本不变，而组内共识时延增长为线性增长，从横坐标可以看出组内的节点数量增加缓慢，其共识时延也增加缓慢，最终dhe‑pbft算法的整体达成共识时间增加缓慢。从图8中可以看出，当节点数量众多的时候，pbft算法的共识时延会急剧增长，共识效率会急剧下降，而本文的dhe‑pbft算法的共识时延不会有显著的增长，适合节点众多的情况。[0047]以上实施例仅为本发明的示例性实施例，不用于限制本发明，本发明的保护范围由权利要求书限定。本领域技术人员可以在本发明的实质和保护范围内，对本发明做出各种修改或等同替换，这种修改或等同替换也应视为落在本发明的保护范围内。当前第1页12当前第1页12