Paper 2022/1423

The Superlinearity Problem in Post-Quantum Blockchains

Sunoo Park, Columbia University
Nicholas Spooner, University of Warwick

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.

Available format(s)
Cryptographic protocols
Publication info
proof of work post-quantum blockchain
Contact author(s)
sunoo @ csail mit edu
nicholas spooner @ warwick ac uk
2022-10-24: approved
2022-10-20: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.