Blockchain protocols differ in fundamental ways, including the mechanics of selecting users to produce blocks (e.g., proof-of-work vs. proof-of-stake) and the method to establish consensus (e.g., longest chain rules vs. BFT-inspired protocols). These fundamental differences have hindered “apples-to-apples” comparisons between different categories of blockchain protocols and, in turn, the development of theory to formally discuss their relative merits.
In this paper, my co-author Tim Roughgarden and I present a parsimonious abstraction sufficient for capturing and comparing properties of many well-known permissionless blockchain protocols. Our framework blackboxes the precise mechanics of the user selection process, allowing us to isolate the properties of the selection process which are significant for protocol design. We illustrate the framework’s utility with two results. First, we prove an analog of the CAP theorem from distributed computing for our framework. This theorem shows that a fundamental dichotomy holds between protocols that are adaptive, in the sense that they can function given unpredictable levels of participation, and protocols that have certain finality properties. Second, we formalize the idea that proof-of-work (PoW) protocols and non-PoW protocols can be distinguished by the forms of permission that users are given to carry out updates to the state.
Resource Pools and the CAP Theorem, pdf.
This is joint work with Tim Roughgarden.