区块链快速入门（四）——BFT（拜占庭容错）共识算法

区块链快速入门（四）——BFT（拜占庭容错）共识算法

一、BFT简介

1、拜占庭将军问题简介

拜占庭将军问题（Byzantine Generals Problem）是Leslie Lamport（2013年的图灵奖得主）用来为描述分布式系统一致性问题（Distributed Consensus）在论文中抽象出来一个著名的例子。
拜占庭将军问题简易的非正式描述如下：
拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。基于一些原因，这10支军队不能集合在一起单点突破，必须在分开的包围状态下同时进攻。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商，从而赢取战斗？这就是著名的拜占庭将军问题。
拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题，即消息传递的信道绝无问题。Lamport已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以，在研究拜占庭将军问题的时候，假定信道是没有问题的，然后去做一致性和容错性相关研究。

2、两将军问题

3、BFT简介

BFT（Byzantine Fault Tolerance），即拜占庭容错，是分布式计算领域的容错技术，拜占庭容错来源于拜占庭将军问题。拜占庭将军问题是对现实世界的模型化，由于硬件错误、网络拥塞或中断以及遭到恶意*等原因，计算机和网络可能出现不可预料的行为。拜占庭容错技术被设计用来处理现实存在的异常行为，并满足所要解决的问题的规范要求。
区块链网络环境符合拜占庭将军问题模型，有运行正常的服务器（忠诚的拜占庭将军），有故障的服务器，还有破坏者的服务器（叛变的拜占庭将军）。共识算法的核心是在正常的节点间形成对网络状态的共识。
通常，发生故障的节点被称为拜占庭节点，而正常的节点为非拜占庭节点。
拜占庭容错系统是一个拥有n台节点的系统，整个系统对于每一个请求，满足以下条件：
　　A、所有非拜占庭节点使用相同的输入信息，产生同样的结果；
　　B、如果输入的信息正确，那么所有非拜占庭节点必须接收这个信息，并计算相应的结果。
拜占庭系统普遍采用的假设条件包括：
　　A、拜占庭节点的行为可以是任意的，拜占庭节点之间可以共谋；
　　B、节点之间的错误是不相关的；
　　C、节点之间通过异步网络连接，网络中的消息可能丢失、乱序并延时到达，但大部分协议假设消息在有限的时间里能传达到目的地；
　　D、服务器之间传递的信息，第三方可以嗅探到，但是不能篡改、伪造信息的内容和验证信息的完整性。
原始的拜占庭容错系统由于需要展示其理论上的可行性而缺乏实用性。另外，还需要额外的时钟同步机制支持，算法的复杂度也是随节点增加而指数级增加。

二、PBFT算法

1、PBFT算法简介

2、PBFT算法原理

PBFT是一种状态机副本复制算法，即服务作为状态机进行建模，状态机在分布式系统的不同节点进行副本复制。每个状态机的副本都保存了服务的状态，同时也实现了服务的操作。将所有的副本组成的集合使用大写字母R表示，使用0到|R|-1的整数表示每一个副本。为了描述方便，通常假设故障节点数为f个，整个服务节点数为|R|=3f+1个，f是有可能失效的副本的最大个数。尽管可以存在多于3f+1个副本，但额外的副本除了降低性能外不能提高可靠性。
所有的副本在一个被称为视图（View）的轮换过程中运作。在某个视图中，一个副本作为主节点（primary），其它的副本节点作为备份节点（backups）。视图是连续编号的整数。主节点由公式p = v mod |R|计算得到，v是视图编号，p是副本编号，|R|是副本集合的个数。当主节点失效的时候就需要启动视图轮换过程。
PBFT算法实现流程如下：

（1）REQUEST
客户端C向主节点p发送

<REQUEST, o, t, c>

