一种面向供应链溯源应用的改进PBFT算法

江雨燕，邵 金，吕 魏

(安徽工业大学管理科学与工程学院,安徽马鞍山243032)

自2008年Satoshi发表《Bitcoin:A peer-to-peer electronic cash system》以来，比特币在全球逐渐发展、稳定运行，其底层技术“区块链”也逐渐引起业界关注。区块链的去中心化特性使数据的验证、记账、存储、维护和传输等过程为分布式系统结构，使用纯数学方法替代中心机构建立分布式节点间的信任关系。区块链类型可分为公有链、私有链和联盟链。公有链服务对象是任何人，并且没有设置访问权限，任何人都可成为节点记账人；私有链与中心化数据库相似，不同点在于系统内部每个节点依然是去中心化的；联盟链一般针对的是特定的组织，节点的数量通常是固定的，接入的管理较为严格。针对供应链溯源应用，最适合的是联盟链。随着供应链上的企业逐渐增多，供应链结构更加复杂。供应链上的信息分布在不同供应链成员手中，信息共享程度较低，信息的真实、可靠性难以保证。王志铧等提出农产品柔性可信溯源系统，利用区块链构建其溯源模型，结合区块链去中心化的特点满足农产品溯源的灵活性需求。针对供应链上下游交易溯源存在的问题，郭珊珊提出区块链上可信溯源解决方案，将区块链分为数据层、存储层、应用层3个层次结构，在底层P2P(peer to peer lending)网络中每个交易角色进行交易，并对区块进行验证；每个节点在存储层存储该链上通过验证的区块信息；在应用层进行交互，实现信息可查询、不可篡改。李明佳等提出基于区块链的食品安全溯源体系，结合区块链隐私保护、分布式容错提供食品运转信息，定位发生问题环节，实现即时溯源，可有效提高食品安全的可靠性。赵公民等提出基于区块链的供应链信任机制，将区块链与供应链硬性、柔性管理机制相融合，助于建立供应链高度的信任氛围。以上文献将各种基于区块链的模型架构应用于区块链溯源，很少考虑到共识算法存在的问题。鉴于此，文中考虑到实用拜占庭容错算法中主节点传递消息可能是恶意传递或是节点故障两种情况，提出基于改进算法的供应链溯源模型，以更好契合实际应用，提高共识效率。

1 PBFT算法及改进

1.1 PBFT算法

图1 一致性协议执行过程Fig.1 Conformance agreement execution process

实用拜占庭容错(practical Byzantine fault tolerance,PBFT)共识算法是一种基于状态机副本复制的分布式一致性算法。要求各节点发送消息时均需签名，其他节点无法修改别的节点消息，在收到客户端请求后，只有经过全网广播完成上一个请求，才会发送下一个请求执行，这与供应链溯源应用相契合。PBFT算法由一致性协议、视图切换协议、检查点协议组成。其中一致性协议提出若总节点数为N，拜占庭节点数目为f（可以容忍的最大数目），正常节点至少为f+1个，即N ≥3f+1,因此在PBFT算法中拜占庭节点的数量f ≤(N-1)/3。该算法的一致性协议中提出了3 个阶段：预准备阶段、准备阶段、确认阶段，执行过程如图1。

图中“Client”为客户端，“Primary”为主节点，“Replica1”和“Replica2”为从节点，“Replica3”为故障节点。“Request”为从客户端发出的请求。

1)预准备阶段(Pre-prepare) 主节点收到客户端请求后，生成并向所有广播节点发送一个预准备消息，消息格式为＜＜Pre,V,n,d＞,M＞，V 为视图编号，d 为计算出的相应哈希值，n 为消息编号，M 为客户端消息。

2)准备阶段(Prepare) 节点i 收到预准备消息生成准备消息，将预准备消息和准备消息写入日志，将准备消息广播至所有备份节点，消息格式为＜Prepare,V,n,d,i＞，其中i 为节点编号，若有f+1 个节点确认该消息真实，达成共识，则进入确认阶段。

