为什么PBFT需要3个阶段消息?

PBFT 解决的是在拜占庭环境下,如何提供一致性,以及如何持续的提供一致性的问题

前言

在面试的时候,很多同学的简历熟悉PBFT共识算法,在现场面试的时候,却只能说个主要逻辑,离完整的算法,还差十万八千里,相似从网络上看了一些文章,就算是熟悉了。当我问“为什么PBFT需要3个阶段消息?2个阶段行不行”时,还没有人能回答出来。

回答这个问题,还要从PBFT要解决的本质问题说起,所以我打算以这样一个思路,为大家回答问题:

  • PBFT与拜占庭问题
  • 拜占庭节点在网络中的行为
  • 什么是3阶段消息
  • 3阶段消息解决什么问题
  • 为什么不能只有前2个阶段
  • 论文使用的2个不变性
  • 为什么3个阶段可以达成一致性

PBFT与拜占庭问题

莱斯利·兰波特在其论文[1]中描述了如下拜占庭问题:

一组拜占庭帝国的将军分别各率领一支军队共同围困一座城市。为了简化问题,将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻,或部分军队撤离可能会造成灾难性后果,因此各位将军必须通过投票来达成一致策略,即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向,他们只能通过信使互相联系。在投票过程中,每位将军都将自己投票进攻还是撤退的信息,通过信使分别通知其他所有将军,这样一来每位将军根据自己的投票,和其他所有将军送来的信息,就可以知道共同的投票结果,而决定行动策略。

问题在于,将军中可能出现叛徒(坏将军),他们不仅可能向较为糟糕的策略投票,还可能选择性地发送投票信息。阻止好将军达成一致的形成策略。

摘自:维基百科:拜占庭将军问题,有删改。

很多人喜欢玩狼人杀,我也喜欢,但我玩的很菜,我用狼人杀跟拜占庭将军问题做个类比。

在狼人杀开局的时候,你是好人,并且不知道自己的队友是谁,也不知道狼人是谁,但所有的好人都有一个共同的目的:干死狼人,好人获胜。所以游戏中需要使用技巧和策略,达成目的。

拜占庭将军问题是类似的,好的将军不知道其他将军是好的,还是坏的,但所有好的将军的目的是:行动一致,共同进退。所以,它们也需要策略达成一致。

BFT是一类解决拜占庭将军问题的策略/算法:让非拜占庭节点达成一致的算法。在这类论文中,拜占庭节点指“坏”的将军,非拜占庭节点指“好”的将军。

PBFT是实用拜占庭算法(Practical Byzantine Fault Tolerance)的缩写,该论文与1999年发表,另外2001年又发表了一篇Practical Byzantine Fault Tolerance and Proactive Recovery,让PBFT拥有恢复能力。

PBFT作为解决拜占庭问题的策略:非拜占庭节点不知道哪些是拜占庭节点,哪些是非拜占庭节点,PBFT要让非拜占庭节点达成一致

拜占庭节点在网络中的行为

拜占庭问题是在分布式对等网络,对通信容错所提出来的。在真实世界中,拜占庭问题是什么样的?

通常使用拜占庭行为,描述拜占庭节点可能的行为,拜占庭行为有:

  • 任何不遵守协议的动作
  • 恶意代码、节点
  • 代码bug
  • 网络故障、数据包损坏
  • 磁盘崩掉、重复丢失
  • 无权限时加入

什么是3阶段消息

3阶段消息

3阶段消息是:Pre-prepare、Prepare和Commit。每个消息都会包含数字签名,证明消息的发送者,以及消息类型,下文中会省略。

Pre-prepare消息由主节点发出,包含:

  • 当前view:v
  • 主节点分配给请求的序号n
  • 请求的摘要d
  • 请求本身m

务必记牢,m、v、n、d,后面会使用缩写

Prepare是副本节点收到Pre-prepare消息后,做出的响应,发送给所有副本节点,包含:

  • v
  • n
  • d

Prepared状态:副本i有Pre-prepare消息,且收到2f个有效的Prepare消息。

副本i达到Prepared状态,可以发送Commit消息,Commit消息的内容和Prepare消息内容相同,但消息类型和数字签名是不同的,所以可以区分。

m可以使用d代替,所以Prepare和Commit消息使用d代替m,来节省通信量。

3阶段消息解决什么问题

