Paper 2022/823

Round Efficient Byzantine Agreement from VDFs

Poulami Das, Technical University of Darmstadt, Germany
Lisa Eckey, Technical University of Darmstadt, Germany
Sebastian Faust, Technical University of Darmstadt, Germany
Julian Loss, CISPA Helmholtz Center for Information Security
Monosij Maitra, Technical University of Darmstadt, Germany

Byzantine agreement (BA) is a fundamental primitive in distributed systems and has received huge interest as an important building block for blockchain systems. Classical byzantine agreement considers a setting where $n$ parties with fixed, known identities want to agree on an output in the presence of an adversary. Motivated by blockchain systems, the assumption of fixed identities is weakened by using a \emph{resource-based model}. In such models, parties do not have fixed known identities but instead have to invest some expensive resources to participate in the protocol. Prominent examples for such resources are computation (measured by, e.g., proofs-of-work) or money (measured by proofs-of-stake). Unlike in the classical setting where BA without trusted setup (e.g., a PKI or an unpredictable beacon) is impossible for $t \geq n/3$ corruptions, in such resource-based models, BA can be constructed for the optimal threshold of $t <n/2$. In this work, we investigate BA without a PKI in the model where parties have restricted computational resources. Concretely, we consider sequential computation modeled via computing a verifiable delay function (VDF) and establish the following results: Positive Result: We present the first protocol for BA with expected constant round complexity and termination under adaptive corruption, honest majority and without a PKI. Earlier work achieved round complexity $O(n\kappa^2)$ (CRYPTO'15) or $O(\kappa)$ (PKC'18), where $\kappa$ is the security parameter. Negative Result: We give the first lower bound on the communication complexity of BA in a model where parties have restricted computational resources. Concretely, we show that a multicast complexity of $O(\sqrt{n})$ is necessary even if the parties have access to a VDF oracle.

Available format(s)
Publication info
Byzantine Agreement Proof of Work Verifiable Delay Functions Impossibility
Contact author(s)
poulamidas22 @ gmail com
lisa eckey @ crisp-da de
sebastian faust @ cs tu-darmstadt de
lossjulian @ gmail com
monosij maitra @ tu-darmstadt de
2022-06-27: last of 2 revisions
2022-06-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Poulami Das and Lisa Eckey and Sebastian Faust and Julian Loss and Monosij Maitra},
      title = {Round Efficient Byzantine Agreement from VDFs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/823},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.