Moonshot 共识：基于区块链 SMR 的乐观协议

写在前面

公共区块链网络正凭借安全的去中心化计算和存储来颠覆现代社会。这些公链将具有容错机制的分布式系统设计与密码学相结合，实现了比传统中心化计算机网络更高的透明度、问责制和完整性，所以非常适合解决许多传统上需要依赖少数受信任方的问题。

因此，区块链为增加个人自治和社会效率提供了许多机会。Supra团队坚信，这项技术有潜力在全球经济和文化方面引发革命，从而定义下一个世纪的走向。

2008年比特币的横空出世为当今区块链行业的发展铺平了道路。如今，公链的队伍正在不断地发展壮大，势必继续掀起区块链行业的热潮。

区块链与共识

那么，究竟什么是区块链呢？简单来说，区块链实质上是一种分布式数据库类型。这个数据库记录了一个不断增长的已完成交易的日志，而所有这些交易皆由系统的用户在与系统交互时提交。这些交易的用途取决于所涉及的区块链的能力，但它们总有某种副作用。这些副作用会更新数据库中称为区块链的状态的另一个部分，并负责跟踪用户关心的信息。区块链网络的目标是确保网络中所有计算机 (通常称为节点) 以相同的顺序处理相同的交易，从而让它们达到相同的状态。

每个区块链网络都依赖于共识协议来实现这种一致性。共识协议由称为验证者 (validators) 的计算机运行，通常将交易分组成块以提高效率。验证者共同同意每个区块的顺序，并生成不可伪造且可验证的协议证明，我们将其称为规范性证明 (canonicity proof)。此证明允许验证者集合之外的节点通过维护自己的区块链本地副本参与区块链网络，而无需参与共识协议。

当节点将新区块添加到其本地区块链中时，该区块被认为具有某种程度的最终确定性(finality)。某些区块链，如比特币及其衍生链，只能保证概率性的最终确定性 (probabilistic finality)。例如，当比特币节点向其本地区块链添加新区块时，可能会因为验证者共同生成了一个不包括此区块的较长链，而最终不得不替换该区块。由于比特币节点需要接受他们所知的最长链，如果发生这种情况，节点将会被迫改变其对链的观点，才能继续成为主链的一部分。

其他网络采用不同的规则来实现相同的效果。但出于本文的目的，我们特别关注实现确定的最终确定性 (deterministic finality) 的区块链共识协议。这些协议确保如果任何节点向其区块链提交新区块，那么它将永远不必用另一个区块替换该区块。这些协议的正式名称为“状态机复制” (State Machine Replication，简称SMR) 协议。

更确切地说，SMR协议确保，如果任何两个诚实的进程各自将一个区块提交到其各自本地区块链的相同位置，则这两个区块被视为相同区块。这种属性称为安全性 (Safety)。这些协议还确保在网络继续运行的同时，验证者会继续向其本地区块链添加新块。这种属性称为活性 (Liveness)。

SMR协议有多种不同类型，现在我们特别关注的是那些通过将每个区块明确链接到其直接前一个区块，逐个对区块进行排序的协议。我们将这些类型的SMR协议称为基于区块链的SMR协议。

上图说明了基于区块链的SMR协议的共识过程。协议始于其中一个验证者 (在此处表示为白色圆圈) 从其本地交易池中构建一个区块，并将其提议给其他节点，作为添加到区块链的候选区块。我们将这个验证者称为领导者 (leader)。之后，其余的验证者努力生成一个针对这个提案的规范性证明，且该提案的构建取决于协议。监控这种证明的任何节点都通过将所有包含的交易添加到其已完成交易的日志，并将其副作用应用于其状态，将相应的区块提交到其本地区块链中，如下图所示：

问题设定

我们现在要介绍的是Moonshot家族基于区块链的SMR协议。这些协议是以Optimistic Proposal为特色的新型区块链共识协议集合。我们将主要关注Moonshot协议家族的第一个协议 – Chained Moonshot。为方便大家理解，我们将首先定义Moonshot协议所构建的环境。

