The Bitcoin Backbone Protocol

2020-03-01 160浏览

1.The Bitcoin BackboneProtocol:Analysis and Applications∗ Aggelos Kiayias† University of Athens aggelos@di.uoa.gr Juan A. Garay Yahoo Labs garay@yahoo-inc.com Nikos Leonardos† LIAFA, Université Paris Diderot–Paris 7 nikos.leonardos@gmail.com July 7, 2015 Abstract Bitcoin is the first and most popular decentralized cryptocurrency to date. In this work, we extract and analyze the core of the Bitcoin protocol, which we term the Bitcoin backbone, and prove two of its fundamental properties which we call common prefix and chain quality in the static setting where the number of players remains fixed. Our proofs hinge on appropriate and novel 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 protocol, specifically focusing on Byzantine agreement (BA) and on the notion of a public transaction 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 is bounded by 1/3. The public transaction ledger captures the essence of Bitcoin’s operation as a cryptocurrency, in the sense that it guarantees the liveness and persistence of committed transactions. Based on this notion we describe and analyze the Bitcoin system as well as a more elaborate BA protocol, proving them secure assuming high network synchronicity and that the adversary’s hashing power is strictly less than 1/2, while the adversarial bound needed for security decreases as the network desynchronizes. 1 Introduction Bitcoin, introduced in [29], is a decentralized payment system that is based on maintaining a public transaction ledger in a distributed manner. The ledger is maintained by anonymous participants (“players”) called miners, executing a protocol that maintains and extends a distributed data structure 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 a hash inequality based on SHA-256, in order to generate new blocks for the blockchain. The blocks that comprise the blockchain contain sets of transactions that are generated at will by owners of bitcoins, who issue transactions that credit any entity of their choice who accepts payments in bitcoin. Payers broadcast transactions and miners include the transactions they receive into the blocks ∗ † An abridged version of this paper appears in Proc. Eurocrypt 2015. Research partly supported by ERC project CODAMODA. 1
2.they generate. Miners are rewarded for maintaining the blockchain by receiving bitcoins; it is in this manner bitcoins are created and distributed among the miners who are the first recipients of newly minted bitcoins. An important concern in Bitcoin (or any e-payment system for that matter) is the prevention of double-spending attacks. Specifically, in the context of Bitcoin, a double-spending attack can occur when the attacker initially credits an account, receives service or goods by the account holder, but then manages to reorganize the transaction ledger so that the transaction that credits the account holder is reverted. In this way, the attacker keeps her bitcoin while receiving services and thus she is able to spend it again somewhere else. In [29], Nakamoto provides an initial set of arguments of why the Bitcoin system will prevent double-spending attacks. Specifically, he argues that if a payee waits for the transaction that gives her credit to advance into the blockchain a number of k blocks, then the probability that an attacker can build an alternative blockchain that “reorganizes” the public blockchain (which contains the credit transaction) drops exponentially with k. Nakamoto argues this by modeling the attacker and the set of honest players as two competing actors performing a random walk moving toward a single direction with probabilistic steps. He demonstrates that the k blocks the payee waits are enough to ensure a negligible (in k) probability of the attacker catching up with the honest players. Nevertheless, the above analysis can be easily seen to beoversimplified:in particular, it does not account for the fact that in Bitcoin’s decentralized setting the attacker may attempt to introduce disagreement between the honest miners, thus splitting their hashing power on different POW instances. Nakamoto himself appeared to recognize the relevance of agreement in the context of Bitcoin, arguing in a forum post [30] that actually “Bitcoin’s basic concept” of building and exchanging a blockchain is capable of solving Byzantine agreement (BA) [36, 27] in the presence of an actively malicious adversary.1 However a thorough analysis establishing the exact security properties of the Bitcoin system has yet to appear. Our results. In this paper we extract, formally describe, and analyze the core of the Bitcoin protocol. We call this protocol the Bitcoin backbone, as we describe it in a way that is versatile and extensible and can be used to solve other problems as well — not just the problem of maintaining a public transaction ledger. The Bitcoin backbone protocol is executed by players that build a blockchain following the Bitcoin source code [31] and allows a set of players to maintain a blockchain in a distributed fashion. The protocol is parameterized by three external functions V (·), I(·), R(·) which we call the input validation predicate, the input contribution function, and the chain reading function, respectively. At a high level, V (·) determines the proper structure of the information that is stored into the blockchain, I(·) specifies how the contents of the blocks are formed by the players, and R(·) 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 the description of the backbone protocol and are left to be specified by the three external functions above, 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 in a synchronous communication network (more details below and in Section 2) in the presence of an adversary that controls a subset of the players. We assume that the protocol is executed by a fixed number n of players; note, however, that this number is not necessarily known to the protocol participants. The players themselves cannot authenticate each other and therefore there is no way 1 In [30] Nakamoto refers to the problem as “Byzantine Generals,” which is often used to refer to the single-source version of the problem. Note that since more than one general may propose a time to attack this in fact is the case where every party has an input 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 equivalent in terms of the number of tolerated misbehaving parties t (t < n vs. t < n/2, respectively). 2
3.to know the source of a message; we capture this by allowing the adversary to “spoof” the source address of any message that is delivered. We assume that messages are eventually delivered and all parties in the network are able to synchronize in the course of a “round.” The notion of round is not important for the description of the backbone protocol (which can also be executed in a loose and asynchronous fashion in the same way that Bitcoin works), however, it is important in terms of Bitcoin’s inherent computational assumption regarding the players’ ability to produce POWs. Specifically, we assume that in a single round, all parties involved are allowed the same number of queries to a cryptographic hash function, as well as to communicate with the other participants. The hash function is modeled as a random oracle [6]. For simplicity we assume a “flat model,” where all parties have the same quota of hashing queries per round, say q; the non-flat model where parties have differing hashing power capabilities can be easily captured by clustering the flat-model parties into larger virtual entities that are comprised by more than one flat-model player. In fact “mining pools” in Bitcoin can be thought of such aggregations of flat-model players. The adversary itself represents such pool as it controls t < n players; for this reason, the adversary’s quota per round is t · q hashing queries. Note that in this setting, the fact t < n/2 directly corresponds to the adversary controlling strictly less than half of the system’s total “hashing power” that all players collectively harness, thus, we will use terms such as “honest majority” and “(1/2)-bounded adversary” interchangeably. In our analysis of the Bitcoin backbone protocol we formalize and prove two fundamental properties it possesses. The properties are quantified by three parameters γ, β and f ; γ and β roughly correspond to the collective hashing power per round of the honest players and the adversary, respectively, while f represents the expected number of POWs that may be found per round by the Bitcoin network participants as a whole. The common prefix property. We prove that if γ > λβ for some λ ∈ [1, ∞) that satisfies λ2 − f λ + 1 ≥ 0, then the blockchains maintained by the honest players will possess a large common prefix. More specifically, if two honest parties “prune” (i.e., cut off) k blocks from the end of their local chains, the probability that the resulting pruned chains will not be mutual prefixes of each other drops exponentially in k (see Definition 2 for the precise formulation). Provided that f is very close to 0 this enables us to choose λ very close to 1 and thus establish the common prefix property as long as an honest majority of participants in the flat-model setting is guaranteed (equivalently, when the adversary controls strictly less than 50% of the hashing 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 suggests much stricter bounds on the adversarial behavior (in fact, the upper bound on the adversary for our analysis approaches 0). The chain-quality property. We prove that if γ > λβ, for some λ ∈ [1, ∞), then the ratio of blocks in the chain of any honest player that are contributed by honest players is at least (1− λ1 ). Again observe that if λ is close to 1, we obtain that the blockchain maintained by honest players is guaranteed to have few, but still some, blocks contributed by honest players; a higher λ would be necessary to guarantee bigger percentages of blocks contributed by honest players in the blockchain. We also observe that this result is basically tight, i.e., that the adversary is capable of following a strategy (that deviates from the strategy of honest players) that enables the introduction of that many blocks in the blockchain, under a favorable (for the adversary) assumption on the propagation of adversarial blocks in the network. While the above two security properties may seem rather abstract since they refer to properties of the data structure that is maintained distributively by the parties, we demonstrate that they are in fact quite powerful and show that the Bitcoin backbone protocol armed with the above 3
4.Figure 1: An overview of the backbone protocol’sapplications:Nakamoto’s BA protocol Πnak BA , our 1/3 1/2 BA protocols ΠBA and ΠBA , and the public ledger protocol ΠPL . All properties must be satisfied with overwhelming probability. In each box we state the name of the property as well as the maximum ratio of the adversarial hashing power that we can prove the protocol withstands (based on 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 distributively maintaining a “robust” public transaction ledger. In Figure 1 we show how the two properties imply the properties of the applications that are explained below. Byzantine agreement for (1/3)-bounded adversaries. As a first application, we show how a randomized 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 that parties form blockchains and act according to the followingrules:'>rules: