万字雄文讲透中本聪共识的经典魅力

中本聪共识是一项真正的创新，它让研究人员、科学家、开发者和工程师在共识协议研究中不断开天辟地。前 Coinbase、a16z、高盛的区块链工程师 Preethi Kasireddy 通过万字雄文向你讲述传统共识算法和中本聪共识算法的不同。对于分布式计算而言，这是一个漫长而曲折的研究和独创性之旅。希望这篇文章能够有助于你对这个领域有更多的了解。

原文标题：《为何说比特币是重大创新？谈传统分布式共识 VS 中本聪共识》
作者：Preethi Kasireddy，区块链真伪验证平台 TruStory 创始人兼首席执行官，曾供职于高盛、a16z、Coinbase
翻译：洒脱喜

译者前言：我们知道，比特币等区块链是分布式系统的一个子集，但它和传统分布式账本是有差异的，那这些差异在于哪里呢？为什么我们说比特币是一项重大创新？来自前 Coinbase、a16z、高盛的区块链工程师 Preethi Kasireddy 将在这篇文章中给出她的答案。

以下为译文：

你知道分布式系统是如何工作的吗？

这可能是一个很难学习的话题，主要是因为围绕它的知识是很分散的 .....

在自我学习分布式计算这个课题之前，我多次趴到了桌上，但经过多次考验和磨难，我终于准备好向您解释分布式系统的基础知识。

我还想讨论区块链技术对该领域的深远影响。区块链迫使工程师和科学家们重新审视并质疑分布式计算中根深蒂固的范式。也许没有其它技术能够比区块链更快地促进这一研究领域的进展。

区块链是一种新型的分布式系统。它的出现始于比特币，并从此在分布式计算领域产生了持久的影响。因此，如果你想真正了解区块链的工作原理，那么掌握分布式系统的原理是至关重要的。

不幸的是，很多关于分布式计算的文献，要么是难以理解的，要么分散在太多的学术论文当中。而让问题变得更复杂的是，当前存在着数百种架构，而所有架构都满足不同的需求。因此，将其归结为一篇可理解的文章，足以称得上是一件壮举。

因为这个领域很广，我不得不仔细选择要覆盖的内容。我还必须进行概括，以掩盖一些复杂性。请注意，我的目标不是让你成为该领域的专家。相反，我只是想让你了解一些知识，开启分布式系统和共识基础知识的旅程。

阅读完这篇文章之后，您将更深入地了解到以下这些内容：

1. 分布式系统是什么？
2. 分布式系统的属性；
3. 在分布式系统达成共识是什么意思？
4. 理解基础共识算法（例如 DLS 和 PBFT）；
5. 为什么中本聪共识是一项重大创新？

我希望你准备好了这次学习！

什么是分布式系统？

分布式系统涉及了一组不同的进程（例如，计算机），将消息在彼此之间进行传递，并协调以实现共同的目标（即，解决计算问题）。

简而言之，分布式系统是一组共同实现统一目标的计算机。虽然这些进程是分开的，但系统对终端用户而言只是一台计算机。

正如我所提到的，分布式系统存在着数百种架构。例如，单个计算机也可以被视为分布式系统；中央控制单元、存储器单元和输入-输出通道，是协作完成一个目标的单独进程。

举飞机的例子，它们的共同努力是让你从 A 点到 B 点：

来源：https://www.weetech.de/en/news-info/tester-abc/distributed-system-1

在这篇文章中，我们将关注分布式系统，其中进程是指空间分离的计算机。

注意：我可能会把「节点」、「对等节点」、「计算机」或「组件」这些术语与「进程」互换使用。对于本文而言，它们都意味着相同的事情。同样地，我可能会使用「网络」和「系统」这两个可互换的术语。

分布式系统的属性

每个分布式系统都有一组特定的特征，这些包括：

A）并发

系统中的进程同时运行，这意味着同时会发生多个事件。换句话说，网络中的每台计算机与网络中的其它计算机，会同时独立地执行事件。

而这就需要协调。

Lamport, L (1978)：分布式系统中的时间、时钟和事件排序

B）缺乏全局时钟

对于同时运行的计算机集合系统，我们需要某种方法来确定事件的顺序。但是，在分布式计算机系统中，有时不可能明确两起事件中的哪起事件是先发生的，因为计算机在空间上是分开的。换句话说，没有一个全局时钟来确定网络中所有计算机发生的事件序列。

在《分布式系统中事件的时间、时钟和顺序》这篇论文当中，Leslie Lamport 展示了如何通过记住以下因素来推断出一个事件是否发生在另一个事件之前：

1）消息是在它们被收到之前发送的； 2）每台计算机都有事件的序列；

通过确定哪个事件是发生在另一个事件之前的，我们可以获得系统中事件的部分排序。

Lamport 的论文描述了一种算法，该算法要求每台计算机都能够「听到」其它每台计算机。

通过这种方式，事件就可以基于这种偏序进行完全排序。

但是，如果我们完全根据每台计算机正在听到的事件进行排序，则可能导致此顺序与外部用户（系统外部）所感知的顺序会不同。因此，该论文提到的算法仍然可允许异常行为。

最后，Lamport 讨论了如何通过使用正确同步的物理时钟来防止这种异常情况。

但是，等等，这里有一个巨大的警告：协调独立的时钟，是一个非常复杂的计算机科学问题。即使你最初准确地设置了一堆时钟，时钟也会在一段时间后开始出现差异。这是由「时钟漂移」问题造成的，这是一种时钟以稍不同速率计算时间的现象。

本质上，这篇论文证明了，事件的时间和顺序，是在空间上分离的分布式计算机系统的基本障碍。

C）组件的独立故障

理解分布式系统的一个关键部分，在于承认分布式系统中的组件会存在故障。这就是它被称为「容错分布式计算」的原因。

拥有一个没有故障的系统是不可能的。真实的系统会存在很多可能的缺陷或弱点，无论这是一个进程崩溃，消息丢失、扭曲或重复，还是网络分区延迟或出现丢弃消息的情况，甚至会出现进程完全失控，并根据一些恶意计划发送消息的情况。

这些失败大致可分为三类：

1.崩溃失败：组件在没有警告的情况下停止工作（例如，计算机崩溃）；
2.遗漏：组件发送了消息，但其它节点并没有收到消息（例如，消息丢失了）；
3.拜占庭：组件的表现是任意的。在受控环境下（例如 Google 或 Amazon 数据中心）出现这类故障是无关紧要的，其中可能没有什么恶意行为。相反，这类错误会发生在所谓的「对抗性环境」下。基本上，当一组分散的独立行动者充当网络中的节点时，这些行动者可能选择以「拜占庭」的方式行事。这意味着他们会恶意选择更改，阻止或不发送消息。

考虑到这些问题，我们的目标是设计一种协议，它可允许具有故障组件的系统，仍可实现共同目标，并提供有用的服务。

鉴于每个系统都会有故障，我们在构建分布式系统时必须做出的核心假设是，即使其部件偏离了正常行为，它也能继续存活，无论是否由于非恶意行为（崩溃失败或遗漏错误）还是因为恶意行为（即拜占庭故障）。

从广义上讲，制作分布式系统时，需考虑两种类型的模型：

1）简单的容错

在一个简单的容错系统中，我们假设系统的所有部分都执行以下两种操作之一：它们要么完全遵循协议，要么失败。这种类型的系统，应能够处理脱机或失败的节点。但它不必担心节点表现出随意或恶意行为。

2）拜占庭容错

简单的容错系统在不受控制的环境当中，并不是很有用。在一个去中心化的系统当中，节点是由独立的参与者控制的，它们之间在开放的、无需许可的互联网上进行通信，我们还需要为那些选择恶意或「拜占庭」行为的节点进行设计。因此，在拜占庭容错系统当中，我们假设节点是可以失败或恶意的。

3） BAR 容错

尽管大多数真实系统都被设计为能够承受拜占庭式的故障，但一些专家认为它过于笼统，并没有考虑到「理性」故障（其中节点可能出于自身利益的考虑而出现偏差行为）。换句话说，根据激励的情况，节点是可以诚实的，也可以是不诚实的。如果激励措施足够高，那么即使是大多数节点也可能会做不诚实的事。

更正式地讲，这被定义为 BAR 模型，它同时考虑了拜占庭和理性故障问题。 BAR 模型假设有三种类型的成员：

