作者 | 蒋勇、文延、嘉文
责编 | 乔治
出品 | 区块链大本营（blockchain_camp）
##文末有福利哟
百花村旁有一座山叫区块链山，属村民集体所有。村外的A公司准备开发区块链山的旅游资源。A公司和村民委员会联合成立了百花旅游开发有限公司，签了股份制合作协议。以下是春节假期期间发生在村民李大和柳五之间的对话：
李大：关于旅游开发区块链山，村民委员会和A公司签约了。
柳五：那我们有什么好处？
李大：我们都是区块链旅游有限公司的股东了。
柳五：股东要干什么工作呢？
李大：关于区块链的开发的重要决定，股东都要投票的。
柳五：那可不成。春节后我要出去打工，在哪儿还不一定呢。哪有时间回来投票。
李大：不要紧，我们可以推选几个代表，比如王老师，他会一直留在村办小学教书，不会走的，而且人又可靠，讲信用。
柳五：我也推选王老师，代表我们在重大决议上投票。
......
在以上对话中，暗含了一种共识，在区块链世界，我们叫它委托权益人证明机制（DPoS）。搞懂共识机制很重要，因为它解决了区块链如何在分布式场景下达成一致性的问题，是保障区块链系统不断运行下去的关键。
从 PBFT 到 PoW，到 PoS，再到 DPoS，它们分别代表了怎么样的运作机制？分别适用于什么样的应用场景？都有什么优缺点？这篇文章通通告诉你。
本篇文章较长，主要包含以下8点关键内容，建议收藏！
1、分布式系统的一致性
2、Paxos 算法
3、Raft 算法
4、PBFT 算法
5、工作量证明 — — PoW
6、股权权益证明 — — PoS
7、委托权益人证明 — — DPoS
8、共识算法的社会学探讨
分布式系统的一致性
所谓一致性，就是指数据要完整、要同步。
比如，我们在网上下了个订单，付了款，商城系统会记录下这些数据，之后无论我们在哪里访问自己的订单，都能看到同样的结果，即便商城系统出了故障，那一般也会返回一个错误提示而不是给我们一个不一样的结果。
再比如银行，我们存了一笔钱进去，无论到哪里，我们查询银行账户的时候金额也不会变。也就是说，在这些系统中，数据的结果总是一致而同步的，即便这些系统的服务器不止一台，但都属于同一个中心集群，在内部是可以高效一致同步的。
区块链系统本质就是一个分布式应用软件。分布式系统的首要问题就是如何解决一致性的问题，也就是如何在多个独立的节点之间达成共识。要注意的是，这里说的是要达成一致，而没有说保证一定要结果正确，比如所有的节点都达成失败状态也是一种一致，说白了就是要成为一致行动人。如果是中心化的场景，达成一致几乎没有任何问题，但分布式环境并不是那么理想的，比如节点之间的通信可能是不可靠的、会有延迟、会有故障，甚至节点直接宕机。
而在无数个节点之间，如果采用同步的方式来调用，那等于失去了分布式的优点，因为绝对理想的一致性，代价通常是很大的。这样一个模型，通常要求不发生任何故障，所有节点之间的通信没有任何时差，这几乎就等于是一台计算机了，这样的强一致性往往意味着性能较弱。
历史经验表明，多路处理器和分布式系统中的一致性问题是非常难以解决的。难点在于以下几个方面。
- 分布式系统本身可能出故障。
- 分布式系统之间的通信可能有故障，或者有巨大的延迟。
- 分布式系统运行的速度可能大不相同，有的系统运行很快，而有些则很慢。
但是，一致性是设计分布式系统时必须考虑的问题。一致性问题历史悠久，而且臭名昭著。传统处理一致性问题的方法有两段式提交、令牌环、时间戳等，计算机专业的读者应该有所耳闻。本文将集中讨论与区块链相关的一致性问题和算法。
1、一致性问题
我们用状态机来解释一致性的问题。所谓状态机是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型，状态可以特指某个系统在某一时刻的数据变量，它具备以下几个特点：
- 状态总数是有限的；
- 任一时刻，只处在一种状态中；
- 某种条件下，会从一种状态转变到另一种状态。
比如进销存系统中某一个时刻的库存状态，银行系统某一时刻的账户状态等，对于分布式系统来说，就是指每个节点拥有的数据状态。假设我们有n台机器，位于不同位置的机器之间通过网络协同工作，所有机器的初始状态是一模一样的。给它们一组相同的指令，我们希望看到相同的输出结果，而且希望看到状态的变化也是一样的。比如机器甲的状态是从状态A到B再到C，而如果机器乙的状态是由A直接到C，这种情况就是不一致的。
总而言之，一致性要求分布式系统中每个节点产生同样的结果或者具备同样的状态，看起来就好像是一台机器一样，前提是没有一个中心服务器作为调度员，这对于分布在互联网上、不在同一个机房内、不属于同一个管理者的分布式系统来说，难度是很大的。出于系统的可用性考虑，对于分布式系统来说，我们一般希望具备以下能力。
- 分布式系统作为一个逻辑整体，不应该返回错误的结果。
- 只要系统里的大部分机器工作正常，整个分布式系统就能有效运行，这也是分布式系统应用的一个优点，抵抗单点故障。
- 系统的性能是可以横向扩展的，对于分布式系统来说，木桶原理不起作用。
- 分布式系统必须是异步的，也就是说每个节点可以按照自己的时序独立工作，没有全序的时间顺序。
要达到这些要求，可是不容易呢！从生活中我们也可以发现，即便有统一的命令指挥，尚且不一定能完全做到整齐划一，何况是没有这么一个指挥员呢！在互联网的场景中，任意一个节点的状态，我们都是没法去强力管控的，比如比特币节点，谁能控制网络中的那些节点呢！可能就是关闭了、断网了，甚至是一个恶意伪装的节点。一切看起来似乎无解。
然而实际上，很多时候我们对一致性的要求并没有那么迫切，在一定的约束下，可以实现所谓的最终一致性，也就是说在某个时刻系统达到了一致的状态。这个节点现在断网了，没问题，等恢复后跟上，通过其他节点来同步自己的数据；那个节点宕机了，也没问题，恢复后跟上。只要整个网络中绝大部分的节点都是正常工作的，整个系统总能在未来的某一个时刻达成数据状态的一致。
2、两个原理：FLP 与 CAP
FLP定理
叫 FLP 是因为提出该定理的论文是由 Fischer、Lynch 和 Patterson 三位作者在1985年发表的，取了各自名字的首字母作为定理名称。
看下定义：在网络可靠、存在节点失效（即使只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性算法。在这个原理的前提下，也告诉人们：不要浪费时间去为异步分布式系统设计在任意场景下都能实现共识的算法，在允许节点失效的情况下，纯粹异步系统无法确保一致性在有限时间内完成。
这个其实也很好理解，比如三个人在不同房间回答问题，虽然三个人彼此之间是可以通过电话沟通的，但是经常会有人时不时地开小差，比如 Alice 和 Bob 都回答了某个问题，Lily 收到了两者的回答结果，然后玩游戏去了，忘了回复，则三个人永远无法在有限时间内获得最终一致的答复。这个定理在理论上证明了此路不通，也就节省了后来者的研究时间。
CAP定理
CAP 定理最早是由Eric Brewer在2000年 ACM 组织的一个研讨会上提出猜想，后来 Lynch 等人进行了证明。我们还是先来看下定义：分布式计算系统不可能同时确保一致性、可用性和分区容错性，这三者不可兼得。通过定义我们可以知道，这是一个典型的不可能三角。那么这三个术语具体是什么意思呢？含义如下。
- 一致性（consistency）：所有节点在同一时刻能够看到同样的数据，即“强一致性”。
- 可用性（availability）：确保每个请求都可以收到确定其是否成功的响应，并且是在有限的时间内。
- 分区容错性（partition tolerance）：因为网络故障导致的系统分区不影响系统正常运行，比如1号模块和2号模块不能使用了，但是3号和4号依然能提供服务。
直觉上的论证很简单：如果网络分成了两半，我在一半的网络中给A发送了10个币，在另外一半的网络中给B发送了10个币，那么要么系统不可用，因为其中一笔交易或者全部两笔都不会被处理，要么系统会变得没有一致性，因为一半的网络会完成第一笔交易，而另外一半网络会完成第二笔交易。
既然不能同时满足，那么如果弱化对某个特性的支持呢？
弱化一致性
比如软件升级新版本后，过一段时间其他人才更新成功；再如网站更新内容后，浏览器也是刷新后才显示更新内容。很多时候对于实时的强一致性并没有很高的要求，生活中也有这样的例子：如果事情不那么紧急，就会发个短消息或者发个邮件，等对方看到了再处理；如果紧急的话，就直接打电话，所以说电话是一种强连接方式，不过很多朋友肯定不喜欢时不时地就有电话打进来吧。
弱化可用性
有些场合对一致性非常敏感，比如银行取款机，一旦系统故障就会拒绝服务，再如飞机上的控制系统，这个时候如果不能实时处理，那可是要命的。对计算机使用比较熟悉的朋友都知道，很多服务器操作系统都是不带图形界面的，只能靠命令行来处理，因为服务器要提高性能，保持可靠，会尽量避免加载不必要的模块，这也是一个牺牲可用性的例子。
弱化分区容错性
对于分布式系统来说，分区容错是必然的，幸运的是这种情况出现的概率并不是很大。如果真的是大规模的服务不可用，那无论是什么样的系统都是不能正常工作的。
计算机系统的设计，有时候跟生活中的场景是很类似的，你不得不做出一些妥协以便保证自己最想要得到的结果。区块链系统中，尤其是公有链系统，使用各种共识算法，优先的目的就是要保证整个系统的容错能力，这也是设计为分布式或者去中心结构的目的之一。
3、拜占庭将军问题
拜占庭将军问题的经典描述是：
拜占庭的军队是由小分队组成的，每个小分队由一个将军指挥，将军们通过传令兵来策划一系列的行动。有些将军是叛徒，他们会有意地妨碍忠诚的将军达成一致的计划。这个问题的目标是使忠诚的将军达成一致的计划，即使背叛的将军一直在诱使他们采用糟糕的计划。
已经证明，如果背叛的将军超过了将军总数的1/3，达成上述目标是不可能的。特别要注意的是，要把拜占庭将军问题和两军问题区分开。两军问题的模型要比拜占庭将军问题简单，并且设立的前提场景也有差别，我们来看一幅示意图：
如上图所示，在此问题模型中，假设有两支对抗的军队（一支为A军，一支为B军），这也就是所谓的两军。A军被B军隔开为两个部分，分别是左A军和右A军。从战斗力来说，A军的两个部分必须同时合力进攻才能打败B军，这就要求A军的左右两支分队必须要协商好进攻时间和一些进攻的其他约定，协商就意味着要通信，通过两边的互相通信来保持进攻指令的一致性。
那么问题来了，左右两边的A军要互相通信，就必须经过B军的区域，这就很难保证通信是畅通的，两边必须要不断发送回执来确认对方是否收到了消息，很显然，从理论上来讲，任何一次的回执都没法真正确认双方的消息接收是一致的。
比如左A军发送了消息给右A军，右A军接收到了并且发送了确认回执给左A军，可是确认回执被B军阻截了，此时左A军无法知道右A军到底收到消息没有，即便右A军的回执成功到达了左A军，可是若没有左A军的回执（左A军的回执也可能被B军阻截），右A军同样无法确认左A军到底收到回执没有。按照这种确认模式，只要有B军的阻截存在，左右两边A军就没法在理论上保证总是能达成一致的消息确认。
我们可以看到，两军问题的关键点在于：两点之间的信道传输不可靠。我们日常使用的大多数网络通信软件（支付、聊天、发送邮件等）其实都会面临这样的问题，通信过程发生在互联网，谁也没法保证中间经过的“B军”是可靠的，一般也只能通过有限次数的双方回执来确认消息的到达，这也是一个不得已的折中方案。
值得注意的是，在这个问题模型中，并没有去假设中间是否存在故意破坏者，也就是在两军的通信过程中，不考虑某一方可能叛变的情况。回到拜占庭将军问题，其考虑的主要问题在于通信的各方（不一定是两军，也可能是多军）存在故意破坏者或叛徒的情况下，大家如何来保持正确的一致性的问题。
拜占庭将军问题的复杂性，可以用计算机容错学里的概念来表述。
- 拜占庭容错：这是最难处理的情况，指的是有一个节点压根就不按照程序逻辑执行，对它的调用会返回随意或者混乱的结果。要解决拜占庭式故障需要有同步网络，并且故障节点必须小于1/3，通常只有某些特定领域才会考虑这种情况，通过高冗余来消除故障。
- 崩溃容错：它比拜占庭容错多了一个限制，那就是节点总是按照程序逻辑执行，结果是正确的，但是不保证消息返回的时间。不能及时返回消息的原因可能是节点崩溃后重启了、网络中断了、异步网络中的高延迟等。
- 遗漏容错：它比崩溃容错多了一个限制，就是一定要“非健忘”。非健忘是指这个节点崩溃之前能把状态完整地保存在持久存储上，启动之后可以再次按照以前的状态继续执行和通信。比如最基本版本的 Paxos，它要求节点必须把投票的号码记录到持久存储中，一旦崩溃，修复之后必须继续记住之前的投票号码。
- 崩溃停止容错：它比遗漏容错多了一个故障发生后要停止响应的要求。简单讲，一旦发生故障，这个节点就不会再和其他节点有任何交互，就像它的名字描述的那样, 崩溃并且停止。
4、共识算法的目的
在有错误的进程存在并且有可能出现网络分区的情况下，FLP 定理堵死了我们在传统计算机算法体系下提出解决方案的可能性。计算机科学家就想，如果我们把 FLP 定理的设定放松一点，问题是否有解呢？
由社会学和博弈论中得到启发，科学家尝试引入了以下机制。
- 激励机制（incentive）。比如，在拜占庭将军问题中给忠诚的将军以奖励。当背叛的将军发现背叛行为没有任何收益的时候，他们还有背叛的动机吗？这里引进了博弈论的概念：我们不再把节点或者说将军分成公正/恶意（忠诚/背叛）两方，认为每一个节点的行为是由激励机制决定的。正如两千年前中国诸子百家热烈争论的话题：人之初，性本善焉，性本恶焉？我们认为，人之初，性无善无恶。性的善恶由后天的激励机制决定。如果激励机制设置得当，考虑到每个节点都有最大化自己利益的倾向，大部分的节点都会遵守规则，成为公正的节点。
- 随机性（randomness）。在拜占庭将军问题中，决定下一步行动需要将军们协调一致，确定统一的下一步计划。在存在背叛将军的条件下，忠诚的将军的判断可能被误导。在传统的中心化系统中，由权威性大的将军做决定。在去中心化的系统中，研究者提出一种设想：是否能在所有的将军中，随机地指定一名将军作决定呢？这个有点异想天开的设想为解决拜占庭将军问题打开了一扇门。
根据什么规则指定做决定的将军呢？对应到金融系统里，就是如何决定谁有记账权。
- 根据每个节点（将军）的计算力（computing power）来决定。谁的计算力强，解开某个谜题，就可以获得记账权（在拜占庭将军问题里是指挥权）。这是比特币里用的PoW共识协议。
- 根据每个节点（将军）具有的资源（stake）来决定。 所用到的资源不能被垄断，谁投入的资源多，谁就可以获得记账权。这是PoS共识协议。
出于上面的考虑，科学家引入共识算法，试图解决拜占庭将军问题。分布式共识协议具有以下两点属性：
- 如果所有公正节点达成共识，共识过程终止；
- 最后达成的共识必须是公正的。
下面我们来谈谈共识算法的适用范围。区块链的组织方式一般有以下3种。
- 私有链：封闭生态的存储网络，所有节点都是可信任的，如某大型集团内部的多数公司。
- 联盟链：半封闭生态的交易网络，存在对等的不信任节点，如行业内部公司A、B、C。
- 公有链：开放生态的交易网络，即所有人都可以参与交易，没有任何限制和资格审核。
由于私有链是封闭生态的存储网络，因此使用传统分布式一致性模型应该是最优的；由于联盟行业链的半封闭、半开放特性，使用 Delegated Proof of ××× 是最优的；对于公有链，PoW应该是最优的选择。
常见共识算法一览表：
Paxos 算法
首先，Paxos 算法解决的是非拜占庭将军问题，也就是说仅仅是指分布式系统中的节点存在故障，但是不存在恶意节点的场景，在这种情况下如何达成共识。
1998年 Lamport 提出 Paxos 算法，后续又增添多个改进版本的 Paxos，形成 Paxos 协议家族。Paxos 协议家族有一个共同的特点就是不易于工程实现，Google 的分布式锁系统 Chubby 作为 Paxos 实现曾经遭遇到很多坑。
除了经典 Paxos（又名Basic Paxos），以下均为 Paxos 的变种，基于 CAP 定律，侧重了不同方向。
- Cheap Paxos
- Egalitarian Paxos
- Fast Paxos
- Multi-Paxos
- Byzanetine Paxos
Paxos 算法实在是太晦涩难懂，上面所列的 Paxos 算法分支就不详细介绍了。如果要想了解一下经典 Paxos 算法的最初描述，可以去看一下 Lamport 的论文《Paxos Made Simple》，在这个算法模型中，使用到了如下的角色：
看到这些角色，有没有觉得很像现代的议会制度。Paxos 正是这样的一个模型，当然在计算机中这些所谓的“人”一般就是指节点，这些角色可以是不同的服务节点也可以是同一个服务节点兼任。提案发出后，就要争取大多数的投票支持，当超过一半支持的时候，发送一半结果给所有人进行确认，也就是说 Paxos 能保证在超过一半的正常节点存在时，系统达成共识。提案过程还可以划分不同的场景，如下所示：
- 单个提案者 多个接收者：这种情况下，一致性容易达成，或者说肯定能达成，因为只有一个提案，要么达成，要么否决或者失败。但是这种情况下，这个唯一的提案者如果出故障，则整个系统就失效了。
- 多个提案者 单个接收者：这种情况下也容易达成共识，对于接收者，选择一个作为决议即可，当然这种情况也属于单点故障结构。
- 多个提案者 多个接收者
多对多这种情况，首先是避免了单点故障，但是问题也变得复杂了，既然提案和接收者都有多个，那以哪个为准呢？并没有特别玄妙的办法，既然多个在一起不好解决，那还是得回到单个提案者上去，只不过增加个规则选出那么一个单个提案者来，大致可以有如下的两个方案：
- 与第一种情况靠近，也就是想个办法选出一个提案者出来，约定在某一个时间段内，只允许一个提案通过，可以设置一些竞争规则或者按照一个时间序列的排列选择，总之最后会选出一个提案者。
- 与第二种情况靠近，允许有多个提案者，但是当节点收到多份提案后，通过某个规则选出一份提案，也就是仍然保持只接收一份，规则可以有各种，比如根据提案序号排列或者根据提案时间等。
实际上，在网络中，类似比特币这种，必然是属于多对多的这种情况，发送转账交易的节点不止一个，矿工不止一个，接收区块进行验证的节点当然也不止一个，Paxos 中为了解决这样的问题，引入了称为“两阶段提交”的方案。
所谓两阶段，就是“准备”和“提交”两个阶段：准备阶段解决大家对哪个提案进行投票的问题，提交阶段解决确认最终值的问题。上述这个过程中，可能会一直有新的提案出现，因此类似于比特币一样，分隔一下时间，比如每隔10分钟打包一次，而打包者只能有一个。
在提交阶段，如果一个提案者在准备阶段接收到大多数节点的回复，则会发出确认消息，如果再次收到大多数的回复，则保持原先的提案编号和内容；如果收到的消息中有更新的提案，则替换为更新的提案内容；如果没有收到大多数的回复，则再次发出请求，等待其他节点的回复确认。当接收者发现提案号与自己目前保留的一致，则对提案进行确认。
就个人的理解，这种做法如果是在一个相对私有的环境中或者网络环境比较好的情况下，效果会比较明显，实际上，所谓的收到大多数的回应，这也是节点自身的一个评估，因为节点并没有更好的办法去判断，到底算不算是大多数了，尤其是节点总数还不固定的情况下。
Raft 算法
由于 Paxos 太难懂、太难以实现，Raft 算法应运而生。其目的是在可靠性不输于 Paxos 的情况下，尽可能简单易懂。斯坦福大学的 Diego Ongaro 和 John Ousterhout 以易理解为目标，重新设计了一个分布式一致性算法 Raft，并于2013年底公开发布。Raft 既明确定义了算法中每个环节的细节，也考虑到了整个算法的简单性与完整性。
与 Paxos 相比，Raft 更适合用来学习以及做工程实现。下面，笔者将以通俗易懂的方式来描述这个过程。
百花村村长一人负责对外事务。比如，县和乡两级的公文来往，公粮征收，工务摊派，税收等。
Raft 是一个强 Leader 的共识协议。我们想象百花村是一个服务器集群，而这个集群的 Leader 就是村长，村里的每户人家（follower）对应一个服务器，每户人家都保存了一个数据副本。所有的数据副本都必须保证一致性。即上级官员下到村里视察时，从每户人家获得的信息应该是一样的。
百花村村长通过村户选举产生。谁得的票数多（简单多数）谁就当选村长。村长有任期概念（term）。任期是一直向上增长的：1，2，3，⋯，n，n 1，⋯。
这里要处理的是平票（split vote）的情况。在平票的情况下，该村村长选举失败，每户人家被分配不同的睡眠值。在睡眠期间的村户不能发起选举，但是可以投票。而且只有选举权，但是没有被选举权。第一个走出睡眠期的村户发起新任期的选举。
由于每户人家有不同长度的睡眠期，这保证了选举一定会选出一个村长，而不会僵持不下，不会出现每次选举都平票的情况。一旦村长产生，任何针对百花村的“写”（比如政府政策宣示，普法教育）必须经过村长。
村长每天都要在村里转一圈，让所有人都看见。表明村长身体健康，足以处理公务。
村长选举出来后，要防止村长发生“故障”，必须定期检测村长是否失效。一旦发现村长发生“故障”，就要重新选举。
村长接收到上级命令，该命令数据处于未提交状态（uncommitted），接着村长会并发向所有村户发送命令，复制数据并等待接收响应，确保至少超过半数村户接收到数据后再向上级确认数据已接收（命令已执行）。一旦向上级发出数据接收 Ack 响应后，表明此时数据状态进入“已提交”（committed），村长再向村户发通知告知该数据状态已提交（即命令已执行）。
下面我们来测试各种异常情况。
- 异常情况1：上级命令到达前，村长挂了。这个很简单，重新选举村长。上级命令以及来自外面的请求会自动过时失效，他们会重发命令和请求。
- 异常情况2：村长接到上级命令，还没有来得及传达到各村户就挂了。这个和异常情况1类似，重新选举村长。上级命令以及来自外面的请求会自动过时失效。他们会重发命令和请求。
- 异常情况3：村长接到上级命令，已传达到各村户，但是各村户尚未执行命令，村长就挂了。这种异常情况下，重新选举村长。新村长选出后，由于已收到命令，就可以等待各村户执行命令（也就是 Commit 数据）。上级命令以及来自外面的请求会自动过时失效。有可能，他们会重发命令和请求。Raft 要求外部的请求可以自动去除重复。
- 异常情况4：村长接到上级命令，已传达到各村户，各村户执行了命令，但是村长并没有收到通知，就在这时候村长挂了。这种情况类似上一种情况，新村长选出后，即可等待通知，完成剩下的任务。外部也会接到通知命令（已完成）。
- 异常情况5：在命令执行过程中，村长身体不适，不能处理公务。因为百花村没有收到村长的“心跳”，百花村的村户就会自动选举（当前任期 1）任村长。这个时候就出现2个村长。这个时候新村长就会接过老村长角色，继续执行命令。即使原村长身体康复，也将成为普通村户。
PBFT 算法
1999年 Castro 和 Liskov 提出的 PBFT（Practical Byzantine Fault Tolerance）是第一个得到广泛应用的BFT算法。在 PBFT 算法中，至多可以容忍不超过系统全部节点数量的1/3的拜占庭节点“背叛”，即如果有超过2/3的节点正常，整个系统就可以正常工作。早期的拜占庭容错算法或者基于同步系统的假设，或者由于性能太低而不能在实际系统中运作。
PBFT 算法解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。也许就是出于效率的考虑，央行推出的区块链数字票据交易平台用的就是优化后的 PBFT 算法。腾讯的区块链用的也是PBFT。
在 PBFT 算法中，每个副本有3个状态：pre-prepare、prepared 和 commited。消息也有3种：pre-prepare、prepare 和 committed。收到 pre-prepare 消息并且接受就进入 prepared 状态。收到 commit 消息并且接受就进入 Committed 状态。下面以一个有4个节点/拷贝的例子说明，这个网络内，仅允许1个拜占庭节点（此处设f=1）。
百花村小学举行百米赛跑比赛，3年级第一组的选手只有4个人：Alice、Bob、Cathy 和 David（简称 A、B、C、D）。为了节省钱，比赛并没有请裁判，而是在4个选手中随机挑出一个做裁判，假设是 Alice。众所周知，百米跑的口令是：“各就各位，预备，跑！”
这里“各就各位”就是 pre-prepare 消息，选手接受了命令就会脚踩进助跑器，而这一动作被其他选手看到，就会认为该选手进入了 prepared 状态。相当于发了一个 prepare 消息给其他选手。同理，预备就是prepare消息，选手接受了就是双手撑起，身子呈弓形，而这一动作被其他选手看到，就会认为该选手进入了 committed 状态。
- 假设A是公正的。Alice 得到老师示意，3年级第一组准备比赛。Alice 就喊：“各就各位！”老师的示意相当于一个外部消息请求。Alice 收到这个消息，给消息编一个号，比如编为030101号。必须编号，因为比赛有一个规则（假想），连续4次起跑失败，整个组都被淘汰。B、C、D同学收到口令后，如果认为命令无误，便都把脚踩进助跑器（拜占庭的那个人例外）。 而这一个动作又相当于互相广播了一个 prepare 消息。A、B、C、D 选手互相看到对方的动作，如果确认多于f个人（由于此处f=1，所以至少是2个人）的状态和自己应有的状态相同，则认为大家进入 prepared 状态。选手会将自己收到的 pre-prepare 和发送的 prepare 信息记录下来。
- 假设A是公正的。Alice 看到至少2个人进入 prepare 状态，Alice 就接着喊：“预备，跑！”。
- 接下来发生的事类似上一步：B、C、D 同学收到口令后（相当于收到 commit 消息），如果认为命令无误，便都双手撑起，身子呈弓形（拜占庭的那个人例外）。而这一个动作又相当于互相广播了一个 commit 消息。 A、B、C、D选手互相看到对方的动作，如果确认多于f个人（由于此处f=1，所以至少是2个人）的状态和自己应有的状态相同，则认为大家进入 committed 状态。当大家都确认进入 Committed 状态后，就可以起跑了！
- 假设A是不公正的。A就会被换掉，重新选一个选手B发令。这时候，由于所有选手都记录了自己的状态和接受/发送的信息。那些换掉前已经是 Committed 状态的选手，开始广播 commit 消息，如果确认多于f个人（由于此处f=1，所以至少是2个人）的状态和自己应有的状态相同，则认为大家进入 committed 状态。而对于换掉前是 prepared 和 pre-prepare 状态的选手，则完全作废以前的命令和状态，重新开始。
PBFT算法主要有以下3个优点：
- PBFT 算法共识各节点由业务的参与方或者监管方组成，安全性与稳定性由业务相关方保证。
- 共识的时延大约在2〜5秒，基本达到商用实时处理的要求。
- 共识效率高，可满足高频交易量的需求。
因为非常适合联盟链的应用场景，PBFT 及其改进算法因此成为目前使用最多的联盟链共识算法。改进主要集中在：
- 修改底层网络拓扑的要求，使用 P2P 网络；
- 可以动态地调整节点数量；
- 减少协议使用的消息数量等。
不过 PBFT 仍然是依靠法定多数（quorum），一个节点一票，少数服从多数的方式，实现了拜占庭容错。对于联盟链而言，这个前提没问题，甚至是优点所在。但是在公有链中，就有很大的问题。
工作量证明 PoW
工作量证明（Proof of Work，以下简称 PoW）机制随着比特币的流行而广为人知。PoW 协议简述如下：
- 向所有的节点广播新的交易；
- 每个节点把收到的交易放进块中；
- 在每一轮中，一个被随机选中的节点广播它所保有的块；
- 其他节点在验证块中的所有的交易正确无误后接受该区块；
- 其他节点将该区块的哈希值放入下一个它们创建的区块中，表示它们承认这个区块的正确性。
节点们总是认为最长的链为合法的链，并努力去扩大这条链。如果两个节点同时广播各自挖出的区块，其他节点以自己最先收到的区块为准开始挖矿，但同时会保留另一个区块。所以就会出现一些节点先收到A的区块并在其上开始挖矿，同时保留着B的区块以防止B的区块所在的分支日后成为较长的分支。直到其中某个分支在下一个工作量证明中变得更长，之前那些在另一条分支上工作的节点就会转向这条更长的链。
平均每10分钟有一个节点找到一个区块。如果两个节点在同一个时间找到区块，那么网络将根据后续节点的决定来确定以哪个区块构建总账。从统计学角度讲，一笔交易在6个区块（约1个小时）后被认为是明确确认且不可逆的。然而，核心开发者认为，需要120个区块（约一天），才能充分保护网络不受来自潜在更长的、已将新产生的币花掉的区块链的威胁。
生物学上有一个原理叫作“不利原理”（handicap principle），该原理可以帮助我们解释工作量证明的过程。这个原理说，当两只动物有合作的动机时，它们必须很有说服力地向对方表达善意。为了打消对方的疑虑，它们向对方表达友好时必须附上自己的代价，使得自己背叛对方时不得不付出昂贵的代价。换句话说，表达方式本身必须是对自己不利的。
定义可能很拗口，但是这是在历史上经常发生的事：在中国历史上，国家和国家之间签订盟约，为了表示自己对盟约的诚意，经常会互质。即互相送一个儿子（有些时候甚至会送太子，即皇位继承人）去对方国家做人质。在这种情况下，为取得信任而付出的代价就是君主和儿子的亲情，以及十几年的养育。
比特币的工作量证明很好地利用了不利原理解决了一个自己网络里的社会问题：产生一个新区块是建立在耗时耗力的巨大代价上的，所以当新区块诞生后，某个矿工要么忽视它，继续自己的新区块寻找，要么接受它，在该区块之后继续自己的区块的挖矿。显然前者是不明智的，因为在比特币网络里，以最长链为合法链，这个矿工选择忽视而另起炉灶，就不得不说服足够多的矿工沿着他的路线走。
要是他选择接受，不仅不会付出额外的辛苦，而且照样可以继续自己的更新区块的挖矿，不会再出现你走你的我走我的，是一个全网良性建设。比特币通过不利原理约束了节点行为，十分伟大，因为这种哲学可以用到如今互联网建设的好多方面，比如防垃圾邮件、防 DDoS 攻击。
PoW 共识协议的优点是完全去中心化，节点自由进出。但是依赖机器进行数学运算来获取记账权，资源的消耗相比其他共识机制高，可监管性弱，同时每次达成共识需要全网共同参与运算，性能效率比较低，容错性方面允许全网50%节点出错。
- 目前比特币已经吸引全球大部分的算力，其他再用PoW共识机制的区块链应用很难获得相同的算力来保障自身的安全。
- 挖矿造成大量的资源浪费。
- 共识达成的周期较长。
股权权益证明 PoS
股权权益证明（Proof of Stack，以下简称 PoS）现在已经有了很多变种。最基本的概念就是选择生成新的区块的机会应和股权的大小成比例。股权可以是投入的资金，也可以是预先投入的其他资源。
PoS 算法是针对 PoW 算法的缺点的改进。PoS 由 Quantum Mechanic 2011年在 bitcointalk 首先提出，后经 Peercoin 和 NXT 以不同思路实现。PoS 不像 PoW 那样，无论什么人，买了矿机，下载了软件，就可以参与。PoS 要求参与者预先放一些代币（利益）在区块链上，类似将财产存储在银行，这种模式会根据你持有数字货币的量和时间，分配给你相应的利息。用户只有将一些利益放进链里，相当于押金，用户才会更关注，做出的决定才会更理性。同时也可以引入奖惩机制，使节点的运行更可控，同时更好地防止攻击。
PoS 运作的机制大致如下：
- 加入 PoS 机制的都是持币人，成为验证者（validator）；
- PoS算法在这些验证者里挑一个给予权利生成新的区块。挑选顺序依据持币的多少；
- 如在一定时间内，没有生成区块，PoS 则挑选下一个验证者，给予生成新区块的权利；
- 以此类推，以区块链中最长的链为准。
PoS 和 PoW 有一个很大的区别：在 PoS 机制下，持币是有利息的。众所周知，比特币是有数量限定的。由于有比特币丢失问题，整体上来说，比特币是减少的，也就是说比特币是一个通缩的系统。在 PoS 模式下，引入了币龄的概念，每个币每天产生1币龄。比如你持有100个币，总共持有了10天，那么，此时你的币龄就为1000，这个时候，如果你发现了一个 PoS 区块，你的币龄就会被清空为0。你每被清空365币龄，你将会从区块中获得一定的利息。因此，PoS 机制下不会产生通缩的情况。
和 PoW 相比，PoS 不需要为了生成新区块而大量的消耗电力，也一定程度上缩短了共识达成的时间。但缺点是：PoS 还是需要挖矿。
委托权益人证明机制 DPoS
委托权益人证明机制（Delegated Proof of Stake，以下简称DPoS）机制是 PoS 算法的改进。笔者试着以通俗易懂的方式来说明这个算法。
假设以下的场景：百花村旁有一座山叫区块链山，属村民集体所有。村外的A公司准备开发区块链山的旅游资源。A公司和村民委员会联合成立了百花旅游开发有限公司，签了股份制合作协议。以下是春节假期期间发生在村民李大和柳五之间的对话：
李大：关于旅游开发区块链山，村民委员会和A公司签约了。
柳五：那我们有什么好处？
李大：我们都是区块链旅游有限公司的股东了。
由于村民都是股东，所有村民就是区块链山的权益所有人。
柳五：股东要干什么工作呢？
李大：关于区块链的开发的重要决定，股东都要投票的。
柳五：那可不成。春节后我要出去打工，在哪儿还不一定呢。哪有时间回来投票。
李大：不要紧，我们可以推选几个代表，比如王老师，他会一直留在村办小学教书，不会走的，而且人又可靠，讲信用。
柳五：我也推选王老师，代表我们在重大决议上投票。
王老师在这里就是委托权益人（也叫见证人）。DPoS 算法中使用见证人机制（witness）解决中心化问题。总共有N个见证人对区块进行签名。DPoS 消除了交易需要等待一定数量区块被非信任节点验证的时间消耗。通过减少确认的要求，DPoS 算法大大提高了交易的速度。通过信任少量的诚信节点，可以去除区块签名过程中不必要的步骤。DPoS 的区块可以比 PoW 或者 PoS 容纳更多的交易数量，从而使加密数字货币的交易速度接近像 Visa 和 Mastercard 这样的中心化清算系统。
李大：我们集体推举王老师的人，每年给王老师一点补偿，因为代表我们参加A公司的董事会也很花时间，挺累人的。
柳五：成啊！
权益所有人为了见证人尽量长时间在线，要付给见证人一定的报酬。
柳五：我还准备推荐陶大妈。文化高，人也好，也会一直留在村里。
李大：陶大妈身体不好，还是不要干这个差事了。
见证人必须保证尽量在线。如果见证人错过了签署区块链，就要被踢出董事会。不能担任见证人的工作。
村民选举出几个见证人后⋯⋯
柳五：这次怎么选出了赖大这家伙。这家伙一贯不干好事。我退出！
如果权益所有人不喜欢选出来的见证人，可以选择卖出权益退场。
DPoS 使得区块链网络保留了一些中心化系统的关键优势，同时又能保证一定的去中心化。见证人机制使得交易只用等待少量诚信节点（见证人）的响应，而不必等待其他非信任节点的响应。见证人机制有以下特点：
- 见证人的数量由权益所有者确定，至少需要确保11个见证人。
- 见证人必须尽量长时间在线，以便做出响应。
- 见证人代表权益所有人签署和广播新的区块链。
- 见证人如果无法签署区块链，就将失去资格，也将失去这一部分的收入。
- 见证人无法签署无效的交易，因为交易需要所有见证人都确认。
共识算法的社会学探讨
对于分布式系统的拜占庭问题，从计算机科学的角度，FLP 与 CAP 定理已经告诉我们无解。研究人员及科学家只有从其他地方寻找灵感。其实并不用花太多时间，他们就会发现，真实的人类世界就是一个分布式系统。如果科技畅销书《三体》的世界真的存在，那么太阳系和三体人所在半人马座的星球同时发生了爆炸，对于我们地球人而言，肯定是太阳系的爆炸先发生，因为光肯定是先到达地球。
而在三体人看来，他们会首先观测到半人马座的爆炸。对于同样的事件，不同的系统接收到事件的顺序是不一样的。不同的系统运行速度也是不一样的。再加上通信的信道是有问题的。在上面三体人的例子里，我们假设光线的传递是毫无障碍的。但是如果光线被传播途中的黑洞给吞噬了，消息永远接收不到怎么办？
比特币的天才之处在于参照人类社会的组织方式和运作方式，引入了共识机制。一个交易的成立与否，也就是分布式账本的记账权，经由特定共识机制达成的共识来决定。共识，是一个典型的社会学概念。本文中描述的各种共识算法，读者应该都有似曾相识的感觉。
PoW，我们可以叫它“范进中举”。范进用了大半辈子学习一种无用的八股文写作，如同比特币矿工用算力来算题，关键是算的题毫无意义。有朝一日，运气好，就可以有权打包所有他认可的交易。
PoS 是用户要预先放入一些利益，这是不是很像我们现实世界中的股份制。人们把真金白银兑换成股份，开始创业。谁的股份多，谁的话语权就大。
DPoS 机制，特别像我们的董事会。选举出代表，代表股东的利益。被选出的代表，一般来说，成熟老练、阅历丰富。不但能快速地处理日常事务，同时也能很好地保护股东的利益。
Paxos、Raft、PBFT 则很像我们生活中的操练队列，通过互相间的消息、口令来达成一致。每排的排头作为Leader，而每排的其余人都以排头为目标，调整自己的行动。瑞波共识算法，初始状态中有一个特殊节点列表，就像一个俱乐部，要接纳一个新成员，必须由51%的该俱乐部会员投票通过。共识由核心成员的51%权力投票决定，外部人员则没有影响力。
由于该俱乐部由“中心化”开始，它将一直是“中心化的”，而如果它开始腐化，股东们什么也做不了。与比特币及点点币一样，瑞波系统将股东们与其投票权隔开，因此比其他系统更中心化。
如果我们去看 Lamport 关于分布式系统共识的论文，就会发现论文是以议员、法案和信使作为阐述理论的样例，读起来不太像一篇计算机论文。
在此可以做一个总结了。传统的、纯正的计算机算法对分布式系统的拜占庭问题已经无处着力了（参考 FLP 与 CAP 定理）。所以在分布式系统的研究中引入了一些社会学的理论和概念，包括上述的博弈论，生物学原理，等等。我们可以把每一个计算机节点想象成一个单元。而计算机网络就是一个个单元组成的社会，我们该如何给这个计算机节点组成的社会设计规则呢，以保证：
- 少量节点太慢，或者故障崩溃的情况下，整个网络还能输出正确的结果；
- 整个网络的响应不能太慢。买一杯咖啡要等一小时是不可接受的；
- 计算机网络出现分区（网络上的某些节点和其余节点完全断开）的时候，仍然能够稳定输出正确的结果；
- 整个系统能够稳定地运行，输出稳定的结果。
我们可以借鉴人类历史上的社会机制、激励机制，达成上述的功能。我们有理由相信，互联网或者分布式网络系统与现实的社会运作有着千丝万缕的联系，正因为如此，区块链的发展并不是冥冥之中的产物。
如今，整个区块链生态内谈论最多的共识算法无非是 PoW 和 PoS。PoW 存在速度慢、耗能高、对环境不友好以及易受规模经济影响等问题，而 PoS 则被认为是很好的替代解决方案。
