区块链技术最早出现在比特币中^[1], 作为已知的分布式账本, 在过去几年中引起各界广泛的研究. Blockchain是一种点对点分布式系统, 具有高安全性和分散存储, 高容错和加密性等特性. 为了解决现有中心化机构效率低、成本高、数字资源垄断等问题, 区块链整合密码学、计算机和通信等领域等技术, 所用技术有非对称加密、时间戳、共识机制和点对点通信^[2], 实现中心化分布式系统. 区块链技术被认为是引起人类社会颠覆性变革的关键技术之一^[3].

公有链和联盟链是区块链的两种主要形式^[4]. 比特币是区块链最早的应用, 也是公共区块链最著名的例子. 比特币作为最早的数字货币, 仅使用单一的去中心化技术, 存在很大功能局限性. 随着智能合约^[5]的发展, 公有链有了更加智能的应用平台. 例如以太坊(etherum)平台就是一个可编程的区块链平台^[6], 在系统资产自动化管理方面有显著进步. 公有区块链是完全去中心化系统, 没有管理和监督, 任何人都可以参与公有链并且访问数据. 因此, 公有链存在一定的弊端, 隐私和安全性难以得到保障, 可靠性差^[7]. 为了更好地保护用户的隐私和监督数据, 提出了联盟链概念, 其中, Hyperledger是经典的联盟链系统^[8]. 联盟链在企业级组织内部广泛发展^[9]. 在联盟区块链中, 只有特定允许的节点才能访问网络. 因此, 联盟区块链可以很好地支持企业级应用程序, 并在公共和政府服务中被广泛采用.

共识机制是区块链的核心, 区块链中有PoW和PoS算法^[10], Raft算法^[11], PBFT算法^[12]等共识机制. 一般情况下存在拜占庭问题都由PBFT算法解决. 拜占庭式故障模型^[13]假设副本可以通过任意行动而被恶意攻击^[14], 该模型适用于区块链系统. 针对模型中的共识问题, 许多理论成果相继出现, 不过较早的协议都是从理论上解决问题, 无法在实际场景中应用. PBFT是第一个为实际应用开发的协议, 解决了分布式文件系统可容忍拜占庭式故障问题. 不过PBFT无法在实际场景中广泛应用, 它存在扩展性差, 通信开销大, 效率低等问题^[15].

针对联盟链的应用场景, 本文提出了一种基于PBFT改进的一致性算法, 称为CLBFT (Credit- Layered Byzantine Fault Tolerance). 受PoW共识机制的启发, 基于信用奖励和惩罚节点, 基于节点信用值的基础上给节点分级, 旨在长期维持系统良好运行. 通过这种方案, 可以大大提高参与者的积极性, 减少恶意节点参与带来的影响, 提高系统的安全性和效率.

1 PBFT

Castro和Liskov在1999年提出的实用的拜占庭容错协议(PBFT)被认为是解决拜占庭将军问题的最经典协议. PBFT是为解决分布式系统中存在拜占庭故障节点从而达成信息一致性的问题. 为保障系统正常运转, 当系统中无效或者恶意点数为f时, 要求总节点n不小于3f+1. PBFT算法主要包括一致性协议, 视图切换协议和检查点协议3个部分.

1.1 一致性协议

一致性协议是PBFT算法的核心, 主要作用是保证区块链系统中信息的正确和相同. 在PBFT算法中存在客户端(client), 主节点(primary), 从节点(replica)3种角色. 客户端c主要作用是向主节点发送请求<REQUEST,o, t, c>,o为请求的具体操作, t为时间戳. 主节点通过视图编号以及节点数集合来确定, 主节点公式如下: ${{p}} = vod \left| R \right|$ , 其中v是视图编号, |R|是节点个数, p是主节点编号. 主节点和从节点作为副本节点参与算法的主要3个通信阶段: 预准备阶段(pre-prepare)、准备阶段(prepare)、确认阶段(commit).

1)预准备阶段: 主节点接受到客户端c的请求, 丢弃错误请求, 对正确的请求进行排序, 并分配编号n. 然后主节点向系统中的其他从节点广播一条<<PRE-PERPARE,v, n, d>,m>消息.

2)准备阶段: 节点对收到的预准备消息进行判断, 如果同意预准备消息, 则进入准备阶段, 然后向其他节点(包括主节点)广播<PREPARE,v, n, d, i>消息.

3)确认阶段: 当节点收到2f+1个通过验证的消息时准备阶段结束进入确认阶段, 节点向包括主节点在内的其他节点发送<COMMIT,v, n, D(m), i>消息.

图1是一次一致性协议过程. “Client”是客户端, “Primary”是主节点, “Replical1”、“Replical2”、“Replical3”是3个从节点. 即使“Replical3”是故障节点, 系统任可以通过一致性协议.

1.2 视图切换协议

