Yahoo Research
[email protected] Aggelos Kiayias†‡ University of Edinburgh, IOHK
[email protected] Nikos Leonardos†§ National and Kapodistrian University of Athens.
[email protected] June 23, 2017 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 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 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. Finally, we show that our analysis of the Bitcoin backbone protocol for synchronous networks extends with relative ease to the recently considered “partially synchronous” model, where there is an upper bound in the delay of messages that is unknown to the honest parties. 1 Introduction Bitcoin, introduced in [Nak08a], is a decentralized payment system that is based on maintaining a public transaction ledger in a distributed manner. The ledger is maintained by anonymous par- ticipants (“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” ∗An abridged version of this paper appears in Proc. Eurocrypt 2015. †Research partly supported by ERC project CODAMODA, # 259152. ‡Work partly done while at the National and Kapodistrian University of Athens §Work partly done while at LIAFA, Université Paris Diderot–Paris 7. 1