分布式共识如何运作?

18-11-20 banq
                   

MartinFowler推荐的文章,论述区块链技术的关键概念,以及中本共识为何如此重要?

分布式系统可能难以理解,主要是因为围绕它们的知识也是分布式的。现在,经过多次考验和磨难,我终于准备好向您解释分布式系统的基础知识。

区块链迫使工程师和科学家重新审视并质疑分布式计算中根深蒂固的范式。

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

分布式系统绝不是新的。科学家和工程师花费了数十年时间研究这一主题。但是区块链与它们有什么关系呢?好吧,如果分布式系统首先不存在,那么区块链所做的所有贡献都是不可能的。

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

不幸的是,很多关于分布式计算的文献要么难以理解,要么分散在太多的学术论文中。为了使问题更复杂,有数百种架构,所有架构都满足不同的需求。将其归结为易于理解的框架非常困难。

因为这个领域很广,我不得不仔细选择我可以覆盖的东西。我还必须进行概括以掩盖一些复杂性。请注意,我的目标不是让你成为该领域的专家。相反,我想给你足够的知识,以启动你的分布式系统和共识的旅程。

阅读完这篇文章之后,你将更加掌握:

  • 什么是分布式系统,
  • 分布式系统的属性,
  • 在分布式系统中达成共识意味着什么,
  • 理解基础共识算法(例如DLS和PBFT),以及
  • 为什么Nakamoto Consensus是一个大问题。

我希望你已经准备好学习,因为课程正在开课。

什么是分布式系统?

分布式系统涉及一组不同的进程(例如,计算机)将消息彼此传递且协调以实现共同目标(即,解决计算问题)。

分布式系统是一组协同工作以实现统一目标的计算机。

简而言之,分布式系统是一组共同努力实现统一目标的计算机。虽然这些过程是分开的,但系统对最终用户来说只是一台计算机。

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

在这篇文章中,我们将专注于分布式系统,其中进程代表的是空间分离的计算机(节点服务器)

分布式系统的属性

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

A)并发

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

这需要协调。

协调就需要时间,时钟和事件排序

B)缺乏全球时钟

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

在“ 分布式系统中的时间,时钟和事件排序”一文中,Leslie Lamport展示了如何通过记住以下因素来推断一个事件是否在另一个事件之前发生:

  1. 消息在收到之前发送。
  2. 每台计算机都有一系列事件。

通过确定哪个事件发生在另一个事件之前,我们可以获得系统中事件的部分排序。Lamport的论文描述了一种算法,该算法要求每台计算机都能监听系统中每台其他计算机。通过这种方式,可以基于该部分排序完全排序事件。

但是,如果我们将顺序完全基于每台计算机监听到的事件,我们可能会遇到此顺序与系统外部用户所感知的不同的情况。因此,该算法会发生异常行为。

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

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

从本质上讲,Lamport的论文表明事件的时间和顺序是在空间上分离的分布式计算机系统中的基本障碍。

C)组件的独立故障

理解分布式系统的一个关键方面是承认分布式系统中的组件存在故障。这就是它被称为“容错分布式计算”的原因。

系统没有故障是不可能的。真正的系统存在许多可能的缺陷或缺陷,无论这是一个进程崩溃; 消息丢失,扭曲或重复; 延迟或丢弃消息的网络分区; 甚至一个进程完全失控,并根据一些恶意计划发送消息。

系统没有故障是不可能的。

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

  • 崩溃 - 失败:组件在没有警告的情况下停止工作(例如,计算机崩溃)。
  • 省略:组件发送消息但其他节点未接收到消息(例如,消息被丢弃)。
  • 拜占庭:该组件表现得任意。这种类型的故障在受控环境(例如,Google或Amazon数据中心)中无关紧要,在这些环境中可能没有恶意行为。相反,这些错误发生在所谓的“对抗性上下文”中。基本上,当一组分散的独立行动者充当网络中的节点时,这些行动者可能选择以“拜占庭”的方式行事。这意味着他们会恶意选择更改,阻止或不发送消息。

考虑到这一点,目标是设计协议,允许具有故障组件的系统仍然实现共同目标并提供有用的服务。

鉴于每个系统都有故障,我们在构建分布式系统时必须考虑的核心因素是,即使其部件偏离正常行为,它是否能够存活,无论是否由于非恶意行为(即崩溃失败或遗漏错误)或恶意行为(即拜占庭故障)。

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

1)简单的容错

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

2A)拜占庭容错