3)确认阶段(Commit) 节点i 确认收到消息后，会向其他备份节点广播该消息，消息格式为＜Commit,V,n,i＞，各节点对收到的消息进行验证，验证成功后,(2n+1/3)个节点会发回相同结果，则该请求完成待执行。

PBFT算法要求总节点数为N ≥3f+1(其中f为拜占庭节点)，一致性协议中的预准备和准备阶段都是副本节点接收主节点发送的序列，让所有共识节点认可这个序列后方可按照序列执行，若副本节点检查消息时发现主节点为拜占庭节点，则会发起视图切换协议，当2f+1 个节点确认视图切换，则选举出新的主节点p=v+1 mod|R|。

PBFT算法是联盟链常用的算法，对区块链共识过程的改善很大，但往往按照编号顺序依次选取主节点，主节点为恶意节点的可能性不确定，且当节点数越多，节点之间的共识效率越低，造成较高的通讯开销。若连续选取的主节点为恶意节点，不停地触发视图切换协议，则会造成极大的系统资源消耗，降低系统安全性。

1.2 改进的PBFT算法

供应链成员中企业出现恶意动机的情况不多见，但不排除网络波动导致无法通信等情况，主节点一般会出现两种错误情况：主节点因故障未发生响应；主节点是拜占庭节点，恶意篡改客户端发送的消息。针对实际应用中主节点会发生变化，提出一种基于PBFT改进的算法—动态实用拜占庭容错算法(dynamic practical Byzantine fault tolerance,DPBFT)。DPBFT算法设置计分机制，每个节点初始分数为0分，第一种未响应的主节点扣5分，第二种作恶的主节点扣10分。若节点诚实，成功完成共识过程则为节点加1分。当所有节点分数相同，随机抽取一个作为主节点；当分数不同，选取分数最高的作为主节点，DPBFT算法流程如图2。

图2 DPBFT算法流程Fig.2 Process of DPBFT algorithm

假设在共识机制中有4个节点，分别为n,n,n,n。其中n,n,n为诚实节点，n为拜占庭节点，交易向量为 S，则n发送给n的交易向量为S，n发送给n的交易向量为S，则G 需要满足以下条件：

G(S)=false 表示通过与其他节点发送的消息核对后，从x 节点发送到y 节点的消息是异常的，两者存在一个拜占庭节点。为降低主节点是拜占庭节点的概率，文中采用计分制定期投票选取主节点的策略，主要步骤如下：

1)网络上的所有副本节点参与投票，选出一个主节点。每个节点的初始分数为0分，每个节点被选为主节点的概率相等，投票决定主节点。后续选择主节点优先从分数最高的节点中抽取。

2)客户端发送请求后，分为3类情况：主节点发送错误消息、主节点无响应、主节点诚实。若主节点无响应，则对该节点扣5分并触发视图切换协议，视图切换消息格式为＜Viewchange,n,C,P,i＞；若主节点发送错误消息，即收到请求后，主节点在全网络进行广播，广播消息的格式为＜＜Pre,V,n,d＞,M＞，恶意分配错误序号，其他从节点无法验证通过，则对该节点扣10分，并进入视图切换协议，发送视图切换消息；若主节点为诚实节点，并成功完成一次共识过程，则为共识过程各节点加1分，将各节点确认的消息验证、记录并写入区块。

3)为防止诚实共识节点在系统正常运行后发生改变或宕机，按照步骤1)的方式重新选取新的主节点，每次根据实时节点分数选取，以降低作恶节点成为主节点的概率。

2 基于DPBFT算法的供应链溯源模型

区块链的基础架构模型包含数据层、网络层、共识层、激励层、合约层和应用层。数据层封装数据区块，并包含链式结构、时间戳、哈希函数等；网络层包括P2P网络、数据传播机制等；共识层包括工作量证明机制、权益证明机制、股份授权证明机制和实用拜占庭容错法等各类共识算法；激励层通过经济因素奖励区块链上率先完成算法工作的节点。合约层封装各类算法与脚本，是区块链的核心，使区块链具可编程性。

