达成共识的英文原文是 come to consensus。达成共识以后，也未必代表数据是完全一致的（Raft 算法中 leader 发出 append log 的 commit 命令即算达成共识？但如果中途数据丢失，则还是会有子节点数据不一致）。

在分布式环境下，多个系统协同工作的效率，受制于系统交叉点的性能。在需要达成分布式共识的场景下，分布式共识算法在保证系统安全性的同时，限制了全系统横向扩展的性能提升。

根据环境的不同，可以应用不同的共识算法。

在完全互信的环境下-私有链、私有的分布式数据库，节点之间可以使用 Paxos 或者 Raft 这种 leader 相对固定的算法。

在有限互信的环境下-联盟链，可以使用 PBFT。PBFT 算法是依据确定性的投票（可能是漫长的投票，也可能进入死循环）达到确定性一致的算法。

在没有互信的情况下-公有链，可以使用 POW/POS/DPOS/POA。这类算法是基于概率得到正确的最终一致性，性能比 PBFT 要稍微好点。

最好的共识算法应该模块化，例如 Corda 中的 notary，Hyperledger fabric 中的 solo/kafka。

FLP Impossibility（FLP 不可能定理）

FLP 是三个作者的名字。

FLP Impossibility（FLP不可能性）是分布式领域中一个非常著名的结果，该结果在专业领域被称为“定理”，其地位之高可见一斑。该定理的论文是由Fischer, Lynch and Patterson三位作者于1985年发表,之后该论文毫无疑问得获得了Dijkstra奖。

顺便要提一句的是，Lynch是一位非常著名的分布式领域的女性科学家，研究遍布分布式的方方面面，对分布式领域有着极其卓越的贡献，其著有”Distributed Algorithms”一书，书中有非常严谨而简洁的逻辑讨论了许许多多的分布式算法。

FLP给出了一个令人吃惊的结论：在异步通信场景，即使只有一个进程失败，也没有任何算法能保证非失败进程达到一致性！

因为同步通信中的一致性被证明是可以达到的，因此在之前一直有人尝试各种算法解决以异步环境的一致性问题，有个FLP的结果，这样的尝试终于有了答案。

FLP证明最难理解的是没有一个直观的sample，所有提到FLP的资料中也基本都回避了sample的要求。究其原因，sample难以设计，除非你先设计几种一致性算法，并用FLP说明这些算法都是错误的。

只要记住这样一个结论即可：在异步通信场景，即使只有一个进程失败，也没有任何算法能保证非失败进程达到一致性！

换言之，Paxos 为代表的协议，都只能保证极大概率不出错达到一致性，不能保证真正的一致性。

可信环境下的共识算法

可信环境下，节点只会故障（fault），不存在恶意节点（corrupt），可能存在丢失消息或者不响应，不会出现恶意的错误信息。

Paxos 算法

Paxos 算法假定有一个全局能够自动生成递增消息编号的服务。

Paxos 算法把角色分为 proposer、acceptor 和 learner。这三种角色都可以有多个节点以避免单点故障，Paxos 算法的目的就是如果多个 proposer 在异步网络环境下有多个提案，怎样让 proposer/acceptor 最终选出一个，然后让 learner 知晓。

Acceptor 可以应对两种请求：

  • prepare 请求，承诺一个 proposer 不再accept编号低于某个值的提案，并返回目前批准最大编号提案的值。
  • accept 请求，如果没有 prepare 过编号大于 N 的提案，而 N 又是可以被批准的（也就是恰好足以成为最大的编号的），则可以 accept 这条提案，这个proposer 应该就可以结束 prepare 和 accept 了，由其他 proposer 继续这个两阶段的旅程，直到这个过程终止。

proposer 就是不断地先向 majority 发出 prepare 请求，然后如果得到了一个 chosen 值，就不断地持续地向 majority广播 chosen 值，直到它被majority accept。acceptor 就在 proposer 逐渐变得一致的过程中，达到一个有 majority 的批准值。