1.拜占庭：拜占庭节点是恶意的，它们试图搞砸你；
2.利他主义者：诚实的节点总是遵循协议。
3.理性节点：理性节点只有在他们认为合适时才会遵循协议。

D）消息传递

如上面所述，分布式系统中的计算机，通过一台或多台其他计算机之间的「消息传递」进行通信和协调。消息可使用任何消息传递协议进行传递，无论是 HTTP，RPC 还是为特定实现构建的自定义协议。

有两种类型的消息传递环境：

1）同步

在同步系统中，假设消息将在某个固定的已知时间内进行传递。

同步消息传递在概念上并没有那么复杂，因为用户拥有一个保证：当他们发送消息时，接收组件将在特定时间范围内获得它。这允许用户使用固定的时间上限来建模他们的协议，该上限是消息到达那里所需的时间。

但是，在真实的分布式系统中，这种类型的环境并不是那么实用，因为计算机可能会崩溃或脱机，并且可能会丢失、复制、延迟或无序接收消息。

2）异步

在异步消息传递系统中，假设网络可能无限延迟消息，复制消息或无序传递消息。换句话说，消息接收的时间长度，没有设置固定的上限。

在分布式系统达成共识是什么意思？

到目前为止，我们已经了解了分布式系统的以下属性：

1. 进程的并发性；
2. 缺乏全局时钟；
3. 存在故障进程；
4. 消息传递

接下来，我们将专注理解在分布式系统中实现「共识」意味着什么。但首先，重申我们之前提到的内容会是非常重要的：目前有数百种不同的用于分布式计算的硬件和软件架构。

其中最为常见的形式被称为复制状态机。

复制状态机

复制状态机是一种确定性状态机，很多计算机会对其进行复制，但它是作为单个状态机运行的。这些计算机中的任何一台都可能出现故障，但状态机仍是可运行的。

在复制状态机中，如果交易有效，则一组输入将导致系统状态转换到下一个状态。一笔交易是在一个数据库中进行的原子操作。这意味着操作要么完全完成，要么根本不发生。在复制状态机中维护的交易集被称为「交易日志」。

从一个有效状态转换到下一个有效状态的逻辑，被称为「状态转换逻辑」。

复制状态机是一组分布式计算机，它们都以相同的初始值开始。对于每个状态转换，每个进程决定下一个值。而达到「共识」，意味着所有计算机必须共同商定该值的输出。

反过来，这在系统中的每台计算机上都保持一致的交易日志（即「实现共同目标」）。

复制状态机必须不断地将新交易接收到该日志当中（即，「提供有用的服务」）。它必须这样做，尽管存在以下这些因素：

1. 有些计算机会出现故障；
2. 网络不可靠，消息可能会出现无法传递、延迟或出现故障的现象；
3. 没有全局时钟来帮助确定事件的顺序；

而这些，就是任何共识算法要去实现的基本目标。

确定了共识问题

如果算法满足以下条件，则我们说该算法达成了共识：

1. 协议：所有非故障节点决定相同的输出值；
2. 终止：所有非故障节点最终决定某些输出值；

（注意：不同的算法具有上述条件的不同变化。例如，有些人将协议属性划分为一致性和整体性。有些人则对有效性、完整性或效率会有概念，但是，没有必要在这篇文章当中探讨这样的细微差别。）

从广义上讲，共识算法通常假设系统中有三种类型的参与者：

1. 提议者（Proposers）；
2. 接受者（Acceptors）；
3. 学习者（Learners）；

提议者通常也被称为领导者或协调者。接受者是监听来自提议者的请求，并用值进行响应的进程。学习者是系统中的其它进程，它们学习决定的最终值。

通常，我们可以通过三个步骤定义共识算法：

第 1 步：选举

1. 进程选择单个领导者来做出决策。
2. 领导者提出下一个有效的输出值。

第 2 步：投票

无故障进程会监听领导者提出的值，对其进行验证，并将其作为下一个有效值。

第 3 步：决定

1. 无故障进程必须就单个正确的输出值达成共识。如果它收到满足某些标准阈值数量的相同投票，则进程将决定该值。
2. 否则，步骤重新开始。

重要的是，每个共识算法都会有不同：

1. 术语（例如轮次、阶段）
2. 如何处理投票的进程；
3. 如何确定最终值的标准（例如，有效性条件）；

