1、拜占庭将军问题基本描述

问题

当我们讨论区块链共识时，为什么会讨论拜占庭将军问题？

区块链网络的本质是一个分布式系统，在存在恶意节点的情况下，希望
整个系统当中的善良节点能够对于重要的信息达成一致，这个机制通常
被称作共识机制（consensus)。

而上述问题的本质就是拜占庭将军问题。

解决方案区别

崩溃容错协议(CFT)和拜占庭容错协议(BFT)的区别

在分布式系统当中，依据系统对于故障组件的容错能力分为崩溃容错协议(crash fault tolerant,CFT)和拜占庭容错t协议(Byzantine fault tolerant,BFT)。

• CFT:针对系统中存在故障节点的情况，常见协议有paxos,raft。
• BFT:针对系统中存在恶意节点的情况，常见协议有PBFT,hotstuff。

恶意节点，就是存在篡改信息，错误信息。

上个图，致敬一下大神。

这个问题产生

拜占庭将军问题，是由莱斯利兰伯特(Leslie Lamport)在其1982年发表的同名论文当中提出的分布式对等网络通信的容错问题。

2、拜占庭容错算法的基本假设

需要对恶意节点的占比和网络的条件进行一个假设。

通常会假设恶意节点小于某一个固定的值，然后以此作为前提条件进行共识算法的设计。

• 例如PoW假设恶意节点占比小于1/2 工作量证明。

• PBFT假设恶意节点占比小于1/3。 拜占庭容错

网络模型

• 同步模型(Synchronous Model))
• 部分异步模型(Partial Asynchronous Model)
• 异步模型(Asynchronous Model)

同步模型（上帝视角）

在一个同步网络的模型中，网络当中的传送消息的延迟小于某个确定的值，这个值可以被参与这个分布式系统的节点所知道。

部分异步模型

在一个部分异步的网络模型当中，网络当中传送的消息的延迟小于某一个值，但是这个值的是参与分布式系统的节点所不知道。

异步模型

• 在一个异步的网络模型中，信息传送的时间可以无限大，只保证信息最终能够传送到。

• 根据FLP不可能原理：在网络可靠、但允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性共识算法(No completely asynchronous consensus protocol can tolerate even a single unannounced process death)。

• 在这种网络模型当中的典型算法代表是：HoneyBadgerBFT。

3、解决拜占庭问题的共识算法

提出的方案

在存在恶意节点的情况下依然能够达成共识的特性叫做拜占庭容错(Byzantine Fault Tolerance).

从1982年这个问题提出以来有许许多多的共识算法被提出。

PBFT

Practical Byzantine Fault Tolerance

三阶段提交

恶意节点f

总节点数n

要求n>=3f+1

POW

这里介绍的是bitcoin当中的Proof of Work。
基本假设
1.网络当中的消息延迟小于某个确定的值。
2.密码学的工具的假设有效，如公私钥加密体系和哈希函数等满足条件。
3.节点中恶意节点的占比小于50%。

运行的流程：

运行的流程：
1)新交易向所有的节点广播。
2)每个节点将新的交易收集到一个区块中。
3)每个节点运行随机数生成函数为它的区块寻找一个工作量证明（使得区块达到要求）。
4)当一个节点找到了工作量证明（挖出的块满足了要求），就向所有的节点广播这个块。
5)节点在区块中所有的交易都是有效的且之前没有被支付的情况下接收这个区块。
6)节点通过使用这个区块的哈希值作为上一个区块在链中创建下一个区块的方式表示对于这个区块的接受。

主链的确定：以最长链作为共识的链
区块的确定(Block Finalization)依赖于一种概率性的保证，一个区块上链之后一般认为后面有T个区块就认为该区块已经加入共识组了。

4、BFT在区块链当中的应用

区块链共识本身是在有一定比例的恶意节点的情况下，在区块链系统当中的节点要达成一致的过程。本身就是一个拜占庭容错问题。
现在的区块链共识算法可以分为两大派别，第一派是在工作量证明的基础上进行各种改进，例如某些权益证明(Proof of Stake)的方案。
另一派是在经典的拜占庭容错算法的基础上进行一定的改进。例如会首先在众多的节点当中选举出少量的委员会节点，之后在委员会节点当中运行一些PBFT算法。

上述两种派别并没有一个明确的划分。

更进一步的推荐，经典的拜占庭算法在区块链当中的演变和应用。
algorand 基于pos

stellar 经典拜占庭的创新 rfba