许可链的性能优化

原文链接：https://mp.weixin.qq.com/s/nr7nNMaDZ7b1PP25glrWWA
区块链，或广义地称为分布式账本技术（DLT），无疑是2016年度的全球热词之一，几乎每天都有这样的新闻传来：世界上的某处又有某家知名机构宣布和某家初创公司开展合作，尝试使用区块链或分布式账本技术解决某个问题。除此之外，各大咨询公司、各类行业组织及监管机构也纷纷发布报告，研讨区块链将如何颠覆我们熟知的世界。
但是，在区块链晴朗的天空的远处，还有两朵小小的令人不安的乌云：其一是区块链的隐私保护，其二是区块链的性能问题。对于前者，业界已有同态加密、零知识证明、伪匿名等多种对策，只是未臻完美，本文也不准备展开阐述。对于后者，其难度相当程度与区块链的类型相关：就当下常见的非许可链及许可链二分法而言，由于共识节点之多寡不同，基础设施之良莠不齐，成员身份之明暗不一，故此非许可链的性能提升相对困难，许可链的性能提升相对容易。然此亦非一定之规，比如通过代议制可在公有链的几千个节点中定期选举产生一个为数较小的共识节点集合，此时也可借鉴许可链的优化技术提升性能。
有鉴于此，本文将缩小关注点，重点关注许可链的性能优化问题。由于PBFT算法[1]及其变体在开源许可链项目中得到的广泛应用，本文将主要以PBFT算法为例展开讨论。
关键词：区块链 许可链 性能优化

一、不忘初心

不完美是这个世界的重要特征，如张爱玲所说的：“有人说过‘三大恨事’是‘一恨鲥鱼多刺，二恨海棠无香，三恨红楼梦未完’。”对于每一位架构师而言，“优化”是个永恒的话题，无论多完美的产品都总有改进之处，而且很多时候一方面的改进必须以另一方面的牺牲为代价。经验告诉我们，在系统和算法的优化过程中，有百利无一弊的帕累托改进纵然不是没有，至少也是稀罕事，最常见的优化都会涉及某种牺牲和代偿。作为优化的最终指导，业务目标优先级的明确是最首要的事情。“优化”所需的“取舍”，一定是服务于业务目标的。鉴于此，本文后续所说的各种优化思路应被理解为仅是参考而非必选，实际项目中仍要“不忘初心”——所谓“初心”，就是业务目标。

二、硬件加速

硬件加速可能是最简单粗暴的性能优化方案，在区块链的发展历史中也有迹可循。比特币的挖矿芯片极大加快了SHA256难题的解题速度，使得使用者相对于未使用者而言获得了相当的优势。但是由于比特币的动态难度调整机制的存在，挖矿芯片的升级换代本身并不能缩短比特币的平均出块时间，也无助于比特币吞吐量的提升，所以称其为“性能优化方案”得看是在什么意义上说事。
然而硬件加速确实可以做得更多，最容易想到的是对非对称密钥签名的并行验证。以FPGA为例，虽然其主频比通用处理器为低（典型值如百MHz之于GHz），但其专用电路可以进行并行流水线处理，在一个时钟周期内实现更多操作。且FPGA可提供远比通用处理器更多的寄存器，从而可以并行验证多个签名。因此在自动化交易领域，硬件加速早已获得广泛应用[2],类似思想自然可以用于区块链的加速。
对于安全性要求很高的许可链来说，硬件加速还有其他附加收益。正如网银若使用USB Key可较使用文件证书有更高安全性一般，许可链私钥的存放若固化于可靠硬件（硬件钱包）也可提升其安全性。另一方面，硬件加速会带来一定的研发及实施成本，但鉴于许可链的玩家都具有相当的经济实力，通常不构成问题。

三、共识算法选择

