pBitcoin-NG A Scalable Blockchain ProtocolIttay Eyal Adem Efe Gencer Emin G un Sirer Robbert van RenesseCornell UniversityAbstractCryptocurrencies, based on and led by Bitcoin, have shown promise as infrastructure forpseudonymous online payments, cheap remittance, trustless digital asset exchange, and smartcontracts. However, Bitcoin-derived blockchain protocols have inherent scalability limits thattrade-o between throughput and latency and withhold the realization of this potential.This paper presents Bitcoin-NG, a new blockchain protocol designed to scale. Based onBitcoin’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 thesecurity and e ciency of Bitcoin-like blockchain protocols. We implement Bitcoin-NG and per- large-scale experiments at 15 the size of the operational Bitcoin system, using unchangedclients of both protocols. These experiments demonstrate that Bitcoin-NG scales optimally, withbandwidth limited only by the capacity of the individual nodes and latency limited only by thepropagation time of the network.1 IntroductionBitcoin has emerged as the nbsp;rst widely-deployed, decentralized global currency, and sparkedhundreds of copycat currencies. Overall, cryptocurrencies have garnered much attention fromthe nbsp;nancial and tech sectors, as well as academics, achieved wide market penetration in un-derground economies [32], reached a 12B market cap and attracted close to 1B in venturecapital [13]. The core technological innovation powering these systems is the Nakamoto con-sensus protocol for maintaining a distributed ledger known as the blockchain. The blockchaintechnology provides a decentralized, open, Byzantine fault-tolerant transaction mechanism, andpromises to become the infrastructure for a new generation of Internet interaction, includinganonymous online payments [12], remittance, and transaction of digital assets [14]. Ongoingwork explores smart digital contracts, enabling anonymous parties to programmatically enforcecomplex agreements [26, 49].Despite its potential, blockchain protocols face a signi cant scalability barrier [45, 30, 17, 4].The maximum rate at which these systems can process transactions is capped by the choiceof two parameters block size and block interval. Increasing block size improves throughput,but the resulting bigger blocks take longer to propagate in the network. Reducing the blockinterval reduces latency, but leads to instability where the system is in disagreement and theblockchain is subject to reorganization. To improve e ciency, one has to trade o throughputfor latency. Bitcoin currently targets a conservative 10 minutes between blocks, yielding 10minute expected latencies for transactions to be encoded in the blockchain.1 The block sizeis currently set at 1MB, yielding only 1 to 3.5 transactions per second for Bitcoin for typical1On average, assuming no backlog, both block interval and the average time to wait for a block starting at anytime are ten minutes. This is a non-intuitive property of the memoryless exponential distribution.1transaction sizes. Proposals for increasing the block size are the topic of heated debate withinthe Bitcoin community [41].In this paper, we present Bitcoin-NG, a scalable blockchain protocol, based on the same trustmodel as Bitcoin. Bitcoin-NG’s latency is limited only by the propagation delay of the network,and its bandwidth is limited only by the processing capacity of the individual nodes. Bitcoin-NGachieves this perance improvement by decoupling Bitcoin’s blockchain operation into twoplanes leader election and transaction serialization. It divides time into epochs, where eachepoch has a single leader. As in Bitcoin, leader election is pered randomly and infrequently.Once a leader is chosen, it is entitled to serialize transactions unilaterally until a new leader ischosen, marking the end of the er’s epoch.While this approach is a signi cant departure from Bitcoin’s operation, Bitcoin-NG main-tains Bitcoin’s security properties. Implicitly, leader election is already taking place in Bitcoin.But in Bitcoin, the leader is in charge of serializing history, making the entire duration of timebetween leader elections a long system freeze. In contrast, leader election in Bitcoin-NG isforward-looking, and ensures that the system is able to continually process transactions.uating the perance and functionality of new consensus protocols is a challengingtask. To help per this quantitatively and provide a foundation for the comparison ofalternative consensus protocols, we introduce several metrics to uate implementations of theNakamoto consensus. These metrics capture perance metrics such as protocol goodput andlatency, as well as various aspects of its security, including its ability to maintain consensus andresist centralization.We uated the perance of Bitcoin-NG on a large emulation testbed consisting of 1000nodes, amounting to over 15 of the current operational Bitcoin network [35]. This testbedenables us to run unchanged clients, using realistic Internet latencies. We compare Bitcoin-NGwith the original Bitcoin client, and demonstrate the critical tradeo s inherent in the originalBitcoin protocol. Controlling for network bandwidth, reducing Bitcoin’s latency by decreasingthe block interval and improving its throughput by increasing the block size both yield adversee ects. In particular, fairness su ers, giving large miners an advantage over small miners.This anomaly leads to centralization, where the mining power tends to be used under a singlecontroller, breaking the basic premise of the decentralized cryptocurrency vision. Additionally,mining power is lost, making the system more vulnerable to attacks. In contrast, Bitcoin-NGimproves latency and throughput to the maximum allowed by network conditions and nodeprocessing limits, while avoiding the fairness and mining power utilization problems.In summary, this paper makes three contributions. First, it outlines the Bitcoin-NG scal-able blockchain protocol, which achieves signi cantly higher throughput and lower latency thanBitcoin while maintaining the Bitcoin trust assumptions. Second, it introduces quantitativemetrics for uating Nakamoto consensus protocols. These metrics are designed to ground theongoing discussion over parameter selection in Bitcoin-derived currency. Finally, it quanti es,through large-scale experiments, Bitcoin-NG’s robustness and scalability.2 Model and GoalThe system is comprised of a set of nodesN connected by a reliable authenticated peer-to-peernetwork. Each node can poll a random oracle [5] as a random bit source. Nodes can generatekey-pairs, but there is no trusted public key infrastructure.The system employs an associated puzzle system, de ned by a cryptographic hash func-tion H. The solution to a puzzle de ned by the string y is a string x such that Hyjx |the hash of the concatenation of the two | is smaller than some target. Each node i has alimited amount of compute power, called mining power, measured by the number of potentialpuzzle solutions it can try per second. A solution to a puzzle constitutes a proof of work, as itstatistically indicates the amount of work a node had to per in order to nbsp;nd it.At any time t, a subset of nodes Bt N are Byzantine and behave arbitrarily, controlledby a single adversary. The other nodes are honest | they abide by the protocol. The miningpower of each node i is mi. The mining power of the Byzantine nodes is less than 1/4 of thetotal compute power at any given time8t Xb2Btmb t nbsp;quot; a node returnstwo di erent states for the machine at time t.Agreement There exists a time di erence function nbsp; such that, given a 0 nbsp;1 1 nbsp;1 nbsp; 2 . Assuming the power of an attacker is bounded by 14 of themining power, we obtain rleader gt; 37, hence rleader 40 is within range.Longest Chain Extension To increase his revenue from a transaction, a miner couldavoid the transaction’s microblock and mine on a previous block. Then he would place thetransaction in its own microblock and try mining the subsequent key block. His revenue in thiscase must be smaller than his revenue by mining on the transaction’s microblock as prescribedPlace inmicroblockz }| {rleader Mine nextkey blockz }| {100 rleader nbsp;45 and rleader lt; 40, leaving no intersection.Under such optimal network assumptions, Bitcoin’s blockchain is therefore more resilient thanBitcoin-NG.Bypassing Fee Distribution We note that a user can circumvent the 40 60 transactionfee distribution by paying no transaction fee, and instead paying the current leader directly,using the coinbase address of the leader’s key block. However, a user does not gain a signi cantadvantage by doing so. As we have seen above, paying only the current leader increases thedirect motivation of the current leader to place the transaction in a microblock, but reduces themotivation of future miners to mine on this microblock. Moreover, if the leader does not includethe transaction before the end of its epoch, subsequent leaders will have no motivation to placethe transaction.Other motives for fee manipulation such as paying a large fee to encourage miners to choosea certain branch after a fork apply to Bitcoin as well as Bitcoin-NG, and are outside the scopeof this work.5.2 Other concernsWallet Security The possibility of placing a poison transaction allows an attacker thatobtains a leader’s private key to revoke his revenue retroactively and earn a small amount.However, such an attacker is better o trying to steal the full leader’s revenue when it be-comes available, therefore the introduction of the poison transaction does not add a signi cantvulnerability.Censorship Resistance A central goal of Bitcoin is to prevent a malicious discriminatingminer from dropping a user’s transactions.First, we note that a leader’s absolute power is limited to his epoch of leadership. A maliciousleader can per a DoS attack by placing no transactions in microblocks. Similarly, a benignleader that crashes during his epoch of leadership will publish no microblocks. Their in uenceends once the next leader publishes his key block. The impact of such behaviors is thereforesimilar to that in Bitcoin, where nodes may mine empty blocks, but rarely do.Assuming an honest majority and no backlog, a user will have her transaction placed in therst block generated by an honest miner. At least 34 of the blocks are generated by honestminers, therefore the user will have to wait for 43 blocks on average, or 1333 minutes. Thefrequent microblocks of Bitcoin-NG do not improve censorship resistance. Key block intervalscan be set to a rate that would reduce censorship to the minimum allowed by the networkwithout incurring prohibitive deterioration of other metrics.Resilience to Mining Power Variation Following Bitcoin’s success, hundreds of alter-native currencies were created [50], most with Bitcoin’s exact blockchain structure, and manywith the same proof-of-work mechanism. To maintain a stable rate of blocks, di erent instancesof the Blockchain tune their proof of work di culty at di erent rates Bitcoin once every 2016blocks { about 2 weeks, Litecoin [31] every 2016 blocks produced at a higher rate { about3.5 days, and Ethereum [49] on every block { about 12 seconds. However, whichever adjust-ment rate is chosen, these protocols are all sensitive to sudden mining power drops. Such dropshappen when miners are incentivized to stop mining due to a drop in the currency’s exchangerate, or to mine for a di erent currency that becomes more pro table due to a change in miningdi culty or exchange rate of either currency. Such changes are especially problematic for smallalt-coins. When their value rises, they observe a rapid rise in mining power as miners nbsp;ockto reap easy revenues. Then, once the di culty rises, the miners move on to mine on morepro table alt-coins and the mining power of the er drops. Now, since the di culty is high,the remaining miners will need a longer time to generate the next block, potentially orders ofmagnitude longer.In Bitcoin-NG, di culty adjustments can create a similar problem, however it only a ectskey blocks. Microblocks are generated at the same constant rate. As a consequence, in case ofa sudden mining power drop, Bitcoin-NG’s censorship resistance is reduced, as key blocks aregenerated infrequently. If a malicious miner becomes leader, it will generate microblocks untilan honest leader nbsp;nds a key block. Nevertheless, transaction processing continues at the samerate, in microblocks. Additionally, even until the di culty is tuned to a correct value, the ratioof time during which malicious miners are leaders remains proportional to their mining power.Forks When issuing microblocks at a high frequency, Bitcoin-NG observes a fork almost onevery key block generation, as the previous leader keeps generating microblocks until it receivesthe key block Figure 2. These forks are resolved quickly | once the new key block arrives at anode, it switches to the new leader. In comparison, when running Bitcoin at such high frequency,forks are only resolved by the heaviest chain extension rule, and since di erent miners may mineon di erent branches, branches remain extant for a longer time compared to Bitcoin-NG.Figure 3 Key block fork. Blocks 2 and 3’ have the same chain weight, and the fork is not resolveduntil key block 7 is generated.Figure 4 Point-consensus delay example with three Bitcoin nodes a, b, and c that generate blocksat heights 1, 2, and 3 explosions and learn that these blocks are in the main chain clouds.Intervals nbsp;1 and nbsp;2 are the 23-point consensus delays at times t1 and t2, respectively.However, Bitcoin-NG may experience key block forks, where more than one key blocks isgenerated after the same pre x of key blocks, as shown in Figure 3. This rarely happens, dueto low frequency and quick propagation of the small key blocks. However, the duration of thefork in this case may be very long, because it is only resolved on the next key block generation.The result is therefore infrequent, but long, key block forks.Although such long forks are undesirable, they are not dangerous. The knowledge of thefork is propagated through the network, and once it reaches the nodes, they are aware of theundetermined state. All transactions that appear only on one branch are therefore uncertain,until one branch gains a lead.6 MetricsWe now detail the metrics we shall use to uate Bitcoin and Bitcoin-NG. These metrics aredesigned to uate the unique properties of the Nakamoto consensus.Consensus Delay Intuitively, consensus delay is the time it takes for a system to reachagreement. We start by de ning, for a speci c cutio/p