Bitcoin meets strong consistency

Christian Decker, Jochen Seidel, Roger Wattenhofer

Buying a coffee with Bitcoin sounds simple, but in reality, it’s a security nightmare. Because Bitcoin only offers "eventual consistency," a merchant has to wait anywhere from 10 minutes to several hours to be reasonably sure a transaction won't be reversed. For a barista, this delay is prohibitively slow; for a fraudster, it’s an invitation to "double-spend."

In this paper, researchers from ETH Zurich propose PeerCensus, a system that brings "strong consistency" to the world of decentralized ledgers, enabling secure, real-time payments.

TL;DR

PeerCensus uses the Bitcoin blockchain as a decentralized certification authority to manage a set of "voting" identities. By running a Byzantine agreement protocol among these identities, it enables a new cryptocurrency called Discoin that confirms transactions in seconds with absolute finality, making it safe for real-time, everyday use.

What Problem Does This Paper Address?

The core issue is the trade-off between openness and consistency.

Bitcoin is open: anyone can join or leave at any time. To prevent one person from creating a million fake identities (a Sybil attack), Bitcoin uses Proof-of-Work (PoW). However, PoW leads to "eventual consistency." Forks happen, and transactions are only "confirmed" once they are buried under enough subsequent blocks. This is too slow for point-of-sale transactions.

Traditional consensus algorithms like PBFT (Practical Byzantine Fault Tolerance) provide "strong consistency"—once a transaction is committed, it’s final. But these algorithms require a fixed, known set of participants. They break down in the open, anonymous, and highly "churny" (nodes joining/leaving) environment of a public peer-to-peer network.

Methods

The authors propose a two-layered architecture called PeerCensus:

  1. The Blockchain (BC) Layer: Instead of using the blockchain to record every transaction, PeerCensus uses it to manage identities. To become a "voter," a node must successfully mine a block. This uses PoW to throttle the rate at which new identities enter the system, mitigating Sybil attacks.
  2. The Chain Agreement (CA) Layer: This layer tracks which of those identities are currently online. It uses a Byzantine agreement protocol to reach consensus on the state of the system.
The PeerCensus architecture decouples identity management (Blockchain) from transaction agreement (Chain Agreement).

On top of this, they build Discoin. Unlike Bitcoin, Discoin decouples block creation from transaction confirmation. Transactions are proposed to the CA layer, which assigns them a sequence number and commits them. Once committed, they stay committed—a property called forward security.

Datasets

The paper doesn't use a traditional training dataset. Instead, it evaluates the system's security through a rigorous probabilistic analysis based on real-world Bitcoin network parameters:

  • Mining Pool Distribution: Data from 333,000 Bitcoin blocks to see if existing mining pools could collude to take over.
  • Network Scale: Estimates of 1,000,000 total resources and 25,000 active online peers.
  • Churn Rates: Conservative estimates for mean time between failures (99 days) and recovery (1 day).

Key Insights and Ideas

  • Blockchain as a Certification Authority: The most novel idea is using the slow, expensive PoW process not for transactions, but as a "gatekeeper" for a high-speed consensus group.
  • Decoupling Mining from Confirmation: By separating these two processes, Discoin can reward all active participants (voters) rather than just the lucky miner who found the last block. This reduces the incentive for "selfish mining" and the formation of massive, centralized mining pools.
  • Dynamic Membership: The paper adapts standard Byzantine agreement protocols to handle a membership that changes over time as new blocks are mined and nodes go offline.

Key Results

  • Security Threshold: The authors prove that PeerCensus remains in a "secure state" as long as a malicious attacker controls less than 1/3 of the total computational resources.
  • Real-World Robustness: Analyzing the top 25 Bitcoin mining pools, they found that even if the 13 largest pools colluded, they would not have enough power to subvert a properly bootstrapped PeerCensus system.
  • Extremely Low Failure Probability: Using current Bitcoin parameters, the system is expected to fail less than once every 7 million years.
Analysis of Bitcoin mining pools shows that the distribution of power is sufficiently decentralized to secure a PeerCensus migration.

Limitations and Future Work

  • Bootstrapping: The system requires a "steady state" to be secure. The authors suggest "retrofitting" the existing Bitcoin blockchain to jumpstart the identity set, but the initial transition period is critical.
  • Privacy: PeerCensus requires tracking which identities are online to form a quorum. The paper does not explicitly address the privacy implications of this tracking compared to Bitcoin's pseudo-anonymity.
  • Scope: The system solves the consistency and double-spend problems but does not address other known issues like transaction malleability or the long-term scaling of the operation log.

By bridging the gap between the wild west of open P2P networks and the rigorous world of classical distributed systems, PeerCensus offers a compelling path toward a cryptocurrency that is actually usable for buying that morning cup of coffee.

Summary updated

Abstract

The Bitcoin system only provides eventual consistency. For everyday life, the time to confirm a Bitcoin transaction is prohibitively slow. In this paper we propose a new system, built on the Bitcoin blockchain, which enables strong consistency. Our system, PeerCensus, acts as a certification authority, manages peer identities in a peer-to-peer network, and ultimately enhances Bitcoin and similar systems with strong consistency. Our extensive analysis shows that PeerCensus is in a secure state with high probability. We also show how Discoin, a Bitcoin variant that decouples block creation and transaction confirmation, can be built on top of PeerCensus, enabling real-time payments. Unlike Bitcoin, once transactions in Discoin are committed, they stay committed.
BibTeX
@inproceedings{decker2016bitcoin,
  author = {Christian Decker and Jochen Seidel and Roger Wattenhofer},
  title = {{Bitcoin meets strong consistency}},
  booktitle = {ICDCN},
  year = {2016},
  doi = {10.1145/2833312.2833321},
}

Loading related content...

Figure