如果两个 proposer1 完成了消息1 prepare，acceptor 又 prepare 了一个更高的 proposer2 的消息2，而会直接拒绝掉 proposer 1 的 accept 消息1，于是proposer 1 提出消息3（这个 retry 机制很有意思，因为 proposer 被拒绝以后并不是直接去询问当前高序号的值，而是用一个更高序号的值去 prepare 来询问 ），让 proposer 的消息2 accept 又失败，于是就产生了活锁。Paxos 无法终止，因为恰好每个 prepare 和 accept 的间隙都被对方给否定掉了。虽然 lamport 证明了在数学上算法应该可以收敛，但受环境所限，并不一定在现实中就必然会收敛。

Raft 算法

论文中文版

Raft 简化 Paxos 的地方在于，它不再是一个多轮多 proposer 达到一致的算法，而是先用 leader election 来制造单一的 trust source，然后由统一的 trust source 发号施令，确定分布式场景下数据的顺序和对错的算法。这个 leader 也避免了活锁的存在。Raft 只是更好理解，属于Paxos 的一个特例场景变种，但并不更容易实现。

Raft 是先做 election，再做 log replication 的。

Raft 有三种角色，follower、candidate、leader。如果 follower 没有收听到 leader 的心跳，那么它就可以假设 leader 不在了（即使它只是因为处在一个 network partition 里，接收不到 leader 的 heartbeat），转变为 candidate，自行发动选举，能不能选举完成，要看自己所在的分区是不是多数分区。系统总是从一群 term 为0 的 follower 开始的，所以系统初始化的时候就会直接开始一场选举。

选举有两个超时。

一个叫election timeout，就是 follower 忍受 leader 不发心跳给自己，变成 candidate 的时长。不同的 follower 的忍受时长不一样，在150ms 到300ms 之间徘徊， 这就导致了有的 follower 变成 candidate 的时间早，有的变成 candidate 的时间短。follower 变成 candidate 第一件事就是选自己，然后把 vote request 发给其他节点，其他节点即使现在还是 follower/candidate 状态，收到 vote request，如果没有投过票，也会立即进入下一个 term 的投票，直接把票投给第一个给自己发 vote request 的节点，自己依然保持 follower/candidate 状态。任意一个 candidate 收到定制拓扑结构里面的多数投票就会自封为 leader。因为其他节点已经投给了别人，所以他们只能乖乖做 follower，接收他们选的 leader 发送过来的信息。

另一个 timeout 叫heartbeat timeout。leader 发送的信息叫做 Append Entries（类似 Kafka 的 appending log），这些信息本身要跟随心跳信息被发送，follower 本身也要发送 response 给 leader。

如果节点出现了一个 term 的选举平局，则这一轮已无法再投票。需要等到下一轮超时，再投一次，产生自封的 leader。感觉上这里就会产生两个问题，首先，自封的 leader 完全可以自称，这就不能解决 bft 问题，其次，这个选举的平局几乎可以无限地进行下去。

一旦一个客户端往 leader 发信息，则 leader 会先在自己的 log 上预 append，然后把 log 通过消息发送给 follower，follower 也都预 append 以后发送 acknowledgement 给 leader。leader 收到多数 acknowledgement 以后就在本地完成提交，然后先把 response 发给客户端，然后告知 follower 把预提交的信息完全提交上去（真 commit）。这也是一个两阶段提交的步骤，但和传统的两阶段提交的算法不一样的是，它的 coordinator 不是固定的，它收集 acknowledgement 并不是收集全部的，而是收集 majority，这就不能保证强一致性。它的最后发送真 commit 本身，也是像传统的两阶段提交算法一样，是不看最后的 acknowledgement 的。难道这些 log 本身是编好序号的？

如果真的出现了网络分区，则小分区的 leader 即使不知道新的 leader 已经产生了，还能以蒙在鼓里的形式继续跟小分区里的 follower 继续通信，也无法真的更新自己的 log 和 follower 的 log，因为它收集不到足够多的 acknowledgement。

