一种基于分组的区块链共识算法

张思贤 文 捷

(复旦大学计算机科学技术学院 上海 200433)

0 引 言

区块链最先于文献[1]中提出，作为虚拟货币比特币的底层技术，因其去中心、不可篡改等特性而为大众所熟悉，但也因为其基于算力的Pow算法浪费大量算力进行共识运算和吞吐量低而为人所诟病。Pow算法的出块时间为10分钟，一个交易从上链到确定不能被篡改，需要后续六个区块的确认，也就是一个小时确认时间。并且基于Pow共识算法的区块链系统每秒钟只能处理七笔交易，并不能适用于当今的物联网或者金融系统。为了缓解这一问题，Ethereum平台尝试提出Pos共识算法。Pos算法加入了币龄的概念，提高了出块的速度，但同时也引入了其他问题，如出块速度不稳定，导致分叉的出现，以及持币不出块等问题。另一方面，在联盟链系统中，以IBM的Fabric平台为例使用的为PBFT算法，其吞吐量能够比公有链系统高出上千倍，并且不需要后续6个区块的确认交易不可逆转。在联盟链系统中，交易一旦打包即可被认为不可逆，但随着系统中节点的增多，为了达成共识其系统中需要进行的通信量也将上升，不具备很好的扩展性。文献[3-4]尝试从两种途径对PBFT算法进行改进，一个是引入gossip协议，另外一个是引入信用机制。文献[7]提出一种交替式的共识算法进行交替出块，文献[8]提出了一种RMBC的区块链使用DBFT共识算法，尝试以分组的形式提高用户节点进入区块链的数量。文献[10]尝试分析Pow类的共识算法以及BFT类的共识算法。

由于现行区块链技术存在的瓶颈，并不适用于当今的物联网技术，现行的物联网技术都是厂商各自定义的标准，彼此之间并不能互联，数据不能打通，而区块具有可信任、不可篡改等特性，因此可以尝试将其应用于物联网系统中，用于处理涉及到两个物联网域的问题。

本文尝试从共识算法出发，提出一种两个阶段式的区块链共识算法，并以此算法提出一种物联网设备互联的架构。

1 预备知识

1.1 盲签名

盲签名[9]因为具有盲性这一特点，可以有效保护所签署的具体内容，广泛应用于电子选举的实现中。投票者先将自己所投的选票进行盲化，然后让签名者对于盲化信息进行签名。在投票系统中，盲化后的信息即为选票。

对签名进行盲化处理：

盲化消息：m′=mre(modN)

(1)

签名消息：s′=(m′)d(modN)

(2)

除盲信息：s=s′×r-1(modN)

(3)

原理为：

red≡r(modN)

s≡s′×r-1≡(m′)dr-1≡mdredr-1≡mdrr-1≡md(modN)

盲签名的盲化、签署及除盲过程如图1所示。

图1 盲签名的盲化、签署以及除盲过程

1.2 实用拜占庭算法(PBFT)

文献[5]提出实用拜占庭算法，用于解决分布式系统中出现的拜占庭问题，其容错率为：f≤(n-1)/3。其中：n为系统的总节点数；f为出现故障的节点数。

该算法的主要流程分为3个阶段：

pre-prepare：主节点向所有备份节点发送准备消息，此时节点状态为pre-prepare。

prepare：包括主节点在内的所有备份节点在收到准备消息后，确定无误，向外广播信息，并且进入prepare阶段。

commit：当收到若干个来自其他副本的prepare信息后即可进入commit阶段。

实用拜占庭算法相对简单高效，但随着节点数目的增多，其通信量会急速上升，不适用于大规模的联盟链环境。文献[6]尝试在Fabric平台中对其进行测试节点与性能的关系，文献[13]尝试改造Fabric的架构，以此提高其吞吐量。

2 算法设计

2.1 算法介绍

整个算法大致分为三个阶段，前期阶段为进入该系统，然后将各节点分配到每个组中。第一阶段使用盲签名投票的形式进行主节点的选取。第二阶段使用实用拜占庭算法从上一个阶段中胜利的节点中选出主节点进行区块的生成。

第一阶段中，参与竞选的i到i+4节点，将其选票以盲化的形式(盲化内容为竞选者的地址)，连同区块信息传递至下一个节点，后续节点首先对区块信息进行验证，然后对各个节点盲化后的信息进行签署。

