The Superlinearity Problem in Post-quantum Blockchains

Sunoo Park, Nicholas Spooner

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationFinancial Cryptography and Data Security - 27th International Conference, FC 2023, Revised Selected Papers
EditorsFoteini Baldimtsi, Christian Cachin
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages18
ISBN (Print)9783031477539
StatePublished - 2024
Event27th International Conference on Financial Cryptography and Data Security, FC 2023 - Bol, Croatia
Duration: May 1 2023May 5 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference27th International Conference on Financial Cryptography and Data Security, FC 2023

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'The Superlinearity Problem in Post-quantum Blockchains'. Together they form a unique fingerprint.

Cite this