尽管如此，如果我们可使用这个通用进程来构建一个算法，它可保证上面定义的一般条件，那我们就有了一个能够达成共识的分布式系统。

听起来，很简单，对吗？

FLP 不可能

… 并不是的。但是你很快就会了解到了！

回想一下，我们如何描述同步系统和异步系统之间的区别：

1. 同步环境是在固定时间范围内传递消息的地方；
2. 异步环境是消息的传递无保证的地方；

这种区别很重要。

在同步环境中达成共识是可能的，因为我们可假设消息传递所需的最长时间。因此，在这种类型的系统中，我们可允许系统中的不同节点轮流提出新的交易，轮询多数投票，如果在最长时限内未提供提议，则跳过任何节点。

但如前所述，假设我们在同步环境中操作，在受控环境（其消息延迟可预测）之外进行是不实际的，例如具有同步原子钟的数据中心。

实际上，大多数环境不允许我们进行同步假设，所以我们必须为异步环境而进行设计。

如果我们不能在异步环境中假设最大的消息传递时间，那么实现终止会困难得多。请记住，达成共识必须满足的条件之一是「终止」，这意味着每个非故障节点必须决定某些输出值。

这被称为「FLP 不可能结果」。它是如何得到这个名字的呢？好吧，很高兴你能问这个问题！

研究人员 Fischer，Lynch 和 Paterson 在 1985 年撰写的《在一个错误进程中不可能达成分布式共识》这一论文中提到，即使只是一个错误的进程，也无法在确定性异步进程中达成共识。

基本上，由于进程可能在不可预测的时间点失败，因此它们也可能在阻止达成共识的恰当时机失败。

这个结果对分布式计算领域而言是一个巨大的头疼点。尽管如此，科学家们还是在继续努力寻找绕过 FLP 不可能的方法。

在较高的层面上，有两种方法可以避免 FLP 不可能：

1. 使用同步假设；
2. 使用非确定论；

现在，让我们深入了解这两种方法。

方法 1: 使用同步假设

好吧，我知道你在想什么：这到底意味着什么？

让我们重新审视我们的不可能结果。这里有考虑它的另一种方式：FLP 不可能结果基本上表明，如果我们不能在系统中取得进展，那么我们就无法达成共识。换句话说，如果异步传递消息，则无法保证终止。回想一下，终止是一个必需条件，这意味着每个非故障节点最终必须决定一些输出值。

但是，如果我们不知道异步网络何时会传递消息，我们如何才能保证每个非故障进程都能决定一个值？

要明确的是，这一发现并未表明共识无法实现，相反，由于不同步，在固定的时间内无法达成共识。说共识是「不可能的」，只是意味着共识「并非总是可行的」，这是一个微妙但至关重要的细节。

避免这种情况的一种方法是使用超时设定。如果在确定下一个值没有进展，我们会等待一个时间段，然后再重新开始步骤。

正如我们即将看到的那样，像 Paxos 和 Raft 这些共识算法就是这样的。

Paxos 算法

Paxos 算法的提出是在 20 世纪 90 年代，这也是第一个真实可用的容错共识算法。它是首个被广泛采用的共识算法，并曾被谷歌和亚马逊等全球互联网公司用于构建分布式服务。

Paxos 的工作方式如下：

阶段 1：准备请求

1. 提议者选择新的提案版本号 (n) ，并向接受者发送「准备请求」。
2. 如果接受者收到准备请求（“prepare,” n），其 n 大于他们已经回复的任何准备请求，接受者发出 (“ack,” n, n’, v’) 或 (“ack,” n, ^ , ^)。
3. 接受者以承诺回应，表示不再接受编号小于 n 的任何提案。
4. 接受者建议他们已接受的最高数提案的值 (v)（如果有的话），否则，他们会以 ^ 回应；

阶段 2：接受请求

1. 如果提议者收到来自大多数接受者的响应，那么它可以发出一个接受请求（“accept,” n, v），其数量为 n，值为 v。
2. n 是准备请求中出现的数字。
3. v 是响应中编号最高的提议值。
4. 如果接受者收到一个接受请求 (“accept,” n, v)，它会接受该提议，除非它经响应了一个数字大于 n 的准备请求。

阶段 3：学习阶段

