OHIE: Blockchain Scaling Made Simple

Haifeng Yu; Ivica Nikolic; Ruomu Hou; Prateek Saxena

Source-linked AI summary

OHIE: Blockchain Scaling Made Simple

Haifeng Yu, Ivica Nikolic, Ruomu Hou, Prateek Saxena

arXiv:1811.12628v3Nov 30, 2018cs.DC

TL;DR

Existing blockchain protocols improve throughput but can become complex and difficult to prove secure. OHIE composes parallel Nakamoto consensus instances to retain simplicity while providing formal safety and liveness proofs. Its prototype experiments show linear bandwidth scaling, 4-10Mbps throughput, and at least about 20x better decentralization than prior works.

Problem
High-throughput blockchain protocols are becoming complex, making formal security proofs increasingly difficult while blockchain systems still need stronger throughput and decentralization.
Method
OHIE composes parallel Nakamoto consensus instances and uses a modular reduction to establish safety and liveness.
Results
4-10Mbps transaction throughput is achieved under 8-20Mbps per-node bandwidth, with throughput scaling linearly with available bandwidth and at least about 20x better decentralization than prior works.
Takeaways & Limitations
OHIE combines a simple implementation and modular safety and liveness proof with high throughput and improved decentralization.
Takeaways & Limitations
Increasing the number of parallel chains beyond a certain point causes a non-trivial increase in propagation delay when the network begins saturating its bandwidth.

Abstract

from arXiv · show

Many blockchain consensus protocols have been proposed recently to scale the throughput of a blockchain with available bandwidth. However, these protocols are becoming increasingly complex, making it more and more difficult to produce proofs of their security guarantees. We propose a novel permissionless blockchain protocol OHIE which explicitly aims for simplicity. OHIE composes as many parallel instances of Bitcoin's original (and simple) backbone protocol as needed to achieve excellent throughput. We formally prove the safety and liveness properties of OHIE. We demonstrate its performance with a prototype implementation and large-scale experiments with up to 50,000 nodes. In our experiments, OHIE achieves linear scaling with available bandwidth, providing about 4-10 Mbps transaction throughput (under 8-20 Mbps per-node available bandwidth configurations) and at least about 20x better decentralization over prior works.

I. INTRODUCTION

OHIE targets a permissionless blockchain protocol that combines Bitcoin-like simplicity and formal security proofs with high throughput and decentralization. It composes parallel Nakamoto consensus instances, and experiments show bandwidth-linear throughput at large scale.

Bitcoin and Ethereum process only about 5KB or 10 transactions per second on average, below 0.2% of average available P2P bandwidth.
Formal proofs are especially important because blockchain upgrades can trigger philosophical disagreements and financial impact.
Recent high-throughput protocols may retain Nakamoto consensus's simplicity yet lack formal end-to-end security proofs.
OHIE aims to tolerate adversarial computational power close to 1/2 and approach a significant fraction of raw network bandwidth.Raw bandwidth is only a crude upper bound because propagation and protocol overheads reduce attainable throughput.
OHIE composes many parallel Nakamoto consensus instances, evenly splits adversarial computational power across chains, and securely derives a global block order.
OHIE's modularity supports safety and liveness proofs by reduction to Nakamoto consensus, while parallel chains provide throughput scaling and simultaneous block production.
4-10Mbps transaction throughput is achieved under 8-20Mbps per-node bandwidth, with up to 50,000 nodes and throughput scaling linearly with available bandwidth.This corresponds to about 1000-2500 transactions per second under a 500-byte average transaction size.

III. CONCEPTUAL DESIGN

OHIE scales Nakamoto consensus by running k parallel chains while preserving per-chain behavior and binding each proof-of-work block to a verifiable chain. Its design uses hash-based chain assignment, Merkle-tree commitments, and parallel propagation to increase block production without immediately increasing propagation delay.

