Paper 2022/1423
The Superlinearity Problem in Post-Quantum Blockchains
Abstract
The proof of work mechanism by which many blockchain-based protocols achieve consensus may be undermined by the use of quantum computing in mining—even when all cryptographic primitives are replaced with post-quantum secure alternatives. First, we offer an impossibility result: we prove that quantum (Grover) speedups in solving a large, natural class of proof-of-work puzzles cause an inevitable incentive incompatibility in mining, by distorting the reward structure of mining in proof-of-work-based protocols such as Bitcoin. We refer to such distortion as the Superlinearity Problem. Our impossibility result suggests that for robust post-quantum proof-of-work-based consensus, we may need to look beyond standard cryptographic models. We thus propose a proof-of-work design in a random-beacon model, which is tailored to bypass the earlier impossibility. We conclude with a discussion of open problems, and of the challenges of integrating our new proof-of-work scheme into decentralised consensus protocols under realistic conditions.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- proof of work post-quantum blockchain
- Contact author(s)
-
sunoo @ csail mit edu
nicholas spooner @ warwick ac uk - History
- 2022-10-24: approved
- 2022-10-20: received
- See all versions
- Short URL
- https://ia.cr/2022/1423
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/1423,
author = {Sunoo Park and Nicholas Spooner},
title = {The Superlinearity Problem in Post-Quantum Blockchains},
howpublished = {Cryptology ePrint Archive, Paper 2022/1423},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1423}},
url = {https://eprint.iacr.org/2022/1423}
}