共识算法的选择是区块链的核心设计考量之一。就目前公开的项目看，相当多的许可链直接采用了传统的拜占庭容错算法（BFT），其中又以经典的PBFT算法及其变体最为常见。这是因为在恶意节点数不超限制的前提下，BFT类算法可以支持较高的吞吐量和极短的终局时间，其正确性和活动性又可被严格证明，非常合乎大机构的需求。由于BFT算法为了达成单次共识一定需要借助消息的多轮组播，有些甚至是多对多的消息组播，比如在PBFT算法中需要1对N的pre-prepare消息组播、N对N的prepare消息组播和commit消息组播，受互联带宽的限制一般不适用于共识节点数较大的情形，但对于成员节点数不大、对交易终局性要求较高的许可链而言却正可扬长避短。反观公有链中使用的POW[3]、DPOS[4]等算法，由于每一轮共识都不可能通过成员间反复传播比对消息来实现，因此需要通过延长终局时间来间接校验，遂有“等待6个以上块的确认”等概率性的终局性规则出现。由此可见，共识节点数和终局性时间之间存在矛盾，每一种区块链都在基于自身目标进行取舍，只有是否适合自己，并无抽象的优劣高下。
学术界已经提出了各种BFT[5] [6] [7]算法，在此难以一一枚举。面对数量众多的BFT算法，如何结合自身需求选择合适的BFT算法是一个大课题，要求区块链的设计者同时深入理解业务需求和算法细节，在此仅举几例以供赏鉴。
Aardvark算法[5]是一个相当值得关注的BFT算法，也被称为RBFT（Robust BFT）算法，其设计指导思想在于提供一种“能够真正容忍拜占庭错误的拜占庭算法”。其作者通过研究认为，当下的很多BFT算法，包括PBFT和Zyzzyva[6]算法在内，其设计思路都是首先考虑尽力优化无拜占庭错误存在时的正确性和系统性能，其次作为兜底方案只是确保即使存在拜占庭错误系统也多少能够继续推进而已，并不去考虑面临拜占庭错误时的系统性能。其结果是，虽然论文中公布的理想情况测试数据一个比一个漂亮，当真面临精心设计的恶意节点协作攻击时系统性能就会急剧下降到接近瘫痪，因此虽然名为拜占庭容错算法，其实并不能在工程实用意义上容忍拜占庭错误。通过对PBFT算法的改良，RBFT算法使得面对最好和最坏的情况系统的性能都能大致保持不变，从而提供了真正实用的BFT。正如我们所熟知的那样，世上没有免费的午餐，其最坏情况的性能提升实际是以降低最好情况的性能换取的。如果区块链支持的业务要求在最坏情况下都能保持良好的性能，则基于RBFT算法构建区块链是值得考虑的。如果区块链的应用场景更关注正常情况的高性能，且能够容忍极端情况下的系统活动性丧失，则传统的PBFT算法可能更为合适。
开源项目Chain提出了自身独特的共识算法，称为Federated Consensus[7]，曾经也用过Simplified BFT的名称，笔者将其理解为PBFT算法的裁剪版本（不要将其与HyperLedger Fabric 1.0使用的SBFT算法[8]混淆起来，后者是PBFT算法的增益版本，将check point的稳定化变为每一轮共识皆需的第四阶段）。在chain之中，有一个固定的、不可变的块生成者（block generator），其唯一的任务就是将交易打包进待签名块后群发给N个块签名者（block signor）验证。每个块签名者如果验证通过了块，就将自己对待签名块的签名回送给块生成者。块生成者只要搜集到M个（M超过N的半数）来自不同块签名者对此的合法签名，对块的验证即告通过，此时块生成者只需要将带有M个签名的块群发出去，接收者看到了M个签名就认为共识已经完成。容错能力方面，这种算法在恶意的块签名者不超过（2M–N–1）个时有效，且算法明确注明不能承受块生成者出现拜占庭错误的情形。值得注意的是，由于其消息模式完全类似RAFT算法[9]和 2PC协议，因此撇开签名和验签的开销不谈，性能上有望接近非拜占庭容错的RAFT算法，实现上也可以简化很多，毕竟传统拜占庭容错算法最大的复杂性正是来自于自动处理块生成者的拜占庭错误。仔细分析可以看出，此算法的性能提升和开发简化完全来自于牺牲了块生成者的拜占庭容错能力，也牺牲了块生成者出问题时的系统活动性。
社区中类似的对PBFT算法的裁剪尚有多种，笔者对此的看法是：由于PBFT算法的每一阶段都有其特殊作用，故除非是裁剪者真正清楚裁剪的代价，业务目标也能够支持此类裁剪，否则不要轻易动手改造PBFT算法。
前文曾述及专用硬件设备的使用。如果区块链的设计者能够投信于特殊的硬件设备，还可在共识方面获得更大的收益。比如Intel的Sawtooth Lake[10]项目构建于Intel自身的SGX技术之上，其中提出的POET（Proof of Elapsed Time）算法提供了一种POW算法的替代方案，可以在不耗费大量电力的同时在公有链中达成类POW共识。可信硬件设备在许可链中的使用尚不止此，比如还可以利用可信硬件设备构建最多能够容忍接近半数恶意节点的区块链，突破普通BFT算法33%恶意节点的限制[11]，恐繁不录。
共识算法虽有多种，但值得庆幸的是在目前的许可链设计中将共识算法抽象化、模块化的趋势已经出现。通过将共识算法设计为可插拔、可替换的组件，用户在使用区块链时可以根据自身需要选择最合适的共识算法（甚至可以选用RAFT一流非拜占庭容错的共识算法），无需修改系统的其他部分。

