云妹导读：
2008年10月31日，中本聪发布比特币白皮书；2009年1月4日2时15分5秒(北京时间)比特币创世块问世。不鸣则已，一鸣惊人。区块链技术就是这样来到了人类的世界，成为当今最热门的一项尖端科技。与许多新兴技术一样，它的发展道路并不是一帆风顺的，但区块链技术从未停止脚步，其底层基础平台层出不穷。
区块链其实就是一种特殊的分布式数据库。各个区块链平台最大的差异集中体现在对共识算法的优化和变革，而区块链与传统分布式数据库的共识层决定了两者的上层应用，区块链中大多以BFT共识算法来解决各个节点在互不信任的情况下达成共识，而传统的分布式数据库一般都建立在各节点不存在作恶的情况下以CFT共识算法做数据一致性从而使各个节点达成共识。本文主要就两类BFT和CFT中知名的共识算法做简单介绍。
BFT（Byzantine Fault Tolerance），即拜占庭容错，是分布式计算领域的容错技术。拜占庭容错来源于拜占庭将军问题，是对现实世界的模型化。由于硬件错误、网络拥塞或中断以及遭到恶意攻击等原因，计算机和网络可能出现不可预料的行为。拜占庭容错技术被设计用来处理现实存在的异常行为，并满足所要解决的问题的规范要求。
区块链网络环境符合拜占庭将军问题模型，有运行正常的服务器，有故障的服务器，还有破坏者的服务器。共识算法的核心是在正常的节点间形成对网络状态的共识。
1
POW
POW（Proof of Work），即工作量证明，也称挖矿，各个节点比拼硬件资源来获得记账权，比特币与以太坊是最知名的两大公有链。目前底层共识算法都为POW，2015年问世的以太坊对POW做了改进。
a) 比特币中的POW
大致流程：
1) 生成矿工（coinbase）交易，并与其它所有准备打包进区块的交易组成交易列表，生成Merkle根哈希值；
2) 把Merkle根哈希及其他相关字段组装成区块头，将区块头的80字节数据作为工作量证明的输入；
3) 不断变更区块头中的随机数Nonce，并对变更后的区块头做双重SHA256哈希运算，将结果值与当前网络的目标值做对比，如果小于目标值则解题成功，即POW完成。hash算法（hash算法（区块头））<目标值target，图一为bitcoin POW源码的核心部分，代码目录为src/rpc/mining.cpp。
▲图一 bitcoin POW源码▲
b) 以太坊中的POW
随着专用挖矿设备ASIC矿机的出现，比特币POW挖矿普通 PC 节点基本无法参与挖矿。以太坊针对比特币的共识机制进行了一系列改进，重新设计了以太坊 POW （ETH）共识算法，称之为Ethash。
Ethash主要特点是对内存大小和内存带宽要求比较高，而对运算能力要求不高。通过生成一个占用大量内存空间，每三万个区块变更一次的DAG（Directed Acyclic Graph）数据集，限制高算力设备性能，降低运算优势。
大致流程如图二所示：
▲图二 以太坊 ethash 挖矿流程图▲
1) 对于每个区块，先算出一个种子。种子的计算只依赖当前区块信息；
2) 使用种子生成伪随机数据集，称为cache。轻客户端需要保存cache；
3) 基于cache生成1GB大小的数据集，称为the DAG。这个数据集的每一个元素都依赖于cache中的某几个元素， 只要有cache就可以快速计算出DAG中指定位置的元素。完整可挖矿客户端需要保存DAG；
4) 挖矿可以概括为从DAG中随机选择元素，然后暴力枚举选择一个nonce值，对其进行哈希计算，使其符合约定的难度，而这个难度其实就是要求哈希值的前缀包括多少个0。验证的时候，基于cache计算指定位置DAG元素，然后验证这个元素集合的哈希值结果小于某个值。
2
POS与DPOS
a) POS
由于POW算法在挖矿过程中对环境和电力的浪费极大，POS作为一种代替算法。POS（Proof of Stake）也称股权证明，大致思想如下：
1) 把生产区块的工作交给拥有更多代币的人，拥有的越多，拥有记账权概率越高；
2) 生产区块的过程中得到代币奖励，可以理解为持有代币带来的利息；
3) 拥有大量代币的人如果攻击网络，则会造成代币价格的下降，对这些人是不利的，所以这些矿工攻击网络的意愿较低；
4) 生产区块只需证明自己持有的代币即可，不需要消耗多少算力，节约能源。
POS虽然一定程度上达到了节约资源的目的，但是引入了新的问题，如nothing at stake问题（由于构造新的区块没有算力成本，所以当区块链出现分叉的时候，用户有可能会倾向于同时在多个分支一起挖矿来获得潜在更高的收益，这样生成了大量的分支，破坏了一致性），极端的情况下会带来中心化的结果，币越多持币时间越长，产生马太效应。
b) DPOS
DPOS（Delegated Proof of Stake）委托权益证明，它的原理是让每一个持有代币的人进行投票，最终选出n个超级节点来进行生产区块，当轮到超级节点时，没能生成区块，会被除名，网络会选出新的超级节点来取代。
以公有链EOS DPOS为例，大致流程：
1) 持有token的用户可以对候选的矿工进行投票；用户在发生交易的时候，把自己的投票包含在交易中；
2) 得票最高的21个用户被选为代表，在下一个周期中负责生产区块；
3) 打乱代表的顺序后，各代表开始依次生产区块。每个代表都有自己固定的时间区间，需要在自己的区间中完成区块的生产发布。目前这个区间是3秒，即在正常情况下每3秒产出一个区块；
4) 每个代表在生产区块的时候，需要找当时唯一的最长链进行生产，不能在其他分支上进行。
3
PBFT
PBFT是Practical Byzantine Fault Tolerance的缩写，意为实用拜占庭容错算法。该算法是Miguel Castro和Barbara Liskov在1999年提出来的，解决了原始拜占庭容错算法效率不高的问题，多应用在联盟链场景中，如fabric0.6。
PBFT算法的无异常流程大致为图三所示：
▲图三 PBFT算法流程图▲
1) 客户端发送请求给主节点。
2) 主节点广播请求给其它节点，节点执行PBFT算法的三阶段共识流程。
3) pre-prepare阶段：leader节点验证请求消息m的有效性，并在其视图内为该请求分配***，并向所有其他节点广播关于该分配的pre-prepare消息。
4) prepare阶段：非leader节点验证请求消息的有效性，并接受***。若该节点同意该分配方案，则向其他所有节点广播出相应的prepare消息；这一阶段其实是要求所有节点达成全局一致的顺序。
5) commit阶段：节点一旦收到来自集群2f+1个的prepare签名消息后，则向其他所有节点广播出commit消息；这一阶段，所有节点已经对顺序达成一致，并对收到请求已做确认。
6) 节点收到来自集群的2f+1个commit消息后，执行请求、落盘，并返回消息给客户端。
7) 客户端收到来自f+1个节点的相同消息后，代表共识已经正确完成（f代表能容忍反叛节点或者坏节点的个数，总共3f+1个节点）。
CFT（Crash Fault Tolerance），即故障容错，是非拜占庭问题的容错技术。Paxos问题是指分布式的系统中存在故障，但不存在恶意节点的场景(即可能消息丢失或重复，但无错误消息)下的共识达成问题，是分布式共识领域最为常见的问题。最早由Leslie Lamport用Paxon岛的故事模型来进行描述而得以命名。解决Paxos问题的算法主要有Paxos系列算法和Raft算法，Paxos算法和Raft算法都属于强一致性算法。
1
Paxos
Paxos算法的基本思路类似两阶段提交：多个提案者先要争取到提案的权利（得到大多数接受者的支持）。成功的提案者发送提案给所有人进行确认，得到大部分人确认的提案成为批准的结案。
Paxos协议有三种角色：
Proposer（提议者）提出提案 (Proposal)。Proposal信息包括提案编号 （Proposal ID） 和提议的值（Value），Acceptor（决策者）参与决策，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数Acceptors的接受，则称该Proposal被批准，Learner（决策学习者）参与决策，从Proposers/Acceptors学习最新达成一致的提案（Value）。
Paxos是一个两阶段的通信协议，Paxos算法的基本流程如图四所示：
▲图四 Paxos算法流程图▲
1) Proposer生成Proposal ID n，可采用时间戳+Server ID生成的唯一的Proposal ID；
2) Proposer向所有Acceptors广播Prepare(n)请求；
3) Acceptor比较n和minProposal（之前接受的提议请求），如果n>minProposal，minProposal=n，并且将 acceptedProposal 和 acceptedValue 返回；
4) Proposer接收到过半数回复后，如果发现有acceptedValue返回，将所有回复中acceptedProposal最大的acceptedValue作为本次提案的value，否则可以任意决定本次提案的value；
5) 到这里可以进入第二阶段，广播Accept (n,value) 到所有节点；
6) Acceptor比较n和minProposal，如果n>=minProposal，则acceptedProposal=minProposal=n，acceptedValue=value，本地持久化后，返回；否则，返回minProposal；
7) 提议者接收到过半数请求后，如果发现有返回值result >n，表示有更新的提议，跳转到1；否则value达成一致。
2
Raft
有感于Paxos的晦涩难懂，Ongaro在2014年提出了更容易理解的Raft算法。它将一致性分解为多个子问题：Leader选举（Leader election）、日志同步（Log replication）、安全性（Safety）、日志压缩（Log compaction）、成员变更（Membership change）。
Raft算法由leader节点来处理一致性问题。leader节点接收来自客户端的请求日志数据，然后同步到集群中其它节点进行复制，当日志已经同步到超过半数以上节点的时候，leader节点再通知集群中其它节点哪些日志已经被复制成功，可以提交到raft状态机中执行。
集群中的节点只能处于leader、follower、candidate这3种状态之一。初始状态所有节点都是follower状态，follower想变成leader必须先成为candidate，然后发起选举投票；如果投票不足，则回到follower状态；如果投票过半，则成为leader；成为leader后出现故障，若故障恢复后已有新leader，则自动*，回归follower状态。
Raft还引入了term的概念用于及时识别过期信息，类似于zookeeper中的epoch；term值单向递增，每个term内至多一个leader；若不同term的信息出现冲突，则以term值较大的信息为准。
Raft还采用了心跳包和超时时间，leader为了保持自己的权威，必须不停地向集群中的其他节点发送心跳包；一旦某个follow在超过了指定时间（election timeout）仍没有收到心跳包，则就认为leader已经挂掉，自己进入candidate状态，开始竞选leader。
Raft的leader选举是通过heartbeat和随机timeout时间来实现的；而日志复制（log replication）阶段是以强leadership来实现的：leader接收client的command，append到自身log中，并将log复制到其他follower；而raft对安全性的保证是通过只有leader可以决定是否commit来实现的。
从Paxos、Raft到PBFT，从POW到POS，再到目前各种各样的Paxos变种、Raft变种、BFT类混合新算法、及各种基于POW算法的改良，分布式一致性算法在不断发展、完善、进化。甚至各大公司也在结合自己的业务实际，研发各种适合自己场景的分布式一致性算法，对共识算法的思考，也在不算深入，从传统的分布式封闭的网络中的共识，到有准入规则的联盟链，再到人人都可参与的公有链开放网络环境中的共识机制，所需要解决的问题越来越复杂，应对的挑战也越来越严峻，我们还有很长的路要走。
参考资料：
*1. http://www.scs.stanford.edu/14au-cs244b/labs/projects/copeland_zhong.pdf
*2. https://people.cs.umass.edu/~emery/classes/cmpsci691st/scribe/lecture17-byz.pdf
*3. https://lamport.azurewebsites.net/tla/byzsimple.pdf
*4. https://blockonomi.com/practical-byzantine-fault-tolerance/
*5. https://medium.com/@VitalikButerin/the-meaning-of-decentralization-a0c92b76a274
*6. https://bitcoin.org/bitcoin.pdf
*7. https://en.wikipedia.org/wiki/Proof-of-work_system
*8. https://bitnodes.earn.com/
*9. https://www.giottus.com/Bitcoin
*10. https://www.nichanank.com/blog/2018/6/4/consensus-algorithms-pos-dpos
*11. https://en.bitcoinwiki.org/wiki/DPoS
*12. https://amplab.github.io/cs262a-fall2016/notes/21-Paxos-Raft.pdf
*13. https://www.the-paper-trail.org/post/2012-03-25-flp-and-cap-arent-the-same-thing/
*14. https://github. com/ethereum/wiki/wiki/White-Paper
15. https://hyperledger-fabric-cn.readthedocs.io/zh/latest/index.html
