背景

在之前的《比特币机制研究》文章中，我们比较详细地探究了拜占庭将军的问题。而拜占庭容错问题，即Byzantine Fault Tolerance（缩写BFT）就源于拜占庭将军问题。
在《分布式系统的Paxos算法和Rfat算法》文章中，我们提到的Paxos算法的作者Lamport，它在研究中证明了：

在将军总数大于3m，背叛者为m活着更少时，忠诚的将军们可以达成战争决策上的一致。

要使得拜占庭将军问题得到共识，必须要满足一下两个条件：
1.每两个忠诚的将军必须收到相同的值v(i)

v(i)即第i个将军的命令

2.如果第i个将军是忠诚的，那么他发送的命令和每个忠诚将军收到的v(i)相同

换一个表述，这个模型可以简化为：

• 所有忠诚的将军遵守相同的决策

• 如果发出决策命令的将军是忠诚的，那么其他忠诚的将军都将遵从该决策

在分布式计算中，理论上不同的计算机通过交互信息达成共识，且按照同一套策略行动。但有时候，系统中的成员计算机可能因为出错发出错误信息，使得节点间沟通失败，进而使得整个系统的一致性受损。

拜占庭容错问题，实际上要解决的是：在网络通信可靠、仅节点可能故障或者异常的状况下如何达成一致性的共识。

一、PBFT算法

PBFT全称：Practical Byzantine Fault Tolerant。
PBFT算法包括三个阶段达成共识：

• 1.Pre-Prepare

• 2.Prepare

• 3.Commit

流程如图所示： PBFT三阶段共识

其中客户端C为发送请求节点，0，1，2，3为其他服务节点，3为故障节点，具体步骤如下：

1.Request

请求端节点C发送请求到任意一个节点，假定是节点0

2.Pre-Prepare

节点0收到C的请求后进行广播，传播至节点1，2，3

3.Prepare

节点1，2，3均要求收到广播后记录并再次广播，节点1传播到节点0，2，3节点，2传播至0，1，3节点，节点3因为故障无法广播

4.Commit

节点0，1，2，3在Prepare阶段，若收到超过一定数量的相同请求，则进入Commit阶段，广播Commit的请求

5.Relay

节点0，1，2在Commit阶段，若收到超过一定数量的相同请求，则对C进行反馈

总结

通过上述流程我们发现，在N ≥ 3F + 1的情况下，一致性是可能解决的，其中N为总的节点数，F为有故障的节点总数。

二、IBFT算法

上面描述的Paxos和Raft一般应用于中心化的分布式系统，或者受限应用的私有区块链，PBFT实用拜占庭共识可以应用于联盟链。这节将要介绍适用于以太坊私联或者联盟链的共识协议IBFT。
伊斯坦布尔BFT（Istanbul Byzantine Fault Tolerant,IBFT），参考自PBFT，作为以太坊EIP（Ethereum Improvement Proposal）的issue 650被提EIP #650。原来的PBFT需要相当多的调整才能使其与区块链协同工作。首先，没有特定的“客户端”发出请求并等待结果。相反，所有验证者都可以被视为客户端。此外，为了保持区块链进展，每轮都会连续选择一个提议者来创建区块提案以达成共识。另外，对于每个共识结果，期望生成一个可验证的新块，而不是一堆对文件系统的读/写操作。
IBFT定义了几个概念：

• Validator： 区块验证参与者
• Proposer： 在本轮共识中，被选择作为出块的验证者
• Round：共识周期。一轮回合以提议者创建区块提案开始，并以区块提交或轮次切换结束
• Proposal：正在进行共识处理的新块生成提案
• Sequence：提案的序列号。序列号应该大于以前的所有序列号，当前每个建议的块高度是其相关的序列号
• Backlog：存储共识信息日志
• Round state：特定序列和轮次的共识信息，包括Pre-Prepare消息、Prepare消息和Commit消息，表示本轮共识状态
• Consensus proof： 可证明该区块的区块提交签名已通过共识流程
• Snapshot：来自上一个时期的Validator投票状态

IBFT继承了原始PBFT，通过PRE-PREPARE、PREPARE和COMMIT三个阶段达成共识。系统可以容忍N个验证器节点的网络中有F个故障节点，其中N = 3F + 1。

1.工作流程

在每轮共识之前，验证器将默认以循环方式选择其中的一个作为提议者，然后提议者将提出一个新的分组提议并将其与PRE-PREPARE消息一起广播。在收到来自提议者的PRE-PREPARE消息后，验证者进入PRE-PREPARED状态，然后广播PREPARE消息。这一步是为了确保所有的验证器都在同一个序列和同一轮上工作。在收到PREPARE消息的2F +1时，验证器进入PREPARED状态，然后广播COMMIT消息。这一步是通知其同行，它接受建议的区块，并将该区块插入链中。最后，验证器等待COMMIT消息的2F + 1进入COMMITTED状态，然后将该块插入链中。
从这个流程中我们可以看出，IBFT协议的块是最终的，这意味着没有分叉，任何有效的块必须位于主链的某个地方。所以：
为了防止错误节点从主链生成完全不同的链，每个验证器在将头插入链中之前，要将2F + 1接收到的COMMIT签名附加到头中的extraData字段。这样，块可以自我验证。

