区块链中的共识算法区块链

在对等网络结构的区块链系统中，每个运行的节点都各自保存自己的数据副本，如何保证彼此之间的数据统一，使网络中产生的数据让大家都能认可，以及确保分布式系统的一致性，这时就需要共识算法来实现。
共识算法解决的是对某个提案（proposal），大家达成一致意见的过程。
常见算法针对非拜占庭错误的情况，一般包括Paxos、Raft及其变种。
对于要能容忍拜占庭错误的情况，一般包括PBFT系列、PoW系列算法等。
Paxos和Raft
Paxos 问题是指分布式的系统中存在故障（fault），但不存在恶意（corrupt）节点场景（即可能消息丢失或重复，但无错误消息）下的共识达成（Consensus）问题。因为最早是 Leslie Lamport 用 Paxon 岛的故事模型来进行描述而命名。
拜占庭问题与算法

【区块链中的共识算法】
拜占庭问题更为广泛，讨论的是允许存在少数节点作恶（消息可能被伪造）场景下的一致性达成问题。拜占庭算法讨论的是最坏情况下的保障。
中国将军问题拜占庭将军问题之前，就已经存在中国将军问题：两个将军要通过信使来达成进攻还是撤退的约定，但信使可能迷路或被敌军阻拦（消息丢失或伪造），如何达成一致。根据 FLP 不可能原理，这个问题无解。

FLP 不可能原理：在网络可靠，存在节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性算法。

拜占庭问题又叫拜占庭将军（Byzantine Generals Problem）问题，是 Leslie Lamport 1982 年提出用来解释一致性问题的一个虚构模型。拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军（系统中的多个节点）需要通过信使来传递消息，达成某些一致的决定。但由于将军中可能存在叛徒（系统中节点出错），这些叛徒将努力向不同的将军发送不同的消息，试图会干扰一致性的达成。
拜占庭问题即为在此情况下，如何让忠诚的将军们能达成行动的一致。
“拜占庭将军问题”模型中，对于将军们（节点）有两个默认的假设：

所有忠诚的将军收到相同的命令后，执行这条命令得到的结果一定是相同的；
如果命令是正确的，那么所有忠诚的将军必须执行这条命令。

假设1的含义是：所有节点对命令的解析和执行是一样的，这个命令必须是一个确定性的命令，不能存在随机性，也不能依赖节点自身的状态。（这个命令不能是心情好就攻击敌人，心情不好就原地休息。）
假设2的含义是：忠诚的将军需要判断接收到的命令是不是正确的。这个判断命令的方法是整个拜占庭容错技术的核心。
对于将军们的通信过程，在“拜占庭将军问题”中也是有默认假设的：点对点通信是没问题的。也就是说，在这里，我们假设A将军要给B将军一条命令X，那么派出去的传令兵一定会准确的把命令X传递给B将军。
我们考虑4个将军的情况，同时假设4个将军中最多只有1个背叛者。当4个将军A、B、C、D把敌人包围了之后，必须协商一个统一的时间去发起进攻。这时，A将军派出了3个传令兵，分别告诉B、C、D将军，下午1点准时发起进攻。到了下午1点，A、C、D三个将军发起了进攻，歼灭了敌人，同时他们三个发现B是背叛的。虽然B背叛了，但是对最终任务没有影响。
但如果A是背叛的，会发生什么情况？A派出3个传令兵，分别告诉B、C、D将军在下午1点、2点、3点发起进攻。于是，到了下午1点，B将军去攻击敌人，由于寡不敌众，全军覆没；2点，C将军全军覆没；3点，D将军全军覆没。
因为对于忠诚的将军来说，他不知道谁是背叛者，所以，他不能完全相信接收到的命令，他必须对命令做出判断。
Byzantine Fault Tolerant 算法面向拜占庭问题的容错算法，解决的是网络通信可靠，但节点可能故障情况下的一致性达成。
最早由 Castro 和 Liskov 在 1999 年提出的 Practical Byzantine Fault Tolerant（PBFT）是第一个得到广泛应用的 BFT 算法。只要系统中有

