关于拜占庭问题及其分析

关于拜占庭问题及其分析

故事起源

拜占庭问题是容错计算中的一个老问题，有莱斯特兰伯特等人在1982年提出。拜占廷帝国为5-15世纪的东罗马帝国，拜占庭城邦拥有巨大的财富，令他的十个邻邦垂涎已久，但是拜占庭高墙耸立，固若金汤，没有任何一个单独的邻邦能够成功入侵，任何单个城邦的入侵行动都会失败，而入侵者的军队也会被歼灭，使得其自身反而容易遭到其它九个城邦的入侵。这十个城邦之间也互相觊觎对方的财富并经常爆发战争。

拜占庭的防御能力如此之强，非大多数人一起不能攻破。而且只要其中一个城邦背叛盟军，那么所有进攻军队都会被歼灭，并随后被其他邻邦所劫掠。因此这是一个互不信任的各个邻邦构成的分布式网络。每一方都小心行事，因为稍有不慎就会给自己带来灾难。为了获取拜占庭的巨额财富，这些邻邦分散在拜占庭的周围，依靠士兵传递消息来协商进攻目的及进攻时间，这些邻邦将军想要攻克拜占庭，但面临的一个困扰，邻邦将军不确定他们之中是否有叛徒，叛徒是否擅自变更进攻意向或者进攻时间？在这种状态下，将军们能否找到一种分布式协议来进行远程协商达成他们的共识，进而赢取拜占庭城邦的财富呢？

假设前提

在拜占庭将军问题模型中，对于将军们有两个公认的假设：

假设一、所有忠诚的将军受到相同的命令后，执行这条命令，得到的结果一定是相同的，它的含义是所有节点对命令的解析和执行是一样的，这个命令必须是一个确定性的命令，不能存在随机性，也不能依赖节点自身的状态，也就是说这个秘密不能是心情好，就攻击敌人，心情不好就原地休息；

假设二、如果命令是正确的，那么所有忠诚的将军必须执行这条命令，换句话说，忠诚的将军需要判断，接收到的命令是不是正确的。

对于将军们的通讯过程，在“拜占庭将军问题”中也是有默认假设的：点对点通信是没有问题的，也就是说在这里，我们假设A将军要给B将军一条命令X，那么派出去的传令兵一定会准确的把命令X传给B将军。

问题

但问题在于，如果每个城邦向其他九个城邦派出一名信使，那么就是这十个城邦，每一个都派出了九名信使，也就是在任何一个时间有总计90次的信息传输，并且每个城市分别收到九条信息，可能每一条都写着不同的进攻时间，除此以外，信息传输过程中，如果叛徒想要破坏原有的约定时间，就会自己修改相关信息，然后发给其他城邦以混淆试听，这样的结果是，部分城邦收到错误信息后，会遵循一个或者多个城邦已经修改过的攻击时间相关信息，从而背叛发起人的本意。这样一来，遵循错误信息的城邦（包含叛徒），将重新广播超过一条信息的信息链，整个信息链会随着他们所发送的错误信息，迅速变成不可信的信息和攻击时间，变成一个相互矛盾的纠结体。

解决办法

针对这个问题，人们主要提出了两种解决方法，一个是口头协议算法；另一个是书面协议算法。

口头协议算法的核心思想：要求每一个被发送的消息都能被正确投递，信息接收者明确知道消息发送者的身份，并且信息接收者知道信息中是否缺少信息。采用口头协议算法，若叛徒数少于1/3时，则拜占庭将军问题可以很容易解决。但是口头协议算法存在着明显的缺点，那就是消息不能溯源。

为解决该问题，提出了书面协议算法。该算法要求签名，不可伪造，一旦被篡改即可发现，同时任何人都可以验证签名的可靠性。

就算是书面协议算法，也不能完全解决拜占庭将军问题，因为该算法没有考虑信息传输延迟、签名体系难以实现的问题。且签名消息记录的保存，也难以摆脱中心化机构。

PBFT(拜占庭容错算法)

PBFT是一种状态机副本复制算法，即服务作为状态机进行建模，状态机在分布式系统的不同节点进行副本复制。每个状态机的副本都保存了服务的状态，同时也实现了服务的操作。将所有的副本组成的集合使用大写字母R表示，使用0到|R|-1的整数表示每一个副本。
为了描述方便，假设|R|=3f+1，这里f是有可能失效的副本的最大个数。尽管可以存在多于3f+1个副本，但是额外的副本除了降低性能之外不能提高可靠性。

首先介绍view、replica　、primary、backups

所有的副本在一个被称为视图（View）的轮换过程（succession of configuration）中运作。在某个视图中，一个副本作为主节点（primary），其他的副本作为备份（backups）。视图是连续编号的整数。
主节点由公式p = v mod |R|
计算得到，这里v是视图编号，p是副本编号，|R|是副本集合的个数。当主节点失效的时候就需要启动视图更换（view change）过程。
Viewstamped Replication算法和Paxos算法就是使用类似方法解决良性容错的。

同所有的状态机副本复制技术一样，PBFT对每个副本节点提出了两个限定条件：
（1）所有节点必须是确定性的。也就是说，在给定状态和参数相同的情况下，操作执行的结果必须相同；
（2）所有节点必须从相同的状态开始执行。在这两个限定条件下，即使失效的副本节点存在，PBFT算法对所有非失效副本节点的请求执行总顺序达成一致，从而保证安全性。

接下去描述简化版本的PBFT算法，忽略磁盘空间不足和消息重传等细节内容。并且，本文假设消息验证过程是通过数字签名方法实现的，而不是更加高效的基于消息验证编码（MAC）的方法。

