Cryptology ePrint Archive: Report 2014/765

The Bitcoin Backbone Protocol: Analysis and Applications

Juan Garay and Aggelos Kiayias and Nikos Leonardos

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. 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.

Category / Keywords: applications /

Original Publication (with major differences): IACR-EUROCRYPT-2015

Date: received 29 Sep 2014, last revised 1 Jul 2019

Contact author: akiayias at inf ed ac uk

Available format(s): PDF | BibTeX Citation

Note: various minor editorial fixes and corrections, compared to the conference version (that includes a complete rewrite and simplification of all proofs using the concept of typical executions from GKL16 as well as a bounded delay model analysis)

Version: 20190701:151939 (All versions of this report)

Short URL: ia.cr/2014/765


[ Cryptology ePrint archive ]