Paper 2020/661

Tight Consistency Bounds for Bitcoin

Peter Gaži, Aggelos Kiayias, and Alexander Russell

Abstract

We establish the optimal security threshold for the Bitcoin protocol in terms of adversarial hashing power, honest hashing power, and network delays. Specifically, we prove that the protocol is secure if $$r_a < \frac{1}{\Delta + 1/r_h}\; ,$$ where $r_h$ is the expected number of honest proof-of-work successes in unit time, $r_a$ is the expected number of adversarial successes, and no message is delayed by more than $\Delta$ time units. In this regime, the protocol guarantees consistency and liveness with exponentially decaying failure probabilities. Outside this region, the simple private chain attack prevents consensus. Our analysis immediately applies to any Nakamoto-style proof-of-work protocol; we also present the adaptations needed to apply it in the proof-of-stake setting, establishing a similar threshold there.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. MINOR revision.ACM CCS 2020
Keywords
blockchainBitcoinproof of workproof of stake
Contact author(s)
peter gazi @ iohk io
aggelos kiayias @ iohk io
acr @ cse uconn edu
History
2020-11-11: last of 3 revisions
2020-06-03: received
See all versions
Short URL
https://ia.cr/2020/661
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/661,
      author = {Peter Gaži and Aggelos Kiayias and Alexander Russell},
      title = {Tight Consistency Bounds for Bitcoin},
      howpublished = {Cryptology ePrint Archive, Paper 2020/661},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/661}},
      url = {https://eprint.iacr.org/2020/661}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.