科普—BFT（拜占庭容错）共识算法

一、BFT简介

一、拜占庭将军问题简介

拜占庭将军问题是 Leslie Lamport（2013 年图灵奖获得者）在他的论文中用来抽象描述分布式共识的一个著名例子。

拜占庭将军问题的简单、非正式的描述如下：

拜占庭帝国要打击强大的敌人，于是派出10支军队包围敌人。 这个敌人虽然比不上拜占庭帝国，但也足以抵挡5支拜占庭正规军的同时进攻。 不知为何，这10支大军无法集中在一起单点突围，必须在各自包围的状态下同时进攻。 他们任何一支军队单打独斗都没有胜算，除非至少有6支军队同时进攻夺取敌国。 他们分散在敌国各地，依靠信号兵相互沟通，协商攻击意图和攻击时间。 困扰这些将领的问题是，他们不确定其中是否有内奸，而内奸可能会擅自改变进攻的意图或时机。 在这种状态下，拜占庭将军能否找到一种分布式协议，让他们远程协商，从而赢得战斗？ 这就是著名的拜占庭将军问题。

Byzantine Generals' Problem 没有考虑信号兵是否会被拦截或无法传递信息，即消息传递的通道绝对没有问题。 Lamport 已经表明，通过在可能丢失消息的不可靠通道上传递消息是不可能达成共识的。 因此，在研究拜占庭将军问题时，假设通道没有问题，然后进行一致性和容错性相关的研究。

2.二将问题

在拜占庭问题之前，已经有一个双将军问题（Two Generals Paradox）：两个将军必须通过一个使者就进攻或撤退达成一致，但是使者可能会迷路或者被敌人挡住（消息丢失或伪造），如何达成协议？

根据 FLP 不可能原理，二将问题没有通用解。

3. BFT简介

BFT（Byzantine Fault Tolerance），即拜占庭容错，是分布式计算领域的一种容错技术。 拜占庭容错来源于拜占庭将军问题。 拜占庭将军问题是对现实世界的建模。 由于硬件错误、网络拥塞或中断以及恶意攻击，计算机和网络可能会出现不可预测的行为。 拜占庭容错技术旨在处理现实中存在的异常行为，满足待解决问题的规范要求。

区块链网络环境符合拜占庭将军问题模型，有正常服务器（忠诚的拜占庭将军）、故障服务器、破坏者服务器（叛逆的拜占庭将军）。 共识算法的核心是在正常节点之间形成对网络状态的共识。

通常，故障节点称为拜占庭节点，健康节点称为非拜占庭节点。

一个拜占庭容错系统是一个有n个节点的系统，整个系统每次请求都满足以下条件：

A. 所有非拜占庭节点使用相同的输入信息并产生相同的结果；

B. 如果输入的信息是正确的，那么所有的非拜占庭节点都必须接收到这个信息，并计算出相应的结果。

拜占庭系统中常用的假设包括：

A、拜占庭节点的行为可以任意，拜占庭节点可以合谋；

B. 节点之间的错误是无关紧要的；

C. 节点通过异步网络连接。 网络中的消息可能会丢失、乱序和延迟。 但是，大多数协议都假定消息可以在有限的时间内到达目的地；

D、服务器之间传输的信息可以被第三方嗅探，但不能被篡改，伪造信息内容，验证信息的完整性。

最初的拜占庭容错系统由于需要论证其理论可行性，缺乏实用性。 此外，还需要额外的时钟同步机制支持，算法的复杂度也随着节点数量呈指数增长。

2. PBFT算法

一、PBFT算法介绍

PBFT（Practical Byzantine Fault Tolerance），拜占庭容错算法，由Miguel Castro和Barbara Liskov在1999年发表的论文“Practical Byzantine Fault Tolerance and Proactive Recovery”中提出。PBFT算法可以工作在异步环境中，并且通过优化解决了原有拜占庭容错算法效率低下的问题，将算法的复杂度从指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中具有可行性。 已被广泛使用。 PBFT算法在故障节点不超过总数1/3的情况下，可以同时保证Safety和Liveness。

