A Survey of Distributed Consensus Protocols for Blockchain Networks

Comprehensive Analysis of Blockchain Consensus Mechanisms
Yang Xiao, Ning Zhang, Wenjing Lou, Y. Thomas Hou
Virginia Polytechnic Institute and State University, VA, USA | Washington University in St. Louis, MO, USA
Read PDF Download PDF Translate PDF

Abstract

Since the inception of Bitcoin, cryptocurrencies and the underlying blockchain technology have attracted an increasing interest from both academia and industry. Among various core components, consensus protocol is the defining technology behind the security and performance of blockchain. From incremental modifications of Nakamoto consensus protocol to innovative alternative consensus mechanisms, many consensus protocols have been proposed to improve the performance of the blockchain network itself or to accommodate other specific application needs.

In this survey, we present a comprehensive review and analysis on the state-of-the-art blockchain consensus protocols. To facilitate the discussion of our analysis, we first introduce the key definitions and relevant results in the classic theory of fault tolerance which help to lay the foundation for further discussion. We identify five core components of a blockchain consensus protocol, namely, block proposal, block validation, information propagation, block finalization, and incentive mechanism.

Key Insight: The design of blockchain consensus protocols should follow the rigor established in prevailing wisdom of cryptography, security, and distributed systems, rather than in an ad hoc manner. This is particularly true when the consensus protocol regulates significant financial values and societal trust.

Key Data Points

50%
Fault tolerance threshold for Nakamoto consensus
33%
Fault tolerance for BFT protocols
7 TPS
Bitcoin's maximum transaction capacity
65,000 TPS
VISA network transaction capacity

Key Insights Summary

Five Components of Blockchain Consensus

We identify five essential components of any blockchain consensus protocol: block proposal, block validation, information propagation, block finalization, and incentive mechanism. This framework provides a systematic way to analyze and compare different protocols.

Fundamental BFT Threshold

For any Byzantine fault tolerant consensus protocol to work correctly, the network must satisfy N ≥ 3f + 1, where f is the number of Byzantine processes. This fundamental result was first proved by Pease et al. in 1980.

Network Synchrony Matters

The level of network synchrony (synchronous, partially synchronous, or asynchronous) significantly impacts the design and capabilities of consensus protocols. The FLP impossibility result shows that consensus cannot be guaranteed in fully asynchronous networks with even one crash failure.

PoS as Energy-Efficient Alternative

Proof-of-Stake protocols have emerged as promising energy-efficient alternatives to Proof-of-Work, moving the opportunity cost from outside the system (waste of computation power) to inside the system (loss of capital and investment gain).

Security-Decentralization-Scalability Trilemma

Blockchain systems face a fundamental tradeoff between security, decentralization, and scalability. Improving one aspect often comes at the expense of the others, creating a challenging design space for protocol developers.

Hybrid Protocols Combine Strengths

Hybrid consensus protocols that combine elements of PoW/PoS with BFT mechanisms can leverage the strengths of different approaches, offering improved performance while maintaining security guarantees.

Content Overview

Document Contents

I. Introduction

Since Bitcoin's inception in late 2008, cryptocurrencies and the underlying blockchain technology have piqued great interest from the financial industry and society as a whole. Blockchain is widely cited as a fully decentralized system and a secure-by-design technology. The blockchain itself is a database that keeps track of all transactions occurred in the network and is replicated at every participating node.

Among the many technical components that a blockchain system is composed of, the distributed consensus protocol is the key technology that enables blockchain's decentralization, or more specifically, that ensures all participants agree on a unified transaction ledger without the help of a central authority. The distributed consensus protocol specifies message passing and local decision making at each node. Various design choices in the consensus protocol can greatly impact a blockchain system's performance, including its transaction capacity, scalability, and fault tolerance.

II. Previous Surveys and Tutorials

Several previous works have surveyed blockchain consensus protocols from different perspectives:

  • Vukolic (2015) compared PoW-based and BFT-based protocols with respect to transaction throughput, scalability limits, consensus finality, and security implications.
  • Cachin et al. (2017) provided an overview of thirteen prominent consensus protocols for permissioned blockchains and emphasized that blockchain design should follow established rigor in cryptography and distributed systems.
  • Bano et al. (2017) presented the first well-structured survey of blockchain consensus protocols, identifying three classes based on committee formation and block proposing rules.
  • Wang et al. (2019) provided a comprehensive survey with an in-depth review of incentive mechanism designs and game-theoretical characterization of Nakamoto consensus.