简单的容错系统在不受控制的环境中不是很有用。在一个分散的系统中,节点由独立的参与者控制,在开放的,无权限的互联网上进行通信,我们还需要设计选择恶意或“拜占庭”的节点。因此,在拜占庭容错系统中,我们假设节点可以失败或恶意。

2B)BAR容错

尽管大多数真实系统都设计为能够承受拜占庭故障,但一些专家认为这些设计过于笼统,并未考虑“理性”故障,如果符合自身利益,节点可能会出现偏差。 。换句话说,取决于激励,节点可以是诚实的和不诚实的。如果激励措施足够高,那么即使是大多数节点也可能不诚实地行事。

更正式地说,这被定义为BAR模型 - 一个指定拜占庭和理性失败的模型。BAR模型假设有三种类型的角色:

  • 拜占庭:拜占庭节点是恶意的,并试图搞砸你。
  • 利他主义:诚实的节点总是遵循协议。
  • Rational理性: Rational节点只有在适合它们时才遵循协议。

D)消息传递

如前所述,分布式系统中的计算机通过一台或多台其他计算机之间的“消息传递”进行通信和协调。消息可以使用任何消息传递协议传递,无论是HTTP,RPC还是为特定实现构建的自定义协议。消息传递环境有两种类型:

1)同步

在同步系统中,假设消息将在某个固定的已知时间内传送。

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

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

2)异步

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

在分布式系统中达成共识意味着什么

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

  • 进程的并发性
  • 缺乏全球时钟
  • 有问题的流程
  • 消息传递

接下来,我们将专注于理解在分布式系统中实现“共识”意味着什么。但首先,重申我们之前提到的内容非常重要:数百种用于分布式计算的硬件和软件架构。

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

复制状态机

复制状态机是一种确定性状态机,它在许多计算机上复制,但作为单个状态机运行。这些计算机中的任何一台都可能出现故障,但状态机仍然可以运行。

在复制状态机中,如果事务有效,则一组输入将导致系统状态转换到下一个事务。事务是对数据库的原子操作。这意味着操作要么全部完成,要么根本不完成。在复制状态机中维护的事务集称为“事务日志”。

从一个有效状态转换到下一个有效状态的逻辑称为“状态转换逻辑”。

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

反过来,这在系统中的每台计算机上维护一致的事务日志(即,它们“实现共同的目标”)。复制的状态机必须不断地将新事务接受到该日志中(即,“提供有用的服务”)。尽管如此,它必须这样做:

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

我的朋友们,这是任何一致性算法的基本目标。

共识问题的定义

如果算法满足以下条件,则算法达成共识:

  • 协议:所有非故障节点决定相同的输出值。
  • 终止:所有非故障节点最终决定某些输出值。

注意:不同的算法具有上述条件的不同变化。例如,有些人将协议属性划分为Consistency和Totality。有些人有一个有效性或完整性或效率的概念。但是,这种细微差别超出了本文的范围。

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

  1. 提议者,通常称为领导者或协调员。
  2. 接受者,监听提议者请求并响应值的过程。
  3. 学习者,系统中的其他过程,学习决定的最终价值

通常,我们可以通过三个步骤定义一致性算法:

第1步:选举

  • 进程选择一个领导进程(即领导者)来做出决策。
  • 领导者提出下一个有效的输出值。

第2步:投票

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

第3步:决定

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

重要的是要注意每个共识算法都有不同:

  • 术语(例如,轮次,阶段),
  • 如何处理投票的程序,以及
  • 决定最终值的标准(例如,有效性条件)。

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

很简单吧?

FLP不可能

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

  • 在同步环境中,消息在固定的时间范围内传递
  • 在异步环境中,无法保证传递消息。

这种区别很重要。

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

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

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

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

这被正式称为“FLP不可能性结果。” 它是如何得到这个名字的?好吧,我很高兴你问这个问题!

某个发生错误的进程即使在确定性异步过程中也是不可能达成共识的。

研究员Fischer,Lynch和Paterson(又名FLP)在他们1985年发表的论文“ 分裂共识与一个错误进程的不可能性 ”中表明上述观点,也就是说,由于进程可能在不可预测的时间内失败,因此它们也可能在阻止达成共识的恰当时机恰好发生错误失败。

这个结果对分布式计算空间来说是一个巨大的失败。尽管如此,科学家们还是继续努力寻找绕过FLP不可能性的方法。

在较高的层面上,有两种方法来规避FLP不可能性:

  1. 使用同步假设。
  2. 使用非决定论。

让我们现在深入了解每一个。

