Byzantine quorum

Why Byzantine quorum is$ 2f + 1?

$ nnodes, $ fByzantine nodes, $ n - fhonest nodes

Let$ abe the quorum

For safety:

Assume that honest nodes are devided into two sets equally and Byzantine nodes vote for the both

In this case, the number of votes must be lower than the quorum for safety

$ (n - f)/2 + f < a

$ ∴ (n + f)/2 < a(1)

For liveness, honest nodes must be able to form a quorum

$ n - f ≧ a(2)

From (1) and (2), for the existence of$ a,

$ (n + f) / 2 < n - f

$ f < n/3

$ ∴ n \geq 3f +1

If $ n = 3f + 1, from (1) and (2),

$ (4f + 1)/2 < a \leq 2f + 1

$ ∴ a = 2f + 1

minaminao.icon < If $ n=kf,

$ (k+1)f/2 < a \le (k-1)f

$ \frac{(k+1)n}{2k} < a \le \frac{(k-1)n}{k}

$ k=1: $ n<a \le 0 (impossible)

$ k=2: $ \frac{3n}{4}<a \le \frac{n}{2} (impossible)

$ k=3: $ \frac{2n}{3}< a \le \frac{2n}{3} (impossible)

$ k=4: $ \frac{5n}{8} < a \le \frac{3n}{4}

$ k\to \infty: $ \frac{n}{2}<a\le n

Message complexity of quorum voting

Authenticator complexity: $ O(n^2) All nodes receive 2f + 1 of votes and every vote is$ O(1)

PBFT's view-change: $ O(n^3)Each message includeds 2f + 1 of votes for a latest checkpoint i.e.$ O(n)

nrryuya.icon > Each votes for a checkpoint can be aggregated. Any set of votes for a checkpoint is allowed -> view-change messages can not be aggregated ->$ O(n^2)at least

Message complexity: All to All ->$ O(n^2), Leaderful Hub and Spoke ->$ O(n)

nrryuya.icon > Gossip?

Synchronous

The threshold is $ f + 1

In synchronous assumption, validators vote for the same block (i.e. no split) if the leader is honest