四、共识算法性能优化：以PBFT为例

PBFT协议的论文中自带了若干优化，不在此重复细节。有几处值得关注，其一是，文中所说用基于对称密钥的MAC（消息认证码）替代基于非对称密钥的数字签名一法，仍有可以讨论之处：虽然法律和监管要求用户指令使用非对称密钥完成数字签名，但法律和监管者是否要求许可链的共识节点间传递的一切信息都使用数字签名而非MAC？由于法律和监管者未必要求系统内部不同组件之间处处启用非对称加密完成通信，因此可能尚留有部分使用MAC替代数字签名的空间可资利用。其二则是几处用摘要发送替代消息发送的优化，此法大大降低了带宽占用，从而使得网络数据传送量趋近于用来传统的RAFT算法，只在内部消息传送跳数上略有增加，因此合理的判断是，只要优化得当，PBFT集群的吞吐量应该和RAFT集群接近，时延只略有上升，但不应存在数量级的差异。虽然理论推演结论如此，鉴于如今基于PBFT的高性能区块链尚不多见，故笔者拟补充几点PBFT原始论文未能提及的性能优化方案以供参考。

1. 打包

因为单个区块通常包含不止一笔交易，而共识或称出块明显是按块进行的，所以打包很可能是在实施区块链时最为普通的优化方案。打包可以将共识节点间进行签名和验签的开销在块中的每笔交易上平摊，从而降低总体的开销。更重要的是，即使区块链的实现者采用最简单的停等模式来实现PBFT算法，也即在第N块达成共识前不启动第N+1块的共识，单纯依靠打包即可显著提升系统的吞吐量。考虑到许可链的成员节点可能跨地域分布，假设节点最大距离2000公里，则在全部节点间完成PBFT所要求的3轮通信至少耗时30ms，使用停等模式1秒最多完成33轮共识（以上计算还尚未计入报文经过网络设备时的额外延时等其他开销）。如果1轮共识只能如论文所说对单个消息完成共识，则每秒吞吐量只是33笔，虽然好于比特币，但若和RAFT的优秀实现相比明显存在问题。如果每轮共识针对打包后的一组消息进行，吞吐量虽不能线性提升，但也可提升明显，在中心化系统性能优化中有过经验的人应该都不难理解这一点。
如果打包方案仅限于此，仍不能减少区块中每笔外部交易带来的验签工作，虽然可以用前文所述硬件方案予以并行处理，但还有结合业务特征进一步优化的可能。许可链的共识节点通常是B端而非C端，C端客户通过B端客户间接接入区块链。如果业务允许，共识节点作为C端客户的代理，可以要求C端客户在提交请求前打包签名再一并提交，比如原本客户对每一笔申报都要独立签名的，现在可以要求客户可将最多10笔申报打成一个小包并一次性签名提交，如此验签工作量直接可以降为原来的若干分之一，若再辅以前述并行硬件处理方案，则系统性能可有明显提升。

