基于信用分级的PBFT共识算法改进方案①

丁庭琛,陈世平

(上海理工大学 光电信息与计算机工程学院,上海 200093)

区块链技术最早出现在比特币中[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=vmod|R|,其中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 一致性协议交互过程

1.2 视图切换协议

视图切换协议是针对主节点发生故障时,维持系统正确运行的协议.1 个视图中有1 个主节点,当主节点发生故障时,视图需要改变,视图编号加1 即v+1,更换新的主节点.主节点发生故障时,从节点触发视图切换协议,系统设置两个触发条件:从最近完成的一个区块的时间戳T开始,在限定时间T1内没有收到新主节点的Pre-prepare 广播,或是在限定时间T2内没有生成新的区块,其中T1＜T2.上述两个触发条件满足其中一个就会触发视图切换协议.为了保证系统的正确性和一致性,视图切换也要进行节点间的交互通信.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 通信的时间复杂度是O (N2),经过三阶段共识之后消息传输次数为2N(N-1).由于通信的复杂性,当节点数超过一定量时,PBFT 协议的性能会急剧下降.最后是PBFT 算法主节点选取随意,选到恶意节点的概率偏高,影响系统效率.

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

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

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

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

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

2.1 信用分级协议

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

图2 节点信用状态分级图

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

表1 节点权限分类

2.2 CLBFT 共识过程

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

图3 CLBFT 流程图

3 性能分析与实验

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

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

其中,transcations为出块时间内系统处理交易数,Δt为出块时间.

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

3.1 算法分析

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

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

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

CLBFT 算法应用节点信用分级协议,恶意节点参与区块共识几率下降,视图切换概率大大降低,所以p1＜p.系数对复杂度为O (N2)通信开销影响很大.

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 和CLBFT 的TPS 随时间比较

图5 PBFT 和CLBFT 随着节点增多通信变化

4 结论

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