PBFT协议为什么要求N>3f+1

in #consensus2 years ago

原文链接 - https://willzhuang.github.io/2018/05/25/PBFT%E5%8D%8F%E8%AE%AE%E4%B8%BA%E4%BB%80%E4%B9%88%E8%A6%81%E6%B1%82N-3f-1/

最坏的情况是:f个节点是有问题的,由于到达顺序的问题,有可能f个有问题的节点比正常的f个节点先返回消息,又要保证收到的正常的节点比有问题的节点多,所以需要满足N-f-f>f => N>3f,所以至少3f+1个节点。

为什么至少要2f个prepare (包括自己的pre-prepare共2f+1)。这是因为之前论证的,如果有f个fault 节点,那么节点总数至少是N=3f+1。简单说一下论证过程,假设总数N个节点,f个fault节点,那么必须接收到N-f个消息应答,才能够判断出结果(因为fault节点可能不发送应答)。N-f个应答中有f个可能是假的(fault节点发出的),那么真实的是N-f-f,要求真实的应答大于假的应答,即N-f-f > f ==> N > 3f。所以: N_min = 3f+1 所以在prepare和commit两个阶段必须收到2f+1(包括自己) 的应答消息,才能证明有f+1非fault节点发送了应答。(注意前提是非fault对于相同的消息,会产生相同的消息应答)那么这里也有个问题:就是接收2f+1个消息的时,判断是否一致,是否需要对比数据的的签名。我的看法是,如果2f+1个v,n都相同,d(m)只需要f+1相同就可以了。否则就共识失败了。

Coin Marketplace

STEEM 0.17
TRX 0.15
JST 0.028
BTC 60045.81
ETH 2420.35
USDT 1.00
SBD 2.43