方法1:使用同步假设

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

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

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

避免这种情况的一种方法是使用超时。如果在确定下一个值时没有进展,我们会等到超时,然后再重新开始步骤。正如我们即将看到的那样,这就是像Paxos和Raft这样的共识算法。

Paxos

Paxos于20世纪90年代推出,是第一个真实的,实用的,容错的一致性算法。它是Leslie Lamport首次被广泛采用的共识算法之一,并被谷歌和亚马逊等全球互联网公司用于构建分布式服务。

Paxos的工作方式如下:

阶段1:准备请求

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

阶段2:接受请求

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

阶段3:学习阶段

  • 每当接受者接受提议时,它都会响应所有学习者(“accept”,“n”,“v”)。
  • 学习者从大多数接受者接收(“accept”,n,v),决定v,并向所有其他学习者发送(“decide”,v)。
  • 学习者接受(“decide”,v)和决定的v。

唷!困惑了吗?我知道这是一个需要消化的大量信息。

但是等等......还有更多!

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

我不会详细介绍,但在这种情况下恢复正常运行的进程非常复杂,因为预计流程会介入并推动解决流程。

Paxos难以理解的主要原因是它的许多实现细节都留给了读者的解释:我们如何知道提议者什么时候失败?我们是否使用同步时钟来设置超时时间来决定提议者何时失败并且我们需要继续下一个等级?

为了提供实施的灵活性,关键领域的几个规范是开放式的。领导者选举,故障检测和日志管理等内容模糊或完全不明确

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

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

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

Raft

2013年,Ongaro和Ousterhout发布了一种名为Raft的复制状态机的新共识算法,其核心目标是可理解性(与Paxos不同)。

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

但是等等......“拜占庭”环境怎么样?

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

崩溃故障更容易处理,因为我们可以将进程建模为工作或崩溃 - 0或1.进程不能恶意行事并撒谎。因此,在崩溃容错系统中,可以构建分布式系统,其中简单多数足以达成共识。

在开放和分散的系统(例如公共区块链)中,用户无法控制网络中的节点。相反,每个节点都会针对其各自的目标做出决策,这可能与其他节点的目标冲突。

在拜占庭系统中,节点具有不同的激励,可以撒谎,协调或任意行动,你不能假设简单的多数足以达成共识。半数或更多的所谓诚实节点可以相互协调以便撒谎。

例如,如果当选的领导者是拜占庭并且与其他节点保持强大的网络连接,则可能危及系统。回想一下我们如何说我们必须对我们的系统建模,以容忍简单的故障或拜占庭故障。Raft和Paxos是简单的容错但不是拜占庭容错。它们不是为容忍恶意行为而设计的。

'拜占庭将军的问题'

试图建立一个可以处理提供冲突信息的进程的可靠计算机系统正式被称为“ 拜占庭一般问题 ”。拜占庭容错协议应该能够实现其共同目标,即使是针对节点的恶意行为。

论文“ 拜占庭将军问题 ”由Leslie Lamport, Robert Shostak, 和Marshall Pease提供的第一手证据,以解决拜占庭将军的问题:它表明,一个系统X拜占庭节点必须有至少3个+ 1的总节点,以达到共识。

原因如下:

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

但是,本文中演示的算法仅适用于同步环境。而拜占庭+异步的环境似乎更难设计。

为什么?

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

像Paxos和Raft这样的算法是众所周知的并且被广泛使用。但也有很多学术工作更侧重于解决拜占庭+异步设置中的共识问题。

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

我们正在实地考察......

到...的土地

理论学术论文!

(见下页)

                   

1
banq
2018-11-20 11:02

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

DLS算法

Dwork,Lynch和Stockmeyer 的论文“ 部分同步存在下的共识 ”(因此称为“DLS”算法)引入了拜占庭容错共识的一个重大进步:它定义了如何在“部分”中达成共识的模型同步系统。“

您可能还记得,在同步系统中,消息从一个处理器发送到另一个处理器所需的时间有一个已知的固定上限。在异步系统中,不存在固定的上限。部分同步位于这两个极端之间。  本文解释了部分同步假设的两个版本:

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

以下是DLS算法的工作原理:  一系列轮次分为“尝试”和“锁定释放”阶段。

  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不可能性。

该算法通过一系列“视图”,其中每个视图都有一个“主要”节点(即领导者),其余视图是“备份”。以下是有关其工作方式的逐步演练:

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

如果领导者没有错误,协议工作正常。然而,检测不良主要和重新选择新主要(称为“视图变化”)的进程非常低效。例如,为了达成共识,PBFT需要二次数量的消息交换,这意味着每台计算机都必须与网络中的每台其他计算机进行通信。

虽然PBFT是对以前算法的改进,但对于存在大量参与者的真实世界用例(例如公共区块链)来说,缩放是不够实际的。但是,嘿,至少在涉及故障检测和领导者选举(与Paxos不同)时更具体。

重要的是要承认PBFT的贡献。它结合了重要的革命性思想,即新的共识协议(特别是在后块链世界中)将从中学习和使用。

例如,Tendermint是一种受PBFT影响很大的新共识算法。在他们的“验证”阶段,Tendermint使用两个投票步骤(如PBFT)来决定最终值。Tendermint算法的设计更加实用。

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

方法2:非确定

正如我们所知,大多数拜占庭容错共识协议最终都采用某种形式的同步假设来克服FLP不可能性。然而,还有另一种方法可以克服FLP不可能性:非确定性。

Nakamoto Consensus

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

传统的共识并不能很好地扩展。

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

Nakamoto Consensus的辉煌正在形成上述概率。f(x)不是每个节点都同意一个值,而是使所有节点都同意值正确的概率。

等等,这甚至意味着什么?

拜占庭容错

不是进行领导者选举然后与所有节点协调,而是根据哪个节点能够最快地解决计算难题来决定共识。比特币区块链中的每个新块都由最快解决这个难题的节点添加。网络继续建立在这个带时间戳的链上,规范链是消耗最多累计计算量的链(即累积难度)。

最长的链不仅可以作为块序列的证明,而且可以证明它来自最大的CPU功率池。因此,只要大部分CPU功率由诚实节点控制,它们将继续产生最长链和超速攻击者。

奖励

Nakamoto Consensus通过假设节点将花费计算工作来决定下一个块的机会。该算法的亮度在经济上激励节点重复执行这种计算上昂贵的谜题,以获得随机赢得大奖励的机会(即,块奖励)。

西比尔阻力

解决这个难题所需的工作证明使协议本身具有Sybil抗性。不需要PKI或任何其他花哨的身份验证方案。

点对点gossip

Nakamoto Consensus的主要贡献是使用gossip协议。它更适用于无法假设非故障节点之间的通信的对等设置。相反,我们假设节点仅连接到其他节点的子集。然后我们使用对等协议,节点之间使用gossip。

在异步环境中没有“技术上”安全

在Nakamoto的共识中,安全保证是概率性的 - 我们正在增长最长链,每个新块都会降低恶意节点尝试构建另一个有效链的可能性。

因此,Nakamoto Consensus在技术上并不保证异步设置的安全性。让我们花点时间了解原因。

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

Nakamoto Consensus在技术上并不保证异步设置的安全性。

在本文讨论的先前算法中,这是可能的,因为我们确定性地在每一步完成一个值。只要我们最终结果是某个值,我们就可以知道过去的状态。然而,比特币在“技术上”不是异步安全的原因是,有可能存在一个网络分区,让分区一侧具有足够大的散列能力的攻击者创建一个比诚实链更快的替代链。在分区的另一边 - 在这个替代链上,他可以尝试改变他自己的一笔交易来收回他花的钱。

不可否认,这将要求攻击者获得大量的散列能力并花费大量资金。

从本质上讲,比特币区块链的不变性源于这样一个事实,即大多数矿工实际上并不想采用替代链。为什么?因为协调足够的散列能力以使网络采用替代链很困难。换句话说,成功创建替代链的可能性非常低,几乎可以忽略不计。

Nakamoto与传统共识

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

根据设计,Nakamoto Consensus使任意数量的节点都可以公开参与,而且没有人必须知道全套参与者。这一突破的重要性不容小觑。谢谢你,Nakamoto。

它比以前的一致性算法更简单,它消除了点对点连接,领导者选举,二次通信开销等的复杂性。您只需在任何计算机上启动比特币协议软件并开始挖掘。

这使其可以在真实环境中轻松部署。它确实是PBFT更“实用”的堂兄。

结论

对于分布式计算来说,这是一个漫长而曲折的研究,障碍和独创性之旅。我希望这篇文章可以帮助你更好地了解这个领域。

Nakamoto Consensus是一项真正的创新,它让全新的研究人员,科学家,开发人员和工程师在共识协议研究中不断开辟新天地。

还有一个全新的协议系列正在开发中超越Nakamoto Consensus:Proof-of-Steak