2. 异步模式

通过上面的分析可以看出，如果限于停等模式，不要说PBFT集群，哪怕是在RAFT集群中吞吐量也不能做到最优。经验表明，在RAFT集群中要想进一步提升吞吐量可以使用所谓“异步”模式，也即主节点甫一发出第N号待共识报文即可立刻发出第N+1号待共识报文，完全无需等到集齐超过半数的确认应答，同样的经验也适用于PBFT集群。在这种模式下，pre-prepare/prepare/commit中的任一阶段都可以有多个区块同处其中，网络带宽得到最大利用，系统吞吐量也能接近对等的RAFT集群。
另一方面，异步模式下有一种更激进的策略：构建一个有区块但没有链的“区块链”。观察PBFT算法即可发现，PBFT算法一次只是对一个数组特定下标的内容完成共识，数组元素是否另行勾连成链则全不相干。PBFT算法允许先对第1001号元素达成共识，再回头对第1000号元素达成共识，这点很类似于以太坊CASPER协议的某个早期版本[12]。其好处是有望进一步降低共识达成的时延，缺点当然是增加了实现的复杂度。鉴于基于prevHash的勾连成链便于迅速比对完整历史，笔者倾向于若非万不得已不需要采用此种策略。

3. 并行执行

这里的并行执行特指PBFT算法执行的内部并行。前面提及利用硬件并行验签的手法，并行执行的思路当然还可以发扬光大。此处可以参考Disruptor[13]的性能优化思路，一方面通过共享缓冲区消除不必要的内存拷贝，一方面将多个原来单线程顺序完成的操作分拆至多个线程并行执行以提升处理速度。实因此种优化并非区块链独有，因此只略提一二。

4. 减少传输量

PBFT协议中常常用到一对多的组播，根据跨机构的网络互联情况，这种组播不一定真能基于UDP组播实现。如果跨机构的网络互联只允许走TCP，此时网卡/网络带宽可能会成为瓶颈。一种解决方法是使用P2P网络和Gossip协议来减少网卡上实际外发的数据量，比如从直接给另外21个节点各发送一份pre-prepare消息变为只给逻辑相邻的5个节点各发送一份pre-prepare消息。另一种可以叠加使用的解决方法是尝试引入压缩算法以期降低数据传送量，但此种方法是否奏效相当依赖于客户消息的可压缩性，即使奏效，也还需要观察额外的压缩解压操作引发的资源消耗是否会引发新的问题，所以也得灵活应变。
尚有另一种思路也可归入此中，其要旨是将完整数据的传播及存储交由较小的集群完成（此集群甚至未必要是BFT集群），在较大BFT集群中针对数据指纹进行共识，如此也可降低BFT集群中需要传播的数据量。公有区块链和IPFS[14]的结合、BigchainDB[15]对Casaandra数据库的运用、Polkadot[16]分离出单独的availability guarantors角色，都是很好的案例。与此同时，对这种设计作出的牺牲也应该有清晰的认识，并结合实际面临的状况予以评估。

五、共识分层和性能优化

