硬核干货｜软硬协同的共识算法设计

导 读

我们知道，相比公有链，联盟链中使用的拜占庭容错(BFT)算法能够有效地提升区块链的交易处理能力。但是，传统的BFT算法，例如PBFT[1]算法，为了容忍f个拜占庭错误节点，需要保证系统中的节点总数至少是3f+1。与之相比，RAFT[2]等能容忍f个停机错误(CFT)的共识算法仅需要2f+1个节点就能正常运作。那么我们不禁会去想，能不能通过某种方法使得一个拜占庭系统也只需要总共2f+1个节点就能够抵御拜占庭攻击呢？
幸运的是，这样的方法是存在的。我们可以借助可信硬件，消除拜占庭节点的二义性（equivocation），从而仅需要2f+1个节点，就能有效地防止拜占庭攻击[3]。
本文以FastBFT[4]为例，介绍FastBFT是如何借助可信硬件，取得比传统BFT算法更好的性能的。

可信硬件

FastBFT算法使用的可信硬件是IntelSGX (Software Guard Extensions)[5]，Intel第六代CPU之后的一组扩展指令集。目前，很多个人电脑和服务器都可以支持SGX相关的功能。在SGX的编程模型中，一个程序分为可信代码(enclave)和不可信代码。SGX保证了在enclave中运行的代码和数据不能被其他程序（包括操作系统和虚拟机监视器）访问和篡改。并且，通过enclave写入到磁盘的数据会被加密，只有该enclave能够读取。不可信代码只能调用enclave提供的有限的可信函数接口来改变enclave的内部状态，获取enclave的内部信息。
因此，FastBFT的代码也分为了两部分，如下图所示：

其中，FastBFT不可信代码负责处理共识消息的收发，以及共识状态的转换。而FastBFT enclave代码则负责处理密钥生成，加解密，安全信道的建立以及共识状态变量的维护。

节点类型

与PBFT算法类似，FastBFT算法也有主节点和从节点之分。不同之处在于，FastBFT算法将从节点进一步划分为f个活跃(active)节点和f个被动(passive)节点。在常规流程中，FastBFT算法只需要f+1个活跃节点（包括主节点）参与共识的消息收发。被动节点仅需要处理来自主节点的Reply消息，更新自身的状态。只有在发生错误时，这f个被动节点才需要参与到共识流程中来。
可信变量与函数接口

在FastBFT中，每个节点的enclave都有自己的公私钥对，并记录了其他节点的公钥。除此以外，每个节点还需要维护并持久化以下变量：计数器值c，view值v，活跃节点列表及会话密钥{Si，ki}。其中c和v是共识相关的状态变量，v值只有在viewchange的时候才会增加，当系统平稳运行时，c会不断增加。
FastBFT enclave对外提供了以下几个可信函数接口：be_primary，update_view，preprocessing，request_counter，verify_counter，update_counter和reset_counter。

▲ be_primary、update_view函数

be_primary是某个节点成为主节点之后，需要调用的enclave方法。它的作用是重置c，更新活跃节点列表，重新生成与活跃节点的会话密钥。
update_view是从节点收到主节点当选的消息后，更新自身enclave状态的方法。该方法接受的参数包括主节点的c、v以及加密后的会话密钥。在证实主节点当选的消息是真实可信之后，从节点调用enclave的update_view方法，重置enclave的c和v，获取与主节点通信的会话密钥。
这两个函数都是FastBFT view change流程中需要调用的方法，本文限于篇幅限制不予讨论。

▲ preprocessing、request_counter与verify_counter函数

preprocessing是FastBFT算法为了实现高效的消息聚合，实现节点enclave之间密钥分享(secret sharing)，主节点需要调用的方法。enclave首先通过哈希函数，将c，v与一个随机生成的原始密钥S进行绑定（commitment），这个commitment记作h。然后，通过基于XOR的密钥分享方案，将原始密钥随机拆分成f+1个子密钥Si，S可以通过将这f+1个子密钥进行异或操作还原出来。最后返回给主节点h，c和v，以及经过加密的，只能被对应从节点的enclave解密的。并且，为了避免每次消息聚合之前都进行密钥分享，调用这个方法后会批量生成从c+1一直到c+m这m组消息。之后的m条共识消息都不再需要调用该方法。

