详解Kaspa共识模型DAG-KNIGHT：如何在部分同步模型中实现1/2的容错率

原文来源：KasMedia

原文标题：THE MASTER OF TIME: HOW DAGKNIGHT SOLVES AN IMPOSSIBILITY RESULT UNACHIEVABLE BY BITCOIN, ETHEREUM AND CLASSICAL BFT MODELS

原文作者：Nicholas Sismil，前 Binance.US 上币部门研究负责人

观点：在区块链和分布式系统理论中存在着一个广为人知的一个著名不可能结论：在一个不完全同步的通信模型下，任何协议或网络都无法实现 1/2 的容错率。这是比特币、以太坊和经典 BFT 模型等其他任何协议都无法解决的问题，但是 Kaspa 将实现的共识模型 DAG-KNIGHT 可以。解决这一问题的关键在于在模拟现实世界的进程中实现一种极强的网络正确性（例如在面对延迟和其它干扰因素时），从而成为网络中的时间之主。

在本文中，我将主要探讨这些问题：

1. 分布式系统的本质；

2. 如何平衡正确性、时效性和容错率？；

3. 最终性与动态可用性（即概率最终性 vs. 绝对最终性）；

4. 比特币、经典 BFT 模型和以太坊在这些属性上的表现及其不足；

5. DAG-KNIGHT 如何突破这一不可能性结果，解决其他所有协议的不足；

6. 最后总结 DAG-KNIGHT 如何成为时间的主宰，以及这对分布式系统理论意味着什么。

分布式系统的定义

分布式系统有多种定义。Leslie Lamport 在 1987 年的一次交流是这样描述的：在一个分布式的系统中，发生在一台你甚至都不知道存在于系统中的计算机上的故障都可能导致你自己的计算机无法使用。Imran Bashir 在他的《区块链共识》一书中则将分布式系统定义为通过消息传递网络为以实现共同目标自主协同工作的匿名计算机的集合。

从根本上说，分布式系统的目标是使其所有的组成部分就系统的整体状态达成一致——即达到共识。尽管 Facebook、谷歌、推特、亚马逊等是中心化管理的企业，但他们采用的都是分布式系统（还有万维网）。在本文中，我将讨论由区块链、分布式账本和区块有向无环图（blockDAG）构成的另外一种分布式系统的历史发展过程。

首先，我们需要了解分布式系统的几个核心属性：正确性、时效性和系统内部容错率。

分布式系统中的正确性、时效性和容错性

Leslie Lamport 在《证明多处理程序正确性》中定义了分布式系统正确性的概念。他认为，一个想要具备正确性的分布式系统必须同时具备活跃度和安全性。安全性是指无法撤销已做出的决定，而活跃度是指无法无限期地延迟做出决定。换句话说，安全性保证了不同的诚实节点永远不会做出不同的决定，而活跃度则保证了每个诚实节点都将最终做出一个决定。

我们将看到，一些分布式系统更倾向于保证活跃度，而另一些则更倾向于保证安全性。

时效性和容错性

时效性反映了分布式系统中的通讯行为模型。通讯模型包括关于网络延迟和处理器延迟及速度的设定。这些设定本质上决定了网络对抗者在系统中能够控制消息延迟的程度。换句话说，通信模型定义了网络对抗者干扰通讯的能力极限。

根据同步方式不同，有三种主要的通讯模型：（完全）同步、异步和部分同步。每种模型决定了系统的容错率，即通信模型决定了协议是否能够抵御 1/3 或 1/2 的错误率。

（完全）同步模型

在同步模型中，存在一个预先已知的最大消息延迟界限∆，所有消息必须在这个时间内送达，网络中的所有参与者都知道消息送达所需的时间。因此，对手最多只能延迟消息的送达时间至δ。举例而言，比特币采用同步模型，那么按照最长链规则操作，该规则遵循每个块的最大延迟 L，L 会不断更新并始终确保块到达的时间约为 10 分钟，即上限延迟∆为 10 分钟。