像许多其他区块链共识协议一样，Moonshot协议使用拜占庭容错 (BFT) 算法。这意味着即使一些验证者崩溃或违反协议，它们仍将继续正确地运行。我们将行为如此的验证者称为拜占庭式验证者 (Byzantine validators)，而准确遵循协议的验证者则称为诚实的验证者(honest validators)。

我们假设所有的拜占庭式验证者都由单个对手控制，意味着他们可以合作，以尽可能多地损害系统。我们还假设这个对手是静态的，意味着它可以在协议开始之前选择要破坏的验证者子集，但在执行过程中不能对此集合进行任何更改。

通俗地说，Moonshot协议容忍最多三分之一的验证者为拜占庭式。更准确地说，我们要求网络中的验证者总数 n 满足n≥3f+1，其中 f 是拜占庭式验证者的数量。出于本文的目的，我们将假设 n=3f+1，并将术语法定人数 (quorum) 用于指代由2f+1个或更多的验证者组成的群体。我们还允许对手在验证者之间的通信通道上具有一定程度的控制。我们假设网络中的所有验证者直接彼此通信。我们还假设在这些点对点链接上发送的消息经过密码学验证，这意味着对手无法伪造或修改这些消息。我们允许对手延迟这些消息，但要求对手最终必须传递这些消息。

具体来说，Moonshot在“部分同步”(Partially Synchronous) 的环境下运行。有界同步网络 (Synchronous network) 是指消息发件人发送消息到接收者接收消息之间的延迟存在已知的上限Δ。相比之下，异步网络 (Asynchronous network) 是指消息传递延迟上没有时间界限的网络。

部分同步网络模型介于这两个模型之间。“部分同步”有几种变体，但我们特别考虑了我们认为最具代表性并且适用于现实世界公共网络的类型。在这个版本的“部分同步”模型中，网络可能在异步和同步之间交替。我们将网络从异步过渡到同步的时刻称为“全局稳定时间” (Global Stabilization Times，简称GST)。您可以在我们的白皮书中找到更正式的定义。

我们使用Δ表示GST后消息传递延迟的上限，并使用δ表示GST后的平均传递延迟。相应地，δ≤Δ，具体取决于对手的行为。

Moonshot 介绍

纵观现有基于区块链的SMR协议，其中一些协议的运作环境与Moonshot相同。我们先介绍这些协议，以便理解Moonshot Optimistic Proposal技术背后的思路。我们将从区块最终确认延迟、区块间隔和消息复杂度 (又称为通信复杂度) 方面对这些协议进行评估。我们将区块间隔定义为区块提议之间的时间，将区块最终确认延迟定义为从提议区块到大多数诚实验证者提交区块之间的时间，然后我们用n来计算就单个区块达成共识所需的大致信息数量，从而渐进地衡量消息复杂度。

具体来说，为了便于计算，我们将只关注这些协议的正常路径 (Normal Path)。当协议在没有中断的情况下运行时，我们将其称为“正常路径”(有时称为Fast Path、Happy Path 或Steady State)。反之，当协议在一定时间内 (以Δ衡量) 未能就共识实例达成一致时，它会进入其回退路径 (Fallback Path)，这种情况可能是由于网络不同步或拜占庭式领导者导致。这些协议在正常路径中运行时效率最高，而回退路径则可以使它们实现活性。我们将在后文中进一步探讨这些协议的回退路径。

Tendermint

Miguel Castro和Barbara Liskovgo共同设计了Practical Byzantine Fault Tolerance (PBFT) SMR协议，并在1999年OSDI会议的论文中公开发表。PBFT是首个针对部分同步环境的拜占庭容错SMR的公开解决方案。多年后，PBFT被应用到区块链环境中的Tendermint协议。Cosmos及其生态系统中的许多区块链目前都使用该协议作为其共识引擎。

与Moonshot假设了一个完全连接的网络，并由不同验证者之间点对点的直接通信链接进行这种方式不同，Tendermint则假设消息通过八卦协议进行传递。为了公平比较，我们将使用在与Moonshot相同的环境中运行的Tendermint变体。我们假设每当Tendermint验证者从其中一个节点那里收到先前未见的消息时，会立即将该消息转发给所有其他验证者。