假设系统已经有了 leader，则 leader 有自己的任期（term），高任期的 leader 会自动打败低任期的 leader。leader 一定要定时地发送自己的心跳数据给 follower，以告知它们自己这一任 leader 还活着，不然系统中会产生新的 leader。

在有限互信的环境下的共识算法

Bazantine General Problem 问题，是1982年 Leslie Lamport 提出的一个解释一致性问题的虚构模型。

对于拜占庭问题来说，假如节点总数为 N，叛变将军数为 F，则当 N >= 3F + 1时，问题才有解，即 Byzantine Fault Tolerant (BFT) 算法。

据说有一种最直观的理解是，假设 N 为3，而 F 为1。A、B、C三个人里面有C会说谎，A、B 都向其他人广播1，而 C 广播 0，则 A 会受到一个1 和 0，B 也会收到一个 1 和 0，A 和 B 都无法判定谁是叛徒。可是 A 在收到1和发出1的时候，难道不能认定自己的1是多数派么？

PBFT 全称是 Practical Byzantine Fault Tolerant，由 Castro 和 Liskov 在1998年提出，是第一个得到广泛应用的 BFT 算法，只要系统中有2/3的节点是正常工作的，则可以保证一致性。

超级账本相关项目大量采用 BFT 相关算法。

Fabric 采用的是可插拔共识算法架构，目前包括三种具体算法：

  1. No-op (consensus ignored)（无操作共识机制？）
  2. SBFT（Zyzzyva 的实现，还未到来）
  3. SIEVE (an enhanced version of classic PBFT)（还未到来）。

传统的 BFT 算法的时间复杂度是 O（NN），[平方复杂度的算法导致它极难横向扩展。因为 n 个节点，每个节点都要广播给所有其他节点知晓自己的信息，必然导致 nn 次通信]4。

在没有互信的情况下的共识算法

这些不同的算法，可以说都是在公有链上的挖矿算法。挖矿有几层含义：

  • 替别人产生了价值（公允的记账）。
  • 为自己挣得了奖励。
  • 能够在挖矿过程中梳理交易，防止双花攻击。

这些算法本质上都是博弈算法。总是要让参与出块决策的参与者们拿出一些高于某个门槛的抵押物，在算法中靠抵押物和少数服从多数的认同达到共识和服从。

PoW（Proof of Work）

PoW 的抵押物是电。每个矿工拿出算力出来寻找随机数，找到随机数的矿工用自说明的区块向其他矿工展示自己消耗的算力，其他矿工通过重复演算确认区块的合法性。

PoW 是中本聪最初设计出来，让每一个比特币钱包的拥有者能够参与整个系统的决策机制-也就是说，他没有料想到职业矿工、加强型矿机甚至矿池的出现。即使是发生了节点故障，或者有人作恶，只要有超过百分之五十一的节点能够健康工作，这个网络就是健康的。

PoW 到现在为止暴露出的弊端是：

  • 中本聪设计 PoW 的构想里面，节点和算力是均匀分布的，网络最终会发展成最大限度的去中心化民主制度。但现实之中，大型矿池的出现，使得几个利益集团可以操控整个网络的发展。
  • 太耗电了。
  • 事实上导致了全网真正确认的速度变得非常慢。因为算力竞赛的胜者，要等待全网中大部分非信任节点把被挖出来的区块加入他们的主 链条（canonical chain）中，还要防止分叉出现。即使横向扩展网络中机器的规模，也无法解决这个问题。

PoS（Proof of Stake）

PoS 是个权益证明算法。

它是要求公有链上的 validator 把他们的经济权益抵押在链上的共识算法。

在 PoS 的算法下，一系列的 validator 提议区块，并给区块投票。投票的权重由他们抵押在这次投票里的权益决定。

任何持有以太坊基本货币的人都可以成为 validator。他们只要发起一个特殊的事务把他们的以太币锁起来，然后就可以开始共识算法了。

从算法的角度来看，主要有两类 PoS 算法：

  • 基于链的
  • BFT 风格的

基于链的PoS 里，算法在每个时间槽伪随机地选择一个 validator。由这个 validator 来指定下一个区块是怎么样的（通常基于已知的最长链的最后一个区块）。那么投票在哪里呢？所以这种算法是不够安全的。