稍加思考即可发现，区块链中其实存在两个独立层面的共识，其一可称为“输入共识”，其含义是各节点对指令的顺序及内容达成共识，类似传统数据通信的会话层，不牵涉业务操作；其二可称为“输出共识”，其含义是业务系统受输入的驱动，状态不断发生跃迁，同时产生一系列输出，此时各参与方对业务系统进入的状态及产生的输出达成共识 。此非孤明之见，Corda 区分交易的uniqueness和validity二者[17]， Polkadot区分cononicality与validity二者，都应是有见于此。
虽然这两层共识在设计上可以分离，但不同区块链对此的回应差别很大，将其说为区块链设计时面临的一大抉择也不为过。总的来说有三种方式：
第一种方式是只提供输入共识，此以Factom[18]项目为例。Factom只对数据内容和顺序进行共识，把对数据的后续检验及处理交给其他应用程序完成。由于不做输出共识，这种区块链很可能不内置智能合约功能。
第二种方式是以紧耦合的方式同时提供输入共识和输出共识，典型案例如以太坊。以太坊的区块头中不仅包含交易根，也包含状态根，通过一套机制同时达成对交易和终态的共识。
第三种方式是以分离的方式同时提供输入共识和输出共识，典型案例如Fabric 1.0[19]的设计。在Fabric 1.0中，输入共识在Orderer之间达成，Orderer只看到数据，并不理解任何业务含义，输出共识则通过Endorsor、Committer和应用层CheckPoint在一定程度上实现。
若按区块链实现的复杂程度来排序，第一种自然最简单，第二种次之，第三种最复杂。若按是否有利于性能优化来排序，则是第一种最佳，第三种次之，第二种最不利于性能优化。取以太坊为例，为了同时达成两层共识，必须在输入共识后串行执行业务逻辑，如此方才完成一轮共识。业务代码本身就可能很复杂，而以太坊的状态通常会保存在KV数据库中，完成一次Patricia树[20]访问又可能需要多次数据库读写，因此共识速度难以提升。另有一重缘故：出块者必须自己先执行一遍业务代码获得终态指纹后才能出块，但出块只是提议，存在交易历史稍后被逆转的可能，哪怕采用BFT算法也是一样。如果交易历史被逆转，原出块者必须先回滚原有交易。为了实现交易回滚，正常执行时就得增加额外操作和资源占用，同时还需要提供回滚逻辑，如以太坊就需通过Patricia树支持状态回滚，但付出了很大性能代价。
第一第三种方式下，业务逻辑和输入共识可以并行执行、不同业务逻辑也可能并行执行，因此最有利于性能优化。第一种方式更是给予用户更大的自由，用户可以完全甩开输出共识，也可以结合应用特征实现自己的输出共识，因此留出更大的性能优化空间。

六、状态通道与分区设计

闪电网络[21]可能是最有名的状态通道应用案例。其论文非常晦涩，但原理却很简单。代码性能调优的经验提示我们：优化编译、改进算法、调整数据结构等方式虽然很重要也很管用，但怎么能比得上“根本不执行”的强悍？既然在比特币区块链中优化性能如此艰难，为何不尽可能将交易放到链外执行？以比特币区块链为后盾，在链下实现真正的点对点微支付交易，区块链处理能力的瓶颈被彻底打破，时延、最终性、容量甚至隐私问题也迎刃而解，这就是比特币“闪电网络”（Lightning Network）的基本思路。
一般而言，通过状态通道技术，两方或有限多方得以共享一套状态，状态必须局部的，也即其变更只影响状态本身，不及其余。初态通过区块链创建，称为建立一个“状态通道”，其后对状态的变更都在链外进行，对外界保密，通过各方联合签名实现状态变更合法性的确认，并通过状态序号等方式在众多合法状态中区分出最新版本。在出现争议时，只要向区块链出示最新版本的合法状态，即可关闭状态通道并根据预设逻辑完成争议裁决。
分区（Sharding）以区块链互操作技术为基础，辅以合理的业务分区，虽然易于理解但很难实现，即使对于许可链也是一样，其主要挑战在于单纯增加分区未必能同步提升总吞吐量，尤其当分区间通信量很大更是如此。考虑到即使对于传统的中心化系统要实现通用的水平扩展也非易事，所以必须降低对于万能灵丹的心理预期。另一方面，从云计算、大数据、双11获得的经验告诉我们，充分利用业务特征将是缓解此类问题的有效手段。建议读者认真揣摩RSCoin[22]的分区设计，自当有所会心。

七、结语

许可链技术还在飞速发展，由于作者水平所限，本文内容一方面未必最新，尤其是不能涵盖未公开的独门秘技，一方面也未能面面俱到，有些课题如虚拟机优化、区块链动态配置切换[23]等无法一一予以探讨。总而言之，技术是灵活的，只要不忘初心，触类旁通，则优化之道自当无穷如天地，不绝似江河。

作者简介：朱立 上交所技术公司架构师，主要研究方向为高可用架构、区块链。
lzhu@sse.com.cn

