[Resource Topic] 2019/1150: The Bitcoin Backbone Protocol Against Quantum Adversaries

Welcome to the resource topic for 2019/1150

The Bitcoin Backbone Protocol Against Quantum Adversaries

Authors: Alexandru Cojocaru, Juan Garay, Aggelos Kiayias, Fang Song, Petros Wallden


Bitcoin and its underlying blockchain protocol have received recently significant attention in the context of building distributed systems as well as from the perspective of the foundations of the consensus problem. At the same time, the rapid development of quantum technologies brings the possibility of quantum computing devices from a theoretical concept to an emerging technology. Motivated by this, in this work we revisit the formal security of the core of the Bitcoin protocol, called the Bitcoin backbone, in the presence of an adversary that has access to a scalable quantum computer. We prove that the protocol’s essential properties stand in the post-quantum setting assuming a general quantum adversary with suitably bounded number of queries in the Quantum Random Oracle (QRO) model. In order to achieve this, we investigate and bound the quantum complexity of a Chain-of-Proofs-of-Work search problem which is at the core of the blockchain protocol. Our results imply that security can be shown by bounding the quantum queries so that each quantum query is worth O(p^{-1/2}) classical ones and that the wait time for safe settlement is expanded by a multiplicative factor of O(p^{-1/6}), where p is the probability of success of a single classical query to the protocol’s underlying hash function.

ePrint: https://eprint.iacr.org/2019/1150

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 .