Cryptology ePrint Archive: Report 2020/661

Tight Consistency Bounds for Bitcoin

Peter Gaži and 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.

Category / Keywords: applications / blockchain, Bitcoin, proof of work, proof of stake

Date: received 2 Jun 2020

Contact author: peter gazi at iohk io,aggelos kiayias@iohk io,acr@cse uconn edu

Available format(s): PDF | BibTeX Citation

Version: 20200603:095859 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]