基于BLS聚合签名技术的平行链共识算法优化方案

刘 琪，郭荣新*，蒋文贤，马登极

（1.华侨大学 信息科学与工程学院，福建 厦门 361021；2.华侨大学 计算机科学与技术学院，福建 厦门 361021；3.杭州复杂美科技有限公司，杭州 310061）

0 引言

中本聪于2008 年11 月1 日发表一篇关于阐述比特币原理的白皮书《比特币：一种点对点式（Peer-to-Peer，P2P）的电子现金系统》［1］，提出一种基于点对点技术的电子现金系统，使网上支付由一方发起，直接支付给另一方，这个过程没有通过任何的金融机构。如果在第三方的监督下才能解决双重支付的问题，那么中本聪提出的这个系统将没有意义。第三方或者中介机构的信任问题一直存在，区块链［2］的出现旨在解决信任问题，它被称作是“信任的机器”。

区块链技术包括分布式存储技术、密码学技术、智能合约和共识机制等，具有数据不可篡改、信息可追溯、公开透明、集体维护、匿名性等特点。随着近几年区块链技术的快速发展，区块链的应用不再局限于金融领域，目前已经渗透于各行各业，比如存证溯源、政务、资产数字化、智慧监管等领域。尽管区块链技术迅猛发展，但是在去中心化的架构下仍然存在性能和交易吞吐量等问题，区块链只有解决此类问题才能有更大规模的落地。Chain33、Polkadot［3］、Cosmos［4］均使用类似的跨链技术［5］来解决区块链面临的性能问题。Cosmos 的技术模式与Chain33 和Polkadot 不同，对于使用者来说门槛更高，每个使用者都要组共识、搭节点，并且链上数据维护成本高，而Chain33 成本相对较低可快速部署。Chain33 和Polkadot 都是平行链模式均采用平行链架构，Polkadot 目前在测试网阶段，从Polkadot 发展规划来看，Chain33 目前已经实现的资产跨链流通等功能，相对领先1～2 年。

Polkadot 最早提出平行链的概念是为了解决区块链在互操作性、可扩展性以及共享安全性方面存在的弊端，但到目前为止还没有实际的应用落地。平行链的概念最早由杭州复杂美科技有限公司提出，百度等也在白皮书中引入这个概念。Chain33 是由杭州复杂美科技有限公司创建的区块链底层系统，Chain33 首创的平行链架构中平行链依附于主链并且使用主链的共识网络，复杂的功能在平行链上完成，主链只做数据存储和共识，即使出现性能问题或者智能合约受到攻击，也仅破坏平行链不会影响主链的安全；由于主链的安全性极高，因此平行链的所有数据可以从主链同步回来。同时平行链也是在主链的基础上搭建的区块链，可以发展独立的区块链生态，拥有自己的节点和部分共识、能够编写多种智能合约、拥有独立的钱包、拥有独立的区块链浏览器等；基于主链统一的交易共识，不论是平行链和主链，还是不同的平行链之间的跨链资产都可以做到无缝转移，使之前的跨链时间从小时分钟级别缩小到几秒，跨链效率高。Polkadot 与Chain33 平行链对比分析如表1 所示。

表1 Polkadot与Chain33平行链的对比分析Tab.1 Comparative analysis of Polkadot and Chain33 parallel chain

比特元（BiTYuan，BTY）是一种简单稳定、可扩展性强的公有链网络。比特元区块链的研发基于Chain33 底层架构，是全球首个实现平行链架构的公有链网络。在比特元区块链上，以比特元为主链向外延伸多条平行链，将不同的交易分散到不同的平行链上执行，分担主链的运算负荷，同时提升整个系统的运行效率。比特元上的各条平行链既可独立开发去中心化应用（Decentralized Application，DApp），建设多样化的应用生态，又可实现多链间的跨链交易和数据交换功能。在比特元中交易首先发送到主链被共识打包，随后同步到平行链上被执行，最后将执行结果的hash 写回主链进行共识，实现交易并行执行提升系统吞吐量TPS（Transactions Per Second），在此过程中BTY 是交易必需的燃料。本文以比特元区块链网络为例介绍Chain33 平行链架构以及结合BLS聚合签名技术对平行链共识算法做优化。

