Paper 2023/1663

Proof-of-Work-based Consensus in Expected-Constant Time

Juan Garay, Texas A&M University
Aggelos Kiayias, University of Edinburgh, IOG
Yu Shen, University of Edinburgh

In the traditional consensus problem (aka Byzantine agreement), parties are required to agree on a common value despite the malicious behavior of some of them, subject to the condition that if all the honest parties start the execution with the same value, then that should be the outcome. This problem has been extensively studied by both the distributed computing and cryptographic protocols communities. With the advent of blockchains, whose main application—a distributed ledger—essentially requires that miners agree on their views, new techniques have been proposed to solve the problem, and in particular in so-called ``permissionless'' environments, where parties are not authenticated or have access to point to point channels and, further, may come and go as they please. So far, the fastest way to achieve consensus in the proof-of-work (PoW)-based setting of Bitcoin, takes O(polylog $\kappa$) number of rounds, where $\kappa$ is the security parameter. We present the first protocol in this setting that requires expected-constant number of rounds. Further, we show how to apply securely sequential composition in order to yield a fast distributed ledger protocol that settles all transactions in expected-constant time. Our result is based on a novel instantiation of ``m-for-1 PoWs'' on parallel chains that facilitates our basic building block, Chain-King Consensus. The techniques we use, via parallel chains, to port classical protocol design elements (such as Phase-King Consensus, super-phase sequential composition and others) into the permissionless setting may be of independent interest.

Available format(s)
Cryptographic protocols
Publication info
byzantine agreementblockchain
Contact author(s)
garay @ cse tamu edu
aggelos kiayias @ ed ac uk
shenyu tcv @ gmail com
2023-10-27: approved
2023-10-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Juan Garay and Aggelos Kiayias and Yu Shen},
      title = {Proof-of-Work-based Consensus in Expected-Constant Time},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1663},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.