此时该协议的通信复杂度为O(n3)，因为当系统正常运行时，每个进程都会收到O(n)个唯一的投票。我们承认，可能存在一种更有效的将Tendermint转换为点对点环境的方法，但我们使用此实现方式是因为它简单，并且我们确信它保留了原始八卦协议所提供的保证。为了便于阅读，我们下图介绍中省略这种更有效的转递。

现在，让我们看看这个修改过的Tendermint版本如何在其正常路径中运行。假设我们有一个由4个验证者组成的网络，其中一个被指定为领导者，负责提议要添加到我们区块链的下一个区块。Tendermint的正常路径如下:

步骤1: 领导者构建一个新的交易区块，扩展上一个已提交的区块，并通过提案 (Proposal) 消息(在Tendermint白皮书中称为Pre-Prepare) 将其广播给其他3个验证者。

步骤2: 验证者将他们对该提案的背书——Prepare投票，发送给其他所有验证者。在步骤2结束时，验证者从每个节点收到一个Prepare投票。他们各自收集这些投票的法定人数，并形成Prepare Quorum Certificate (Prepare QC)，然后锁定相关区块。

步骤3: 在形成Prepare QC的基础上，验证者向彼此发送第二次提案的背书——Commit投票 (在Tendermint白皮书中称为Pre-Commit)。同样，他们每个验证者从彼此那里收集这些投票的法定人数，并形成Commit QC。Commit QC作为区块的规范性证明，允许监控它的节点提交相关区块。

步骤3之后，验证者进入新的轮次，重复这一进程。因此，Tendermint 的正常路径具有以下特点:

区块最终确认延迟: Tendermint在3δ内确认一个区块;
区块间隔: Tendermint每隔3δ产生一个区块;
通信复杂度: Tendermint验证者必须发送O(n3)条消息才能就某一区块达成共识。

Tendermint的两轮投票使之获得了Safety SMR属性。第一轮投票产生的Prepare QC证明，大多数诚实的验证者认为新区块是有效的。第二轮产生的Commit QC证明，大多数诚实的验证者都知道这个事实，并锁定了相关的区块。Tendermint的投票规则确保，如果验证者锁定了一个区块，那么它不会为在区块链中相同位置或高度提议的任何其他区块投票。

因此，由于QC证明需要3f+1票中的2f+1票，如果一个区块实现了Commit QC，那么，即使拜占庭验证者为这两个区块投票，任何其他在相同高度提议的区块最多也只会收到2f票。然而，这个规则相当严格，阻止了并发，并且在没有Tendermint八卦协议提供保障的情况下，阻碍了活性。我们会在之后介绍的协议中放宽这一要求。

Jolteon

现在，让我们探讨一下最近的SMR协议，Jolteon。这个协议展现了round pipelining的概念，并且像Tendermint一样，包括两个投票阶段。Jolteon运行的正常路径如下:

步骤1: 与Tendermint类似，领导者构建一个区块B1并向所有人广播;
步骤2: 同样与Tendermint类似，验证者为这个区块发送Prepare投票。但是，并没有像所有人广播这些投票，而是直接将投票发送给下一轮的领导者，后者充当聚合器并像此前一样构建QC;
步骤3: 随后，该领导者创建一个新区块，其中包含B1的QC作为证明，表明它正在扩展最近被网络接受的区块。在步骤3结束时，所有验证者都会收到B1的QC，使他们能够锁定B1;
步骤4和5: 然后，重复步骤2和3，以构建B2的Prepare QC。该QC作为B1的Commit QC，同时与第三位领导者提议的B3一起发送给所有验证者，使他们能够锁定B2并提交B1。

如我们所见，Jolteon在很多方面与Tendermint有所不同。首先，它允许领导者基于其前任的Prepare QC来提出提案。这使得协议能够同时在多个区块上达成共识，与Tendermint的严格顺序进展相比，这是一项显著的优化。这反过来使之能够通过将Prepare和Commit投票合并成一条消息来进一步减少达成共识所需的消息数量，至少在正常路径中，B2的Prepare投票也对应于B1的Commit投票。我们将后一种优化称为QC chaining。QC chaining最早在Chained HotStuff中引入。

然而，上述优化伴随着一些副作用，包括潜在的安全威胁。Jolteon通过一种称为“双链提交规则”(Two-Chain Commit Rule) 的修改提交条件来克服这些威胁。这个规则要求节点只有在监控到两个连续区块 B 和 B′ 的 QC 时，才在r轮提交区块B，并按照高度升序提交其所有未提及的祖先区块。其中，B′在r+1轮中提出，且包含B的QC。

简而言之，这意味着如果任何节点用B触发了双链提交规则，那么在对 B之后提出的任何区块进行投票之前，必须至少有f+1个诚实的验证者锁定了 B。Jolteon的投票规则比Tendermint的更为复杂，因此无需详细说明原因，这反过来确保了未来每个认证区块 (即获得QC的区块) 都保证扩展B。

最后，Tendermint验证者广播他们的投票，而Jolteon则依赖于投票聚合器。Jolteon的鼻祖 HotStuff 最初引入了投票聚合的概念，其目的是即使在投票阶段验证者只能与另一个验证者进行通信，也能获得能够在正常路径中达成共识的协议。更确切地说，HotStuff的目标是使每个共识实例的正常路径消息复杂度为O(n)。

然而，使用单个验证者来聚合投票也意味着，其他验证者必须等待聚合器发送QC，因而需要更长的时间才能了解结果。因此，基于聚合器的协议，如HotStuff和Jolteon，基本上将投票阶段分为两个步骤。所以虽然上图中的Leader 3能够在Leader 1提出B1后4δ内完成最终确认，但其余验证者必须再等待δ来完成相同的操作。

综上所述，Jolteon在其正常路径中实现了以下几点：

区块最终确认延迟 (Block Finalization Latency): Jolteon在5δ内确认一个区块;
区块间隔 (Block Period): Jolteon每2δ产生一个区块;
通信复杂度 (Communication Complexity): Jolteon验证者必须发送O(n)条消息才能就某一区块达成共识。

Chained Moonshot

Moonshot 应运而生。Moonshot协议使用名为Optimistic Proposal的新优化，进一步提升了Chained HotStuff 及其衍生协议的并发性。这项技术听起来很简单: Moonshot 的领导者不再等待前一区块提出的 QC，而是一旦收到区块就立即创建自己的提案。这使得协议在其正常路径期间每δ 就能启动一个新的共识实例，而这正是基于区块链的 SMR 协议的最佳区块周期。

Chained Moonshot 是 Moonshot 的一种变体，与 Jolteon类似，它实现了 Chained HotStuff 的 QC 链接。不过，它放弃了投票聚合器的方法，而是更倾向于 Tendermint 和其他类似PBFT协议的广播模型，以获得更低的区块最终确认延迟。现在我们来看一下其正常路径如何运作:

步骤 1: 与之前一样，第一个领导者广播一个新的区块B1;
步骤 2: 与 Tendermint 类似，验证者广播他们对B1的投票。但是，下一轮的领导者同时提出B2，并通过在B2中包含称为B1摘要的简明摘要 (例如B1的加密哈希) 来引用B1作为其父块。在收到足够多B1的投票以后，验证者锁定B1并进入下一轮;
步骤 3: 随后，重复步骤 2，第三个领导者在验证者广播他们对B2的投票时提出B3,不过，在锁定B2的 QC 后，验证者还会再提交 B1。

重要的是，只有在正常路径期间提议的区块已经锁定在其父块的情况下，Chained Moonshot 的验证者才会对其进行投票。此外，Chained Moonshot 的验证者只有在r+1轮 (即允许其为区块投票的一轮) 和进入回退路径之前，监控到该区块的 QC，才允许锁定为r轮提议的区块。这与双链提交规则 (已修改为要求B′包含B的摘要而不是B的 QC) 相结合，确保了正常路径的安全性。

与简化版 Tendermint 不同，Chained Moonshot 的回退路径确保验证者不需要重新广播他们收到的每条消息才能获得活性属性。不过，它的投票广播仍使协议在正常路径中每个决策的通信复杂度达到 O(n2)条消息。综上，Chained Moonshot 在正常运行下表现出以下特点：