由于经过盲处理各个节点并不知道其为哪个节点投票，只需要对交易记录进行验证与传递。等到区块信息回到i至i+4节点，i至i+4节点则可进行除盲处理，根据选票选出胜利节点，并且广播获胜信息，将交易数据连同签署信息写入区块链中。在传播的过程中，投票节点并不知道到底投的是i到i+4中的哪一个节点。

1) 前期阶段。区块链网络中的各个节点都保存着一份列表，列表上面会出现一个联盟内节点的地址，这个地址标识着这些节点之间为一个联盟。此联盟内节点数存在一个上限，下文假设为M。

新加入到网络中的节点a，向周边发放自己的公钥P，然后进入等待状态，网络中的其他节点b收到来自a的请求加入信息后，确定自己的联盟内节点数目仍未到达上限，将接受加入信息附带上时间戳，以及本节点的公钥S，使用P加密，并以报文的形式传送，表示该节点已被加入至本联盟。

在收到确定报文后(可能同时会收到多个报文，以时间戳最早的为主)， 确定加入该联盟，并且发送回执报文，使用S加密，表示接收成功。b收到报文后向全组节点广播，更新联盟节点列表，并向节点a同步最新的节点列表，a随即同步全网中区块的所有数据。

2) 第一阶段。联盟中的节点以某种环的形式进行连接，如图2所示。

图2 节点以环的形式进行连接

(1) 从联盟中随机选取一个节点i作为初始节点，i以及i后序的i+1、i+2、i+3、i+4将作为本轮的候选节点。

(2) 以环的形式从i+4开始传递其投票信息，后续每个节点将从上写入其投票状况，其投票信息使用上文提及的盲签名进行生成，进行盲化。

(3) 当投票信息传递回i节点时可确认本轮投票结束，参与竞选的各节点依次对盲签名结果进行除盲处理，即可统计得到相应的票数。

(4)i至i+4节点可观察到投票的结果，确定自己是否获胜，并且对外传递信息。

(5) 参与本轮投票并且成功选出胜利者的节点，将能获得奖励。

(6) 下一轮的共识将从i+5开始。

(7) 待下次循环进行至i节点，则可判定一次循环结束，重新排列其环状结构，再次进行主节点的选取。

(8) 胜出节点进入第二阶段共识。

3) 第二阶段。由于使用分组的形式，因此将有若干个胜利节点进入第二阶段的共识。在第二阶段中将使用PBFT算法进行数据的同步，其中主节点的选取将以j=h%N的形式进行选取，h为区块链的长度，N为参与共识的节点个数，结束后回到第一轮共识。

2.2 算法分析

1) 运行效率。将此节点应用于规模较大的联盟链环境中，能够有效降低网络中节点需要进行交流的通信量。使用PBFT算法，当节点数目上升的时候将导致性能的下降。在达成共识的过程中，需要进行信息的交换，节点数目越多需要的数据交换量就越多，在未限定节点数目的PBFT算法中需要的通信量为O(n2)；在节点数目为1 000的情况下所需要交换的通信量为1 000 000；改进后，由于进入PBFT算法的节点由原来的1 000个分为现在的5组，每组中只存在一个节点的胜出，因此通信量为25，为原本的1/4 000。由于在第一阶段中，只需要进行一轮投票就能选出胜者，其通信量为O(n)。若基于效率的原因考虑，胜出第一轮进入第二轮的节点可以选择复制后续若干个区块的生成，然后将出块权转给下一个leader节点，此时整个系统的运行效率与PBFT算法相仿，并且能够容纳更多的节点。

2) 安全性。由于使用盲签名的形式进行投票，节点间并不知道彼此间投票的结果，并且投票结果不能篡改，这提高了选票结果的随机性。由于投票者并不知道其投票的候选人为哪一位，因此只能随机从候选节点中选取一人进行投票，直到最后结果公布，参与投票的候选节点才会知道知道自己所投选的节点为哪一个。

3) 奖励机制。在Pow类型的共识算法中，奖励机制是基于挖矿的性质，节点进行哈希运算，成功挖掘出区块就能获得奖励。本文算法由于不存在挖矿这一环节，可以将奖励的机制加入至前期投票的过程中，参与投票并且成功票选出胜利的节点以及胜出节点将能获得奖励，以降低节点间的相互竞争，使系统稳定运行下去。