PBFT算法使用密码学相关技术（RSA签名算法、消息验证码和摘要）来保证消息传递过程不可篡改和不可破坏。

2. PBFT算法原理

PBFT是一种状态机副本复制算法，即将服务建模为状态机，状态机在分布式系统的不同节点上进行副本复制。 状态机的每一个副本保存了服务的状态，同时也实现了服务的操作。 所有副本的集合用大写字母R表示，用0到|R|-1的整数表示每个副本。 为了描述方便，通常假设故障节点的个数为f，整个服务节点的个数为|R|=3f+1，其中f为可能发生故障的最大副本数。 虽然可以有超过 3f+1 个副本，但额外的副本除了性能之外不会提高可靠性。

所有副本都在称为视图的轮换过程中运行。 在某种意义上，一个副本作为主节点（primary），其他副本节点作为备份节点（backups）。 视图是连续编号的整数。 主节点由公式p = v mod |R|计算，v为视图号，p为副本号，|R| 是副本集的数量。 当主节点发生故障时，需要启动视图轮换过程。

PBFT算法的实现过程如下：

(1) 请求

客户端 C 发送给主节点 p

问。

o：请求的具体操作

t：客户端请求时附加的时间戳

c：客户端 ID。

REQUEST：包含消息内容m，消息摘要d(m)。

客户签署请求。

(2) 预先准备

主节点收到客户端的请求后，需要验证客户端请求报文的签名是否正确。

非法请求被丢弃。 为了正确请求，分配一个数字n，主要用于对客户端的请求进行排序。然后广播一个

<

, 米>

给其他副本节点的消息。

v：视图编号

d 客户端消息摘要

m：消息内容

制作主节点签名。

n是[h,H]在一定范围内的区间。

(3) 准备

副本节点 i 收到主节点的 PRE-PREPARE 消息，需要进行如下检查：

A.主节点PRE-PREPARE消息签名是否正确。

B、当前副本节点是否收到了相同v、编号n但签名不同的PRE-PREPARE消息。

C、d、m的总结是否一致。

D、n是否在区间[h,H]内。

非法请求被丢弃。正确的请求，复制节点i向包括主节点在内的其他节点发送消息

message,v,n,d,m同上面的PRE-PREPARE消息一样，i是当前复制节点号。

制作副本节点 i 的签名。 将 PRE-PREPARE 和 PREPARE 消息记录到日志中，以在视图轮换期间恢复未完成的请求操作。

如果在 PREPARE 阶段发生视图旋转，则 PREPARE 阶段的请求将被丢弃。

(4) 提交

主节点和副本节点收到PREPARE消息后需要进行如下检查：

A. 复制节点的PREPARE消息签名是否正确。

B、当前replica节点是否收到了同一个视图v下的n。

C、n是否在区间[h,H]内。

D、d是否与当前收到的PRE-PPREPARE中的​​d相同

非法请求被丢弃。如果副本节点i收到2f+1条经过验证的PREPARE消息，说明网络中的大部分节点都收到了同意信息，然后向包括主节点在内的其他节点发送消息

message, v, n, d, i 与上面的PREPARE消息相同。

制作副本节点 i 的签名。 将COMMIT消息记录到日志中，用于恢复视图轮转过程中未完成的请求操作。 将其他副本节点发送的PREPARE消息记录到日志中。

COMMIT 阶段用于确保网络中的大多数节点已收到足够的信息以达成共识。 如果在COMMIT阶段发生view rotation，则保留原COMMIT阶段的请求，不达成共识，请求号不会丢失。

(5) 回复

主节点和副本节点在收到COMMIT消息后需要进行如下检查：

A、副本节点COMMIT消息签名是否正确。

B、当前replica节点是否收到了同一个视图v下的n。

C、d、m的总结是否一致。

D、n是否在区间[h,H]内。

非法请求被丢弃。如果副本节点i收到2f+1条通过验证的COMMIT消息，则说明当前网络中的大多数节点已经达成共识比特币共识算法，运行客户端的请求操作o，并返回

