Paper 2017/454

Algorand: Scaling Byzantine Agreements for Cryptocurrencies

Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich

Abstract

Algorand is a new cryptocurrency system that can confirm transactions with latency on the order of a minute while scaling to many users. Algorand ensures that users never have divergent views of confirmed transactions, even if some of the users are malicious and the network is partitioned. In contrast, existing cryptocurrencies allow for temporary forks and therefore require a long time, on the order of an hour, to confirm transactions with high confidence. Algorand uses a new Byzantine Agreement (BA) protocol to reach consensus among users on the next set of transactions. To scale the consensus to many users, Algorand uses a novel mechanism based on Verifiable Random Functions that allows users to privately check whether they are selected to participate in the BA to agree on the next set of transactions, and to include a proof of their selection in their network messages. In Algorand's BA protocol, users do not keep any private state except for their private keys, which allows Algorand to replace participants immediately after they send a message. This mitigates targeted attacks on chosen participants after their identity is revealed. We implement Algorand and evaluate its performance on 1,000 EC2 virtual machines, simulating up to 500,000 users. Experimental results show that Algorand confirms transactions in under a minute, achieves 30$\times$ Bitcoin's throughput, and incurs almost no penalty for scaling to more users.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
yossigi @ csail mit edu
History
2017-09-24: last of 2 revisions
2017-05-25: received
See all versions
Short URL
https://ia.cr/2017/454
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/454,
      author = {Yossi Gilad and Rotem Hemo and Silvio Micali and Georgios Vlachos and Nickolai Zeldovich},
      title = {Algorand: Scaling Byzantine Agreements for Cryptocurrencies},
      howpublished = {Cryptology ePrint Archive, Paper 2017/454},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/454}},
      url = {https://eprint.iacr.org/2017/454}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.