Paper 2024/637

Towards Permissionless Consensus in the Standard Model via Fine-Grained Complexity

Marshall Ball, NYU
Juan Garay, Texas A&M University
Peter Hall, NYU
Aggelos Kiayias, University of Edinburgh, IOHK
Giorgos Panagiotakos, IOHK

We investigate the feasibility of permissionless consensus (aka Byzantine agreement) under standard assumptions. A number of protocols have been proposed to achieve permissionless consensus, most notably based on the Bitcoin protocol; however, to date no protocol is known that can be provably instantiated outside of the random oracle model. In this work, we take the first steps towards achieving permissionless consensus in the standard model. In particular, we demonstrate that worst-case conjectures in fine-grained complexity, in particular the orthogonal vectors conjecture (implied by the Strong Exponential Time Hypothesis), imply permissionless consensus in the random beacon model—a setting where a fresh random value is delivered to all parties at regular intervals. This gives a remarkable win-win result: either permissionless consensus exists relative to a random beacon, or there are non-trivial worst-case algorithmic speed-ups for a host of natural algorithmic problems (including SAT). Our protocol achieves resilience against adversaries that control an inverse-polynomial fraction of the honest computational power, i.e., adversarial power $A = T^{1−ε} $ for some constant $ε > 0$, where $T$ denotes the honest computational power. This relatively low threshold is a byproduct of the slack in the fine-grained complexity conjectures. One technical highlight is the construction of a Seeded Proof of Work: a Proof of Work where many (correlated) challenges can be derived from a single short public seed, and yet still no non-trivial amortization is possible.

Available format(s)
Cryptographic protocols
Publication info
Consensusproof of workfine-grained complexity
Contact author(s)
marshall ball @ cs nyu edu
garay @ cse tamu edu
pf2184 @ nyu edu
aggelos kiayias @ ed ac uk
pagio91i @ gmail com
2024-04-26: approved
2024-04-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Marshall Ball and Juan Garay and Peter Hall and Aggelos Kiayias and Giorgos Panagiotakos},
      title = {Towards Permissionless Consensus in the Standard Model via Fine-Grained Complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2024/637},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.