Tower BFT:Solana 的高性能 PBFT 实现 | Solanas 8 Innovations

在本篇博客中,我们将探讨 Tower BFT。Tower BFT 是 Solana 创建的 PBFT 自定义实现,更强调实时性而不是一致性。在共识达成前,Tower BFT 使用 Solana 的历史证明 (PoH) 作为时钟,以降低消息传递的开销和延迟。

“为提供实时性,副本如果无法执行请求,则必须移动到一个新的视图。但是,需要注意,当至少 2f + 1 个非故障副本处于同一视图中时,此时间段应尽可能最大化,并且在执行某个请求的操作之前,需确保此时间段呈指数式增长。”(《实用拜占庭容错[1]》,Miguel CastroBarbara Liskov

Solana 实现的是 PBFT 的一种衍生,但其存在一个根本性的区别。PoH 在共识达成前会提供一个全局时间源。我们的 PBFT 实现使用 PoH 作为网络时钟,且 PBFT 中副本所用的指数递增式超时可以在 PoH 本身中计算和强制执行。

PoH 是作为有序哈希函数实现的可验证延迟函数。我们使用 VDF 这种宽松的定义,原因在于验证需要(计算时间)/(核心数)。PoH 的基本工作原理如下:

Sha256 尽可能快地进行循环,使每个输出成为下一个输入。
对循环进行采样,并记录迭代次数和状态。

记录的样本表示时间推移(编码为可验证数据结构)。此外,该循环可用于记录事件。

引用任何样本的消息一定是在相应样本之后创建的。
消息可以插入到循环中,并可与状态一并进行哈希处理。这保证了在下一次插入之前消息已经创建。

此数据结构保证了事件嵌入的时间和顺序,这个核心理念是 Solana 所有主要技术优化的基础。

换一种方式来解释:假如你现在处于一座岛上,一个瓶子漂流到你身边,瓶子内有一个 U 盘,U 盘中有 Solana PoH 账本。仅使用 PoH 账本,你可以计算网络中所有节点的状态。例如,如果为此账本所投的一票没有记录到最近 X 次哈希中,则节点会被视为失败。如果在最近 X 次哈希中,网络中绝对多数节点均对验证消息进行了签名,则账本被视为有效。

检查此数据结构的所有节点会计算出完全相同的结果,且无需任何对等通信。
PoH 哈希唯一地标识账本的这一分叉。
仅在获得投票的 PoH 哈希存在于账本中时,验证投票消息才有效。

这就引出了投票和 PBFT 的概念。由于账本本身可充当可靠的网络时钟,我们可以在账本中对 PBFT 超时进行编码。

投票从 N 个哈希超时开始。

验证者(通过消减)会保证在对某个 PoH 哈希作出投票后,验证者不再对不是该投票子级的任何 PoH 哈希投票(至少对于 N 个哈希)。

所有前批投票的超时时间均翻倍。

为使操作更易于管理,投票被限制在一个固定的哈希时段内(我们称之为”时隙”)。我们的期望时隙是表示大约 400 毫秒的哈希数。每隔 400 毫秒,网络具有一个潜在的回滚点,但每次后续投票会使网络在公开该投票前需停顿的实时时间翻倍。

假设每个验证者在过去 12 秒内进行了 32 次投票。12 秒之前的投票现在的超时时间为 2³² 个时隙,即大约 54 年。其结果就是,网络永远不会回滚该投票。最新投票的超时时间为 2 个时隙,即大约 800 毫秒。随着新区块加入账本,旧区块获得确认的可能性愈来愈大,因为旧投票的时隙数每隔一个时隙(大约 400 毫秒)就会翻一倍。

注意,尽管这听起来像是工作量证明中的概率性确定,但实际上不是。在 ⅔ 的验证者对某个 PoH 哈希投票表决后,该 PoH 哈希即被规范化,无法回滚。这与工作量证明不同,工作量证明中没有规范化的概念。

为防止被锁在网络其余部分之外,每个验证者仅在网络中绝大多数节点也投票表决相同账本后才会投票。各个验证者会监视之前某次投票的超时何时会超过预定义的阈值(例如,从 5 分钟到 10 分钟),并确保网络中绝对多数节点对包含该投票的分叉进行了投票。实际上,验证者会执行以下工作:

检查是否绝对多数节点已经对一个超时 10 分钟的时隙进行了投票
如果没有,则不投票

那么,在分区期间以及超时时间到期时,网络会发生什么情况呢?

任何已过期的选票均会被清除。
当且仅当子级别具有相同超时时间时,上一级别的超时才会翻倍。

例如,假设某个场景中当前的超时为:

64, 32, 16, 8, 4, 2

如果某个验证者停止给 17 个时隙投票,然后重新开始投票,则该验证者产生的超时将为:

64, 32, 2

需要再进行另外 4 次连续投票,之后所有上一级别的超时才会再次翻倍。

64, 32, 4, 2

64, 32, 8, 4, 2

64, 32, 16, 4, 2

最终,第四次投票会使所有超时翻倍。

128, 64, 32, 16, 8, 4, 2

此方法使得网络可以连续地流式处理区块,无需在绝对多数节点观察到相同账本之前暂停账本。另一个值得注意的方面是,网络中的每个参与者都可以在无任何 P2P 通信的情况下计算其他各个参与者的超时。这使得 Tower BFT 具有异步性。

我们预期会出现许多被快速丢弃的微分叉。当某个验证者检测到多个分叉时,诚实的验证者会计算各个分叉的有效权益加权超时,并选择最大的一个。验证者奖励仅适用于达到 2³² 超时的投票。因此,验证者对超时最大的分叉投票符合激励机制,因为权益加权超时最大的分叉会在网络中产生最大的奖励。