区块链共识协议综述

发布日期：2025-01-04 12:24    点击次数：91

自2009年比特币[1, 2]系统出现以来, 其底层区块链技术逐渐受到来自学术界和产业界的关注, 并获得快速的发展.当前, 区块链技术已经得到广泛使用.例如, 基于数字货币的跨境支付作为区块链技术的一大应用场景, 近年来已经广为人知并开始被商家接受[3]; 一系列基于区块链技术的金融服务[4, 5]、供应链技术[5, 6]、政府治理[7]、游戏服务[8]等已经出现并获得成功运用. 区块链作为一种链式数据结构, 由不断增长的区块利用哈希指针前后链接而成.区块链中的数据只能追加、不可删除或篡改.区块链系统是一个典型的分布式系统, 其中每个节点维护一份本地区块链数据备份.在区块链系统中, 区块链共识协议制定了一组每个节点必须遵守的规则, 最终保证分布式系统中各节点区块链数据备份的一致性. 区块链共识协议分为两个主要步骤: 出块节点选举和主链共识.在出块节点选举阶段, 某个节点(或多个节点)成为出块节点, 提出新区块.由于分布式网络中可能存在的恶意节点及分叉块的影响, 其他节点在收到新区块以后不能直接将其加入自己的本地区块链中.所有节点需要利用主链共识对新区块及其构成的主链达成一致.出块节点选举机制和主链共识共同保证了区块链数据的正确性和一致性, 从而为分布式环境中的不可信主体间建立信任关系提供技术支撑. 作为区块链系统的核心组件, 共识协议同时决定了区块链系统的性能及安全性.例如, 流行度最高的比特币系统[9]采用概率性共识协议.为了保证区块在大规模分布式系统中的广泛传播, 比特币系统将区块大小限制为1MB, 区块间隔设置为10min, 从而导致比特币系统每秒只能处理约7笔交易(比特币区块大小约1MB, 区块间隔维持在10min左右, 每笔交易大小约250字节, 因此, 理论上每秒交易数=(1×1024×1024÷250)÷(10×60)≈7).当交易量上升时, 系统堵塞现象时有发生.此外, 对于安全性要求较高的大数额交易, 比特币官方客户端Bitcoin Core推荐用户等待随后6个区块的确认(约1个小时)[10], 使其具有更高的概率安全性. 为了改善比特币系统的性能, 研究开发人员不断对其共识协议进行优化, 比如缩短区块间隔、区块扩容等, 然而这些优化同时可能带来对安全性[11-13]的负面影响.自从区块链技术诞生以来, 大量研究工作围绕设计与分析共识协议开展, 如Bitcoin-NG[11], Algorand[14], Byzcoin[15], Honeybadger[16]等, 同时也形成了多个基于区块链的系统, 如Ethereum[17], Litecoin[18], Hyperledger Fabric[19]等. 随着区块链研究工作的推进, 研究人员开始对区块链技术从不同方面进行梳理[20-23]: 文献[20]讨论了比特币和以太坊工作量证明机制的异同; 文献[21]讨论了基于证明的共识协议, 包括工作量证明、权益证明等, 并比较了工作量证明和权益证明的异同; 文献[22]从激励机制的角度讨论了非许可链共识协议; 文献[23]按时间顺序梳理了主要的区块链共识协议.上述研究工作一般将区块链共识协议视为整体讨论, 缺乏对共识协议的步骤划分以及不同步骤间详细比较分析.据前所述, 共识协议分为出块节点选举和主链共识两个主要步骤.这一分类视角在区块链协议设计方面十分常用[2, 14, 15, 24, 25].基于对共识协议主要步骤的划分, 有助于研究及开发人员理解共识协议的运行流程.进而, 通过比较各步骤采用机制, 清晰准确地理解不同机制的优劣.最后, 不同步骤间的机制组合也可以为协议设计提供新的想法. 本文中, 我们从区块链共识的两个主要步骤(出块节点选举和主链共识)对共识协议进行解耦分析.通过对每个步骤采用的机制进行综合性梳理、对比和分析, 观察共识协议的发展趋势, 为研究人员和开发者提供有用建议.具体而言, 在出块节点选举机制部分, 我们主要围绕目前已得到广泛研究与应用的工作量证明和权益证明展开讨论, 总结工作量证明和权益证明机制存在的问题, 从解决问题的角度讨论了随后出现的各种替代性证明机制.在主链共识部分, 我们根据主链共识的性质, 将主链共识分为概率性共识和确定性共识两类.在概率性共识中, 我们讨论了各种主链选取规则, 包括最长链规则[2]、GHOST[12]、包容性协议[26]等, 并从概率性共识的持久性和活性角度对上述规则进行分析比较.在确定性共识中, 我们首先讨论了经典的拜占庭协议[27]以及其应用到区块链中需要解决的问题, 随后讨论了各种基于拜占庭容错协议达成一致的共识算法, 包括Algorand的BA*协议[14]、Byzcoin的PBFT协议[15]、Stellar的SCP协议[28]及Honeybadger[16], 并从确定性共识的安全性和活性角度对各种协议进行分析比较.最后, 我们总结了共识协议发展趋势以及可能的研究方向, 为未来研究提供参考. 本文第1节介绍区块链共识协议的运行流程以及区块链系统的分类.第2节描述出块节点选举机制, 分析比较工作量证明机制和权益证明机制的现有工作.第3节描述主链共识, 并分析比较各种概率性共识和确定性共识.第4节总结研究发现及未来的展望.1 区块链共识协议 区块链共识协议属于拜占庭容错协议, 保证区块链网络中诚实节点在恶意节点干扰下也能达成共识.在分布式系统中, 依据系统对故障组件的容错能力, 共识协议分为崩溃容错协议(crash fault tolerant, 简称CFT)和拜占庭容错协议(Byzantine fault tolerant, 简称BFT)两大类[20].CFT协议保证系统在组件宕机的情况下也能达成共识, 适用于中心化的分布式数据集群, 例如Google分布式锁服务Chubby[29]、Paxos[30]协议等.BFT协议由Leslie Lamport在1982年提出, 保证分布式系统在故障组件[31, 32]的干扰下依然可以达成一致性.由于区块链网络的开放性质, 区块链共识协议需要抵御恶意节点干扰, 因此属于BFT协议. 区块链系统的运行流程如图 1所示.用户利用区块链客户端(钱包、网页等)发起交易, 交易通过点对点(peer- to-peer, 简称P2P)网络[2, 33]广播, 节点验证交易格式和内容, 若无误, 则加入本地交易池中并广播给其他节点; 根据共识协议的出块节点选举规则, 网络中的某节点成为出块节点; 出块节点将交易打包、生成新区块, 并通过点对点网络广播新区块; 节点收到区块后, 验证区块及交易的格式和内容正确性, 若无误, 则更新本地区块链数据; 节点若收到同一高度的多个区块, 则根据共识协议的主链共识对区块链数据达成一致.通过以上分析可看出, 区块链共识协议主要分为两个步骤: 出块节点选举以及主链共识[2, 14, 15, 25].前者用于选举分布式系统中的出块节点、生成新区块, 后者则对区块链数据达成一致. Fig. 1 Blockchain system running flow diagram 图 1 区块链系统运行流程图 按节点准入机制, 区块链系统分为非许可链(permissionless blockchain)和许可链(permissioned blockchain)两类[34, 35].非许可链系统中没有许可机构对节点进行身份审查, 节点以匿名形式任意加入或退出系统, 因此非许可链又被称为公开链(public blockchain).基于这种开放性质, 非许可链系统规模通常较大, 共识节点甚至可达上万[36, 37].许可链系统中节点需经过中心机构的准入审查, 获得授权后才能加入系统.因而, 许可链系统规模往往较小, 节点数通常为几十到几百[16, 38].针对不同应用场景, 许可链又分为联盟链(consortium blockchain)和私有链(private blockchain)[34, 39].联盟链通常由具有相同行业背景的多家不同机构组成, 共识节点来自联盟内各个机构, 区块链数据在联盟机构内部共享.私有链通常部署在单个机构内部, 共识节点来自机构内部, 类似于传统的分布式数据集群.由于区块链共识协议的相关研究主要针对非许可链, 因此我们在本文中主要分析非许可链共识协议, 同时也包括一些典型的许可链共识协议. 我们将非许可链和许可链共识协议的不同特征总结见表 1.针对准入机制, 非许可链共识协议允许节点自由准入, 许可链共识协议要求节点审查准入.基于此特性, 非许可链一般应用于公开链的场景, 而许可链应用于联盟链、私有链的场景.据上所述, 非许可链共识协议一般具有较高的网络规模, 许可链共识协议的网络规模相对较低.通常情况下, 分布式系统网络规模越大, 达成共识的难度越高, 因而非许可链吞吐量通常较低, 许可链较高.在一致性方面: 非许可链共识协议通常以一定概率确保数据一致, 实现弱一致性; 许可链通常采用确定性方式确保数据一致, 实现强一致性. Table 1 Comaprison between permissionless and permissioned blockchains 表 1 非许可链和许可链特征比较 2 出块节点选举机制 区块链共识协议的出块节点选举机制与传统分布式协议中的领导人选举(leader election)问题[40]类似.该问题于1977年由Gérard Le Lann[40]正式提出, 指分布式系统中采用某种机制选出一个领导人节点, 该节点负责发起提案并发送给其他节点, 其他节点基于提案更新数据, 以此提升分布式系统运行效率.领导人选举思想应用于随后一系列的分布式系统共识协议研究[30, 41, 42].在这些研究工作中, 领导人节点的生命周期较长, 通常持续到节点宕机, 因此也被称为强领导人[42].由于区块链系统的出块节点负责发起区块提案并发送给其他节点, 以此完成区块链数据的更新, 因此, 出块节点选举机制类似于领导人选举问题.有所不同的是, 区块链共识协议的出块节点选举机制需要抵御开放网络环境中的恶意节点.通过在P2P网络中伪造大量虚拟节点, 恶意节点可以发起女巫攻击[43], 从而控制区块链系统.为了解决这一问题, 区块链系统在出块节点选举环节通常采用“身份定价”机制, 例如工作量证明[11, 15, 17, 18]、权益证明[24, 44, 45]等.下面分别对这两种机制进行综述分析.2.1 工作量证明机制 比特币[2]首次使用工作量证明(proof of work, 简称PoW)机制进行出块节点选举, 随后的大量区块链研究工作及系统都采用这一机制.工作量证明的概念最早由Jakobsson等人在1999年提出[46], 用于实现可验证的计算任务.工作量证明包括证明者和验证者两个角色, 证明者向验证者出示证据, 表明自己在某时间段内完成了一定数量的计算任务.由于产生证据需消耗一定量计算资源, 工作量证明可用于缓解垃圾邮件和其他拒绝服务攻击问题. 比特币基于难题形式实现工作量证明机制.如定义1所示, 比特币节点寻找满足条件的Nonce(number only used once)值, 使区块哈希低于目标难度值D.解决该工作量证明难题的节点将成为出块节点, 负责发起区块提案. 定义1(比特币工作量证明难题). 给定全网统一的难度值D、区块元数据blockData, 寻找满足条件的Nonce值, 使得根据哈希函数SHA-256计算得到的区块哈希blockHash低于目标难度值D: $ blockHash = Hash(blockData,Nonce) \le D. $ 由于哈希算法具备的输入敏感和抗碰撞[47, 48]特点, 节点唯有不断调整输入值(Nonce、交易数据等)以寻找满足条件的Nonce, 因此, 节点解决难题从而成为出块节点的概率与其可用的计算资源成正比.计算资源的投入可被视为一种身份定价机制[46, 49], 即便攻击者伪造大量虚拟身份, 也无法提升计算资源, 从而增加成为出块节点的优势.因此, 工作量证明难题解决了分布式系统中的女巫攻击问题[43].另一方面, 由于哈希算法具备的正向快速和逆向困难[48]特点, 验证节点可利用出块节点寻找的解快速验证正确性.因此, 工作量证明难题实现了匿名分布式网络中的可公开验证. 作为首个区块链系统, 比特币系统所采用的工作量证明机制被应用到大量的区块链共识协议研究[11, 14-16, 25, 26, 50, 51]及新的区块链系统[44, 45, 52]中.随着区块链研究工作的推进, 研究人员逐渐发现比特币工作量证明机制的不足, 并在此基础上进行改进.表 2总结了比特币工作量证明机制(以下简称比特币PoW)的不足及相应改进工作, 下面分别对这些不足进行综述分析. Table 2 Problems and corresponding solutions of PoW mechanism 表 2 工作量证明机制的问题及其解决方案 2.1.1 算力中心化 比特币的工作量证明机制(PoW)具有计算密集型的特点, 容易导致网络算力中心化.在比特币白皮书中, 中本聪(Satoshi Nakamoto)提出了“一处理器一票(one-CPU-one-vote)”的概念.在中本聪的设想中, 节点使用个人电脑即可进行PoW运算, 参与出块节点选举, 并获得相应报酬.然而, 随着比特币价格的上涨, 出块节点获得的区块奖励吸引了大量算力加入, 比特币网络中的哈希算力呈指数级增长趋势[64].共识节点参与PoW运算的物理设备从早期的个人电脑转换为GPU, 再演变为目前广泛使用的专用集成电路(application-specific integrated circuits, 简称ASIC)矿机. 因比特币PoW具备计算资源可聚集和可外包的特点, 大多数节点选择加入矿池以保证收入的稳定性[1, 65].伴随计算资源的聚集, 比特币网络出现多个大型矿池.矿池由矿池管理员和矿工构成.如定义2所示, 矿池管理员将计算子任务下发给矿工, 子任务难度值d远低于全网统一难度值D.矿工找到子任务难题解后, 提交给矿池.由于部分子任务难题解也是定义1中比特币PoW难题解, 矿池将获得区块奖励, 并根据矿工根据提交的子任务解的数量分配报酬.矿池子任务难题的设计保证矿工收入的稳定性.截止2019年7月9日, 占比第一的BTC.com矿池拥有21.9%的算力, 前两大矿池拥有33.9%的算力.算力中心化会带来一系列的安全问题[65-67], 例如发动双花攻击、自私挖矿攻击等. 定义2(矿工工作量证明难题). 给定难度值d(d < < D)、区块元数据blockData, 寻找满足条件的Nonce值, 使根据哈希函数SHA-256计算得到的区块哈希blockHash低于目标难度值d: $ blockHash = Hash(blockData,Nonce) \le d. $ 针对比特币PoW算力中心化问题, 一些研究工作和区块链系统提出了改进措施, 包括替换SHA-256哈希函数、设计外包困难的PoW难题、去中心化矿池等.针对SHA-256哈希函数计算密集型的特点, 一些区块链系统选择用内存密集型哈希函数替代原有函数.例如, 莱特币(Litecoin)[18]和狗狗币(Dogecoin)[53]采用Scrypt算法[68], 以太坊[17]采用Ethash算法[69], 大零币(ZeroCash)[54]和小零币(ZeroCoin)[55]采用Equihash算法[70].内存密集型哈希函数由于计算时占用内存多、难以并行计算, 能在一定程度上降低ASIC矿机的算力优势.针对比特币PoW难题可外包的特点, 研究人员修改难题形式使其外包困难, 达到区块链系统去中心化的目标.例如, 文献[56]重新设计比特币PoW难题, 使矿池管理者将计算任务分发给矿工后, 矿工可修改计算任务中获取奖励的地址, 并不被矿池管理者发现.文献[57]实现了基于智能合约的去中心化矿池SmartPool, 矿池可自动执行子任务难题分发与确认工作, 替代矿池管理员, 矿工在获得稳定收入的前提下, 共同维护SmartPool, 从而保持算力的去中心化.2.1.2 资源浪费 比特币工作量证明机制导致的算力资源浪费问题一直被广为诟病.从2016年开始, 比特币网络的哈希率(哈希/秒)呈指数级增长.截至2019年7月, 哈希率达到70EH/s(百亿亿次哈希/秒).现有文献[71]估计, 比特币网络年用电量与爱尔兰或奥地利年用电量相当. 为了解决资源浪费问题, 现有研究工作和区块链系统主要提供了两种改进措施, 即提供有用服务和其他特定能力证明.一些区块链系统利用PoW计算过程中消耗的算力提供有用服务.例如, 素数币(Primecoin)[58]将PoW难题改进为寻找符合要求的素数, 供公众使用, 进而促进数学领域发展.素数币PoW难题的解包括3种形式的素数, 即第1类坎宁安链(Cunningham chain of first kind), 第2类坎宁安链(Cunningham chain of second kind)和双链(bi-twin chain).有用工作证明(proof of useful work, 简称PoUW)[59]提出了基于广泛计算问题的PoW难题, 解决正交向量、最短路径等问题. 除了利用算力提供有用的服务以外, 大量共识协议利用其他特定能力证明, 如权益证明(proof of stake, 简称PoS)[24, 44, 50, 72, 73]、空间证明(proof of space, 简称PoSp, 又被称为容量证明(proof of capacity, 简称PoC)、存储证明(proof of storage, 简称PoSt)[61]、权威证明(proof of authority, 简称PoAu)[62]、信誉证明(proof of reputation, 简称PoR)[63]替代工作量证明.这些特定能力证明中, 节点成为出块节点的概率分别与其拥有的某种稀缺资源相关, 如权益(即加密货币数量)、内存或硬盘存储空间、权威、信誉相关, 与算力无关.例如, 文献[61]的空间证明用内存消耗型难题替代PoW算力难题.PoAu与PoR思想类似, 只有具有较高权威或信誉度的节点才能成为出块节点, 由于区块带有节点签名, 节点被检测到作恶后会丧失出块资格.因此, PoAu与PoR只能用于具有准入机制的许可链系统中, 无法用于非许可链系统.在这几类特定能力证明中, 权益证明受到广泛研究与实际应用, 因此, 我们将在第2.2节详细讨论权益证明机制.2.1.3 性能 比特币工作量证明机制是算力竞争型的出块节点选举机制, 限制了出块环节的性能提升.如前所述, 由于比特币系统平均区块间隔为10min, 区块大小限制为1MB, 因此理论上交易吞吐量约每秒7笔交易.低吞吐量限制了比特币系统的广泛应用.随着比特币系统关注度上升, 网络中未确认交易数增多.截至2019年7月10日, 比特币网络存在近5万笔未确认交易[74].性能问题成为比特币PoW中亟待解决的问题. 针对比特币PoW的低性能问题, 一些研究工作和区块链系统通过修改参数和改进出块节点选举机制提升效率.例如, 以太坊、莱特币、狗狗币系统分别将比特币PoW机制中的区块间隔调整为15s、2.5min和1min[75], 以此加速交易处理速度.缩短区块间隔看起来是改善性能的可行方案, 然而一些研究工作发现, 缩短区块间隔存在安全隐患.文献[11-13]指出: 足够长的区块间隔保证区块数据在P2P网络中广泛传播, 区块间隔缩短会削弱系统安全性.例如, 当攻击者掌握30%系统算力时, 为了达到和比特币系统同等程度的安全性, 以太坊、莱特币、狗狗币系统需要分别等待至少37个、28个、47个区块长度确认[75]. 除以上工作外, Bitcoin-NG[11]通过修改比特币的出块节点选举机制提升交易性能.Bitcoin-NG将区块分为关键块(key block)和微块(micro block)两类: 关键块包含比特币PoW难题的解, 体现出块节点的工作量证明; 微块包含关键块对应的出块节点签名, 但不包含难题的解, 不体现工作量证明.节点生成关键块后, 负责在随后的区块间隔时间内将交易打包进微块并签名.通过验证节点签名, 其他节点判断微块的合法性.通过在区块间隔连续产生微块, Bitcoin-NG实现了在出块节点选举环节加速交易处理.关键块和微块的概念随后也在Byzcoin[15]中得到应用.2.1.4 总结 工作量证明机制广泛应用于区块链共识协议的出块节点选举环节.针对算力中心化、资源浪费、低性能等问题, 一些研究工作和区块链系统针对工作量证明机制进行改进.在工作量证明机制的调研过程中, 我们发现一些可行研究点. ●   首先, 工作量证明改进工作多以白皮书的形式提出, 缺乏理论及实验数据支撑.例如, 以太坊系统等白皮书大多从概念层面进行论述, 没有相关实验数据支撑, 也没有进行安全性证明. ●   其次, 众多的工作量证明改进机制之间缺乏相互比较, 无法判读其优劣势.例如, 包括Scrypt[68]、Ethash[69]、Equihash[70]在内的众多内存密集型哈希函数没有相互比较, 尚不清楚这些算法针对算力中心化问题的改进程度.值得注意的是, 目前已出现针对以上内存密集型哈希函数的专用矿机. ●   再者, 由于分布式系统的各方面复杂因素, 对协议进行参数调整需要加以严格的安全证明.例如, 莱特币等调整参数的改进方案看似可行, 但被证明存在安全隐患[13], 最终没能达到预期效果.2.2 权益证明机制 针对工作量证明机制的资源浪费问题, 比特币社区[76]在2011年首次提出了权益证明机制, 根据节点掌握的比特币数量而不是算力作为权重选举出块节点.权益证明机制的安全性基于权益拥有者比矿工更有动力维护网络安全的假设[44, 72, 76], 当区块链系统遭到攻击, 权益拥有者自身利益更容易受损.2012年, 权益证明机制首次在点点币(peercoin/ppcoin)[44]系统中得到应用.点点币以权益作为选举权重, 提出了权益证明难题. 定义3(点点币权益证明难题). 给定全网统一的难度值D, 区块元数据blockData, 寻找满足条件的时间戳timeStamp, 使根据哈希函数SHA-256计算得到的区块哈希blockHash低于目标难度值.目标难度值为全网统一难度值D和币龄coinDay的乘积.币龄是节点持有权益(即节点持有的数字货币数量, coin)与持有时间(day)的乘积: $ blockHash = Hash(blockData,timeStamp) \le D \times coinDay. $ 与比特币工作量证明难题相比, 点点币权益证明难题主要有两处不同: 哈希运算中移除随机数Nonce, 引入币龄调整难题难度.由于移除随机数Nonce, 点点币权益证明难题减轻了工作量证明难题算力竞争问题.在给定元数据blockData的情况下, 共识节点在求解点点币权益证明难题中, 可尝试的只有时间戳变量.由于点点币采用以秒计数的UNIX时间戳, 节点求解难题时尝试空间有限.因此, 点点币权益证明难题大大缩小了工作量证明难题的计算尝试空间, 减缓了算力竞赛带来的资源浪费问题. 点点币以币龄作为权重, 实现根据权益选举出块节点的目标, 币龄的概念随后在披风币(Cloakcoin)[77]和新星币(Novacoin)[78]中也得到应用.币龄是用户权益和持有时间的乘积.假设用户A拥有10个点点币并持有90天, 累计900币龄.用户B拥有10个点点币并持有45天, 累计450币龄.根据点点币权益证明难题, 用户A解决难题的可能性2倍于用户B. 点点币权益证明难题创新性地使用币龄概念衡量权益, 使得持有较多数字货币并活跃的节点更积极参与系统运行, 但也存在不足.不活跃节点可能通过长期持有权益累积大量币龄, 提高自己成为出块节点的可能性, 从而等待发动攻击的时机.针对这一问题, 未来币[45]和黑币[79]在权益证明难题中以权益替代币龄, 维理币[80]使用类似币龄的权益时间(stakeTime)概念, 节点离线后权益时间会逐渐减少, 活动证明(proof of activity, 简称PoA)[50]将权益证明与工作量证明结合, 使得只有在线的活跃节点才能获得挖矿收益和交易费.这几种方法都用于改进点点币系统中不活跃节点问题.2.2.1 基于随机函数的权益证明 以上所述的权益证明机制在一定程度上缓和了工作量证明机制的算力浪费问题, 但采用的仍是基于难题求解的竞争性选举机制.为了进一步解决算力浪费问题、提高出块节点选举效率, 随后的大量研究工作[14, 24, 72]采用基于随机函数的权益证明机制.这类机制采用以权益作为权重的随机算法确定出块节点, 同时, 其他节点可通过随机算法验证出块节点身份的正确性.由于不再利用算力竞争成为出块节点, 基于随机函数的权益证明属于非竞争性选举机制. 活动证明[50]、活动链(chains of activity, 简称CoA)[71]和Ouroboros[24]利用follow-the-satoshi算法[50]随机选举出块节点.聪(satoshi)是比特币的最小货币单位, follow-the-satoshi算法将零和比特币发行总量(以聪为单位)间的一个随机数作为输入, 通过追溯区块数据, 找到目前持有该货币的节点, 该节点即成为出块节点.假设用户A持有10个比特币, 用户B持有5个比特币, 用户A被follow-the-satoshi算法选中的概率2倍于用户B.因此, follow- the-satoshi算法实现根据权益进行出块节点选举. 表 3 对基于随机函数实现权益证明的研究工作及系统进行总结.PoA[50]、CoA[72]和Ouroboros[24]采用不同方式更新follow-the-satoshi算法的随机种子.PoA[50]中, 出块节点首先需要生成满足PoW的空区块(不包含交易, 只包含区块元数据的空区块)哈希, 将该哈希作为随机算法输入, 选出一组背书节点.出块节点搜集一定数量背书节点签名后才能打包交易、生成合法区块.因此, PoA[50]的出块节点选举机制实质是PoW和PoS的结合, PoW区块哈希的不可预测保证了PoS选举结果的不可预测.CoA[72]将当前区块的前N个区块哈希作为随机算法输入, 选出后N个区块的出块节点.Ouroboros[24]基于安全多方计算(multi-party computation, 简称MPC)更新随机种子.Ouroboros将多个区块间隔称为一个纪元(epoch), 纪元内的出块节点共同组成组委员(committee), 组委会节点参与MPC算法, 合作更新随机种子.Algorand[14]基于可验证随机函数(verifiable random function, 简称VRF)进行出块节点选举, 各节点利用自己的私钥和全网统一的随机种子作为算法输入, 判断自己是否是本轮的出块节点.若成为出块节点, 节点将同时出示算法生成的选举证明, 供其他节点验证.前一区块间隔的出块节点利用VRF函数更新下一间隔的随机种子.除了以上基于随机函数的出块节点选举机制外, Tendermint[81]采用确定性轮询算法决定出块节点, 每个区块间隔将确定性产生一个出块节点. Table 3 PoS mechanisms based on random algorithms 表 3 基于随机算法的权益证明机制 2.2.2 问题及解决方案 在出块节点选举环节, PoS以权益替代算力作为选举权重, 解决了算力浪费问题.随着对权益证明工作的推进, 研究人员发现PoS也存在一些问题, 主要包括粉碎攻击、无权益攻击和长程攻击.表 4对权益证明机制的问题及其解决方案进行总结. Table 4 Problems and corresponding solutions of PoS mechanism 表 4 权益证明机制的问题及其解决方案 粉碎攻击(grinding attack)指节点通过尝试随机参数提高成为出块节点概率的一类攻击形式.例如, 攻击者通过尝试点点币权益证明难题中的时间戳(timeStamp)和拥有的多个账户币龄提高成为出块节点概率[60].与点点币类似, 未来币中也有时间戳尝试和公钥尝试问题.除此以外, 基于随机函数的权益证明可提前尝试随机种子, 提高随后被选中为出块节点的概率[24, 50, 60].由于随机种子基于以前的区块哈希, CoA[72]可能会遭到粉碎攻击[24]. 粉碎攻击的解决方案主要包括参数不可尝试以及随机种子限制: 前者指权益证明难题中不包括可尝试参数; 后者指随机种子尽量不依赖区块本身信息, 否则存在随机算法偏向某一节点的可能.例如, Ouroboros[24]和Ouroboros Praos[82]利用多方安全计算产生随机算法种子, 既解决了可尝试参数问题, 同时保证随机性与区块信息无关. 无权益攻击(nothing-at-stake)指被选中的出块节点在同一高度产生多个区块, 导致区块分叉无法解决的问题.无权益攻击是出块节点出于利益最大化作出的选择.如图 2所示, 基于权益证明的区块链系统在高度h处出现分叉, 节点A是高度h+1的出块节点, 由于尚不确定在高度h上被最终确认的区块, 节点A选择同时在多个分叉块后产生区块.因此, 无论最终哪一区块是合法区块, 节点A都可获利. Fig. 2 Illustration of nothing-at-stake attack 图 2 无权益攻击图示 无权益攻击的攻击成本低, 出块节点无需任何代价即可生成多个区块, 最终导致多个分叉区块齐头并进, 永远无法达成共识.无权益攻击的现有解决方案主要包括保证金制度和安全硬件.保证金制度指共识节点需在账户中存取一定金额保证金, 若节点被监测发动无权益攻击, 则罚没其保证金, 从经济激励角度解决无权益攻击.例如, 以太坊的PoS提案Slasher[83]和Casper[84]都引入了保证金制度.类似地, Tendermint[85]也引入了保证金机制, 且保证金比例和共识票数成正比.除此以外, 文献[86]基于可信执行环境(trusted execution environment, 简称TEE)的安全硬件, 限制节点在同一高度只能生成一个区块. 长程攻击(long range)指攻击者试图从某一高度区块后重新生成后续所有区块, 覆盖这一区间区块数据, 也被称为历史攻击(history attack).由于长程攻击要求攻击者的区块生成速度快于其他节点, 因此理论上只有掌握超过50%权益的攻击者才能发动长程攻击, 然而实际上, 攻击者可通过控制或贿赂历史时刻拥有大量权益的节点[86]发动长程攻击.例如, 攻击者A拥有21%的权益, 节点B在某一历史时刻拥有30%的权益, 随后将30%权益转让他人, 攻击者可通过控制或贿赂的手段, 利用节点B在历史时刻拥有的权益, 从该时刻重新生成区块. 由于节点转移权益后不再有维护系统安全的动机, 攻击者可通过贿赂历史时刻拥有大量权益的节点发动长程攻击.针对这一问题的解决方案主要包括移动检查点机制和密钥演进加密技术.移动检查点机制[87]将某一历史高度的区块作为检查点, 检查点前的区块不可篡改.移动检查点机制在点点币[44]、未来币[45]、黑币[79]、snow white[88]中得到使用.点点币和黑币依赖中心服务器定期发布检查点.未来币[45]不接受720个区块以前的历史区块分叉.与未来币类似, snow white[88]不接受对距离当前区块太远的历史区块分叉.除了检查点机制以外, Ouroboros Praos[82]采用密钥演进加密技术解决长程攻击[87].节点随着时间需要不断演变私钥, 当攻击者盗取了节点目前的密钥时, 由于不能伪造过去的签名, 无法利用节点的历史权益发送长程攻击. 除以上安全问题外, 委托权益证明(delegated proof of stake, 简称DPoS)[89]通过投票机制缩小共识节点范围, 使PoS在大规模网络中得以高效应用.DPoS中的票数与权益成正比, 权益所有者投票选出一部分节点作为候选出块节点, 这些节点再利用PoS的随机算法成为出块节点.节点若在给定时间段内未完成出块, 将被移出候选出块节点列表.因此, 持有权益较少的节点可通过投票维护系统安全, 而不必购买专业硬件设备成为共识节点.投票机制还可用于权益所有者修改系统参数, 包括交易大小、区块间隔、交易费规则等, 实现了区块链系统自治.2.2.3 总结 权益证明机制由早期基于难题的竞争性机制, 逐渐演变为基于随机函数的非竞争性出块节点选举机制.后者由于安全且高效, 是目前权益证明共识协议的重点研究方向.我们在调研过程中发现, 尽管研究成果众多, 目前尚没有权益证明机制及其安全问题的综述研究.因此, 本文对权益证明及其3种主要攻击方法和对应解决方案进行总结.此外, 相比工作量证明机制, 采用权益证明机制的区块链系统仍较少.再者, 一些区块链系统采用工作量证明和权益证明结合的方式, 前期利用工作量证明完成权益的初始分配, 再逐渐过渡到权益证明机制, 例如以太坊、点点币等.但是, 目前尚没有关于工作量证明如何安全过渡到权益证明的相关研究.3 主链共识 主链共识指分布式网络节点对区块数据达成一致的过程.如前所述, 在区块链系统运行流程中, 分布式网络中的节点根据出块节点选举机制成为出块节点、生成新区块并广播.由于出块节点选举机制存在同一高度产生多个区块的可能, 节点本地维护区块形成的树状结构, 即区块树(block tree)[12], 因此, 节点需要利用主链共识对区块树中最终的区块链数据达成一致. 根据区块数据是否满足最终一致性, 主链共识可分为概率性共识和确定性共识: 概率性共识中区块数据以一定概率达成一致, 随着时间推移概率逐渐提高, 不能保证区块数据将来不可更改, 这种一致性也称为弱一致性; 确定性共识中一旦区块数据达成一致便不可更改, 又被称为强一致性.3.1 概率性共识 非许可链系统广泛使用达成概率性共识的主链选取规则.由于非许可链网络规模较大[36, 37], 消息传输时间长、传输代价高, 因此通常采用一轮广播即可达成共识的主链选取规则.在这类规则中, 出块节点将生成的新区块广播给其他节点, 节点使用主链选取规则从本地区块树中确定主链区块, 各节点的主链区块随着时间推移接近一致.3.1.1 最长链规则 最长链规则在比特币白皮书[2]中首次提出, 选取区块树中的最长分支作为主链.由于比特币采用工作量证明机制, 最长链累积着最多的工作量证明.根据比特币白皮书中“一处理器一票”的思想, 最长链可被视为分布式网络中大部分节点投票做出的决定.因此, 只要大部分算力由诚实节点掌握, 分布式网络就可以利用最长链规则对区块数据达成一致.最长链规则是目前应用最广泛的主链选取规则, 在一系列研究工作[11, 24, 50, 72]和区块链系统[17, 18]中得到使用. 假设节点的本地区块树如图 3所示, 区块树中最长的分支(虚线分支)将成为主链.交易确认数指交易所在区块的长度, 交易未被打包时称为0次确认(0-confirmation), 交易被区块包含称为1次确认(1-confirmation).随着区块被后续区块不断链接, 确认数不断增加.交易确认数越多, 一致性概率越高、安全性越高.在图 3中, 交易3(tx3)为1次确认, 交易1(tx1)为2次确认, 交易2(tx2)则是5次确认.因此, 交易2安全性高于交易1, 交易1高于交易3.比特币白皮书[2]中的分析表明: 假设攻击者拥有10%的系统算力, 6次确认交易的安全性高于99.9%.为兼顾系统安全性与系统效率, 比特币客户端根据交易金额的大小为交易推荐不同确认数[90], 金额较大交易确认数越多, 保证交易安全性. Fig. 3 Illustration of the longest chain rule 图 3 最长链规则图示 最长链规则性能受到协议参数和网络环境的影响, 如区块间隔、区块大小、交易大小、网络规模、带宽等.如表 5所示, 比特币系统中, 当区块大小为1MB、区块间隔为10min、交易大小为250字节时, 交易吞吐量(transaction per second, 简称TPS)约等于7, 比特币系统从2018年1月至今的平均交易确认时延大于10min[91]. Table 5 Performance analysis of probabilistic consensus protocols 表 5 概率性共识协议的性能分析 3.1.2 GHOST规则 文献[12]发现, 在交易请求增多时, 比特币不得不频繁地创建大区块以提高交易吞吐量.大区块将导致区块传输时间延长, 使得分叉块增多、诚实节点算力分散, 此时, 恶意节点将更容易发动攻击.为了在交易请求增多时依然保证较高安全性, Sompolinsky等人提出了GHOST(greedy heaviest-observed sub- tree)[12]规则作为最长链规则的替代. 图 4展示了一种网络中出现多个分叉块的情形, 当诚实节点的算力被分散时, 最长链规则的安全性降低.例如, 攻击者秘密生成一条私有区块链(黑色链条), 当私有区块链长度超过网络中公开的最长链时将其发布, 根据最长链规则, 攻击者的私有区块链将成为主链.攻击者可通过私有区块链发动双花攻击, 从而破坏区块链系统安全性.在最长链规则中, 主链外区块都被视为分叉块抛弃, 不用于维护系统安全性.与最长链不同, GHOST规则将分叉块纳入主链选取规则, 区块树中最重子树的区块将构成主链, 又被称为最重链.由于最重链代表网络中的大部分算力, 文献[12]认为: 只要诚实节点掌握大多数算力, GHOST规则在网络交易吞吐量高的情况下也能保证安全性.如图 4所示, 尽管攻击者生成更长的私有区块链, 由于没有累积足够多的工作量证明, 无法替代GHOST规则选出的最终链.GHOST规则随后在包容性协议[26]和Conflux中用来选择主链, 但据我们所知, 该规则目前并未直接应用于非许可链系统中(我们注意到: 以太坊声称使用GHOST规则来选取主链, 并实现了一个GHOST的简化版本[12], 但项目代码[92]显示, 目前采用的仍是最长链规则). Fig. 4 Illustration of GHOST rule 图 4 GHOST规则图示 如表 5所示, 当区块间隔为1s、区块大小为1MB、网络规模为1 000节点时, GHOST协议的吞吐量约为200.文献[12]中未给出交易确认时延的实验数据.值得注意的是, 文献[12]在相同实验条件下对比了GHOST与最长链规则的性能, 实验结果显示: 在不同参数设置中, GHOST的吞吐量都略低于最长链规则, 但其在处理高吞吐量交易时拥有更高安全性能.GHOST的安全性将在第3.1.6节中详细讨论.3.1.3 包容性协议 包容性协议[26]将GHOST规则与有向无环图(directed acyclic graph, 简称DAG)结合, 进一步提高交易吞吐量.包容性协议修改了以比特币为代表的传统区块链数据结构, 区块可以指向多个父区块而不是唯一一个, 新区块将所有没有被指向的区块(即叶子区块)作为父区块, 因此, 包容性协议中区块构成了有向无环图而不是区块树.基于该有向无环图, 包容性协议首先利用GHOST规则选出主链, 遍历主链区块的多个分叉父区块, 如果分叉块中的交易和主链交易没有冲突, 则将分叉块也纳入主链中.通过利用分叉块交易内容, 包容性协议进一步提升交易通量, 并且对于网络连接差、不能及时广播区块的节点更加友好. 如表 5所示, 当区块间隔为1s、区块包含50笔交易、网络规模为100节点时, 包容性协议的吞吐量约为30.文献[26]中未给出交易确认时延的实验数据.3.1.4 SPECTRE协议 SPECTRE[51]协议利用成对投票(pair voting)解决冲突区块问题, 提高系统吞吐量并保证安全性.与包容性协议类似, SPECTRE中新区块指向多个父区块, 形成有向无环图, 在此基础上运行投票规则. 假设区块x和y是一对包容冲突交易的区块, z区块将对冲突区块进行投票, 投票规则如下. 1)   z是x的后代区块, 不是y的后代区块, z投票给x, 表示为x≤y. 2)   z同时是x和y的后代区块, 则根据本区块之前有向无环图的区块投票结果确定.如果投票数量相等, 则根据预定义规则决定(区块哈希的字典顺序等). 3)   z既不是x的后代区块, 也不是y的后代区块, 则根据本区块之后有向无环图的区块投票结果确定.如果投票数量相等, 则根据预定义规则决定. 图 5展示了SPECTRE协议的运行规则.交易x和y是攻击者发起的两笔冲突交易, 交易x是攻击者支付给商家的正常交易, 交易y是恶意交易.将交易x广播之前, 攻击者预先生成包含交易y的区块及之后两个区块(区块13、区块14)并隐藏.为了欺骗商家获得收益, 攻击者首先广播交易x, 并等待交易x被包含到区块中.商家确认交易x后, 攻击者将隐藏区块链发布出来, 企图替代交易x所在的区块链. Fig. 5 Illustration of SPECTRE protocol 图 5 SPECTRE协议图示 在SPECTRE协议中, 节点可并行产生区块, 随后再用投票规则处理冲突区块, 整体上提升交易处理速率; 同时, 投票规则保证攻击者的隐藏区块链无法颠覆主链.由图 5可知, 除攻击者产生的所有区块都认可交易x.区块6~区块10是区块x但不是区块y的后代, 根据规则1投票给x.区块1~区块5不是x和y的后代, 根据规则3投票给x.区块11、区块12是x和y的后代, 根据规则2投票给x.SPECTRE基于工作量证明机制选举出块节点, 文献[51]认为: 只要网络中诚实节点掌握大多数算力, 投票机制可不断提升历史交易优势, 从而消除来自恶意节点隐藏区块链的威胁[93], 保证系统安全性. 如表 5所示, 当区块间隔为0.1s、区块大小为100KB时, SPECTRE协议的交易确认时延约为11s.文献[51]中未给出交易吞吐量的实验数据.3.1.5 Conflux协议 Conflux[25]协议基于有向无环图计算出区块内交易的全局顺序, 通过剔除冲突交易, 使所有分叉块内的交易得到利用, 从而提升系统吞吐量.Conflux的区块间有两类指向关系: 父边(parent edge)和引用边(reference edge).父边指向父区块, 每个区块只有一条父边.除父边外, 区块可以有多条引用边, 引用边指向所有目前没有被父边引用的叶子区块, 引用边代表时间上的发生在先(happen-before)关系.Conflux利用GHOST规则选出有向无环图中的主链, 利用主链和两类指向关系对所有区块进行全局排序.基于区块的全局排序, 区块内的交易也达成全局排序.随后, Conflux从交易全局排序中剔除掉重复和冲突的交易, 对余下交易达成共识. 与包容性协议和SPECTRE协议相比, Conflux将共识粒度从区块细化到交易, 利用交易排序算法将所有分叉块里的交易得以利用, 因而提升了交易吞吐量.文献[25]将Conflux协议与工作量证明的出块节点选举机制结合, 同时, Conflux也可与其他出块节点选举机制结合, 例如权益证明机制. 如表 5所示, 当区块间隔为5s、区块大小4MB、交易大小250字节、网络规模1万节点时, Conflux的吞吐量为3 200, 远高于相同实验参数设置下的最长链和GHOST规则.但由于使用GHOST规则选举主链, Conflux的交易确认时延和GHOST一致, 都是10min.3.1.6 安全分析 由于大量共识协议[14, 15, 24]围绕持久性和活性进行安全性分析, 本节主要从持久性和活性两方面对概率性共识进行安全性分析.文献[13, 94, 95]基于传统分布式协议的安全性和活性目标, 提出并总结了区块链共识协议中持久性和活性目标.由于大部分概率性共识与工作量证明机制结合, 因此概率型共识的安全性分析主要基于工作量证明的出块节点选举机制. ●   持久性(persistence) 持久性衡量概率性共识中区块链数据的一致性.持久性指如果某区块在节点的本地区块链中拥有k个区块的深度, 该区块在其他节点的本地区块链中(极大概率)也拥有k个区块的深度.由于网络传播等限制, 各个节点的本地区块链可能暂时不一致, 但k个区块之前的数据(极大概率)是一致的. ●   活性(liveness) 活性衡量概率性共识中区块链系统的可用性.活性指诚实节点发起的交易最终被打包进节点区块链中, 并满足持久性.由于网络吞吐量等限制, 诚实节点发起的交易可能不会立即被处理, 但最终会被处理. 诚实节点掌握大多数算力的情况下, 最长链规则在同步和异步网络中都满足持久性和活性要求.比特币白皮书[2]对基于工作量证明的最长链规则首先进行了非正式分析, 在网络同步且诚实节点掌握大多数算力时, 协议满足持久性要求.随后, 文献[13]对最长链规则进行了理论证明, 在网络同步且诚实节点拥有大多数算力的情况下, 最长链规则满足持久性和活性要求.在此基础上, 文献[96]证明了最长链规则在延迟时间有上界的异步网络中, 且诚实节点拥有大多数算力的情况下, 满足持久性和活性要求, 并可以适应算力动态变化. 在诚实节点掌握大多数算力情况下, GHOST规则满足持久性和活性要求, 但活性弱于最长链规则.GHOST规则[12]作为最长链规则的替代, 只要诚实节点掌握大部分算力, 在网络交易吞吐量高的情况下, 依然可以保证安全性.文献[97]理论证明了GHOST协议满足持久性和活性, 然而文献[97]认为: 在网络交易吞吐量高的情况下, GHOST规则相对最长链规则并没有性能优势.除此以外, 文献[97]提出了一种针对区块链活性的攻击方法, 通过干扰交易和区块的传播, 拖延交易的确认时间, 从而破坏活性.在这种攻击方式下, GHOST的活性弱于最长链规则.由于Conflux利用GHOST协议选择主链, 因此安全性质和GHOST相同[25]. 在诚实节点掌握大多数算力的情况下, 包容性协议满足持久性和活性.文献[26]未对包容性协议进行理论证明, 但通过实验方式显示, 协议可满足持久性和活性. 在诚实节点掌握大多数算力的情况下, SPECTRE协议可保证区块链系统的持久性和弱活性(SPECTRE协议中未对持久性(persistence)进行证明, 但其中的一致性、安全性与持久性同一定义, 因此我们将其看做对持久性的证明)[51].SPECTRE协议在交易内容互不冲突时, 能保证交易在有限时间内被打包到区块中, 即满足活性要求.然而, 当攻击者同时发起两笔冲突交易时, 合法交易只能满足弱活性, 即交易最终会被打包到区块中, 但时间有明显延迟. 在与工作量证明机制结合的情况下, 大部分概率性共识协议存在激励相容(incentive compatibility)问题.激励相容问题指节点的个人目标与系统目标不一致, 其中最典型的是自私挖矿问题.在工作量证明机制的基础上, 为鼓励节点加入网络维护安全, 系统通常以数字货币形式给出块节点一定报酬.然而大量研究工作[65, 66, 98, 99]发现, 当节点掌握算力达到一定程度时, 理性节点选择不遵守协议将获得更高的收益.这些节点被称为自私挖矿节点, 他们将生成的新区块隐藏起来, 并选择在将来的适当时机公开, 从而获得更高收益.这些隐藏区块可能会颠覆网络的公开区块, 引发安全问题. 文献[65]首次发现最长链规则中的自私挖矿问题.在自私挖矿影响下, 最长链规则的安全边界从50%降低到33%, 即只能抵御算力不超过33%的恶意节点.随后, 一系列研究工作[66, 98]在最长链规则上拓展不同的自私挖矿策略, 进一步降低系统安全边界.与最长链规则类似, GHOST规则和包容性协议也受到自私挖矿的影响[26, 66]. SPECTRE协议没有说明是否存在自私挖矿问题.此外, 由于Conflux协议基于GHOST规则选择主链, 也有同样的自私挖矿问题. 表 6 对以上讨论的概率性共识协议安全性质进行总结.除包容性协议以外, 以上概率性共识都从理论上证明满足持久性和活性目标.目前仅有最长链和GHOST规则在持久性和活性上的对比分析工作, 其他概率性共识之间缺乏对比.其次, GHOST规则在研究工作中备受关注, 但缺乏区块链系统应用, 以太坊目前仍采用最长链规则.再者, 几乎所有基于工作量证明的概率性共识都存在自私挖矿问题, 目前, 自私挖矿问题在最长链规则上得到大量研究, 但在其他概率性共识上的研究较少. Table 6 Analysis of the security properties of probabilistic consensus protocols 表 6 概率性共识协议的安全性质分析 3.2 确定性共识 概率性共识在交易延迟与安全性存在天然的权衡问题[100], 限制了区块链技术的应用场景.因此, 一些研究工作采用确定性共识确保区块数据的强一致性.概率性共识的权衡问题源于区块数据的一致性概率随着时间推移逐渐提高, 为保证交易安全性, 用户不得不等待多个区块确认, 带来明显的交易延时.延时问题限制了基于概率性共识的区块链系统的商业应用, 因此, 一些研究工作[14-16, 28]采用确定性共识替代概率性共识.如上所述, 在确定性共识中, 区块一旦写入节点本地区块链, 就不存在随后被改变的可能性.确定性共识有两个明显优势[15]: 首先, 用户不用等待较长时间确保交易安全性; 其次, 由于同一高度仅有一个合法区块, 节点不用在分叉区块上浪费计算资源. 拜占庭容错协议用于解决分布式系统中的拜占庭将军问题, 在存在恶意节点的情况下达成一致性.拜占庭将军问题由Leslie Lamport在1982年[31]提出, 诚实将军在叛徒将军的干扰下对进攻命令达成一致.拜占庭将军问题是分布式系统中正常组件在故障组件干扰下达成一致的抽象描述. 经典的拜占庭容错协议通常面向中心化的分布式集群达成确定一致性, 如PBFT[27]、Byzantine Paoxs[101]等, 但无法直接应用在区块链系统中.在这些协议中, 共识节点数量固定或者变化缓慢[27], 节点之间需要多轮广播通信[102], 通信复杂度较高.然而区块链系统中的节点数量不断动态变化, 区块链系统(特别是非许可链)的网络规模也不支持节点间的多轮广播通信, 因此, 区块链拜占庭容许协议需要适应系统特点进行改进.3.2.1 非许可链拜占庭容错协议 为了在网络规模较大的非许可链系统中达成确定性共识, 一些研究工作[14, 15]将拜占庭容错协议和区块链的出块节点选举机制相结合, 被称为混合协议[103].混合协议也分为出块节点选举和主链共识两个阶段: 在出块节点选举阶段, 混合协议采用区块链的选举机制, 抵御开放网络中的女巫攻击等问题; 在主链共识阶段, 混合协议通常让多个出块节点构成组委会, 运行拜占庭容错协议, 对新区块达成一致.组委会成员通常随着时间变化[103]. Algorand[14]是权益证明和拜占庭容错协议结合的混合协议.在出块节点选举阶段, Algorand利用基于随机函数的权益证明选出一组出块节点, 每个节点发起区块提案(block proposal)并广播, 各提案附有随机优先级, 每个节点只保留优先级最高的区块; 随后, 节点再运行一轮拜占庭一致性协议(BA*), 将自己接收到的最高优先级区块作为输入, 对区块达成共识. Algorand中的拜占庭一致性协议分为两个阶段: 归约(reduction)和二进制一致性(binary agreement). 规约阶段保证各节点持有相同的最高优先级区块, 解决网络传输导致的节点本地最高优先级区块可能不一致的问题.在规约阶段, 所有节点广播自己本地最高优先级的区块哈希, 接收到其他节点的区块哈希后, 节点统计每个区块的票数, 认定票数最高的区块为最高优先级区块; 没有票数最高区块时, 将空区块作为最高优先级区块.归约阶段达成一致的区块将作为二进制一致性阶段的输入. 二进制一致性阶段对规约阶段生成的区块达成确定性共识.在二进制一致性阶段, 出块节点选举环节发起区块提案的节点形成组委会, 对规约阶段的区块投票.区块收到一定数量票数后, 就被确认为最终区块.所有节点将该区块更新到本地区块链中, 达成确认性共识.由于网络原因, 二进制一致性阶段的投票可能会重复多次.如表 7所示, 当区块间隔为1min、区块大小为1MB、网络规模为5万节点时, Algorand的交易吞吐量达到327MB/h, 交易确认时延小于1s. Table 7 Performance analysis of deterministic consensus protocols 表 7 确定性共识协议的性能分析 Byzcoin[15]是工作量证明和实用拜占庭容错协议结合的混合协议.Byzcoin首先利用工作量证明机制选举出块节点、生成新区块, 随后再利用实用拜占庭容错协议对新区块达成确定性共识.如图 6所示, 在出块节点选举阶段, 节点利用工作量证明生成新区块并广播.一个时间间隔(1天或1周, 可调整)内的出块节点构成组委会.组委会成员的票数为在该时间间隔内的出块数量, 成员利用实用拜占庭容错协议对新区块投票达成共识.出块节点广播新区块, 组委会成员验证区块无误后返回签名作为投票, 出块节点搜集至少2/3票数后, 广播组委会成员签名, 证明新区块已经被组委会接收并验证.组委会成员接收到广播信息后, 再次返回签名, 表示同意将该区块写入区块链中, 出块节点搜集至少2/3票数后, 再次广播区块, 并写入区块链中.至此, 共识节点对该区块达成确定性共识.由于通信过程中涉及大量签名和验签操作, 为提高效率, Byzcoin引入集体签名技术, 可一次同时验证多个签名.如表 7所示, 当关键块间隔为10min、区块大小为32MB、网络规模为144节点时, Byzcoin的TPS为974, 时延为68s. Fig. 6 Byzcoin hybrid consensus protocol 图 6 Byzcoin混合共识协议 不同于Algorand和Byzcoin采用混合协议, Stellar共识协议[28]采用联邦拜占庭协议(federated Byzantine agreement, 简称FBA)达成共识.Stellar是一个开放的实时跨境支付系统[104], 为了使拜占庭协议支持非许可链中开放成员的需求, 引入仲裁系统分片(quorum slice)达成共识.在拜占庭协议中, 仲裁系统指可达成共识的一组节点.仲裁系统分片是仲裁系统子集.Stellar的仲裁系统基于某种标准划分, 例如声誉或权益, 节点可同时加入多个仲裁系统分片.仲裁系统分片保持交集, 保证共识达成. Stellar共识协议主要分为投票、接收和确认这3个阶段. ●   在投票阶段, 节点对接收到的交易进行投票并广播投票信息. ●   在接收阶段, 若节点v-blocking集合中的所有节点都投票给该交易, 则接收该交易.v-blocking是和该节点所在的全部仲裁分片有交集的节点集合. ●   在确认阶段, 节点间通过消息交互对接收阶段的交易达成最终共识.仲裁分片互相影响, 最终保证所有诚实节点对交易达成确定性共识. 文献[28]中未给出Stellar协议的实验数据.3.2.2 许可链拜占庭容错协议 如上所述, 许可链根据应用场景不同分为联盟链和私有链, 其中, 企业级联盟链是目前应用最广的许可链系统.由于网络规模限制、共识一致性要求高, 许可链更适合采用拜占庭容错协议[38].目前的一些研究工作[16]和系统[19, 80, 105]探索拜占庭容错协议在许可链中的应用. HoneyBadger[16]首次将实践拜占庭容错协议应用到纯异步许可链中.HoneyBadger系统中, 共识节点身份已知且数量固定, 节点两两建立经过认证的可信通道.为了消除出块节点广播区块这一环节的带宽瓶颈, HoneyBadger没有采用出块节点选举机制, 取而代之的是: 各节点在每轮出块开始时, 从本地交易缓冲池中选择部分交易进行广播.为了避免拜占庭节点故意忽略某些交易从而影响系统活性, 节点不广播交易内容本身而是经门限加密后的交易密文.所有节点收到密文集合后, HoneyBadger通过拜占庭协议对一组位向量(bit vector)达成共识, 假设位向量第N位为真, 则将密文集合对应的第N位密文还原, 并将其中包含的交易写入区块.如表 7所示, 当交易大小为250字节、网络规模为104节点时, HoneyBadger的TPS为1 500, 时延小于6min. 联盟链系统Tendermint[81]采用基于轮询机制的实用拜占庭容错协议对新区块达成共识.在出块节点选举环节, Tendermint采用确定性轮询机制决定出块节点.由于未采用类似工作量证明的身份定价机制, 为防止拜占庭节点发动女巫攻击, 系统规定节点必须在账户存入保证金才能参与拜占庭容错协议的投票过程, 保证金数额与票数成正比.在网络弱同步且诚实节点掌握至少2/3票数的情况下, Tendermint满足安全性和活性.如表 7所示, 当区块大小为1万笔交易、交易大小为250字节、网络规模为全球64节点时, Tendermint的TPS约为4 000, 延迟约等于2s[81]. 除使用拜占庭容错协议外, 一些企业级区块链系统采用CFT协议而非BFT协议达成确定性共识.2016年初, Linux基金会发起了Hyperledger项目, 旨在建立企业级区块链框架[106], 目前已有超过270个机构加入[107]. Hyperledger Fabric(以下简称Fabric)是Hyperledger项目中备受关注的一个子项目, 打造面向许可链的分布式数据平台.Fabric v0.5采用了PBFT协议在共识节点之间对交易内容实现共识[106], 目前最新的Fabric v1.4用Raft和Apache Kafka两种CFT协议实现共识[108].3.2.3 安全分析 确定性共识需要满足安全性和活性两个基本性质对应概率性共识中的持久性和活性.此外, 由于不存在分叉, 确定性共识不存在概率性共识中的自私挖矿问题[14, 15]. ●   安全性(safety)衡量确定性共识中区块链数据的一致性[109].如果某区块被写入节点的本地区块链中, 该区块也被其他节点写入本地区块链中.即各节点在同一高度拥有相同区块. ●   活性衡量确定性共识中区块链系统的可用性.活性指由诚实节点发起的交易最终会被打包进区块链中、并且满足持久性.由于网络吞吐量等限制, 诚实节点发起的交易可能不会立即被处理, 但最终会被处理. 在强同步网络及诚实节点掌握至少2/3权益的情况下, Algorand满足安全性和活性.Algorand拜占庭一致性协议(BA*)基于强同步网络, 大多数(如95%)诚实节点发送的消息在已知时间间隔内可发送给其他大多数诚实节点.BA*在弱同步网络情况下不能达成一致性, 需要等待网络变为强同步.Algorand采用权益证明的出块节点选举机制, 要求诚实节点掌握系统中至少2/3的权益.最好情况下, 即每个节点收到的最高优先级区块一致时, Algorand需要节点间的四轮交互达成共识; 最坏情况下则需要13轮.文献[14]利用1 000台虚拟机模拟50 000用户运行Algorand协议, 实验显示: 确认1MB大小的区块需要约22s延迟; 区块大小为10MB时, Algorand吞吐量为750MB/h. 在弱同步网络及节点总数至少3f+2的情况下, Byzcoin满足安全性和活性.Byzcoin是实用拜占庭容错协议和工作量证明的混合协议, 网络环境要求和实用拜占庭容错协议一致, 即消息延迟有上限但上限不可知的弱同步环境.当网络存在f个恶意节点时, Byzcoin需要至少3f+2节点数才能达成共识.文献[15]在1 008个节点上运行Byzcoin协议, 当区块大小为1MB~2MB时, 交易延迟为10s~20s, 交易吞吐量为700笔/秒. 在同步网络及节点选择足够多的仲裁分片的情况下, Stellar满足安全性, 但恶意节点故意过滤交易时, Stellar活性受到影响.Stellar分为投票、接收和确认这3个阶段, 投票和接收阶段要求同步网络, 确认阶段可以是异步网络, 总体上, Stellar需运行在同步网络中.在节点选择足够多的仲裁分片, 且仲裁分片中声誉或权益高的节点是诚实节点时, 文献[28]证明: Stellar满足安全性, 但恶意节点在Stellar的交易投票阶段故意过滤交易, 会影响交易活性.文献[28]未对Stellar协议的性能表现开展实验. 在纯异步网络及节点总数至少为3f+1时, HoneyBadger满足安全性和活性.HoneyBadger要求节点身份已知且数量固定, 节点间需要两两建立可信通道.在纯异步通信环境下, HoneyBadger保持活性.由于采用拜占庭容错协议, 为抵御f个恶意节点, HoneyBadger需要至少3f+1个节点保证安全性.HoneyBadger可用于广域网中的联盟链系统, 系统可扩展至上百节点数.在跨5个洲的104个节点上运行HoneyBadger协议时, 交易吞吐量达到1 500笔/秒, 延迟不到6min; 在32个节点上运行时, 交易吞吐量最高达到20 000笔/秒, 延迟为30s左右[16].3.2.4 总结 表 8 总结了以上所述确定性共识协议的安全性质.Algorand、Byzcoin和Stellar协议面向非许可链场景, HoneyBadger、Tendermint协议面向网络规模受限的许可链应用场景.Algorand等协议基本都满足安全性和活性, 但Stellar系统在存在恶意节点时, 系统活性会受到破坏.在网络层面上, Algorand和Byzcoin要求弱同步网络, Stellar要求同步网络, HoneyBadger可在纯异步网络中运行.尽管对网络要求低, HoneyBadger只能在节点身份已知且数量不变的非许可链环境中运行, 且要求节点两两建立可信通道, 对节点间通信要求较高.在安全边界上, 大多数确定性共识协议继承了拜占庭协议3f+1的安全边界, Stellar则要求仲裁分片相交.此外, 由于各协议在实验设计方面缺乏统一标准, 包括节点数目、节点硬件配置、区块和交易大小设置等, 以致于文献中各协议的性能表现实验结果难以横向对比. Table 8 Analysis of security properties of deterministic consensus protocols 表 8 确定性共识协议的安全性质分析 4 总结与展望 本文中, 我们将区块链共识协议分为出块节点选举和主链共识两个主要步骤, 通过对每个步骤采用机制进行综合梳理、对比和分析, 发现如下关键问题, 值得广大研究人员关注. ●   在出块节点选举机制, 我们围绕工作量证明和权益证明展开讨论.区块链的出块节点选举机制类似传统分布式协议的领导人选举问题, 与之不同的是: 为抵御开放网络环境中的恶意节点, 出块节点选举机制通常基于“身份定价”机制, 包括工作量证明和权益证明. ➢   工作量证明通过物理资源的投入抵御恶意节点, 存在算力中心化、资源浪费、选举性能低等若干问题.为了解决这些问题, 一些研究工作用内存密集型函数替代计算密集型函数、利用算力提供有用服务、调整工作量证明难题参数等.部分方案改变了系统性质, 从而引出了新的研究问题, 包括改变区块大小、出块间隔、难度调整算法等, 研究人员可针对已有攻击方式在改进系统中的新型攻击手段、安全边界展开研究. ➢   权益证明被用于解决工作量证明的资源浪费问题, 由早期的竞争性难题机制逐渐演变为基于随机函数的非竞争性机制.非竞争性机制由于安全和高效, 是目前权益证明的重点研究方向.权益证明也存在粉碎攻击、无权益攻击和长程攻击等问题, 但目前尚没有对权益证明及其安全问题的综述研究. ●   在主链共识步骤, 根据区块数据的一致性性质, 我们将主链共识分为概率性共识和确定性共识, 并分别展开讨论. ➢   概率性共识从早期基于区块树的选取规则逐渐演变为基于有向无环图的选取规则, 且共识粒度从区块细化为交易, 部分有向无环图协议对交易全局顺序达成概率性共识.当前, 大部分概率性共识通过理论证明满足安全性和活性.然而, 概率性共识之间缺乏对比工作, 目前仅有最长链和GHOST规则的安全性对比分析.在调研过程中我们发现, 最长链规则仍是区块链系统的主导规则, GHOST规则在研究工作中备受关注但目前缺乏实际应用.此外, 几乎所有基于工作量证明的概率性共识都存在自私挖矿问题, 但尚未有研究工作对除最长链规则以外的其他概率性共识度量自私挖矿攻击的影响. ➢   为满足非许可链开放成员及网络规模要求, 大多数确定性共识将出块节点选举机制与拜占庭容错协议相结合, 实现区块链系统的确定一致性.这些协议通常运行于异步网络中, 并要求恶意节点不超过节点总数的1/3.据我们所知, 目前尚没有可运行于大规模纯异步网络中的确定性共识协议.HoneyBadger作为纯异步共识协议, 只适用于节点身份和数量都已知的非许可链系统. 区块链具有去信任、开放自治、匿名可溯源、信息不可篡改等特性, 是构建可信数字经济的重要基础设施.共识协议作为区块链核心技术, 近年来得到广泛关注和大量研究.本文对现有区块链共识协议进行综合梳理, 为研究人员和开发者提供有用参考.