客户端

客户端c向主节点发送<REQUEST,o,t,c>请求执行状态机操作o，这里时间戳t用来保证客户端请求只会执行一次。客户端c发出请求的时间戳是全序排列的，后续发出的请求比早先发出的请求拥有更高的时间戳。例如，请求发起时的本地时钟值可以作为时间戳。

每个由副本节点发给客户端的消息都包含了当前的视图编号，使得客户端能够跟踪视图编号，从而进一步推算出当前主节点的编号。客户端通过点对点消息向它自己认为的主节点发送请求，然后主节点自动将该请求向所有备份节点进行广播。

副本发给客户端的响应为<REPLY,v,t,c,i,r>，v是视图编号，t是时间戳，i是副本的编号，r是请求执行的结果。

客户端等待f+1个从不同副本得到的同样响应，同样响应需要保证签名正确，并且具有同样的时间戳t和执行结果r。这样客户端才能把r作为正确的执行结果，因为失效的副本节点不超过f个，所以f+1个副本的一致响应必定能够保证结果是正确有效的。

如果客户端没有在有限时间内收到回复，请求将向所有副本节点进行广播。如果请求已经在副本节点处理过了，副本就向客户端重发一遍执行结果。如果请求没有在副本节点处理过，该副本节点将把请求转发给主节点。如果主节点没有将该请求进行广播，那么就有认为主节点失效，如果有足够多的副本节点认为主节点失效，则会触发一次视图变更。

本文假设客户端会等待上一个请求完成才会发起下一个请求，但是只要能够保证请求顺序，可以允许请求是异步的。

PBFT要系统共同维护一个状态，所有节点采取的行动一致。为此，需要运行三类基本协议，包括：一致性协议、检查点协议和视图更换协议。同时，一致性协议要求来自客户端的请求在每一个服务节点上都按照一个确定的顺序执行，这个协议把节点分为两类：主节点和从节点，主节点仅有一个并负责请求排序，从节点按照主节点排序处理请求。

1）主节点的“选举”
PBFT的主节点“选举”和Raft算法的选举不一样，只是通过一个模运算进行或者选择当前存活的节点编号最小的节点成为新的主节点。

p = v mod |R 
v 是view的编号，从0开始一直连续下去，这样可以理解为从replica 0 到 replica |R-1 依次当primary节点，当每一次view change发生时。

p = v mod |R|，其中p为节点编号、v为视图编号，|R|为节点数量。当主节点失效后就需要启动视图更换。

2）PBFT算法基本流程：

1）从全网节点选举出一个主节点（Leader），新区块由主节点负责生成。
（2）每个节点把客户端发来的交易向全网广播，主节点将从网络收集到需放在新区块内的多个交易排序后存入列表，并将该列表向全网广播。
（3）每个节点接收到交易列表后，根据排序模拟执行这些交易。所有交易执行完后，基于交易结果计算新区块的哈希摘要，并向全网广播。
（4）如果一个节点收到的2f（f为可容忍的拜占庭节点数）个其它节点发来的摘要都和自己相等，就向全网广播一条commit消息。
（5）如果一个节点收到2f+1条commit消息，即可提交新区块及其交易到本地的区块链和状态数据库。

3）算法核心三阶段流程
三阶段流程如下图所示，核心三阶段分别为pre-preare阶段（预准备阶段）、prepare阶段（准备阶段）和commit阶段（提交阶段），图中的C代表客户端，0、1、2、3代表节点的编号，打叉的3代表可能是一个故障节点或者问题节点，0为主节点。

image

首先，客户端向主节点发起请求，主节点0收到客户端请求，会向其它节点发送pre-prepare消息，其它节点就收到了pre-prepare消息，就开始了这个核心三阶段共识过程了。

我们采用三阶段协议来广播请求给replicas：pre-prepare, prepare, commit。
（1）pre-prepare阶段：

主节点收到客户端请求，给请求编号，并发送pre-pre类型信息给其他从节点。

image.png

从1节点收到pre-pre类型信息，如果同意这个请求的编号，如果同意就进入prepare阶段

（2）Prepare阶段：

从1节点同意主节点请求的编号，将发送prepare类型消息给主节点和其他两个从节点。如果不发，表示不同意。

image.png

图：从1节点发prepare信息给其他节点

从1节点如果收到另外两个从节点都发出的同意主节点分配的编号的prepare类型的消息，则表示从1节点的状态为prepared,该节点会拥有一个prepared认证证书。

为了防止viewchange导致主节点给请求分配的编号失效，引入commit阶段。

（3）commit阶段

从1节点进入prepared状态后，将发送一条COMMIT类型信息给其它所有节点告诉他们它有一个prepared认证证书了。

image.png

图：从1节点发commit类型信息给其他节点

如果从1节点收到2f+1条commit信息，证明从1节点已经进入commited状态。

只通过这一个节点，我们就能认为客户端的请求在需要的节点中都到达了prepared状态，每一个需要的节点都同意了主节点分配的编号。当一个请求在某个节点中到达commited状态后，该请求就会被该节点执行。

整个流程：

image

DBFT：小蚁区块链（delegated BFT，授权拜占庭容错机制）

用权益来选出记账人，然后记账人之间通过拜占庭容错算法 达成共识。
优点：专业化的记账人可以容忍任何类型的错误记账由多人协同完成，每一个区块都有最终性，不会分叉算法的可靠性有 严格的数学证明缺点：当三分之一或以上记账人停止工作后，系统将无法提供服务当三分之一或以上记账人联合作恶，且其他所有的记账人恰好分割为两个网络孤岛时，恶意记账人可以使系统出现分叉，但是会留下密码学证据