同步系统简单并能提供强大的正向结果。但它们过于严格，难以在不损害安全性的情况下有效模拟现实世界（如网络中断和意外长时间攻击）。例如，设置一个较长的延迟∆可以提供代表现实世界的强正结果，但会导致长时间超时和性能下降。相反，设置一个较短的延迟∆可以提高性能，但可能无法准确模拟现实世界，从而损害安全性。换句话说，如果网络参与者高估延迟，系统运行会比实际情况慢；反之，系统则不够安全。

此外，尝试在两者之间找到一个理想的平衡也并不容易。例如，如果发送者广播一条消息给两个接收者，一条消息在∆−ϵ后到达，另一条消息在∆+ϵ后到达，那么现实世界中的行为就会与模型设定所希望不同，这会损害系统的安全性。

尽管同步模型存在这些问题，它仍能达到 1/2 的最高容错界限。这是因为我们可以假设系统中的每个节点在固定时间内都能看到每一次投票，从而达成共识。具体来说，如果系统中有 n 个节点，其中 f 个是故障节点，我们希望至少有 f+ 1 个正确节点的消息能够超过 f 个故障节点的消息。一旦所有消息都收到，根据同步模型，这样的共识就能达成。

即如果：

n ≥ f+(f+ 1)

f ≤ (n-1)/2 

f < n/2 

那么最大的容错率达到½。

异步模型

异步模型试图通过不对网络延迟做任何假设来克服同步模型遇到的问题：即使正常运行的节点间也没有网络延迟的限制。这样有两个优点：首先，没有通讯时间限制，不同步（迟到的）消息就不会意外损害安全性；其次，由于没有固定的超时时间，节点就可以适应系统实际发生的延迟而仍保持活跃。

然而，这也带来了一些代价。Fischer、Lynch 和 Patterson 在其论文《带有一个故障进程的分布式一致不可能性》中提出了一个不可能性定理，在异步模型下，即使只存在一个故障节点，也无法保证一致性。换句话说，在异步模型中，只要一个错误的节点就足以使一致性变得不可能。

尽管如此，在随机算法下，在 t 秒内达到一致性是可能的，因为随着 t 的增长，一致性的概率会以指数方式接近 1 。因此，异步可能一致性算法只能达到 1/3 的容错率，而不是½。

此外，Eric Brewer 证明了一致性（安全性）、活跃度和分区容忍性（partition tolerance）这三者在异步分布式系统中不能同时存在。分区容忍性是指保证系统在网络在分区期间（某些节点之间的消息无法传递）仍能运行。因此，在异步系统中，存在一个三难困境——必须在安全性、活跃度和分区容忍性三者中选择其二，而不能全部兼得。

尽管该定理适用于异步模型系统，但网络分区仍然遵守异步假设并在所有时序模型中都会出现。因此，无论使用何种模型，系统在网络分区期间必须要么侧重活跃度，要么侧重安全性。

部分同步模型

系统有两种方式实现部分同步。第一种方式是，当系统正常运行时采用同步模型，在发生故障（如网络故障或攻击）时切换到异步模型。这种方式假设存在一个观测全局网络的时钟，并且参数∆指定了同步阶段消息可能发生的最大延迟。然而在异步阶段，参数∆不起作用，全局稳定时间（GST）决定了通信模型从同步切换到异步的时间点。这种版本称为 GST 版本。

第二种方式是假设消息传递没有已知的边界，而是存在一个未知的有限上限δ，这个上限可以由网络对抗者选择。在这种版本中，不存在 GST，也没有异步和同步阶段之间的切换。相反，消息将始终在∆时间步内传递，就像在同步模型中一样。

特别值得一提的是，无论哪种部分同步模型都具有 1/3 的容错率。正如 Dwork、Lynch 和 Stock 的工作中正式证明的不可能性结果那样，部分同步模型不能实现 1/2 的容错率。

最终性和动态可用性