1. 每当接受者接受提议时，它会响应所有学习者 (“accept,” n, v)
2. 学习者从大多数接受者那里接收 (“accept,” n, v) ，决定 v，并向所有其他学习者发送 (“decide,” v) ；
3. 学习者接受 (“decide,” v) 并决定 v；

来源：https://www.myassignmenthelp.net/paxos-algorithm-assignment-help

嗯！困惑了吗？我知道这里有很多信息需要去消化。但是，等等……还有更多的信息！

我们现在知道，每个分布式系统都是有故障的。在 Paxos 算法中，如果提议者失败（例如，因为存在遗漏错误），则可延迟决策。Paxos 通过从第 1 阶段的新版本号开始处理此问题，即使之前的尝试从未结束。

我不会详细介绍，但在这种情况下，恢复正常运行的进程是非常复杂的。

Paxos 难以理解的主要原因，是它的很多实现细节都留给了读者：例如我们如何知道提议者什么时候失败？我们是否使用同步时钟来设置超时时间，来决定提议者何时失败？等等。

Paxos 在领导者选举，故障检测和日志管理等内容是模糊或完全不明确的。

这种设计选择最终成为 Paxos 最大的缺点之一，它不仅难以理解，而且也很难实现。反过来，这使得分布式系统领域也难以驾驭。

到目前为止，你可能想知道同步假设的来源。

在 Paxos 中，虽然算法中没有明确的超时，但在实际实现时，在一些超时时间之后选择一个新的提议者是实现终止所必须的。否则，我们就无法保证接收者会输出下一个值，系统可能会因此停止运行。

Raft 算法

2013 年，Ongaro 和 Ousterhout 发布了一种名为 Raft 的复制状态机共识算法，其核心目标是可理解性（与 Paxos 的最大不同之处）

我们从 Raft 算法学到的一个重要新事物，是使用共享超时的概念来处理终止问题。在 Raft 中，如果你崩溃了并重新启动，你需要等待至少一个超时时间，才能让自己被宣布为领导者，并保证你取得进步。

但等等 ... 拜占庭环境呢？

虽然传统的共识算法（例如 Paxos 和 Raft）能够使用某种程度的同步假设（即超时）在异步环境中发展，但它们不是拜占庭容错的。它们只是崩溃容错的。

崩溃故障是较容易处理的，因为我们可以将进程建模为工作或崩溃（0 或 1），进程不能恶意行事或撒谎。因此，在崩溃容错系统中，分布式系统是可构建的，其中简单的多数参与者就足以达成共识。

而在开放和去中心化的（例如公链）系统中，用户无法控制网络中的节点。相反，每个节点都会针对其各自的目标做出决策，这可能与其他节点的目标冲突。

在拜占庭系统中，节点具有不同的激励，它们可以撒谎、协调或任意行动，你不能假设简单的多数节点就能够达成共识。一半或更多的诚实节点是可相互协调和欺骗的。

然而，Raft 并不是为了容忍这种行为而设计的。例如，如果当选的领导者是拜占庭，并且与其他节点保持强大的网络连接，则可能会危及系统。Raft 和 Paxos 是简单的容错，但不是拜占庭容错。

拜占庭将军问题

试图建立一个可处理冲突信息进程的可靠计算机系统，被称为「拜占庭将军问题」。拜占庭容错协议应该能够实现其共同目标，即使是遭受来自节点的恶意行为。

Leslie Lamport，Robert Shostak 和 Marshall Pease 撰写的《拜占庭将军问题》论文，提供了解决拜占庭将军问题的第一个证明：它表明具有 x 个拜占庭节点的系统，必须至少有（3x + 1）个总节点，才能达到共识。

原因如下：

如果 x 节点出现故障，则系统需要与（n-x）节点协调后才能正常运行（因为 x 节点可能有故障（拜占庭）并且没有响应）。但是，我们必须为不响应的可能没有错误的 X 节点做准备，它也可能是做出回应的 X 节点。如果我们希望非故障节点的数量超过故障节点的数量，我们至少需要（n-x-x）> x，因此，n> 3x + 1 是最佳的。

但是，该论文中演示的算法仅适用于同步环境。这不是一个好消息！看起来，我们只能得到一个或另一个（拜占庭 vs 异步），对吗？

但为什么不包括两个呢？

简而言之，建立一个能够承受异步环境和拜占庭环境的共识算法 ...... 好吧，这就像创造奇迹一样。

