一种基于积分制的改进实用拜占庭容错算法

沈 瑞，李玲娟

(南京邮电大学 计算机学院，江苏 南京 210023)

0 引 言

比特币诞生于2008年，由一个化名为中本聪的学者在论文中首次提出[1]，其背后的区块链技术得到越来越多的重视与发展。区块链是一种计算机技术在价值互联网时代的创新应用模式，是数据库、密码学、网络技术等多种技术整合集成的结果，具有去中心化、去信任化、集体维护、不可篡改等特点[2]。从数据的角度，可以把区块链看成由一个个区块组成，区块记录着经过验证的、区块创建过程中发生的所有交易记录。近年来，区块链技术的价值不断被挖掘，在金融、身份验证、社交通讯等多个领域都有着广泛的应用，并得到了许多国家政府的高度重视。

共识算法是区块链技术的核心，用于解决在去中心化的分布式互连网络中，如何判断区块数据正确性和所有权，以使所有的节点达成共识的问题[3]。由于应用场景的不同，共识算法的侧重点也不同。公有链大部分采用PoW算法[4]、PoS算法[5]、DPoS算法[6]和它们的变形算法，而目前落地的实际应用大多数基于联盟链运行，其采用的共识算法主要是基于消息传递，主流算法有PBFT算法[7]、Paxos算法[8]和Raft算法[9]。

PBFT算法在区块链中得到广泛应用，但也存在一些不足，不能完全适应所有的应用场景。为了解决PBFT算法通信开销大、节点参与共识的积极性不够高等问题，该文提出一种基于积分制的改进的实用拜占庭算法(improved practical Byzantine algorithm based on point system，P-PBFT)。

1 相关知识

1.1 区块链的类型

按照应用场景和设计体系的不同，区块链可分为公有链、联盟链、私有链[10]。

(1)公有链。

公有链所有节点都对外开放，每个人都可以从公有链中读取数据，发送交易。在公有链上，每个节点都可以自由加入或者退出，网络运行时以扁平、无分层的对等网络拓扑结构相互连通，不存在任何中心化的服务节点，是一种完全去中心化的区块链[11]。访问门槛低，数据公开透明且无法篡改、匿名性等是其主要特点，比特币就是公有链的典型代表。

(2)私有链。

私有链是指区块链的开发与维护由一个组织统一管理，各个节点的读取权限与写入权限由该组织决定，不对公共网络开放的区块链[12]。私有链虽然节点权限有所限制，但区块链网络仍然运行在多个节点，其数据的安全性依旧会得到一定的保证。与公有链相比，私有链具有处理交易速度快、交易成本低、隐私保护好等特点。

(3)联盟链。

联盟链是一种介于公有链和私有链之间的区块链，通常应用于不同的企业或组织之间。链上节点都有着相对应的实体，不同的实体组成联盟，节点的加入需要联盟授权，参与者共同维护区块链的运行。联盟链的读取权限对所有节点开放，写入和验证权限则需要联盟内部决定，属于部分去中心化区块链。目前已有很多联盟链，比较知名的有超级账本(hyperledger)项目[13]。

1.2 共识算法

共识算法起源于分布式系统领域，传统共识算法一般面向分布式数据库操作。而在区块链环境下，更多的是面对拜占庭容错问题[14]，传统共识算法不能很好地解决这类问题，因此一系列新的共识算法被提出。常用共识算法如下:

(1)工作量证明(proof of work，PoW)。

PoW的核心思想是通过分布式节点的算力竞争来保证数据的一致性和共识的安全性。而在区块链中，比特币系统则是这一算法的最早实践者，比特币系统的各节点通过计算一个求解复杂但是验证容易的SHA256数学难题来竞争记账权，最快解决该难题的节点将获得下一区块的记账权和系统自动生成的比特币奖励。

PoW算法虽有效地保证了区块链网络的安全性和去中心化性，但其缺点也十分显著。PoW算法需要节点进行大量的计算，但这种计算不具有现实意义，只会带来大量的电力资源消耗，且需要的交易确认时间过长，不适合一般的商业应用。

(2)权益证明(proof of stake，PoS)。