Parallel chains: OHIE runs k parallel Nakamoto-consensus instances, each with a distinct genesis block and chain identifier, while miners extend the chains concurrently.Within each instance, miners follow Nakamoto consensus’s longest-path rule.
Proof of work: The last log2 k hash bits assign a mined block to one of the k chains, while the preceding proof-of-work condition preserves the target mining probability.Under the random-oracle assumption, the hash portions used for chain assignment and proof of work can be selected appropriately.
Proof of work: For a fixed chain, each hash operation generates a block with probability p, preserving the same block interval as Nakamoto consensus.The construction chooses the OHIE proof-of-work difficulty so valid blocks require log2 1/p leading-zero bits.
Security reasoning: Each OHIE chain approximately follows the distribution of a single Nakamoto chain, although chains remain correlated because every block is assigned to exactly one chain.The paper states that Lemma 3 formalizes this behavior while bounding the probability of bad events.
Throughput: With k parallel chains, OHIE expects k blocks across all chains every c·δ time, and experiments report minimal propagation-delay impact until network bandwidth saturates.This motivates choosing k as large as the available bandwidth permits.
Chain binding: A Merkle tree commits the miner’s local last block from every chain, allowing honest nodes to verify that the assigned block extends the selected chain.The chain index encoded by the mined block selects the corresponding Merkle leaf; blocks whose selected leaf does not match are rejected.
Confirmation: Confirmations are tracked along each chain: under T = 2, chains 0, 1, and 2 contain 2, 6, and 2 partially-confirmed blocks, while only chain 1’s first 2 blocks are fully confirmed.The figure illustrates the confirm-bar state rather than introducing a different consensus rule.

C. Ordering Blocks across Chains – A Starting Point

OHIE orders partially-confirmed blocks from parallel chains by assigning rank metadata that keeps chains balanced and supports a safe global order. Its implementation combines this ordering with Nakamoto-style chain structures and protocol processing.

Starting point: Blocks after the confirmation bar cannot yet enter the total order, and chain imbalance can grow unbounded over time.The confirmation bar is limited by the chain with the fewest partially-confirmed blocks.
Ordering mechanism: Each block carries a (rank, next rank) tuple, and fully-confirmed blocks are ordered by increasing rank with chain-id tie-breaking.A newly generated block can represent multiple blocks’ worth of progress on the shortest chain.
Rank assignment: A new block sets its next rank to at least the maximum expected next rank across chains, ensuring its chain catches up in rank.The next rank must also exceed the block’s own rank, so ranks increase along each chain.
Rank assignment: Using a next rank larger than the current maximum is allowed because other chains can catch up when subsequent honest blocks are added.OHIE does not require all chains to have exactly equal lengths at every moment.
Global ordering: The confirmation bar is the minimum next rank among chains, so blocks with smaller ranks can be safely marked fully-confirmed and added to the SCB.At the Figure 2 example’s time t4, the confirmation bar is 5 and 9 partially-confirmed blocks become fully-confirmed.
Implementation: OHIE uses k parallel chains with Nakamoto-style parameters and processes messages, proof-of-work attempts, and blocks through a Nakamoto-like main loop.Nodes maintain one block tree per chain, with all but the last T blocks on the longest path treated as partially-confirmed.

V. SECURITY GUARANTEES OF OHIE

OHIE’s security analysis covers all possible adversarial strategies. The section therefore states an unrestricted adversary scope for its analysis.

The security analysis holds under all possible strategies of the adversary.
OHIE’s adversary model does not restrict the strategies considered by the security analysis.
The stated security result applies across the full set of adversarial strategies considered by the model.

A. Overview of Guarantees

Theorem 1 establishes growth, quality, consistency, and quality-growth guarantees for OHIE’s parallel chains and final SCB, with explicit probability bounds. These guarantees transfer Nakamoto-style properties across chains while supporting increased honest-block incorporation.