历史上协议分为两类：基于最长链的协议和经典 BFT 共识协议。前者采用同步模型，遵循中本聪共识，即最长链规则：当链之间存在分歧时，选择最长的链。后者采用部分同步模型，基于状态机复制进行操作，随机选择验证者来提议区块，并通过多轮投票决定是否将区块纳入链中。每轮投票中，所有诚实且在线的验证者会对特定区块进行表决。

与基于最长链的协议不同，BFT 共识协议对区块的生成不依赖于链的长度或大小。BFT 共识偏向安全性而非活跃度，并提供绝对最终性，即系统内做出的决定永远不会被撤销。然而，由于偏重安全性，经典 BFT 模型无法实现动态可用性。经典 BFT 共识模型包括 Tendermint、PBFT 和 HotStuff 模型。

另一方面，基于最长链的协议（包括比特币和其泛化版本 GHOST）无法实现绝对最终性，而是通过动态可用性来达到概率最终性。动态可用性允许节点在任何时间加入或离开系统，而不影响系统的安全性。因此，动态可用性体现了真正的无许可性——节点不会因停机或技术故障而受到惩罚。此外，在网络分区或攻击期间，即使参与度较低，动态可用协议仍能做出决定。

许多人认为基于最长链的协议偏重活跃度而非安全性，但这并不完全正确。这一点非常重要。在通过概率实现活跃度的模型中，活跃度和安全性的区分是人为且具有误导性的，因为在概率上实现活跃度的模型中，安全性和活跃度是相互依存的。

人们可能会认为绝对最终性优于概率最终性，但情况并非如此，因为每种模型在处理分区问题时有所不同。在经典 BFT 共识系统中，如果在分区期间参与度过低，可能达不到规定需要的人数，从而无法完成所需的投票，导致区块链停滞。然而，即使活跃参与者数量减少到一个，只要始终存在诚实的多数，基于最长链的系统在分区期间就不会停止运行。相反，在这种情况下，账本的网络输出仍会继续增加，并具备自动纠错的能力：即使节点在最初存在分歧，网络最终也将收敛并达成共识。这种纠错能力与网络安全性的强弱有关。

正如 Neu 等人所示，在相同环境下模拟经典 BFT 模型和最长链模型时，在动态参与且网络分区的情况下，最长链协议的账本网络输出总是持续增长，而经典 BFT 协议的最终性在低参与度或分区期间会停滞。

因此，虽然经典 BFT 共识模型提供了安全性和绝对最终性，但其代价是网络中断时无法自愈或恢复。此外，这也牺牲了系统无需许可（permissionless）的特点，导致系统中心化。例如，一些 BFT 协议要求节点必须保持在线，否则将受到惩罚。相当一部分类似的规则毫无疑问是不符合去中心化网络的设计思想的。

以太坊：PoS 的广泛应用和陷阱

许多人希望摆脱 PoW 网络以节约电力和硬件成本，并实现更好的可扩展性。PoS 模型最初是作为中本聪共识的替代方案在链式区块链模型中应用。PoS 模型通过随机选择质押者，并按其权益比例赋予创建单个区块的权利，来模拟 PoW 的工作过程。

然而，许多人没有意识到这会导致两个主要问题：无利害攻击和长程攻击。

无利害攻击发生在两个矿工几乎同时创建区块时，网络必须根据最长链规则决定采用哪条竞争链。在 PoW 网络中，我们将选择具有最多工作量的最长链——即在经济上消耗了最多系统外部资源的链。而在 PoS 中，选择正确的链不需要外部资源，因此没有自然的机会成本。由于没有机会成本，质押者可以在每个链的版本上下注，导致系统的安全性崩溃。理性的质押者会扩展到他们看到的每条的可能的链上去以最大化回报。

长程攻击发生在对手通过贿赂获得过去验证者的密钥，重新编写区块链历史，即创建虚假的网络历史。

