HOME
极简区块链共识协议

区块链作为典型的分布式系统,其共识核心的设计和实现一直困扰着开发者。如何设计一种简单而高效的共识协议一直是学术界和工业界追求的目标。比特币的设计虽然简单,但性能低下且共识结果具有一定随机性,因此不适用于企业之间业务量巨大的场景。近年来大家非常关注的联盟链中应用的共识算法(PBFT、Tendermint)虽然性能接近传统的共识算法(Paxos、Raft),但协议设计相对比较复杂,实现难度较高。本文着眼于一种针对联盟链设计的极简区块链协议 Streamlet。具有一定区块链知识背景的人只需要不到10分钟就能理解整个共识流程,因此 Streamlet 不仅适用于工程化实现,而且具有非常现实的教学意义。

背景

Streamlet[1] 由 Cornell 大学的 Elaine Shi 教授团队在2020年2月的斯坦福区块链大会提出(也许更早),其前身是 Pala[2]。Streamlet 可以算作是近五年来区块链领域与传统拜占庭共识(Byzantine fault-tolerant,BFT)领域的集大成之作,在包括经典 PBFT[3],Cosmos 在用的 Tendermint[4],以太坊 2.0 将要用的Casper[5],以及 Facebook 推出的数字货币 Libra[6] 所基于的 HotStuff[7] 等协议中都能感受到对 Streamlet 的影响。尽管如同一个大杂烩,但 Streamlet 的目标是一种堪比比特币的极简区块链协议。

Streamlet 遵循传统 BFT 协议的容错规则,即在节点数目为 n 的网络中,可以容忍最多 f 个拜占庭节点,需要满足 n > 3f。Streamlet 依赖于半同步(partially synchronous)网络假设,即网络在大部分情况都是好的,消息可以在一个能够预测的延迟内传播,但在某些情况下网络可能会经历一段波动期(Global Stabilization Time,GST),并最终会恢复。在GST期间,网络延迟无法预测。Streamlet 和大多数协议一样,保证协议在异步网络下的安全性(safety),当网络回归同步时可以进一步保证活性(liveness)。

Streamlet

在 Streamlet 中,协议的运行被划分为一个个同步的 epoch(这里的epoch是指生成一个区块的时间周期,例如每个 epoch 持续 1 秒),每个 epoch 都由哈希算法随机分配一个 leader进行“随机选主”。每个 leader 在属于自己的 epoch 中发布(propose)一个区块给其它 replica 节点投票(vote)。投票可以被看作是投票者用自己的私钥对区块哈希值的签名,并将其广播给其它所有节点。如果一个区块收到了来自超过 2/3 不同节点的投票,则被认为是“已证区块(notarized block)”。由已证区块组成的链被称为“已证链(notarized chain)”。接下来介绍整个 propose-vote 的流程中的一些细节。

  • 发布规则(Proposing Rule)。每个 leader 都在本地最长的已证链的基础上发布新的区块,即新区块的 prevHash 指向本地最长的已证链末尾的区块。
  • 投票规则(Voting Rule)。每个 replica 只对来自当前 leader 发布的第一个区块投票,并且该区块必须扩展自本地最长已证链,即该区块的 prevHash 必须指向投票者本地最长的已证链末尾的区块。
  • 确认规则(Commit Rule)。一个区块在区块链中被确认(commit)意味着网络中所有诚实节点对这个区块已经达成了共识,不会再对共识结果修改。已证区块并不一定最终会被确认。在一个已证链中,当存在三个连续的已证区块时,其中前两个区块以及同一链上之前的所有区块都被确认。在这里,连续区块的意思是连续的 epoch。例如,在图 1 中,epoch 5、6、7 连续产生了三个已证区块,因此当区块 7 成为已证区块时,区块 5 和 6 以及之前的区块 2 都被确认。
图 1. Streamlet 安全性举例[1]

Streamlet 协议的整个流程到这里就全部介绍完了,是不是堪比比特币中的 PoW 一样简单?其中的发布规则和投票规则类似于比特币中的最长链(The Longest Rule)原则,而确认规则类似于比特币中一般需要末尾 6 个区块确认的规则。两者看起来有很多相似之处,但算法本质却大有径庭。从这点看来,Streamlet 吸收了区块链的设计精髓并将其与传统的 BFT 协议融合在一起,得到了新一代的 BFT 协议。那么有些读者可能想问了,如此简单的协议安全性如何呢?

安全性

在区块链中,协议的安全性可以简单表述为不存在两个同样高度的不同区块被确认。在这里我们简单通过图示来展示在异步网络以及拜占庭攻击的情况下 Streamlet 是如何保证安全性的。如上面的图 1 所示,由于 epoch X 的区块与区块 6 在同一高度,那么问题可以转化为:是否存在区块 X 且 X 是已证区块?

为了证明上面的问题不存在,我们采用反证法。首先,假设存在已证区块 X,那么只存在两种可能性,即 X = 4 或者 X ≥ 8,这是由于同一个 epoch 不可能产生两个已证区块(诚实的 replica 不会在同一 epoch 给不同的区块投票)。下面分情况讨论。

  • X = 4。由于区块 X 是已证区块,意味着有超过 2/3 的节点给区块 X 投票,那么可以进一步推论出超过 2/3 的节点在给 X 投票的时候已经在本地有了已证区块 3。因此,当协议运行到 epoch 5 的时候,不可能有足够多的节点给区块 5 投票。这是由于投票规则的限制,诚实节点只给最长已证链上的区块投票。这与区块 5 是已证区块的假设违背。
  • X ≥ 8。由于区块 7 是已证区块,意味着有超过 2/3 的节点给区块 7 投票,那么进一步可以推测超过 2/3 的节点在给区块 7 投票的时候已经在本地有了已证区块 6。因此,当协议运行到 epoch X 的时候,同样由于投票规则的限制,区块 X 不可能成为已证区块,这与假设违背。