request_counter是主节点要发起提案消息前，需要调用的方法。该方法接受一个传入参数x。enclave首先把c+1，然后对进行签名，返回该签名。通过这个签名，可以起到绑定与x的效果。
verify_counter是活跃节点收到来自主节点的PREPARE消息和COMMIT消息后，需要调用的方法。该方法传入的参数包括主节点enclave签名后的,以及主节点enclave的preprocessing方法生成的。从节点的enclave需要确保签名中的c，v与解密获取的c，v一致，并且c比本地的c大1。验证通过后，enclave本地的c+1，返回Si，h。通过这个方法，活跃节点的c与主节点的c进行了同步。返回的Si使得之后主节点能够恢复出原始密钥S，h则能够让活跃节点确认原始密钥S的真实性。
以上这三个函数是FastBFT常规流程中需要调用的函数，对于读者理解FastBFT算法尤其重要。

▲ update_counter与reset_counter函数

update_counter是被动节点收到来自主节点的Reply消息后调用的方法。它作用是更新被动节点enclave的c值。
reset_counter是节点宕机重启后，在重新加入共识网络前，需要调用的方法。它的作用是接收f+1个来自不同节点enclave的一致的c，v，状态消息，同步本地enclave的c和v。

FastBFT算法的常规流程

FastBFT算法的常规流程分为：Preprocessing,Request, Prepare, Commit及Reply这五个阶段。整个流程如下图所示：

在Proprocessing阶段，主节点通过调用enclave的preprocessing方法，获取密钥分享消息。然后将这些密钥分享消息发送给各个活跃节点。
当主节点收到来自客户端的请求REQUEST后，就会进入Request阶段。这时，主节点需要调用enclave的request_counter方法获取enclave对REQUEST，c+1，以及v的签名。然后，将REQUEST及enclave签名一起作为PREPARE消息的内容，发送给活跃节点。
当活跃节点收到来自主节点的PREPARE消息后，就进入了Commit阶段。此时，活跃节点会将主节点enclave的签名以及从Proprocessing阶段获取的对应的密钥分享消息通过verify_counter方法通知enclave。enclave验证通过后，告知活跃节点子密钥Si和h。然后，活跃节点将Si发送回主节点。主节点收齐f+1个来自活跃节点的子密钥Si之后，就可以重建出原始密钥S。之后，主节点就可以执行REQUEST请求，再次调用enclave的request_counter方法，获取enclave对REQUEST执行的结果res，c+1，以及v的签名。然后，将一起作为COMMIT消息的内容，发送给活跃节点。
当活跃节点收到来自主节点的COMMIT消息后，就进入了Reply阶段。此时，活跃节点通过对比的哈希值与之前enclave返回的哈希值h，判断主节点是否成功地恢复出了原始密钥。然后，活跃节点也执行REQUEST请求，判断执行结果是否与主节点执行结果一致。之后，再调用verify_counter方法，获取c+1对应的子密钥Si’以及原始密钥的绑定h’，并将Si’发送回主节点。主节点收齐f+1个来自活跃节点的子密钥Si’之后，就可以重建出原始密钥S’。然后将REQUEST，res，S，S’连同密钥分享信息及之前两个来自enclave的签名都作为REPLY消息的内容，发送给客户端及被动节点。被动节点收到REPLY消息后，首先验证消息的真实性。验证通过后，调用两次enclave的update_counter方法更新enclave内部的c和v值。

FastBFT快在哪里

