**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: **ia.cr/2020/661

[ Cryptology ePrint archive ]