Paper 2022/1423

The Superlinearity Problem in Post-Quantum Blockchains

Sunoo Park, Columbia University
Nicholas Spooner, University of Warwick
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.