针对供应链溯源应用，文中将模型架构分为数据层、合约层、应用层，具体如图3。相对于公有链，联盟链的控制权更易设定，扩展性较好，联盟成员共同维护供应链链上的信息安全，影响到每一成员的自身利益。因此在设计架构时不涉及激励层，同时将共识层中共识算法融合到数据层，与合约层对接。

图3 供应链溯源模型架构Fig.3 Supply chain traceability model architecture

1)数据层 主要定义数据结构和存储数据，节点与节点之间通过哈希函数所求的结果，将某特定时间内收到的交易记录封装在一个带有时间戳的数据区块中，这些交易记录通过Merkle树的哈希过程生成Merkle根存储在区块头，区块头包含哈希值、时间戳、Merkle树根和区块高度等数据。共识过程的核心是选主和记账两部分，从输入数据节点之间的交易数据到封装好的数据区块，分为选主、造块、验证、记账4个阶段，每执行一轮便生成一个新的区块，区块结构如图4。其中：Nonce为随机数；TX为Transaction交易名，HASH为每笔交易特有的哈希值，HASH12为交易1，2的哈希值；HASH3，HASH4为串联两个交易记录之间的哈希值。数据层中的链式结构从创世块到新增区块形成的一条最长主链，记录链上的历史数据，决定其可溯源的特性。

图4 区块结构Fig.4 Block structure

2)合约层 封装算法、脚本以及智能合约，是实现操作数据的关键。供应链的参与成员共同制定合约内容，并使用脚本代码嵌入系统，一旦满足合约条件即自动执行，外界无法参与其中，也可有效避免各成员出现拖欠付款的情况，实现合约执行的智能化。共识算法是保证区块链网络不被恶意节点攻击、篡改数据的核心，在合约层封装执行改进的DPBFT算法，可减少节点与节点之间的通信以及主节点出现问题时交易的延迟。数据层将数据记录在区块后，通过合约层DPBFT算法验证，若各节点验证正确并将消息返回到客户端，表示新的交易被确认，则增加链的长度，不可对前面的数据进行修改，保证数据的完成性。

3)应用层 用户与应用程序的交互层，区块链网络在合约层实现读写接口以供调用，生产商、供应商、分销商、零售商等通过搭建的区块链网络进行存储交易信息并记录，作为消费者，通过扫描产品的二维码，获取产品的从生产商到零售商的完整流通信息；作为生产商、供应商等供应链上游成员，注册身份信息申请成为区块链网络中的节点，与区块链网络保持同步。在生产、加工、包装、配送、分销、零售产品的同时，将相关流转的数据添加进区块中，写入区块链。由于区块链本身的不可篡改性和加密技术，可保证产品流转过程信息的可追溯性和真实性。

以食品溯源为例，将其供应链分为生产环节、加工环节、流通环节、销售环节、市场监管等步骤。

1)生产环节 从生产过程开始记录产品的品种、数量、生长条件、发货日期等，于特定时间将该批次的产品信息录入本地生产数据库同时生成加工批次码，将信息上链。

2)加工环节 记录产品收货时间、产品种类名、加工时间、加工温度、发货数量、发货时间等，根据产品的加工批次码进行加工，加工结束后将批次码、加工时间、发货人、发货时间写入区块链系统。

3)流通环节 记录收货数量、收货人姓名、收货日期并通过温度传感器记录流通过程中的产品温度，生成运输批次码。尤其在全球疫情期间，要加入进口冷冻食品核酸检测信号，一旦发现冷冻食品出现问题及时迅速上报，将更新的运输产品数量写入区块链系统。

4)销售环节 食品通过物流运输到达经销商后，经销商记录收货时间、入库时间、出库时间、销售地点，上传到区块链系统。通过网络、店面等方式销售到消费者手中，消费者扫描二维码可获得产品的所有流通信息，从生产环节的加工批次码到销售环节的运输批次码，可清晰准确了解产品来源。

