Skip to content

Latest commit

 

History

History
28 lines (13 loc) · 1.8 KB

consensus.md

File metadata and controls

28 lines (13 loc) · 1.8 KB

关于拜占庭场景通过投票达成共识的本质思考

为简化讨论,假设共有3f+1个节点,其中f个恶意节点,2f+1个诚实节点,并且这里只讨论对单个值的共识(多次迭代,即可实现对多个值的共识)。

这里假设投票模型是按view切换,每个view内有若干轮,每轮内诚实节点最多只会投1票。(篇幅原因不赘述了,类似pbft)

然后有个很关键的结论(引理1):每轮最多只有1个值能获得2f+1个投票。

证明略。

首先定义下锁定:每个view有一特定轮投票,在该轮对某个值投票,即锁定在该值。

根据引理1,该轮最多只有一个值能被2f+1个节点锁定。因此如果有2f+1个节点在某个view锁定了某个值,便可认为在这个view达成了共识;如果有某种机制保证到了下个view,这个值仍将继续被锁定,那么可以认为彻底达成了共识。

于是对锁定后的投票加个限制,一旦某个节点锁定在某个值,那么它只对这个值投票(此即安全性),除非得知2f+1个其他节点投了更新(view更高)的某个值(此即活性,解锁)。这样便能保证一旦2f+1个节点锁定在了某个值,即可认为彻底达成了共识。简而言之:共识=2f+1锁定,这是满足安全性的,接下来是活性。

又有个很关键的结论(引理2):如果锁定蕴含对之前view锁定值的解锁能力,那么在网络良好时,只要锁定最新值的节点作为leader,并且所有诚实节点都在同一个view,那么便可达成共识。

证明略。

所以,只要让锁定蕴含解锁能力,活性便也解决了。

于是只需要复用引理1,在锁定轮之前先进行一轮投票,只有得到2f+1个投票的值才是合法的锁定值。

未完待续