1 区块链中常用的共识算法

共识机制在去中心化的思想上解决了节点之间相互信任的问题，是区块链能够稳定持续运行下去的主要力量。目前区块链中常用的共识算法［6］可分为两大类：公有链和许可链。公有链的典型代表有工作量证明（Proof-of-Work，PoW）［7］、权益证明（Proof-of-Stake，PoS）［8］以及股份授权证明（Delegate Proof of Stake，DPoS）［9-10］；许可链的典型代表有实用拜占庭容错（Practical Byzantine Fault Tolerance，PBFT）［11］和（Replicated And Fault Tolerant）［12］。对上述共识算法从去中心化程度、容错率、资源消耗以及吞吐量等方面作简单对比分析，如表2 所示。

表2 区块链常用共识算法的对比分析Tab.2 Comparative analysis of commonly used consensus algorithms in blockchain

这些常用的共识算法都可应用于主链中，而平行链中每个超级节点都会向主链提供共识交易。n个超级节点的共识结果在主链达成共识，共识的规则是2/3 的超级节点结果一致，第2 章将详细介绍平行链的共识算法。

2 平行链架构

2.1 主链+平行链架构

图1 展示了主链+平行链架构，该架构中一条主链附属多条平行链，每条平行链只与主链交互，各条平行链之间互相不干涉对方的交易。平行链的共识流程为：首先共识交易在主链上被打包；紧接着平行链上的超级节点从主链同步共识交易，并打包交易数据生成区块同时上传上链请求；然后主链上的节点广播共识交易并验证共识结果的正确性；最后平行链上的所有节点同步交易数据。

图1 主链+平行链架构Fig.1 Main chain+parallel chain architecture

主链+平行链架构具有如下几个特点：

1）高效性：平行链发送共识交易到主链上进行共识验证和数据存储，多条平行链交易并行处理，共识效率大幅提升。

2）稳定性：平行链上运行复杂的功能，主链只做存证等一些核心功能，整个架构简单稳定。

3）安全性：平行链的安全由主链保障，当智能合约或虚拟机被攻击时仅破坏平行链，平行链上的所有数据可以快速从主链同步，从而保证数据完整不被更改。

4）高扩展性：平行链拥有自己的生态，能在链上发行自己的通证（token），相当于一条独立自主的公链，并且支持主链和平行链跨链和平行链之间的跨链交易。

2.2 平行链的节点设计

Chain33 平行链上的节点有授权节点、超级节点、监督节点和普通节点4 种角色，下面对它们分别进行介绍。

1）授权节点。

授权节点是参与共识、发送共识交易的节点。不是所有的节点都有权限发送共识交易，只有授权节点可以发送共识交易，普通节点没有权限发送共识交易。

2）普通节点。

普通节点不发送共识交易，只接收共识交易并校验共识结果，以此体现区块链分布式一致性校验的设计思路，即授权节点负责共识安全，普通节点保持和授权节点一致，所有节点协同统一。

3）超级节点。

超级节点负责平行链的共识安全，并得到一定的挖矿奖励，每个超级节点都会向主链发送共识交易，n个超级节点达成共识的规则是超过2/3 的超级节点共识结果一致；只有有了超级节点共识，平行链的跨链功能才可以启用。

4）监督节点。

监督超级节点的共识过程，防止超级节点联合作弊。当超级节点的共识结果和监督节点的结果不一致时，暂停共识，直到超级节点或监督节点修正共识结果达成共识为止。

2.3 平行链共识算法的过程分析

主链上的共识算法有多种，比如在公有链中使用PoS，在联盟链中使用Tendermint 或PBFT，在私链中使用RAFT。平行链上的共识算法与主链使用的共识算法不同，主要的区别是平行链依赖于主链的共识网络，主要过程为平行链授权节点或超级节点发送共识交易到主链上进行共识，然后再同步共识交易到平行链进行自共识验证，共识规则为超过2/3节点共识结果一致则达成共识，自共识不通过的平行链节点将停止生成区块。

表3 详细描述了平行链共识过程之前先设定共识过程中涉及的符号及其含义。

表3 符号及其含义Tab.3 Symbols and their meanings

目前平行链的共识算法如下所示。

1）各参数的设定。

①设平行链上待共识的区块为B1；