为了解决无利害攻击，Vitalik Buterin 提出了 Slasher 的概念：如果质押者在两个分叉上签署相同高度的区块，他们就会失去区块奖励。然而，Vlad Zamfir 和 Ethan Buchman 为 Slasher 添加了额外的功能——质押保证金。这样，明显违规的节点会被削减其质押保证金，而不是仅仅放弃部分利润，这是一种更大的惩罚。这些改进后来被纳入以太坊的 Gasper 共识模型，并证明了 ETH 作为 PoS 资产的价值仅通过强制质押保证金和削减惩罚来保障——如果不锁定 ETH，就没有能支持以太坊的经济价值。

换句话说，ETH 的价值不是通过工作量证明的无法伪造的成本性创造的，而是被强制维持的，这与我们今天的法币系统非常相似，因此无法作为硬通货运作。比特币则具有无法伪造的成本性，因为通过资本支出（如硬件矿机）和运营支出（如电力）来生产新的比特币需要花费大量成本。伪造比特币非常困难，因为伪造者需要重做之前所有的昂贵工作量证明，并且速度要超过网络中的所有持续工作量证明。

弗兰肯斯坦：以太坊的 Gasper

Gasper 旨在依靠 PoS 网络结合基于最长链规则模型的同步通信模型和经典 BFT 模型的部分同步通信模型的设计。前者通过 LMD GHOST（最新消息驱动的最贪婪最重的观察子树）实现，是一种最长链规则的泛化；后者通过 Casper FFG（友好的最终性小工具）实现。LMD GHOST 是 GHOST 的一个变种，是 Kaspa 网络的创建者 Sompolinsky 和 Zohar 在《比特币中高速交易处理的安全》中提出的包容性协议的一部分。在以太坊中，LMD GHOST 作为分叉选择规则运作，每个分叉处，验证者选择得到所有验证者最多支持（即收到最多最新消息）的链，而不是最长链。在 PoW 网络的 GHOST 模型中，支持指的是工作量最多的链。而在 LMD GHOST 中，支持指的是获得最多投票的链（参与者根据其质押 ETH 余额加权获得投票）。

以太坊还设立了查验区块节点以便引入问责机制，如果验证者违反系统规则则会被罚款，罚金将取决于具体的违规情况。Casper FFG 是 Vlad Zamfir 的论文《友好的小幽灵：一种正确构建的区块链共识协议》衍生产物。然而，以太坊决定将 Casper 作为最终性小工具实现，作为概率活跃度链顶层的额外安全层，即 LMD GHOST。因此，Casper FFG 在网络分区期间也能确保提议区块的安全性。然而，由于 Casper FFG 按照部分同步模型运作，只有当验证者集的总数中少于 1/3 故障/对抗性时，才能实现最终性，即其容错性为 1/3 。由于 Casper FFG 提供可问责的安全性，它本身并不存在一般意义上的、确定的活跃度，而是提供了一种新的、更弱形式的、概率性的活跃度。

正如 Vitalik 所说，“可信的活跃度意味着算法不应陷入无法最终确定任何事物的状态的拥堵。”

Gasper 还实施了弱主观检查点作为防范长程攻击的措施。在弱主观检查点之前的 Gasper 区块链历史无法被撤销，即如果节点接收到与检查点冲突的区块，它将拒绝该区块，防止长程攻击。弱主观性的一个问题是，新的或重新加入网络的节点必须信任和依赖其他节点以获得系统的正确更新状态，这与去中心化的目标相矛盾，即构建一个无需信任的系统。工作量证明则按照客观性运作，新节点可以独立得出与网络其他部分相同的结论，从而实现无需信任的系统。

因此，尽管以太坊的 Gasper 融合了同步性与部分同步性及活跃度与安全性，但这是以牺牲许多其他特性为代价的，主要源于对强制权益证明的追求。

PoS 带来的主要问题

首先，由于放弃实现中本聪共识，它用强制保证金取代了无法伪造的成本性，创造了一种弱经济价值形式。其次，它实施了削减惩罚，包括离线惩罚。尽管离线惩罚很小，可能只相当于错过奖励的机会成本，但动态可用性仍然有限。第三，弱主观性的查验节点在系统内默认了信任的存在。=这违背了区块链技术的初衷。

