Algorand: Scaling Byzantine Agreements for Cryptocurrencies

By Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, Nickolai Zeldovich. 2017

1,773 citations recorded by the source corpus.

Algorand is a new cryptocurrency that confirms 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 temporarily 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 125x Bitcoin's throughput, and incurs almost no penalty for scaling to more users.

Subfields: Artificial Intelligence, Computer Networks and Communications, Information Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Information Systems

Citations in the corpus

Mitigating Sybils in Federated Learning Poisoning (2018, background): “More recent alternatives have explored the use of proof of stake [16], which weighs clients by the value of their stake in the system.”
Biscotti: A Ledger for Private and Secure Peer-to-Peer Machine Learning (2018, methodology): “In Algorand, each peer is assigned a priority for two particular roles: block proposal and block selection.”
A Survey of Distributed Consensus Protocols for Blockchain Networks (2019, methodology): “Therefore, according to the authors [13], weak synchronony is sufficient for consensus safety during BA ’s routine operation Algorithm 7: Casper FFG”
HotStuff: BFT Consensus with Linearity and Responsiveness (2019, background): “As described above, recent blockchain solutions hybridize Proof-of-Work solutions with classical BFT solutions in various ways [7, 17, 26, 29, 31, 33, 42].”
Biscotti: A Blockchain System for Private and Secure Federated Learning (2021, methodology): “PoF is a consensus protocol for secure and private federated learning based on a recently proposed blockchain consensus mechanism called proof-of-stake (PoS) [32], [56].”
Security and Privacy for Green IoT-Based Agriculture: Review, Blockchain Solutions, and Challenges (2020, methodology): “The PoWe is proposed by Gilad et al. [110], which is based on the Algorand consensus model.”
Mobile Edge Computing, Blockchain and Reputation-based Crowdsourcing IoT Federated Learning: A Secure, Decentralized and Privacy-preserving System (2019, methodology): “Motivated by Algorand [12], we use Veriﬁable Random Functions (VRF) as a local and non-interactive way to select a subset of users as the leader candidates (weighed by their coins) and determine their priorities.”
A Vademecum on Blockchain Technologies: When, Which, and How (2019, background): “For Tendermint and other less known protocols [299], [300], [301] random committee selection is”
Monoxide: Scale out Blockchains with Asynchronous Consensus Zones (2019, methodology): “In summary, the existing proposals targeting on the single chain and non-sharding solution [42, 41, 43, 15, 29, 24, 18] are bound to the network bandwidth and cannot scale out; while the sharding systems either do not support full sharding [32], or may lower the attack bar after sharding [23, 47].”
Asynchronous Federated Learning on Heterogeneous Devices: A Survey (2021, background): “For example, Algorand [122] is a byzantine-tolerant consensus algorithm with excellent scalability while maintaining a high level of security.”
The Limitations of Federated Learning in Sybil Settings (2020, background): “, information from social networks or peer-to-peer systems are not applicable [22, 53, 55, 63, 64].”
A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks (2018, neutral): “[161] further propose a consensus protocol called ‘‘Algorand’’.”
Blockchain for AI: Review and Open Research Challenges (2019, neutral): “Ethereum and Hyperledger blockchains [130], [131].”
Solutions to Scalability of Blockchain: A Survey (2020, methodology): “With all these approaches, Algorand scales to 500,000 users in experiments and achieves high throughput. f: OTHER CONSENSUS Some other new consensus algorithms have been proposed in recent years, including PoA (proof-of-authority) [75], PoC (proof of capacity) [76] and PoP (proof-of-Participation) [”
Blockchain and IoT Integration: A Systematic Survey (2018, background): “Algorand is a BA class of algorithm [43].”
SBFT: A Scalable and Decentralized Trust Infrastructure (2018, background): “Other projects like Algorand [39] have only simulations and no open source code.”
RapidChain: Scaling Blockchain via Full Sharding (2018, methodology): “Recently, several protocols have been proposed to mitigate the performance and scalability issues of Bitcoin’s blockchain [23, 29, 41, 52, 56, 47, 32, 4, 42] using hybrid architectures that combine the open-membership nature of Bitcoin with traditional Byzantine fault tolerance [57, 19].”
Proof-of-Stake Consensus Mechanisms for Future Blockchain Networks: Fundamentals, Applications and Opportunities (2019, methodology): “Similar to Algorand, Tendermint has high transaction throughputs, e.g., up to 800 Tx/s, and low transaction confirmation time, e.g., 1 second on average [31], due to the blocks being immediately finalized.”