PaperlayerView exact revision on arXiv

Source-linked AI summary

Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing

Eleftherios Kokoris-Kogias, Philipp Jovanovic, Nicolas Gailly, Ismail Khoffi, Linus Gasser, Bryan Ford

arXiv:1602.06997v3cs.CR

TL;DR

Bitcoin transactions can require about an hour for confirmation and provide only probabilistic guarantees, limiting suitability for real-time transactions. ByzCoin applies scalable collective signing and dynamic, proof-of-work-proportional consensus groups to provide strong consistency while preserving open membership. Experiments report consensus in under 20 seconds for 1MB blocks, under one minute confirmation latency, and throughput higher than PayPal.

  • Problem

    Bitcoin’s high transaction-confirmation latency limits its suitability for real-time transactions, while later work revealed vulnerabilities involving transaction reversibility, double-spending, and strategic mining attacks.

  • Method

    ByzCoin brings PBFT-style strong consistency to cryptocurrencies using collective signing, dynamic membership proportional to proof-of-work, and tree-structured communication to address openness, scalability, block conflicts, and commitment rate.

  • Results

    ByzCoin experimentally reaches consensus in less than 20 seconds for 1MB blocks and achieves 974 TPS with 68-second confirmation latency for 32MB blocks and 144 participants.

  • Takeaways & Limitations

    ByzCoin’s strong consistency increases Bitcoin’s security guarantees against N-confirmation double-spending, intentional forks, and selfish mining while enabling high scalability and low transaction latency.

  • Takeaways & Limitations

    ByzCoin’s safety fails at 30% in the described Byzantine setting, although Bitcoin remains safe at 48% when clients can wait long enough.

Abstract

from arXiv · show

While showing great promise, Bitcoin requires users to wait tens of minutes for transactions to commit, and even then, offering only probabilistic guarantees. This paper introduces ByzCoin, a novel Byzantine consensus protocol that leverages scalable collective signing to commit Bitcoin transactions irreversibly within seconds. ByzCoin achieves Byzantine consensus while preserving Bitcoin's open membership by dynamically forming hash power-proportionate consensus groups that represent recently-successful block miners. ByzCoin employs communication trees to optimize transaction commitment and verification under normal operation while guaranteeing safety and liveness under Byzantine faults, up to a near-optimal tolerance of f faulty group members among 3f + 2 total. ByzCoin mitigates double spending and selfish mining attacks by producing collectively signed transaction blocks within one minute of transaction submission. Tree-structured communication further reduces this latency to less than 30 seconds. Due to these optimizations, ByzCoin achieves a throughput higher than PayPal currently handles, with a confirmation latency of 15-20 seconds.

1 Introduction

Bitcoin offers open, decentralized transaction processing, but its probabilistic consensus requires extended confirmation delays and remains vulnerable to reversibility and strategic attacks. ByzCoin combines strong consistency, collective signing, and dynamically formed proof-of-work-weighted groups to improve confirmation speed, scalability, and security.

  • Motivation: About one hour may be needed for Bitcoin transactions to become secure and irreversible, limiting suitability for real-time use.Bitcoin’s probabilistic consistency also leaves transactions exposed to reversibility, double-spending, and strategic mining attacks.
  • Motivation: Strong consistency would let miners agree immediately, allow confirmation when a transaction appears, and provide forward security after block commitment.These benefits avoid resolving forks and reduce the need for prolonged waiting before accepting transactions.
  • Approach: ByzCoin applies PBFT principles to Bitcoin while addressing open membership, large consensus groups, proof-of-work conflicts, and transaction commitment rate.Its design combines collective signing with proof-of-work-proportional dynamic membership and transaction-verification decoupling.
  • Results: Less than 20 seconds is required for a 144-miner group to reach consensus on a 1MB block.A 1008-miner group reaches consensus on an 8MB block in 90 seconds, while a 144-participant group processes 974 TPS with 32MB blocks and 68-second confirmation latency.
  • Limitations: ByzCoin remains limited by Bitcoin’s proof-of-work and can suffer temporary denial-of-service, censorship, or exclusion under Byzantine behavior.Its security guarantee applies only when attackers consistently control less than one third of consensus-group shares.
  • Results: Two orders of magnitude higher throughput and confirmation latency under one minute are demonstrated experimentally for a strongly consistent cryptocurrency.The contribution statement reports these as the central experimental outcomes.

2 Background and Motivation