2.IBFT状态机

IBFT是一种状态机复制算法。每个验证器都维护一个状态机副本以达到块一致。

状态机状态变换图如下： IBFT状态机
详细流程描述如下：

1. NEW-ROUND -> PRE-PREPARED：

• Proposer 从交易池中收集transactions
• Porposer 生成block proposal，并且广播给所有的validators，然后进入PRE-PREPARE状态
• 每个validator在收到PRE-PREPARE消息时进入PRE-REPARED状态，条件如下：
  （1）Block proposal 是来自一个合理的Proposer
  （2）Block header是合理的
  （3）Block proposal的Sequence(序列号)以及Round(轮次)要匹配validator的状态
• Validator广播PREPARE信息给其他的validator。

2.PRE-PREPARED -> PREPARE：

• Validator 收到 2F+1 个合理的PREPARE信息，然后进入PREPARE状态。合理的信息要符合以下几点：
  （1）匹配的Sequence和Round
  （2）匹配的Block Hash
  （3）信息要来自已知的Validator
• Validator在进入PREPARE状态后，广播COMMIT信息

3.PREPARE -> COMMITTED：

• Validator 收到2F + 1个合理的COMMIT信息后，进入COMMITTED状态。合理的信息要符合以下几点：
  （1）匹配的Sequence和Round
  （2）匹配的Block Hash
  （3）信息要来自已知的Validator

4.COMMITTED -> FINAL COMMITTED：

• Validator 把2F + 1个Commitment签名放进Block Header的extraData中，并且尝试插入该Block到区块链中。
• 插入Block成功后，Validator进入FINAL COMMITTED状态

5.FINAL COMMITTED -> NEW ROUND:

• Validator们选出一个新的Proposer开启新的Round。

总结

IBFT共识算法在金融事务共识容错方面有非常高的效率和性能，因此被作为以太坊企业联盟链quorum的重要共识算法。有人测试在一个区块包含2000个交易的初步测试中，IBFT共识区块链达到了400～1200的TPS。

三、以太坊的PoW算法——Ethash算法

在之前的《比特币机制研究》文章中，我们比较详细得探究了比特币的PoW算法。Pow可以简化为一个数学和经济模型：

所有矿工公平竞争一个区块的挖矿权，每个矿工遵循一个规则，对候选的区块进行Hash运算，当运算Hash值小于当前难度系数，就认为该矿工提供的候选区块满足条件，可以广播到全网验证并确认。区块链以最长的确认的区块主链作为链的基础，分叉会被抛弃，因此谁最先真实计算出来这个块的Hash，谁就成为这个块的矿工，矿工享受这个出块周期的收益，获得特点数量的价值奖励。

PoW实际是一种计算能力的竞争的公开比赛，强者胜出它的核心是Hash运算，谁的Hash运算更快，谁就更有可能挖掘出新的区块，获得更多的经济利益。在Bitcoin的发展过程中，挖矿设备经历了(CPU=>GPU=>ASIC)的进化过程，其中的动机就是为了更快地进行Hash运算。随着矿机门槛地提高，参与者久越来越少，这与区块链的去中心化构想背道而驰。
因此，在共识算法设计时，为了减少ASIC矿机的优势(专用并行计算)，Ethereum增加了对于内存的要求，即在进行挖矿的过程中，需要占用消耗大量的内存空间，而这是ASIC矿机不具备的(配置符合运算那能力的内存太贵了，即使配置，这也就等同于大量CPU了)。即将挖矿算法从CPU密集型(CPU bound)转化为IO密集型(I/O bound)。

我们这里就详细介绍下以太坊的PoW算法：Ethash算法。

以太坊挖矿算法 Ethash 又名 Dashimoto （Dagger-Hashimoto），是 Hashimoto 算法结合 Dagger 算法产生的变种算法。

1.Ethash概要

• 矿工挖矿不再是仅仅将找到的nonce填入区块头，还需要填入一项MixDigest，这是在挖矿过程中计算出来的，它可以作为矿工的确在进行消耗内存挖矿工作量的证明。验证者在验证区块时也会用到这一项。

• 先计算出约16MB大小的cache，约1GB的dataset由这约16MB的cache按特定算法生成，dataset中每一项数据都由cache中的256项数据参与生成，cache中的这256项数据可以看做是dataset中数据的parent。只所以是约，是因为其真正的大小是比16MB和1GB稍微小一点(为了好描述，以下将省略约)

• cache和dataset的大小并非一成不变，16MB和1GB只是初始值，这个大小在每年会增大73%,这是为了抵消掉摩尔定律下硬件性能的提升，即使硬件性能提升了，那么最终计算所代表的工作量不会变化很多。结合上一条，那么其实每经过30000个区块，cache和dataset就会增大一点，并且重新计算

• 全节点(比如矿工)会存储整个 cache和dataset，而轻客户端只需要存储 cache。挖矿(seal)时需要dataset在内存中便于随时存取，而验证(verify)时，只需要有cache就行，需要的dataset临时计算就行。

2.Ethash基本流程