文章图片
的节点是正常工作的，则可以保证一致性。
算法的核心思想是：对于每一个收到命令的将军，都要去询问其他人，他们收到的命令是什么。
回到刚才的第二种情况（A是背叛者），A派出3个传令兵，分别告诉B、C、D将军在下午1点、2点、3点发起进攻。B将军派出传令兵去告诉C和D两位将军，B收到的命令是下午1点进攻。C也同样派出了传令兵分别告诉B和D两位将军，C收到的命令是下午2点进攻。D也同样告诉B和C两位将军，D收到的命令是下午3点进攻。于是，B得到了3条指令：A命令B下午1点进攻，A命令C下午2点进攻，A命令D下午3点进攻。B很容易判断出来，A是背叛者（因为B知道最多只有一个背叛者）。C和D也能做出同样的判断。因此这次进攻时间的协商是无效的。
采用了这种办法以后，另一种情况又会怎样？当B是背叛者，A将军派出了3个传令兵，分别告诉B、C、D将军，下午1点准时发起进攻。B告诉C说B收到的命令是下午2点，B告诉D说收到的命令是下午2点，C和D分别告诉另外2个将军，A告诉他们的命令是下午1点。
于是，C、D收到的消息都是两个1点，一个2点。对于C、D而言，不需要判断是A和B谁是背叛者——他们只需要执行收到多的那个命令就可以了。
如果A是忠诚的，那么B是背叛的，这种情况下对于A来说，他知道自己是忠诚的，他发出的命令，至少有2个将军会执行，所以下午1点，A、C、D三个将军一起去进攻，有3个将军一起发起攻击，敌人被歼灭了。如果B是忠诚的，那么B会收到两个1点一个2点，B也会执行收到多的命令，于是B、C、D三个将军一起去进攻，有3个将军一起发起攻击，敌人被歼灭了。不管怎样，按照这种方式执行，结果是没问题的。
采用PBFT方法，本质上就是利用通信次数换取信用。每个命令的执行都需要节点间两两交互去核验消息，通信代价是非常高的。通常采用PBFT算法，节点间的通信复杂度是节点数的平方级的。
注意，上面所讨论的所有情况里，还有一个假设：所有传递的消息都是口头消息。口头协议满足三个条件：

A1：每个被发送的消息都能够被正确的投递
A2：信息接收者知道是谁发送的消息
A3：能够知道缺少的消息

意思就是，A告诉B下午1点进攻，B可能告诉C说“A命令我下午2点进攻”。如果采用了书面消息，那么情况是不一样的。除了A1，A2和A3以外，我们在口头协议之上添加一个条件A4，使之成为书面协议

A4：（a）签名不可伪造，一旦被篡改即可发现，而叛徒的签名可被其他叛徒伪造；（b）任何人都可以验证签名的可靠性。

A派传令兵给B一张纸，A将军用自己独特的笔迹写的“下午1点进攻”，然后要求B把这张纸传给C，B在纸上用自己独特的笔迹签名表示同意，然后B传给C，C也签名表示同意，然后D也同意，最后签过所有名的纸再给每个人看一眼，就可以让所有节点一致了。这种采用书面签名消息的情况，对算法要求简单得多。但是，采用书面消息的前提是：每个将军都知道其他将军的笔迹是什么样的，并且无法模仿其他将军的笔迹。
在PBFT的基础上，又出现了很多变种算法，这些算法往往都带有一些额外的假设。例如：认为发起请求的客户端一定是忠诚的，由客户端去验证节点是否忠诚；认为绝大部分时候将军都是忠诚的，所以降低两两交互核验消息的次数；通过对节点进行分工，来提高整个系统的处理速度；等。这些变种算法由于增加了额外的假设，导致了整个系统的去中心化程度的降低（关于区块链系统去中心化程度的理解，可以参见本系列的第6篇文章）。
PBFT 算法包括三个阶段来达成共识：Pre-Prepare、Prepare 和 Commit。
超级账本中的共识算法目前fabric嵌入的共识算法是pbft。
参考网址：
拜占庭问题与算法
区块链研习 | 看懂“拜占庭容错”，也就看懂了区块链的核心技术
拜占庭将军问题深入探讨
超级账本PBFT（拜占庭容错）算法详解（太复杂了没细看）