[Resource Topic] 2020/661: Tight Consistency Bounds for Bitcoin

Welcome to the resource topic for 2020/661

Tight Consistency Bounds for Bitcoin

Authors: Peter Gaži, Aggelos Kiayias, Alexander Russell


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.

ePrint: https://eprint.iacr.org/2020/661

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .