Asynchronous Algorand: Reaching Agreement with Near Linear Communication and Constant Expected Time

Ittai Abraham; Eli Chouatt; Ivan Damgård; Yossi Gilad; Gilad Stern; Sophia Yakoubov

Paper 2025/303

Asynchronous Algorand: Reaching Agreement with Near Linear Communication and Constant Expected Time

Ittai Abraham, Intel Labs

Eli Chouatt, Hebrew University of Jerusalem

Ivan Damgård, Aarhus University

Yossi Gilad, Hebrew University of Jerusalem

Gilad Stern, Tel Aviv University

Sophia Yakoubov, Aarhus University

Abstract

The celebrated Algorand protocol solves validated byzantine agreement in a scalable manner in the synchronous setting. In this paper, we study the feasibility of similar solutions in the asynchronous setting. Our main result is an asynchronous validated byzantine agreement protocol that we call Asynchronous Algorand. As with Algorand, it terminates in an expected constant number of rounds, and honest parties send an expected bits, where is the number of parties. The protocol is resilient to a fully-asynchronous weakly-adaptive adversary that can corrupt a near-optimal number of parties () and requires just a VRF setup and secure erasures. A key innovation in Asynchronous Algorand is a rather simple but surprisingly effective method to do \textit{committee-based role assignment} for asynchronous verifiable secret sharing in the YOSO (You Only Speak Once) model. This method achieves near-optimal resilience and near-linear communication complexity while relying solely on a verifiable random function (VRF) setup and secure erasures.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: consensus asynchrony
Contact author(s): ittai abraham @ intel com
eli chouatt @ mail huji ac il
ivan @ cs au dk
yossigi @ cs huji ac il
giladstern @ tauex tau ac il
sophia yakoubov @ gmail com
History: 2025-02-21: approved; 2025-02-20: received; See all versions
Short URL: https://ia.cr/2025/303
License: CC BY

BibTeX

@misc{cryptoeprint:2025/303,
      author = {Ittai Abraham and Eli Chouatt and Ivan Damgård and Yossi Gilad and Gilad Stern and Sophia Yakoubov},
      title = {Asynchronous Algorand: Reaching Agreement with Near Linear Communication and Constant Expected Time},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/303},
      year = {2025},
      url = {https://eprint.iacr.org/2025/303}
}