视图切换协议是针对主节点发生故障时, 维持系统正确运行的协议. 1个视图中有1个主节点, 当主节点发生故障时, 视图需要改变, 视图编号加1即v+1, 更换新的主节点. 主节点发生故障时, 从节点触发视图切换协议, 系统设置两个触发条件: 从最近完成的一个区块的时间戳T开始, 在限定时间T₁内没有收到新主节点的Pre-prepare广播, 或是在限定时间T₂内没有生成新的区块, 其中T₁<T₂. 上述两个触发条件满足其中一个就会触发视图切换协议. 为了保证系统的正确性和一致性, 视图切换也要进行节点间的交互通信. View-Change的工作过程如下:

1) 视图切换协议开启后, 从节点进入视图v+1, 并向所有节点广播View-Change消息.

2) 副本节点在收到2f+1条(包括自身)View-Change消息后, 向视图v+1中的主节点发送View-Change-Ack 消息, 新主节点收到View-Change-Ack消息后进入New-View阶段.

3) 新的主节点选择检查点作为“New-View”请求的起始状态, 然后根据本地块链接数据执行一致性协议.

1.3 检查点协议

在共识过程中, 节点会生成大量的日志, 系统长期运行下就会存储大量信息. 检查点协议的作用就是减小节点信息存储规模, 释放经过共识认证的日志消息, 降低系统内存开销. 某些节点由于自身故障或网络问题没有和其他节点同步, 影响系统的运行, 因此需要Checkpoint协议周期性工作, 它在确认节点的一致性后清除经过验证的证书.

1.4 PBFT存在的问题

虽然PBFT算法对区块链的共识性能改善很大, 但是任然存在通信开销大, 扩展性差, 效率低等问题. 首先PBFT算法是一种部分同步模式共识算法, 为了保证非故障节点以相同顺序执行客户端的请求, 需要三阶广播通信实现异步模式下的安全性, 造成大量的通信开销. 其次, PBFT算法需要点对点通信进行拜占庭容错共识. 在N个节点的网络中, PBFT通信的时间复杂度是 ${\rm O}\left( {{N^2}} \right)$ , 经过三阶段共识之后消息传输次数为 $ 2N(N-1)$ . 由于通信的复杂性, 当节点数超过一定量时, PBFT协议的性能会急剧下降. 最后是PBFT算法主节点选取随意, 选到恶意节点的概率偏高, 影响系统效率.

2 基于分级的高效共识机制

PBFT算法中选取主节点随意. 它是根据编号的顺序依次得到主节点, 并且选出的主节点没有任何检验, 无法保证系统的安全性. 用这种方法选举出来的主节点存在恶意节点的可能性很大, 从识破恶意节点到通过视图切换协议更换主节点, 造成大量网络通信开销, 降低了系统效率. 本文采用信用评估和节点分级协议对PBFT算法加以改进, 提出了CLBFT共识机制. CLBFT主要改进的地方有:

1)制定信用积分规则, 评估节点信用状态.

2)依据信用积分对节点进行分级, 选择积极节点参与一致性协议, 提高节点动态性.

3)在可信节点层选择主节点, 大大减少恶意节点对系统运行的破坏, 减少通信开销, 提高系统效率.

2.1 信用分级协议

定义C_i代表节点的信用积分, 节点的信用级别划分为4个级别: A、B、C、D. 刚加入的节点的信用值为C_normal, 根据节点在系统中的行为增加信用积分或减少信用积分. 节点在系统中参与一次有效区块的生成则节点信用积分加1; 节点在系统中未生成有效区块则信用积分减5. 信用值在C_normal≤C_i<C_good区间的节点信用级别为B, 初入节点也在此列; 当节点的信用值大于C_good时, 即C_i>C_good, 节点信用级别为A; 信用值为C_bad≤C_i<C_normal时, 节点信用级别为C; 当节点的信用值低于C_bad时, 即C_i<C_bad节点的信用级别为D. 节点信用分级转换如图2所示.

依据信用分级协议将节点划分为四类, 每类节点有不同的权限. A类节点信用级别最高, 优先担任主节点. 其次是B类节点, 当A类节点被选择完毕或不存在A类节点, 可以从B类节点中选择主节点. C类节点由于信用级别偏低不适合担任主节点, 但任然可以作为从节点参与区块共识. D类节点信用级别太低, 不能参与共识. 权限分类不仅能够大大提高节点的积极性, 而且有效预防恶意节点成为主节点. 有效地减少恶意节点参与共识带来的通信损失和减少View-Change变更次数, 提高系统效率, 如表1区分节点权限.

2.2 CLBFT共识过程

CLBFT算法的过程如图3所示. 首先, 根据信用分级协议对节点进行分级. 信用分级协议的周期为zCT, 其中CT是检查点协议的周期,z为系数. 依据系统中节点数量调整合适的系数z按照周期间隔zCT更新节点信用积分, 节点依据信用积分分成不同级别. 然后, 不同级别的节点有不同的权限, 有相应权限的节点参与选出主节点. 节点根据自身的行为获得相应的信用积分, 当节点积分满足A类信用级别时, 进入集合A. 集合A中的节点获得视图编号, 参与主节点选择, 保证主节点选取的最优性. 接下来, 主节点选出后参与一致性协议, 并监督一致性协议以判断主节点是否触发View-Change中设置的两个超时触发条件. 若超时, 触发视图切换协议, 更换主节点, 视图v+1, 否则生成新区块写入区块链. 最后执行改进的检查点协议(Checkpoint)释放经过共识认证的日志消息, 降低系统内存开销.