像 Paxos 和 Raft 这样的算法，是众所周知且被广泛使用的。但也有很多学术工作正在尝试研究拜占庭+异步的共识算法。

所以系上你的安全带 ......

我们将要实地考察理论学术论文的领域。

你应该感到兴奋！还记得我们之前讨论过的「创造奇迹」吗？

我们将查看两种算法（DLS 和 PBFT），这些算法要比以往任何时候都更接近于打破拜占庭+异步的障碍。

DLS 算法

由 Dwork，Lynch 和 Stockmeyer 共同撰写的论文《部分同步存在下的共识》引入了拜占庭容错共识的一项重大进步：它定义了如何在一个「部分同步系统」中达成共识，该算法也因三位作者的名字而被称为「DLS」算法。

你可能还记得，在同步系统中，消息从一个处理者发送到另一个处理者所需的时间有一个已知的固定上限。在异步系统中，则不存在固定的上限。

而部分同步，则位于同步系统和异步系统之间。

该论文解释了部分同步假设的两个版本：

1. 假设消息传递的长短存在固定边界。但它们不是先验已知的。无论实际的界限如何，目标都是达成共识。
2. 假设消息传递的上限是已知的，但它们只能保证在某个未知时间开始（也称为「全球标准化时间」，GST）。目标是设计一个能够达成共识的系统，无论何时发生。

以下是 DLS 算法的工作原理：

一系列 round 分为「尝试」和「锁定释放」阶段。

1. 每一轮都有一个提议者，并从每个进程开始，传达他们认为正确的值。
2. 如果至少有（N − x）个进程传达了一个值，则提议者“提出”该值。
3. 当进程从提议者处接收建议值时，它必须锁定该值，然后广播该信息。
4. 如果提议者从 x + 1 进程接收到他们锁定某个值的消息，则将其作为最终值提交。

DLS 是一项重大技术突破，因为它创造了一种新的网络假设类型，即部分同步，其还证明了这种假设的共识是可能的。DLS 论文中另一个必要的内容，是将拜占庭和异步设置达成共识的问题分为两个方面：安全性和活跃性。

安全性

这是我们前面讨论过的「协议」属性的另一个术语，其中所有非故障进程都对同一输出达成一致。如果我们能够保证安全性，则我们能够保证整个系统保持同步。我们希望所有节点同意交易日志的总顺序，尽管会存在失败和恶意行为者的干扰。而违反安全性，意味着我们最终会得到两个或更多有效的交易日志。

活跃性

这是我们早期讨论的「终止」属性的另一个术语，其中每个非故障节点最终决定某些输出值。在区块链设置当中，活跃性意味着区块链通过添加有效新区块而不断增长。活跃性是很重要的，因为它是网络继续有用的唯一方式，否则，网络就会停滞不前。

正如「FLP 不可能」告诉我们的，在完全异步的系统中是无法达成共识的。而 DLS 论文认为，为实现活跃条件而做出部分同步假设，足以克服 FLP 不可能性。

因此，这篇论文证明了算法不需要使用任何同步假设来实现安全条件。

很明确，对吧？如果不是，不要担心。让我们深入探讨这个概念：

请记住，如果节点没有决定某个输出值，系统就会暂停。因此，如果我们做出一些同步假设（即超时），以保证终止，并且其中一个会失败，那么这也会使系统停止。

但是，如果我们设计一个算法，其中我们假设了超时（以保证安全性），而如果同步假设失败，则会带来导致两个有效交易日志的风险。

这比前一种选择会危险得多。如果服务损坏（即没有安全性），则没有必要提供有用的服务（即活跃性）。

基本上，拥有两个不同的区块链，会比整个区块链停止会更糟。

分布式系统总是需要权衡利弊的，如果你想克服限制（例如 FLP 不可能），你必须在其它地方做出牺牲。在这种情况下，将关注点分解为安全性和活跃性是非常好的。它允许我们构建一个在异步设置中安全，但仍需要某种形式超时来保持生成新值的系统。

尽管 DLS 论文提供了所有内容，但 DLS 算法从未真正被广泛实施，或用于真实世界的拜占庭式设置。这可能是由于 DLS 算法的核心假设之一，是使用同步处理器时钟（以便具有共同的时间概念）。实际上，同步时钟容易受到大量攻击，并且它在拜占庭容错设置中并不是很好。