请求。
o:请求的具体操作
t:请求时客户端追加的时间戳
c：客户端标识。
REQUEST: 包含消息内容m，以及消息摘要d(m)。
客户端对请求进行签名。
（2）PRE-PREPARE
主节点收到客户端的请求，需要对客户端请求消息签名是否正确进行校验。
非法请求则丢弃。正确请求，分配一个编号n，编号n主要用于对客户端的请求进行排序。然后广播一条

<<PRE-PREPARE, v, n, d>,  m>

消息给其它副本节点。
v：视图编号
d客户端消息摘要
m：消息内容

<PRE-PREPARE, v, n, d>

进行主节点签名。
n是要在某一个范围区间内的[h, H]。
（3）PREPARE
副本节点i收到主节点的PRE-PREPARE消息，需要进行以下校验：
A、主节点PRE-PREPARE消息签名是否正确。
B、当前副本节点是否已经收到了一条在同一v下并且编号也是n，但是签名不同的PRE-PREPARE信息。
C、d与m的摘要是否一致。
D、n是否在区间[h, H]内。
非法请求则丢弃。正确请求，副本节点i向其它节点包括主节点发送一条

<PREPARE, v, n, d, i>

消息, v, n, d, m与上述PRE-PREPARE消息内容相同，i是当前副本节点编号。

<PREPARE, v, n, d, i>

进行副本节点i的签名。记录PRE-PREPARE和PREPARE消息到log中，用于视图轮换过程中恢复未完成的请求操作。
PREPARE阶段如果发生视图轮换会导致丢弃PREPARE阶段的请求。
（4）COMMIT
主节点和副本节点收到PREPARE消息，需要进行以下校验：
A、副本节点PREPARE消息签名是否正确。
B、当前副本节点是否已经收到了同一视图v下的n。
C、 n是否在区间[h, H]内。
D、d是否和当前已收到PRE-PPREPARE中的d相同
非法请求则丢弃。如果副本节点i收到了2f+1个验证通过的PREPARE消息，表明网络中的大多数节点已经收到同意信息，则向其它节点包括主节点发送一条

<COMMIT, v, n, d, i>

消息，v, n, d,  i与上述PREPARE消息内容相同。

<COMMIT, v, n, d, i>

（5）REPLY
主节点和副本节点收到COMMIT消息，需要进行以下校验：
A、副本节点COMMIT消息签名是否正确。
B、当前副本节点是否已经收到了同一视图v下的n。
C、d与m的摘要是否一致。
D、n是否在区间[h, H]内。
非法请求则丢弃。如果副本节点i收到了2f+1个验证通过的COMMIT消息，说明当前网络中的大部分节点已经达成共识，运行客户端的请求操作o，并返回

<REPLY, v, t, c, i, r>

给客户端，r：是请求操作结果，客户端如果收到f+1个相同的REPLY消息，说明客户端发起的请求已经达成全网共识，否则客户端需要判断是否重新发送请求给主节点。记录其它副本节点发送的COMMIT消息到log中。

3、PBFT算法的垃圾回收

<CheckPoint, n, d, i>

4、PBFT算法的视图轮换

<VIEW-CHANGE, v+1, n, C, P, i>

<NEW-VIEW, v+1, V, O>

消息。V是有效的VIEW-CHANGE消息集合。O是主节点重新发起的未经完成的PRE-PREPARE消息集合。PRE-PREPARE消息集合的选取规则如下：
A、选取V中最小的stable checkpoint编号min-s，选取V中prepare消息的最大编号max-s。
B、在min-s和max-s之间，如果存在P消息集合，则创建

<<PRE-PREPARE, v+1, n, d>, m>

消息。否则创建一个空的PRE-PREPARE消息，即：

<<PRE-PREPARE, v+1, n, d(null)>, m(null)>

5、PBFT算法的优缺点

