Source-linked AI summary
Bitcoin-NG: A Scalable Blockchain Protocol
Ittay Eyal, Adem Efe Gencer, Emin Gun Sirer, Robbert van Renesse
TL;DR
Bitcoin-derived blockchains face scalability limits because throughput and latency depend on block size and interval, constraining applications such as payments and smart contracts. The paper presents Bitcoin-NG, which separates leader election from transaction serialization, introduces evaluation metrics, and tests the protocol against Bitcoin. It reports that Bitcoin-NG can scale until network propagation limits latency and individual-node processing limits throughput, while retaining Bitcoin’s trust assumptions.
Problem
Bitcoin-derived blockchain protocols trade off throughput against latency, limiting their potential for payments, remittances, digital assets, and smart contracts.
Method
Bitcoin-NG separates infrequent random leader election from transaction serialization and is evaluated with quantitative consensus metrics and large-scale unchanged-client experiments.
Results
Bitcoin-NG achieves higher throughput and lower latency than Bitcoin while maintaining Bitcoin’s trust assumptions and security properties.
Takeaways & Limitations
Bitcoin-NG scales until network diameter limits consensus latency and individual-node processing power becomes the throughput bottleneck.
Takeaways & Limitations
Under optimal zero-latency network assumptions, Bitcoin’s blockchain is more resilient than Bitcoin-NG.
Abstract
from arXiv · showhide
Cryptocurrencies, based on and led by Bitcoin, have shown promise as infrastructure for pseudonymous online payments, cheap remittance, trustless digital asset exchange, and smart contracts. However, Bitcoin-derived blockchain protocols have inherent scalability limits that trade-off between throughput and latency and withhold the realization of this potential. This paper presents Bitcoin-NG, a new blockchain protocol designed to scale. Based on Bitcoin's blockchain protocol, Bitcoin-NG is Byzantine fault tolerant, is robust to extreme churn, and shares the same trust model obviating qualitative changes to the ecosystem. In addition to Bitcoin-NG, we introduce several novel metrics of interest in quantifying the security and efficiency of Bitcoin-like blockchain protocols. We implement Bitcoin-NG and perform large-scale experiments at 15% the size of the operational Bitcoin system, using unchanged clients of both protocols. These experiments demonstrate that Bitcoin-NG scales optimally, with bandwidth limited only by the capacity of the individual nodes and latency limited only by the propagation time of the network.
1 Introduction
Bitcoin-derived blockchains promise broad digital-payment and contract infrastructure, but their parameters impose a throughput–latency trade-off. Bitcoin-NG separates leader election from transaction serialization to improve scalability while retaining Bitcoin’s trust model and security properties.
- Motivation: Cryptocurrencies support pseudonymous payments, remittances, digital-asset exchange, and programmable agreements through blockchain-based decentralized consensus.The paper describes blockchain technology as an open, Byzantine fault-tolerant transaction mechanism for these applications.
- Bitcoin-NG: Bitcoin-NG decouples leader election from transaction serialization by assigning each epoch a single leader who serializes transactions until the next leader is chosen.Leader election remains random and infrequent, while transaction serialization proceeds unilaterally within the epoch.
- Bitcoin-NG: Bitcoin-NG maintains Bitcoin’s security properties while using forward-looking leader election to continually process transactions instead of freezing between elections.The paper contrasts this with Bitcoin, where the elected leader serializes history and the system can remain frozen between leader elections.
- Evaluation: The paper introduces metrics covering protocol goodput, latency, consensus maintenance, and resistance to centralization.These metrics provide a quantitative basis for evaluating and comparing Nakamoto-consensus implementations.
- Evaluation: Large-scale experiments with 1000 nodes compare unchanged Bitcoin-NG and Bitcoin clients under realistic Internet latencies and quantify Bitcoin’s throughput–latency trade-offs.The testbed represented over 15% of the operational Bitcoin network.
2 Model and Goal
The model uses authenticated peer-to-peer nodes, random-oracle randomness, cryptographic puzzles, and proof of work under a bounded Byzantine adversary. Its goal is to evaluate replicated-state-machine consensus through termination, agreement, and validity properties.
- System model: Nodes communicate over a reliable authenticated peer-to-peer network and may query a random oracle, while no trusted public-key infrastructure is assumed.Nodes can generate key pairs independently.
- System model: The puzzle system uses a hash condition to produce proof of work, with mining power measured by the number of potential solutions a node can try per second.A valid solution statistically indicates the computational work performed.
- Adversary: Byzantine nodes may behave arbitrarily, but their mining power remains below one-quarter of total compute power at any time.This bound reflects the stated vulnerability of proof-of-work blockchains to selfish mining by attackers larger than 1/4 of the network.
- Consensus goals: The nodes implement a replicated state machine whose properties are compared with classical consensus through termination, agreement, and validity.These properties formalize eventual consistency, convergence among nodes, and limits on transitions not originating from honest inputs.
3 Bitcoin and its Blockchain Protocol
Bitcoin serializes transactions in a proof-of-work blockchain maintained by miners, with balances represented as a replicated state machine. Forks are resolved by the heaviest chain, while branches outside it are pruned and their transactions ignored unless later adopted.
- Bitcoin state: Bitcoin’s replicated state machine maintains user balances, and miners manage transitions representing transactions that move funds between addresses.Transactions are cryptographically protected so only the rightful address owner can transfer funds.
- Blocks and mining: Each valid block links to its predecessor, contains a proof-of-work solution and transaction Merkle root, and rewards its miner with a coinbase transaction.This structure records transactions as an ordered blockchain.
- Blocks and mining: Mining rewards combine user-paid per-transaction fees with newly created Bitcoins.The reward compensates miners for producing blocks.
- Forks: Concurrent valid blocks with the same predecessor create forked branches, and miners may continue extending any branch they know.Forks form a tree of alternative chain histories.
- Fork resolution: Bitcoin resolves forks by directing miners to the heaviest known chain, which represents the serialized replicated-state-machine inputs.Random tie-breaking is used when chains have equal weight.
- Fork resolution: Blocks and branches outside the main chain are pruned, so their transactions are ignored unless later included without contradiction.A pruned transaction can be adopted later unless a conflicting spend has already entered the main chain.
- Fork frequency: Because block dissemination takes seconds but mining intervals average ten minutes, accidental bifurcation occurs approximately once every 60 blocks.The disparity between propagation and mining times makes ordinary forks relatively infrequent.
4 Bitcoin-NG
Bitcoin-NG separates leader election from transaction serialization using key blocks and frequent microblocks, improving latency and bandwidth while preserving Bitcoin’s trust model and incentive structure.
- Bitcoin-NG serializes transactions with better latency and bandwidth without sacrificing other properties.
- The protocol divides time into epochs, each with one leader, and uses key blocks for leader election and microblocks for ledger entries.Key blocks contain proof of work and a public key for subsequent microblocks.
- Key-block intervals remain exponentially distributed because miners solve Bitcoin-like cryptographic puzzles, while difficulty adjustment maintains a target average rate.
- Microblocks are signed by the latest key-block key, contain valid ledger entries, and do not affect chain weight because they lack proof of work.
- Frequent microblocks can create short forks during leader switches, but the new key block resolves them after propagation; users should wait that propagation time before confirmation.
- Transaction fees are split 40% to the current leader and 60% to the subsequent leader, with rewards paid through mature coinbase transactions.
- Microblocks enable double-spending attempts through conflicting states, while poison transactions invalidate fraudulent leaders’ revenue as a deterrent.
5 Security Analysis
Bitcoin-NG preserves Nakamoto-consensus properties under its stated assumptions while changing leader and transaction incentives. Its main security boundaries concern attacker power, fee manipulation, censorship, and rare but potentially long key-block forks.
- Incentives: Miners with less than 1/4 of total network capacity are incentivized to include transactions and extend the heaviest and longest chains.In Bitcoin-NG, extending the heaviest and longest chains are distinct behaviors.
- Consensus security: Bitcoin-NG maintains Nakamoto consensus termination, agreement, and validity under the corresponding Bitcoin assumptions.The protocol argues that heaviest-chain extension preserves termination and agreement, while selfish-mining resilience supports validity.
- Selfish mining: Bitcoin-NG is resilient to selfish mining by attackers controlling less than 1/4 of mining power, because microblocks carry no chain weight.Unweighted microblocks prevent attackers from gaining an advantage by secretly mining on unpublished microblocks.
- Network assumptions: Under an optimal zero-latency network, Bitcoin-NG is less resilient than Bitcoin because its security bounds provide no attacker-power intersection.The stated bounds are rleader > 45% and rleader < 40% for Bitcoin-NG, versus almost 1/3 security for Bitcoin.
- Fee manipulation: Users can bypass the 40–60% fee distribution by paying the current leader directly, though this gives no significant advantage under the paper’s incentive analysis.Doing so increases the current leader’s motivation but reduces future miners’ motivation to extend that microblock.
- Censorship resistance: A malicious leader can censor transactions only during its leadership epoch, after which the next leader ends its influence.The paper compares this effect with Bitcoin miners producing empty blocks.
- Censorship resistance: At least 3/4 honest mining power implies an average wait of 4/3 blocks, or 13.33 minutes, for a transaction to enter an honest miner’s block.Frequent microblocks do not improve censorship resistance, although key-block intervals can be adjusted.
- Forks: Key-block forks are infrequent but may last until the next key block, leaving branch-specific transactions uncertain until one branch leads.Unlike short microblock forks, these forks are not resolved immediately by the arriving key block.
6 Metrics
The paper introduces metrics for measuring agreement, chain finality, fairness, and proof-of-work efficiency in Nakamoto-consensus systems. These metrics quantify how quickly nodes converge, how long transitions remain uncertain, and how mining power is represented and used.
- Consensus delay: Consensus delay measures how far back nodes must look to find a common state-machine transition prefix.The ε-point consensus delay is the smallest Δ for which at least ε·|N| nodes agree on the prefix.
- Fairness: Fairness is the ratio between non-largest miners’ transition representation and their share of total mining power.A fairness value of 1.0 is optimal because transition representation matches mining-power representation.
- Mining efficiency: Mining power utilization is the ratio of mining power securing the system to total mining power.Power spent on work absent from the blockchain accounts for the difference.
- Finality metrics: Time to prune measures how long a node takes to learn that a previously observed transition was removed from history.Its δ-percentile indicates how long a user should wait for confidence that a transition occurred.
- Finality metrics: Time to win measures the δ-percentile gap between a transition becoming never-to-be-pruned and the last conflicting belief by another node.The metric is zero when the conflicting belief occurs earlier.
7 Experimental Setup
The evaluation uses a 1000-node emulated network, modified standard clients, simulated mining, and measured latency and mining-power distributions. The setup targets realistic Bitcoin-like propagation and controlled comparisons of consensus performance.
- Testbed: 1000-node experiments evaluate Bitcoin and Bitcoin-NG on an emulated network.The testbed is designed to approximate a substantial fraction of the operational Bitcoin network.
- Implementation: The Bitcoin baseline uses the standard client release 0.10.0 with minimal instrumentation.Bitcoin-NG is implemented by modifying the same client version.
- Implementation: Bitcoin-NG implementation omits fee distribution and microblock signature checking because the paper estimates negligible performance impact.Fee distribution requires about one fixed-point operation per transaction, while signature checking adds several milliseconds per microblock.
- Mining model: Mining is simulated with a scheduler that triggers block generation at exponentially distributed intervals.This replaces proof of work while preserving the approximate inter-arrival distribution used in the experiments.
- Mining-power model: Mining entities are modeled from weekly block-generation rankings, with unidentified blocks treated as separate miners.The analysis uses public mining data for the year ending August 31, 2015, and notes that about 9% of blocks were unidentified.
- Network model: The emulated network uses randomly connected nodes, measured Internet-latency histograms, and approximately 100 kbit/sec bandwidth per node pair.Each node connects to at least five uniformly selected peers.
- Validation: The setup validates propagation by varying block sizes while holding transaction-per-second load constant.Measured propagation time has a linear relation with block size, qualitatively matching operational Bitcoin measurements.
8 Evaluation
The evaluation compares Bitcoin-NG and Bitcoin across block frequency and block size, showing that Bitcoin’s performance improvements create security tradeoffs while Bitcoin-NG largely avoids them.
- Overall comparison: Bitcoin-NG qualitatively outperforms Bitcoin across the measured range, without comparable deterioration in security-related metrics.Bitcoin-NG maintains superior performance in almost all metrics while avoiding the security degradation observed in Bitcoin.
- Block frequency: Increasing Bitcoin’s block frequency reduces consensus latency but increases forks, consensus latency, and time to prune relative to Bitcoin-NG.Key-block forks can require a branch to accumulate more key blocks before resolution.
- Block frequency: Bitcoin’s mining power utilization drops toward 1/4 as block frequency increases, accompanied by deteriorating fairness.At high frequencies, the largest miner tends to generate the main-chain blocks while other miners catch up.
- Block frequency: Bitcoin-NG’s rare key-block contention allows frequent microblocks to reduce consensus delay and time to prune while leaving other metrics at optimal levels.The protocol confines contention to key-block generation, so higher microblock frequencies do not produce comparable fork effects.
- Block size: Larger blocks increase transaction frequency but also increase consensus latency, time to win, and time to prune because propagation takes longer and forks become more likely.The resulting bandwidth–latency tradeoff is accompanied by significant mining-power loss and reduced fairness in Bitcoin.
- Block size: At high bandwidth, Bitcoin-NG clients approach their processing capacity, causing degradation in consensus latency and time to prune.This is a capacity boundary rather than the security degradation observed for Bitcoin.
9 Related Work
Related work addresses blockchain scalability through client improvements, centralized relays, off-chain systems, side chains, alternative chain structures, and consensus analyses. Bitcoin-NG instead removes the dependency between fork rate and block size or rate while retaining favorable fairness and mining-power properties.
- Alternative consensus protocols: GHOST uses subtree work in its chain-selection rule, whereas Bitcoin-NG maintains low fork rates at high bandwidth and throughput for better fairness and mining-power utilization.A practical GHOST implementation that propagates all blocks incurred overhead that outweighed the chain-selection benefit in the reported evaluation.
- Alternative blockchain structures: Inclusive blockchains improve fairness and mining-power utilization through a directed acyclic graph, but combining them with Bitcoin-NG may enable denial-of-service and double-spending attacks.The risk arises because decommissioned leaders could retroactively introduce transactions for inclusion by the current leader.
- Faster Bitcoin: Client efficiency improvements reduce propagation time and the collision window, but their benefit scales proportionally with processing-speed improvements.A processing-speed increase of x% permits only an x% block-size increase at the same fork rate.
- Bitcoin-NG: Bitcoin-NG provides a qualitative improvement beyond client optimization by removing fork-rate dependence on block size or transaction rate.The paper contrasts this with faster clients, whose improvement remains limited by the same fork relationship.
- Alternative performance approaches: Centralized fast relays improve throughput and latency but increase centralized control and reduce fairness for miners outside the relay.The relay gives participating miners an advantage over miners using the standard peer-to-peer network.
- Off-chain solutions: Off-chain solutions do not address scaling a Nakamoto-consensus replicated state machine because transactions may be lost when channel participants fail.The cited failure case concerns transactions that were never stored in the blockchain.
- Side chains: Side chains shard workload across separate chains, but they do not improve efficiency when transactions cannot be partitioned.Each shard can use Bitcoin-NG, but the benefit depends on feasible workload sharding.
10 Conclusion
The paper frames Bitcoin’s scalability limits as a perceived tradeoff between performance and security, then concludes that Bitcoin-NG can reach network- and node-capacity bottlenecks instead.
- Motivation: Bitcoin and related cryptocurrencies have reached scalability limits, while debate has been hampered by a perceived tradeoff between performance metrics and security goals.The paper describes the resulting discussion as favoring short-term, incremental compromise solutions.
- Conclusion: Bitcoin-NG scales so that network diameter limits consensus latency and individual-node processing power limits throughput.The conclusion presents this as the demonstrated scalability point of the protocol.
B Competition on a Key-Block Fork
A competing key-block fork creates strategic competition between leaders because each can offer fees to the subsequent miner.
- Competition on a Key-Block Fork: On a competing key-block fork, each leader can publish transactions offering a large fee to the subsequent miner to induce branch selection.The paper notes that this competition may introduce dynamics beyond the scope of the work, while branches may copy transactions placed in the competing branch.