对于客户端，r:是请求操作的结果。 如果客户端收到f+1条相同的REPLY消息比特币共识算法，则说明客户端发起的请求已经达成全网共识。 否则，客户端需要判断是否重新向主节点发送请求。 将其他副本节点发送的COMMIT消息记录到日志中。

3. PBFT算法的垃圾收集

为了保证在视图轮转过程中能够恢复之前的请求，每个副本节点都会将一些消息记录到本地日志中。 请求执行后，副本节点需要清除之前请求的记录消息。 最简单的方式是在Reply消息后对当前状态进行一次共识同步，但是成本比较高，所以可以在执行多个请求K（例如：100）后进行一次状态同步。 状态同步消息为CheckPoint消息。

副本节点 i 发送

对于其他节点，n是当前节点保留的最后一次查看请求号，d是当前状态的总结，CheckPoint消息记录在日志中。 如果副本节点i收到2f+1条经过验证的CheckPoint消息，则清除之前日志中的消息，将n作为当前稳定的checkpoint。

实践中，当副本节点i向其他节点发送CheckPoint消息时，其他节点还没有完成K次请求，因此不会立即响应i的请求，会按照自己的节奏往前走，但此时发送的CheckPoint没有形成稳定，为了防止i处理请求过快，设置一个高低水位区间[h,H]解决上面提到的问题。 低水位h等于上一个稳定的checkpoint的编号，高水位H=h+L，其中L为指定值，等于该checkpoint处理的请求数K的整数倍周期，并且可以设置为L = 2K。 当副本节点i的处理请求超过高水位H时，此时会停止，等待stable checkpoint改变，再继续。

4. PBFT算法的视角旋转

如果主节点是邪恶的，它可能会为不同的请求分配相同的序号，或者不分配序号，或者使相邻的序号不连续。 备份节点应该有责任主动检查这些序号的合法性。 如果主节点下线或者没有广播客户端的请求，客户端设置超时机制。 如果超时，它将请求消息广播到所有副本节点。 副本节点检测到主节点恶意或离线，并启动视图轮换协议。

副本节点广播到其他节点

信息。 n为最新的稳定检查点编号，C为2f+1验证的CheckPoint消息集合，P为当前副本节点未完成请求的PRE-PREPARE和PREPARE消息集合。

当主节点 p = v + 1 mod |R| 接收到 2f 个有效的 VIEW-CHANGE 消息，它广播到其他节点

信息。 V 是一组有效的 VIEW-CHANGE 消息。 O 是主节点重新发起的不完整的 PRE-PREPARE 消息集合。 PRE-PREPARE消息集的选择规则如下：

A. 在V中选择最小的稳定检查点数min-s，在V中选择最大的prepare messages数max-s。

B.在min-s和max-s之间，如果有P消息集合，创建

<

, 米>

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

<

1, n, d(空)>, m(空)>

, m(null) 是一条空消息，d(null) 是一条空消息摘要。

复制节点收到主节点发来的NEW-VIEW报文，验证有效性，如果有效则进入v+1状态，开始O中的PRE-PREPARE报文处理流程。

5. PBFT算法的优缺点

PBFT算法的优点：

PBFT算法具有交易吞吐量和吞吐量高、可用性高、易于理解等特点。

PBFT算法的缺点：

A. 计算效率取决于参与协议的节点数量。 由于每个副本节点都需要与其他节点进行P2P共识同步，随着节点数量的增加，性能会迅速下降，但在节点较少的情况下，可以有很好的性能，分叉的概率很低。 不适用于节点过多的区块链，可扩展性较差。

B、系统节点固定，无法应对公链的开放环境。 仅适用于联盟链或私有链。

有连锁环境。

C、PBFT算法要求总节点数n>=3f+1（其中f代表恶意节点数）。 系统中故障节点的数量不应超过全网节点的1/3，容错率较低。

6. PBFT算法的应用场景