III. Fault-Tolerant Distributed Consensus

The fault-tolerant distributed consensus problem has been extensively studied in distributed systems since the late 1970s. We consider a distributed system that consists of N independent processes. Each process begins with an individual initial value and communicates with others to update this value.

System Model

We classify distributed systems based on:

  • Process Failure: Crash failure vs. Byzantine failure
  • Network Synchrony: Synchronous, partially synchronous, and asynchronous networks

Byzantine Fault Tolerant Consensus

BFT consensus is defined by four requirements:

  • Termination: Every non-faulty process decides an output.
  • Agreement: Every non-faulty process eventually decides the same output.
  • Validity: If every process begins with the same input, then the output equals that input.
  • Integrity: Every non-faulty process' decision must have been proposed by some non-faulty process.

The fundamental result for BFT consensus is that N ≥ 3f + 1 is required to tolerate f Byzantine processes.

Consensus Protocols for Different Network Models

We review several important consensus protocols:

  • Partially Synchronous Networks: DLS protocol, Viewstamped Replication (VR), Paxos, Practical Byzantine Fault Tolerance (PBFT)
  • Asynchronous Networks: Bracha's RBC, Ben-Or's ACS, HoneyBadgerBFT, BEAT

IV. An Overview of Blockchain Consensus

Compared to traditional distributed computing with a clear client-server model, a blockchain network allows every participant to be both a client (to issue transactions) and a server (to validate and finalize transactions).

Blockchain Infrastructure

Blockchain networks are generally classified into two categories:

  • Permissionless Blockchains: Allow free join and leave without authorization (e.g., Bitcoin, Ethereum)
  • Permissioned Blockchains: Require participants to be authorized first (e.g., Hyperledger Fabric, Corda)

Consensus Goal

We define the following requirements for blockchain consensus:

  • Termination: At every honest node, a new transaction is either discarded or accepted into the blockchain.
  • Agreement: Every new transaction and its holding block should be either accepted or discarded by all honest nodes.
  • Validity: If every node receives a same valid transaction/block, it should be accepted into the blockchain.
  • Integrity: At every honest node, all accepted transactions should be consistent with each other (no double spending).

Five Components of Blockchain Consensus Protocol

We identify five key components of any blockchain consensus protocol:

  1. Block proposal: Generating blocks and attaching generation proofs
  2. Information propagation: Disseminating blocks and transactions across network
  3. Block validation: Checking blocks for generation proofs and transaction validity
  4. Block finalization: Reaching agreement on the acceptance of validated blocks
  5. Incentive mechanism: Promoting honest participation and creating network tokens

V. The Nakamoto Consensus Protocol and Variations

The Nakamoto consensus protocol is the key innovation behind Bitcoin and many other established cryptocurrency systems. It can be summarized by the following rules:

  • Proof of Work (PoW): Block generation requires solving a cryptographic puzzle
  • Gossiping rule: New transactions/blocks are immediately broadcast to peers
  • Validation rule: Blocks/transactions are validated before acceptance
  • Longest-chain rule: The longest chain represents network consensus
  • Block rewards and transaction fees: Incentivize miners to participate honestly

Drawbacks and Vulnerabilities

Nakamoto consensus faces several challenges:

  • Tight tradeoff between performance and security
  • Energy inefficiency due to PoW mining
  • Eclipse attacks that isolate miners from the network
  • Selfish mining strategies that can disrupt consensus
  • Centralization risks from mining pools

Improvements and Variations

Several protocols have been proposed to address Nakamoto's limitations:

  • GHOST Rule: Uses the heaviest subtree instead of the longest chain
  • Bitcoin-NG: Decouples leader election from transaction serialization
  • Hybrid PoW-BFT Protocols: Combine PoW with BFT for better performance

VI. Proof-of-Stake Based Consensus Protocols

Proof-of-Stake (PoS) originates from the Bitcoin community as an energy efficient alternative to PoW mining. In PoS, a stakeholder's chance to propose a block is proportional to its stake value (token ownership).

Classes of PoS Protocols

We identify four classes of PoS protocols:

  1. Chain-based PoS: Inherits components from Nakamoto consensus but replaces PoW with PoS (e.g., Peercoin, Nxt)
  2. Committee-based PoS: Uses MPC to determine a committee for orderly block generation (e.g., Ouroboros, Snow White)
  3. BFT-based PoS: Incorporates BFT consensus for deterministic block finalization (e.g., Tendermint, Algorand, Casper FFG)
  4. Delegated PoS (DPoS): Uses social voting to elect delegates for consensus (e.g., EOSIO, Lisk, BitShares)