Bitcoin’s probabilistic, fork-prone consensus creates confirmation, throughput, and scalability limitations, while PBFT provides strong consistency but assumes small, closed replica groups. CoSi’s collective signatures and communication trees offer the mechanisms ByzCoin uses to address these constraints.

  • Bitcoin: Bitcoin uses proof-of-work blocks and a longest-chain rule, but temporary forks can invalidate transactions and force clients to wait about six additional blocks.This corresponds to an average confirmation latency of about 60 minutes.
  • Bitcoin: 7 TPS is Bitcoin’s estimated throughput limit, compared with 500 TPS for PayPal and 4000 TPS for VISA.Increasing block size could raise throughput but also increases propagation delays and fork probability.
  • Bitcoin-NG: Bitcoin-NG separates proof-of-work keyblocks for leader election from transaction-carrying microblocks, improving throughput without resolving Bitcoin’s consistency weaknesses.Leaders can still fork or rewrite history, leaving clients exposed to double spending without extended confirmation waits.
  • Byzantine Fault Tolerance: PBFT tolerates at most f faults among 3f + 1 participants and uses pre-prepare, prepare, and commit phases with two-thirds quorums.A view-change protocol replaces a faulty leader when a quorum detects malicious behavior or lack of progress.
  • Byzantine Fault Tolerance: PBFT’s fixed membership, O(n^2) communication, and requirement that clients contact a super-majority make large-scale deployment and secure verification difficult.These limitations motivate scalable group formation, tree communication, and compact collective signatures.
  • Scalable Collective Signing: CoSi lets a leader obtain a collectively signed statement from decentralized witnesses using communication trees, producing a compact signature with efficient verification.The protocol combines Schnorr multisignatures with tree aggregation; an Ed25519 signature is about 64 bytes.

3 ByzCoin Design

ByzCoin progressively transforms a simplified PBFT-and-Bitcoin design into a cryptocurrency protocol that preserves Byzantine safety while addressing open membership, scalability, and network assumptions.

  • System model: ByzCoin is designed for weakly synchronous, untrustworthy networks and assumes Byzantine miners control less than 1/4 of total hash power.Miners may arbitrarily delay, drop, reorder, or duplicate messages; the hash-power bound addresses vulnerability to selfish mining attacks.
  • Strawman design: ByzCoin starts from PBFTCoin, an intentionally simplified combination of PBFT and Bitcoin with a fixed trustee group of n = 3f + 1.PBFTCoin assumes at most f faulty trustees and uses them to maintain a Bitcoin-like blockchain.
  • Strawman design: The fixed-trustee assumption is unrealistic for open-membership cryptocurrencies, while MAC-authenticated direct communication creates O(n^2) communication complexity.These restrictions motivate the subsequent ByzCoin refinements.
  • Design progression: ByzCoin addresses its design challenges by dynamically determining consensus groups with proof of work, replacing direct MAC communication with signatures, and refining PBFT-based processing.The stated refinements preserve Bitcoin’s Sybil resistance while reducing normal-case communication costs.

3.3 Opening the Consensus Group

ByzCoin opens PBFT membership by using proof-of-work shares from recently successful miners, making voting power proportional to recent mining activity while retaining incentives for participation.

  • Opening membership: Open membership conflicts with conventional BFT assumptions because security thresholds require a defined group, while unrestricted membership permits Sybil attacks.ByzCoin uses proof-of-work to identify resource-committed participants.
  • Proof of membership: Each newly mined block grants its miner a consensus-group share, while shares outside the fixed-size sliding window expire.The mechanism converts Bitcoin mining into proof of membership.
  • Proof of membership: A miner’s voting power equals its current-window shares, making group influence statistically proportional to contributed hash power when aggregate hash power is stable.Voting power reflects successful mining within the active window.
  • Share window: A one-day or one-week window at a ten-minute mining rate yields w = 144 or w = 1008, respectively.The window size affects fault resilience and limits membership to recently active miners.
  • Mining rewards: ByzCoin splits block rewards and transaction fees across current consensus-group members in proportion to their shares.This incentive replaces the assumption of voluntary participation in the fixed PBFTCoin group.

3.4 Replacing MACs by Digital Signatures

