A Survey of Distributed Consensus Protocols

Abstract

Since the inception of Bitcoin, cryptocurrencies and the underlying blockchain technology have attracted increasing interest from both academia and industry. Among various core components, the consensus protocol is the defining technology behind the security and performance of blockchain.

This survey presents a comprehensive review and analysis of state-of-the-art blockchain consensus protocols. The authors identify five core components of a blockchain consensus protocol and analyze a wide spectrum of protocols using this framework. The analysis provides insights into the fundamental differences of various proposals in terms of their suitable application scenarios, key assumptions, expected fault tolerance, scalability, drawbacks, and trade-offs.

Introduction

The distributed consensus protocol is the key technology that enables blockchain's decentralization, ensuring all participants agree on a unified transaction ledger without a central authority. The Nakamoto consensus protocol implemented in Bitcoin was the first to resist double-spending attacks in a decentralized peer-to-peer network.

However, Nakamoto consensus faces performance bottlenecks including unsustainable energy consumption, low transaction capacity, poor scalability, and long-term security concerns. In response, researchers have proposed new block proposing mechanisms such as proof of stake (PoS), proof of authority (PoA), and proof of elapsed time (PoET).

Fault-Tolerant Distributed Consensus

The paper provides background on classical fault-tolerant consensus in distributed systems, covering Byzantine fault tolerance (BFT) requirements: termination, agreement, validity, and integrity. It discusses consensus under different network synchrony assumptions (synchronous, partially synchronous, and asynchronous) and introduces well-known protocols like PBFT, Paxos, and HoneyBadgerBFT.

For blockchain compatibility, BFT-SMR protocols need adaptation to allow all participants to propose transactions/blocks and reach consensus on multiple transactions concurrently.

Overview of Blockchain Consensus

The paper presents the basic framework of blockchain and consensus goals, introducing the five essential components of a blockchain consensus protocol:

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

Nakamoto Consensus Protocol and Variations

The Nakamoto consensus protocol is the key innovation behind Bitcoin and many other established cryptocurrency systems. This section covers Bitcoin's network setting, consensus goals, and the five components of Nakamoto consensus.

The paper discusses drawbacks and vulnerabilities of Nakamoto consensus, including the tight tradeoff between performance and security, energy inefficiency, eclipse attacks, selfish mining, and centralization risks through mining pools.

Improvements like the GHOST rule and Bitcoin-NG are covered, along with hybrid PoW-BFT protocols such as PeerConsensus, SCP, and ByzCoin.

Proof-of-Stake Based Consensus Protocols

Proof-of-Stake (PoS) originates as an energy-efficient alternative to PoW mining. The paper identifies four classes of PoS protocols:

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

The section also covers vulnerabilities specific to PoS, including costless simulation, nothing-at-stake, posterior corruption, long-range attacks, stake-grinding, and centralization risks.

Other Emerging Blockchain Consensus Mechanisms

Beyond established schemes, the paper covers emerging consensus mechanisms for specific application scenarios:

• Proof of Authority (PoA): Validators stake with identity instead of tokens
• Proof of Elapsed Time (PoET): Simulates PoW mining time using trusted execution environments
• Proof of TEE-Stake (PoTS): Harmonizes TEE and blockchain consensus
• Proof of Retrievability (PoR): Uses storage resources as proof
• Ripple Consensus Protocol (RCPA): Uses unique node lists for consensus
• DAG-based protocols: BlockDAG (SPECTRE, PHANTOM) and txDAG (Tangle, Byteball, Nano)

Comparison and Discussion

The paper provides comprehensive comparisons of consensus protocols using the five-component framework, along with fault tolerance and transaction processing capabilities. Protocols with BFT-style finalization typically achieve 33% fault tolerance, while those with probabilistic finality (like Nakamoto consensus) achieve 50% fault tolerance.

The comparison reveals that protocols with BFT-style block finalization can achieve thousands of TPS but work best with small network sizes, while protocols for large-scale public networks are predominantly permissionless with probabilistic finality and typically capped at hundreds of TPS for security reasons.

On Designing Blockchain Consensus Protocol

The paper discusses the paradigm shift in protocol design from early heuristic approaches to formal methods drawing from distributed computing, cryptography, and trusted computing. Modern protocols incorporate sophisticated cryptographic primitives and come with formal security analysis.

The authors highlight the security-decentralization-scalability trilemma facing blockchain consensus design and discuss protocol composability, noting that hybrid approaches allow cherry-picking components to fulfill specific application needs.

Conclusion

This survey provides a comprehensive review of blockchain consensus protocols, analyzing them with respect to fault tolerance, performance, and vulnerabilities. The five-component framework, classification methodology, protocol abstractions, and performance analyses help researchers and developers understand blockchain consensus fundamentals and facilitate future protocol design.

As blockchain technology continues to evolve, consensus protocols will likely incorporate more hybrid approaches and sophisticated cryptographic techniques to balance the competing demands of security, decentralization, and scalability.