V神发布「99%容错共识算法」指南，快看！

V神原名：Vitalik，这位在区块链领域被称之为“神”的年轻黑客自从创建了以太坊后，他的言论就受到了区块链领域人士的关注，作为技术出身的Vitalik在区块链领域有着绝对的权威。

V神在博客上发布了一篇《一个99%容错共识的指南》引起区块链领域的轰动。要知道，我们熟知的51%攻击是最大的容错率（50%），也就是说全网只要恶意节点超过50%就可以发起“51%攻击”。

V神发布的 “99%容错共识算法“又是怎么回事呢？

V神的博客译文：（省去了前面铺垫）

......

Leslie Lamport 写于 1982 年的著名论文《拜占庭将军问题》描述了该算法。下面是我尝试用简化的形式描述和重构该算法。

假设有N个节点，我们分别用0，……，N-1 来标识，并且在网络延迟加上时钟差异有个已知的界限 D（比如，D = 8 秒）。每个节点具有在时间T（恶意节点当然能够早于或晚于时间 T）发布一个值的能力。所有节点等待 (N - 1) * D 秒，运行以下过程。定义 x : i 是“节点i签署的值 x”，x : i : j 是“节点i签署的值 x，并且由节点 j签署该值和签名”，等等。在第一个阶段发布的提议以 v : i的形式出现，代表某些 v和 i，包含提出它的节点的签名。

如果验证节点i收到一些消息 v : i[1] : … : i[k]，其中 i[k] 是一个索引列表，这些索引已经（顺序）签署了消息（只是v 本身将计为 k = 0，并且v:i 计为 k = 1），然后，验证器检查（i）时间是否小于 T + K * D，以及（ii）它们是否还没看到一个有效的包含 v 的消息。如果这两个验证都通过，那么，它们就发布 v : i[1] : … : i[k] : i。

在 T + (N-1) * D时刻，节点停止侦听，它们使用一些“选择”功能从所有它们已经看到的有效消息中选择一个值（比如，它们取最高的）。然后，它们决定这个值。

节点 1（红色）是恶意节点，而节点 0 和节点 2（灰色）是诚实节点。一开始，这两个诚实节点给出它们的提议 y 和 x，攻击者晚提出 w 和 z，w 准时到达节点 0，但是没能准时到达节点 2，z 既没有准时到达节点 0，也没有准时到达节点 2。在 T + D 时刻，节点 0 和节点 2 重新广播了它们看到但还没有广播过的所有值，并在上面添加了它们的签名（x 和 w 用于节点 0，y 用于节点 2）。两个诚实节点都看到了{x，y，w}，然后，它们可以使用一些标准选择函数（即，按字母顺序，最高的：y）。

现在，我们来探究一下这个为什么可行。我们需要证明的是，如果一个诚实节点已经看到一个特定值（有效的），然后，其他各个诚实节点也看到了该值（如果我们能证明这个，那么我们就知道所有的诚实节点在运行同样的选择函数，因此它们会输出相同的值）。假设任意一个诚实节点收到消息v : i[1] : … : i[k]，它们认为有效（即，它在T + k * D时刻前到达）。 假设 x 是单个其他诚实节点的索引。那么，x 要么是{i[1] … i[k]}的一部分，要么不是。

在第一种情况下（设 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受两倍网络时延加上时钟差异的约束。然后，我们对观察者施加不同的超时：观察者在 T + (k – 0.5) * D 时刻前收到 v : i[1] : … : i[k]。现在，假设观察者看到一个消息并接收它。它们将能够在T + k * D时刻前广播给一个诚实节点，并且诚实节点会发出附有其签名的消息，该消息将在 T + (k + 0.5) * D时刻前达到所有其他观察者，那么，具有 k+1个签名的消息超时。

改造其它共识算法