ByzCoin replaces PBFT’s direct MAC-based authentication with digital signatures, enabling transferable evidence and sparser communication patterns that reduce normal-case communication complexity.

  • Communication scalability: PBFT’s MAC-authenticated all-to-all communication has O(n^2) complexity, motivating a more scalable authentication design.The original choice avoided public-key operations, but improved asymmetric cryptosystems make that cost less problematic.
  • Communication scalability: Digital signatures let the leader collect and distribute third-party-verifiable evidence without requiring every trustee to communicate directly with every other trustee.The resulting sparse topologies can reduce normal-case communication complexity from O(n^2) to O(n).

3.5 Scalable Collective Signing

ByzCoin uses collective signing to make PBFT’s prepare and commit phases scalable, reducing per-node verification costs and providing compact proofs of irreversible transaction commitment.

  • Collective signing: CoSi aggregates signatures for PBFT rounds, serving as a scalable primitive rather than implementing consensus or Byzantine fault tolerance itself.ByzCoin uses CoSi to collect and aggregate prepare and commit messages.
  • PBFT integration: Two sequential CoSi rounds implement PBFT’s prepare and commit phases, with the first producing a super-majority proof of acceptance.The leader initiates both rounds.
  • PBFT integration: The second commit round prevents a Byzantine leader from double-spending by requiring members to validate the prepare proof and collectively sign the block hash.At least one honest node would otherwise need to sign both conflicting histories.
  • Scalability benefits: O(1)-size messages and O(1) verification replace O(n)-size messages and O(n) computation when participants verify a collective signature instead of n individual signatures.This reduces bandwidth and computation costs during consensus rounds.
  • Light-client verification: An O(1)-size collective commit signature lets light clients verify irreversible block and transaction commitment in O(1) computation time.Verification does not require storing the full blockchain or trusting a particular full node.

3.6 Decoupling Transaction Verification from Leader Election

ByzCoin decouples leader election from transaction verification using proof-of-work keyblocks and collectively signed microblocks. This design resolves keyblock conflicts deterministically while preserving an ordered, consistent microblock chain.

  • Architecture: Keyblocks elect leaders and establish consensus-group membership, while microblocks carry transactions and are collectively signed by the current group.Keyblocks use proof-of-work; microblocks reference preceding microblocks and keyblocks to preserve ordering and identify the authoritative group and leader.
  • Architecture: ByzCoin stores keyblocks and microblocks in separate parallel chains, avoiding the race caused when miners must update keyblock headers as microblocks arrive.The keyblock chain records mined blocks, while the microblock chain depends on it to identify each microblock’s era, group, and leader.
  • Consistency: An honest super-majority prevents a malicious or amnesiac leader from extending any microblock other than the most recently committed one.Competing keyblocks may still appear, but they cannot create an inconsistent microblock chain; they can only temporarily interrupt liveness until resolution.
  • Keyblock conflicts and selfish mining: Keyblock forks are resolved by hashing the sorted competing headers and using final hash bits to select the winner without voting.Because part of the hash input is unknown before the fork, the resulting entropy is difficult for an attacker to optimize; gaining better-than-50% fork odds is as hard as finding a new block.
  • Fairness and view changes: Mandatory PBFT view-changes transfer verification authority to each newly elected keyblock miner, addressing the fairness cost of decoupling verification from leader election.When keyblock conflicts occur, competing view-changes may cause miners to adopt one keyblock and its associated consensus group.
  • Tree creation: Prebuilding communication trees during the preceding keyblock round reduces coordination overhead and lets conflicting leaders use the same propagation pattern.The process also stops the previous leader from wasting effort on microblocks and helps nodes learn and decide conflicts quickly.

3.7 Tolerating Churn and Byzantine Faults

ByzCoin treats tree communication as a normal-case optimization rather than a sole requirement, reverting to flat communication when tree faults threaten liveness. It also addresses membership churn by requiring stronger support for the first microblock of a new era.

  • Threat model: A Byzantine adversary may compromise tree-based liveness through denial of service, so ByzCoin must tolerate failures in strategically important tree nodes.The analysis considers attackers able to identify the correct signing-tree nodes and trigger a simple DoS attack.
  • Tree fault tolerance: When tree communication is compromised, the leader can revert to non-tree communication for the remainder of the era, preserving a more robust fallback.Tree communication is explicitly treated as a normal-case performance optimization rather than a prerequisite for the protocol’s operation.
  • Tree fault detection: A failed tree is detected when the leader does not receive two-thirds of acknowledgments before the timer expires or a rejection arrives.The leader then switches to the flat structure before witnesses conclude that the leader itself is faulty.
  • Fallback performance: Flat ByzCoin remains able to sign keyblocks quickly for a 144-witness, day-long window while maintaining throughput higher than Bitcoin’s, but communication latency returns to O(n).If all floor(N/3) faults are consecutive leaders, the worst case can reach O(n^2) communication latency.
  • Membership churn and BFT: The first microblock of a new era requires 2f + 2 supporting signatures to ensure it extends the previous leader’s latest committed microblock despite stale membership views.If the leader cannot obtain that support, it synchronizes by obtaining a latestcheckpoint from the previous roster and the node that lost membership.

