比原链 BBFT 如何让共识更快——兼论 BBFT 与 FBFT/HotStuff 的比较

本贴最后更新于 1723 天前,其中的信息可能已经东海扬尘

前言

近日比原链(BYTOM)技术团队发布了 Bystack 区块链 BaaS 平台,其中包括侧链的共识算法 BBFT(Bystack Byzantine Fault Tolerance)。笔者将在这篇文章中阐述比原链 BBFT 尝试解决的问题以及分析 BBFT 与其他各家共识协议的主要差异。BBFT 是一个 PBFT 的变形,它的原理与 PBFT 一脉相承。若想深刻理解 BBFT 的巧思,则必须进入 PBFT 的脉络推敲。早在区块链藉由比特币的大红大紫之前,PBFT 就作为共识协议存在于世界上了。由 Castro 和 Liskov 于 1999 年发明,它是一个具有 20 年历史的经典设计,它的发明是为了解决分布式系统中的一个经典问题:拜占庭将军问题。直到今日,PBFT 仍蕴含许多值得反复推敲的巧思,不断启发后世发明出更好的协定。 

PBFT 基本的运作流程

 

PBFT 是一个具有二轮投票的三阶段协议,每个视域(View)都会有一个特定的节点作为领导节点(Primary/Leader),负责通知所有节点进入投票流程。各节点则会经历 Pre-prepare/Prepare/Commit 这三个阶段,并依据接收的讯息决定是否投票/进入下一阶段,每个节点投完票后将讯息发给所有其他的节点。若个节点在两阶段投票之后取得多数共识,则各节点可以更新本机的状态,结束这一回合。 视域变换(View-change)仅当多数节点发起时执行,当目前的领导节点并未正常执行任务时,这可以替换当前的领导节点,保证协议正常运作。

 

PBFT 的特性

 

PBFT 与中本聪共识(区块链)有相当不同的特性:PBFT 是一个许可制的、基于领导节点的、基于通讯的、安全性重于活跃性的共识协定。

  • 许可制的(Permissioned):PBFT 并非完全开放的,这是由于 PBFT 需要让节点能够验证彼此的讯息以及精准掌握节点的数量,区块链则是属于对任何人都开放的非许可制(Permissionless)。
  • 基于领导节点的(Leader-based):也就是先决定领导节点(Leader),再由领导节点送出提议,这样做最直接的好处就是不需要浪费自己的运算资源去争取当领导节点的机会,然而缺点就是只有在视域变换时才轮替领导节点,成为领导节点的机会并不公平,缺乏加入网络的诱因;区块链则是在多个提案中选择工作证明难度最高的区块作为共识,虽然这样会造成运算资源的浪费,但是成为出块者的机率大致是公平的,其与算力成正比。
  • 基于通讯的(Communication-based):PBFT 的安全性奠基于 3 阶段投票,虽然不必如工作证明般消耗大量计算资源,但数量庞大的通讯也造成可扩展性的瓶颈——就算是号称最实用的 PBFT,也无法扩展到 1000 个以上个节点。不仅如此,PBFT 使用消息验证代码(MAC),每投一轮票就需要每一个节点验证一次讯息,大量的签名/验证也是另一个潜在的瓶颈。
  • 安全性重于活跃性的(Safety over Liveness):PBFT 不论在何种网络假设下(同步/异步)都能确保安全性,几乎不可能出现分岔,因此具有实时敲定(Instant Finality)的特性;相对地,区块链则是活跃性重于安全性,其安全性有赖于同步的网络,而具有复数个共识(及分岔)的情况也相当常见,需要经过一定数量的区块「确认」才能保证其不再分岔的机率足够大。

 

PBFT 的问题

 

首先,PBFT 中的每个节点都需于每一轮投票中做 n-n 的通讯,假设 n 为 1000,则每一次的共识都需要至少 100,000 次的通讯,尽管 PBFT 已经是 BFT 家族当中最实用的协议,这么巨量的通讯需求仍是扩展的瓶颈。

 

如何提升效率?

 

聚合签名