②设第一 平行链 为p_chain1(x1，x2，…，xn)，其 中x1，x2，…，xn称为超级节点，并且满足n≥3f+1，f∈N+；

③设p_chain1(x1，x2，…，xn) 对应的 主链为C1(X1，X2，…，Xn)；

④ 待共识的区块B1中包含的若干信息有：状态哈希s_hash、签名信息S、待共识的区块高度H和打包各交易的状态信息MS；

⑤ 各超级节点(x1，x2，…，xn)打包B1的若干信息生成区块信息BMi={s_hash_i，Hi，Si，MSi}；

⑥ 达成共识的节点数设为Num。

2）共识过程。

①x1，x2，…，xn分别将BM1={s_hash_1，H1，S1，MS1}，BM2={s_hash_2，H2，S2，MS2}，…，BMn={s_hash_n，Hn，Sn，MSn} 发送至主链C1上对应节点x1，x2，…，xn处。由于发送1 笔共识交易将产生0.001 BTY 的手续费，因此n个共识节点发送n笔共识交易需产生0.001nBTY 的手续费。

②x1，x2，…，xn将BM1，BM2，…，BMn记录到主链上并互相广播。

③X1，X2，…，Xn每个节点有R1，R2，…，Rn这n笔共识交易的全部内容，由于1 笔共识交易占用4 KB 的存储空间，因此n笔共识交易共占用主链4nKB 的存储空间。

④ 此时进行共识验证，x1，x2，…，xn从C1同步共识交易Tx={BM1，BM2，…，BMn}，此时p_chain1(x1，x2，…，xn)上每个节点都含有其他节点的共识交易信息。

⑤p_chain1进行自共识，若Num≥n*2/3，即{BM1，BM2，…，BMn}中至少有n*2/3 个区块信息相同则达成共识。

⑥ 假设满足阈值，达成共识，共识结果为R={s_hash，H，S，MS}生成的共识标识为u，共识高度为H。

2.4 平行链共识算法的缺陷

由2.3 节可知平行链的共识过程为双层共识，首先平行链交易发送到主链上进行共识打包；然后平行链同步主链的区块并选取与本平行链有关的交易执行，再将区块哈希发送到主链上做共识；最后平行链上的节点同步主链的共识交易进行二次共识。平行链共识全过程的缺陷分析如下：

1）平行链上的超级节点越多，发送到主链上的共识交易就越多，多笔相同的共识交易将占据主链大量的存储空间；并且多条平行链依附于一条主链，主链上交易记录的越多，主链的交易处理能力［13］就越弱。

2）平行链上的超级节点每发送一次共识交易到主链上就会产生一笔手续费，当多个超级节点同时发送共识交易则会产生多笔手续费，同时消耗大量的资源。

3 平行链共识算法优化设计

3.1 Leader节点选取算法

在平行链聚合签名方案中，需要选取一个Leader 节点发送整个共识交易，并且支持轮换操作。

当前的一些Leader 节点选取算法比较复杂，比如有权重设计，或者不支持轮换操作，只让一个节点发送共识交易，可能只消耗一个节点的手续费，不具备公平性。此处通过对比RAFT［14］中的Leader 节点选取方案可知，在RAFT 共识机制中，Leader 节点选举成功后会不断地向follower 跟随节点发送心跳消息，选举周期将会一直持续到某个follower 节点没有收到心跳消息并成为candidate 候选节点为止，这时开启下一轮Leader 节点的选举。由于RAFT 中Leader 节点任期时间无法确定并且不支持轮换操作，每个节点消耗的手续费差别大，因此不适用于平行链的共识算法。针对上述不足，设计较为轻量的Leader 节点选举和轮换机制，保证系统稳定。

决定Leader 节点的因素是高度（height）和偏移（offset），当offset=0 时，有关超级节点中Leader 节点的选举和轮换机制如下。

1）平行链各个超级节点配置成功后，顺序固定，依次作为Leader 节点。

2）假设现有超级节点A、B、C、D，对应的索引依次为0、1、2、3。

3）现设置初始Leader 节点索引为0，即base=0，每隔一定共识高度轮换下一个节点为Leader 节点，假设每隔100 高度做一次轮换。