PBFT算法中的节点数量是固定的，节点身份是预先确定的，不能动态增加或删除。 只能应用于节点数固定的联盟链或私有链场景。

PBFT在很多场景都有应用。 在区块链场景中，一般适用于需要强一致性的私有链和联盟链场景。 但如果能结合DPOS节点代表选举规则，也可以应用到公链上，在不可信网络中解决拜占庭容错问题。 在Hyperledger Fabric项目中，共识模块被设计为可插拔模块，支持PBFT、Raft等共识算法。

3. POW算法

一、POW算法介绍

POW（Proof of Work），即工作量证明，又称挖矿。 工作量证明通过计算猜测一个值（nonce），使得交易数据拼凑后内容的Hash值满足指定的上限。 由于Hash问题在目前的计算模型下需要大量的计算，可以保证在一段时间内系统中只会出现少数几个合法的提案。 如果能够做出合法的提议，就证明提议者确实付出了一定的工作量。

Hash Cash 是 Adam Back 于 1997 年发明的一种工作量证明机制，用于抵抗电子邮件拒绝服务攻击和垃圾邮件网关滥用。

2. POW算法原理

工作量证明的主要特点是客户端需要做一些困难的工作才能得到一个结果，而验证者可以很容易地通过结果检查客户端是否做了相应的工作。 工作量证明方案的一个核心特征是不对称性：工作对请求者来说是适度的，对验证者来说很容易验证。

给定一个基本字符串，在基本字符串的后面加上一个称为nonce的整数值，对变化后的（添加nonce）字符串进行SHA256哈希运算，如果得到的哈希结果（以十六进制表示）以某个字符串（如"0000"),则验证通过。 为了达到工作量证明的目的，需要不断增加nonce值，并对得到的新字符串进行SHA256哈希运算。

由于给定的基本串在不同的场合是不确定的，对于不同的基本串和nonce的组合，使用SHA256计算字符串开头的Hash值的计算次数是不确定的，但是会是一个概率事件统计规律。

根据规则，预计需要大约 2^16 次尝试（哈希值的伪随机特性可用于概率估计）得到 4 个前导 0 的哈希。

3.比特币的POW实现

比特币区块由区块头和区块中包含的交易列表组成。 区块头大小为80字节，其组成包括：

4字节：版本号

32字节：前一个区块的哈希值

32字节：交易列表的Merkle根哈希

4字节：当前时间戳

4字节：当前难度值

4字节：随机数Nonce值

80 字节的区块头是 Bitcoin 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. 网络性能太低，需要等待多次确认，容易分叉，区块确认共识耗时长，不适合商业应用。

五、POW算法的应用场景

大多数矿业区块链项目都采用 POW 共识机制，例如 BTC、ETH、LTC。

4.POS算法

一、POS算法介绍

POS（Proof of Stake），即权益证明，是POW共识机制的升级版。 根据每个节点占用代币的比例和时间，按比例降低挖矿难度，从而加快寻找随机数的速度。

针对POW的缺陷，Sunny King在2012年提出了POS，基于POW和POS的混合机制发布了PPCoin。

2. POS算法原理

POS原理的核心概念是币龄，即持有货币的时间。 例如，如果您有 10 个币并持有它们 90 天，您的币龄将为 900 个币日。

钱币的使用意味着钱币时代的毁灭。

在 POS 中，有一种特殊的交易叫做利息币，即持有者可以通过消耗币龄来获取利息，同时获得为网络和 POS 造币的优先出块权。

POW通过算力证明自己有资格编写区块链，PoS通过拥有的币龄证明自己有资格编写区块链。

3. POS算法的优缺点

POS算法的优点：

A. 不消耗大量算力挖矿，节省能源消耗。

B.一定程度上缩短达成共识的时间

C、反作弊。

POS算法的缺点：

A. 本质仍有待挖掘，商业应用痛点尚未解决

B. 在极端情况下，会导致中心化的结果

4.点点币的POS实现

Peercoin的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 挖矿的难度。 目标值与难度成反比，目标值越大，难度越低； 反之亦然。

