Technical Summary: Merged Bitcoin: Proof of Work Blockchains with Multiple Hash Types

1. Problem Statement

The Bitcoin protocol, while securing over one trillion USD in value, faces significant security risks associated with a 51% attack. The primary motivation for this work is to increase the security threshold of the Bitcoin protocol to alleviate the risk of such catastrophic attacks. Current methods to increase security, such as increasing honest mining power via specialized SHA-256 circuits, introduce vulnerabilities:

• Centralization: Reliance on specialized circuits concentrates power among agents with the best access to them.
• Hardware Backdoors: A limited number of ASIC manufacturers creates a single point of failure; if compromised, the protocol becomes vulnerable even if the majority of miners are honest.
• Quantum and Algorithmic Advances: Adversaries may gain asymmetric advantages through algorithmic improvements or specialized hardware (e.g., Grover's algorithm for quantum speedup) targeting a single hash type.

The authors propose Merged Bitcoin, a protocol that allows blocks linked by different hash types to form a single chain. The goal is to increase the cost of attack, reduce centralization risks, and mitigate vulnerabilities specific to single hash types.

2. Methodology and Theoretical Framework

The Multiple Random Resource Model

The paper models nodes (honest and dishonest) as possessing varying amounts of hashing resources for $n$ different hash types. These resources parameterize a Poisson arrival process.

• Blockrates: The model defines honest blockrates ($h_i$) and dishonest blockrates ($b_i$) for each hash type $i$, measured in blocks per second.
• Score System: Each block type $i$ is assigned a score constant $c_i$. The fork choice rule selects the chain with the highest total score ($\sum c_i N_i$, where $N_i$ is the count of blocks of type $i$).
• Network Model: The analysis operates under a $\Delta$-bounded delay network model, where network latency is bounded by $\Delta$.

Information-Theoretic Motivation and Impossibility

The authors initially investigate whether security can be conditioned on an "AND" of multiple 51% thresholds (i.e., the protocol is secure unless an adversary controls >50% of every hash type simultaneously).

• The "Big-And" Hypothesis: The authors explore if an information-theoretic exponentially decreasing error probability can be achieved if insecurity requires an adversary to dominate all hash types.
• Impossibility Result (Theorem 10): The paper proves that for any permissionless distributed protocol satisfying specific properties (chain property, adversary equivalence, and adversary withhold ability), the "Big-And" security region is impossible. If a protocol is secure under a configuration $(h, b)$, it cannot be secure under the swapped configuration $(b, h)$. This implies that a protocol cannot be secure whenever any single hash type has less than 50% adversarial power; insecurity can occur even if the adversary controls less than 50% of some hash types, provided they control enough of others.

Security Region Analysis

Despite the impossibility of the ideal "Big-And" region, the paper derives closed-form bounds for the security region of Merged Bitcoin.

• Security Condition: Merged Bitcoin is secure if the adversary's score growth rate ($\lambda_a = \sum c_i b_i$) is strictly less than the honest score growth rate ($\lambda_h$) under full delay conditions.
• Bounds Derivation:
  • Lower Bound (Lemma 13/17): Derived using a "Delta Interval Deletion Process," which removes blocks arriving within $\Delta$ of a "guaranteed" block. This yields a conservative estimate of the honest score growth rate.
  • Upper Bound (Lemma 15/19): Derived using a "Small Block Increase Process," which artificially increases the score of small blocks if a larger block arrives within $\Delta$. This provides an upper limit on the honest score growth rate.
• Zero Delay Case: When $\Delta = 0$, the security region simplifies to $\sum c_i b_i < \sum c_i h_i$.

3. Key Contributions and Results

1. Formalization of Merged Bitcoin

The paper introduces a protocol where blocks of different hash types form a single chain, governed by a score-based fork choice rule. It provides closed-form upper and lower bounds on the security region in the $\Delta$-bounded delay model.

2. Optimization of Attack Cost

In a linear cost-per-hash economic model, the paper proves that Merged Bitcoin can maximize the cost of an attack.

• Theorem 23: By appropriately choosing score constants $c_i$ such that the cost-per-unit-score is equal across all hash types ($p_i/c_i$ is constant), the minimum cost of attacking Merged Bitcoin equals the sum of the costs of attacking each individual protocol separately ($p_1 h_1 + p_2 h_2$). This is proven to be the optimal cost of attack for any multi-hash consensus protocol under these constraints.

3. Difficulty Adjustment Mechanism

To prevent the protocol from collapsing into a single hash type due to technological advances or cost asymmetries, the authors propose a minimum fraction difficulty adjustment.

• If the fraction of blocks produced by a specific hash type falls below a threshold, its relative difficulty is incrementally adjusted downward. This ensures that miners will re-enter the market for that hash type once it becomes profitable, maintaining a diverse mix of hash types.

4. Comparison with Minotaur

The paper distinguishes Merged Bitcoin from the Minotaur protocol (a merged Proof-of-Work/Proof-of-Stake system).

• Chain Outage: Minotaur can suffer a permanent chain outage if no blocks are produced in a recency interval; Merged Bitcoin does not.
• Takeover Attacks: Minotaur is vulnerable to a takeover attack where an adversary can eventually control the chain with probability 1 if they control any mining power, due to the finite recency interval. Merged Bitcoin maintains a non-zero fraction of honest blocks with probability 1.
• Prospective Attacks: Minotaur is vulnerable to prospective attacks where an adversary knows in advance they will produce a high-score side chain (allowing targeted double-spending). Merged Bitcoin, relying on Poisson arrival times for block discovery, prevents adversaries from knowing in advance if they will produce a block, thereby mitigating this attack vector.

5. Robustness to Asymmetric Advantages

The paper argues that Merged Bitcoin provides a partial remedy for asymmetric advantages, such as those from quantum attacks (Grover's algorithm) or hardware backdoors.

• Quantum/Backdoor Resistance: If an adversary gains an advantage in one hash type (e.g., via a specialized quantum circuit), they must simultaneously possess specialized circuits for all hash types to dominate the chain. This increases the complexity and cost of a successful attack exponentially with the number of hash types ($n$), assuming independence of attack probabilities.

4. Significance and Claims

The paper claims that Merged Bitcoin offers a rigorous method to increase the security threshold of Bitcoin-like protocols without relying on the "Big-And" impossibility result. Its significance lies in:

• Maximizing Attack Cost: Proving that the protocol can be tuned to make the cost of attack equal to the sum of attacking individual chains, which is the theoretical maximum for multi-hash protocols.
• Decentralization: Allowing personal computers (which may be efficient at non-SHA-256 hashes like Ethash) to viably participate, reducing reliance on specialized ASICs.
• Trust Aggregation: Enabling parties with different trust assumptions (e.g., a Bitcoin maximalist and an Ethereum maximalist) to agree on a single ledger, as the merged chain's security is derived from the aggregate honest power of all types.
• Theoretical Bounds: Providing the first closed-form bounds for the security region of a multi-hash Proof-of-Work protocol in a bounded delay network.

The authors acknowledge that while the "Big-And" security region is impossible for permissionless protocols, the proposed protocol achieves a comparable exponential decrease in error probability against power-limited adversaries (e.g., those limited by hardware backdoor risks) and successfully maximizes the economic cost of an attack. Future work is identified as analyzing the $k$-confirmation rule and exploring protocols that might achieve the "Big-And" region if adversary withholding capabilities are restricted.