Theorem 1: With probability at least 1 − k · exp(−Ω(λ)) − k · exp(−Ω(T)), OHIE satisfies its four stated properties across k chains.The theorem applies for constant f < 1/2, suitable p, and k ≥ 1.
Growth: Each of the k chains grows by at least T blocks every 2T ticks on any honest node.
Quality: Every T consecutive blocks on each chain contain at least 1−f T honest blocks.
Consistency: The SCB views of any two honest nodes are prefix-consistent, and later views extend earlier ones after the stated timing conditions.
Quality-growth: After the initial 2Tpn ticks, every (γ+2)·2Tpn interval adds at least γ·k·y honest blocks to the SCB.

C. Proof for Theorem 1

The proof reduces each OHIE chain to a Nakamoto-consensus execution, transfers the established chain properties, and then derives consistency and quality-growth for the SCB. A lemma connects properties holding on every component chain to the final total order.

Reduction: The proof constructs, for each OHIE chain, a Nakamoto adversary whose execution is strongly statistically close after mapping blocks.This reduction lets existing Nakamoto properties carry over to each individual OHIE chain.
From chains to SCB: The proof then conditions on the Nakamoto properties holding for every component chain and analyzes rank and next-rank values to establish SCB properties.
Reduction: The reduction uses a simulated OHIE execution coupled with a real Nakamoto execution, with complete proof details deferred to Appendices B through D.
From chains to SCB: If the three Nakamoto properties hold for all k chains, the SCB satisfies consistency and quality-growth with probability at least 1 − exp(−Ω(λ)).
Final proof: Applying the chain-level theorem to all k chains and Lemma 4 completes the proof of Theorem 1.

D. Discussion and Comparison

OHIE derives its guarantees modularly from Nakamoto consensus while scaling quality-growth across parallel chains. The resulting throughput benefit is approximately proportional to the number of chains, subject to bandwidth limits.

Comparison with prior results: OHIE can directly reuse alternative Nakamoto-consensus analyses, preserving their c, growth-rate x, and quality-rate y guarantees.Its proof treats (p, λ, T)-Nakamoto guarantees as a black box.
Theorem guarantees: Each of OHIE’s k chains grows by at least T blocks every x ticks, while every T consecutive blocks contain at least y honest blocks.These are the growth and quality properties inherited by the parallel chains.
Theorem guarantees: After the first x ticks, every honest node adds at least γ·k·y honest blocks to the SCB within (γ + 2)·x + 2∆ ticks.This quality-growth property applies for every integer γ ≥ 1.
Comparison with prior results: OHIE’s long-term SCB quality-growth rate is about k times the corresponding prior Nakamoto result, explaining its k-fold throughput increase.The comparison treats the 2∆ term as dominated by (γ + 2)·x.
Confirmation latency: Θ((log 1/ϵ + log k)∆) ticks gives OHIE’s confirmation latency, usually Θ(∆log 1/ϵ) in practical settings.This latency is reported as the same as in the cited Nakamoto analyses.
Comparison with prior results: Increasing k beyond a certain point raises ∆ non-trivially when the system begins saturating network bandwidth.Thus the number of parallel chains cannot grow without bound.

VI. EXPERIMENTAL EVALUATION

The evaluation measures OHIE’s propagation behavior under varying bandwidth and parallelism. Parallel propagation uses substantial bandwidth without substantially increasing BPD, supporting bandwidth-oriented scaling.

Methodology: OHIE’s prototype uses EC2 experiments with up to 50,000 nodes, 8–20 Mbps per-node bandwidth, and results averaged over five stabilized runs.Nodes connect to eight randomly selected peers.
Block propagation: 1.7–1.9 seconds is the BPD for 20 KB blocks across 8–20 Mbps configurations.Similar values were observed for block sizes from 10 KB to 64 KB.
Block propagation: 3.2 seconds is the BPD for 10–20 KB blocks even in macro experiments with 50,000 nodes.The passage attributes this behavior to random-graph connectivity and average hop counts.
Parallel propagation: Under 20 Mbps raw bandwidth, 60 parallel blocks per second cause no substantial BPD increase.The experiment uses 20 KB blocks and varies the number of parallel propagations.
Parallel propagation: About 50% of raw bandwidth can be used for parallel block propagation without significant negative BPD impact across the tested configurations.This finding supports using parallel chains to approach a significant fraction of raw network bandwidth.