4）设置base=(height/100)%nodes，得到当前共识高度下Leader 节点的索引，height依次增长，base也依次增长。

5）Leader 节点需要每隔一段时间比如t=5 s 发送心跳消息，向其他节点声明自己是Leader 节点；同时其他非Leader 节点也在等待接收心跳消息。

6）Leader 节点每隔5 s 发送一次心跳消息，只要非Leader节点在1 min 以内能够收到一次心跳消息就不用做offset偏移；如果非Leader 节点在1 min 之内没有收到来自Leader 节点的心跳消息，那么设置一个offset偏移值，令offset=(offset+1)%nodes，并 且Leader=(offset+base)%nodes可 以唯一确定一个新的Leader 节点。

这种情况又分为以下两类。

1）Leader 节点确实没有发送心跳消息，非Leader 节点重新选取下一个Leader 节点；若本节点发现自己是Leader 节点，则广播心跳消息。

2）如果仅自己没有收到心跳消息，其他非Leader 节点都收到心跳消息，那么仅该节点偏移Leader 节点，直到自己是Leader 节点为止，广播心跳消息。

但这样会出现两个Leader 节点的情况，如果同时有多个不同Leader 节点的心跳消息，则节点会和自己索引作比较。

①若两个base索引不同，则不处理，说明两个Leader 节点不是同样的共识高度。

②若base相同，offset不同，如果自己的offset索引比较小，则接受大的Leader 节点索引为Leader，具体为设置新的offset；如果自己offset比较大，则不处理。

这样在处理一些僵尸节点的时候，系统会自动切换到下一个节点为Leader 节点继续服务，发送共识消息；因为共识height不变，所以此时base也不变，只是offset改变发生偏移。

当共识高度超过预先设置的间隔之后，base才会发生改变，从而更新下一个Leader 节点，保持系统共识稳定。

3.2 BSL签名算法

BLS（Boneh-Lynn-Shacham）签名算法由Boneh 等［15］提出，BLS 签名无需随机数生成器即可实现聚合多个签名以及m-n多重签名，同时减少节点间的多余通信开销。该签名算法有两个基本概念：曲线哈希和曲线配对即双线性映射e函数［16-17］。

BLS 签名算法与椭圆曲线数字签名算法（Elliptic Curve Digital Signature Algorithm，ECDSA）和Schnorr 签名算法不同：在ECDSA 和Schnorr 签名中对消息求哈希的结果是数值；而在BLS 签名算法中用新型散列函数对消息求哈希，并将得到的结果映射到椭圆曲线的一个点上［18］。

双线性映射e函数由六元组η=(G1，G2，GT，n，e，g1，g2)组成，G1和G2是阶为p的加法循环群，GT是具有相同阶的乘法循环群。g1是加法群G1的生成元，g2是加法群G2的生成元。e是双线性映射，需要进行曲线配对，则有G1×G2→GT。设P，Q为曲线上的两个点，∀a，b∈Zp，则满足以下性质：

可见，配对函数对曲线上的运算满足分配律、交换律和结合律。

BLS 签名过程如下：假设待签名的消息为m，私钥为k，公钥P=k*G；求签名S时，先对消息m求哈希后映射到椭圆曲线上，得到曲线哈希H（m），再乘以私钥k即得S=k*H(m)。公钥P验证签名S，则有：

本文采用BLS 聚合签名技术对平行链共识算法进行优化。假设Leader 节点要聚合N个超级节点的签名，由于平行链共识的特点是签名不同共识数据相同，因此共识交易设为M，对共识交易求曲线哈希可得H（M），ki为私钥，可得公钥Pi=ki*G，聚合签 名Si=ki*H(M)，则需验 证e(G，Si)=e(Pi，H(M))成立。验证过程如下：

4 平行链共识算法的优化方案

传统的平行链共识算法是平行链的每个共识节点都发送共识交易。优化方案是平行链的共识节点先内部发送共识交易并附上BLS 签名数据；再由Leader 节点整合共识交易并聚合交易签名；最后将新的共识交易发送到主链上验证，同时结合BLS 聚合签名技术防止篡改的发生。这种共识算法既节省区块空间、节约手续费，还能够保证系统的安全。

4.1 系统初始化设置