权益证明是为了弥补工作量证明的一些不足而诞生的，在权益证明机制中，记账权的归属不再是算力最高的节点，而是具有最高权益的节点。权益体现在节点对于虚拟货币的所有权，在最早的PoS应用Peercoin中，权益被称为币龄。一个节点的币龄越长，其在区块链系统中的权力越大，挖矿的难度越低，所获得奖励也越多。

与PoW算法相比，PoS算法共识过程主要依靠系统内部的权益，而不需要消耗太多外部算力和资源，因此可以有效地解决PoW中算力浪费的问题，并且能够在一定程度上缩短达成共识的时间，提升系统运行性能。

(3)委任权益证明(delegated proof of stake，DPoS)。

DPoS算法由比特股项目提出，是PoS算法的一种演化版本。DPoS算法采用了类似董事会投票的机制，系统中每个节点都是股东，权益相当于选举票，每个节点都可以把自己的选举票投给信任的代表。最后得票最高的一部分节点成为董事会成员，按照既定的时间表轮流对交易进行打包结算、并且生产新区块。相比于PoS算法，DPoS减少了参与验证区块的节点数量，区块可以得到更快的确认，区块链系统的性能得到了进一步的提升。

(4)实用拜占庭容错(practical Byzantine fault tolerance，PBFT)。

拜占庭容错算法BFT最早由Pease和Lamport在20世纪80年代提出，不同于以上几种共识算法，BFT类协议是依靠节点之间相互传递消息来对提案达成确定性共识结果，因此早期的拜占庭系统需要指数级的操作，所以未能得到实际应用。直到1999年Miguel Castro和 Barbara Liskov提出了PBFT(实用拜占庭容错)算法，解决了原始BFT算法的信息传输复杂度太高的问题，由此实用拜占庭容错算法在实际系统中变得可行[15]。而在区块链环境下，实用拜占庭容错算法多使用于联盟链中。

1.3 P2P网络

区块链与P2P的出发点都是去中心化。

P2P网络即对等网络，是在同等地位的节点之间分配计算任务与网络负载的分布式网络架构[16]。P2P网络模型与客户端/服务器模型不同，P2P网络中没有客户端或服务器的概念，不存在中心节点，只存在对等的同级节点。每个节点既寻求服务，同时也提供服务。P2P网络中的节点没有数量、范围、时间或空间上的限制，每个节点都可以自由地加入或退出P2P网络。

P2P网络具有去中心化、可扩展性、健壮性、高性价比、隐私保护和负载均衡的特点[17]。在P2P网络中，节点不需要服务器即可提供资源和服务，避免了中心服务器的瓶颈，且起到了负载均衡的效果。

从技术上来讲，区块链就是应用P2P的网络架构，通过密码学来保证数据的安全，通过共识算法来保证数据的一致性。P2P一般存在4种网络模型，分别是：集中式、纯分布式、混合式和结构化模型。区块链应用依据自身的实际情况选择不同的P2P网络模型，比特币采用的是混合式网络模型，而以太坊采用的则是结构化网络模型。

1.4 Merkle树

Merkle树属于区块链数据层，是区块链中重要的数据结构，其基本结构如图1所示。

图1 Merkle树

该树的每个叶子节点值是对应数据的哈希值，非叶子节点是它的两个子节点合在一起的哈希值，依次叠加，直到计算出整棵树的根节点，最后生成Merkle根。Merkle根是由所有叶子节点值得到的，因此只要验证Merkle根是否相等，就可以知道叶子节点的数据是否有改动。在分布式系统中，Merkle树可以快速验证在传输过程中数据否发生变化，大大降低了计算复杂度。

1.5 加密技术

加密算法是区块链中不可缺少的一个环节，在区块链中所涉及的加密技术主要包括非对称加密、哈希算法和数字签名。

非对称加密算法是指在对数据进行加密和解密过程中使用不同密钥的一种加密算法。非对称加密过程中使用的密钥成对产生，其中公开的密钥叫公钥，任何人都可以获取，非公开的密钥叫私钥，对外是保密的。公钥与私钥都可以用来加解密，如果用私钥对信息进行加密，只能用公钥解密信息。如果用公钥对信息进行加密，只能用私钥解密信息。与对称加密相比，非对称加密无需交换密钥且算法强度高，所以具有更高的安全性，但是其加解密过程复杂度高且耗费时间较长，一般只适合加密少量数据，适用于数字签名、登录验证等场景。常见的非对称加密算法有ECC(椭圆曲线加密)算法和RSA加密算法等。相比RSA，ECC优势是可以使用更短的密钥来实现与RSA相当或更高的安全性。

