The Bitcoin Backbone ProtocolAnalysis and Applications Juan A. GarayYahoo Labsgarayyahoo-Aggelos KiayiasyUniversity of Athensaggelosdi.uoa.grNikos LeonardosyLIAFA, Universit Paris Diderot–Paris July 7, 2015AbstractBitcoin is the first and most popular decentralized cryptocurrency to date. In this work, weextract and analyze the core of the Bitcoin protocol, which we term the Bitcoin backbone, andprove two of its fundamental properties which we call common prefix and chain quality in thestatic setting where the number of players remains fixed. Our proofs hinge on appropriate andnovel assumptions on the “hashing power” of the adversary relative to network synchronicity;we show our results to be tight under high synchronization.Next, we propose and analyze applications that can be built “on top” of the backbone pro-tocol, specifically focusing on Byzantine agreement BA and on the notion of a public trans-action ledger. Regarding BA, we observe that Nakamoto’s suggestion falls short of solving it,and present a simple alternative which works assuming that the adversary’s hashing power isbounded by 13. The public transaction ledger captures the essence of Bitcoin’s operation asa cryptocurrency, in the sense that it guarantees the liveness and persistence of committedtransactions. Based on this notion we describe and analyze the Bitcoin system as well as amore elaborate BA protocol, proving them secure assuming high network synchronicity andthat the adversary’s hashing power is strictly less than 12, while the adversarial bound neededfor security decreases as the network desynchronizes.1 IntroductionBitcoin, introduced in [29], is a decentralized payment system that is based on maintaining a publictransaction ledger in a distributed manner. The ledger is maintained by anonymous participants“players” called miners, cuting a protocol that maintains and extends a distributed data struc-ture called the blockchain. The protocol requires from miners to solve a “proof of work” POW,aka “cryptographic puzzle” see, e.g., [16, 38, 4, 24], which essentially amounts to brute-forcing ahash inequality based on SHA-256, in order to generate new blocks for the blockchain. The blocksthat comprise the blockchain contain sets of transactions that are generated at will by owners ofbitcoins, who issue transactions that credit any entity of their choice who accepts payments in bit-coin. Payers broadcast transactions and miners include the transactions they receive into the blocksAn abridged version of this paper appears in Proc. Eurocrypt 2015.yResearch partly supported by ERC project CODAMODA.1they generate. Miners are rewarded for maintaining the blockchain by receiving bitcoins; it is inthis manner bitcoins are created and distributed among the miners who are the first recipients ofnewly minted bitcoins.An important concern in Bitcoin or any e-payment system for that matter is the prevention ofdouble-spending attacks. Specifically, in the context of Bitcoin, a double-spending attack can occurwhen the attacker initially credits an account, receives service or goods by the account holder, butthen manages to reorganize the transaction ledger so that the transaction that credits the accountholder is reverted. In this way, the attacker keeps her bitcoin while receiving services and thus sheis able to spend it again somewhere else.In [29], Nakamoto provides an initial set of arguments of why the Bitcoin system will preventdouble-spending attacks. Specifically, he argues that if a payee waits for the transaction that givesher credit to advance into the blockchain a number ofk blocks, then the probability that an attackercan build an alternative blockchain that “reorganizes” the public blockchain which contains thecredit transaction drops exponentially with k. Nakamoto argues this by modeling the attacker andthe set of honest players as two competing actors pering a random walk moving toward a singledirection with probabilistic steps. He demonstrates that the k blocks the payee waits are enough toensure a negligible in k probability of the attacker catching up with the honest players.Nevertheless, the above analysis can be easily seen to be oversimplified in particular, it does notaccount for the fact that in Bitcoin’s decentralized setting the attacker may attempt to introducedisagreement between the honest miners, thus splitting their hashing power on different POWinstances. Nakamoto himself appeared to recognize the relevance of agreement in the contextof Bitcoin, arguing in a forum post [30] that actually “Bitcoin’s basic concept” of building andexchanging a blockchain is capable of solving Byzantine agreement BA [36, 27] in the presenceof an actively malicious adversary.1 However a thorough analysis establishing the exact securityproperties of the Bitcoin system has yet to appear.Our results. In this paper we extract, ally describe, and analyze the core of the Bitcoinprotocol. We call this protocol the Bitcoin backbone, as we describe it in a way that is versatile andextensible and can be used to solve other problems as well not just the problem of maintaininga public transaction ledger. The Bitcoin backbone protocol is cuted by players that build ablockchain following the Bitcoin source code [31] and allows a set of players to maintain a blockchainin a distributed fashion. The protocol is parameterized by three external functions V ;I ;R which we call the validation predicate, the contribution function, and the chain readingfunction, respectively. At a high level, V determines the proper structure of the ination thatis stored into the blockchain, I specifies how the contents of the blocks are ed by the players,andR determines how a blockchain is supposed to be interpreted in the context of the application.Note that the structure, contents, and interpretation of the blockchain are not important for thedescription of the backbone protocol and are left to be specified by the three external functionsabove, which are application-specific we provide examples of these functions in Section 5.We analyze the Bitcoin backbone protocol in a static setting when the participants operate ina synchronous communication network more details below and in Section 2 in the presence ofan adversary that controls a subset of the players. We assume that the protocol is cuted by afixed number n of players; note, however, that this number is not necessarily known to the protocolparticipants. The players themselves cannot authenticate each other and therefore there is no way1In [30] Nakamoto refers to the problem as “Byzantine Generals,” which is often used to refer to the single-sourceversion of the problem. Note that since more than one general may propose a time to attack this in fact is the casewhere every party has an value, i.e., Byzantine agreement. In fact, in an anonymous setting such as Bitcoin’s,the single-source version is nonsensical. Note that in the cryptographic setting, the two problems are not equivalentin terms of the number of tolerated misbehaving parties t t for some 2 [1;1 that satisfies2 f 1 0, then the blockchains maintained by the honest players will possess a largecommon prefix. More specifically, if two honest parties “prune” i.e., cut off k blocks from theend of their local chains, the probability that the resulting pruned chains will not be mutualprefixes of each other drops exponentially in k see Definition 2 for the precise ulation.Provided that f is very close to 0 this enables us to choose very close to 1 and thus establishthe common prefix property as long as an honest majority of participants in the flat-modelsetting is guaranteed equivalently, when the adversary controls strictly less than 50 of thehashing power. On the other hand, when the network “desynchronizes” and f gets closer to 1,achieving a common prefix requires , where is the golden ratio, which in turn suggestsmuch stricter bounds on the adversarial behavior in fact, the upper bound on the adversaryfor our analysis approaches 0.The chain-quality property. We prove that if , for some 2 [1;1, then the ratioof blocks in the chain of any honest player that are contributed by honest players is at least1 1 . Again observe that if is close to 1, we obtain that the blockchain maintained by honestplayers is guaranteed to have few, but still some, blocks contributed by honest players; a higherwould be necessary to guarantee bigger percentages of blocks contributed by honest playersin the blockchain. We also observe that this result is basically tight, i.e., that the adversary iscapable of following a strategy that deviates from the strategy of honest players that enablesthe introduction of that many blocks in the blockchain, under a favorable for the adversaryassumption on the propagation of adversarial blocks in the network.While the above two security properties may seem rather abstract since they refer to propertiesof the data structure that is maintained distributively by the parties, we demonstrate that theyare in fact quite powerful and show that the Bitcoin backbone protocol armed with the above3Figure 1 An overview of the backbone protocol’s applications Nakamoto’s BA protocol nakBA, ourBA protocols 13BA and 12BA, and the public ledger protocol PL. All properties must be satisfiedwith overwhelming probability. In each box we state the name of the property as well as themaximum ratio of the adversarial hashing power that we can prove the protocol withstands basedon the corresponding backbone property. The value stands for a negligible quantity.properties can be used as a basis for solving other problems, including the problem of distributivelymaintaining a “robust” public transaction ledger. In Figure 1 we show how the two properties implythe properties of the applications that are explained below.Byzantine agreement for 13-bounded adversaries. As a first application, we show how a ran-domized BA protocol can be built on top of the Bitcoin backbone protocol more or less directly,and based solely on the POW assumption. We instantiate the V ;I ;R functions so thatparties blockchains and act according to the following rules each party i attempts to insertits own vi 2f0;1ginto the blockchain; a blockchain is valid only if blocks contain elementsin f0;1g; the protocol terminates when the blockchain has reached a sufficient length; and, theblockchain is read by the honest parties by pruning k elements from its end and returning the ma-jority bit appearing in the resulting blockchain’s prefix. We show how the common prefix propertyand the chain-quality property of the backbone protocol ensure Agreement and Validity BA’s basicproperties; see Section 2 with high probability, thus turning the Bitcoin backbone protocol into aprobabilistic BA protocol.Observe that for the above protocol to work the chain-quality property should ensure that amajority of blocks in the blockchain originate from the honest players otherwise Validity is lost.Our chain quality property enables this with overwhelming probability assuming the adversarialpower is bounded by 13. This approach is different from Nakamoto’s proposal [30] for BA, which,as we also show, only guarantees Validity with overwhelming probability if the adversary has anegligible amount of hashing power. On the positive side, we stress that Nakamoto’s protocol failsgracefully when the adversarial power gets close to 50 as Validity can be shown with constantprobability but not overwhelming.Public transaction ledgers and BA for honest majority. Next, we focus on how a “robust publictransaction ledger” can be built on top of the Bitcoin backbone. We instantiate the V ;I ;R functions so that parties blockchains and act according to the following rules each partywhich in this context is called a “miner” receives a set S of transactions on its tape andattempts to insert those in its blockchain, omitting any transactions in S that are already includedin it. A Bitcoin transaction is, for example, a statement of the type “account A credits account4B a z number of bitcoins,” which is signed using the secret key that corresponds to account A’sBitcoin address; each account has a unique Bitcoin address. Reading a blockchain, on the otherhand, amounts to returning the total sequence of transactions that is contained in the blockchainof the miner and note that miners may disagree about the chain they report.We show how the common prefix property and the chain-quality property ensure two propertiesneeded by the ledger, which we call Persistence and Liveness, assuming an honest majority andarbitrary adversarial behavior. Persistence states that once a transaction goes more than k blocks“deep” into the blockchain of one honest player, then it will be included in every honest player’sblockchainwithoverwhelmingprobability, anditwillbeassignedapermanentpositionintheledger.On the other hand, Liveness says that all transactions originating from honest account holders willeventually end up at a depth more than k blocks in an honest player’s blockchain, and hence theadversary cannot per a selective denial of service attack against honest account holders. Forboth properties to hold we require an honest majority i.e., that the adversary’s hashing poweris strictly less than 50 assuming high network synchronicity i.e., that the expected number ofPOW solutions per round satisfies2 f0. If this is violated, Persistence requires stricter boundson adversarial hashing power in order to be preserved following the bounds of the common prefixproperty.In the context of Bitcoin, our analysis implies that the Bitcoin backbone provides an operationaltransaction ledger under the assumptions i the adversary controls less than half of the totalhashing power, and ii the network synchronizes much faster relative to the POW solution rate,iii digital signatures cannot be forged. On the other hand, when the network desynchronizes ourresults cannot support that the ledger is maintained by assuming an honest majority. This negativeresult is consistent with the experimental analysis provided by Decker and Wattenhoffer [15], whopredicted a drop below 50 in the required adversarial bound for any setting when inationpropagation is problematic. Our result also provides some justification for the “slow” rate of 10-minute increments used in Bitcoin block generation. Specifically, ination propagation in theBitcoin network is on the order of seconds3 so the ratio essentially f of this time window overthe average 10-minute period is reasonably close to “small” and thus transaction persistence canbe shown for roughly an honest majority. On the other hand, cryptocurrencies including Litecoin,Primecoin and others, reacting to the demand to offer faster transaction proce