PaperlayerView exact revision on arXiv

Source-linked AI summary

Consensus in the Age of Blockchains

Shehar Bano, Alberto Sonnino, Mustafa Al-Bassam, Sarah Azouvi, Patrick McCorry, Sarah Meiklejohn, George Danezis

arXiv:1711.03936v2cs.CR

TL;DR

Blockchain consensus protocols are difficult to contextualize because open-blockchain research is complex, rapidly evolving, and lacks a comprehensive systematic study. The paper surveys classical, PoW, PoX, and hybrid protocols, evaluates them with a common framework, and identifies research gaps and challenges for future work.

  • Problem

    Open-blockchain consensus research is complex and rapidly evolving, yet no systematic and comprehensive study had mapped its protocol landscape.

  • Method

    The paper systematically surveys classical, PoW, PoX, and hybrid consensus protocols and evaluates their security, performance, and design properties with a common framework.

  • Results

    The study presents a comprehensive systematization of blockchain consensus protocols and evaluates their performance and security properties using a novel framework.

  • Takeaways & Limitations

    The evaluation highlights open challenges involving gaps between BFT and blockchains, security–performance tradeoffs, incentives, and privacy.

Abstract

from arXiv · show

The blockchain initially gained traction in 2008 as the technology underlying bitcoin, but now has been employed in a diverse range of applications and created a global market worth over $150B as of 2017. What distinguishes blockchains from traditional distributed databases is the ability to operate in a decentralized setting without relying on a trusted third party. As such their core technical component is consensus: how to reach agreement among a group of nodes. This has been extensively studied already in the distributed systems community for closed systems, but its application to open blockchains has revitalized the field and led to a plethora of new designs. The inherent complexity of consensus protocols and their rapid and dramatic evolution makes it hard to contextualize the design landscape. We address this challenge by conducting a systematic and comprehensive study of blockchain consensus protocols. After first discussing key themes in classical consensus protocols, we describe: first protocols based on proof-of-work (PoW), second proof-of-X (PoX) protocols that replace PoW with more energy-efficient alternatives, and third hybrid protocols that are compositions or variations of classical consensus protocols. We develop a framework to evaluate their performance, security and design properties, and use it to systematize key themes in the protocol categories described above. This evaluation leads us to identify research gaps and challenges for the community to consider in future research endeavours.

I. INTRODUCTION

Blockchains enable decentralized, transparent interaction without trusted intermediaries, but consensus remains central to their performance and scalability. This paper addresses the lack of a systematic, comprehensive account of blockchain consensus protocols by surveying protocol families and evaluating their design space.

  • Blockchain motivation: Blockchains are decentralized, replicated, immutable, and tamper-evident logs that let parties interact and verify data without a trusted intermediary.Their properties make them relevant to applications including finance, voting, public records, sharing economies, and social media.
  • Research problem: Consensus protocols determine how distributed nodes agree whether data should be added to the blockchain.Consensus is closely tied to blockchain performance and scalability, which remain major barriers to widespread adoption.
  • Research problem: Bitcoin enabled consensus in an open, decentralized network through proof-of-work, but probabilistic leader election can produce forks and weak consistency.The passage also identifies Bitcoin’s poor performance as a limitation.
  • Research gap: Before this work, blockchain consensus lacked a systematic and comprehensive study, while its literature was vast, fast-moving, and concentrated in non-peer-reviewed venues and white papers.These conditions make the field difficult to contextualize and survey comprehensively.
  • Contributions: The paper surveys classical, PoW, PoX, and hybrid consensus protocols, introduces a common evaluation framework, and identifies open research challenges.The framework maps high-level design themes rather than attempting to evaluate every individual protocol.
  • Related work: The study positions itself as the most comprehensive systematic investigation of blockchain consensus protocols to date.It builds on related surveys and evaluation frameworks covering cryptocurrencies, classical consensus, private blockchains, and PoW security and performance.

2) Evaluation:

The paper combines distinct literature-selection strategies for mature classical consensus and rapidly evolving blockchain consensus, then evaluates protocols through a shared framework. That framework organizes security, performance, and design properties while exposing practical limitations and research challenges.

  • Methodology: The methodology treats classical consensus and blockchain consensus separately because the two research areas differ substantially in maturity.Classical consensus is surveyed through seminal, influential works and established reference texts.
  • Methodology: Blockchain consensus requires a mixed-source survey because the field is high-volume, high-churn, and dominated by non-academic venues.Citation impact cannot reliably rank work in this young field, so the authors begin with an actively maintained bibliographic repository and refine the collection.
  • Evaluation framework: The evaluation framework covers security properties including consistency, transaction censorship resistance, and denial-of-service resistance.It also considers performance dimensions such as throughput and latency, along with category-specific design properties.
  • Evaluation framework: The framework uses a common reference table across PoW, PoX, and hybrid protocols and generally assumes partial synchrony.The table is intended to visualize the field at a high level rather than enumerate every individual protocol.
  • Classical consensus: Consensus protocols support state-machine replication by helping replicas agree on ordered state mutations under specified network and failure models.The surveyed models include synchronous, asynchronous, partially synchronous, crash, and Byzantine settings, with liveness and safety as core properties.
  • Classical consensus: PBFT coordinates views through leaders, reliable broadcast, replica monitoring, and view changes, with Byzantine safety requiring n = 3f + 1.Checkpointing can reduce storage by retaining the current state rather than the full action sequence.

V. PROOF-OF-WORK CONSENSUS

Proof-of-work consensus uses computational puzzles to select leaders in permissionless networks, with Bitcoin providing the canonical design. The approach derives from earlier anti-spam proof-of-work systems and adjusts mining difficulty to regulate block production.

  • Bitcoin and Nakamoto consensus: Bitcoin introduced a novel composition of existing technical components that uses proof-of-work to achieve consensus in a fully decentralized, permissionless network.This design is also called Nakamoto consensus.
  • Origins of PoW: Proof-of-work originated in anti-spam proposals requiring senders to solve computational puzzles as evidence that work was performed.Hashcash later used a SHA-1 puzzle requiring a hash with at least 20 leading zero bits.
  • Mining mechanism: Nakamoto consensus replaces Hashcash’s SHA-1 puzzle with two successive SHA-2 hashes and accepts hashes below a target integer t.Lowering t increases the number of guesses and therefore the work needed to produce a valid block.
  • Evaluation framework: Table I evaluates selected blockchain consensus systems using security, performance, design, and message-complexity fields, with n denoting participants and c committee size.Symbols distinguish properties that hold, fail, partially hold, do not apply, or could not be extracted.
  • Mining mechanism: Bitcoin miners repeatedly hash candidate block headers, and successful miners append valid blocks and receive new coins as rewards.The network resets the target every 2016 blocks so blocks are produced probabilistically about every 10 minutes.

B. Forks

Proof-of-work resolves competing blockchain histories by selecting the chain with the greatest accumulated work, but forks arise when miners extend the same prior block. Fork risk increases with propagation delays and can lower resistance to majority-computing-power attacks.

  • Fork formation: Forks occur when two miners find different blocks extending the same previous block.PoW consensus resolves the competing histories by accepting the chain with the most accumulated work.
  • Fork security: A double-spending attacker must create a fork with more accumulated work than the chain being overridden.The threat model assumes that an adversary controlling majority computing power can outpace the remaining network.
  • Fork security: 51% attack resistance is defined by the percentage of network computing power required to outpower the rest of the network.This percentage is the network’s security threshold.
  • Fork security: Increasing block size or decreasing the inter-block interval increases fork probability because delayed miners may work on stale blocks.The resulting propagation disadvantage makes the network more susceptible to attacks from miners that avoid those delays.

C. Scaling Bitcoin

