前言

关于拜占庭将军的问题,也很有意思,可以当作故事看看。

PBFT是Practical Byzantine Fault Tolerance的缩写,意为实用拜占庭容错算法。
1999年,卡斯托(Miguel Castro)与李斯克夫(Barbara Liskov)提出了实用拜占庭容错算法,解决了原始拜占庭算法效率不高的问题。

PBFT作为一种许可制的一种算法,应用于区块链的共识机制,具有很高的可靠性。节点之间通过协商达成共识一致,可以保证在不超过三分之一的“恶意”节点下,区块链系统正常地运转。

目前,PBFT算法已经广泛的应用于多家主流的区块链基础平台,例如EOS、Fabric、趣链、PlatON等,他们也在PBFT算法的基础上进行了改进。也涌现了很多衍生的共识算法,例如Tendermint、DBFT、CBFT…

PBFT算法流程

好了,上面一大堆的话主要是为了说明PBFT共识算法在当前区块链技术的重要性。

pbft流程

结合这个图片,来说说我对PBFT算法的理解。

参数定义

  • Primary:当前轮次的出块节点(也称主节点)
  • Replica:当前轮次的验证节点(其他共识节点的范称,也称从节点)
  • N:共识节点的数量,上图共有4个共识节点。
  • f:可容错的最大节点数量,上图可以允许的最大数量为1,满足3f+1=N
  • view:可以理解为当前Primary节点的任期

主节点Primary如何选取?

对于Primary节点的选取,其实有很多种方法。

  • 所有共识节点轮流坐庄的方式,一个节点成为Primary节点之后,生产一个区块,区块完成共识之后,将由下一个序号节点担任下一轮的Primary节点(这种情况共识节点数量其实是固定的)。
  • 结合DPOS选举,加入经济模型,投票选出每轮的共识节点,然后进行轮流出块(采用DPOS+PBFT的混合共识,每轮的共识节点可以是变化的)。

对于主节点的选取,可以加入VRF算法,以保证节点的随机性。

知乎上的VRF算法介绍,先挖一个坑,之后在去研究。

共识步骤

pbft流程

PBFT共识步骤其实主要可以分为三个阶段:PRE-PREPARE,PREPARE,COMMIT.

共识的步骤如下:

  • 主节点生成区块(GENERATE-BLOCK)
  • 主节点广播区块以发起共识流程(PRE-PREPARE)
  • 从节点验证区块后广播准备就绪消息(PREPARE)
  • 各节点收到至少2f+1个PREPARE消息后,广播提交确认消息(COMMIT)
  • 各节点收到至少2f+1个COMMIT消息后,将区块写入区块链(IMPORT-BLOCK)

PRE-PREPARE 阶段主要是出块节点出块之后立即广播区块给其他共识节点。(将军告诉士兵们要打仗了..)

PREPARE阶段主要是其他共识节点在收到区块后对区块进行验证, 验证通过后对区块HASH进行签名,并将签名广播给其他共识节点,在指定的超时时间内,一旦节点收到2f个不同节点的PREPARE消息后,则进入COMMIT阶段。(士兵们收到了将军的号令,并广播大家(将军、其他士兵)–我知道要打仗的这个消息。)

COMMIT阶段如果节点收到了2f个不同节点的PREPARE消息后,向其他节点发送COMMIT消息,同时接受其他节点广播的COMMIT消息,如果节点收到了包括自己在内的2f+1(1即自己)个COMMIT消息,则三阶段完成。(这个阶段可以理解为,士兵1在PREPARE阶段做的事情,其实士兵2是不晓得的,同样士兵1也不晓得士兵2有没有跟自己一样完成了PREPARE阶段告诉所有人--我知道要打仗这个事情。这个阶段完成之后的目的就是保证没有奸细,互通有无。)

当一个区块签名数收集到2f+1后,则此块被确认,共识完成,区块将被写入区块链。

共识异常

共识异常分多种情况:

  • 主节点未发起PRE-PREPARE,导致超时
  • 共识过程中节点未收到2f+1期待的确认,导致超时
  • 收到主节点的区块数据与自身区块链不匹配或共识消息异常

当共识在PRE-PREPARE和PREPARE阶段发生异常时,非主节点发起VIEW-CHANGE,以尝试切换主节点,在VIEW-CHANGE过程中,节点不再影响区块共识消息。主节点则不发起VIEW-CHANGE。

pbft_viewchange流程

VIEW-CHANGE的步骤如下:

  • 非主节点指定新view参数(这里是可拓展的,可以是块高h+记录这个共识节点的失败次数e),广播VIEW-CHANGE
  • 非主节点收到至少2f+1个VIEW-CHANGE消息后向新view节点发送VIEW-CHANGE-ACK
  • 新view节点收到至少2f+1个VIEW-CHANG-ACK后,向各节点广播NEW-VIEW

过程是和共识过程相似的,这里就不再阐述。