Paper 2014/765

The Bitcoin Backbone Protocol: Analysis and Applications

Juan Garay, 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.

Note: Minor edits in notation and terminology about security parameters. Added a remark on polylogarithmic round complexity for consensus.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
A major revision of an IACR publication in EUROCRYPT 2015
Contact author(s)
akiayias @ inf ed ac uk
History
2020-08-14: last of 17 revisions
2014-09-30: received
See all versions
Short URL
https://ia.cr/2014/765
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/765,
      author = {Juan Garay and Aggelos Kiayias and Nikos Leonardos},
      title = {The Bitcoin Backbone Protocol: Analysis and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2014/765},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/765}},
      url = {https://eprint.iacr.org/2014/765}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.