哈希函数也称散列函数，是一种单向映射函数。哈希函数将输入数据通过哈希算法生成特定长度的值，该值就称之为哈希值。哈希函数具有单向性、不可逆等特征，逆向求解哈希函数十分困难，几乎不能通过现有的哈希值反推出原文，因此可以有效保证信息的安全性。通过散列算法运算求得的哈希值具有固定长度，且哈希值远远小于输入长度，压缩性保证了任意长度消息压缩映射得到确定长度散列值。哈希函数具有高度灵敏性，如果输入的数据发生字节变化，那通过哈希运算得到的哈希值可能完全不同。哈希函数在区块链中发挥了极其重要的作用，可以进行数据验证、数字签名，保证了区块链系统中数据的安全性和完整性。

数字签名是数字摘要技术和非对称加密技术相结合的应用，为数字信息的完整性和发送者身份的真实性提供了强有力的保障。数字签名的流程是发送方将自己要传输的消息进行哈希，得到摘要，再用私钥将哈希值进行加密，最终得到加密数据。发送方将数字信息原文、加密后的数字摘要和公钥一同发给接收方。同时，接收方会用相同的散列函数生成数字信息的数字摘要。然后接收方使用发送方的公钥对消息和消息摘要进行解密，得到数字摘要。如果发送方的摘要和接收方的摘要相同，则即可证明数字信息的完整性和发送方身份的真实性。如果不同，则说明数字信息已经被篡改。

2 基于积分制的改进实用拜占庭容错算法P-PBFT的设计与分析

2.1 PBFT算法分析

PBFT算法每次共识发生在一个视图(view)中，视图是连续编号的整数，每个视图对应一个主节点，其余都是备份节点。在总节点数为n的系统中，PBFT算法所能容忍的错误节点数f最大为(n-1)/3。

(1)PBFT算法流程。

PBFT算法通过五个阶段达成共识，如图2所示。

图2 PBFT算法共识流程

各阶段的具体流程如下：

请求阶段：客户端节点向主节点发送请求m。

预准备阶段：主节点接收到来自客户端的请求后，给该请求分配一个序列号n，生成一个预准备消息，预准备消息的格式为，这里的v是视图编号，d是客户端发送的请求m的摘要。然后向所有备份节点发送预准备消息。

准备阶段：备份节点接收到主节点的消息并对预准备消息进行验证，如果验证通过，生成准备消息并向其他节点广播，同时将预准备和准备消息写入消息日志，i表示节点编号。

确认阶段：节点收到来自其他备份节点的准备消息，对消息内容进行验证，若验证通过则向所有节点发送确认消息。

回复阶段：当节点完成确认阶段后，向客户端发送回复消息，当客户端接收到f+1个不同的节点发来的相同消息时，回复阶段完成，共识流程结束。

(2)视图切换。

PBFT在视图中执行共识流程时，如果主节点发生宕机或者成为恶意节点，导致共识流程无法进行的时候，系统会运行视图变更协议，根据p=v mod R的规则重新选举主节点，其中v是视图编号，R是节点个数。

(3)PBFT算法的不足。

PBFT算法在节点数量较多的情况下，通信开销很大，无法满足实际系统的需要。另外，主节点选举随意，在实际应用中无法起到激励节点的作用，且增大了主节点的作恶几率，降低了系统运转的可持续性和安全性。

2.2 P-PBFT算法设计思想

针对PBFT算法的不足，结合实际区块链系统的应用情况，该文提出的P-PBFT算法对PBFT做了以下几点改进：

(1)结合DPOS思想，成立节点委员会，委员会里的节点数目根据实际需要设置，只有委员会里的节点才可以参与共识和竞争主节点，其余的节点只进行投票与结果保存，可以降低系统的通信开销，提升系统性能。

(2)引入积分制的概念，给每个节点设置积分，节点的初始积分可根据实际应用的需要来设置。节点使用积分进行投票，选举参与共识流程的节点。当主节点发生错误从而触发视图切换协议的时候，扣除当前主节点的5%积分作为惩罚，然后根据积分的排名顺次选举主节点，这样可以保证主节点的可靠性，提高节点竞争主节点的积极性。