参考文献

[1]M. Castro and B. Liskov, “Practical Byzantine fault-tolerance and proactive recovery,” ACM Transactions on Computer Systems, vol. 20, no. 4, pp. 398–461, Nov. 2002.
[2] A. MacArthur, “FPGA's - Parallel Perfection?,” Automated Trader, issue 02, July. 2006
[3] Satoshi Nakamoto, “ Bitcoin: A Peer-to-Peer Electronic Cash System”
https://bitcoin.org/bitcoin.pdf, 2008.
[4] “Delegated Proof-of-Stake Consensus,”
https://bitshares.org/technology/delegated-proof-of-stake-consensus/, 2014
[5] A. Clement, E. Wong, L. Alvisi, M. Dahlin, and M. Marchetti, “Making Byzantine fault tolerant systems tolerate Byzantine faults,” in Proc. of NSDI’09, 2009.
[6] Kolta, R., Alvisi, L., Dahlin, M., Clement, A., and Wong, E., “Zyzzyva: speculative Byzantine fault tolerance,” In SOSP (2007).
[7] “Federated Consensus

https://chain.com/docs/protocol/papers/federated-consensus, 2016
[8] S. Schubert, “Simple BFT,
https://jira.hyperledger.org/browse/FAB-378, 2016
[9] D. Ongaro, and J. Ousterhout, “In Search of an Understandable Consensus Algorithm,” In Proc ATC’14, USENIX Annual Technical Conference (2014), USENIX.
[10] Sawtooth Lake Project Homepage

http://intelledger.github.io/
[11] G.S.Veronese,M.Correia,A.N.Bessani,L.C.Lung,andP.Ver´ıssimo, “Efficient byzantine fault-tolerance,” IEEE Trans. Computers, vol. 62, no. 1, pp. 16–30, 2013.
[12] V. Buterin, “Understanding Serenity, Part 2: Casper

https://blog.ethereum.org/2015/12/28/understanding-serenity-part-2-casper/ , 2015
[13] M. Fowler, “Dissecting the Disruptor: Why it’s so fast

http://mechanitis.blogspot.com/2011/07/dissecting-disruptor-why-its-so-fast.html, 2011
[14] J. Benet, “IPFS-Content Addressed, Versioned, P2P File System(Draft 3)

https://github.com/ipfs/ipfs/blob/master/papers/ipfs-cap2pfs/ipfs-p2p-file-system.pdf
[15] T. McConaghy et al , “BigchainDB, A Scalable Blockchain Database
https://www.bigchaindb.com/whitepaper/, 2016
[16] G. Wood, “POLKADOT: VISION FOR A HETEROGENEOUS MULTI-CHAIN FRAMEWORK. Draft 1

https://raw.githubusercontent.com/polkadot-io/polkadotpaper/master/PolkaDotPaper.pdf
[17] R. G. Brown, “Corda: An introduction

https://www.r3cev.com/blog/2016/8/24/the-corda-non-technical-whitepaper, 2016
[18] P. Snow, et al., “Factom: Business Processes Secured by Immutable Audit Trails on the Blockchain, ”

https://github.com/FactomProject/FactomDocs/blob/master/Factom_Whitepaper.pdf
[19] E. Androulaki, et al., “Next Consensus Architecture Proposal, ”
https://github.com/hyperledger/fabric/blob/f19a1e6988b62c9ba566d6268d5baedea36061b8/proposals/r1/Next-Consensus-Architecture-Proposal.md
[20] Ethereum, “Patricia Tree, ”
https://github.com/ethereum/wiki/wiki/Patricia-Tree
[21] J. Poon, and T. Dryja, “The Bitcoin Lightning Network: Scalable Off-Chain Instant Payments, ”

https://lightning.network/lightning-network-paper.pdf, 2016
[22] G. Danezis, S Meiklejohn, “ Centrally Banked Cryptocurrencies,”

https://arxiv.org/abs/1505.06895, 2015
[23] A. Bessani, J. Sousa, “State Machine Replication for the Masses with BFT-SMART,”In 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2014, pages 355–362, 2014