锐客网

  1. 首页 > it技术 > >

4.7　拜占庭问题与算法

拜占庭问题（Byzantine Problem）更为广泛，讨论的是允许存在少数节点作恶（消息可能被伪造）场景下的一致性达成问题。拜占庭容错（Byzantine Fault Tolerant，BFT）算法讨论的是在拜占庭情况下对系统如何达成共识。
1.两将军问题
在拜占庭将军问题之前，就已经存在两将军问题（Two Generals Paradox）：两个将军要通过信使来达成进攻还是撤退的约定，但信使可能迷路或被敌军阻拦（消息丢失或伪造），如何达成一致？根据FLP不可能原理，这个问题无通用解。
2.拜占庭问题
拜占庭问题又叫拜占庭将军问题（Byzantine Generals Problem），是Leslie Lamport等科学家于1982年提出用来解释一致性问题的一个虚构模型。拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军（系统中的 多个节点）需要通过信使来传递消息，达成某些一致的决定。但由于将军中可能存在叛徒（系统中节点出错），这些叛徒将努力向不同的将军发送不同的消息，试图 干扰共识的达成。拜占庭问题即为在此情况下，如何让忠诚的将军们能达成行动的一致。
论文中指出，对于拜占庭问题来说，假如节点总数为N，叛变将军数为F，则当N≥3F+1时，问题才有解，由BFT算法进行保证。
例如，N=3，F=1时。
提案人不是叛变者，提案人发送一个提案出来，叛变者可以宣称收到的是相反的命令。则对于第三个人（忠诚者）收到两个相反的消息，无法判断谁是叛变者，则系统无法达到一致。
提案人是叛变者，发送两个相反的提案分别给另外两人，另外两人都收到两个相反的消息，无法判断究竟谁是叛变者，则系统无法达到一致。
更一般的，当提案人不是叛变者，提案人提出提案信息1，则对于合作者来看，系统中会有N-F份确定的信息1，和F份不确定的信息（可能为0或1，假设叛变者会尽量干扰一致的达成），N-F>F，即N>2F情况下才能达成一致。
当提案人是叛变者，会尽量发送相反的提案给N-F个合作者，从收到1的合作者看来，系统中会存在（N-F）/2个信息 1，以及（N-F）/2个信息0；从收到0的合作者看来，系统中会存在（N-F）/2个信息0，以及（N-F）/2个信息1；另外存在F-1个不确定的信 息。合作者要想达成一致，必须进一步对所获得的消息进行判定，询问其他人某个被怀疑对象的消息值，并通过取多数来作为被怀疑者的信息值。这个过程可以进一 步递归下去。
Leslie Lamport等人在论文《Reaching agreement in the presence of faults》中证明，当叛变者不超过1/3时，存在有效的拜占庭容错算法（最坏需要F+1轮交互）。反之，如果叛变者过多，超过1/3，则无法保证一定 能达到一致结果。
那么，当存在多于1/3的叛变者时，有没有可能存在解决方案呢？
设想F个叛变者和L个忠诚者，叛变者故意使坏，可以给出错误的结果，也可以不响应。某个时候F个叛变者都不响应，则L个 忠诚者取多数即能得到正确结果。当F个叛变者都给出一个恶意的提案，并且L个忠诚者中有F个离线时，剩下的L-F个忠诚者此时无法分别是否混入了叛变者， 仍然要确保取多数能得到正确结果，因此，L-F>F，即L>2F或N-F>2F，所以系统整体规模N要大于3F。
能确保达成一致的拜占庭系统节点数至少为4，此时最多允许出现1个坏的节点。
3.拜占庭容错算法
拜占庭容错算法（Byzantine Fault Tolerant，BFT）是面向拜占庭问题的容错算法，解决的是在网络通信可靠但节点可能故障情况下如何达成共识。拜占庭容错算法最早的讨论在1980 年Leslie Lamport等人发表的论文《Polynomial Algorithms for Byzantine Agreement》，之后出现了大量的改进工作。长期以来，拜占庭问题的解决方案都存在复杂度过高的问题，直到PBFT算法的提出。
1999年，Castro和Liskov于论文《Practical Byzantine Fault Tolerance and Proactive Recovery》中提出的Practical Byzantine Fault Tolerant（PBFT）算法，基于前人工作进行了优化，首次将拜占庭容错算法复杂度从指数级降低到了多项式级，目前已得到广泛应用。其可以在失效节 点不超过总数1/3的情况下同时保证Safety和Liveness。
PBFT算法采用密码学相关技术（RSA签名算法、消息验证编码和摘要）确保消息传递过程无法被篡改和破坏。
算法的基本过程如下：
·首先通过轮换或随机算法选出某个节点为主节点，此后只要主节点不切换，则称为一个视图（View）；
·在某个视图中，客户端将请求发送给主节点，主节点负责广播请求到所有其他副本节点；
·所有节点处理完成请求，将处理结果返回给客户端。客户端检查是否收到了至少f+1个来自不同节点的相同结果，作为最终结果。
主节点广播过程包括三个阶段的处理：预准备（pre-prepare）阶段、准备（prepare）阶段和提交（commit）阶段。预准备和准备阶段确保在同一个视图内请求发送的顺序正确；准备和提交阶段则确保在不同视图之间的确认请求是保序的：
·预准备阶段： 主节点为从客户端收到的请求分配提案编号，然后发出预准备消息<

，message>给各副本节点，其中message是客户端的请求消息，digest是消息的摘要；
·准备阶段： 副本节点收到预准备消息后，检查消息合法，如检查通过则向其他节点发送准备消息
，带上 自己的id信息，同时接收来自其他节点的准备消息。收到准备消息的节点对消息同样进行合法性检查。验证通过则把这个准备消息写入消息日志中。集齐至少2 f+1个验证过的消息才进入准备状态；
·提交阶段： 广播commit消息，告诉其他节点某个提案n在视图v里已经处于准备状态。如果集齐至少2 f+1个验证过的commit消息，则说明提案通过。
具体实现上还包括视图切换、checkpoint机制等，读者可自行参考论文内容，在此不再赘述。
4.新的解决思路
拜占庭问题之所以难解，在于任何时候系统中都可能存在多个提案（因为提案成本很低），并且要完成最终一致性确认过程十分困难，容易受干扰。
比特币的区块链网络在设计时提出了创新的PoW（Proof of Work）概率算法思路，针对这两个环节进行了改进。
首先，限制一段时间内整个网络中出现提案的个数（通过增加提案成本）；其次是放宽对最终一致性确认的需求，约定好大家都 确认并沿着已知最长的链进行拓展。系统的最终确认是概率意义上的存在。这样，即便有人试图恶意破坏，也会付出相应的经济代价（超过整体系统一半的计算 力）。
后来的各种PoX系列算法，也都是沿着这个思路进行改进，采用经济上的惩罚来制约破坏者。


来源：我是码农，转载请保留出处和链接！
【4.7　拜占庭问题与算法】本文链接：http://www.54manong.com/?id=967
'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646208", container: s }); })(); '); (window.slotbydup = window.slotbydup || []).push({ id: "u3646147", container: s }); })();

    推荐阅读


    上一篇：信用卡融资的优势，这些你了解过吗?

    下一篇：How Far are We from Solving Pedestrian Detection?