假设我们有一些其他共识算法（例如，PBFT，Casper FFG，基于链的 PoS），这些算法的输出可以被偶尔上线的观察者看到（我们称之为阈值相关共识算法，而不是上面提到的算法，那些被我们称为延迟相关共识算法）。假设阈值相关共识算法持续运行，其模式是不断地“最终化”新块到区块链上（即，每个最终化的值指向一些作为“父节点”的之前最终化的值，如果有个指针顺序 A -> … -> B，我们称 A 是 B 的后代）。我们可以把延时相关算法改造到这个结构上，让总是在线的观察者能够在检查点上获得一种“强大的终结性”，具有大约 95% 的容错率（通过添加更多验证器和要求该过程花费更长的时间，您可以任意地推动这个值接近 100%）。

每当时间到达 4096 秒的倍数时，我们运行延迟相关算法，选择 512 个随机节点参与到该算法。一个有效的提议是由阈值相关算法最终确定的任何有效链的值。如果一个节点在T + k * D (D = 8 秒)时刻前看到一些最终确定具有k 个签名的值，它就把该链放到其已知链集合，并在添加了它自己的签名后重新广播它，观察者像以前一样使用T + (k – 0.5) * D的阈值。

最后用到的“选择”函数很简单：

最终确定的值，如果不是那些在上一轮中已经同意成为最终确定的值的后代，将被忽略。最终确定的无效值被忽略。要在两个最终确定的值之间做出选择，就选择具有更低哈希值的那个。如果 5% 的验证器是诚实的，那么只有大约一万亿分之一的概率随机选到的 512 个节点没有一个是诚实节点，并且只要网络延迟加上时钟差异小于 D/2，上述算法就有用，就算因为延时相关算法的缺省容错率被破坏而呈现多个冲突的最终确定的值，也能正确地协调在某些单独最终确定的值上的节点。

如果满足阈值相关共识算法的默认容错率（通常是 50%，或是 67% 诚实），那么阈值相关共识算法将不会最终确定任何新的检查点，或者，它将最终确定那些相互兼容的新检查点（即，一系列把前一个点作为父节点的检查点），因此，即使网络延迟超过 D/2（或 D），作为结果，参与延迟相关算法的节点不同意它们接受的值，它们接受的的值仍然被保证是同一个链上的一部分，因此，没有实际的分歧。一旦在未来某一轮，延迟恢复正常，那么，延迟相关共识将回到“同步”状态。

如果阈值相关和延迟相关共识算法的假设同时（或在连续的轮次中）被破坏，那么该算法可以崩溃。比如，假设在某一轮次，阈值相关共识算法最终确定 Z -> Y -> X，并且延迟相关共识算法在Y 和X 之间不一致，那么在下一轮次中，该阈值相关共识算法最终确定 X 的后代 W ，其中X不是 Y 的后代；在该延迟相关共识算法中，那些跟 Y 一致的节点将不接受W，但是，跟X 一致的节点会接受 W。无论如何，这是不可避免的，在拜占庭容错理论中，不存在超过 1/3 容错率的安全同步共识，这是一个众所周知的结果，因为即使允许同步假设，但是假设离线观察者不可能超过 1/2 容错。

丨V神博客原文丨

We’ve heard for a long time that it’s possible to achieve consensus with 50% fault tolerance in a synchronous network where messages broadcasted by any honest node are guaranteed to be received by all other honest nodes within some known time period (if an attacker has more than 50%, they can perform a “51% attack”, and there’s an analogue of this for any algorithm of this type). We’ve also heard for a long time that if you want to relax the synchrony assumption, and have an algorithm that’s “safe under asynchrony”, the maximum achievable fault tolerance drops to 33% (PBFT, Casper FFG, etc all fall into this category). But did you know that if you add even more assumptions (specifically, you require observers, ie. users that are not actively participating in the consensus but care about its output, to also be actively watching the consensus, and not just downloading its output after the fact), you can increase fault tolerance all the way to 99%?

This has in fact been known for a long time; Leslie Lamport’s famous 1982 paper “The Byzantine Generals Problem” (link here) contains a description of the algorithm. The following will be my attempt to describe and reformulate the algorithm in a simplified form.