PBFT 算法

另一种由 Miguel Castro 和 Barbara Liskov 于 1999 年发表的拜占庭容错算法，被称为「实用拜占庭容错」（PBFT）。对于展示拜占庭行为的系统而言，它被认为是一种更为「实用」的算法。

从这个意义上来说，「实用」意味着它可以在互联网等异步环境中运行，此外它也进行了一些优化，使其较以前的共识算法要更快。该论文中提到，以前的算法虽然被证明是「理论上可行的」，但它们要么太慢，无法被使用，要么是为了安全性而做了假定同步。

正如我们已经解释的那样，在异步设置中，这可能是非常危险的。

简而言之，PBFT 算法表明，假设（n-1）/ 3 个节点出现了故障，它可以提供安全性和活跃性。正如我们之前讨论的那样，这是我们需要容忍拜占庭故障的最小节点数。因此，该算法的抵抗性是最理想的。

无论有多少节点出现故障，该算法都能够提供安全性。换句话说，它没有为安全性而假设同步。然而，该算法确实依赖于同步性来实现活跃：

最多的情况下，（n-1）/ 3 个节点可出现故障，并且消息延迟的增长速度不会超出某个时间限制。

因此，PBFT 通过使用同步假设来保证活跃性，从而规避了 FLP 不可能性。

该算法通过一系列「view」，其中每个 view 都有一个「主要」节点（即领导者），其余 view 都是「备份」节点。以下是有关 PBFT 工作方式的逐个步骤：

1. 在客户端上发生了一笔新的交易，并向主要节点广播；
2. 主要节点将它复制到所有的备份节点；
3. 备份节点执行交易，并向客户端发送回复；
4. 客户端希望从备份节点处获得 x + 1 个与结果相同的回复。这是最终结果，且状态转变发生了。

如果领导者没有发生错误，协议会工作得很好，然而，检测不良主要节点和重新选择新主要节点（称为 view 变化）的过程是非常低效的。例如，为了达成共识，PBFT 需二次数量的消息交换，这意味着每台计算机都必须与网络中的每台其他计算机进行通信。

（注：完整解释 PBFT 算法需另起一篇文章，这里不会详细解释。）

虽然 PBFT 是对以前算法的改进，但对于存在大量参与者的真实世界应用（例如公链）而言，它的扩展性是不够的。但是，嘿，至少在涉及故障检测和领导者选举（与 Paxos 不同）方面，该算法会显得更明确一些。

承认 PBFT 算法的贡献是重要的，它结合了重要的革命思想，而新的共识协议（特别是后区块链世界）可从中学习和进行改进。

例如，Tendermint 是一种受 PBFT 影响很大的新共识算法。在 Tendermint 的「验证」阶段，其使用了两个投票步骤（和 PBFT 一样）来决定最终值。与 PBFT 算法的主要区别在于，Tendermint 的设计，会更加实用。

例如，Tendermint 每轮都会轮换新的领导者。如果当前轮次的领导者在一段时间内没有响应，其会跳过领导者，并且算法会简单地移动到带有新领导者的下一轮。这实际上比每次需要进行 view 更改和选择新领导者时使用点对点连接更有意义。

方法 2：非确定论

正如你从上面了解到的，大多数拜占庭容错共识协议，最终使用某种形式的同步假设来克服 FLP 不可能性。然而，还有另一种方法可以克服 FLP 不可能性，即：非确定论。

进入中本聪共识

正如我们刚刚了解到的那样，在传统的共识中，f （x）被定义为提议者和一群接受者必须全部协调和通信，以决定下一个值。

这太复杂了，因为它需要知道网络中的每个节点，以及每个节点与其它节点的通信（即，二次通信开销）。简而言之，它不能很好地扩展，并且不能在开放、无需许可的系统中工作（其中任何人都可以随时加入和离开网络）。

而中本聪共识的聪明之处，在于概率性地完成了上述的过程。相比每个节点都同意一个值，f(x) 是使所有节点都同意值是正确的可能性。

等等，这意味着什么？

拜占庭容错

