共识算法-拜占庭将军问题
title: 共识算法-拜占庭将军问题
tags: 区块链,共识算法
故事
拜占庭是东罗马帝国的首都,由于当时拜占庭罗马帝国国土辽阔,每支军队的驻地分隔很远,将军们只能靠信使传递消息。在打仗的时候，拜占庭军队内所有将军必需达成一致的共识，才能更好地赢得胜利。但是，在军队内有可能存有叛徒，可能会引起下面的问题:
- 叛徒可能欺骗某些将军自己将采取进攻行动。
- 叛徒可能怂恿其他将军行动。
- 叛徒可能迷惑其他将军，使他们接受不一致的信息，从而感到迷惑。
因此,将军们必须有一个预定的方法协议,使所有忠诚的将军能够达成一致,而且少数几个叛徒不能使忠诚的将军做出错误的计划。
注意：拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题。
拜占庭将军问题
“拜占庭将军问题”也被称为“拜占庭容错”。
在分布式系统中,特别是在区块链网络环境中,也和拜占庭将军的环境类似，有好的节点(类似忠诚的拜占庭将军),有坏节点,还有恶意节点(类似叛变的拜占庭将军)。通常，这些发生故障节点被称为拜占庭节点，而正常的节点即为非拜占庭节点。
拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或断开以及遭到恶意攻击，计算机和网络可能出现不可预料的行为。
共识算法的核心是在正常的节点间形成共识。
求解拜占庭将军问题,隐含要满足以下两个条件:
1.每个忠诚的将军必须收到相同的命令值ⅵ(ⅵ是第i个将军的命令)。
2.如果第i个将军是忠诚的,那么他发送的命令和每个忠诚将军收到的ⅵ相同
于是,拜占庭将军问题的可以描述为:一个发送命令的将军要发送一个命令给其余n-1个将军,使得：
- Q1.所有忠诚的接收命令的将军遵守相同的命令;
- Q2.如果发送命令的将军是忠诚的,那么其他忠诚的将军遵守所接收的命令;
Lamport(莱斯利·兰伯特)对拜占庭将军间题的研究表明,当n>3m时,即叛徒的个数m小于将军总数n的1/3时,通过口头同步通信(假设通信是可靠的),可以构造同时满足Q1和Q2的解决方案,即将军们可以达成一致的命令。但如果通信是可认证、防篡改伪造的(如采用PKI认证,消息签名等),则在任意多的叛徒(至少得有两个忠诚将军)的情况下都可以找到解决方案。
而在异步通信情况下,情况就没有这么乐观。 Fischer- Lynch- Paterson定理证明了,只要有一个叛徒存在,拜占庭将军问题就无解圓。翻译成分布式计算语言,在一个多进程异步系统中,只要有一个进程不可靠,那么就不存在一个协议,此协议能保证有限时间内使所有进程达成一致。
由此可见,拜占庭将军问题在一个分布式系统中,是一个非常有挑战性的问题。因为分布式系统不能依靠同步通信,否则性能和效率将非常低。因此寻找一种实用的解决拜占庭将军问题的算法一直是分布式计算领域中的一个重要问题。
解决方案
在经典的情形下，我们可以找到两种办法，口头协议和书面协议
口头协议
口头信息即使将军们派人用口信传达消息，必须满足以下条件：
- 每个被发送的消息都能够被正确投递
- 信息接受者知道消息是谁发的
- 能够知道缺少的消息
口头协议实现很简单，假设我们有10个将军，其中任意一个将军1派信使发送消息，其他2-10的将军收到1的消息，将军直接相互转告，一轮下来每个将军都有10个信息（加上自己发的消息），如果有叛徒，那么消息就可能不一致，那么怎么决策呢，如果超过一半以上的将军决定进攻，那么就进攻，简而言之就是少数服从多数。
但是这个也有明显缺点，不知道上一个消息的来源是谁，即不知道谁是叛徒。
书面协议
书面协议相比口头协议，将军们如果同意执行协议，会在书信上盖章（签名）。
- 这个盖章不可伪造，一但篡改可被发现。
- 任何将军都可以相互之间验证盖章的可靠性
相比于口头协议，书面协议解决了溯源问题， 但是仍然面临着一些问题：
- 信息传输慢
- 无法避免盖章被伪造
- 书信保存，无法保证人手一份。