零点课堂 | V神详述：如何实现99%的容错共识？（1）

很长一段时间以来，我们一直听说在同步网络中,实现50%容错的共识是有可能的。在同步网络中，任何可信节点广播的消息都可以保证在某个已知时间段内被所有其它可信节点接收。

如果攻击者超过50%，他们就可以执行“51%攻击”，对于区块链上同类型的任何算法都有可能出现类似的情况。

我们也一直听过这样的说法：如果你想放松同步假设，并且拥有一种“异步下安全”的算法，最大可达到的容错率可下降到33% (PBFT、Casper FFG等都属于此类)。

然而，如果添加更多假设(具体来说，你不仅需要观察者来关注那些不积极参与共识但关心其输出的用户，也要积极地关注共识，而不仅仅是在结果出现后下载其输出)，这样可以把容错率一路提高到99%吗?

事实上，这一点 早已人尽皆知。莱斯利·兰伯特（Leslie Lamport）1982年在著名的谈及“拜占庭一般问题”的论文中包含了对算法的描述。下面我将尝试用简化的形式重新来描述和表述这个算法。

假设有N个参与共识的节点，每个人都提前同意这些节点代表谁(根据上下文，它们可以由可信方选择，或者如果需要更强的去中心化程度，可以通过一些工作证明或利害关系进行证明)。

我们把这些节点标记为0…N-1。另外，还假设网络延迟和时钟差异上有一个已知的限制D。（例如，D = 8秒)。每个节点都有能力在T时刻发布值(恶意节点当然可以早于T或晚于T地发布值)。

所有节点等待(N – 1)∙D秒，运行如下进程。定义x: i为“节点i签名的值x”，x: i: j为“节点i签名的值x，并且x与j一起签名”，等等。在第一阶段发表的提案将采用v的形式: i的形式为一些v和i，其中包括提出该提案的节点的签名。

如果一个验证器i收到一些消息v: i[1]:…: i[k]， 其中 i[1]:…:i[k]是已经按顺序对消息进行了签名的索引列表（只是v本身会算作k = 0,而v:i则为k = 1),那么验证程序检查(i)的时间将小于T + k∙D,同时他们尚未看到包含以下内容的有效消息;如果两项检查均通过了，则会发布v: i[1]:…: i[k]: i。

在T + (N – 1)∙D时，节点停止监听。此时，就可以保证所有的可信节点都“有效地看到了”相同的一组值。

如果问题要求选择一个值，则可以使用一些“选择”函数从他们看到的值中选择一个值（例如采用哈希值最低的值）。然后节点可以就该值达成共识。

现在，让我们来探究一下为什么这种方式有效。我们需要证明的是,如果一个诚实节点（有效地）看到了特定的值,然后其它的诚实节点也看到该值(如果我们证明了这一点,那么我们知道所有诚实节点都看到了同一组值,因此如果所有诚实节点都运行相同的选择功能,他们会选择相同的值)。

假设任何诚实节点收到一条消息v: i[1]:…i[k]，他们认为是有效的。在时间T + k∙D之前到达)，假设x是另一个诚实节点的索引。x要么是i[1]的一部分:…要么不是。

• 在第一种情况下(对于此消息，x=i[j]),我们知道诚实节点x已经广播该消息,他们这样做是为了响应他们在时间T+（j – 1）·D之前收到的带有j-1签名的消息。此时他们广播了他们的消息,那么所有诚实节点一定都会在时间T + j∙D前收到消息。
• 在第二种情况下，由于诚实节点在时间T + k∙D之前看到消息，那么它们就会用自己的签名传播消息，并保证包括x在内的所有人都会在时间T + (k + 1)∙D之前看到它。

注意，该算法使用添加自己签名的行为作为消息超时的一种“碰撞”。正是这种能力保证了一个诚实的节点如果及时看到了消息，那它们也可以确保其它所有节点也能及时看到消息，因为“准时”的定义增加的时间超过了每添加一个签名的网络延迟。

在一个节点是诚实的情况下，我们能否保证被动的观察者(比如关心结果的非共识参与节点)也可以看到结果。

按照计划，存在一个问题。假设一个指挥官和k(恶意)验证器的某个子集生成一条消息v: i[1]:…i[k]，并且在T + k∙D前广播给一些受害者，受害者认为消息是“准时”,但当他们转发时,消息只会在T + k∙D之后达到所有的已经协商一致的诚实节点,而所有协商一致的诚实节点将会拒绝它。

但我们可以堵住这个洞，提出一个新的约束：要求D在两倍的网络延迟加上时间差。然后我们给观察者一个不同的超时:观察者接受v: i[1]:…i[k]必须在 T + (k – 0.5)∙D之前。

现在，假设观察者看到一条消息并接受了它。他们能够在时间T + k∙D之前将其广播到一个诚实节点,并且诚实节点将发布带有签名的消息,该消息将在T + D (k + 0.5)之前到达所有其它观察者，同时带有k + 1个签名的消息将会超时。