4 Performance Evaluation

ByzCoin’s evaluation measures consensus latency and throughput under varying group sizes and block sizes, using tree-based collective signing to scale beyond flat communication. The prototype achieves sub-20-second consensus for 144-node, 1 MB groups and near-1000 TPS while exposing a latency–throughput trade-off.

  • Experimental Setup: The evaluation varies consensus group size, block size, communication layout, and throughput configuration to assess ByzCoin’s practical overhead.Experiments use up to 1008 simulated nodes, 200 ms round-trip latency, and 35 Mbps per simulated host; transaction verification is emulated.
  • Consensus Group Size Comparison: 28 times more nodes, from 36 to 1008, increase tree-based consensus latency close to 2 times, from 6.5 to 14 seconds.For 1008 nodes, tree-based ByzCoin’s 1 MB signing latency is lower than the flat approach with 36 nodes; at 1008 nodes it is 3 times faster than individual-signature tree communication.
  • Block Size Comparison: A 2 MB block quadruples flat consensus latency, whereas tree-based ByzCoin maintains scalability because the leader outsources block transmission to other nodes.PBFT reaches 40 seconds for 250 KB blocks in the compared experiment, while ByzCoin’s 1 MB signing latency is close to 10 seconds.
  • Block Size Comparison: 90 seconds is sufficient for tree-based ByzCoin to sign a 32 MB block containing approximately 66,000 transactions, compared with approximately 10 minutes for Bitcoin.For 8 MB blocks, signing latency increases only linearly even with 1008 miners; one-transaction blocks take 3 seconds.
  • Transaction Throughput: Close to 1000 TPS is achieved with 144 nodes, while the 1008-node configuration reaches close to 700 TPS and the flat ByzCoin-like model raises Bitcoin throughput by more than one order of magnitude.The 144-node result is reported as double PayPal’s throughput; reverting to 1 MB microblocks when the tree fails still gives ten times Bitcoin’s current throughput.
  • Transaction Throughput: 10–20 seconds of latency is available with 1–2 MB microblocks under normal load, while adaptive block sizing increases throughput during overload.The simple ByzCoin variant instead has optimal throughput and acceptable latency with 1 MB microblocks.

5 Security Analysis

ByzCoin’s security analysis examines transaction safety, proof-of-membership security, and defenses against Bitcoin attacks. It reports sub-minute transaction security, evaluates consensus-group sampling, and identifies attack conditions and remaining vulnerabilities.

  • 5.1 Transaction Safety: ByzCoin secures transactions in below one minute, whereas Bitcoin requires several hours to reach the same double-spending guarantee.The comparison concerns the time until a double-spending attack has less than 0.1% chance of success; ByzCoin’s latency is tied to producing a collectively signed microblock.
  • 5.2 Proof-of-Membership Security: The proof-of-membership analysis models Byzantine members with a cumulative binomial distribution over the share-window size w.The model uses Byzantine probability p = 0.25 and evaluates the probability of selecting fewer than c = ⌊w/3⌋ Byzantine members.
  • 5.2 Proof-of-Membership Security: w = 144 is the suggested lower bound for the share window, while w = 288 and above provides a more reasonable security margin and w = 1008 still performs well.Window selection must balance consensus latency, a desired security level of ideally ≥99%, and increased resource churn for larger windows.
  • 5.3 Defense Against Bitcoin Attacks: A collectively signed microblock mitigates Race and Finney attacks with verification latency from a few seconds up to one minute.A single transaction can instead be sent for signing and secured in less than 4 seconds, at higher cost.
  • 5.3 Defense Against Bitcoin Attacks: Checking a microblock’s collective signature lets merchants verify super-majority acceptance, after which conflicting forks are rejected and a view change occurs.This mechanism addresses N-confirmation double-spend attempts because the remaining signers reject the attacker’s new block, even when the attacker is leader.
  • 5.3 Defense Against Bitcoin Attacks: Collective signatures prevent an eclipsed victim from accepting an alternate attacker-controlled transaction history, although ByzCoin does not prevent eclipsing or message delays.The guarantee applies to transaction commitment within a partitioned network fragment.
  • 5.3 Defense Against Bitcoin Attacks: Selfish and stubborn mining strategies become ineffective because ByzCoin resolves forks deterministically, making hidden-chain construction waste resources and reduce revenue.The paper leaves bias-resistant public randomness as a future approach for attackers controlling more than 33% hash power.
  • 5.3 Defense Against Bitcoin Attacks: ByzCoin inherits Bitcoin-NG’s vulnerability to temporary leader censorship, although later honest leaders eventually process censored transactions.The consensus group’s other miners also double-check the leader’s actions.