设平行链为p_chain_1，平行链上的共识节点n需满足n≥3f+1，f∈N+。预配置的聚合签名算法为BLS 签名算法，BLS 签名是利用双线性对构造的一种短签名方案；预配置授权账户组，根据x1，x2，…，xn顺序依次设置平行链上节点的索引为0，1，…，n-1(n≥4)。

4.2 共识过程

共识算法流程如图2 所示。

图2 优化后的平行链共识算法流程Fig.2 Flow chart of parallel chain consensus algorithm after optimization

1）系统设置。令q为大素数，加法循环群G1和乘法循环群G2为q阶，P是G1的生成元，Q是G2的生成元；双线性映射为e=G1×G2→GT，定义散列函数H0：{0，1}*→G1。

2）生成共识内容并提取密钥。假设平行链待共识的区块为p_block(100)，其对应的主链区块为block(200)。以平行链P1上的节点x1为例说明，x1从block(200)同步p_chain_1 的各笔交易Tx=(tx1，tx2，…，txn)，x1打包Tx并生成p_block_x1，计 算p_block_x1获得共 识内容msg(100)_x1={block_hash，height，bitmap}。BLS 签名需 要的私钥为Secp265k1 的1/2，采用Secp265k1 私钥不断取hash直到满足BLS 范围为止作为BLS 私钥，令节点x1的私钥为xa，则x1的公钥为Pub_bls_x1=ka*P。

3）签名。x1根据BLS 聚合签名算法对msg(100)_x1进行签名获得签名数据bls_(msg(100)_x1)=ka*H(msg(100)_x1)。

4）对交易内容求哈希并映射到曲线上。H(msg(100)_x1)=H(block_hash‖height‖bitmap)。

5）预设授权账户组。x1，x2，…，xn按序排列并设置索引为0，1，…，n-1，一一对应于 BLS 公 钥Pub_bls_x1，Pub_bls_x2，…，Pub_bls_xn。

6）广播。x1将msg(100)_x1+bls_(msg(100)_x1)广播给其他节点x2，x3，…，xn；同理x2，x3，…，xn节点也作如上运算操作。在x1，x2，…，xn都正常运行的情况下，对x1而言已收到其他节点的共识内容和签名信息{msg(100)_x2+bls_(msg(100)_x2)，msg(100)_x3+bls_(msg(100)_x3)，…，msg(100)_xn+bls_(msg(100)_xn)} 。

7）自共识 。各个节 点的共 识内容msg(100)_x1，msg(100)_x2，…，msg(100)_xn在内部进行自共识。若x1不同，其余都相同，则Num=n-1 ≥2/3*n(n≥4)，达成共识，共识内容为msg(100)。

8）聚合签名。聚合达成共识的节点，其签名数据为bls_（msg（100）_x2）+bls_（msg（100）_x3）+… +bls_（msg（100）_xn），在之前设置好的授权账户组中，令达成共识为1，未达成共识为0，即bitmap=(0，1，1，1，…，1)。

9）聚合后 的共识交易。Tx100=｛msg（100），bls（msg（100_x2）+bls（msg（100_x3）+… +bls（msg（100_xn）｝，bitmap=（0，1，1，1，…，1）。

10）验证聚合签名正确性。由Leader 节点将Tx100 发送至主链上，主链节 点根据bitmap=(0，1，1，1，…，1) 授 权账 户组查找对应的BLS 公钥可得到｛Pub_bls_x2，Pub_bls_x3，…，Pub_bls_xn｝，聚合签名公钥得｛Pub_bls_x2+Pub_bls_x3+… +Pub_bls_xn=｝，结合共识内容msg(100)判断：

是否正确。

下面给出聚合签名验证过程的正确性证明。

因为式（5）的正确性被成功验证，所以平行链上的各个共识节点可以先互相广播发送共识交易达成共识，再由Leader 节点将达成的共识交易内容与各节点的交易签名聚合后发送到主链上；主链根据bitmap在预配置的授权账户组中查找到平行链的各共识节点所对应的BLS 公钥，对聚合签名验证通过，且公钥账户超过2/3 共识阈值，则共识通过，同时证明该优化算法的可行性。

5 实验与结果分析

5.1 Leader节点选取实验

