The New CAP Theorem on Blockchain Consensus Systems

One of the most emblematic theorems in the theory of distributed databases is Eric Brewer’s CAP theorem. It stresses the tradeoffs between Consistency, Availability, and Partition and states that it is impossible to guarantee all three of them simultaneously. Inspired by this, we introduce the new CAP theorem for autonomous consensus systems, and we demonstrate that, at most, two of the three elementary properties, Consensus achievement (C), Autonomy (A), and entropic Performance (P) can be optimized simultaneously in the generic case. This provides a theoretical limit to Blockchain systems’ decentralization, impacting their scalability, security, and real-world adoption. To formalize and analyze this tradeoff, we utilize the IoT micro-Blockchain as a universal, minimal, consensus-enabling framework. We define a set of quantitative functions relating each of the properties to the number of event witnesses in the system. We identify the existing mutual exclusions, and formally prove for one homogenous system consideration, that (A), (C), and (P) cannot be optimized simultaneously. This suggests that a requirement for concurrent optimization of the three properties cannot be satisfied in the generic case and reveals an intrinsic limitation on the design and the optimization of distributed Blockchain consensus mechanisms. Our findings are formally proved utilizing the IoT micro-Blockchain framework and validated through the empirical data benchmarking of large-scale Blockchain systems, i.e., Bitcoin, Ethereum, and Hyperledger Fabric.