锐客网

  1. 首页 > it技术 > >

PBFT算法实现过程

区块链技术

转载：https://www.jianshu.com/p/2383c7841d41 PBFT算法 三个阶段：预准备（pre-prepare）、准备（prepare）、和确认（commit）
PBFT算法实现过程
文章图片

步骤：

  1. 从全网节点选举出一个主节点（Leader），新区块由主节点负责生成
  2. Pre-Prepare：每个节点把客户端发来的交易向全网广播，主节点0将从网络收集到需放在新区块内的多个交易排序后存入列表，并将该列表向全网广播，扩散至123
  3. Prepare：每个节点接收到交易列表后，根据排序模拟执行这些交易。所有交易执行完后，基于交易结果计算新区块的哈希摘要，并向全网广播，1->023，2->013，3因为宕机无法广播
  4. Commit：如果一个节点收到的2f（f为可容忍的拜占庭节点数）个其它节点发来的摘要都和自己相等，就向全网广播一条commit消息
  5. Reply：如果一个节点收到2f+1条commit消息，即可提交新区块及其交易到本地的区块链和状态数据库。
拜占庭容错能够容纳将近1/3的错误节点误差，IBM创建的Hyperledger 0.6版本就是使用了该算法作为共识算法（1.0版本已弃用，使用kafka）。
【PBFT算法实现过程】这个机制下有一个叫视图view的概念，在一个视图里，一个是主节点，其余的都叫备份节点。主节点负责将来自客户端的请求给排好序，然后按序发送给备份节点们。但是主节点可能会是拜占庭的：它可能会给不同的请求编上相同的序号，或者不去分配序号，或者让相邻的序号不连续。备份节点应当有职责来主动检查这些序号的合法性，并能通过timeout机制检测到主节点是否已经宕掉。当出现这些异常情况时，这些备份节点就会触发视图更换view change协议来选举出新的主节点。
视图是连续编号的整数。主节点由公式p = v mod |R|计算得到，这里v是视图编号，p是副本编号，|R|是副本集合的个数。当主节点失效的时候就需要启动视图更换（view change）过程。
预准备阶段
在预准备阶段，主节点分配一个序列号n给收到的请求，然后向所有备份节点群发预准备消息，预准备消息的格式为<
,m>，这里v是视图编号，m是客户端发送的请求消息，d是请求消息m的摘要。
请求本身是不包含在预准备的消息里面的，这样就能使预准备消息足够小，因为预准备消息的目的是作为一种证明，确定该请求是在视图v中被赋予了序号n，从而在视图变更的过程中可以追索。另外一个层面，将“请求排序协议”和“请求传输协议”进行解耦，有利于对消息传输的效率进行深度优化。
备份节点对预准备消息的态度：
只有满足以下条件，各个备份节点才会接受一个预准备消息：
  1. 请求和预准备消息的签名正确，并且d与m的摘要一致。
  2. 当前视图编号是v。
  3. 该备份节点从未在视图v中接受过序号为n但是摘要d不同的消息m。
  4. 预准备消息的序号n必须在水线上下限h和H之间。
水线存在的意义在于防止一个失效节点使用一个很大的序号消耗序号空间。
进入准备阶段：
如果备份节点i接受了预准备消息<
,m>，则进入准备阶段。在准备阶段的同时，该节点向所有副本节点发送准备消息
，并且将预准备消息和准备消息写入自己的消息日志。如果看预准备消息不顺眼，就什么都不做。
接受准备消息需要满足的条件：
包括主节点在内的所有副本节点在收到准备消息之后，对消息的签名是否正确，视图编号是否一致，以及消息序号是否满足水线限制这三个条件进行验证，如果验证通过则把这个准备消息写入消息日志中。
准备阶段完成的标志：
我们定义准备阶段完成的标志为副本节点i将(m,v,n,i)记入其消息日志，其中m是请求内容，预准备消息m在视图v中的编号n，以及2f个从不同副本节点收到的与预准备消息一致的准备消息。每个副本节点验证预准备和准备消息的一致性主要检查：视图编号v、消息序号n和摘要d。
预准备阶段和准备阶段确保所有正常节点对同一个视图中的请求序号达成一致。。
进入确认阶段
当(m,v,n,i)条件为真的时候，副本i将向其他副本节点广播，于是就进入了确认阶段。每个副本接受确认消息的条件是：
  1. 签名正确；
  2. 消息的视图编号与节点的当前视图编号一致；
  3. 消息的序号n满足水线条件，在h和H之间。
一旦确认消息的接受条件满足了，则该副本节点将确认消息写入消息日志中。（补充：需要将针对某个请求的所有接受的消息写入日志，这个日志可以是在内存中的）。
接受确认消息需要满足的条件
我们定义确认完成committed(m,v,n)为真得条件为：任意f+1个正常副本节点集合中的所有副本i其prepared(m,v,n,i)为真；本地确认完成committed-local(m,v,n,i)为真的条件为：prepared(m,v,n,i)为真，并且i已经接受了2f+1个确认（包括自身在内）与预准备消息一致。确认与预准备消息一致的条件是具有相同的视图编号、消息序号和消息摘要。
确认被接受的形式化描述
确认阶段保证了以下这个不变式：对某个正常节点i来说，如果committed-local(m,v,n,i)为真则committed(m,v,n)也为真。这个不变式和视图变更协议保证了所有正常节点对本地确认的请求的序号达成一致，即使这些请求在每个节点的确认处于不同的视图。更进一步地讲，这个不变式保证了任何正常节点的本地确认最终会确认f+1个更多的正常副本。
故事的终结
每个副本节点i在committed-local(m,v,n,i)为真之后执行m的请求，并且i的状态反映了所有编号小于n的请求依次顺序执行。这就确保了所有正常节点以同样的顺序执行所有请求，这样就保证了算法的正确性。在完成请求的操作之后，每个副本节点都向客户端发送回复。副本节点会把时间戳比已回复时间戳更小的请求丢弃，以保证请求只会被执行一次。
使用计时器的超时机制触发视图变更事件
视图变更将在主节点失效的时候仍然保证系统的活性。视图变更可以由超时触发，以防止备份节点无期限地等待请求的执行。备份节点在接收到一个有效请求，但是还没有执行它时，会查看计时器是否在运行，如果没有，那么它将启动计时器；当请求被执行时就把计时器停止。如果计时器超时，将会把视图变更的消息向全网广播。
PBFT算法实现过程
文章图片

各个节点会收集视图变更信息，并发送确认给 view v+1 中的主节点。新的主节点收集了视图变更和视图变更确认消息（包含自己的信息），然后选出一个checkpoint作为新view处理请求的起始状态。它会从checkpoint的集合中选出编号最大（假设编号为h）的checkpoint。接下来，主节点会从h开始依次选取h到h+L（L是高低水位之差）之间的编号n对应的请求在新的view中进行pre-prepare，如果一条请求在上一个view中到达了committed状态，主节点就选取这个请求开始在新的view中进行第三阶段。但是如果选取的请求在上一view中并没有被prepare，那它的编号n有可能是不被同意的，我们选择在新的view中作废这样的请求。

    推荐阅读


    上一篇：算法导论 — 8.3 基数排序

    下一篇：大数据面试集锦---Hadoop篇