相比选举一个领导者，然后与所有节点协调，而是根据哪个节点能够最快解决计算难题来解决共识。比特币区块链中的每个区块，都由解决这个难题的节点添加。拥有最多累积工作量的链（即累积难度）即是标准链。最长的链，不仅可作为区块序列的证明，而且可以证明它来自最大的 CPU 功率池。因此，只要大部分 CPU 功率由诚实节点控制，它们将继续产生最长链，并超过攻击者。

区块奖励

中本聪共识，通过假设节点为争夺下一个区块，会扩展计算投入的方式而工作。该算法的聪明之处，在于经济上激励节点重复执行这种计算，以获取随机获得区块奖励的机会。

抵抗女巫（Sybil）攻击

解决这个难题所需的工作量证明，使得协议本身具有抵抗女巫攻击的特性。它不需要 PKI 或任何其他花哨的身份验证方案。

对等 gossip

中本聪共识的主要贡献，是使用了 gossip 协议，它更适合于无法假设非故障节点间通信的对等设置。相反，我们假设节点仅连接到其它节点的子集。然后，我们使用对等协议，其中消息在节点之间互相传播。

在异步环境中，并不是「技术」安全的

在中本聪共识中，安全保障是概率性的，我们会不断增长最长链，而每个新区块都会降低恶意节点尝试构建另一个有效链的可能性。

因此，中本聪共识在技术上并不保证异步设置的安全性。让我们花点时间了解下原因。

对于在异步设置中实现安全性条件的系统，我们应该能够在异步网络条件下维护一致的交易日志。考虑它的另一种方式，是节点可随时脱机然后再返回在线状态，并使用区块链的初始状态来确定最新的正确状态（而不管网络状况如何）。任何诚实节点都可以查询过去的任意状态，并且恶意节点不能提供诚实节点认为是真实的欺诈性信息。

在本文讨论的前几种算法中，这是可能的，因为我们确定性地在每一步完成一个值。只要我们终止每个值，我们就可以知道过去的状态。然而，比特币在「技术上」不是异步安全的，其原因是有可能存在一个网络分区，其中攻击者具有足够强大的算力来创建一条比诚实链更快的替代链。在这个替代链上，攻击者可尝试改变他自己的一笔交易来收回他所花的钱。

不可否认的是，这就要求攻击者获得大量的算力，而这需要大量的资金。

从本质上讲，比特币区块链的不可更改性来源于这样一个事实：即大多数矿工实际上并不想采用替代链。这是因为，要掌握足够的算力以使其余矿工采用替代链是很困难的。换句话说，成功创建替代链的可能性是非常低的，它几乎可以忽略不计。

中本聪共识 vs 传统共识算法

出于实际目的，中本聪共识是拜占庭容错的。但它显然没有达成共识研究人员传统上所假设的共识。因此，它最初被视为完全脱离拜占庭容错世界。

感谢你，中本聪！

根据设计，中本聪共识可以让任意数量的节点以开放式的方式参与系统，而且没有人必须要知道完整的参与者集。这一突破的重要性不容小觑！

它比以往的共识算法要更简单，它消除了以前共识算法在点对点连接、领导者选举、二次通信开销等方面的复杂性。你只需在任何计算机上启动比特币协议软件，并开始挖矿任务。

这使其可在真实环境中轻松部署，它确实是比 PBFT 更「实用」的共识算法。

结论

现在你应该对分布式系统共识算法的简要基础知识有所了解了。对于分布式计算而言，这是一个漫长而曲折的研究和独创性之旅。我希望这篇文章能够有助于你对这个领域有更多的了解。

中本聪共识是一项真正的创新，它让研究人员、科学家、开发者和工程师在共识协议研究中不断开天辟地。

还有一个全新的协议系列正在不断开发中，嗯，它就是权益证明（Proof-of-stake），作者在接下来的文章中会谈到，敬请关注！

注：为了简单目的，作者跳过了很多重要的论文和算法。例如 Ben Orr 的 Common Coin 也使用了概率方法，但它没有最佳的抵抗性。其它算法如哈希现金（Hash Cash）也使用 PoW，但其是用于限制电子邮件垃圾邮件和拒绝服务攻击目的的。这篇文章遗漏了很多传统的共识协议！但作者认为，上述内容足以帮助你了解传统共识算法和中本聪共识算法的不同。

特别感谢 Zaki Manian 提出的有关分布式共识的所有问题。

来源链接：www.8btc.com