(3)设置积分衰减周期T，按70%的比例减少节点的积分，防止系统过度中心化。

2.3 P-PBFT算法流程

P-PBFT算法流程如图3所示。

图3 P-PBFT算法流程

具体步骤如下：

第一步：客户端发送请求，系统进行响应，如果系统存在主节点，直接进入第二步。系统不存在主节点的时候，所有节点投票选举出委员会节点和主节点。

第二步：委员会里的节点走共识流程，共识成功，主节点增加5积分，委员会节点增加3积分，其余节点增加1积分。如果主节点发生错误从而触发视图切换，则进行第三步。

第三步：扣除当前主节点的5%积分，积分排名第二的节点当选为主节点。

此外，每T个周期后，系统进行积分衰减，每个节点减少70%的积分，并且重新选举委员会成员。

2.4 P-PBFT算法通信开销分析

设定系统的节点个数为N，对于PBFT算法，参与共识的节点个数即为N，三阶段共识的通信开销为2N(N-1)。对于P-PBFT算法，设定委员会节点个数为M，则三阶段共识的通信开销为2M(M-1)，M≤N，且随着M/N的减小，通信开销的降低会更加明显。

3 仿真实验及结果分析

该文基于Go语言实现了一个小型区块链系统，分别运行PBFT算法和P-PBFT算法，(每秒完成的交易数量，单位为个/秒)进行对比，以检验算法的总体效果。

实验环境是：操作系统为Windows10，CPU为Intel (R) Core (TM) i5 - 6300U 2.30 GHz，内存为12 GB。算法实现语言为Go，测试工具为Apache-JMeter。

(1)固定数量节点在不同时刻的吞吐量测试。

测试基于本地10个服务端节点，其中委员会节点数量设置为4个，另开一个客户端节点，负责向服务端发送需要共识的交易。开启Apache-JMeter进行压力测试，配置50个线程，创建Http请求，共识完成则记录一次请求成功，结果如图4所示，横坐标为时间，纵坐标为吞吐量。

图4 固定数量节点在不同时刻的吞吐量对比

可以看出，不同时刻吞吐量略有不同，后续测试将观察平均吞吐量。

(2)不同节点数量下的吞吐量测试。

实验分别开启6节点、8节点、10节点、12节点、14节点、16节点、18节点，作为服务器端，其中P-PBFT算法的委员会节点个数设置为6，另开客户端接口，取平均数据吞吐量，结果如图5所示，其中横坐标为节点数，纵坐标为吞吐量。

图5 不同节点数量下的吞吐量对比

可以看出，在节点数量较少的情况下，P-PBFT算法和PBFT算法的吞吐量相差不大。这是因为节点数量较少的时候，P-PBFT算法参与共识的节点数量和PBFT算法相近，且选举委员会节点也需要消耗一定的资源和时间。

(3)积分变化测试。

对10个节点分别编号为N1～N10，其中N1、N2、N3、N4的积分赋值为10、8、6、4，其余节点的积分赋值为1，N1、N2、N3、N4成为委员会节点，N1节点担任主节点，设置衰减周期为10分钟。经过十轮交易之后，各节点积分如表1所示。

表1 十轮交易前后积分对比

可以看出，随着共识成功的交易量增加，委员会里的节点与其他节点的积分差距扩大，可以提高参与共识的节点的积极性。

当将主节点端口关闭(即模拟主节点发生错误的情况)时，客户端发送请求，会触发视图切换协议，主节点被扣除5%的积分，积分排名第二的N2就成为新的主节点。系统运行十分钟后，所有节点积分全部扣除70%，并重新进行委员会节点选举。

4 结束语

针对实用拜占庭算法PBFT在联盟链节点数较多的情况下性能欠佳的问题，对其加以改进，设计了一种基于积分制的共识算法P-PBFT。结合DPOS思想并引入积分制度，降低了算法通信开销，可以支持更多的节点。改进主节点的选举方式，提高了节点参与共识的积极性；设置积分衰减机制，避免了联盟链中可能出现的过度中心化问题，使得算法更加适应实际的区块链系统。实验与分析表明P-PBFT算法能有效地减少系统通信开销，提高系统吞吐量。