4) 硬分叉。由于节点的最终出块是基于PBFT算法，因此能够有效避免分叉的问题。因为区块的节点都是经过最终投票来决定的，不存在像Pow算法中节点同时挖块成功所导致的分叉问题。

5) 联盟链。该算法能在联盟链环境下进行使用，以此缓解PBFT算法带来的通信量大的问题，以此容纳更多的节点进入网络。

6) 使用环进行连接。该算法在分组中使用环进行连接的主要原因在于，分组中的节点相对于全网节点，数量较少，使用环传递数据更加高效，若在全网进行环的连接，传递投票信息与区块信息将受网络的严重影响。数据的传递时间将随着节点数目的上升而上升，节点越多这个环就越大，不能保证稳定的出块速度。

3 应 用

可尝试将该算法应用于物联网[11]系统中。现行的物联网系统中，并没有一个严格的标准，还处于不同的厂商之间互相制定标准，并且大多数为一些性能较弱的设备。另一方面由于节点的性能相对较弱，不能进行较为复杂的共识算法，如Pow与Pos共识算法。文献[2]提出基于物联网系统进行改造的算法，改变Pow算法的计算公式，让节点更加容易计算出结果。我们尝试从上文中提出的共识算法出发，提出一种新的基于区块链物联网共识架构。

我们所提出的物联网系统将分为两层：内部系统与外部系统。内部系统负责管理一系列性能相对较弱的节点，外部系统负责管理一系列性能相对较强的节点。内部系统对应一系列性能较弱的设备，如：灯、共享自行车等，其主节点为一系列性能较好的节点，对应一些性能相对较好、对于电力不是瓶颈的设备，如路由器、平板电脑等。

3.1 内部系统

内部系统的组成为一系列性能相对较差的节点以及一部分性能相对较好的节点，彼此组成环的形式，其中内部系统负责维护一条关于自身内部系统的区块链用于记录每一笔交易操作。

性能较差节点：负责投票，不负责数据的存储以及与外部系统直接交互。若需要数据，则需向性能较好的节点发起查询操作即可，可部署智能合约，进行投票以及数据的自动转发至下一个节点。当发起主节点选取时，投票信息在节点间进行传递，性能较差的节点需要调用智能合约随机地从候选地址中进行选取，并且对候选地址生成的信息进行盲签，然后将数据传递至下一个节点中。

性能较好节点：负责打包交易，负责与外部系统进行交互。一般情况下，一个内部系统中将存在若干个性能较好的节点，彼此间互相参与竞选成为本回合的胜利节点，彼此对本系统的所有数据进行备份，并且与外部系统进行交互。基于性能的考虑，一次节点竞选成为本回合的胜出节点后，需要负责后续若干个区块的生成，以此减少节点间来回投票所带来的消耗。对于内部系统来说，其效率较高，一旦主节点被选取成功，后续任何打包数据上链的操作，将不需要进行耗费资源的Pow计算，只要副本节点间没有任何异议，则可直接进行数据的上链。性能较差的节点只需要接受来自主节点的指令或者查询交易记录即可，无需进行数据的全量备份。

具体流程如下：

1) 内部系统中的每个节点将以某种环的形式进行连接，彼此只需知道下一个节点的地址。

2) 参与竞选的i，i+1、i+2、i+3、i+4等若干个性能较好的节点，发起竞选操作，将其公钥使用盲签的形式，生成一个地址，同时写进一个区块中，连同交易进行传递。

3) 接收到的节点，将从i到i+4的所生成的数据中随机选取一个进行盲签，然后往下一个区块进行传递。

4) 若下一个接收到的节点并不为i，则重复3)的操作。

5) 当区块传递到i至i+4节点时，可将区块中被盲签化的数据进行除盲处理，统计结果并选出胜利节点，向网络中广播本轮胜出的节点。

6) 胜出的节点，将交易进行打包，生成区块，并且广播至相邻的i+1至i+4节点，待若干个区块成功生成后，则重新发起竞选操作。

3.2 外部系统

外部系统为一系列性能较好的节点，在这里我们可以理解为不同的系统，作为联盟间的系统共同维护着一条联盟之间的区块间的区块链。由于节点数目相对内部系统较少，因此可直接使用PBFT算法进行数据的同步与写入，其中主节点的选取沿用j=h%N(h仍然为区块链的长度，N为涉及到的厂商的数目)的形式进行选取。基于视图切换带来消耗等原因，假如在外部系统的主节点不存在作恶的情况下，将负责若干个回合区块的生成，再重新选取。

