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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
byzantine agreementblockchain
Contact author(s)
garay @ cse tamu edu
aggelos kiayias @ ed ac uk
shenyu tcv @ gmail com
History
2023-10-27: approved
2023-10-26: received
See all versions
Short URL
https://ia.cr/2023/1663
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1663,
      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{https://eprint.iacr.org/2023/1663}},
      url = {https://eprint.iacr.org/2023/1663}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.