为什么BFT要求诚实节点数量大于总节点的三分之二

相信很多人都知道,BFT(Byzantine fault tolerance)要求诚实节点数量大于总节点的三分之二。

为什么会有这个要求?

多数派原则

多数派原则在分布式系统很常见,即确保网络分化情况下的决议唯一。其原理是,假如节点总数是2f+1,那么一项决议得到多于f个节点赞成则获得通过。leader选举中,网络分化下,只有具有多数派节点的部分才可能选出leader。多数派还可以用于副本管理,根据实际情况调整写副本数和读副本数,在可靠性和性能之间取得平衡。 在分布式系统,无论paxos,还是raft,以投票来达成共识,在整个达成共识的过程中都遵守多数派原则。

下面先看多数派原则在raft中应用。

raft

假定f表示系统同时允许最大故障节点数量(f节点数量决定了系统可用性的概率),在这种情况下,根据多数派原则,那么正常节点至少为f+1,即可以得出系统总节点数为2f+1。

BFT

在Raft协议中假设所有节点都是诚实节点,而在BFT假定系统存在一些作恶节点。 那么一个BFT中最多允许有多少个作恶节点?

进行逆向思考如下:

假如系统有f个作恶节点,那么在多数派系统,不作恶节点至少有f+1个。 f+1节点能够满足吗?不可以,网络分区是一直都存在,结合raft上,那么不作恶节点至少为2f+1,从而可以得出总节点数3f+1个。

参考

  1. 漫谈分布式系统、拜占庭将军问题与区块链
Share Comments
comments powered by Disqus