BFT 风格的 PoS 里，validator 被真正随机地被选出来提议区块，但哪个区块被加到主链上，是由多轮投票决定的。这个算法才是现在以太坊的 PoS 基础。

PoS 相对于 Pow 的优点是什么？

  1. 省电。
  2. 不需要增发新的货币-实际上现在很多 ICO 里都留有货币增发的口子，就是为了不断激励矿工。
  3. 可以从博弈论机制设计的角度来防止中心化的卡泰尔出现。

PoS 是如何融入传统的拜占庭容错研究（成果）的？

其实 PoW 是依赖于同步网络模型的。网络延迟越高，容错性越低。如果网络延迟等于出块时间，整个系统的容错性降为0。

Proof of work has been rigorously analyzed by Andrew Miller and others and fits into the picture as an algorithm reliant on a synchronous network model. We can model the network as being made up of a near-infinite number of nodes, with each node representing a very small unit of computing power and having a very small probability of being able to create a block in a given period. In this model, the protocol has 50% fault tolerance assuming zero network latency, ~46% (Ethereum) and ~49.5% (Bitcoin) fault tolerance under actually observed conditions, but goes down to 33% if network latency is equal to the block time, and reduces to zero as network latency approaches infinity.

PoS 算法更加贴近拜占庭共识模型。

PoW 算法是 AP 的算法。BFT 风格的共识算法更加贴近一致性（依然保证可用性）。

什么是利益无关问题，以及如何解决它

在 PoW 模型下，一个利益相关者不可能给每个区块都下注，因为分散下注需要分散电力，这在经济上并不划算。但如果 PoS 模型不做一些准备措施，那么在分布式环境下下注也可以以以类似双花攻击（甚至是多花攻击）的方式存在，这样的行为如果不受到惩罚，实际上是给产生共识制造障碍。

第一种解法，Slasher。不允许一个 validator 试图同时创建两条链。但这要求 validator 在分叉发生前就选好，而且两条分叉链上的 validator 都必须一样。

第二种方法就很简明了。猜对链条的人得到 +R 的奖励，猜错的人受到 -F（可以等于 R） 的惩罚。

所以这和拜占庭容错理论有什么关系？

传统的拜占庭理论可以证明，“如果一个系统有安全鼓掌，那么最少三分之一的节点是有过失的”。而 BFT 风格的 PoS 算法则试图证明，“如果一个系统有安全鼓掌，那么最少三分之一的节点是有过失的，而且你知道哪些节点有过失，即使你在故障发生时不在线”。（译者按：这简直就是记名投票）。

PoS 技术说明的英文和中文版本。

看了那么多 PoS 到底是怎么工作的呢？

PoS 里的 validator 不再被称作 miner，而被称作 forger。

在所有货币都预售了的系统里面，PoS 是没有区块奖励的（挖矿有点名不副实了），只赚手续费。

所有人如果想成为 validator，可以加入一个 validator 池，然后总会被选上：

“You automatically get inducted after some time,” explained Vitalik Buterin himself on a post shared on Reddit.

Casper 是带有惩罚机制的 PoS 算法。系统会挑出它认为做了坏事的 validator，扣除它的准备金赌注，并取消掉它成为 validator 的资格（这有什么意义？）。具体步骤：

The validators stake a portion of their Ethers as stake.
After that, they will start validating the blocks. Meaning, when they discover a block which they think can be added to the chain, they will validate it by placing a bet on it.
If the block gets appended, then the validators will get a reward proportionate to their bets.
However, if a validator acts in a malicious manner and tries to do a “nothing at stake”, they will immediately be reprimanded, and all of their stake is going to get slashed.

恶意攻击被称作Malicious manner 或者 Byzantine manner。

在出现惩罚措施以前，nothing at stake 问题使得攻击 PoS 网络变得很简单，惩罚措施试图使得全网的共识更加像 PoW。在 PoS 中，51%攻击的必要条件是，一个人必须有全网51%的货币。

