锐客网

  1. 首页 > it技术 > >

【区块链】PBFT（实用拜占庭容错）算法详解

区块链

拜占庭将军问题： 寻找一个方法，使得将军们能在一个有叛徒的非信任环境中建立对战斗计划的共识。
共识算法的核心是在正常的节点间形成对网络状态的共识。
共识算法协议的属性：
1）一致性：所有的非缺陷进程必须同意同一个值
2）正确性：如果所有的非缺陷进程有相同的初始值，那么所有的非缺陷进行所同意的值是同一个初始值。
3）可结束性：非缺陷进程必须最终必须确定一个值。
BFT拜占庭容错系统： 拜占庭容错技术被设计用来处理异常行为（包括硬件错误、网络拥塞、以及恶意攻击），被设计用来处理这些异常行为。
发生故障的节点是拜占庭节点，正常的节点为非拜占庭节点。
一致性协议： 一致性协议要求来自客户端的请求在每个服务节点上都按照一个确定的顺序执行。
一致性协议把服务器节点分为两类：主节点和从节点，其中主节点仅有1个。
在协议中，主节点负责将客户端的请求排序；从节点按照主节点提供的顺序执行请求。
视图:每个服务器工作时所设定的配置信息；
一致性协议至少包含3个阶段：request---请求，pre-prepare---序号分配，reply---响应。
有的会有prepare---交互，commit---序号确认这俩阶段。
PBFT（实用拜占庭容错）算法流程： PBFT算法前提，采用密码学算法保证节点之间的消息传送是不可篡改的。
PBFT容忍无效或者恶意节点数：f，为了保障整个系统可以正常运转，需要有2f+1个正常节点，系统的总节点数为：|R| = 3f + 1。也就是说，PBFT算法可以容忍小于1/3个无效或者恶意节点。
PBFT是一种状态机副本复制算法，所有的副本在一个视图（view）轮换的过程中操作，主节点通过视图编号以及节点数集合来确定，即：主节点 p = v mod |R|。v：视图编号，|R|节点个数，p：主节点编号。
PBFT算法每个客户端请求需要经过5个阶段，通过采用两次两两交互的方式在服务器达成一致后再执行客户端的请求。由于客户端不能从服务端获得任何服务器运行状态，PBFT中主节点是否发生错误只能由服务器监测。如果服务器在一段时间内不能完成客户端的请求，就会触发视图更换协议。
PBFT算法主体实现流程图如下：
【区块链】PBFT（实用拜占庭容错）算法详解
文章图片

C为客户端，0~3是服务节点。其中，0是主节点，3是故障节点。
request---请求，pre-prepare---序号分配，prepare---交互，commit---序号确认， reply---响应。
协议的基本过程如下：
1、客户端向主节点发送请求，激活主节点的服务操作。
2、当主节点收到请求后，启动三阶段的协议以向各节点广播请求。
1）pre-prepare阶段，主节点给请求赋值一个序列号n，广播序号分配消息和客户端的请求消息m，并将构造pre-prepare消息发送给各个节点；
2）prepare阶段，从节点接受pre-pare消息，向其他服务节点广播prepare消息。
3）commit阶段，各节点对试图内的请求和次序进行验证后，广播Commit消息，执行收到的客户端请求并给客户端以相应。
3、客户端等待来自不同节点的响应，若有m+1个响应相同，则该响应为运算的结果。

参考文献：
【【区块链】PBFT（实用拜占庭容错）算法详解】https://blog.csdn.net/jfkidear/article/details/81275974

    推荐阅读


    上一篇：【Thinking|C++中的static const

    下一篇：一种去掉偶尔产生不规则极端数值点的滤波方法