区块最终确认延迟: Chained Moonshot 在3δ内完成区块的确认；
区块吞吐量 (Block Throughput): Chained Moonshot 每δ产生一个区块；
通信复杂度: Chained Moonshot 验证者必须发送O(n2) 条消息才能就某个区块达成共识。

下图总结了 Tendermint、Jolteon 和 Chained Moonshot 的正常路径的区别:

得到显著提升的性能

我们应用了Chained Moonshot，并通过修改 Facebook Research 提供的Narwhal-HotStuff 应用中的 Jolteon 来检验我们的理论预测。我们将这个应用与现有的 Jolteon 应用进行了比较，并将两者从 Narwhal 分离，以确保我们的测试结果不受内存池活动的影响。

我们考虑了两个指标: 区块吞吐量和区块最终确认延迟。前者通过计算至少有2f+1个验证者提交的区块数量来衡量，而后者则是指从领导者创建区块到第2f+1个验证者提交区块之间的时间。

我们测试的网络规模从 10 个节点到 200 个节点不等，区块大小从 1.8kB 到 18MB 不等。我们在 AWS的 m5.xlarge 实例上运行了每个基准测试。这些实例分布在全球多个区域，对于 10个和 50 个节点的测试，使用了 5 个区域，对于 100 和 200 个节点的测试，使用了 20 个区域。我们每个配置运行了 5 分钟，每个配置重复运行了三次，以帮助消除异常值。我们观察到以下结果。

与我们的理论分析相符，在所有配置中，Chained Moonshot在五分钟内最终确认的区块数量比 Jolteon 多。有趣的是，Chained Moonshot 在吞吐量上的相对提升通常随着网络规模的增加而增加，这表明在测试的配置中，与聚合投票相比，通过广播投票所带来的通信开支可以忽略不计。

不过，Chained Moonshot 对吞吐量的提升不如预期。将其理论区块周期与 Jolteon 的理论区块周期进行比较，得出的预期提升为100%。但在现实所有配置下，它的吞吐量最低提高了 24.5%，最高提高了 78.4%，平均提高了 54.9%，皆没有高于预期值。

尽管如此，我们用来模拟区块周期的分析模型并不精确: 它既没有考虑投票和区块的相对大小，也没有考虑网络的大小，而这两者都会影响实际的消息延迟。我们将在未来的文章中进一步阐述这一点，届时我们将介绍根据更精确的分析模型而开发的另一种Moonshot变体。

相比之下，Chained Moonshot 在提交延迟方面的改进甚至优于将其理论区块最终确认延迟与 Jolteon 的延迟进行比较而得出的 40% 的下降幅度。在所有配置中，Chained Moonshot 的改进幅度最小为 22.8%，最大为 58.7%，平均为 41.1%。

将这两个指标的结果结合起来，可以得出下图。该图显示了两个协议的吞吐量 (以每秒完成的字节数为单位)，与它们的平均区块最终确认延迟之间的关系。为了强调在较小的负载大小下性能的相对差异，两个坐标轴都是对数刻度。除了 10 个节点的图，图表上的每个点对应于前两个图表 x 轴上的一个负载大小，负载大小从 x 轴上的零点开始沿线递增。我们在10 个节点的网络测试集中额外增加了180MB的负载，以帮助阐明趋势。

如图所示，100 和 200 个节点网络的曲线在负载越大的情况下越向后弯曲。发生反转的点标志着相关协议的饱和点 (saturation point)，在此之后，增加负载大小只会导致性能下降。

总体而言，该图清楚地表明，在所有配置中，Chained Moonshot的吞吐量更高，延迟更低。此外，对于达到饱和的网络规模，它还能产生更高的饱和点。您可以在我们的技术白皮书中找到有关 Chained Moonshot 和 Jolteon 实验更详细的讨论。

写在最后

综上，Chained Moonshot是对Jolteon这种先进区块链共识协议的新型改进。它将投票广播和提案渠道相结合，实现了低延迟和高吞吐量，尤其是在网络条件有利的情况下。本文简要介绍了该协议的许多细节，包括它在拜占庭故障下的表现。Moonshot 还有其他变体 (其中一些变体仍在开发中)，我们将在未来的文章中进行讨论。

Leave a Reply Cancel Reply