Casper 的两种版本 Casper FFG 和 Casper CBC，详情见本文。

Casper 和 Pow 一样，都会造成富者愈富-Pow 本身已经让很多矿池成为 cartel
了。

PoA（Proof of Authority）

PoA 算法指的是网络里有些预先批准节点（sealers），新的签名者 加入网络必须经过老的 sealer 批准。这样其实就制造了一个严格控制的网络环境。为了防止坏节点破坏网络，一个签名者只能签署一定数量的连续区块（(floor(SIGNER_COUNT / 2) + 1)）中的最多一个区块。换言之，心怀恶意的攻击无法防御，只能被这种设计有限控制。

以太坊的 PoA 算法被称作 Clique 协议，协议的描述在这里，它还产生了一个Rinkeby test network。这个测试网络每15秒出一个块，和主网的ethash想要达到的目标一致。

是不是 PoS 永远不能升级到 PoA 了？PoA 是不是就是为了联盟链设计的？

另外一篇描述了 Clique 用法的文。

接下来我们来好好描述 Clique 的具体细节：

授权（即签署）区块

要为网络签署一个区块，一个签名者要给一个包含一切数据（偏偏不包含签名本身）的哈希值签名。这这意味着这个哈希值包含了块头部的一切字段（包括nonce和mixDigest），以及除了65字节后缀以外的 extraData。这些字段按照黄皮书里定义的顺序被散列（译者按：类似比特币的试算算法）。

这个哈希值用标准的secp256k1曲线（椭圆曲线）算法签名，得到的65字节签名就作为65字节的拖尾后缀被嵌入extraData。

为了保证心怀恶意的签名者（丢失了私钥）不能对网络造成伤害。每个签名者被允许签署SIGNER_LIMIT个连续区块中的最多一个。区块顺序不是固定的，但循序签名区块比不循序签名区块权重更大。

授权策略

只要签名者遵守上述规范，他们可以授权和散播他们认为合适的区块。下面的建议策略会减少网络通信和小分叉，所以它是建议特征：

  • 如果一个签名者被允许签署一个区块（他在授权名单上而且最近没有签过名）。
    • 计算下一个区块的最佳签署时间（父区块 + BLOCK_PERIOD）。
    • 如果签名者是循序的，等到那个确定时间，直接签署和广播区块。
    • 如果签名者是不循序的，按照rand(SIGNER_COUNT * 500ms)延迟签名。

这个小策略可以保证循序签名者（它的区块权重更高）相比起不循序签名者有轻微的签署和传播优势。也因此这个设计也允许通过提升签名者的数量得到轻微的（性能）扩展。

从以上策略可以看出，实际上 PoA 里依然有可能产生分叉，除非使用严格的单账户 PoA。

为什么要标准化 PoA

PoW 在无价值网络上是不安全的，PoS 还远未实现。PoA 作为一个过分简单的解，就被实现出来挽救测试网络了。

PoA 可以被认为是 PoW 的简化版-而不是 PoS 的进化版（以前我想错了），它直接授权了一群主，让他们尽量按顺序出块，当然这种设计（scheme）下依然有分叉的可能。

Clique 算法的相关文献在这里。

DPoS（Delegated Proof of Stake）

旧的共识算法无法解决交易性能问题。

DPoS 使用见证人（witness）的机制来解决中心化和性能问题的矛盾。

传统的区块链共识算法有一个很大的弊病，就是需要在大规模范围内被验证非出块节点验证过。DPoS 争取把收集事务、生成区块、验证区块这一系列事件局部化到小范围的少量可被信任节点里，特别是不需要再等待若干个区块累加确认时间。

DPoS 是受控中心化的，每个客户端最终可以通过公平选举，决定哪些节点成为代表绝大多数用户的代理人。

DPoS 背后的理性逻辑（Rationale）是：

  • 使权益所有者能够通过投票决定记账人
  • 最大化权益所有者的红利
  • 最小化保证网络安全的消耗
  • 最大化网络的性能（可能诚实节点之间通过架设专有网络进行通信）
  • 最小化运行网络的成本（可能诚实节点之间通过架设专有网络进行通信）

