张迪 燕山大学理学院

一、绪论

以区块链为核心的分布式系统近年来受到了广泛的关注。中本聪是比特币的开发者兼创始者，他提出的区块链结构是在没有中央权威的情况下对交易进行时间戳的方式[1]。中本聪共识能够使网络参与者在不受信任或半可信的环境中操作，并且可以在网络参与者之间存在拜占庭式故障的情况下进行操作[2]。由于需要保证交易的终结性以及计算效率，研究人员重点关注在不超过f 个故障节点的假设下，以确定性方式运行的拜占庭容错共识算法[3，4]。

本文提出的另一种拜占庭容错(Byzan tine Fault Tolerant，BFT)共识算法具有模块化结构，并且可以很简单的实现，主要应用于超级账本区块链平台中，优点是既可以实现交易的低延迟，又实现了相当高的交易吞吐量。

二、另一种BFT 共识算法

另一种BFT 共识算法中的典型参与者：

客户端：每个在区块链系统中注册了公钥的用户即为客户端，作用是生成交易并将交易发送到排序服务。

节点：即网络参与者，负责对提案中的交易进行验证以达成共识，并将共识后的交易存储到块中，节点可以维护完整的交易历史记录，以验证提案。诚实节点是尝试与网络同步、创建有效选票、提交，并且从不创建分叉块的节点。

排序服务：负责获取交易集和创建块提案的功能模块，提案中包括一组要由节点验证和表决的交易。

为了简化一般流水线，本文做出以下假设：首先，假设客户端是由节点知道的，且客户端有一个已知节点的列表来进行交互；其次，客户端有自己的秘钥安全地存储在设备上；最后，客户端有权在区块链上执行特定的命令子集或智能合约。区块链系统中的另一种BFT 共识算法的一个回合可描述为以下5 个步骤：

·客户端使用命令形成交易，并使用其私钥对交易签名；

·客户端将交易发送给节点。节点接收交易，执行无状态验证，即验证格式是否错误，并将其转接到操作系统中；

·操作系统生成一个包含有序交易列表的提案并将其发送给节点；

·提案已被送交给有表决权的节点，节点进入协作阶段，本阶段中节点通过网络交换选票并决定块；

·节点将该块提交到其本地存储中。

·操作系统收集交易以便将其包含到新的提案中，提案是在操作系统中收集了一定数量的交易之后或在一个时间限制之后生成的，然后操作系统在提案创建后向所有节点广播该提案。

三、协作阶段

节点在收到来自排序服务的提案后计算经验证的提案。节点生成的块由提案的哈希值、验证提案的交易和链加密验证所需的附加元数据组成。不同的节点可以从同一个提案中计算不同的块，一条投票消息包含一对哈希值和一个签名，当从网络中接收到消息时，签名用于节点进行身份验证。

当节点对块哈希进行投票时，它会将当前一轮验证节点生成一个顺序，该顺序是在网络中传播投票所需的节点的排序。该顺序由一个函数生成，该函数将块哈希和初始节点列表作为参数，返回均匀分布的列表。

四、激励实例

本节描述了A、B、C、D 四个节点进行的一轮另一种BFT 共识算法的执行步骤。每个客户端将自己的交易发送到排序服务，排序服务的责任是收集所有交易、排序交易以及创建块提案P1，然后与网络中的每个节点共享提案P1。

A 的验证过程：A 是P1的验证者，如果交易根据验证规则不存在错误，则该交易是有效的，A 将所有的有效交易创建一个块，并计算块的哈希值H1。A 在得知提案哈希值H1和节点的初始顺序(A，B，C，D)后，使用哈希值H1作为排序函数的输入，计算得出当前一回合的排序，结果为(C，D，A，B)。于是，A 创建了一张选票并将选票传递给本回合排列名单上的第一个节点C。A 将其本地状态切换为等待提交消息，直到某个时间延迟。

C 的状态：C 接受了A 的投票。假设C 从P1的验证过程中计算出相同的哈希值H1，进而使用排序函数计算出相同的顺序，则C 将投票传递给自己，此时，C 现在有两票，A 的和C 的，但B 和D 还没有投票。

D 分享投票：D 同样计算出哈希值H1，并将他的选票传递给C，现在C 拥有的票数大于此刻网络中所有节点的三分之二。C 将来自节点的所有选票广播提交消息。除了B 之后，每个节点都接收到一条提交消息，并使用哈希值H1向块添加签名，并更新本地状态。

B 的状态：假设B 的网络存在问题，错过了之前回合，包括C 的提交信息。B没有将哈希值H1的投票传播给C，因此他的状态不一致，B 计算出哈希值H1，得到不同的节点顺序(A，B，D，C)，B 将他的选票传播给A，此时A 已经收到C 的提交信息，他将C 的提交信息转发给B，B 验证来自A 的提交信息并应用。在达成共识之后，B 拥有与其他人相同的状态。

五、结论

本文提出的另一种BFT 共识算法通过对块提案的投票，在网络中至少3f+1个节点中存在不超过f 个故障节点的假设下，保证了交易处理的安全性和活性，同时对算法在不同情况下的执行步骤进行了全面的描述。