通过上述概要的说明，我们大致了解了ETH挖矿时的特殊点，主要在于一大一小两个数据集。

（1）Cache和DAG

• 小Cache：初始大小约为16M，容量大小以后每30000个区块会更改一次。通过Seed种子进行一些运算得到第一个数，之后在小cache中的每个数都是前一个数取哈希后得到的。

一般轻节点存储此小cache。

• 大DAG(有向无环图数据)：DAG生成规则为找到cache中对应的元素后 根据元素中的值计算出下次要寻找的下标，循环256次后获得cache中最终需要的元素值进行hash计算得到DAG中元素的值。如下所示： DAG生成

（2）挖矿流程（全节点）

挖矿过程 详细图

矿工挖矿的过程为，选择Nonce值映射到DAG中的1个item，通过item中的值计算出下次要找的下标，循环64次，得到最终item，将item中的值hash计算得到结果，结果和target比较，符合条件则证明挖到区块，如果不符合则更换nonce继续挖矿。矿工在挖矿过程中需要将1G的DAG读取到内存中。

（3）验证流程（轻节点）

将块头里面的Nonce值映射到DAG中的1个item，然后通过cache数组计算出该item的值，通过item中的值计算出下次要找的下标，循环64次，得到最终item，将item中的值hash计算得到结果，结果和target比较，符合条件则验证通过。轻节点在验证过程中不需要将1G的DAG读取到内存中。每次用到DAG的item值都使用cache进行计算。

验证过程

验证过程跟挖矿过程类似，对于全节点来说，在内存中保存了大的DAG，只需循环计算64次后得到最后的哈希值与目标值比较即可；对于轻节点来说，首先通过小的cache计算出大的DAG后再计算，后面过程跟全节点一样了。

总结

以太坊为什么需要这2个不同大小的数组进行辅助hash运算呢，直接进行hash运算会有什么问题？如果只是进行重复计算会导致挖矿设备专业化，减少去中心化程度。因为我们日常使用的计算机内存和计算力是都需要的，如果挖矿只需要hash运算，挖矿设备则会设计地拥有超高算力，但对内存可以缩小到很小甚至没有。所以我们选用1G的大内存增加对内存访问的频率，增加挖矿设备对内存访问需求，从而更接近于我们日常使用的计算机。

四、PoS算法——Casper算法

PoW共识需要浪费大量的能源，制约了区块链的可持续发展。由于产生了一种被称为权益证明的PoS（Proof of Stake）算法，它将PoW中的计算算力改为系统权益，拥有权益越大则成为成功验证区块的概率越大。

PoS可以避免大量的挖矿能源浪费，但是也有一个天生的不足，即资产权益越多的人，获得验证出块的几率就会越大，作恶产生分叉的可能性也就越大。以太坊需要一种惩罚作恶的经济模型来修正PoS的不足，于是以太坊最终要进化到Casper共识协议。Casper实施了一个进程，使得它可以惩罚所有的恶意因素。权益证明在Casper协议下是这样工作的：

• ❑验证者押下一定比例的自身拥有的以太币作为保证金。

• ❑然后，当他们发现一个他们认为可以被加到链上的区块的时候，将以通过押赌注来验证它。

• ❑如果该区块被加到链上，验证者们将得到一个与他们的赌注成比例的奖励。

• ❑但是，如果一个验证者采用一种恶意的方式行动、试图做“无利害关系”的事，则将立即遭到惩罚，他们所有的权益都会被砍掉。

上面的工作原理也可以简述成这样：验证者获得交易验证资格后，就开始验证区块，如果区块没有问题，就会将其添加到区块链中，同时验证者将会获得一笔与他们的赌注成比例的奖励。同样的，押注10万以太币的人获得的奖励是只押注了1万以太币的人的10倍，赌注越多，获得的奖励也越多。但是如果一个验证者采用一种恶意的方式试图作弊，那么他将立即遭到惩罚，除了赌注全部没收以外，所有的权益也都会被砍掉。

除此之外，Casper设计了苛刻的激励来保证网络的安全，包括惩罚离线的矿工，使得验证者对他们的节点正常运行时间恪尽职守。放松懈怠很可能导致他们失去自己的保证金。这些“惩罚”属性给予了Casper相对标准工作量证明协议PoW的比较明显制约不良行为的机制。

以太坊按照版本循序渐进的过渡思路，提出了两个版本的Casper，即Casper FFG和Casper CBC。

1.Casper FFG

Casper FFG：Casper the Friendly Finality Gadget

Casper FFG是一个混合PoW/PoS共识机制。它是正准备进行初步应用的版本，也是被精心设计好来缓冲权益证明的转变过程的。设计的方式是，在Ethash PoW工作量证明协议上叠加权益证明。区块仍将通过工作量证明来挖出，每50个区块就将有一个权益证明检查点验证，通过网络验证人来评估区块的最终有效性。FFG更侧重于通过多步骤过渡为以太网络引PoS。

2.Casper CBC

Casper CBC：Casper the Correct-By-Construction，也叫 Casper the Friendly GHOST

这是个很重要的算法，详细可以看这篇文章：
《V神详解Casper CBC》