每个权益所有者通过投票决定区块的签名验证者，任何一个拥有超过1%投票的人都可以参与到董事会。所有的代表构成一个“董事会”，轮流签署区块。如果一个董事错过了签署区块的机会，客户会自动把投票给予其他人。最终，这些错过签署机会的董事会被取消资格，其他人就可以加入董事会。董事会成员会收到少量代币作为奖励，用来激励在线时间和参与竞选。每一个董事必须要将单个区块平均奖励的100倍作为保证金，从而确保其至少99%的在线时间。

EOS 的候选代表出自各大研究所、大学、交易所等地方，是 well-known 节点。

不从普通用户中选择见证者的原因：

  • 普通用户大部分时间不在线
  • 攻击者可以使用其权益控制网络，而不经过其他人的认可
  • 由于没有挖矿，在去中心化网络中生成随机数变得不可能。

现实工作中，普通用户是通过钱包中的投票选项来选择见证者的。在全网出现不诚实区块的时候，正常的钱包可能在交易以前强制举行一轮新投票。但具体的投票过程，没有具体文献披露出来。

假设手续费等于验证成本，则全网只能有一个验证节点，蜕变为中心化节点。假设手续费100倍于验证成本，则全网可以拥有100个去中心化节点。这个平均成本核算说明了现在比特币挖矿并不 rational，需要依靠矿金激励的支持。

见证人干了什么：

  • 生成区块和广播区块的权威（类似 authority）。
  • 负责用自己的私钥对收集来的 P2P 网络中的合法交易进行验证、打包和签名。
  • 在比特股实现中，见证人的排列顺序是随机的，因为网络拓扑结构不固定，而且网络连通性没有保障。而 EOS 的实现则是定制拓扑的 round robin 结构，因为它是确定 well-known 节点的，每个出块者都可以跟下一个出块者直连以防块扩散速度不足。而且这种定制的 round robin 顺序可能还会被洗牌算法所改变。

经典的出块过程：

在比特股/Steemit的时代，3秒出一个块，EOS 的时代，可能1秒就出一个块。 出块时间深受假定的网络延迟模型影响。

EOS 的出块过程里面，如果一个见证者的出块失败了，该 slot 的指定区块会被 skipped 掉，而不是由其他出块者补上。

理论上每个 transaction 都包含对一个最近区块的交易 hash 值（这也就意味着 transaction 必须有时效性了，其他区块链的区块里是没有这个限制的）。这也就意味着，每个签署人签署一个新区块，都会增强对历史交易的认定。这被称为 TaPoS（Transaction as Proof of Stake）。它可以：

  • 防止跨分叉的事务重放。
  • 通知网络某个用户和它们的权益在某个特定分叉上。

按照 BM 在视频里的说法，在 DPoS + TaPoS 双重防御下，也需要三分之二的区块生产者都在老的区块上产生新的区块，最终确定性(finality)才能被保证，这至少需要45（3*15）秒。这个数字为什么和 BFT 要求的比例一模一样？按照 BM 在视频里的说法，只需要三分之一的节点是非拜占庭恶意节点，网络就不会被拜占庭恶意攻击攻破。

DPoS 对于攻击的抑制

  • 不管是因为掉线，还是因为有意拒绝，如果见证人没有签署它应该签署的区块，它将被解职，并是去未来的稳定预期收入。因此不诚实的委托代表只有在明确有其他利益诉求时才会选择放弃区块生成。
  • 见证人无法签署无效的交易，因为交易需要所有见证人都确认。

在现实世界里，通常需要11个或者21个当选见证者，候选见证者可能需要100个。

以上内容参考《区块链核心技术：委任权益证明算法DPoS》和《缺失的白皮书：DPOS共识算法工作原理及鲁棒性根源分析
》。我们都知道区块链应该能够防止双重支付攻击，但这篇文章《http://www.8btc.com/dpos_bitfarm》也提到要防止拒绝服务攻击。