拜占庭网络下的共识

[AlexiaChen]

前言

分布式共识算法大概分为非拜占庭容错和拜占庭容错(BFT)这两类。非拜占庭共识有些时候又称为Crash Fault Tolerance(CFT)，也就是崩溃错误容忍，就是我们平时更经常听过的Paxos， Raft了，这类分布式网络下只考虑节点不响应，宕机崩溃的情况，分布式网络怎样继续工作达成共识的问题。而拜占庭容错就是要考虑拜占庭节点了，这种节点就会作恶，不仅仅可能不回复消息，可能还会回复假消息，在这样有非法节点的分布式网络下，这是BFT家族算法考虑的共识问题，BTF共识网络开销太大，后来1999年才出现了PBFT，开销降低到了O(n^2)， 这样好多了。除了BFT家族，还有一种是非BFT的，比如PoW， PoS，DPoS这类适用于大网络环境下，但是据说DPoS早期是没有被数学证明过是拜占庭容错的，BFT类是有大量的研究和学术脉络了，早被证明正确了，比如HotStuff，还有近期的小飞象算法。

这里需要重点讲述的就是PBFT算法的大致思想，以及其他的一些用到的工程实现是怎样做的，比如Tendermint这类工具框架。

正文

PBFT算法

PBFT的算法需要对错误节点的数量进行一个预估建模，就是要估计作恶节点的最大数量，设作恶节点的数量是f，那么节点的总数就应该是n，其中n >= 3*f + 1。也就是要比3倍的作恶节点还多，换句话说，正常节点数量是Q= n - f = 2*f + 1, 正常节点是作恶节点的2倍还多,这样才可以保证容错，符合服从大多数的民主机制。

PBFT主要是基于状态机的三阶段提交，其中有主节点和从节点，从节点也就是接收方状态机副本了：

• pre-prepare： 主节点P2P广播发送消息m，从节点从P2P收到消息m，就进入 prepare阶段
• prepare： 从节点P2P广播发送消息m的摘要Digest(m)的prepare消息， 如果其他从节点接收到关于消息m的2*f + 1个prepare消息，那么就说明大部分节点已经认同了这个消息m，进入commit阶段
• commit： 从节点P2P广播发送消息m的摘要Digest(m)的commit消息，如果其他从节点收到关于消息m的2*f + 1个commit消息，就说明已经有大部分节点执行提交了这个消息m，然后它提交这个消息后，返回reply消息给client，表示提交成功

最后client收到f + 1个reply消息后，就确认了。接下来client发送下一个消息，通过主节点扩散到全网，重复以上步骤。

优缺点也明显，通信开销虽然降低到了O(n^2)，但是通信开销还是大，不适用大规模的类似BTC的动态网络，节点到达100个，性能下降很快，只适用于私有链或者联盟链，所以Fabric等用PBFT算法。因为随着n的变大，f的值也要随之调整，PBFT这些参数是个固定的，动态增加删除很复杂。优点也是有的，这样达成的共识不容易分叉。

Tendermint中的PBFT变种算法

Tendermint作为一个共识引擎，它里面实现的就是一个PBFT类的变种，下面来讲解下它的思想，该共识也是三阶段提交， 5种状态的状态机协议，其中2种节点角色：Proposer， Validator：

• NewHeigh： 完成提交一个新块到了一个新高度就进入NewHeigh状态，选举出一个Proposer，接下来就是Proprosal阶段
• Proprosal： 在propose开始阶段，被选中的proposer会给P2P广播一个proposal。如果proposer锁定在上一轮中的block上，那么proposer在本轮中发起的proposal会是锁定的block，并且在proposal中加上proof-of-lock字段。
• prevote: 在Prevote开始阶段，每个Validator会判断自己是否锁定在上一轮的proposed区块上，如果锁定在之前的proposal区块中，那么在本轮中继续为之前锁定的proposal区块签名并广播prevote投票。否则为当前轮中接收到的proposal区块签名并广播prevote投票。如果由于某些原因当前Validator并没有收到任何proposal区块，那么签名并广播一个空的prevote投票。
• Precommit: 在precommit开始阶段，每个Validator会判断，如果收集到了超过2/3 prevote投票，那么为这个区块签名并广播precommit投票，并且当前Validator会锁定在这个区块上，同时释放之前锁定的区块，一个Validator一次只能锁定在一个区块上。如果一个Validator收集到超过2/3空区块（nil)的prevote投票，那么释放之前锁定的区块。处于锁定状态的Validator会为锁定的区块收集prevote投票，并把这些投票打成包放入proof-of-lock中，proof-of-lock会在之后的propose阶段用到。如果一个Validator没有收集到超过2/3的prevote投票，那么它不会锁定在任何区块上。这里，介绍一个重要概念：PoLC，全称为 Proof of Lock Change，表示在某个特定的高度和轮数(height, round)，对某个块或 nil (空块)超过总结点 2/3 的Prevote投票集合，简单来说 PoLC 就是 Prevote 的投票集。在precommit阶段后期，如果Validator收集到超过2/3的precommit投票，那么Validator进入到commit阶段。否则进入下一轮的propose阶段。
• Commit:
  • commit阶段分为两个并行的步骤：
    • Validator收到了被全网commit的区块，Validator会为这个区块广播一个commit投票。
    • Validator需要为被全网络precommit的区块，收集到超过2/3commit投票。 一旦两个条件全部满足了，节点会将commitTime设置到当前时间上，并且会进入NewHeight阶段。在整个共识过程的任何阶段，一旦节点收到超过2/3commit投票，那么它会立刻commit块。