3.3 跨链操作

外部系统可作为系统间跨链操作的媒介。跨链指的是两个相互独立的区块链系统进行互操作，大多用于虚拟货币的交换。文献[12]指出了区块链跨链系统中架构，在物联网系统中我们可以使用内部系统的主节点作为内部系统以及外部系统之间的调节点。在此可以理解为两个互为独立的系统之间的互操作或者两个不同的物联网系统之间数据的传递，区块链技术保证了数据的正确性。由于使用两层的形式，任何来自外部的指令都能经被内部系统的主节点拦截，并且由于使用了区块链技术可溯源不可篡改等性质，保证了交易数据的真实性，操作一旦发生并且上链，将不能被篡改与抵赖，可使用智能合约的形式进行数据格式的转换。

具体流程如下：

1) 首先内部系统A中的某一节点向当前的leader节点发起一笔向外部节点进行操作。

2) leader将其广播至外部系统中，涉及到的相关内部系统B的主节点，对相应信息进行验证，若无任何异议，则发送至相应的内部节点中进行操作。

3) 相应的内部节点接收到请求后，若确认无误执行操作，并要求主节点将其交易打包进块，内部系统B的主节点将数据打包上链，结果最终写进区块链中。

4) 外部系统接收到该结果已被B系统执行后，将该交易记录上链，并且通知A系统。

5) A系统将交易上链，确定本次跨链操作执行完毕。

3.4 出错处理

1) 若中间某一环节出现错误，整个系统将进行回滚，若在外部系统中涉及到的相关节点将操作回绝，则内部系统A将立即得到反馈，并将其反馈至相应的内部节点。若此笔操作由于某种原因被取消，交易信息可自行选择记录上链。

2) 若内部系统B中将操作进行回绝，则B中的节点则会将操作失败以及其原因回调给内部系统A，后续操作如1)。

3.5 整体优势

1) 由于使用了三层区块链的形式，其操作数据将全程上链，此时各个区域的节点都能从区块链中获取交易信息，若对历史操作记录存疑，可直接在链上进行查询。

2) 该系统相对稳定，若系统出现宕机或其他问题，则可由其他性能相差无几的节点接替其主节点的位置。性能较差的节点并不需要进行区块链的维护，只需要接受来自主节点的指令，以及进行主节点的选取。

3) 由于使用leader节点代为跟踪后续的操作，因此内部系统中发起交易的节点可以继续做相应的操作，等待事件执行完毕后，会得到回传。

4) 使用层层验证的机制，涉及到三个环节的校验：内部系统A的主节点，内部系统B的主节点，以及内部系统相应执行的节点。这保证了跨域系统中的节点不会频繁收到恶意的指令。

5) 所有存储在区块上的信息，使用Merkle Tree(默克尔树)[3]的形式进行组织，用于快速验证和快速查找。

6)使用了智能合约进行数据格式的转换，解决不同厂商之间存在的数据格式不一致的问题。

7)为了防止节点的作恶，可使用保证金的形式，每当涉及到跨链的操作，需要向内部系统中的主节点发一笔交易以及保证金，其保证金在交易已经确定正式被执行之前将锁定。随着操作记录的上链，保证金将解锁。在确定交易记录被上链之前，可使用智能合约对保证金进行锁定。

8) 使用分域的形式，可实现两个物联网设备域之间跨域操作，使用leader节点进行后续交易的跟踪，各个域内的其他节点可继续其自身的其他任务，而无需时刻跟踪其发出去的操作，待后序操作成功leader节点将会告知。

4 结 语

本文提出一种两阶段式的共识算法，在第一阶段中使用投票的形式选取胜利节点，在第二阶段中进行PBFT算法实现区块的生成，解决了PBFT算法无法适用于节点规模较大的情况。未来将尝试从第二阶段进行改进。基于此算法提出一种物联网设备的架构体系，内部系统组织性能较低的节点，只负责随机进行投票，选举出主节点和执行主节点，或者对外部系统分发命令，外部系统使用性能较好的节点管理内部系统的数据上链、外部系统的数据上链以及跨链操作等，使用智能合约进行数据格式的转换，用于解决各个产商之间数据格式不兼容的问题。