为了提升效率,一个直觉的思路是:避免 n-n 的通讯。我们可以指定网络中的某节点作为协调者来发送/接收每个节点的投票,这样每个节点都只需要向协调者发送讯息即可,从而避免了 n-n 的通讯。然而,在这样的情境下,协调者有作恶的可能,因为协调者可以在未确实接收到指定数量的讯息前便执行下一轮投票或者进行状态更新。因此,我们可以使用门坎签章(Threshold Signature)来保证协调者的正当行为,门坎签章的可以保证:需集合超过门坎数量(t-of-n)的签章才有效。也就是说,我们可以指定:唯有当协调者集合 2f+1 个门坎签章后,协调者才能带着合法的签名继续推进共识。Harmony FBFT 便是一个使用聚合签名以提升效率的 BFT 家族协议。

图 1:FBFT Signature Aggregation

管线设计

每个内容都必须经过二轮投票/三个阶段才能达成共识,如果有 m 个内容就需要执行 2m 次投票。管线设计(Pipelining)可以减少投票的次数,它的基本思路如下:让每个节点在投第 i 轮的 prepare 阶段时,同时也是对其前一个内容 i-1 的 commit 阶段投票。这样做便可以节省对同一个内容重复投票的冗余,大幅提升效率。这样的思路首见于 2018 年发表的 HotStuff 协议。

图 2:HotStuff Pipelining

只让部分节点参与共识:最小生成树

另外一种提高效率的方法,就是避免使所有的节点参与共识,这也正是比原链 BBFT 采取的作法。在 BBFT 中,节点分为三种:Consensus Node/Gateway Node/Leader Node,这些节点形成树的结构,树为网络中节点的最小生成树(Minimal Spanning Tree),可能由分布式算法得出,或是由外部服务提供。树叶的节点即为 Consensus Node;树根为 Leader Node;其他部分为 Gateway Node。每种节点都有分别的任务:Consensus Node 负责进行投票;Gateway Node 则不需参与投票,但必须负责聚合由 Consensus Node 送来的签章;Leader Node 负责与其他 Leader Node 交换讯息。BBFT 的运作流程如下图所示,BBFT 的共识过程,便是讯息由树根向树叶传播再回到树根的过程。

图 3:BBFT: Minimal Spanning Tree

图 4:BBFT Process

 

如何确保正确性(Safety and Liveness)?

 

在为 PBFT 带入新技术以提升效率的同时,也必须确保协议本身的安全性与活跃性。接下来我们来看看,上述的协议是如何确保这两者。

视域变换(View-change)

FBFT 沿用了 PBFT 的视域变换,即在正常情况下并不更换领导节点,仅有当超过 2f+1 个节点发起视域变换才会更迭领导节点。视域变换虽然本身是一个能够替换作恶领导节点的机制,但它同时要求协议必须具有 3 个阶段,才能保证协议的安全性(即不分岔)。

领导节点轮替(Rotating Leader)

HotStuff 另一方面则引入了领导节点轮替的机制,在每个回合都更换领导节点,如此来回避视域变换高额的通讯成本。领导节点轮替也常见于许多 BFT 家族的协议,算是目前保障安全性机制的主流。

混合式(Hybrid)

比原链 BBFT 则取各家所长,同时应用了视域变换与领导节点轮替,等于是上了双重保险。不过值得注意的是,目前的 BBFT 技术白皮书仅有一轮投票的模型,并未提出两轮投票/三阶段共识的模型。另外,领导节点轮替的顺序也将基于各节点的权益(Stake),若节点出现违反协议的行为则该节点会遭受惩罚。

 

BBFT 的挑战

 

综合以上的分析与比较,BBFT 目前有几个显著的挑战。首先,是最小生成树的产生方式,如何同时兼顾去中心化与效率?其次是 BBFT 仅采取单轮投票作为共识,在引入视域变换的情况之下,可能会发生分岔,这样的网络也会遭受日蚀攻击的威胁。最后,引入门坎签章的前提下,势必需要引入分布式私钥生产协议(Distributed Key Generation)以共同生成私钥,这部分于技术白皮书中尚未提及,却是可能造成瓶颈的潜在因子。

 

结语

本篇文章简介了 PBFT 的特性及其效能问题,并比较了 FBFT/HotStuff/BBFT 等协议针对效能问题的解决思路,最后归纳出比原链 BBFT 的未来挑战,希望能帮助读者更理解 BBFT 的精髓。 

参考资料

作者:Juin Chiu

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...