Scaling Bitcoin requires improving throughput or latency without reducing the network’s security threshold or requiring connection upgrades. Proposed approaches modify chain selection, leader operation, propagation, and mining-pool organization.

  • Performance–security trade-off: Bitcoin’s block frequency can be reduced to 1 minute per block without reducing the existing network’s security threshold.This result was obtained by modelling the network’s bandwidth distribution using real-world broadband data.
  • Chain selection: GHOST uses off-main-chain blocks and a tree structure to achieve higher transaction rates without undermining Bitcoin security.It differs from Bitcoin’s linear blockchain by organizing blocks in a tree.
  • Performance–security trade-off: Increasing throughput or decreasing latency in PoW blockchains lowers resilience to 51% attacks.The central scaling challenge is to improve performance while maintaining the network’s security threshold without requiring network-connection upgrades.
  • Protocol design: Bitcoin-NG separates PoW leader election from transaction serialization, allowing transaction latency to approach network propagation delay.During an epoch, the elected leader can append transactions until a new leader is selected.
  • Mining pools: Mining pools reduce reward variance but undermine decentralization and can enable transaction censorship by a malicious pool manager.Decentralized pool techniques seek proportional rewards while avoiding centralized control.

E. Incentives

Blockchain consensus incentives and proof-of-stake designs address weaknesses in Nakamoto consensus, but introduce new attack surfaces and stake-management challenges. Alternative proof-of-X schemes replace computational work with ownership, deposits, destroyed coins, or coin age.

  • Incentive compatibility: Nakamoto consensus is not completely incentive compatible despite rewarding miners with newly created coins.Its security relies on economically incentivizing miners to validate and mine blocks.
  • Protocol attacks: Selfish mining can enable a 51% attack with as little as 25% of network computing power.Colluding miners withhold blocks to maintain a lead while others waste computation on stale blocks.
  • Proof-of-stake: Proof-of-stake weights block votes by participants’ in-band investment, such as currency held in the blockchain.Many systems randomly elect leaders from stakeholders in proportion to their stake.
  • Proof-of-stake: Private proof-of-stake leader election resists denial-of-service attacks because candidates reveal selection only after checking it privately.A malicious leader may censor transactions temporarily, but later leaders can add them after re-election.
  • Proof-of-stake: Ouroboros uses a jointly agreed random seed and a stake-proportional pseudorandom leader election, distributing rewards to all participants.The same seed selects the next epoch’s participant subset.
  • Proof-of-stake: Proof-of-stake must track changing stakeholder balances; Ouroboros bounds stake shifts, while Snow-White uses sufficiently old stake distributions.These constraints support agreement about the stake distribution used for selection.
  • Proof-of-X security: PoX introduces nothing-at-stake, grinding, and long-range attacks compared with Nakamoto consensus.Mitigations include stake penalties, unbiasable randomness or deterministic leader election, and protections against rewriting historical blocks.
  • Proof-of-X variants: Proof-of-deposit locks coins during mining, proof-of-burn destroys coins, and proof-of-coin-age weights possession by time since coins last moved.These variants use different forms of coin ownership or commitment as mining evidence.

B. Proof-of-Capacity

Proof-of-capacity replaces computational work with disk-space allocation and can support distributed storage, but outsourced storage creates a centralization risk. Trusted-hardware alternatives replace or repurpose computational work, while inheriting hardware-specific vulnerabilities.

  • Proof-of-capacity: Proof-of-capacity weights block votes by participants’ ability to allocate substantial disk space.PermaCoin requires eligible leaders to store segments of a large file distributed by an authoritative dealer.
  • Proof-of-capacity: PermaCoin repurposes proof-of-work for distributed storage by requiring miners to store segments of a large file.The design aims to provide censorship-resistant file storage.
  • Centralization risk: Outsourcing file storage makes proof-of-capacity vulnerable to centralization.PermaCoin’s proof-of-retrievability requires sequential reads in pseudorandom order, making outsourced storage slower and reducing solution-finding chances.
  • Trusted hardware: Proof-of-elapsed-time elects the participant whose trusted enclave reports the shortest wait time.The elected leader supplies an attestation that the wait was shortest and the block was not broadcast prematurely.
  • Trusted hardware: Resource-Efficient Mining treats useful proof-of-work instruction cycles as lottery tickets and uses two-layer attestation to authorize block minting.The attestations certify both useful work and correct instruction-cycle accounting.
  • Trusted-hardware limitations: Breaking one trusted-hardware device can let an attacker always win the lottery, while collecting more chips increases block-winning probability.These are identified as limitations of proof-of-elapsed-time approaches.