人为安全和活跃度区别带来的主要问题

第四，以太坊没有改进其分叉选择规则（例如 LMD GHOST），而是屈服于协议中错误的人为活跃度与安全性区分。也就是说，以太坊没有增强网络的自我修复能力，而是使用了经典 BFT 共识的工具 Casper FFG。

这导致了第五个问题，Casper FFG 只能实现 1/3 的容错率。虽然在部分同步模型中，这是最高的容错率，但它确实是一个限制。正如我们将看到的，DAG-KNIGHT 可以做得更好。

最后，Gasper 引入了高复杂度，这损害了基础层的安全性、不变性以及 ETH 作为货币的能力。这种对复杂性的无尽追求创造了一个“弗兰肯斯坦式”的系统。

总结：比特币、经典 BFT 和以太坊

比特币能够实现 1/2 的高容错性，但这是以牺牲对现实世界（如互联网延迟、网络中断和意外长时间攻击）的建模和可扩展性为代价的。因此，比特币不能成为有效的交换媒介，因为若降低其上限延迟以实现更快的交易速率，会损害其安全性和保障。

另一方面，经典 BFT 模型偏向安全性，牺牲了在网络分区或攻击期间的动态可用性和自我修复能力。此外，由于经典 BFT 模型依赖部分同步通信模型，它们只能实现 1/3 的容错性。

以太坊试图融合基于最长链模型和经典 BFT 模型的优点，但结果却是创造了一个不必要的怪物自毁式系统。

DAG-KNIGHT：时间之主

DAG-KNIGHT 在部分同步模型中实现了 1/2 的容错率。要知道，Cynthia Dwork、Dwork、Lynch 和 Stock 曾正式证明，在部分同步模型中，实现超过 1/3 的容错率是不可能的，Shi 和 Pass 在其论文《混合共识》中进一步形式化了这一点。现在，让我们解释 DAG-KNIGHT 是如何做到这一点的。

首先，需要了解 GHOST-DAG 的工作原理，以及 DAG-KNIGHT 如何在此基础上进行构建。相关信息可以在 Spectre、Phantom 和 GHOST-DAG 的子部分中找到。我在文章《如何解决区块链三难困境：BlockDAG 和中本聪共识的友谊》中详细描述了 GHOST-DAG 如何解决这一问题。

实现不可能：DAG-KNIGHT 和部分同步性

DAG-KNIGHT 通过最大限度地利用 PoW 解决了 Dwork 等人提出的不可能性结果。工作量证明将交易排序协议与最终性协议分离。共识模型决定了如何排序交易，例如比特币的最长链规则和 DAG-KNIGHT 的排序规则，并且这些规则是所有参与者（包括对抗性节点）以相同方式运行的规范算法。另一方面，交易的最终性是一个非约束性程序，每个用户根据其对系统的本地信仰进行配置或计算。

在比特币中，这一默认时间基于假设α，即攻击者拥有网络总哈希率的 10 ％，并且节点愿意承担<0.1 的风险ε。然而，节点也会依据其本地系统信仰作出相应的反应。例如，如果一个比特币节点认为恶意矿工拥有不到 1/3 的哈希率，那么该节点将比认为上限为 49 ％的节点更快确认交易，这允许 34 ％的攻击者损害前者，但无法损害后者。

另一个将排序与最终性分离的工作量证明的例子是 Spectre，这是一个部分同步 PoW 区块的 DAG 排序算法。在 Spectre 中，节点必须配置一个单独的参数来指定其延迟上限 d，这个参数是不为系统其他部分所知的。此外，每个节点对其选择的 d 负责，过于不准确的选择可能会损害它们。例如，如果一个节点高估了 d，它无法识别不可逆交易；如果一个节点低估了 d，它会过早接受交易。然而，Spectre 无法实现高活跃度。