前面提到,PBFT解决的是拜占庭问题的一致性,即让非拜占庭节点达成一致。更具体的说:让请求m,在view内使用序号n,并且完成执行m,向客户端发送响应

为什么不能只有前2个阶段消息

这个问题的等价问题是:为什么Pre-prepare和Prepare消息,不能让非拜占庭节点达成一致?

Pre-prepare消息的目的是,主节点为请求m,分配了视图v和序号n,让至少f+1个非拜占庭节点对这个分配组合<m, v, n>达成一致,并且不存在<m', v, n>,即不存在有2个消息使用同一个v和n的情况。

Prepared状态可以证明非拜占庭节点在只有请求m使用<v, n>上达成一致。主节点本身是认可<m, v, n>的,所以副本只需要收集2f个Prepare消息,而不是2f+1个Prepare消息,就可以计算出至少f个副本节点是非拜占庭节点,它们认可m使用<v, n>,并且没有另外1个消息可以使用<v, n>

既然1个<v, n>只能对应1个请求m了,达到Prepared状态后,副本i执行请求m,不就达成一致了么?

并不能。Prepared是一个局部视角,不是全局一致,即副本i看到了非拜占庭节点认可了<m, v, n>,但整个系统包含3f+1个节点,异步的系统中,存在丢包、延时、拜占庭节点故意向部分节点发送Prepare等拜占庭行文,副本i无法确定,其他副本也达到Prepared状态。如果少于f个副本成为Prepared状态,然后执行了请求m,系统就出现了不一致。

所以,前2个阶段的消息,并不能让非拜占庭节点达成一致。

如果你了解2PC或者Paxos,我相信可以更容易理解上面的描述。2PC或Paxos,第一步只是用来锁定资源,第2步才是真正去Do Action。把Pre-prepare和Prepare理解为第一步,资源是<v, n>,只有第一步是达不成一致性的。

2个不变性

PBFT的论文提到了2个不变性,这2个不变性,用来证明PBFT如何让非拜占庭节点达成一致性

第1个不变性,它是由Pre-prepare和Prepare消息所共同确保的不变性:非拜占庭节点在同一个view内对请求的序号达成共识。关于这个不变性,已经在为什么不能只有前2个阶段消息中论述过。

介绍第2个不变性之前,需要介绍2个定义。

  • committed-local:副本i已经是Prepared状态,并且收到了2f+1个Commit消息。
  • committed:至少f+1个非拜占庭节点已经是Prepared状态。

第2个不变性,如果副本i是committed-local,那么一定存在committed。

2f+1个Commit消息,去掉最多f个拜占庭节点伪造的消息,得出至少f+1个非拜占庭节点发送了Commit消息,即至少f+1个非拜占庭节点是Prepared状态。所以第2个不变性成立。

为什么3个阶段消息可以达成一致性

committed意味着有f+1个非拜占庭节点可以执行请求,而committed-local意味着,副本i看到了有f+1个非拜占庭节点可以执行请求,f+1个非拜占庭节点执行请求,也就达成了,让非拜占庭节点一致。

虽然我前面使用了2PC和Paxos做类比,但不意味着PBFT的Commit阶段就相当于,2PC和Paxos的第2步。因为2PC和Paxos处理的CFT场景,不存在拜占庭节点,它们的主节点充当了统计功能,统计有多少节点完成了第一步。PBFT中节点是存在拜占庭节点的,主节点并不是可靠(信)的,不能依赖主节点统计是否有f+1个非拜占庭节点达成了Prepared,而是每个节点各自统计,committed-local让节点看到了,系统一定可以达成一致,才去执行请求。

总结

本文介绍了2个阶段消息是无法达成一致的原因,而为什么3阶段消息可以。最核心的还是要理解好,PBFT解决了什么问题,以及它是如何解决的。

PBFT解决的是在拜占庭环境下,如何提供一致性,以及如何持续的提供一致性的问题。本文只介绍了如何提供一致性,没有提如何持续提供一致性,即PBFT的可用性。现在,不妨思考一下,View Change是如何保证切换时一致性的,是否也需要2个不变性的支持呢?

作者:大彬 原文: http://lessisbetter.site/2020/03/15/why-pbft-needs-3-phase-message/

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

  • 发表于 2020-03-18 21:03
  • 阅读 ( 2376 )
  • 学分 ( 77 )
  • 分类:入门/理论

2 条评论

请先 登录 后评论
石头
石头

5 篇文章, 394 学分