Synchronous BFT Under an Information Theoretic Setting with Private Observations

Byzantine Fault Tolerance (BFT) protocols enable reliable consensus in distributed systems, even with malicious nodes. Synchronous BFT protocols provide the strongest fault tolerance, ensuring security as long as more than half the nodes are honest, leveraging cryptographic signatures implemented via asymmetric algorithms. This paper studies the possibility of eliminating the reliance on cryptographic signatures and trusted third parties to distribute public and private keys for synchronous BFT. We formulated a synchronous BFT problem where each node has an unbounded computational power and can have a private observation of a random variable. The joint distribution of all the random variables is known to all nodes. We call this problem Information-Theoretic BFT (IT-BFT). To maintain liveness, we partition the nodes into two layers, with Layer 1 containing at most one malicious node. The performance of a secure IT-BFT protocol is quantified using the consensus rate defined as the entropy of the consensus information gained per consensus round, and the consensus capacity of an IT-BFT problem is the supermum of consensus rate of all secure IT-BFT protocols. For a system with n nodes and f malicious nodes, we show that the Gács-Körner (GK) common information of the Layer 1 nodes is a lower bound on the consensus capacity, which is tight for a family of secure IT-BFT protocols when n=2 f+1. When n ≥ 2 f+2, a better lower bound on the consensus capacity is obtained, which can be strictly higher than the GK common information bound.