干货 | PoS 区块链共识算法中的同步和时序假设

与 Alexis Gauba 合著。

所有区块链和加密货币都需要 共识 ，或者说，就系统中所有参与者的账本状态达成一致。然而，实现共识并非易事，使共识最难实现的一个原因是作为协议运行环境的底层网络。正如你在 这篇 （编者注：即文末超链接《区块链栈层》），关于区块链堆栈的文章中所看到的，区块链不仅仅只包含协议及其参与者。它还包括参与者之间的连接（网络信道本身），在互联网中运行。

不幸的是，互联网并不总能流畅地运行。一般情况下互联网都是非常缓慢的。有些时候则会完全停止工作。消息和信息在传输过程中可能会丢失、不会到达他们想要的目的地。如果参与者崩溃或者失去网络连接，他们会完全退出网络。

网络模型

不论是加密货币还是更传统的分布式系统使用的共识协议，在构建网络模型时都必须考虑这些潜在的错误信道。探讨传统的分布式系统和区块链共识的文献都必须定义节点相互通信的设置，称为 网络模型 。这指的是节点是如何在双向信道中通过发送消息进行通信的。在区块链共识协议中，这些节点形成了点对点网络，这意味着每条消息都会通过 gossip 协议 被广播到网络中的每个节点。

不同的协议基于它们的运行环境采用不同的网络模型。换句话说，一些协议被用来在不可靠网络中工作，这些网络会丢失消息，并且可能会导致消息延迟，如互联网。其他协议针对及其可靠的网络通道进行了优化，例如被许可的企业 内部网 。这些协议被假设会在不同的消息同步模型中运行。

由于交易、签名和区块在协议中传递，参与者之间的消息同步需要一些时间。如果消息可以被随意延迟甚至全部丢弃，共识协议就必须将这一点纳入考量范围。

鉴于大量精力和资金被用于研究区块链和加密货币的共识机制，研究现有的方案并探索其网络假设如何影响其现实可行性是非常重要的。

网络模型的类型

接下来我们将探讨一些主要的网络模型及其假设：

同步假设意味着对所有信息的延迟有一个已知上限。即所有信息都必然在某个可以预先确定的时间内被传达，并且网络中的所有参与者都知道消息需要传递多久。

假设我们有一个可预测的可靠网络。想象在我们的可靠网络中，所有消息都会在发出后 10 秒就送达目的地。这意味着如果某个参与者向另一个参与者发送消息，那么他们都知道对方最迟不到 10 秒后就能收到。

因此，在同步模型中，协议可以在不连续回合中以锁步（lockstep）的形式推进。该模型中的所有参与者都知道消息多久会分发完成（例如 10 秒上限）。在这种情况下，他们可以在决定同一时刻 T 发送消息时同步，然后等到 T +10秒，此时他们便知道网络中的所有消息都已经被发送和接收。这一过程构成一个回合然后再重复，因为参与者参考他们在 T +10时刻收到的新消息，然后发出将在 T +20时刻被接收的新消息。协议伴随这些不连续的回合得到推进。

虽然同步设置是最容易达成共识的，但有些人认为由于互联网的不可靠性，同步模型在实践中是不现实的。这是一个强有力的假设， 所有 消息都有一些到达目的地的最大延迟；如果同步假设被打破，协议就无法工作，那这样的协议显然不够健壮。因此，协议设计者通常希望网络假设可以更弱一些（即协议本身能应对更不利的情况），我们将在下面进行探讨。

半同步(Semi-synchrony)类似于全同步，因为存在预定的最大网络延迟。不同之处在于，在全同步的情况下，参与者确切地知道网络延迟有多长， 在半同步中，消息传递时间可以由随机变量建模，该随机变量的概率分布对于协议中的参与者来说是已知的 。进一步的分析，请看 这里 。

部分同步(Partially Synchronous)的设置，由 Cynthia Dwork , Nancy Lynch , 以及 Larry Stockmeyer 在 1988 年发布的论文 中首次进行了总结，实际上描述了两种不同的情形：

1. 第一种方案是网络延迟有上限， 但网络中的参与者不知道该上限的确切值 。也就是说，也许所有信息都能在 10 秒内传递完毕，但系统中的参与者并不知道这一点；在消息到达接收方之前，他们只知道上限可能会是两年。但参与者知道的是，所有消息最终都会到达接收方。
2. 第二种方案实经过一段特定的被称为全局标准时间（GST）的时间后，网络会实现全同步。在此之前，参与者不知道全同步即将到来，而且不会提前收到任何消息。

在这种设置下的共识协议往往比全同步下的协议更加健壮，但作为折衷，通常会更复杂。部分同步协议是对互联网情境的更加真实的代表，但仍不完美。因此，我们迎来共识协议的圣杯：全异步。