3 性能分析与实验

PBFT算法的主节点选取较为随意, 是根据编号的顺序依次得到主节点. 用这种方法选举出来的主节点存在恶意节点的可能性很大, 视图切换协议较多会造成大量网络通信开销, 降低了系统效率. 本文提出的CLBFT算法是对PBFT算法的改进. 制定信用积分规则, 评估节点信用状态. 依据信用积分对节点进行分级, 积极节点参与一致性协议, 消极节点权限受限, 提高节点动态性. 在可信节点层选择主节点, 减少恶意节点对系统运行的破坏, 减少通信开销, 提高系统效率.

吞吐量一般指单位时间内系统处理的事务数, 吞吐量的高低显示了系统承受负载, 处理事务或者请求交易的能力. 在区块链领域中, 一般用每秒交易数TPS(Transaction PerSecond)来表示, 即:

$ TPS = transcations/\Delta {{t}} $

(1)

其中, transcations为出块时间内系统处理交易数, $\Delta {{t}}$ 为出块时间.

系统硬件配置为: Inter Core i5-7300 CPU, 8GB内存. Linux系统是Ubuntu16.04, 根据Hyperledger Fabric V1.1的环境建立仿真平台. 采用多节点运行分布式共识过程.

3.1 算法分析

假设系统的节点总数为n, 系统发生视图切换协议的概率为p(p是平均发生视图切换协议次数占总共识次数的占比), w用于统计通信次数.

PBFT一致性协议经过三阶段广播, 通信的时间复杂度是 ${\rm O}\left( {{N^2}} \right)$ , 通信次数为 $ 2n(n-1)$ . 视图切换协议的通信次数为 $ n(n-1)$ . 所以PBFT在p概率下发生视图切换协议后的总通信次数可以计算 $ 2n(n-1)+pn(n-1)$ , 即:

$w = \left( {p + 2} \right)n\left( {n - 1} \right)$

(2)

CLBFT使用信用分级协议有效地预防错误节点成为主节点, 并降低错误节点参与共识的概率. CLBFT算法发生视图切换的概率为p₁, p₁<p. 信用分级协议周期性触发, 系统通过一个周期中各个节点所得信用积分给节点分不同等级, 然后通过副本节点广播给其他节点, 所用通信次数为: (n–1). 所以CLPBFT算法在p₁概率下发生视图切换协议总通信次数为: $ 2n(n-1)+ p_1n(n-1)+(n-1)$ , 所以:

$ {{w = }}\left( {{{{p}}_{{1}}}{{ + 2}}} \right){{n(n - 1) + (n - 1)}} $

(3)

CLBFT算法应用节点信用分级协议, 恶意节点参与区块共识几率下降, 视图切换概率大大降低, 所以p₁<p. 系数对复杂度为 ${\rm O}\left( {{N^2}} \right)$ 通信开销影响很大.

3.2 吞吐量测试

图4所示, 纵坐标为系统吞吐量, 横坐标为系统运行时间. 系统设置100个节点, 错误节点随机变化但不超过33个, 满足总节点n不少于3f+1, f为恶意节点, 比较PBFT和CLBFT的吞吐量随时间变化. 在容错范围内, PBFT的效率在整个模拟过程中是稳定的. 随着系统长期运行, 基于信用分级的CLBFT算法有效地提高系统的吐吞量. 由于恶意节点参与共识概率大大降低, 主节点错误率下降, 视图切换协议的概率随之下降, 系统稳定性和效率得到提升.

3.3 通信开销验证

在图5中, 纵坐标为区块平均生成一次的通信次数, 横坐标为系统中的节点数, 节点数分别取20,40,60,80,100比较PBFT和CLBFT随着节点增多通信变化. 随着系统内节点的增加, CLBFT通信开销比PBFT越来越小, 如图5所示.

4 结论

近年来, 区块链在多个领域日益流行. 作为区块链的两种主要形式, 公有链和联盟链在不同应用领域研究各自核心共识机制. 针对联盟应用场景, 现有实用拜占庭容错算法(PBFT)存在视图变更频繁, 系统通信开销过大, 大量节点加入后系统效率低下等问题. 本文提出了一种基于PBFT改进的CLBFT算法, 设置节点基于信用分级的方法, 依据节点在系统中的表现赋予节点不同的权限. 降低恶意节点参与共识的概率, 从而有效避免频繁的视图变更带来的通信资源浪费. 仿真结果表明, 在系统长期运行下, CLBFT降低了系统通信开销, 提高了系统效率.