Vulnerabilities of PoS

PoS protocols face several unique vulnerabilities:

  • Costless simulation: Ability to simulate blockchain history at no cost
  • Nothing-at-stake: Rational to validate on multiple competing chains
  • Posterior corruption: Corrupting historical stakeholders
  • Long-range attacks: Regrowing a longer valid chain from early history
  • Stake-grinding attacks: Biasing randomness in favor of attackers
  • Centralization risk: Wealth concentration leading to monopoly

VII. Other Emerging Blockchain Consensus Mechanisms

Beyond PoW and PoS, several other consensus mechanisms have been proposed for specific application scenarios:

  • Proof of Authority (PoA): Validators stake with identity instead of tokens
  • Proof of Elapsed Time (PoET): Uses trusted execution environments for fair leader election
  • Proof of TEE-Stake (PoTS): Combines TEE with staking for secure committee selection
  • Proof of Retrievability (PoR): Uses storage space as the scarce resource
  • Ripple Consensus Protocol (RCPA): Uses unique node lists for efficient consensus
  • BlockDAG-based Protocols: Use directed acyclic graphs instead of linear chains (e.g., SPECTRE, PHANTOM)
  • TxDAG-based Protocols: Use transaction-based DAGs (e.g., Tangle, Byteball, Nano)

VIII. Comparison and Discussion

We compare the discussed consensus protocols using our five-component framework, along with their fault tolerance and transaction processing capabilities.

Key Finding: Protocols with BFT-style block finalization typically achieve 33% fault tolerance and guarantee deterministic finality, while protocols inheriting probabilistic finality from Bitcoin generally achieve 50% fault tolerance but with eventual consistency.

Protocols with BFT finalization can achieve thousands of TPS but typically work best with small network sizes. In contrast, protocols designed for large-scale permissionless networks generally achieve lower throughput (typically under 100 TPS) due to security considerations.

IX. On Designing Blockchain Consensus Protocol

The design of blockchain consensus protocols has evolved from early heuristic approaches to more formal methods inspired by established research in distributed computing, cryptography, and trusted computing.

The Security-Decentralization-Scalability Trilemma

Blockchain systems face a fundamental tradeoff between three objectives:

  • Security: Consensus security and anti-censorship capability
  • Decentralization: Geographic diversity and participant distribution
  • Scalability: Transaction throughput and network size

Improving one aspect often comes at the expense of the others, creating a challenging design space.

Protocol Composability

The existence of hybrid consensus protocols demonstrates the possibility of cherry-picking individual protocol components to fulfill specific application needs. This composability also enables progressive protocol improvement, where individual components can be updated without overhauling the entire protocol.

X. Conclusion

In this survey, we provided a comprehensive review and analysis of the state-of-the-art blockchain consensus protocols. We presented a background of classical fault-tolerance consensus research, introduced a five-component framework for analyzing blockchain consensus protocols, and reviewed a broad array of protocols with respect to their design philosophy, security issues, and performance characteristics.

We hope this survey will provide blockchain developers and researchers a comprehensive view on the state-of-the-art consensus protocols and facilitate the process of designing future protocols that can better balance the security-decentralization-scalability trilemma.

References

The complete paper contains 144 references to academic papers, white papers, and official documentation. Key references include:

[1] S. Nakamoto, "Bitcoin: A peer-to-peer electronic cash system," 2008.
[27] M. Castro, B. Liskov et al., "Practical byzantine fault tolerance," in OSDI, vol. 99, 1999, pp. 173-186.
[64] C. Decker, J. Seidel, and R. Wattenhofer, "Bitcoin meets strong consistency," in Proceedings of the 17th International Conference on Distributed Computing and Networking, 2016.
[90] E. K. Kogias, P. Jovanovic, N. Gailly, I. Khoffi, L. Gasser, and B. Ford, "Enhancing bitcoin security and performance with strong consistency via collective signing," in 25th USENIX Security Symposium, 2016.
[133] Y. Sompolinsky, Y. Lewenberg, and A. Zohar, "SPECTRE: A fast and scalable cryptocurrency protocol," IACR Cryptology ePrint Archive, vol. 2016, p. 1159, 2016.

For the complete reference list, please refer to the full PDF document.

Note: The above is only a summary of the survey content. The complete document contains extensive analysis, algorithmic abstractions, vulnerability analyses, and detailed comparisons. We recommend downloading the full PDF for in-depth reading.