拜占庭将军问题(Byzantine Generals Problem)
一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。
拜占庭容错
拜占庭将军中可能出现叛徒，他们不仅可能向较为糟糕的策略投票，还可能选择性地发送投票信息。假设有9位将军投票，其中1名叛徒。8名忠诚的将军中出现了4人投进攻，4人投撤离的情况。这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻，而给4名投撤离的将领送信表示投撤离。这样一来在4名投进攻的将领看来，投票结果是5人投进攻，从而发起进攻；而在4名投撤离的将军看来则是5人投撤离。这样各支军队的一致协同就遭到了破坏。对于分布式系统来说, 这就是出现了”脑裂“的情况。
由于将军之间需要通过信使通讯，叛变将军可能通过伪造信件来以其他将军的身份发送假投票。而即使在保证所有将军忠诚的情况下，也不能排除信使被敌人截杀，甚至被敌人间谍替换等情况。因此很难通过保证人员可靠性及通讯可靠性来解决问题。
假使那些忠诚（或是没有出错）的将军仍然能通过多数决定来决定他们的战略，便称达到了拜占庭容错。
早期解决方案
拜占庭容错算法最早的讨论可以追溯到 Leslie Lamport 等人 1982 年 发表的论文《The Byzantine Generals Problem》，之后出现了大量的改进工作，代表性成果包括《Optimal Asynchronous Byzantine Agreement》（1992 年）、《Fully Polynomial Byzantine Agreement for n>3t Processors in t+1 Rounds》（1998 年）等。长期以来，拜占庭问题的解决方案都存在运行过慢，或复杂度过高的问题，直到“实用拜占庭容错算法”（Practical Byzantine Fault Tolerance，PBFT） 算法的提出。
实用拜占庭容错(PBFT)
PBFT 算法采用密码学相关技术（RSA 签名算法、消息验证编码和摘要）确保消息传递过程无法被篡改和破坏。
算法的基本过程如下：
- 首先，通过轮换或随机算法选出某个节点为主节点，此后只要主节点不切换，则称为一个视图（View）。
- 在某个视图中，客户端将请求 <REQUEST,operation,timestamp,client> 发送给主节点（如果客户端发给从节点，从节点可以转发给主节点），主节点负责广播请求到所有其它从节点并完成共识。
- 所有节点处理完成请求，将处理结果 <REPLY,view,timestamp,client,id_node,response> 返回给客户端。客户端检查是否收到了至少 f+1 个来自不同节点的相同结果，作为最终结果。
主节点广播过程包括三个阶段的处理：预准备（Pre-Prepare）、准备（Prepare）和提交（Commit）。预准备和准备阶段确保在同一个视图内请求发送的顺序正确；准备和提交阶段则确保在不同视图之间的确认请求是保序的。
- 预准备阶段：主节点为从客户端收到的请求分配提案编号，然后发出预准备消息 <<PRE-PREPARE,view,n,digest>,message> 给各从节点，主节点需要对预准备消息进行签名。其中 n 是主节点为这个请求分配的序号，message 是客户端的请求消息，digest 是消息的摘要。这一步的目的是为请求分配序号并通知其他节点，因此可以不包括原始的请求消息，可以通过其他方式将请求同步到从节点。
- 准备阶段：从节点收到预准备消息后，检查消息（包括核对签名、视图、编号）。如消息合法，则向其它节点发送准备消息 <PREPARE,view,n,digest,id>，带上自己的 id 信息，并添加签名。收到准备消息的节点同样对消息进行合法性检查。节点集齐至少 2f+1 个验证过的消息则认为验证通过，把这个准备消息写入本地提交消息日志中。这一步是为了确认大多数节点已经对序号达成共识，本节点已经准备好进行提交了。
- 提交阶段：广播 commit 消息 <COMMIT,v,n,d,id> 并添加自己签名，告诉其它节点某个编号为 n 的提案在视图 v 里已经处于提交状态。如果集齐至少 2f+1 个验证过的 commit 消息，则说明提案被整个系统接受。
PBFT 算法和 Raft 算法的过程十分类似。区别在于 PBFT 算法中并不假设主节点一定是可靠的，因此增加了额外的从节点之间的交互，当发现主节点不可靠时通过重新选举选出新的主节点。
具体实现上还包括 checkpoint（同步节点状态和清理本地日志数据）、视图切换（重新选举主节点）等机制，读者可自行参考论文内容，在此不再赘述。
拜占庭容错类的算法因为要考虑最恶意的存在“捣乱”者的情况，在大规模场景下共识性能往往会受到影响。
比特币的新思路
拜占庭问题之所以难解, 主要是因为:
- 提案成本过低, 导致同一时间存在多个提案
- 最终确认过程易受干扰, 导致大规模场景下确认成本过高
比特币的创造性在于
- 向拜占庭问题引入经济模型, 提高提案成本, 降低同时存在的提案个数
- 从最终确认转向概率确认, 即不要求100%达成一致, 而是一直沿着最长链进行拓展, 使最终确认成为概率性的; 当概率确认的概率足够高, 则可等价于最终确认