Suppose that there are N consensus-participating nodes, and everyone agrees who these nodes are ahead of time (depending on context, they could have been selected by a trusted party or, if stronger decentralization is desired, by some proof of work or proof of stake scheme). We label these nodes 0....N-1. Suppose also that there is a known bound D on network latency plus clock disparity (eg. D = 8 seconds). Each node has the ability to publish a value at time T (a malicious node can of course propose values earlier or later than T). All nodes wait (N-1) * D seconds, running the following process. Define x : i as “the value x signed by node i”, x : i : j as “the value x signed by i, and that value and signature together signed by j”, etc. The proposals published in the first stage will be of the form v: i for some v and i, containing the signature of the node that proposed it.

If a validator i receives some message v : i[1] : ... : i[k], where i[1] ... i[k] is a list of indices that have (sequentially) signed the message already (just v by itself would count as k=0, and v:ias k=1), then the validator checks that (i) the time is less than T + k * D, and (ii) they have not yet seen a valid message containing v; if both checks pass, they publish v : i[1] : ... : i[k] : i.

At time T + (N-1) * D, nodes stop listening. At this point, there is a guarantee that honest nodes have all “validly seen” the same set of values.

Node 1 (red) is malicious, and nodes 0 and 2 (grey) are honest. At the start, the two honest nodes make their proposals y andx, and the attacker proposes both w and z late. w reaches node 0 on time but not node 2, and z reaches neither node on time. At time T + D, nodes 0 and 2 rebroadcast all values they've seen that they have not yet broadcasted, but add their signatures on (x and w for node 0, y for node 2). Both honest nodes saw {x, y, w}.

If the problem demands choosing one value, they can use some “choice” function to pick a single value out of the values they have seen (eg. they take the one with the lowest hash). The nodes can then agree on this value.

Now, let’s explore why this works. What we need to prove is that if one honest node has seen a particular value (validly), then every other honest node has also seen that value (and if we prove this, then we know that all honest nodes have seen the same set of values, and so if all honest nodes are running the same choice function, they will choose the same value). Suppose that any honest node receives a message v : i[1] : ... : i[k] that they perceive to be valid (ie. it arrives before time T + k * D). Suppose x is the index of a single other honest node. Either x is part of {i[1] ... i[k]} or it is not.

In the first case (say x = i[j] for this message), we know that the honest node x had already broadcasted that message, and they did so in response to a message with j-1 signatures that they received before time T + (j-1) * D, so they broadcast their message at that time, and so the message must have been received by all honest nodes before time T + j * D.In the second case, since the honest node sees the message before time T + k * D, then they will broadcast the message with their signature and guarantee that everyone, including x, will see it before time T + (k+1) * D.Notice that the algorithm uses the act of adding one’s own signature as a kind of “bump” on the timeout of a message, and it’s this ability that guarantees that if one honest node saw a message on time, they can ensure that everyone else sees the message on time as well, as the definition of “on time” increments by more than network latency with every added signature.

In the case where one node is honest, can we guarantee that passive observers (ie. non-consensus-participating nodes that care about knowing the outcome) can also see the outcome, even if we require them to be watching the process the whole time? With the scheme as written, there’s a problem. Suppose that a commander and some subset of k (malicious) validators produce a message v : i[1] : .... : i[k], and broadcast it directly to some “victims” just before time T + k * D. The victims see the message as being “on time”, but when they rebroadcast it, it only reaches all honest consensus-participating nodes after T + k * D, and so all honest consensus-participating nodes reject it.

But we can plug this hole. We require D to be a bound on two times network latency plus clock disparity. We then put a different timeout on observers: an observer accepts v : i[1] : .... : i[k] before time T + (k - 0.5) * D. Now, suppose an observer sees a message an accepts it. They will be able to broadcast it to an honest node before time T + k * D, and the honest node will issue the message with their signature attached, which will reach all other observers before time T + (k + 0.5) * D, the timeout for messages with k+1 signatures.

Retrofitting onto other consensus algorithms