C. End-to-end Performance of OHIE

End-to-end experiments evaluate throughput, decentralization, and confirmation latency under varying bandwidth. OHIE scales throughput and decentralization with bandwidth while maintaining stable confirmation latency across configurations.

Experimental setup: OHIE evaluates end-to-end throughput, decentralization factor, and confirmation latency with 12,000 nodes by default and additional 50,000-node experiments.The 50,000-node results are within 1% of corresponding 12,000-node results.
Experimental setup: OHIE assigns k according to available bandwidth so that k × block size/block interval ≈ 0.5 × available bandwidth.For 8, 12, 16, and 20 Mbps, the experiments use k = 250, 370, 500, and 620.
Throughput and decentralization: OHIE’s throughput scales roughly linearly with available bandwidth and reaches about 50% of available bandwidth.The experiments use 20 KB blocks with a 10-second interval on each chain.
Throughput and decentralization: 61.8 is OHIE’s decentralization factor under 20 Mbps, at least about 20× higher than prior permissionless protocols’ reported results.OmniLedger is cited as the prior best comparison at about 3.1.
Confirmation latency: 1–5 minutes are needed for partial confirmation and another 2–4 minutes for full confirmation under 20 Mbps.The reported references are 60 minutes for Bitcoin and 3 minutes for Ethereum.
Confirmation latency: Confirmation latencies remain stable from 8 to 20 Mbps with T = 30, so latency does not deteriorate as OHIE throughput increases.The stability result covers both partial and full confirmation.

A. Proof for Lemma 4

The proof establishes OHIE consistency and quality growth by first ruling out conflicting attachments, then lifting per-chain properties to the global SCB.

Consistency: With probability at least 1 −exp(−Ω(λ)), honest nodes never accept different attachments for the same block.The proof excludes hash collisions and successful verification of previously unseen hash inputs except with exponentially small probability.
Consistency: Identical blocks accepted by honest nodes have identical hash, leaf, leaf proof, rank, and next rank fields.The argument traces Merkle proofs to a unique leaf and uses induction over the attachment dependencies for rank fields.
Consistency: The consistency property requires every block’s attachment values to be the same on all honest nodes.This lets the proof reason about a block’s rank and next rank without node-specific values.
Consistency: Any two honest-node SCBs are prefix-comparable, and later views extend earlier views under the stated timing conditions.The proof compares partially confirmed blocks chain by chain and shows that newly added blocks follow the shared prefix.
Quality growth: With probability at least 1−exp(−Ω(λ)), OHIE satisfies the quality-growth property when each chain satisfies Theorem 2’s three properties.This is stated as Lemma 7, alongside the analogous consistency guarantee in Lemma 6.

B. Additional Formalism for the Proof of Lemma 3

This section formalizes OHIE’s random-oracle and network model and specifies the Nakamoto consensus protocol used in the reduction for Lemma 3.

Random-oracle model: OHIE models proof-of-work with random oracle H1, separating costly computation from free verification.H1.compute() represents mining effort, while H1.verify() captures inexpensive checking.
Block verification: Each block carries its hash value so receivers can verify proof-of-work without recomputing it.The attachment stores f(B), enabling verification through H1.verify() rather than H1.compute().
Random-oracle model: A separate random oracle H2 constructs and verifies OHIE’s Merkle trees, independently of the proof-of-work oracle H1.The two-oracle abstraction can still be implemented using one random oracle without changing the implementation.
Mining condition: Valid OHIE blocks require log2(1/(kp)) leading zeroes and log2 k trailing zeroes in their hashes.This replaces Nakamoto’s usual leading-zero condition while preserving the intended mining probability.
Nakamoto specification: Figure 6 specifies Nakamoto consensus with repeated state reception, mining, and state transmission.The specification follows the cited Nakamoto-consensus formulation and attaches each block’s hash for free verification.
Network model: The network model lets an adversary control message delays arbitrarily subject to the bound ∆ and observe messages when sent.Honest nodes communicate through the adversary in the formal model.