从上述的流程，我们可以总结出，FastBFT算法的“快”主要体现在以下几个方面：通过可信硬件，减少系统的节点总数；通过轻量级的密钥分享方案实现高效的消息聚合；通过划分活跃节点与被动节点来减少与被动节点的通信。
首先，我们看到，在FastBFT算法中，一共只需要2f+1个节点。更少的节点数量意味着更快的响应时间。在常规流程中，主节点只需要发送f+1条消息，接收f+1条消息就可以进入到下一个阶段。而在PBFT等算法中，节点需要广播3f+1条消息，接收至少2f+1条消息才能进入到下一个阶段。
其次，在PBFT等经典算法中，从节点在收到主节点的PrePrepare等消息后需要向所有节点广播Prepare消息，消息总量为O(n^2)。而FastBFT的常规流程中，所有从节点仅需要发送子密钥给主节点，消息总量为O(n)。这极大地减轻了网络的压力。
并且，在HotStuff[6]等共识算法中，消息聚合是通过基于椭圆曲线的聚合签名来完成的。而基于椭圆曲线的聚合签名速度较慢，影响共识的效率。而FastBFT则使用了基于XOR的密钥分享方案，仅需要进行f次异或操作就完成了消息聚合，极大地提升了共识的效率。值得注意的是，FastBFT能使用如此简单的方法完成消息聚合的原因还是因为可信硬件的支持。由于密钥拆分在enclave内部进行，拜占庭节点无法获知原始密钥和子密钥，也无法进行篡改。这样才能保证消息聚合的安全性。
最后，将节点划分为活跃节点与被动节点之后，被动节点仅需要接收Reply消息更新自身的共识状态，而不需要发送任何消息。这进一步地降低了网络带宽的消耗，降低了系统的运行成本。

总 结

FastBFT作为一种基于软硬协同设计的共识算法，很好地向大家展示了如何使用可信硬件突破传统共识算法理论的限制。我们可以看到，基于可信硬件，FastBFT极大地降低系统的部署成本，显著地提升共识的效率。
大家如果对于本文或者区块链算法感兴趣，欢迎后台交流，或者加入趣链科技技术交流群（可添加小助手桔子微信：18458407117，备注“进群”即可）。

进阶加餐

▲ FastBFT的正确性（safety）

由于完整的FastBFT算法还涉及异常流程view change，已经超出本文的介绍范围，在此仅对FastBFT的安全性做一个简单的论证加餐，以便读者了解大貌。
首先，我们可以发现，每对仅能绑定一条信息。这是因为，每次主节点调用enclave的request_counter方法后，enclave中记录的c就会加1。并且，一旦view change，enclave会将v加1。这样就保证了同一对不会被重用。于是就有效地防止了拜占庭节点向不同节点发送不同的提案消息，消除了拜占庭节点的二义性。
其次，在常规流程中，c每次都会增加1，并且enclave的verify_counter方法也会判断c是否比之前的c大1。这对共识消息的顺序做了进一步的限制。
再次，我们可以看到，在FastBFT中，一个提案达成共识需要经过类似PBFT的两轮广播。与PBFT的区别在于FastBFT的Quorum是f+1而PBFT是2f+1。由于共识消息都有enclave的参与，拜占庭节点无法随意构造虚假的信息，FastBFT的view change流程可以保证即使只有f+1个view change消息，也能够恢复出达成共识的提案请求，确保该请求一定会被执行。
于是，所有正确节点都将以相同顺序执行同样的提案请求。

▲ FastBFT的其他优化

除了前面提到的优化外，FastBFT还引入了广播树来缓解主节点的通信压力。如下图所示：

当1号节点作为主节点要广播PREPARE等消息时，只需把消息发送给2，3号节点。2，3号节点会将消息进一步转发给4，5，6，7号节点。通过这种方法，主节点的发送消息的数量就从O(n)降低到了O(1)。
当然，此时密钥分享、消息聚合等步骤也会有所变化，本文就不在此赘述了，感兴趣的同学可以参考原论文了解相关实现[4]。

作者简介

汪晓可
来自趣链科技基础平台部，区块链软硬件协同设计研究小组

参考文献
[1] Practical Byzantine Fault Tolerance
[2] In Search of an UnderstandableConsensus Algorithm
[3] On the (Limited) Power of Non-Equivocation
[4] Scalable Byzantine Consensus via Hardware-assisted Secret Sharing
[5] Intel SGX Explained.
[6] HotStuff: BFT Consensus with Linearity and Responsiveness