上面两种情况已经包含了可能出现的所有情况,因此安全性得证。虽然图 1 所示的情况是一个个例,但很容易对结论进行一般化证明。详细证明可以参考原论文。

活性

活性的含义是客户端发送的交易最终会在区块链上被确认。在传统 BFT 协议中,活性的保证的其中一个前提是足够多的诚实节点在同一 epoch 的时间足够长。Streamlet 为了使得协议足够简单,采用了同步时钟来保证活性。例如,每个 epoch 被预设成固定的 1 秒钟。在实际的使用中可以将每个 epoch 的时长根据网络最大延迟来设置。由于以上的限制,Streamlet 一般只会被部署在网络条件较好的数据中心网络中,否则很难找到一个合适的 epoch 长度,进而影响协议性能。

在 Streamlet 中,活性的证明被表述为在 GST 之后如果连续 5 个 epoch 都是诚实的 leader,那么一定会有区块被确认。由于在长时间运行中,总会出现至少一次联系 5 个 leader 都是诚实的情况,因此活性可以得到保证。那么问题是,为什么需要 5 个连续的而不是 3 个?这里可以简单理解为前 2 个 epoch 用来解决由于 GST 所造成的潜在的不一致,之后连续 3 个 epoch 则是确认规则所要求的,为了保证最终能有区块被确认。完整的活性证明可以参考原论文。

协议对比

接下来通过对比讨论目前常见的几种 BFT 协议之间的差异。其中,Streamlet 和 HotStuff/LibraBFT 都是新型的链式 BFT,即节点的每次投票不仅是对当前区块的投票,同时也是对这个区块之前所有区块的投票,因此相比于 Tendermint 和 PBFT来说,消息的种类较少,实现起来也更简单,也更容易优化性能。由于链式 BFT 的特性,接收到一轮 2/3 投票的区块并不会被 commit,因此当区块不连续的时候会有分叉产生。

在协议同步方面,只有 Streamlet 采用了同步时钟的方式。由于很难保证不同节点之间的时钟严格同步,所以一般情况下每个 epoch 的时间会略长与网络最高延迟,从而提高了协议的延迟。其它三种协议采用传统的超时加倍模式,即每当一段等待时间之后没有收到区块,那么则将下一轮的等待时间加倍。虽然这种方式没有额外的网络开销,但在某些极端情况下会使得协议长时间停滞。LibraBFT 使用了消息传递的模式(Pacemaker)进行同步。虽然这种方式能够快速实现同步,但也使得 view-change 时的消息复杂度提高到 O(n^2)。

Best-case 延迟是指在最好的情况下协议经过多少轮投票可以确认一个区块。虽然 Streamlet 和 HotStuff/LibraBFT 都要求 3 个连续的区块才触发确认事件。但 Streamlet 可以一次确认两个区块,而 HotStuff/LibraBFT 只能一次确认一个区块。

从消息复杂度来看,HotStuff/LibraBFT 和 Tendermint 采用聚合签名或者阈值签名的技术由一个节点(比如 leader)将来自 replica 的签名聚合成一个单一签名后再广播给所有 replica,因此消息复杂度可以达到 O(n)。而 Streamlet 和 PBFT 则在投票阶段使用了广播,使得消息复杂度较高。

另外一个值得被提到的特性是 view-change 时的响应性(Responsiveness)。响应性指的是当 view-change 发生时,下一个 leader 是否能快速推进协议。例如,Tendermint 没有响应性,在发生 view-change 的时候节点需要等待一个 timeout,以确保在 timeout 之内收到所有的有效消息。如果没有 timeout 的假设,则可能会由于节点锁在不同的阶段而导致活性出现问题。HotStuff/LibraBFT 和 PBFT 都有响应性,但代价分别是多一轮的投票以及更高的复杂度。

从上面的对比可以看出,即使共识算法经过了这么多年的发展,也没有出现哪个协议是全能将军。协议的设计本质就是在取舍,不仅体现在安全性和活性之争,也包括性能、复杂度、容错性、响应性等多种性质。某些协议的特性只有遇到合适的应用场景才能发挥价值。例如,在一些网络环境较好的数据中心当中,选择 Streamlet 可能在工程实现以及延迟上更有优势,而在一些广域网环境中可能选择消息复杂度更低且具有响应性的 HotStuff 更好。

总结

Streamlet 作为新一代 BFT 共识协议,很好地将区块链中的链式结构与传统 BFT 相结合,极大简化了协议设计,不仅降低了开发者学习区块链和 BFT 协议的门槛,也为工程师们开发区块链系统提供了很好的模板。

参考文献

[1] Streamlet: Textbook Streamlined Blockchains

[2] PaLa: A Simple Partially Synchronous Blockchain

[3] Practical Byzantine Fault Tolerance

[4] Tendermint

[5] Casper the Friendly Finality Gadget

[6] State Machine Replication in the Libra Blockchain

[7] HotStuff: BFT Consensus in the Lens of Blockchain

作者简介

盖方宇

来自趣链科技基础平台部,区块链共识算法研究小组