Blockchain Security when Messages are Lost

Taha Ameen, Suryanarayana Sankagiri, Bruce E. Hajek

Abstract

Traditional blockchain security analysis often relies on synchronous network assumptions that do not reflect the realities of the public internet. This work explores the $0-\infty$ communication model, where messages between honest miners are either delivered instantly or lost permanently. By analyzing the structure of block propagation through transmission-graphs, the authors establish a new, tighter security threshold for the longest-chain protocol: $\frac{\beta}{1-\beta} < 1 - d$. This result demonstrates that blockchains are significantly more resilient to message loss than previously suggested in literature.

Introduction: Beyond Ideal Networks

Most security proofs for protocols like Bitcoin’s longest-chain rule assume a synchronous model where messages arrive within a fixed, known time limit. However, real-world networks experience packet drops and timeouts. In academic terms, a lost message represents "infinite delay."

Significant message loss can fragment honest miners, causing them to see different versions of the "longest chain." Meanwhile, a coordinated adversary—who communicates perfectly internally—gains a massive advantage to create forks and execute double-spend attacks. This research addresses a critical gap: quantifying exactly how much message loss a blockchain can handle before its security collapses.

Methodology: The $0-\infty$ Model and Transmission-Graphs

The authors introduce the $0-\infty$ communication model: when an honest miner broadcasts a block, every other honest miner either receives it instantly (with probability $1-d$) or never receives it at all (with probability $d$). To analyze this setup, the researchers move beyond simple chain-growth counting and utilize complex combinatorial tools:

  • Transmission-Graphs: A directed acyclic graph (DAG) that maps out exactly which honest miners "heard" which blocks, providing a structural view of network consensus.
  • Forward and Backward Special Sequences: Specific chains of blocks (FS and BS blocks) that act as anchors for the network's consensus.
  • $\eta$-Nakamoto Blocks: A refined version of "Nakamoto blocks"—blocks mathematically guaranteed to remain in every future longest chain.
Main-blocktree and corresponding Transmission-graph.

Key Insights and Robustness

A central finding of this work is that security does not necessarily collapse even when more than half of the messages are lost ($d > 0.5$). By focusing on the propagation structure rather than simple block counts, the authors identified a significantly larger "safe zone" for protocol operation.

Key observations include:

  • Exponential Security: The probability of a security violation (e.g., a transaction reversal) decays almost exponentially as the number of confirmations ($\tau$) increases.
  • Linear Scaling with Users: The risk of failure scales linearly with the number of honest users ($|H|$), reflecting the statistical difficulty of ensuring every user in a large group reaches the same conclusion simultaneously in a noisy environment.
  • Robustness Measure ($\eta$): The parameter $\eta$ allows for the quantification of the "lead" honest miners maintain over adversarial side-chains.

Key Results: A Tighter Security Bound

The primary contribution of this work is the establishment of a new security bound: the protocol is secure if $\frac{\beta}{1-\beta} < 1 - d$, where $\beta$ is the adversary's share of computing power and $d$ is the probability of message loss.

Comparison of the tolerable adversarial power $\beta$ vs. message loss probability $d$.

As illustrated in the figure above, this new bound (the blue line) significantly expands the known "tolerable region" for adversarial power compared to previous state-of-the-art analysis (the orange line). This proves that blockchains can remain secure even in high-noise regimes, provided the adversarial power is sufficiently low.

Limitations and Future Work

While the $0-\infty$ model provides a robust theoretical foundation, it is a simplification; real-world network delays are usually a mix of short delays, long delays, and total losses. Additionally, the model assumes a "perfectly coordinated" adversary, which is a standard worst-case assumption. Future work could involve applying these transmission-graph techniques to Proof-of-Stake (PoS) or other BFT-based consensus mechanisms to further explore resilience in non-ideal network conditions.

Summary updated

BibTeX
@inproceedings{ameen2022blockchain,
  author = {Taha Ameen and Suryanarayana Sankagiri and Bruce E. Hajek},
  title = {{Blockchain Security when Messages are Lost}},
  booktitle = {ConsensusDay@CCS},
  year = {2022},
  doi = {10.1145/3560829.3563557},
}
Figure