可用于区块链的共识算法

• 引言
• 两军问题
• 拜占庭将军问题
• 如何解决拜占庭将军问题？
  • 司令副官模型
  • PBFT（Practical Byzantine Fault Tolerance）
  • 比特币的POW共识
  • POS（Proof of Stake）共识
  • DPOS（Delegated Proof of Stake）共识
• 总结

引言

上一篇写了分布式一致性协议相关理论与算法，那些算法不可用于区块链系统之中，不可防止作恶情况，只能容忍节点宕机、网络分区等情况。

这节，我们一起看看区块链中常用的共识算法。先来看看为什么分布式网络需要共识？

两军问题

如图，白军军队实力强大，且居于要地，蓝军被白军隔开成为了两个军队，只有两个蓝军达成一致（具体几点几分开始进攻白军），方可战胜白军。但蓝军1、蓝军2要想达成一致，必须使用信使穿过白军领地进行互相通信，才能同时进攻取胜。但由于白军可能抓捕信使，导致两方蓝军无法达成共识情况。所以两军问题表达的是，信道不可信（消息丢失，超时等），如果存在可信信道，则两军问题可解。

两军通信，就像TCP的三次握手，需要双方发送并且得到反馈才能确认彼此以收到正确消息达到共识。

拜占庭将军问题

拜占庭将军问题是一个共识问题: 首先是由莱斯利·兰伯特(Leslie Lamport)及其他两人于1982年提出，被称为Byzantine Failure。核心描述是军中可能有叛徒，却要保证进攻一致。与分布式系统类比，节点中有作恶节点，也可能被黑客攻击。

![](data:image/svg+xml;utf8,<?xml version="1.0"?>)

图是丑了一点，大家将就了[捂脸哭]。

拜占庭帝国想要进攻一个强大的城市，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。基于一些原因，这10支军队不能集合在一起单点突破，必须在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商，从而赢取战斗？这就是著名的拜占庭将军问题。

应该明确的是，拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题，即消息传递的信道是可信安全的。Lamport已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。以下已假定信道是安全可靠的

这个问题说到底是一个关于一致性和正确性的算法问题，这个算法是针对的是忠诚的将军，因为叛徒可以不传，或者乱传消息捣乱。我们就是要在有叛徒的干扰下，找到一个容忍干扰的算法——BFT（Byzantine fault tolerance）拜占庭容错。

可以看出，两军问题是拜占庭将军问题的特例。

什么可以称为拜占庭错误？

作恶节点，或者被黑客攻击的节点。节点宕机、网络分区、超时等都不是拜占庭错误。

如何解决拜占庭将军问题？

司令副官模型

拜占庭将军问题中：每一个将军都需要与所有将军进行通信，已得知其他将军的进攻安排，从而达到共识。所以拜占庭将军问题可简化为司令——副官模型。一个司令，多个副官，需要一致性协议保证，司令发出的命令，多个副官可以得到一致的结果。

一个司令把自己的命令传递给n-1个副官，使得：

​ 一致性：所有忠诚的副官遵守一个命令（结果集中的大多数 n/2+1）。

​ 正确性：若司令是忠诚的，每一个忠诚的副官遵守他发出的命令。（若将军是作恶的，则只需要遵守第一条）

BFT为什么需要节点数n>=3f+1?

f为拜占庭错误节点数，也是BFT可以容忍的叛徒数量。

反证法，如果n<3f+1 即当f= 1时，n = 3。

1. 如果司令是忠诚的，一个副官忠诚，一个副官叛徒。当司令发送进攻命令给两个副官，两个副官会彼此询问司令的命令是什么，这时候叛徒副官就会伪造假命令，说司令给他的命令是撤退，那忠诚副官就懵了，因为他收到的是进攻命令，此时忠诚副官不知道司令是叛徒还是另一个副官是叛徒。

2. 如果司令是叛徒，两个副官是忠诚的。司令分别给两个副官一个进攻，一个撤退；两个副官通信时发现彼此收到的命令不一致，也无法达成共识。

所以得出n<3f+1时无法达到拜占庭容错，需要n>=3f+1。具体推导可看参考里的论文，或者李永乐老师的视频。

PBFT（Practical Byzantine Fault Tolerance）

BFT假设信道没有问题，也就是不考虑消息不可达、消息丢失、乱序、重复、网络分区等情况。Miguel Castro (卡斯特罗)和 Barbara Liskov （利斯科夫）在1999年发表的论文《 Practical Byzantine Fault Tolerance 》中首次提出 pbft 算法，该算法容错数量也满足 3f+1<=n。

pbft 算法的基本流程主要有以下四步：

本作品采用《CC 协议》，转载必须注明作者和本文链接