Using Throughput-Centric Byzantine Broadcast to Tolerate Malicious Majority in Blockchains

Ruomu Hou, Haifeng Yu, Prateek Saxena

Abstract

Fault tolerance in blockchains is typically defined by the fraction $f$ of adversarial power the system can withstand. While most existing designs are limited to $f < 0.5$, this work demonstrates that blockchains can indeed tolerate a malicious majority. By shifting the core primitive from Byzantine Consensus to a novel, throughput-centric Byzantine Broadcast protocol called OverlayBB, we present BCube: a Proof-of-Stake blockchain capable of operating under $f = 0.7$. In experiments with 10,000 nodes, BCube achieves a transaction throughput of 163 Kbps and practical confirmation latencies, marking a significant milestone in robust decentralized systems.

Introduction

Most modern blockchains, including Bitcoin and Ethereum, rely on Byzantine Consensus, which is mathematically impossible to achieve when an adversary controls 50% or more of the network ($f \ge 0.5$). This vulnerability is increasingly relevant as mining power concentrates and "51% attacks" become more frequent.

While the primitive known as Byzantine Broadcast (BB) can theoretically tolerate up to $f < 1$, traditional BB protocols suffer from extremely low throughput. They often flood the network with signatures, resulting in a "throughput-to-bandwidth" (TTB) ratio so poor that high-speed connections yield only bits per second of useful data. BCube bridges this gap by optimizing BB for high-throughput blockchain environments.

The OverlayBB Protocol

To overcome the bandwidth explosion of traditional broadcast, the authors developed OverlayBB. This protocol introduces several key mechanisms to ensure efficiency and security:

  • Fragmentation: Blocks are split into $s$ fragments, allowing for parallelized transmission and reduced individual message sizes.
  • The Forerunner Rule: To prevent nodes from accepting incomplete data, a node may only forward the final fragment (containing cryptographic signatures) if it has already successfully forwarded all preceding fragments.
  • Delay and Compensation: To mitigate "junk" proposals from an adversary, nodes use a scoring system ($2dy - t$) to prioritize pushes. If network congestion causes delays, the protocol adjusts the acceptance threshold to compensate.
  • Signature Aggregation: Utilizing BLS381 (MSP-pop), hundreds of signatures are compressed into a single 96-byte string, drastically reducing overhead.
Table of key notation and parameters used in the OverlayBB and BCube protocols.

BCube: A Robust Blockchain Architecture

BCube integrates OverlayBB into a Proof-of-Stake (PoS) framework. To maintain continuous operation, it employs Pipelining, where multiple instances of OverlayBB run concurrently to fill blockchain slots.

Illustration of pipelined broadcast instances and the round-by-round message flow between nodes, including adversarial alignment of busy rounds.

Furthermore, BCube addresses the risk of a malicious majority biasing the random beacons used for committee selection. By introducing a "weak" Proof-of-Work (PoW) requirement for beacon generation, the system forces adversaries to expend significant computational resources to manipulate the selection process, even if they hold a majority of the stake.

Evaluation and Key Results

The system was evaluated using a Go implementation deployed across 21 high-end PCs, simulating a 10,000-node network with a 20 Mbps bandwidth cap per node. Under a malicious fraction of $f = 0.7$, the results were as follows:

  • Throughput: BCube achieved 163 Kbps. While lower than $f < 0.5$ chains, this is 350x faster than previous BB-based designs and exceeds Bitcoin's average throughput (~14 Kbps).
  • Latency: Confirmation for a $2^{-30}$ error probability takes less than 6 hours. For comparison, Bitcoin requires over 9 hours to reach the same mathematical certainty against a 25% adversary.
  • Scalability: The performance remains stable as the network scales to 10,000 nodes, proving the protocol's viability for large-scale public deployment.

Conclusion and Future Work

BCube proves that the "50% barrier" is not an absolute limit for functional blockchains. By prioritizing throughput in Byzantine Broadcast, it is possible to build systems that remain secure even when the majority of the network is malicious.

Future research will focus on relaxing the synchronous network assumption (where messages must arrive within a fixed time $\delta$) and exploring "progressive confirmation" to reduce latency for smaller transactions. Despite these remaining challenges, BCube provides a foundational blueprint for the next generation of highly fault-tolerant decentralized ledgers.

Summary updated

Abstract

Fault tolerance of a blockchain is often characterized by the fraction $f$ of "adversarial power" that it can tolerate in the system. Despite the fast progress in blockchain designs in recent years, existing blockchain systems can still only tolerate $f$ below $0.5$. Can practically usable blockchains tolerate a malicious majority, i.e., $f$ above $0.5$? This work presents a positive answer to this question. We first note that the well-known impossibility of {\em byzantine consensus} for $f$ above $0.5$ does not carry over to blockchains. To tolerate $f$ above $0.5$, we use {\em byzantine broadcast}, instead of byzantine consensus, as the core of the blockchain. A major obstacle in doing so, however, is that the resulting blockchain may have extremely low throughput. To overcome this central technical challenge, we propose a novel byzantine broadcast protocol OverlayBB, that can tolerate $f$ above $0.5$ while achieving good throughput. Using OverlayBB as the core, we present the design, implementation, and evaluation of a novel Proof-of-Stake blockchain called BCube. BCube can tolerate a malicious majority, while achieving practically usable transaction throughput and confirmation latency in our experiments with $10000$ nodes and under $f = 0.7$. To our knowledge, BCube is the first blockchain that can achieve such properties.
BibTeX
@inproceedings{hou2022using,
  author = {Ruomu Hou and Haifeng Yu and Prateek Saxena},
  title = {{Using Throughput-Centric Byzantine Broadcast to Tolerate Malicious Majority in Blockchains}},
  booktitle = {IEEE Symposium on Security and Privacy},
  year = {2022},
  url = {https://openreview.net/forum?id=0arHLqXdOo},
}
Figure