pBFT算法的关键设计,你可能忽视了...

  • 子叶
  • 更新于 2021-04-15 11:54
  • 阅读 4306

pBFT为什么不要三个阶段,看完你就知道。

实用拜占庭容错算法,简称pBFT,是首个可以在实际应用场景中相对高效的解决拜占庭将军问题的BFT算法,由Miguel Castro和Barbara Liskov在1999年提出。

pBFT已经过多年的实践验证,算法成熟度高,网上有大量的资料和文章介绍拜占庭将军问题和pBFT算法原理,但大部分都只是关注于算法的流程和机制,却忽略了当中重要的设计。

因此,本文不再详细介绍拜占庭将军问题和pBFT的基本原理,而是重点介绍几个关键设计:

  1. 假设恶意节点数量为f个,为什么网络需要至少3f+1个节点?
  2. 为什么需要三个阶段?为什么两个阶段不行?
  3. 客户端为什么只需要f+1个确认即可?

本文中的概念和符号的定义,都尽可能保持与论文一致。但为了增加文章的可读性,我尽可能用简单的语言描述,方便大家理解。如果要进一步深刻理解,按需阅读原文。

01 为何至少3f+1?

拜占庭容错算法的目的是使得所有诚实的节点最终状态一致并且是正确的。要达到这样的目的,必须满足诚实的节点数量多于恶意的节点(少数服从多数)。

在实际的开放网络环境中,不仅有恶意节点,还有由于网络拥堵或机器故障等原因,存在部分短暂失联的节点,也需要作为考虑的因素。

因此,假设恶意节点和失联节点的数量均为f,全网节点总数量为N,那么按照少数服从多数原则,剩余的诚实节点必须满足N-f-f>f,由此可得,N>3f,即N不少于3f+1。

02 为何需要三个阶段?

在回答这个问题前,首先补充说明几个关键的知识点。

一、三个阶段,二个状态

pBFT的三个核心阶段为Pre-prepare、Prepare和Commit,两个状态分别为Prepared和Committed-local。某一节点接收到2f+1(含自己)条Prepare消息时,状态更改为Prepared并进入Commit阶段;当接收到2f+1(含自己)条Commit消息后,状态更改为Committed-local。

二、状态一致性

要保持诚实的节点保持状态一致,本质上只需要所有的节点按相同的顺序执行客户端的请求Request,换句话说,每一个序列n要求关联唯一的Request消息。

三、View Change

开始新一轮共识后,在任何阶段内无按时完成共识时,任何节点都有权发起View Change更换主节点,新的主节点在此过程中会收集已进入Prepared状态对应的Pre-prepare消息,并在新的一轮共识中对这部分消息重新共识。

举个例子,节点A已进入Prepared状态,但下一阶段时发起View Change消息,并将对应的Pre-prepare消息一起广播,那么新的节点B会接收到此Pre-prepare消息。

回到问题本身,假设不需要三个阶段,只需要Pre-prepare、Prepare,有可能出现如下情况:某一节点A进入Prepared状态后,认为已完成共识并执行请求Q,但其他节点并没有在规定的时间内进入Prepared状态而发起View Change,当中的View Change消息并不包含请求Q对应的Pre-Prepare消息,又由于A认为已正常完成共识并没有发生View Change,所以最终导致新的主节点并没有收到Q对应的Pre-Prepare消息,从而导致序列n会分配给另一个请求Q'。

简单来说,两个阶段无法保证发生View Change时,部分已共识的请求在新一轮共识中继续完成。

那么,为什么三个阶段就可以避免这种情况呢?

因为只要有一个节点进入Committed-local状态,意味着有2f+1个节点进入Prepared状态,而View Change发起成功的要求同样是满足至少2f+1,总的来说,即使有f个恶意节点,也可以保证至少1个诚实的节点将对应Pre-Prepare消息发给新的主节点继续完成共识,从而保证一个序列n永远对应一个请求。

03 为何客户端只需要f+1次确认?

理解了问题2后,问题3也就很好理解了。客户端f+1确认是为了保证至少有一个诚实节点已经完成了3阶段的共识,只要一个诚实节点完成了,意味着其他诚实节点在一定能够完成,所以只需要f+1即可。

04 结束语

作为一名工程师,除了要理解算法的机制(How)本身,更需要理解机制如此设计的原因(Why),只有这样才能算得上深刻理解一个算法。

点赞 2
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

1 条评论

请先 登录 后评论
子叶
子叶
区块链爱好者。 专注区块链技术和分享。 gzh:区块链Hacker。