因此，持币天数越长，挖到区块的几率就越大。

5. DPOS 算法

一、DPOS算法介绍

DPOS（Delegated Proof of Stake）是一种基于POW和POS的新型共识算法。 由Bitshares的首席开发者Dan Larimer（现为EOS CTO）于2014年4月提出并申请。 DPOS既可以解决POW在挖矿过程中产生的DPOS过度能耗问题，又可以避免POS权益分配下可能出现的信任平衡偏向问题。

DPOS 是由社区选出的可信账户（超级节点，如前 101 票）创建区块。 比如选出101个超级节点，即101个矿池，超级节点之间的权利是完全对等的。 普通持币者可以随时投票更换超级节点（矿池）。 DPOS的去中心化并不意味着每个持币者都有直接的股权，而是需要间接的投票权来保证选出的超级节点节点不作恶，但也可以通过拉票成为超级节点或备用超级节点。

2. DPOS算法原理

DPOS算法的基本原理：

A、股东根据所持股份行使表决权，而不是依靠挖矿竞争获得记账权。

B、股东利益最大化。

C. 最小化维护网络安全的成本。

D. 最大化网络的有效性。

E. 最小化运行网络的成本（带宽、CPU等），在不浪费大量电能的情况下实现网络的安全稳定。

在 DPOS 共识算法中，区块链的正常运行依赖于超级节点。 超级节点的职责主要包括：

A、提供服务器节点，保证节点正常运行；

B. 节点服务器收集网络中的交易；

C. 节点验证交易并将交易打包成区块；

D. 节点广播区块，其他节点验证后将区块添加到自己的数据库中；

E. 主导和推动区块链项目的发展；

DPOS算法的运行机制如下：

A. 所有持币者首先选出超级节点负责签署区块

B、DPOS的规则是最长链获胜，每个超级节点必须按照生产进度轮流出块。 假设schedule安排A、B、C依次出块，则一定时间内产生的区块如下：

C.如果恶意节点产生分叉块，假设A和C是诚实节点，只有节点B是恶意的，因为B产生块的速度（每个周期一个块）比A和C慢根据块一起出块的速度（每个周期一个块），诚实节点仍然会根据最长链获胜的规则获胜。

D. 同一节点产生重复区块的速度也慢于诚实节点协作产生区块的速度，因此最长链获胜规则将确保诚实节点的链获胜。

E.如果三个超级节点A、B、C的网络出现碎片化、碎片化。 短期内，三条链并行运行确实是可以的，但是一旦网络连接恢复，短链自然会回到最长链。 超级节点的数量是奇数，所以两派势均力敌、胶着的局面不会持续太久，其中一方最终会拥有更长的链条。

3、对恶意节点的DPOS惩罚

注册成为候选超级节点需要保证金（约10XTS），超级节点通常需要两周左右的时间才能达到盈亏平衡，从而促进受托人的稳定，保证矿场至少满挖两周。

DPOS对恶意节点的惩罚是：未按计划出块的超级节点将在下一轮投票落选，并没收已缴纳的保证金。

恶意节点可以在短时间内作恶。 恶意块只会保留很短的时间。 很快，超级节点将回到诚实节点达成的共识，创造最长链，回到没有作恶区块的最长链。 .

4. DPOS算法优缺点

DPOS算法的优点：

A. 能耗优势，网络运营成本低。

B. 理论上更去中心化。

C. 更快的确认速度。 出块速度以秒为单位，交易确认以分钟为单位。

DPOS算法的缺点：

A.坏节点无法及时处理，坏节点只能在选举后清除。

B、小散选民积极性不高。

C. 依赖代币

五、DPOS算法的应用场景

比特股（Bitshare）是一种使用DPOS机制的加密货币，通过引入技术民主层减少中心化带来的负面影响。

DPOS系统仍然存在中心化，但中心化是受控的，超级节点由普通持币者选举产生。 DPOS 通过保留货币持有者的控制权来分散系统。