DAG-KNIGHT 利用工作量证明这一特性，使其交易排序规则对延迟无关紧要，而交易最终性取决于用户本地配置的延迟上限。因此，它在这种意义上是部分同步的。响应性是经典部分同步通信模型中的一个关键特征，根据协议共识模型如何响应延迟，有两种形式的响应性。一种强响应性来自于可以根据网络的可观察延迟确认交易的协议。另一种弱响应性是指协议在当前由网络对抗者造成的最大延迟下紧密运行。DAG-KNIGHT 按照后一种方式工作，因此能够绕过 Dwork 的不可能性结果。

正如 DAG-KNIGHT 论文所述：“在 KNIGHT 中，仅设置本地观察到的延迟上限是不够的，相反，该上限应反映攻击者可能造成的最大延迟。即使消息当前完全在 1 或 2 秒内传播，但如果攻击者可能破坏网络，使消息最多需要 30 秒通过，客户端应将 D 设置为 30 秒。”

虽然这似乎是一个限制，但实施弱响应性的能力创造了第一个在部分同步性下实现 1/2 容错率的共识模型，打破了不可能的结果。

打破不可能的结果：这意味着什么？

作为中本聪共识最长链规则的泛化，DAG-KNIGHT 实现了动态可用性、概率最终性和自我修复能力。然而，DAG-KNIGHT 相较于比特币能更快地实现最终性，因此也能更快地实现安全性。也就是说，重组的概率更快地趋向于零，从而更快地达到最终性。这意味着每秒可以生成 100 个区块，矿工获得补贴和无转换费用区块奖励的速度也更快，从而变成彻底的去中心化系统，使单独挖矿变得更有效率。

与经典 BFT 模型不同，DAG-KNIGHT 在网络分区期间不会停止运行，同时实现了可能的最高容错率 1/2 ，而 BFT 模型只能实现 1/3 。此外，与比特币不同，DAG-KNIGHT 可以模拟现实世界的异步性，避免长时间超时和性能下降，同时确保在低延迟界限下的安全性。因此，比特币无法成为理想的交换媒介，因为降低其上限延迟以增加交易速度会损害安全性和保障。而 DAG-KNIGHT 则可以创造第一个无状态未来世界的储备货币。

此外，DAG-KNIGHT 作为一个非双重共识模型实现了这一框架，而不是像以太坊的 Casper FFG 那样不断添加更多层。DAG-KNIGHT 仅仅改进了其基础层的分叉选择规则，从而实现了简化，这是远离复杂的以太坊式“弗兰肯斯坦”怪物的一大进步。简化允许更快和更安全的发展，并且 DAG-KNIGHT 通过强经济价值实现了简化：a. 基于无法伪造的工作量证明的资产；b. 强客观性，即消除以太坊弱主观性模型中的信任问题。

最后，DAG-KNIGHT 进一步去中心化了 PoW，因为α、ε和δ是由节点本地决定和确定的，而不是像比特币的上限延迟那样的中央规则，间接解决了 Friedrich Hayek 所谓的地方知识问题。每个人都有一些独特的信息优势，只有在决策依赖于这些信息时，才能得到最有效的利用。因此，个体（或在我们的情况下，节点）根据其特定时间和地点的情况拥有独特的信息，计划（特别是经济计划，对于 Hayek 来说，但这也可以涉及α、ε和δ）最好由个体参与者以分布式的方式进行，因为中心化的计划缺乏这些信息，无法准确地考虑到每一个个体的知识。

结论：Kaspa 的未来共识模型 DAG-KNIGHT 解决了比特币、以太坊及经典 BFT 模型无法实现的不可能性结果，作为一个部分同步模型，具有可能的最高容错界限。DAGKNIGHT 提供了比任何其他协议更强的安全性、可扩展性和去中心化。没有其他协议正式实现过这样的壮举，也许也没有其他协议能再做到。因此，Kaspa 是名副其实的时间之主。