Cryptology ePrint Archive: Report 2019/1150

The Bitcoin Backbone Protocol Against Quantum Adversaries

Alexandru Cojocaru and Juan Garay and Aggelos Kiayias and Fang Song and Petros Wallden

Abstract: 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.

Category / Keywords: cryptographic protocols / Blockchain, Post-Quantum, Quantum Random Oracle

Date: received 3 Oct 2019, last revised 19 Feb 2020

Contact author: a d cojocaru at sms ed ac uk, juan a garay at gmail com, akiayias at inf ed ac uk, fang song at tamu edu, petros wallden at ed ac uk

Available format(s): PDF | BibTeX Citation

Version: 20200219:183552 (All versions of this report)

Short URL: ia.cr/2019/1150


[ Cryptology ePrint archive ]