C. Overview of Proof for Lemma 3

The proof overview reduces one OHIE chain to Nakamoto consensus by simulating OHIE through a middlebox, after excluding low-probability oracle failures.

Proof strategy: The proof first removes hash collisions and successful verification of unseen inputs, changing the execution distribution by only an exponentially small amount.The cleanup applies analogous modifications to H1 and H2 interfaces.
Reduction: For any OHIE adversary A, the proof constructs a Nakamoto adversary A′ whose execution simulates OHIE through a middlebox.The middlebox simulates OHIE honest nodes while invoking A as a black box.
Simulation: When Nakamoto mines a block, the middlebox returns the corresponding OHIE proof-of-work result and assigns the OHIE block to chain 0.When Nakamoto fails to mine, it returns a random value conditioned on failing OHIE’s leading- and trailing-zero tests.
Simulation: The middlebox forwards adversarial messages between executions and tunnels adversarial H1.compute() queries to Nakamoto’s oracle.H1.verify(), H2.compute(), and H2.verify() queries are answered from the middlebox’s internal tables.

D. Proof for Lemma 3

The detailed proof uses hybrid executions and bookkeeping tables to show that OHIE’s simulated chain is statistically close to, and then equivalent with, Nakamoto consensus.

Hybrid construction: Hybrid2 answers oracle queries through tables T1, T2, and T3, preserving prior mappings and preventing collisions.H1 mappings connect OHIE blocks to Nakamoto blocks, while H2 mappings handle Merkle-tree values.
Hybrid argument: Hybrid1 and Hybrid2 are strongly statistically close when the relevant bad events do not occur.The four oracle interfaces have the same joint return-value distribution under this conditioning.
Bad-event bounds: The collision event involving table T3 occurs with probability exp(−Ω(λ)).Each newly created Nakamoto block receives a fresh random nonce, and the execution length is polynomial in λ.
Correspondence: Hybrid3 is an execution of Nakamoto consensus against adversary A′, with OHIE and Nakamoto blocks linked by a one-to-one mapping.The mapping preserves block acceptance and predecessor relationships between the executions.
Correspondence: An honest simulated OHIE node adds a mapped block if and only if the corresponding honest Nakamoto node adds its block.Honesty status is preserved under the mapping.
Conclusion: Combining the hybrid closeness and correspondence yields Hybrid3 = EXEC(Nakamoto, p, λ, T, A′).This completes the reduction used to prove Lemma 3.

E. Security Properties of Conflux

The simulation shows Conflux’s security properties deteriorate as throughput increases, while the authors discuss fixes involving lower throughput or explicitly separated chains.

Scope: The balance-attack results are simulation-based and may change under parameters different from those used in Conflux’s paper.The authors also state that the attack itself is folklore and is not presented as a contribution of this section.
Possible fixes: A proposed fix is to operate Conflux closer to GHOST’s relatively low-throughput parameter range, while another explicitly separates computation across multiple chains.The authors state that the low-throughput fix is effective in their simulation and identify multi-chain designs as another solution.
Balance attack: The balance attack maintains two growing forks by dividing honest nodes into two groups and extending separate branches.The adversary generates blocks on both branches while honest nodes in each group extend its assigned fork.
Balance attack: The attack is effective in Conflux because its high throughput comes from generating many blocks per round despite slower block propagation.One cited setting generates a 4MB block every 5 seconds, while propagation takes about 100 seconds, yielding roughly 20 blocks per round.
Simulation results: With 20 blocks per round, Conflux tolerates f less than 0.2 when the target fork length is no more than 15.The simulation considers the top 0.01% of fork lengths, matching Conflux’s stated risk tolerance.
Simulation results: With 200 blocks per round, Conflux tolerates f less than 0.1 under the same target fork length.The tolerated malicious fraction decreases as the number of blocks per round increases.