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.
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.
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