Paper 2022/1383

Sublinear-Round Broadcast without Trusted Setup against Dishonest Majority

Andreea B. Alexandru, Duality Technologies
Julian Loss, Helmholtz Center for Information Security
Charalampos Papamanthou, Yale University
Giorgos Tsimos, University of Maryland, College Park

Byzantine broadcast is one of the fundamental problems in distributed computing. Many practical applications from secure multiparty computation to consensus mechanisms for blockchains require increasingly weaker trust assumptions, as well as scalability for an ever-growing number of users, which rules out existing solutions with linear number of rounds or trusted setup requirements. In this paper, we propose the first sublinear-round and trustless Byzantine broadcast protocol. Unlike previous sublinear-round protocols, our protocol does not assume the existence of a trusted dealer who honestly issues keys and common random strings to the parties. Our protocol is based on a new cryptographic protocol called verifiable graded consensus, designed to act as an untrusted online setup, enabling $n$ parties to almost agree on shared random strings. We propose an implementation of the verifiable graded consensus protocol using transparent setup verifiable delay functions and random oracles, which is then used to run a committee-based Byzantine protocol, similar to Chan et al. (PKC 2020), in an unbiased fashion. Finally, we obtain a polylog-round trustless Byzantine broadcast with amortized communication complexity of $\tilde O(n^2)$, which can be further improved to $\tilde O(n)$ per instance for multiple instances of parallel broadcast.

Available format(s)
Cryptographic protocols
Publication info
BroadcastConsensus protocolsGraded agreementRandom beacons
Contact author(s)
aalexandru @ dualitytech com
lossjulian @ gmail com
charalampos papamanthou @ yale edu
tsimos @ umd edu
2023-04-17: revised
2022-10-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Andreea B. Alexandru and Julian Loss and Charalampos Papamanthou and Giorgos Tsimos},
      title = {Sublinear-Round Broadcast without Trusted Setup against Dishonest Majority},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1383},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.