Yossi Gilad
Rotem Hemo
Silvio Micali
ABSTRACT
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.
Supplemental Material
- M. Abd-El-Malek, G. R. Ganger, G. R. Goodson, M. K. Reiter, and J. J. Wylie. Fault-scalable Byzantine fault-tolerant services. In Proceedings of the 20th ACM Symposium on Operating Systems Principles (SOSP), pages 59--74, Brighton, UK, Oct. 2005. Google Scholar
Digital Library
- I. Bentov and R. Kumaresan. How to use Bitcoin to design fair protocols. In Proceedings of the 34th Annual International Cryptology Conference (CRYPTO), Santa Barbara, CA, Aug. 2014.Google ScholarCross Ref
- I. Bentov, C. Lee, A. Mizrahi, and M. Rosenfeld. Proof of activity: Extending Bitcoin's proof of work via proof of stake. In Proceedings of the 2014 Joint Workshop on Pricing and Incentives in Networks and Systems, Austin, TX, June 2014.Google Scholar
- I. Bentov, A. Gabizon, and A. Mizrahi. Cryptocurrencies without proof of work. In Proceedings of the 2016 Financial Cryptography and Data Security Conference, 2016.Google ScholarCross Ref
- I. Bentov, P. Hubáček, T. Moran, and A. Nadler. Tortoise and hares consensus: the Meshcash framework for incentive-compatible, scalable cryptocurrencies. Cryptology ePrint Archive, Report 2017/300, Apr. 2017. http://eprint.iacr.org/.Google Scholar
- D. J. Bernstein. Curve25519: New Diffie-Hellman speed records. In Proceedings of the 9th International Conference on Theory and Practice in Public-Key Cryptography (PKC), pages 207--228, New York, NY, Apr. 2006. Google ScholarDigital Library
- Bitcoin Wiki. Confirmation. https://en.bitcoin.it/wiki/Confirmation, 2017.Google Scholar
- BitcoinWiki. Mining hardware comparison, 2016. https://en.bitcoin.it/wiki/Mining_hardware_comparison.Google Scholar
- BitcoinWiki. Bitcoin scalability. https://en.bitcoin.it/wiki/Scalability, 2017.Google Scholar
- BitcoinWiki. Proof of stake. https://en.bitcoin.it/wiki/Proof_of_Stake, 2017.Google Scholar
- D. Boneh and M. K. Franklin. Identity-based encryption from the Weil pairing. In Proceedings of the 21st Annual International Cryptology Conference (CRYPTO), Santa Barbara, CA, Aug. 2001. Google ScholarDigital Library
- G. Brockman. Stellar, July 2014. https://stripe.com/blog/stellar.Google Scholar
- V. Buterin. Minimal slashing conditions. https://medium.com/@VitalikButerin/minimal-slashing-conditions-20f0b500fc6c, Mar. 2017.Google Scholar
- C. Cachin, K. Kursawe, F. Petzold, and V. Shoup. Secure and efficient asynchronous broadcast protocols. In Proceedings of the 21st Annual International Cryptology Conference (CRYPTO), pages 524--541, Santa Barbara, CA, Aug. 2001. Google ScholarDigital Library
- M. Castro and B. Liskov. Practical Byzantine fault tolerance and proactive recovery. ACM Transactions on Computer Systems, 20(4), Nov. 2002. Google ScholarDigital Library
- J. Chen and S. Micali. Algorand. Technical report, 2017. URL http://arxiv.org/abs/1607.01341.Google Scholar
- A. Clement, E. L. Wong, L. Alvisi, M. Dahlin, and M. Marchetti. Making Byzantine fault tolerant systems tolerate Byzantine faults. In Proceedings of the 6th Symposium on Networked Systems Design and Implementation (NSDI), pages 153--168, Boston, MA, Apr. 2009. Google ScholarDigital Library
- C. Decker and R. Wattenhofer. Information propagation in the Bitcoin network. In Proceedings of the 13th IEEE International Conference on Peer-to-Peer Computing, Sept. 2013.Google ScholarCross Ref
- R. Dingledine, N. Mathewson, and P. Syverson. Tor: The second-generation onion router. In Proceedings of the 13th Usenix Security Symposium, pages 303--320, San Diego, CA, Aug. 2004. Google ScholarDigital Library
- N. Döttling and S. Garg. Identity-based encryption from the Diffie-Hellman assumption. In Proceedings of the 37th Annual International Cryptology Conference (CRYPTO), pages 537--569, Santa Barbara, CA, Aug. 2017.Google ScholarCross Ref
- J. R. Douceur. The Sybil attack. In Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS '02), Cambridge, MA, Mar. 2002. Google ScholarDigital Library
- P. Erdős and A. Rényi. On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5:17--61, 1960.Google Scholar
- Ethereum Foundation. Ethereum, 2016. https://www.ethereum.org/.Google Scholar
- Ethereum Foundation. Create a democracy contract in Ethereum, 2016. https://www.ethereum.org/dao.Google Scholar
- I. Eyal and E. G. Sirer. Majority is not enough: Bitcoin mining is vulnerable. In Proceedings of the 2013 Financial Cryptography and Data Security Conference, Mar. 2014.Google ScholarCross Ref
- I. Eyal, A. E. Gencer, E. G. Sirer, and R. van Renesse. Bitcoin-NG: A scalable blockchain protocol. In Proceedings of the 13th Symposium on Networked Systems Design and Implementation (NSDI), pages 45--59, Santa Clara, CA, Mar. 2016. Google ScholarDigital Library
- Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich. Algorand: Scaling Byzantine agreements for cryptocurrencies. Cryptology ePrint Archive, Report 2017/454, Version 20170924:210956, Sept. 2017. http://eprint.iacr.org/.Google Scholar
- S. Goldberg, M. Naor, D. Papadopoulos, and L. Reyzin. NSEC5 from elliptic curves: Provably preventing DNSSEC zone enumeration with shorter responses. Cryptology ePrint Archive, Report 2016/083, Mar. 2016. http://eprint.iacr.org/.Google Scholar
- E. Heilman, A. Kendler, A. Zohar, and S. Goldberg. Eclipse attacks on Bitcoin's peer-to-peer network. In Proceedings of the 24th Usenix Security Symposium, pages 129--144, Washington, DC, Aug. 2015. Google ScholarDigital Library
- S. Higgins. Bitcoin mining pools targeted in wave of DDoS attacks. Mar. 2015. https://www.coindesk.com/bitcoin-mining-pools-ddos-attacks/.Google Scholar
- A. Kiayias, I. Konstantinou, A. Russell, B. David, and R. Oliynykov. Ouroboros: A provably secure proof-of-stake blockchain protocol. Cryptology ePrint Archive, Report 2016/889, 2016. http://eprint.iacr.org/.Google Scholar
- S. King and S. Nadal. PPCoin: Peer-to-peer cryptocurrency with proof-of-stake, Aug. 2012. https://peercoin.net/assets/paper/peercoin-paper.pdf.Google Scholar
- E. Kokoris-Kogias, P. Jovanovic, N. Gailly, I. Khoffi, L. Gasser, and B. Ford. Enhancing Bitcoin security and performance with strong consistency via collective signing. In Proceedings of the 25th Usenix Security Symposium, pages 279--296, Austin, TX, Aug. 2016.Google ScholarDigital Library
- R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. L. Wong. Zyzzyva: Speculative Byzantine fault tolerance. ACM Transactions on Computer Systems, 27(4):7:1--39, 2009. Google ScholarDigital Library
- L. Lamport. The part-time parliament. ACM Transactions on Computer Systems, 16(2):133--169, 1998. Google ScholarDigital Library
- J. Li and D. Mazières. Beyond one-third faulty replicas in Byzantine fault tolerant systems. In Proceedings of the 4th Symposium on Networked Systems Design and Implementation (NSDI), Cambridge, MA, Apr. 2007. Google ScholarDigital Library
- D. Mazières. The Stellar consensus protocol: A federated model for internet-level consensus. https://www.stellar.org/papers/stellar-consensus-protocol.pdf, 2014.Google Scholar
- S. Micali. Fast and furious Byzantine agreement. In Proceedings of the Innovations in Theoretical Computer Science (ITCS) Conference, 2017.Google Scholar
- S. Micali, M. O. Rabin, and S. P. Vadhan. Verifiable random functions. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), New York, NY, Oct. 1999. Google ScholarDigital Library
- A. Miller, Y. Xia, K. Croman, E. Shi, and D. Song. The Honey Badger of BFT protocols. In Proceedings of the 23rd ACM Conference on Computer and Communications Security (CCS), pages 31--42, Vienna, Austria, Oct. 2016. Google ScholarDigital Library
- A. Monaghan. US wealth inequality: top 0.1% worth as much as the bottom 90%, Nov. 2014. https://www.theguardian.com/business/2014/nov/13/us-wealth-inequality-top-01-worth-as-much-as-the-bottom-90.Google Scholar
- S. Nakamoto. Bitcoin: A peer-to-peer electronic cash system. https://bitcoin.org/bitcoin.pdf, 2008.Google Scholar
- R. Pass and E. Shi. Hybrid consensus: Efficient consensus in the permissionless model. Cryptology ePrint Archive, Report 2016/917, 2016. http://eprint.iacr.org/.Google Scholar
- Peercointalk. Peercoin invalid checkpoint. https://www.peercointalk.org/t/invalid-checkpoint/3691, 2015.Google Scholar
- O. Riordan and N. Wormald. The diameter of sparse random graphs. Combinatorics, Probability and Computing, 19(5-6):835--926, Nov. 2010. Google ScholarDigital Library
- P. Rizzo. BitGo launches "instant" Bitcoin transaction tool, Jan. 2016. http//:www.coindesk.com/bitgo-instant-bitcoin-transaction-tool/.Google Scholar
- J. Rubin. The problem of ASICBOOST, Apr. 2017. http//:www.mit.edu/~jlrubin/public/pdfs/Asicboost.pdf.Google Scholar
- Y. Sompolinsky and A. Zohar. Secure high-rate transaction processing in Bitcoin. In Proceedings of the 2015 Financial Cryptography and Data Security Conference, 2015.Google ScholarCross Ref
- Y. Sompolinsky, Y. Lewenberg, and A. Zohar. SPECTRE: A fast and scalable cryptocurrency protocol. Cryptology ePrint Archive, Report 2016/1159, 2016. http://eprint.iacr.org/.Google Scholar
- N. Szabo. Smart contracts: Formalizing and securing relationships on public networks. First Monday, 2(9), Sept. 1997. http://firstmonday.org/ojs/index.php/fm/article/view/548/469.Google Scholar
- R. Turpin and B. A. Coan. Extending binary Byzantine agreement to multivalued Byzantine agreement. Information Processing Letters, 18(2):73--76, Feb. 1984.Google ScholarCross Ref
- M. Vasek, M. Thornton, and T. Moore. Empirical analysis of denial-of-service attacks in the Bitcoin ecosystem. In Proceedings of the 18th International Financial Cryptography and Data Security Conference, Barbados, Mar. 2014.Google ScholarCross Ref
- WonderNetwork. Global ping statistics: Ping times between WonderNetwork servers, Apr. 2017. https://wondernetwork.com/pings.Google Scholar
- Zerocoin Electric Coin Company. ZCash: All coins are created equal, 2017. https://z.cash.Google Scholar
Recommendations
Blockchain Trilemma Solver Algorand has Dilemma over Undecidable Messages
ARES '19: Proceedings of the 14th International Conference on Availability, Reliability and SecurityA variety of solutions, e.g., Proof-of-Work (PoW), Proof-of-Stake (PoS), Proof-of-Burn (PoB), and Proof-of-Elapsed-Time (PoET), have been proposed to make consensus mechanism used by the blockchain technology more democratic, efficient, and scalable. ...
Algorand: A secure and efficient distributed ledger
AbstractA distributed ledger is a tamperproof sequence of data that can be publicly accessed and augmented by everyone, without being maintained by a centralized party. Distributed ledgers stand to revolutionize the way a modern society ...
Towards a Verified Model of the Algorand Consensus Protocol in Coq
Formal Methods. FM 2019 International WorkshopsAbstractThe Algorand blockchain is a secure and decentralized public ledger based on pure proof of stake rather than proof of work. At its core it is a novel consensus protocol with exactly one block certified in each round: that is, the protocol ...
Comments