1) Permissioned:

Committee configuration balances safety and performance: permissioned systems typically use static, trusted membership, while permissionless systems require dynamic mechanisms to resist Sybil attacks.

  • Permissioned systems usually assume static committee members, whereas permissionless systems require dynamic membership for Sybil resistance.
  • ByzCoin updates its committee through a sliding window, adding miners and ejecting the oldest members while weighting votes by recent mining blocks.
  • Reconfiguration must wedge the old committee so it cannot approve concurrent transactions, while preserving transactions already being processed.
  • Peercensus admits members through collective reachability validation and detects departures with failure detectors, but false eviction alarms can stall the system.Rate-limiting leave proposals is suggested as a mitigation.
  • Algorand and Snow-White use randomness from previous blocks to select committees for each epoch.

3) Full:

Full-committee and committee-based designs adapt classical BFT protocols, proof-of-work membership, and private selection to address efficiency, censorship, denial-of-service, and participation concerns.

  • Solidus lets an external leader propose transactions and nominate itself once, preventing a stable PBFT leader from gradually installing corrupt committee members.
  • ByzCoin replaces PBFT’s O(n^2) all-to-all messaging with O(n) collective signing and produces a fixed 64-byte signature verifiable in O(1) time.The signature attests that at least two-thirds of the committee witnessed the block.
  • Censorship by a malicious leader can harm fairness without compromising safety; systems address it through non-leader proposals or leader re-election.
  • ByzCoin has medium DoS resistance, Elastico high within single committees, and Chainspace medium because its intra-committee configuration is unspecified.Elastico can deadlock when an adversary floods transactions spanning multiple committees; Omniledger improves robustness using O(n) group communication.
  • Proof-of-stake systems protect against DoS by privately electing committees whose membership remains hidden until selected participants announce themselves.
  • Permissioned systems such as Hyperledger use pluggable consensus and are resilient to committee DoS and transaction censorship under their trust assumptions.
  • Classical BFT models distinguish cooperative and Byzantine players, while decentralized volunteer networks additionally require participation incentives.
  • Committee-based systems commonly share rewards among members, while Solidus models rational players and argues that equal rewards can create participation problems.

A. Committee Topology

Sharded consensus organizes committees through flat or hierarchical topologies, dynamic assignment, and cross-committee protocols, but randomness, coordination, and client dependence remain constraints.

  • Committee Topology: Chainspace and Omniledger use flat committee topologies, while Elastico uses normal committees plus a leader committee that orders transactions.
  • Committee Topology: Dynamic committee assignment should be random to prevent adversaries from concentrating Byzantine nodes in one committee.
  • Committee Topology: Permissionless committee reconfiguration requires shared randomness, but current distributed solutions tolerate up to 1/6 Byzantine peers with high message complexity.
  • Committee Topology: Omniledger replaces a random subset of committee members each epoch while maintaining liveness during reconfiguration.
  • Committee Topology: Elastico reassigns nodes to different committees each epoch, with committee count scaling linearly with computational power.
  • Cross-committee consensus: Cross-committee transactions require atomic, consistent coordination; Omniledger and RSCoin use client-mediated validation, locking, clearance, and output processing.
  • Cross-committee consensus: Client-driven atomic commit can lock inputs indefinitely if the client stops participating, so Chainspace instead coordinates commit collaboratively among concerned committees.
  • Open problems: Traditional BFT-based sharding remains a subject of open-problem research for blockchain deployments.

1) ‘Open’ vs ‘closed’ asynchronous protocols:

Blockchain consensus must reconcile the openness of permissionless participation with mechanisms developed for closed groups, while sharding introduces additional integrity and verifiability challenges.

  • Open vs closed protocols: Randomized BFT protocols can provide safety and liveness asynchronously, but still require closed groups and cannot directly replace open Nakamoto consensus.
  • Open vs closed protocols: BFTSmart has O(N^2) message complexity, whereas ByzCoin reduces common-case BFT consensus to O(N) using modern signatures.
  • Membership and keys: BFT committees require authenticated point-to-point channels, making membership and key tracking challenging in dynamic permissionless committees.
  • Membership and keys: Broadcasting identities across the network costs O(n^2) messages; directory committees reduce this burden but may undermine decentralization or reproduce committee-formation challenges.
  • Sharding risks: Sharding requires atomic execution across committees to preserve linearizability, but a malicious committee can compromise every transaction that touches it.
  • Sharding risks: Chainspace assigns contract authors responsibility for identifying trusted infrastructure and provides auditing to detect malicious committees.
  • Sharding risks: Sharded systems define separate committee blockchains or rely on a central entity to combine shard transactions, leaving global verifiability less clear.
  • Permissionless committees: PoW and PoX resist Sybil takeover, but large miners have greater committee-dominance likelihood at higher hashing cost than single-leader PoW.

2) Bootstrapping committees:

The section surveys committee bootstrapping, incentives, governance, and privacy as interconnected design concerns in decentralized consensus. It highlights unresolved trade-offs between participation, scalability, security, and privacy.

  • Bootstrapping committees: Committee assignment can be randomized, but smart-contract-based mapping supports finer governance across permissioned and permissionless committees.Chainspace is cited as an example where committees may follow different participation policies.
  • Bootstrapping committees: Geographic distribution, jurisdictional diversity, and organizational independence can contribute to coercion resistance when bootstrapping committees.The discussion uses Tor’s directory authorities as an example of a closed consensus group operating in an adversarial environment.
  • Incentives and governance: Incentives should be distributed across protocol phases and committees regularly reconfigured because large committees can make individual rewards trivial.The section frames decentralized participants as rational players whose utility affects participation.
  • Incentives and governance: Incentive design remains insufficiently analyzed for cheap block creation, BFT protocols, and multi-committee systems.The text identifies these gaps alongside known limitations in PoW incentives.
  • Incentives and governance: Governance and protocol evolution influence whether participants view their investments as likely to be repaid, but these broader incentives remain understudied.The section distinguishes these considerations from concrete rewards for protocol participation.
  • Privacy: Privacy protection creates a trade-off: permissioned systems can restrict consensus participants, while protocol-layer methods can impose computational and scalability costs.The discussion contrasts trusted closed groups with cryptographic techniques and off-chain execution patterns.

APPENDIX

The appendix defines the framework’s consensus, system, security, performance, and implementation dimensions. These terms specify how protocols and their evaluation settings are classified.

  • Security and access: Security dimensions cover tolerated malicious or faulty nodes, denial-of-service resistance, transaction censorship resistance, and permissioned versus permissionless participation.Permissioned systems restrict consensus participation to selected authorities, whereas permissionless systems allow anyone to join.
  • Evaluation metadata: The appendix also records whether implementation code is publicly available and the experimental setup used to generate throughput and latency results.These fields describe reproducibility and the configuration underlying reported performance numbers.
  • Committee structure: The framework distinguishes single-committee from multiple-committee organization and records how committee members are assigned, either statically or dynamically.It separately defines committee structure, intra-committee configuration, and inter-committee configuration.
  • Committee structure: Committee formation records how participants are selected, including proof-of-work, proof-of-stake, and trusted hardware.Participants are the nodes involved in the consensus protocol.
  • Consensus properties: Consensus dimensions include agreement within one committee, agreement across committees, leader selection, and consistency strength.Inter-committee consensus may optionally be mediated by an external party such as a client.
  • Performance: The framework measures latency from transaction proposal to consensus and throughput as the maximum transaction-agreement rate.Throughput is expressed in transactions per second or hour.
Loading 1711.03936v2…