异步设置在达成共识方面的难度是最高的。在该设置中，没有最大网络延迟。 也就是说，消息可能需要无限长的时间才能到达他们想要的接收方那里 。

有许多著名的分布式系统结论说明了在异步假设下实现共识的难度有多高，例如 FLP 不可能 定理。直观地说，很容易理解这个难点。如果消息 可能永远 不会到达目的地，那么网络中的所有节点为了确保能够达成一致，该如何适当的通信呢。然而，这种设置的好处之一是它是互联网的完美抽象，并且以这种方式构建的协议构造得非常好而且健壮。

另一种思考同步的方式受比特币的启发。这种考虑网络时序的最新方式源于 Rafael Pass 和 Elaine Shi 教授的论文： 沉睡的共识 。比特币不需要许可，并且允许节点随意退出和重新加入网络。在传统文献中，这可能会被视为同步失败，因为节点脱离网络可能会与所有发出和接收的信息都无限延迟相似。

此外，在它们最新的文章 重新思考高扩展共识 中，Pass 和 Shi 证明，中本聪共识（如比特币）协议为了保持其安全性，区块间隔必须设置为比网络最大延迟还要大的常量。

随着新的共识模型得到开发，每个共识模型都不得不对各自的网络模型做出相应的决定，时刻将 安全性和活跃度 放在首位，这个理念由 Leslie Lamp 第一次提出。分布式系统的 安全性 要求“不会发生不好（坏）的事情”，并且不同的协议可以指定它们希望避免的无用行为。在区块链设置中的 活跃度 ，根据 Pass 和 Shi 所描述的，指“由诚实用户提交的有效交易能够很快地合并到账本中”的属性。

（校对注：对这两种属性的理解非常重要。这是分布式系统属性的两个基本维度，只讨论一者而不讨论另一者一定是不完整的；分析共识算法，我们要问的是：它在什么条件下能实现什么属性？具体的示范见下文。）

PoS 共识的网络模型

在我们 可替代共识协议的元分析 中，我们考虑了某些主流 PoS 平台运行的网络模型。我们考虑了 Tendermint、Thunderella、Algorand、Dfinity、Ouroboros Genesis、Casper FFG，以及 Casper TFG。我们不妨看看这些协议如何看待它们置身其中的网络。

Tendermint

Tendermint 在选举（proposal，提议）阶段以部分同步运行，而且一旦区块被选举出，就会以异步回合运行。这是因为如果 1/3 或者更多的验证者变得无响应，网络就会停止，这意味着区块可能永远不会被验证，也不会被添加到区块链中。

Thunderella

Thunderella 具有异步优化的快速路径，并与区块链底层的同步配对；这些设计使得协议在终极意义上乃是同步模型。

Algorand

Algorand 提供基于部分同步的安全性，使得在异步周期后，网络必须在相当长的时间段内严格同步，才能在区块的 排序 上达成共识。

Dfinity

Dfinity 在同步模型中得到了形式化验证，但实际上是半同步，基于接收的消息触发超时机制实现安全性和活跃性。该协议不依赖于全局时间或假设同步时钟。

Ouroboros

Ouroboros Genesis 在半同步并且所有节点都能够访问全局时钟时可以保证系统的安全性，这意味着每个节点都可以用信号通知完成当前回合的时钟。一旦所有诚实节点都在当前回合中ping过时钟，时钟就会变动一次。任何节点也可以从时钟读取 - 该时钟的输出称为逻辑时间。

Casper

Casper FFG 没有明确说明协议运行的同步模型，但要求所有客户端都具有本地时钟，这些时钟是完全同步的，并且任何不一致都可以被视为已知的通信延迟的一部分，因此我们认为该协议采用同步模型。

Casper TFG (CBC) 提供异步安全性，因为区块不会由于未来事件的任意时序而被回滚，并且在给定一些同步假设的情况下提供活跃性。

在构建具有各种网络模型假设的协议时存在某些权衡，并且如上所述，不同的模型满足不同的需求。但是，在决定采用哪种协议而不是只考虑一个参数（在这种情况下是网络模型）时， 将这些协议作为一个整体进行检查是非常重要的。区块链系统在实际环境中运行的可行性（不受理论目标约束）是开发这些系统的关键考虑因素。

特别感谢 Aparna Krishnan 以及 Peter Lu 的讨论和反馈，为这篇文章做出了重要贡献。

原文链接: https://medium.com/mechanism-labs/synchrony-and-timing-assumptions-in-consensus-algorithms-used-in-proof-of-stake-blockchains-5356fb253459

作者:zk - Zubin Koticha

翻译&校对:刘亚辉 Dev & 阿剑