An exploration of the BFT consensus mechanism of Dfinty expressed as a succinct algorithm and proposed enhancements.


We explore a Byzantine Consensus protocol called Dfinity Consensus, recently published in a technical report. Dfinity Consensus solves synchronous state machine replication among n=2f+1 replicas with up to f Byzantine faults. We provide a succinct explanation of the core mechanism of Dfinity Consensus to the best of our understanding. We prove the safety and liveness of the protocol specification we provide. Our complexity analysis of the protocol reveals the follows. The protocol achieves expected O(f×Δ) latency against an adaptive adversary, (where Δ is the synchronous bound on message delay), and expected O(Δ) latency against a mildly adaptive adversary. In either case, the communication complexity is unbounded. We then explain how the protocol can be modified to reduce the communication complexity to O(n3) in the former case, and to O(n2) in the latter.


December, 2018