Projects per year
Abstract / Description of output
A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. Arguably, its main impact has been in the setting of cryptocurrencies such as Bitcoin and its underlying blockchain protocol, which received significant attention in recent years due to its potential for various applications as well as for solving fundamental distributed computing questions in novel threat models. PoWs enable the linking of blocks in the blockchain data structure and thus the problem of interest is the feasibility of obtaining a sequence (chain) of such proofs. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multisolution Bernoulli search, for which we establish its quantum query complexity. Effectively, this is an extension of a threshold direct product theorem to an averagecase unstructured search problem. Our proof, adding to active recent efforts, simplifies and generalizes the recording technique of Zhandry (Crypto'19). As an application, we revisit the formal treatment of security of the core of the Bitcoin consensus protocol, the Bitcoin backbone (Eurocrypt'15), against quantum adversaries, while honest parties are classical and show that protocol's security holds under a quantum analogue of the classical “honest majority'' assumption. Our analysis indicates that the security of Bitcoin backbone is guaranteed provided the number of adversarial quantum queries is bounded so that each quantum query is worth O(p^−1/2) classical ones, where p is the success probability of a single classical query to the protocol's underlying hash function. Somewhat surprisingly, the wait time for safe settlement in the case of quantum adversaries matches the safe settlement time in the classical case.
Original language  English 

Pages (fromto)  132 
Journal  Quantum 
Volume  7 
Issue number  944 
DOIs  
Publication status  Published  9 Mar 2023 
Fingerprint
Dive into the research topics of 'Quantum MultiSolution Bernoulli Search with Applications to Bitcoin’s PostQuantum Security'. Together they form a unique fingerprint.
Blockchain Technology Fellowship
NonEU industry, commerce and public corporations
1/09/21 → 31/08/24
Project: Research

EPSRC Hub in Quantum Computing and Simulation
Kashefi, E., Arapinis, M., Heunen, C. & Wallden, P.
1/12/19 → 30/11/24
Project: Research
