Source-linked AI summary
Bitcoin Meets Strong Consistency
Christian Decker, Jochen Seidel, Roger Wattenhofer
TL;DR
Bitcoin’s eventual consistency permits double-spending concerns and makes confirmation too slow for everyday payments. The paper proposes PeerCensus, which uses Bitcoin’s blockchain to manage identities and support strong consistency, then outlines Discoin, which separates block creation from transaction confirmation. PeerCensus is secure with high probability under a resource-share condition, while Discoin provides fast confirmations that remain committed.
Problem
Bitcoin’s eventual consistency leaves conflicting transactions unresolved for too long, creating double-spending concerns for everyday payments.
Method
PeerCensus uses Bitcoin’s blockchain to certify participating identities and combines blockchain and agreement techniques; Discoin uses this foundation to decouple block creation from transaction confirmation.
Results
With φR < 1/2 − ϵ after reaching steady state, PeerCensus is in a secure state with high probability.
Takeaways & Limitations
Discoin enables real-time payments with forward security: once a transaction is committed, it cannot be reverted.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
Bitcoin’s eventual consistency makes everyday payments slow and vulnerable to double-spending, so the paper proposes PeerCensus to support strongly consistent applications and Discoin for fast, irreversible confirmations.
- Motivation: Bitcoin transactions can be double-spent because conflicting payments spread through the network and may be selected differently before confirmation.A fraudulent customer can inject a second transaction at multiple vantage points, increasing its likelihood of entering the blockchain.
- Motivation: Confirmation can take about 30 minutes for a low-value payment and several hours when blockchain forks require subsequent blocks.Bitcoin generates a block every 10 minutes, while transaction flooding and backlog add further delay.
- PeerCensus: PeerCensus uses Bitcoin’s blockchain to introduce and manage participating identities, providing a foundation for strongly consistent applications.The system is application agnostic and can be shared by multiple applications.
- Discoin: Discoin builds on PeerCensus and decouples transaction confirmation from block creation, so committed transactions cannot later be reverted.Discoin can use a Byzantine agreement protocol to commit transactions to the transaction history.
- System implications: PeerCensus concentrates computational resources on a shared blockchain, strengthening it against attacks compared with splitting resources across many altcoin blockchains.A shared instance can support an arbitrary number of applications.
- System implications: The proposed migration from Bitcoin to Discoin is intended to preserve Bitcoin’s accumulated resources and public acceptance while enabling strong consistency and real-time payments.The migration analysis reports an expected PeerCensus failure rate of fewer than once every 7 million years.
- System design: The system is designed to address peer churn and Bitcoin’s eventual consistency by combining a blockchain with a Chain Agreement component.The paper identifies the Blockchain and Chain Agreement as PeerCensus’s two core components.
III. SYSTEM MODEL
PeerCensus models a dynamic peer-to-peer system in which controlling entities manage peers and computational resources. Proof-of-Work limits entry, while peers and resources can join, leave, fail, and recover over time.
- The system consists of a peer-to-peer network, controlling entities, and computational resources.The network executes PeerCensus; entities model individuals controlling peers; resources model computational limitations.
- Proof-of-Work limits peer entry, with the number of identities an entity can introduce determined by its computational resources.
- Peers use public-key cryptography for identities, with each peer generating a keypair and its public key serving as its identity.The model assumes no identity collisions and does not require identities to be ordered.
- Peers may be online or offline, joining or leaving at arbitrary times through voluntary halting or involuntary crashes.
- Communication uses authenticated point-to-point messages that are eventually delivered between online peers.
- Resources may exit voluntarily or through failure, with failure and recovery probabilities independent of their controlling entity.
IV. DYNAMIC MEMBERSHIP PROTOCOL
PeerCensus is a trustless decentralized certification authority organized into Blockchain, Chain Agreement, and Application layers. The Blockchain layer uses Proof-of-Work to regulate identity entry.
- The PeerCensus protocol provides a trustless decentralized certification authority for identities.
- PeerCensus consists of Blockchain, Chain Agreement, and Application layers.
- The Blockchain layer is based on a Proof-of-Work mechanism.
A. Blockchain (BC)
The Blockchain layer throttles new identity joins with Proof-of-Work and maintains a legal chain of hash-linked blocks. Mining proposes identity-bearing blocks, while Chain Agreement preserves a committed prefix.
- Proof-of-Work Mechanisms: Proof-of-Work is fast to verify but computationally difficult and feasible to find, with nonce-finding distributed as exp(1/d).The parameters are difficulty d, challenge c, and nonce x.
- The Blockchain Protocol: The blockchain throttles new identity joins by requiring computational work before blocks can be appended.
- The Blockchain Protocol: A block contains a hash, difficulty, peer, and bit-string, and legal blocks must hash-link to the preceding block and include a valid Proof-of-Work.
- The Blockchain Protocol: Mining attempts to find a legal block extending the current chain and containing the miner’s identity.
- The Blockchain Protocol: The Chain Agreement protocol ensures that peers accept only extensions sharing the previously agreed blockchain as a prefix.This provides forward security against accepting conflicting extensions after agreement.
- The Blockchain Protocol: When a proposed block is accepted, its peer becomes voting; otherwise the proposer continues mining.
B. Chain Agreement (CA)
Chain Agreement tracks online membership and shared state using Byzantine agreement, while coordinating blockchain extensions and application operations. Ordered timestamps, rank-based primaries, and failover support operation commitment under churn.
- Shared state: Chain Agreement tracks an operation log, online voters, and the blockchain as shared state.
- Operations: Operations receive totally ordered logical timestamps, and exactly one operation is committed at each logical time step.A timestamp is (ℓ, v, s), representing blockchain length, primary view number, and sequence number.
- Primary selection: Voting peers are ranked by how recently they obtained voting rights, and the rank determines the primary for the next time step.
- Primary selection: PBFT failover increases the view number without assistance from a failed primary.
- Limitation: Because of churn, Chain Agreement cannot support snapshots, unlike PBFT with fixed membership.
- Operations: Each operation proceeds through propose, pre-prepare, prepare, and commit before being applied.
- Operations: Chain Agreement supports block, join, and leave operations that respectively append blocks, rejoin offline voters, and remove failed peers.
C. Application
The application layer uses PeerCensus membership information to order and process deterministic operations while keeping application logic separate from the certification authority. Clients synchronize membership data, submit operations, and verify confirmations.
- Applications use certification-authority membership information, including identity rankings and timestamps, to access PBFT capabilities such as application-state snapshots.
- Operations on shared application state receive timestamps combining the certification authority’s membership timestamp with a primary-assigned sequence number.
- Application logic and state remain separate from certification-authority decisions, allowing one certification-authority and blockchain instance to serve multiple applications.
- Clients synchronize membership information, submit operations to the application, and verify that operations were confirmed correctly.
V. SAFETY & LIVENESS
PeerCensus seeks to extend Byzantine-agreement guarantees to a dynamic peer-to-peer setting by maintaining fewer than one-third attacker-controlled online voters. Under steady state and bounded attacker resources, it is secure with high probability, while insecurity preserves past commitments but constrains future operations.
- PBFT provides safety and liveness when fewer than one-third of participants are faulty, but PeerCensus must address changing membership and peer churn.
- PeerCensus is secure when the attacker controls less than one-third of online voters; exceeding this threshold defines an insecure state without protocol guarantees.
- If PeerCensus becomes insecure, the attacker can hinder others’ voter-set entry, so new application operations are applied only at the attacker’s will.
- Previously committed operations cannot be modified or undone, so strong consistency remains guaranteed up to the point when the attacker takes control.
- PeerCensus assumes a steady state in which online peers and resources follow expected values, justified by sufficiently long operation and a bootstrapping method.
- If PeerCensus reaches steady state and the attacker controls less than 1/2 −ϵ of resources, it is secure with high probability.
- Resource churn, membership churn, and miner’s luck influence attacker and defender voter populations and block shares.
A. Preliminaries
The analysis models resource and membership dynamics probabilistically, then bounds deviations in attacker-controlled resources, voters, and blocks. These bounds supply the components needed for the main security theorem.
- Resource churn: Resource availability is modeled as an independent two-state Markov chain, yielding an expected ρ|R| online resources in steady state.
- Resource churn: Lemma 1 bounds deviations of the attacker-to-defender ratio of online resources, φR, using the resource population size n and resource ratio r.
- Resource churn: A union-bound argument controls the probability that φR exceeds its target by combining deviations in attacker and defender online-resource counts.
- Resource churn: The resource-churn proof minimizes its resulting bound when β = γ, with α = 2β/(1−β).
- Membership churn: Membership churn is characterized in steady state by σ = p_pr/(p_pr + p_pf).
- Membership churn: Lemma 2 bounds deviations in the attacker-to-defender ratio of online voters, φI, using voter-set size n and the peer ratio s.
- Miner’s luck: Lemma 3 bounds the attacker’s blockchain block ratio, φB, while accounting for blockchain length ℓ and attacker resource fraction t.
- Miner’s luck: The expected block ratio depends on the resource distribution rather than simply equaling the attacker’s resource fraction, motivating Corollary 1’s transformed bound.
B. Establishing Theorem 1
The security proof targets the probability that PeerCensus reaches an insecure state. It decomposes that event into deviations in resource share, voter share, and block share, then combines their bounds to establish Theorem 1.
- For φR < 1/2 −ϵ, the proof bounds the probability of an insecure Chain Agreement state by exp(−Ω(min(|R|, |I|, ℓ))).
- The proof introduces U as the event that resource, block, or voter ratios deviate beyond α, β, or γ, with α + β + γ = ϵ.
- Because U is necessary but insufficient for insecurity, bounding U provides a sufficient route to bounding the insecure-state event.
- Applying the bounds from two lemmas and one corollary to the three deviation terms completes the proof of Theorem 1.
C. Reaching the Steady State
PeerCensus reaches a secure steady state by bootstrapping resources, voting identities, and peers from Bitcoin’s blockchain, then incrementally committing the migration interval. The migration requires that no entity controls enough historical blocks to subvert the system.
- C. Reaching the Steady State: PeerCensus requires a controlled bootstrapping period with sufficient resources, voting identities, and online peers to establish favorable failure bounds.Without promoted identities, the first block finder could control the entire system.
- C. Reaching the Steady State: Bitcoin’s blockchain supplies PeerCensus’s initial resources, voting identities, and peers by deriving identities from block-finder addresses in reward transactions.Each Bitcoin block’s reward transaction contains an address that identifies the new voting identity.
- C. Reaching the Steady State: Migration fixes a blockchain length lm, selects a representative set of recent identities, and begins PeerCensus execution before incrementally committing blocks through lm.The initial online identities are drawn from a range ending k blocks before the migration point.
- C. Reaching the Steady State: The migration is secure only if no entity has mined enough Bitcoin blocks to control PeerCensus; with j ≥10,000, no single entity controls more than 25% of identities.The authors report that even the largest 28 pools together would not reach the required control share.
D. Real World Guarantees
The paper estimates PeerCensus’s failure probability under representative real-world parameters and reports a very low expected failure rate. The section uses resource and identity assumptions to quantify the system’s security margin.
- D. Real World Guarantees: The real-world analysis estimates PeerCensus’s failure probability using parameters for resources, identities, and the system’s security margin.The analysis is presented as an example of guarantees expected from real-world PeerCensus instances.
- D. Real World Guarantees: 14% of the security margin is assigned to 2αR, 11% to αM, and 75% to 2αI in the discrete-time failure analysis.The cited allocation subdivides the security margin ε across the three terms.
VI. DISCOIN
Discoin is a cryptocurrency built on PeerCensus that tracks account balances and confirms transactions independently of block generation. Its design targets simpler state management and permanent transaction commitment, while the surrounding discussion situates it among consensus and cryptocurrency systems.
- VI. DISCOIN: Discoin is presented as an application built on PeerCensus, with accounts identified by public/private key pairs.The public key identifies an account, while the private key authenticates messages.
- VI. DISCOIN: A Discoin transaction transfers v coins from account a to b and is valid only when the source balance covers v and the signature verifies.The transaction includes the signed tuple ⟨a, b, v⟩σ.
- VI. DISCOIN: Committing a transaction updates account balances, while each block-found event distributes r newly generated coins equally among all identities.The reward is triggered by a timestamp change rather than requiring a separate block-finder-only mechanism.
- VI. DISCOIN: Discoin tracks account balances directly, separates transaction commitment from block generation, and keeps committed transactions irreversible.The protocol is described as leaner and simpler than Bitcoin’s transaction-output model.
- VI. DISCOIN: Bitcoin account balances can be migrated into Discoin by computing balances through height lm and committing a snapshot before new Discoin transactions.This bootstraps Discoin after PeerCensus has been initialized.
- VI. DISCOIN: PeerCensus and Discoin rely on established Byzantine agreement protocols, including PBFT, Zyzzyva, and SGMP.The cited protocols are described as later improvements in message complexity.
- VI. DISCOIN: PeerCensus addresses inconsistent state views such as double-spending but does not address transaction malleability or privacy issues.These are explicitly identified as unresolved problem classes.