PBFT算法的优点:
PBFT算法具有高交易通量和吞吐量，高可用性，易于理解。
PBFT算法的缺点:
A、计算效率依赖于参与协议的节点数量，由于每个副本节点都需要和其它节点进行P2P的共识同步，因此随着节点的增多，性能会下降的很快，但在较少节点的情况下可以有不错的性能，并且分叉的几率很低，不适用于节点数量过大的区块链，扩展性差。
B、系统节点是固定的，无法应对公有链的开放环境，只适用于联盟链或私
有链环境。
C、PBFT算法要求总节点数n>=3f+1(其中，f代表作恶节点数)。系统的失效节点数量不得超过全网节点的1/3，容错率相对较低。

6、PBFT算法的应用场景

三、POW算法

1、POW算法简介

2、POW算法原理

工作量证明的主要特征是客户端需要做一定难度的工作得出一个结果，验证方却很容易通过结果来检查出客户端是不是做了相应的工作。工作量证明方案的一个核心特征是不对称性：工作对于请求方是适中的，对于验证方则是易于验证的。

给定一个基本字符串，在基本字符串后面添加一个叫做nonce的整数值，对变更后（添加nonce)的字符串进行SHA256哈希运算，如果得到的哈希结果（以16进制的形式表示）是以某个字符串（如”0000″）开头的，则验证通过。为了达到工作量证明的目标，需要不停的递增nonce值，对得到的新字符串进行SHA256哈希运算。
由于给定的基本字符串在不同的场合并不确定，对于不同的基本字符串和nonce的组合，要使用SHA256计算得到某个字符串开头Hash值的计算次数并不确定，但会是一个符合统计学规律的概率事件。
按照规则，预期大概要进行2^16 次尝试（哈希值的伪随机特性可以做概率估算），才能得到4个前导0的哈希散列。

3、比特币的POW实现

比特币区块由区块头和该区块所包含的交易列表组成。区块头大小为80字节，其构成包括：
　　 4字节：版本号
　　 32字节：上一个区块的哈希值
　　 32字节：交易列表的Merkle根哈希值
　　 4字节：当前时间戳
　　 4字节：当前难度值
　　 4字节：随机数Nonce值
　　 80字节长度的区块头，即为比特币Pow算法的输入字符串。
　　交易列表附加在区块头之后，其中第一笔交易为矿工获得奖励和手续费的特殊交易。
工作量证明过程，即为不断调整Nonce值，对区块头做双重SHA256哈希运算，使得结果满足给定数量前导0的哈希值的过程，其中前导0的个数，取决于挖矿难度，前导0的个数越多，挖矿难度越大。
每创建2016个块后将计算新的难度，此后的2016个块使用新的难度。计算步骤如下：
　　A、找到前2016个块的第一个块，计算生成这2016个块花费的时间。
即最后一个块的时间与第一个块的时间差。时间差不小于3.5天，不大于56天。
　　B、计算前2016个块的难度总和，即单个块的难度x总时间。
　　C、计算新的难度，即2016个块的难度总和/14天的秒数，得到每秒的难度值。
　　D、要求新的难度，难度不低于参数定义的最小难度。

4、POW算法的优缺点

POW算法的优点：
A、完全去中心化
B、节点自由进出
C、安全性高
POW算法的缺点：
A、记账权向资本集中
B、挖矿造成大量的资源浪费。
C、网络性能太低，需要等待多个确认，容易产生分叉，区块的确认共识达成的周期较长，不适合商业应用。

5、POW算法的应用场景

POW共识机制用在了大部分挖矿的区块链项目，比如BTC、ETH、LTC。

四、POS算法

1、POS算法简介

2、POS算法原理

POS原理的核心概念为币龄，即持有货币的时间。例如有10个币、持有90天，即拥有900币天的币龄。
　　使用币即意味着币龄的销毁。
　　在POS中有一种特殊的交易称为利息币，即持有人可以消耗币龄获得利息，同时获得为网络产生区块以及POS造币的优先权。
POW通过算力证明自己有资格写区块链，而PoS通过拥有的币龄来证明自己有资格写区块链。

3、POS算法的优缺点

