A General Framework for the Security Analysis of Blockchain Protocols

Andrew Lewis-Pye, Tim RoughgardenarXiv 2020 · OpenReview

TL;DR

This paper introduces a unified framework to formally analyze and compare different types of permissionless blockchain protocols (like PoW and PoS). It reveals fundamental trade-offs between liveness and security, particularly in partially synchronous networks, and establishes "certificates" as a key concept for achieving security in such settings.

What Problem Does This Paper Address?

Comparing different blockchain protocols (e.g., Proof-of-Work vs. Proof-of-Stake, or longest-chain vs. BFT-style consensus) is challenging because they have fundamentally different mechanisms for selecting block producers and achieving consensus. This lack of a common theoretical ground hinders direct, "apples-to-apples" comparisons and the development of a unified understanding of their relative merits and security guarantees. The authors aim to bridge this gap by creating a general framework that abstracts away protocol-specific details, allowing for a more principled analysis of their core properties.

Methods

The authors propose a "parsimonious abstraction" that blackboxes the user selection process, treating it as a "permitter oracle." This allows them to focus on the properties of this selection mechanism and its impact on protocol security and liveness under different network synchrony assumptions (synchronous, partially synchronous). They introduce key concepts like:

  • Resource Pool: Represents a user's balance (e.g., hashrate for PoW, stake for PoS) used for selection.
  • Sized vs. Unsized Settings: Differentiates protocols where the total resource balance is known (sized, typical for PoS) from those where it's unknown (unsized, typical for PoW).
  • Certificates: Stand-alone proofs of block confirmation, crucial for security in partially synchronous settings.
  • Permissioned Reducts: A way to decompose the analysis of permissionless protocols into analyzing a simpler, permissioned version and the user selection mechanism.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • CAP Theorem Analogy for Blockchains: The paper proves a CAP-type impossibility result: in the unsized and partially synchronous setting, a protocol cannot be both live (progressing) and secure (no conflicting blocks). This highlights a fundamental trade-off.
  • Certificates are Key to Partition Security: In partially synchronous settings, producing "certificates" (formal proofs of block confirmation) is shown to be both a necessary and sufficient condition for security. This explains why BFT protocols, which often produce such certificates, can achieve security where others might struggle.
  • Sized vs. Unsized Dictates Certificate Production: Protocols in the "unsized" setting (like PoW) cannot produce certificates, even in synchronous settings, if an adversary has a non-trivial resource balance. Conversely, protocols in the "sized" setting (like PoS) can be recalibrated to produce certificates.
  • Modular Analysis: The framework enables a modular approach to analyzing permissionless blockchains by reducing the problem to analyzing a permissioned version of the protocol and its user selection mechanism.

Key Results

  • Theorem 3.1: No protocol can be both adaptive (live in the unsized, partially synchronous setting) and partition secure.
  • Theorem 4.1: If a protocol is partition secure, it must produce certificates.
  • Theorem 6.1: In the synchronous and unsized setting, a live protocol cannot produce certificates in the presence of a non-trivial adversary.
  • Theorem 6.2: In the timed, bounded adversary, and sized setting, if a protocol is in "standard form," it can be recalibrated to produce certificates.

Limitations and Future Work

The authors acknowledge that their model simplifies the "honest vs. dishonest" user dichotomy and omits game-theoretic analysis of user incentives, which is crucial for real-world blockchain robustness. They suggest future work should integrate user incentives into the framework. Additionally, they propose formalizing the implementation of the "permitter oracle" itself, which would allow for a complete protocol specification and analysis. They also mention that other performance measures, such as "chain quality," were omitted for simplicity but are important for a full analysis.

Summary updated

Abstract

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. Byzantine fault-tolerant (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. This paper presents a parsimonious abstraction sufficient for capturing and comparing properties of many well-known permissionless blockchain protocols, simultaneously capturing essential properties of both proof-of-work (PoW) and proof-of-stake (PoS) protocols, and of both longest-chain-type and BFT-type protocols. Our framework blackboxes the precise mechanics of the user selection process, allowing us to isolate the properties of the selection process that are significant for protocol design. We demonstrate the utility of our general framework with several concrete results: 1. We prove a CAP-type impossibility theorem asserting that liveness with an unknown level of participation rules out security in a partially synchronous setting. 2. Delving deeper into the partially synchronous setting, we prove that a necessary and sufficient condition for security is the production of "certificates," meaning stand-alone proofs of block confirmation. 3. Restricting to synchronous settings, we prove that typical protocols with a known level of participation (including longest chain-type PoS protocols) can be adapted to provide certificates, but those with an unknown level of participation cannot. 4. Finally, we use our framework to articulate a modular two-step approach to blockchain security analysis that effectively reduces the permissionless case to the permissioned case.
BibTeX
@misc{lewispye2020general,
  author = {Andrew Lewis-Pye and Tim Roughgarden},
  title = {{A General Framework for the Security Analysis of Blockchain Protocols}},
  year = {2020},
  eprint = {2009.09480},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2009.09480},
}
Figure