6 Related Work

Related work addresses Bitcoin’s performance, latency, membership, or consensus limitations through alternative chain rules, off-chain mechanisms, sidechains, and Byzantine protocols. ByzCoin differs by targeting scalable Byzantine consensus while retaining open membership.

  • Open-membership consensus: ByzCoin and Bitcoin both implement state-machine replication with open membership, unlike classic Byzantine-fault-tolerant systems with static or slowly changing groups.The comparison includes PBFT, Tendermint, and Hyperledger as more traditional approaches.
  • Bitcoin performance proposals: GHOST changes Bitcoin’s fork-selection rule by choosing the subtree receiving the most computational effort rather than the chain with the most proof-of-work.The cited passage presents GHOST as a proposal addressing Bitcoin performance shortcomings.
  • Off-chain and sidechain approaches: Off-chain channels and sidechains improve latency, throughput, or workload distribution but do not address the core scaling problem of open, distributed state-machine replication.The passage names the two-point channel protocol, Lightning Network, micropayment channels, and sidechains.
  • Byzantine consensus alternatives: Ripple uses collectively trusted subnetworks, Tendermint evaluates at most 64 validators, and PeerCensus remains a preliminary theoretical alternative.The passage also identifies validator link bandwidth as a primary bottleneck that Tendermint does not address.
  • Byzantine consensus alternatives: Stellar’s Federated Byzantine Agreement enables participation through quorum slices, but its security depends on clients correctly configuring trustees under a nontrivial trust model.

7 Limitations and Future Work

The paper identifies limitations involving leader-based exclusion, attacks beyond the Byzantine threshold, proof-of-work assumptions, and unresolved scaling and randomness questions. Several defenses are proposed, but fuller analysis remains future work.

  • Consensus-group exclusion: A malicious leader can exclude consensus-group nodes by controlling communication-tree placement, although exclusion also costs the victims newly minted-coin rewards.The attack is possible in both flat and tree-based variants, with different leader-control mechanisms.
  • Consensus-group exclusion: A peer-to-peer overlay and self-adapting communication tree could mitigate leader exclusion by allowing nodes to receive announcements from multiple sources and reattach subtrees.The paper leaves a more thorough analysis of this attack for future work.
  • Defenses against 33%+ attacks: Attackers controlling more than one-third of consensus shares can censor transactions or obtain signatures for conflicting microblocks, and ByzCoin safety fails at 30% in the cited comparison.Bitcoin remains safe at 48% in that comparison if clients can wait long enough.
  • Defenses against 33%+ attacks: The peer-to-peer network can detect equivocation such as microblock forks when messages are authenticated and spoofing is impossible, but the analysis assumes complete network control is unrealistic.
  • Proof-of-work alternatives: Proof-of-work remains a scope boundary because its energy waste and ASIC advantages motivate alternatives such as memory-intensive puzzles, proof-of-stake, and social-trust methods.The paper treats the ideal proof-of-work alternative as an issue for future work.
  • Other directions: Sharding could improve ByzCoin’s scalability, but generating bias-resistant public randomness must first be analyzed for a sharded design.

8 Conclusion

ByzCoin is a scalable Byzantine-fault-tolerant consensus algorithm for open decentralized blockchain systems. Its strong consistency strengthens security against several Bitcoin attacks while enabling high scalability and low transaction latency.

  • Conclusion: ByzCoin applies scalable Byzantine fault tolerance to open decentralized blockchain systems such as Bitcoin.
  • Conclusion: Strong consistency shields against N-confirmation double-spending, intentional forks, and selfish mining while enabling high scalability and low transaction latency.
Loading 1602.06997v3…