LinBFT: Linear-Communication Byzantine Fault Tolerance for Public Blockchains

Understand

This paper presents LinBFT, a novel Byzantine fault tolerance (BFT) protocol for blockchain systems that achieves amortized O(n) communication volume per block under reasonable conditions (where n is the number of participants), while satisfying determinist guarantees on safety and liveness.

• This significantly improves previous results, which either incurs quadratic communication complexity, or only satisfies safety in a probabilistic sense.
• LinBFT is based on the popular PBFT protocol, and cuts down its $O(n^4)$ complexity with three tricks, each by $O(n)$: linear view change, threshold signatures, and verifiable random functions.
• All three are known, i.e., the solutions are right in front of our eyes, and yet LinBFT is the first $O(n)$ solution with deterministic security guarantees.