The above could theoretically be used as a standalone consensus algorithm, and could even be used to run a proof-of-stake blockchain. The validator set of round N+1 of the consensus could itself be decided during round N of the consensus (eg. each round of a consensus could also accept “deposit” and “withdraw” transactions, which if accepted and correctly signed would add or remove validators into the next round). The main additional ingredient that would need to be added is a mechanism for deciding who is allowed to propose blocks (eg. each round could have one designated proposer). It could also be modified to be usable as a proof-of-work blockchain, by allowing consensus-participating nodes to “declare themselves” in real time by publishing a proof of work solution on top of their public key at th same time as signing a message with it.

However, the synchrony assumption is very strong, and so we would like to be able to work without it in the case where we don’t need more than 33% or 50% fault tolerance. There is a way to accomplish this. Suppose that we have some other consensus algorithm (eg. PBFT, Casper FFG, chain-based PoS) whose output can be seen by occasionally-online observers (we’ll call this the threshold-dependent consensus algorithm, as opposed to the algorithm above, which we’ll call the latency-dependent consensus algorithm). Suppose that the threshold-dependent consensus algorithm runs continuously, in a mode where it is constantly “finalizing” new blocks onto a chain (ie. each finalized value points to some previous finalized value as a “parent”; if there’s a sequence of pointers A -> ... -> B, we’ll call A a descendant of B).

We can retrofit the latency-dependent algorithm onto this structure, giving always-online observers access to a kind of “strong finality” on checkpoints, with fault tolerance ~95% (you can push this arbitrarily close to 100% by adding more validators and requiring the process to take longer).

Every time the time reaches some multiple of 4096 seconds, we run the latency-dependent algorithm, choosing 512 random nodes to participate in the algorithm. A valid proposal is any valid chain of values that were finalized by the threshold-dependent algorithm. If a node sees some finalized value before time T + k * D (D = 8 seconds) with k signatures, it accepts the chain into its set of known chains and rebroadcasts it with its own signature added; observers use a threshold of T + (k - 0.5) * D as before.

The “choice” function used at the end is simple:

Finalized values that are not descendants of what was already agreed to be a finalized value in the previous round are ignoredFinalized values that are invalid are ignoredTo choose between two valid finalized values, pick the one with the lower hashIf 5% of validators are honest, there is only a roughly 1 in 1 trillion chance that none of the 512 randomly selected nodes will be honest, and so as long as the network latency plus clock disparity is less than D/2the above algorithm will work, correctly coordinating nodes on some single finalized value, even if multiple conflicting finalized values are presented because the fault tolerance of the threshold-dependent algorithm is broken.

If the fault tolerance of the threshold-dependent consensus algorithm is met (usually 50% or 67% honest), then the threshold-dependent consensus algorithm will either not finalize any new checkpoints, or it will finalize new checkpoints that are compatible with each other (eg. a series of checkpoints where each points to the previous as a parent), so even if network latency exceeds D/2 (or even D), and as a result nodes participating in the latency-dependent algorithm disagree on which value they accept, the values they accept are still guaranteed to be part of the same chain and so there is no actual disagreement. Once latency recovers back to normal in some future round, the latency-dependent consensus will get back “in sync”.

If the assumptions of both the threshold-dependent and latency-dependent consensus algorithms are broken at the same time (or in consecutive rounds), then the algorithm can break down. For example, suppose in one round, the threshold-dependent consensus finalizes Z -> Y -> X and the latency-dependent consensus disagrees between Y and X, and in the next round the threshold-dependent consensus finalizes a descendant W of X which is not a descendant of Y; in the latency-dependent consensus, the nodes who agreed Y will not accept W, but the nodes that agreed X will. However, this is unavoidable; the impossibility of safe-under-asynchrony consensus with more than 1/3 fault tolerance is a well known result in Byzantine fault tolerance theory, as is the impossibility of more than 1/2 fault tolerance even allowing synchrony assumptions but assuming offline observers.

如果你是企业总裁/精英人士，请点击以下链接：

【区块链培训】IBC商学院高端总裁班（深圳站）开始报名啦！

“IBC商学院公众号，技术+智慧 赢未来

IBC商学院作为全球区块链技术交流平台，拥有区块链领域的博士、专家的强大师资力量。在这里你可以得到区块链最新资讯，学习区块链知识、区块链技术编程以及区块链项目投资，财富建立于智慧之上！