5)市场监管 食品监管部门在检查食品安全时扫描二维码查看相关数据是否符合产品本身信息，完成对整个食品供应链全生命周期的监控，实现对整个溯源流程把控。

3 实验与结果分析

实验测试设备为AMD Ryzen 2600X 处理器、16 GB 内存的Windows 10 系统的PC 机，开发环境为JetBrains GoLand 2019.2.3 x64，通过GO程序语言实现DPBFT算法。通信开销和交易延迟是体现算法效率、衡量共识算法的重要指标，通信开销指网络节点在共识过程产生的通信量，交易延迟指从客户端发送交易请求到客户端确认收到共识消息的过程中交易时长。为验证DPBFT算法的有效性，文中选取DPBFT及PBFT两种算法的通信开销和交易延迟指标进行比较分析。

PBFT算法的通信时间复杂度为O(N)，假设整个网络节点数为n，则完成一次一致性协议的通信次数为2n(n-1)。节点数较大时，通信量较大，造成共识效率低下。当主节点为恶意节点或未响应，会进行视图切换协议，向各副本节点广播视图变更消息，其通信次数为n(n-1)。假设PBFT算法执行视图切换协议的概率为p，则发生视图切换后的通信次数T 为

DPBFT 算法通过计分制降低主节点为恶意节点的概率，节点数增加时，减少恶意节点参与共识过程。将完成一次过程后的计分情况全网广播，通信次数为(n-1)。假设DPBFT算法执行视图切换协议的概率为q，且q ＜p，则在DPBFT算法中发生视图切换的通信次数L 为

DPBFT算法的通信复杂度也是O(N)，通过计分制使投票选出的主节点作恶或无响应的概率大大降低，即第二项系数q 小于p。发生视图变更概率变小，在节点数增多的情况下，系数对通信复杂度的影响更大。两种算法通信开销比M=T/L，计算式如式(5)。

DPBFT算法面对主节点不同情况时有不同程度的扣分机制，在一轮共识过程结束选取新的主节点时提升主节点诚实的概率，触发视图切换协议的频率降低。q 值越小，M 值越大，网络中节点数不断增长时，DPBFT 通信开销相较PBFT 算法越来越小，当p =0.324，q=0.215时，两种算法的通信开销比M 如图5。

分别以4，8，12，16个节点为例，为不失一般性，取50次实验的平均值。两种算法的通信开销和交易延迟结果如图6，7。

图5 两种算法的通信开销比Fig.5 Communication cost ratio of the two algorithms

图6 两种算法的通信开销Fig.6 Communication volume of the two algorithms

图7 两种算法的交易延迟Fig.7 Transaction delay of the two algorithms

由图6可看出：节点为4个时，DPBFT算法与PBFT算法的通信开销差距不大，DPBFT算法完成一次共识过程的通信开销平均为41 次，PBFT 算法平均56 次；当节点增加到16 个时，DPBFT 算法通信开销平均422次，PBFT算法通信开销平均366次，通信开销显著降低。

由图7可看出，PBFT算法的延迟较高，DPBFT在降低主节点为拜占庭节点的概率后，其交易延迟有所降低，节点为16个时，PBFT算法的平均交易延迟109 ms，DPBFT算法的平均交易延迟99 ms。

4 结 论

针对供应链溯源模型中PBFT算法存在通信开销大、系统消耗高的问题，提出一种改进的PBFT算法—DPBFT算法。设置计分机制，根据计分情况选取主节点，降低主节点为拜占庭节点的概率，优化共识过程；针对供应链溯源特点，利用区块链技术设计三层供应链溯源模型架构，将DPBFT算法融合于模型合约层，解决传统溯源系统存在的数据不安全、易被篡改等弊端。实验结果表明：节点数较少时，DPBFT与PBFT算法的通信开销相似，但DPBFT算法的交易延迟有所降低；节点数增多时，DPBFT算法可减少通信开销与在网络交易过程中的交易延迟，提升共识效率，加快系统运转速度。