Rigorous and Generalized Proof of Security of Bitcoin Protocol with Bounded Network Delay

1. Problem Statement

The paper addresses the formal security proof of the Bitcoin protocol under a bounded network delay model ($\Delta$-bounded delay), where an adversary can delay the transmission of blocks by up to time $\Delta$.

While previous works (specifically [7] and [8]) attempted to prove Bitcoin's security in this model, the authors identify critical flaws and limitations:

• Incorrect Assumption in [7]: The proof in [7] incorrectly assumes that the difference between the adversary's chain length and the honest chain length follows a random walk. The authors provide a counterexample demonstrating that this process is not a random walk due to dependencies in block arrival times.
• Complexity and Lack of Rigor in [8]: The alternative proof in [8] is described as long, non-intuitive, and lacking precise definitions for the variables used in its ergodic arguments.
• Limited Scope: Existing proofs generally assume uniform block scores (standard Bitcoin). They do not easily generalize to protocols allowing blocks of different types with varying point values (scores), such as the "Merged Bitcoin" protocol introduced in a companion paper.

The goal is to provide a rigorous, self-contained, and generalized proof that establishes the security region for Bitcoin (and generalized variants) where the honest mining rate exceeds the adversary's rate, even under network delays.

2. Methodology and Model

The authors propose a generalized model and a novel mathematical approach to resolve the errors in prior work.

A. Generalized Protocol Model

• Variable Block Scores: Unlike standard Bitcoin where every block has a score of 1, this model allows miners (both honest and adversarial) to mine blocks of different types, each with a specific score $c_i > 0$.
• Fork-Choice Rule: Miners extend the chain with the highest total score.
• Network Model: The $\Delta$-bounded delay model is used. The adversary can delay honest blocks by up to $\Delta$ and delay their own blocks arbitrarily before broadcasting, but once broadcast to one honest node, the delay to others is bounded by $\Delta$.

B. Key Definitions

• Fully-Delayed Honest Chain ($T_h$): A hypothetical chain where all honest blocks are delayed by the maximum time $\Delta$ and no adversary blocks are present.
• Nakamoto Interval: A time interval of length $2q$ centered at $\tau_q$ containing exactly one honest block (a "loner") such that:
  1. No other honest blocks exist in the extended interval $[\tau_q - q - \Delta, \tau_q + q + \Delta]$.
  2. No adversary blocks exist in $[\tau_q - q - 2\Delta, \tau_q + q + 2\Delta]$.
  3. The honest chain dominates the adversary chain in the past (Event $E_1$) and future (Event $E_2$) relative to this interval.
• Nakamoto Block: The honest block arriving within a Nakamoto interval. The paper proves these blocks stay in the canonical chain forever.

C. Mathematical Approach: The Punctured Arrival Process

To correct the "random walk" error in [7], the authors introduce a punctured arrival process:

1. Puncturing: The timeline is divided into intervals of length $B$ followed by gaps of length $\Delta$. Blocks arriving during the $\Delta$ gaps are "deleted" (punctured).
2. Independence: This puncturing creates independent and identically distributed (i.i.d.) segments of score growth.
3. Random Walk Construction: The cumulative score of these punctured segments forms a true random walk.
   • If the honest mining rate ($\lambda_h$) is greater than the adversary rate ($\lambda_a$), the random walk has a positive drift.
   • Using random walk theory, the authors prove that with probability $p > 0$, the honest score growth stays above a certain threshold indefinitely, while the adversary score growth stays below its average.

3. Key Contributions

1. Correction of Prior Errors: The paper explicitly identifies and fixes the erroneous random walk assumption in [7] by utilizing a punctured block arrival process to generate a valid random walk with i.i.d. increments.
2. Generalization to Multi-Score Blocks: The proof is generalized to handle blocks with different scores, making it applicable to "Merged Bitcoin" and other generalized consensus mechanisms.
3. Rigorous Security Region Definition: The authors define the security region strictly as $\lambda_a < \lambda_h$, where $\lambda_h$ is the fully-delayed honest score growth rate and $\lambda_a$ is the adversary score growth rate.
4. Bootstrap Argument: The paper employs an induction-based "bootstrap argument" to show that the probability of having no secure blocks in a time interval $t$ decays exponentially as $t$ increases.

4. Key Results

The paper establishes the following theorems:

• Theorem 1 (Nakamoto Blocks Persist): If a Nakamoto interval occurs (defined by events $L_q$, $E_1$, and $E_2$), the honest block within that interval remains in the canonical chain forever.
• Theorem 2 (Existence of Nakamoto Intervals): If $\lambda_h > \lambda_a$, the probability that any given interval of sufficient size is a Nakamoto interval is strictly greater than 0.
  • This is proven by showing that the honest score growth rate stays close to or above $\lambda_h$ and the adversary rate stays close to or below $\lambda_a$ with non-zero probability.
• Theorem 3 (Main Security Theorem): If $\lambda_h > \lambda_a$, the probability that a sub-interval of length $t$ contains no honest blocks that stay in the chain forever goes to zero exponentially as $t \to \infty$.
• Corollary (Infinite Honest Blocks): With probability 1, the canonical chain contains infinitely many honest blocks if $\lambda_h > \lambda_a$.
• Theorem 4 (Insecurity Region): If $\lambda_a > \lambda_h$, the protocol is insecure. An adversary can execute a private mining attack to eventually dominate the chain with probability 1.

5. Significance

• Rigorous Foundation: This work provides the first rigorous, self-contained proof of Bitcoin's security in the bounded-delay model that corrects the mathematical flaws of previous attempts.
• Robustness: By proving security for generalized block scores, the results support the viability of complex blockchain extensions like Merged Bitcoin, ensuring they inherit the same security guarantees as standard Bitcoin.
• Methodological Advancement: The introduction of the punctured arrival process offers a new, robust technique for analyzing stochastic processes in distributed systems where standard random walk assumptions fail due to network delays and dependencies.
• Clear Security Boundary: The paper definitively establishes that the condition for security is simply that the fully-delayed honest mining rate must exceed the adversary's mining rate, providing a clear metric for network designers.

In summary, the paper resolves long-standing gaps in the theoretical understanding of Bitcoin's security, offering a mathematically sound proof that the protocol remains secure against all attacks (including selfish mining and balance attacks) as long as the honest network's effective mining power (accounting for delays) exceeds that of the adversary.