POS算法的优点：
A、不消耗大量算力挖矿，节省能耗。
B、在一定程度上缩短了共识达成的时间
C、防作弊。
POS算法的缺点：
A、本质仍然需要挖矿，未解决商业应用的痛点
B、极端的情况下会带来中心化的结果

4、点点币的POS实现

点点币的POS证明计算公式为：
　　proofhash < 币龄x目标值
　　展开如下：
　　hash(nStakeModifier + txPrev.block.nTime + txPrev.offset + txPrev.nTime + txPrev.vout.n + nTime) < bnTarget x bnCoinDayWeight
　　其中proofhash，对应一组数据的哈希值，即hash(nStakeModifier + txPrev.block.nTime + txPrev.offset + txPrev.nTime + txPrev.vout.n + nTime)。
　　币龄即bnCoinDayWeight，即币天，即持有的币数乘以持有币的天数，此处天数最大值为90天。
　　目标值，即bnTarget，用于衡量POS挖矿难度。目标值与难度成反比，目标值越大、难度越小；反之亦然。
　　因此，持有的币天越大，挖到区块的机会越大。

五、DPOS算法

1、DPOS算法简介

2、DPOS算法原理

DPOS算法的基本原则：
A、持股人依据所持股份行使表决权，而不是依赖挖矿竞争记账权。
B、最大化持股人的盈利。
C、最小化维护网络安全的费用。
D、 最大化网络的效能。
E、 最小化运行网络的成本 (带宽、CPU等)，在不浪费大量电力的情况下实现网络的安全稳定。
在DPOS共识算法中，区块链的正常运转依赖于超级节点，超级节点的职责主要有：
A、提供一台服务器节点，保证节点的正常运行；
B、节点服务器收集网络里的交易；
C、节点验证交易，把交易打包到区块；
D、节点广播区块，其它节点验证后把区块添加到自己的数据库；
E、带领并促进区块链项目的发展；
DPOS算法运行机制如下：
A、所有持币者先选出超级节点负责签署区块
B、DPOS的规则是最长链胜出，每个超级节点必须按照生产排程，轮流产生区块。假设排程排定A、Ｂ、Ｃ分别轮流生产区块，在一定时间内产生的区块如下：

C、如果恶意节点生产了分叉区块，假设Ａ、Ｃ都是诚实的节点，只有B节点是恶意的，由于B产生区块的速度（每个周期生产一个区块）慢于A、Ｃ合力产生区块的速度（每个周期生产一个区块），根据最长链胜出的规则，诚实的节点还是会胜出。

D、同一个节点要产生重复两个区块的速度也要慢于诚实节点合作产生区块的速度，所以最长链胜出规则会保证诚实节点的链会胜出。
E、如果A，B，C三个超级节点的网络出现碎片化，各自为政的情况。在短期内的确可能三链并行，但一旦网络连接恢复，短链自然会向最长链回归。超级节点数量为奇数，所以两大派系势均力敌僵持不下的情况不会维持太久，最终势必会有其中一方的链更长。

3、DPOS对恶意节点的惩罚

注册成为候选超级节点需要支付一笔保证金（约10 XTS)，通常担任超级节点约两周后才可达到损益平衡，因此促进了受托人的稳定性，确保至少会挖满两周的矿。
DPOS对恶意节点的惩罚为：不按排程产生区块的超级节点将在下一轮被投票剔除，被没收缴纳的保证金。
恶意节点在短期内是能够作恶的，恶意的区块只是短时间保留而已，很快超级节点之间会回归诚实节点达成的共识，制造出最长链，向没有作恶区块的最长链回归。

4、DPOS算法的优缺点

DPOS算法的优点：
A、能耗优势，网络运行成本低。
B、理论上更加去中心化。
C、较快的确认速度。出块速度秒级，交易确认分钟级。
DPOS算法的缺点：
A、坏节点不能被及时处理，只有经过选举才能清除坏节点。
B、小散投票积极性不高。
C、依赖代币

5、DPOS算法的应用场景