Paper 2019/1150

The Bitcoin Backbone Protocol Against Quantum Adversaries

Alexandru Cojocaru, Juan Garay, Aggelos Kiayias, Fang Song, and 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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
BlockchainPost-QuantumQuantum Random Oracle
Contact author(s)
a d cojocaru @ sms ed ac uk
juan a garay @ gmail com
akiayias @ inf ed ac uk
fang song @ tamu edu
petros wallden @ ed ac uk
2020-02-19: last of 2 revisions
2019-10-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alexandru Cojocaru and Juan Garay and Aggelos Kiayias and Fang Song and Petros Wallden},
      title = {The Bitcoin Backbone Protocol Against Quantum Adversaries},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1150},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.