原文标题：《<深度解析共识算法>系列分享活动之<共识算法入门>》
原文来源：Algorand Official
今晚 8 点（区块律动 BlockBeats 小编注：2020 年 2 月 27 日），《深度解析共识算法》系列分享活动第一期正式与大家见面。Algorand 基金会副总监朱海潮首先带来主题为《共识算法入门》的在线分享，深入浅出地介绍了关于共识算法的起源、分类和安全性等话题。
背景知识
分布式系统
最早使用共识算法这个名词的其实是来自分布式系统领域的科学家们，所以这里我们首先需要理解下分布式系统这个概念。
简单来说，分布式系统指的是一组计算机同时工作，并且之间互相通信，完成同一个计算目的。虽然这会是一个由多台计算机组成的系统，但对于使用它的用户来说，它用起来就像是一台计算机一样。一个典型的例子就是飞机系统，一架飞机中有着多台计算机系统，他们互相通信协作，共同完成带你飞来飞去这一伟大目标。
在一个分布式系统中，我们通常会将其中的一个个计算机称为节点（node）。节点之间会互相通过发送消息（message）来进行通信，消息中会包含需要节点执行的事务（event），节点在收到事务后会独立进行所需的计算，并更新本地保存的结果，或将结果发送给客户端（Client），这就构成了一个分布式系统。
状态复制机（Replicated State Machine）
很明显，区块链系统也是一种分布式系统。
并且区块链系统本身使用的模型，也是分布式系统中最典型的一种模型 – 状态复制机（Replicated State Machine）。先给非计算机科学背景的朋友们简单讲下什么是状态机（State Machine）。
状态机是一种抽象后的计算机模型，它指的是一台能够储存一组状态（State）的计算机，在收到来自外部的输入（Input）或者事件（Event）时，它会发生状态的转变（StateTransition），如上图所示。
还是用区块链举个例子，每一个区块链节点本质上就是一个状态机，它保存了当前所有账户的余额等信息，而这些信息就可以被看作是状态；当节点收到外界发来的交易（Transaction）时，它就会根据交易信息去计算每个账户的新余额；计算完成后，节点会将新的账户余额存储下来，成为新的状态，这也就完成了状态的转变。
由多个这样的节点互相连接构成的网络就叫做状态复制机。在正常情况下，当收到外界发来的交易时，状态复制机网络中的所有节点都会按照交易信息独立计算，并存储新的状态；并且多个节点的最终状态会保持一致，同时对外提供相同的输出；虽然网络中存在多个状态机，但从外界来看，就像是在使用一个单独的状态机一样。而为了使一个状态复制机网络能保持正常并且可靠运行的算法，就叫做共识算法（Consensus Algorithm）。
共识算法的定义
背景知识介绍到这里，我们就可以给共识算法下个定义了。共识算法需要使状态复制机网络中的能够达到以下状态：
（1）一致性/安全性（Agreement/Consistency）：所有非错误的节点能够对于事件（交易）的顺序达成共识，并对外提供相同的状态输出；
（2）可终止性/活性（Termination/Liveness）：所有非错误节点最终都能完成计算并输出一个值。
这样看起来，要想实现这么一个算法好像并没有那么困难，但实际上在通往共识的道路上我们需要跨过三座大山：时钟，容错和网络。
时钟
状态复制机中的事件是有先后顺序的，而我们需要解决的第一个问题，就是如何知道这些事件的先后顺序。这个问题最简单的解决方法是找一个统一的全球时钟，让所有的节点都按照这个时钟来标记事件发生的时间。然而这样的一个时钟在分布式系统中是不存在的，即使我们选中世界上某处的一个时钟作为时间源，不同节点访问该时钟所需要的时间都会不一样，这就依然会导致各节点对于事件发生的先后顺序产生不一样的观察结果。
分布式系统领域的计算科学家 Leslie Lamport 在他 1978 年的论文中提出了一种基于消息到达的先后顺序来判断事件顺序的方法。然而这种方法依然需要依赖各节点都拥有「较为一致」的物理时钟这一前提假设。而在现实情况中这一假设并不稳定存在，由于物理时钟的细微差别，再经过一段时间的运行后，各时钟之间都难免会出现一些偏差；而且最初的时间调整工作，也是一个比较困难的社会工程学问题。
所以 Lamport 的这篇工作的主要贡献，还是在于为我们清晰地指出了状态复制机模型中，缺少统一的时钟是一个重大问题，也是需要共识算法来解决的问题之一。
容错
状态复制机中的每个节点都是独立的，而节点出现错误的概率也是独立的。这些错误的原因可能是节点的网络出现问题，也可能是硬件问题，或者是什么停电了地震了之类的，都可能导致节点出错。
分布式系统领域对于错误有一个统一的定义：只要一个节点不能按照预先订好的协议进行正常的计算和消息的收发，那么它就算是出现了错误（Fault）。
而共识算法的另一个设计目的，就是容错（Fault Tolerance）：即让一个状态复制机系统能够在有节点出现错误的情况下，依然能够对状态达成共识，并对外提供统一的输出。
网络
状态复制机中的各个节点需要依赖网络来互相进行通信，发送消息；它们可以选择依赖现有的如 HTTP 或 RPC 协议进行通信，也可以选择自定义的协议进行。但无论选择哪种网络协议，现实世界中的网络并不总是牢靠的。发送出去的消息可能会出现延迟，丢失，传输可能中断。
分布式系统中对于网络条件的定义可以简单的分为同步和异步两种。同步指的是网络中的消息总是可以在某一个常数时间 t 内被传送到；而异步指的是网络中的传输时延，并不存在一个这样的上限。（理解同步和异步的概念很重要，接下来我们会经常用到它。）而这也是共识算法需要解决的问题，它需要网络的不稳定性考虑在内，并且保证系统依然能够达成状态共识。
稍微总结一下，共识算法是能使状态复制机网络中的各非错误节点对于交易的顺序达成共识（一致性），并总能在规定时间内对外提供输出（可终止性）的算法；并且它需要能保持系统在下列条件下依然能正常可靠的工作：
不存在全球统一的时钟
各节点可能独立出错
网络中传送的消息并不总是可靠
FLP 不可解定理
理解了什么是共识算法，也明白了共识算法需要解决的问题。我们还需要知道在共识算法领域一个非常重要的定理：FLP 不可解定理。该定理在 1985 年发布的论文 Impossibility of Distributed Consensus with One Faulty Process 中被首次提出，它的作者是 Fischer, Lynch, 和 Paterson 三人，所以也就被称为了 FLP 定理。
这个定理其实很简单：
「在这篇论文中我们证明了，即使只有一个错误节点的存在，任何共识算法都不可能在异步网络条件下实现可终止性。」
这是一个经过严格证明和同行审议的结论，事实上至今为止的许多尝试也都证明了这个理论的牢不可破。而这句话中的「任何」两字也好像已经为共识算法的大航海时代画上了一个句号，但显然坚韧的科学家们并不打算认输。
实际上，这个理论可以从另一个角度来理解：若是想要实现一个共识算法，我们只能在「异步网络条件」和「可终止性」这两者中进行权衡，二选一。所以这个定理是为后来出现的许许多多共识算法指明了方向，而这其中最早出现的，也是最经典的一个就是 Paxos。
Paxos 共识算法
Paxos 共识算法的首篇论文发表于 1989 年，主要贡献者还是 Leslie Lamport。Paxos 算法在之后的发展中衍生出了很多不同的改进版本，成为了一个协议族，大家比较耳熟的 Raft 也是其中之一。实际上直到今天 Google 和 Amazon 的系统里都仍然在使用这类算法。
我们着重理解一下 Paxos 是怎么绕过上述的 FLP 不可能定理的。对于大多数系统来说可终止性是不可妥协，否则对于用户来说整个系统根本就无法实现其功能。所以 Paxos 的选择在论文中假设网络条件为同步网络，即舍弃异步网络这一条件，从而保证可终止性。这就意味着它会在算法的实现中规定一个超时时间，一旦超过该时间没有收到消息，则继续进行下一步骤。
实际上与 Paxos 一样，后来的所有共识算法基本上都是选择去妥协网络条件而保有可终止性。不过需要注意的是 Paxos 共识算法是不能用于区块链中的，而其中的原因正是因为在区块链中，我们还需要考虑有名的拜占庭将军问题。
拜占庭容错和 BFT 共识算法
上面在介绍共识算法需要解决的问题时提到了容错，里面提到了两种节点：能正常收发消息的节点，和不能正常发消息的错误节点。但在更加实际的环境中，尤其是在区块链中，节点可能会做出比离线更过分的事情：它可能故意违反共识算法的规定发送错误消息。
这类节点也许会给不同的节点发送不同的消息，或者是几个节点联合起来共同发送错误的信息，尝试欺骗正常节点。在分布式系统中这个问题被叫做拜占庭将军问题（ByzantineGenerals Problem），在 1982 年被正式提出。这份学术工作依然是由 Leslie Lamport 领衔主演。在这篇论文中，这些会作恶的节点被称为拜占庭节点（Byzantine Node）。而一个能够在拥有拜占庭节点的网络中依然保证网络能达成共识的共识算法，就叫做拜占庭容错共识算法，也简称叫 BFT 共识算法（Byzantine-FaultTolerance Consensus Algorithm）。
上面提到的 Paxos 并不是 BFT 共识算法，即它只能在非拜占庭网络中正常工作；但在区块链中需要的显然必须是 BFT 共识算法。接下来，我们就可以结束背景故事的章节，正式开始介绍一些 BFT 共识算法了。
共识算法的网络假设
上面也提到了，大部分的共识算法都是通过对网络条件做妥协，通过假设不同的网络条件来绕过 FLP 定理的。这些网络假设，大致可以分成三类：
异步模型（AsynchronousModel）- 即网络中的消息延迟可以无限大
同步模型（SynchronousModel）- 即网络中的消息延迟小于某个确定的
部分异步模型（PartialAsynchronous Model）- 即网络在「好的一天」是同步的，在「不好的一天」是异步的。
异步模型
使用异步模型的代表作是 HoneyBadgerBFT，于 1983 年被提出。
使用异步模型就意味着它将需要对可终止性做出妥协，即它将无法在确定的时间内终止，而是有一个概率性的终止时间，即随着时间推移它会逐渐收敛，趋向于终止。这个算法理论上是可行的，但理论上它的终止时间是指数型的，而且消息复杂度是 o(n^3)，即每轮共识过程需要发送节点数量的三次方次的交易。这就意味着它将占用大量的带宽资源，而且终止时间可能会非常长。所以异步模型本身更偏向于理论一些，有着学术贡献，但在实战中基本很难应用。
同步模型
使用同步模型的代表是 LSP，也是由 Lamport 在 1983 年提出的。
同步模型的网络中存在着一个最大消息时延上限 t，通过充分运用这个 t，它可以在实现拜占庭容错的同时，获得共识的可终止性。比特币中使用的中本聪共识本质上也算是同步网络模型，它通过工作量证明限制了每一次共识的时间，并且可以容忍至少一半的拜占庭节点。
同步模型也有着一些限制。由于每轮同步都需要等待固定的时延，所以响应度（Responsiveness）会比较低：即共识的速度不会随着网络状态变好或变坏而调整，而是有着固定的共识时间。
部分异步模型
部分异步模型是最实用的网络假设模型了。大部分我们现在用的共识算法都是基于这个模型的，包括 PBFT，Tendermint，Hotstuf 等等。部分异步模型的一个特点是它通常会有个提议者（Leader），由 Leader 来在每轮共识开始时提出（propose）一个值，然后接着由其他节点针对这个值进行共识。
使用部分异步模型的算法都会比较复杂，需要经过严格的数学证明才能证明它的共识算法的特性（一致性和可终止性）。也正是因为这个原因，市场上的大多数共识算法其实都可以一眼就看出来是假的：它们要么没有严谨的数学证明，要么压根就没有解决共识算法该解决的问题，而仅仅沦落为散币的套路。
BFT 共识算法的安全性假设
设计 BFT 共识算法时需要做的另一种假设，就是安全性假设。
所有的 BFT 共识算法都会对拜占庭节点的数量进行假设，即要求拜占庭节点的数量占总节点的数量需要低于某一个值，否则算法就不能实现其功能。最常见的是 1/3 拜占庭容错，即算法可以容忍不多于三分之一的拜占庭节点。PBFT，Hotstuff 和 Algorand 等都采用了这一安全假设。这个分析仅限于使用投票（Quorum-based）的共识算法，有一些特殊的算法是无法用这种方法来描述安全性的，比如比特币中的中本聪共识。
需要注意的是，这里讨论的仅仅是 BFT 共识算法自身对于作恶节点的容忍度，并不代表区块链系统的安全性。而要实现区块链系统的安全性，我们还需要另外的机制，关于这个，我们将在最后一个章节中对此进行讨论。
几个经典 BFT 共识算法
DLS
DLS 这篇论文是第一个使用部分异步网络假设的 BFT 共识算法。这里大概解释一下这个算法大致是如何工作的，让大家有个概念：
（1）每一轮都得有个 Leader，每一轮开始后，各个节点首先进行一轮通信，将自己认为正确的 value 发布出去。
（2）如果 Leader 收到了 n-f 个相同的 value，它就再把这个 value 给所有的节点广播一遍。
（3）这时当各个节点收到这个 value 以后，它要将这个值「锁定」，然后再给所有的其他节点广播一遍。
（4）当 Leader 收到了来自 f+1 个节点的锁定后的 value 后，它就会将这个 value 作为最终值。
从这个过程还是可以比较直观的看出它是如何满足一致性的条件的，即至少有 n-f 个节点可以对于一个最终值达成一致。除此之外，一个共识算法还需要满足可终止性，这里就需要用到网络假设了：即部分异步网络中存在一个最大时延（在好的一天），而如果某个节点在这个时延时间内没有回复，我们就可以算它是掉线了，从而使网络整体的可终止性得到了保证。
PBFT 和 SBFT
PBFT 这篇文章认为之前的工作都过于理论而无法在实践中应用，所以提出了一种新的更实际的基于部分异步网络假设的算法。PBFT 可以在最多 (n-1)/3 的节点为错误节点（包括拜占庭节点）的条件下同时实现安全性和活性。它大致上是这么工作的：
（1）首先也需要有一个 Leader，Leader 会收到来自客户端的一个值
（2）Leader 将这个值广播到其他所有节点那里去
（3）每个节点收到后对这个值进行确认，然后将这个值广播给其他所有节点，并等待至少 2f 个其他节点的消息广播
（4）当收到至少 2f 个其他节点的消息时，对其中的值进行验证，然后再次广播，并再次等待至少 2f 个其他节点的消息广播
（5）如果再次收到了 2f 个其他节点的消息，并且其中的值无误，则确认该值为最终值
以上这个过程，在 Leader 没问题的情况下的消息复杂度是 O(n^2)，而当需要进行换届时则需要发送 O(n^3) 的消息。同样 PBFT 这个算法也可以通过数学证明来证明共识过程结束之后，至少有 n-f 个节点可以对于一个值达成共识，即实现了共识的一致性。
而 SBFT 主要是在 PBFT 的基础上做出了一些优化：主要是通过使用门限签名（Threshold Signatures）来减少了一层消息复杂度。
Tendermint
Tendermint 是 Cosmos 提出的一个 BFT 共识算法，它的特点是在 Leader Failure 的情况下依然是 O(n^2) 的消息复杂度。这得益于 Tendermint 在普通情况下和换届的情况下，使用了完全一样的共识流程，所以复杂度也相同。
Hotstuff
Hotstuff 是一个近几年最新提出的 BFT 共识算法，这份工作对之前 BFT 共识算法中的投票过程进行了抽象，从而得出了一个更加精简的共识算法。
Hotstuff 中使用了一个叫做 Quorum Certificate（QC）的概念，在某个区块拥有了足够数量的 QC 以后，该区块则可被判定为最终确定；同时算法规定了一个选择 QC 的逻辑，从而保证了共识算法的一致性；另外还设计了一个 Pacemaker 模块，保证了算法的可终止性。
从上面的表格也可以看出来这个算法拥有最小的消息复杂度；同时其精简的特性也使得其工程实现变得非常简单。值得一提的是 Facebook 的 Libra 里也使用了 Hotstuff 作为共识算法。
Algorand
Algorand 的创新之处在于它将密码学抽样的方法应用到了 BFT 共识算法中，使得在有大量节点参与的网络中也能实现快速共识。Algorand 使用了 VRF（Verifiable RandomFunction）这一工具，从所有节点中随机抽样选择一部分节点参与到共识过程中，从而让真正参与到共识中的节点数大幅降低。
它的共识过程大致分为两轮：首先各节点在本地通过运行 VRF 函数来计算自己是否可以成为该轮共识的 Leader；之后再通过同样的方式选出一个共识委员会（Commetee），运行一个快速的 BA（ByzatineAgreement）共识算法，来对 Leader 提出的区块进行投票共识，并将最终结果广播给网络中的所有节点。
Algorand 共识算法的有几个非常好的特点：
共识速度快：即使在有大量节点（一万起）的情况下，也能拥有极快的共识速度和极高的交易处理效率。
不会分叉：上面所提到的共识算法中，只有中本聪共识是可以在有大量节点的环境下使用的，但中本聪共识会不可避免的产生分叉，从而影响交易确认速度（一般需要等六个区块确认）；而 Algorand 不会产生分叉，也就是说所有交易都能在一个区块内得到确认。
抗网络分片：在网络中的节点收到网络层面的攻击时（比如 DDoS 拒绝服务攻击），可能会导致网络分片的产生，而一般的共识算法并不会将这种攻击考虑在其安全模型中；最新版的 Algorand 算法中则将这种情况考虑在内，并且实现了即使在网络分片情况下，也能实现共识，并且快速恢复。
这些都是在实际的分布式系统中，尤其是区块链系统中非常需要的特性。所以可以看出来，Algorand 是一个非常实用，非常适合区块链的共识算法。
区块链的安全性
到这里我们就已经学习了什么是 BFT 共识算法，了解了它的网络假设和安全性假设，并且也已经了解了几种经典的算法。然而，区块链还需要解决一个问题：上面的大多数 BFT 共识协议只能保证在拜占庭节点数量小于 1/3 的情况下正常运转，可一条区块链，尤其是无须许可的区块链（即任何人都可以加入成为节点），恶意节点的数量可能远远大于这个比例，这种情况下要如何才能保证共识协议和区块链的安全呢？
这时候就需要一些节点准入机制了。一般的节点准入机制，都会使用经济激励，来激励善良的节点加入共识过程中，并劝退那些作恶的节点，从而保证区块链网络中的节点们满足 BFT 共识算法所需要的安全性假设。
下面我们就简单介绍三个最常见的准入机制：PoW，PoC 和 PoS。要注意的是接下来关于准入机制的讨论就已经不在共识算法的范畴内了。他们是在区块链系统中，为了保证系统安全性，而必须配合共识算法而存在的机制。这也是为什么本质上 PoW 和 PoS 并不是共识算法。
工作量证明（Proof of Work）
工作量证明机制要求节点通过进行集中的运算从而计算出一个满足特定要求的数值（称为哈希值），并且可以大致推算出节点为了计算这个数值而花费了多少计算资源。该机制最早被应用在防止垃圾邮件这个应用上，不过它最有名的应该是在比特币中的应用了，下面我们就用比特币来举例解释 PoW 如何保证区块链的安全性。
比特币协议要求，一个节点如果想要作为节点参与到共识中去，那就必须要提交一个合格的 PoW 证明。比特币协议保证了每个 PoW 的计算大致需要花费 10 分钟，从而满足了中本聪共识需要的同步网络假设。这样，当一个节点想要参与到共识中时，他就必须要花费足够的计算资源才可以，在比特币中这些资源也被称为算力。对于一个敌手（Adversary）来说，如果他想要成功攻击比特币网络，成功的在中本聪共识的限制下强行让大家对他发送的恶意信息进行共识，他就需要持续花费大量资源，去控制大量的算力，这就是俗称的 51% 攻击。
安全性实质上是攻击成本和攻击收益的比值。在比特币这个例子中，根据挖矿市场算力的价格和比特币的市值，我们可以分别大致估算出 51% 攻击所需要的成本和成功后能获得的收益。将两者进行对比我们就能发现，过大的攻击成本和不成比例的攻击收益，足以构成劝退攻击者的城墙。也正是因为如此，PoW 确实能保证比特币系统的安全。
空间证明（Proof of Capacity）
PoC 空间证明是最近一段时间算是比较网红的节点准入机制。它的大致想法是使用硬盘的空间来替代 PoW 中的计算资源。节点可以提供一个证据来证明自己拥有多大的存储空间，而拥有较大空间的节点便可以拥有更多的参与共识的权利。
PoC 其实本质与 PoW 类似，只不过是将持续计算的成本换成了购买硬盘空间所需要的一次性成本。这种机制的好处是硬件设备不需要那么强的散热设备了，所以发出的噪音会小很多；同时主要成本从电价变成了单位存储空间的价格，让没有电力资源的人也可以参与其中，更加去中心化一些。
不过这并不是说使用 PoC 的项目都拥有与 PoW 相同的安全性，我们还需要看其共识算法是否可靠等等。
权益证明（Proof of Stake）
PoS 权益证明是另一种的经典节点准入机制。它算是将上面两种进行了进一步的抽象，直接通过节点所拥有或抵押的加密货币的数量来计算节点能加入共识权重。
比较有名的几个案例有 Delegated PoS 和 Bonding PoS，前者让所有持币者将币抵押给某个节点，从而使其成为 21 个共识节点中的一员；后者让所有节点各自为自己抵押代币，并按照抵押的代币的数量来计算加入共识的权重。
Algorand 也使用了 PoS 作为节点准入机制。其做法非常简单直观，直接根据各节点所拥有的代币数量作为其被 VRF 算法选中的权重：即账户上拥有越多的币，也就越容易被选中参与到共识中。Algorand 的创始人 Silivo Micali 教授将这种机制称为 Pure PoS，因为它不需要任何人去抵押代币，所有的代币都是随时流通着的。
作为理性人的用户们总是对于流动性有着偏好，所以对于 Bonding PoS 这种机制来说，并不会有很多人拿出币来进行抵押，这也就降低了区块链网络的攻击成本，对区块链和其上的资产的安全性构成了威胁。
而 Pure PoS 这种机制，并不要求用户抵押代币，网络中流通的所有代币基本上都将构成攻击成本，这就大大抬高了攻击的门槛，从而提升了 Algorand 平台和其上资产的安全性。
总结
我们从最基础的分布式系统这一概念出发，介绍了共识算法的定义和它需要解决的问题，并延伸到了 BFT 共识算法这一领域；同时大致讲解了几种最经典的 BFT 共识算法；最后对区块链的安全性这一话题进行了讨论。
在此之后，我们会对非常黑科技的共识算法 Algorand 进行更深入的讲解，来帮助大家进一步理解共识算法这一课题。
来源链接：mp.weixin.qq.com
区块律动 BlockBeats 提醒，根据银保监会等五部门于 2018 年 8 月发布《关于防范以「虚拟货币」「区块链」名义进行非法集资的风险提示》的文件，请广大公众理性看待区块链，不要盲目相信天花乱坠的承诺，树立正确的货币观念和投资理念，切实提高风险意识；对发现的违法犯罪线索，可积极向有关部门举报反映。
共识算法 硬核 比科普更高一层的知识普及内容，比如zk-SNARK技术解读、Sperax王教授的那些文章。