Chain33 是一套支持共识、数据库、执行器等可插拔、易升级的区块链架构，本文基于Chain33 底层架构搭建平行链架构，通过Go 语言实现平行链共识算法的优化。实验环境配置如表4 所示。

表4 实验环境配置Tab.4 Experimental environment configuration

本文实验中设置4 个超级节点进行Leader 节点的选取，分别为A、B、C、D，对应的索引号分别为0、1、2、3，分别对Leader 节点选取过程中出现的3 种情况进行分析。

1）normal：正常情况。

2）case1-1：Leader 节点因本身故障在规定时间内未发出心跳消息，进行offset偏移至下一个节点。

3）case1-2：Leader 节点因本身故障未在规定的时间内发出心跳消息并且进行offset偏移至下一个节点处时，下一个节点仍发生故障再次进行offset偏移操作。

假设当Leader 节点为D 索引号为3 时未正常发出心跳消息，Matlab 仿真图如图3 所示。

图3 Leader节点选取算法Fig.3 Leader node selection algorithm

分析图3 可得，在normal 正常情况下随着共识高度的增长每隔100 共识高度发生一次Leader 节点轮换操作，当Leader 节点为D、索引号为3 时，下一次轮换又回到节点为A、索引号为0 处，一直重复这种循环；在case1-1 情况下，Leader 节点为D、索引号为3 时发生故障，此时进行offset偏移至下一个节点为A、索引号为0 处，此时A 正常；在case1-2情况下，进行offset偏移至A，但此时A 节点也出了故障，因此再次进行offset偏移至下个节点。由图3 可知，无论发生哪种情况每个共识高度都只有唯一的一个Leader 节点，保证每次只有一个Leader 节点将共识交易发送到主链上且只收取一次交易手续费。

5.2 性能测试

在平行链上分别设置4、7、10、13、16、19、22 个超级节点，从交易手续费、占用主链存储空间、交易吞吐量以及时延这4 个方面进行测试，通过Matlab 对优化前后的平行链共识算法仿真，如图4 所示。

图4 优化前后不同指标对比Fig.4 Different indicators comparison before and after optimization

由图4（a）可知，优化前有n个超级节点发送n笔共识交易，收取n笔手续费0.01nBTY；优化后仅由Leader 节点发送一笔共识交易，因此无论有多少个超级节点，只收取一笔手续费0.01 BTY。

由图4（b）可知，优化前n个共识节点会发送n笔共识交易到主链上参与共识，多笔共识交易会占用大量主链空间，n笔将占用4nKB 的存储空间；优化后，最终由Leader 节点发送一笔共识交易至主链，因此只占用主链区块空间4 KB。

由图4（c）可知，随着超级节点数量的增多吞吐量均呈下降趋势。优化前下降速度更快，当超级节点更多时对其影响更大；优化后吞吐量下降比较缓慢，当超级节点更多时，吞吐量可能仅有细微变化，最终曲线将接近水平状态，整体看来TPS 仍然会较高。

由图4（d）可知，随着超级节点数量的增多共识延时均呈增长趋势。优化前增长剧烈，超级节点数量越多发送到主链上的共识交易就越多，平行链上的节点进行二次共识的时间就越长，最终的共识时延也越长；而优化后虽然增加了BLS 聚合签名的过程但该过程不到1 ms，对整个共识的过程影响不大，因此共识时延增长缓慢。

6 结语

共识算法是区块链的核心技术，本文首先介绍区块链主链的几种常见共识算法，包括PoW、PoS、DPoS、PBFT；然后介绍平行链+主链的架构，即平行链共享于主链的共识网络，一条主链可以附属多条平行链，能够实现交易并行执行，保障系统运行的稳定性和安全性；最后基于该架构对传统平行链共识算法的缺陷进行分析，并且针对该缺陷设计基于BLS 聚合签名的平行链共识优化算法。该算法采用Leader 节点选取算法和BLS 聚合签名算法，在保障系统安全性的前提下能够有效解决多笔共识交易占用主链大量空间和浪费手续费的问题；同时在TPS 吞吐量和共识时延方面优化后的平行链共识算法的性能也是优于优化前的平行链共识算法。这种优化只是平行链共识算法性能提升的一种尝试，未来还可以针对主链的共识算法作进一步改进，以此提升整个平行链架构的效率。