Loi Luu
ABSTRACT
Cryptocurrencies, such as Bitcoin and 250 similar alt-coins, embody at their core a blockchain protocol --- a mechanism for a distributed network of computational nodes to periodically agree on a set of new transactions. Designing a secure blockchain protocol relies on an open challenge in security, that of designing a highly-scalable agreement protocol open to manipulation by byzantine or arbitrarily malicious nodes. Bitcoin's blockchain agreement protocol exhibits security, but does not scale: it processes 3--7 transactions per second at present, irrespective of the available computation capacity at hand.
In this paper, we propose a new distributed agreement protocol for permission-less blockchains called ELASTICO. ELASTICO scales transaction rates almost linearly with available computation for mining: the more the computation power in the network, the higher the number of transaction blocks selected per unit time. ELASTICO is efficient in its network messages and tolerates byzantine adversaries of up to one-fourth of the total computational power. Technically, ELASTICO uniformly partitions or parallelizes the mining network (securely) into smaller committees, each of which processes a disjoint set of transactions (or "shards"). While sharding is common in non-byzantine settings, ELASTICO is the first candidate for a secure sharding protocol with presence of byzantine adversaries. Our scalability experiments on Amazon EC2 with up to $1, 600$ nodes confirm ELASTICO's theoretical scaling properties.
- Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. bitcoin.org, 2009.Google Scholar
- Blockchain stats. Bitcoin statistics. https://blockchain.info/stats, 2012.Google Scholar
- Bitcoin wiki. Scalability. https://en.bitcoin.it/wiki/Scalability, 2015.Google Scholar
- Mastercard. Mastercard's transaction per second. http://newsroom.mastercard.com/2012/11/26/mastercard- sees-black-friday-performance-up-26-percent/, 2016.Google Scholar
- Visa. Visa's transactions per second. https://usa.visa.com/content_library/modal/benefits-accepting-visa.html, 2016.Google Scholar
- Jeff Garzik. Making decentralized economic policy. http://gtf.org/garzik/bitcoin/BIP100-blocksizechangeproposal.pdf, 2015.Google Scholar
- Gavin Andresen. Bitcoin improvement proposal 101. https://github.com/bitcoin/bips/blob/master/bip-0101.mediawiki, 2015.Google Scholar
- Jeff Garzik. Bitcoin improvement proposal 102. https://github.com/bitcoin/bips/blob/master/bip-0102.mediawiki, 2015.Google Scholar
- Ittay Eyal, Adem Efe Gencer, Emin Gun Sirer, and Robbert van Renesse. Bitcoin-ng: A scalable blockchain protocol. http://arxiv.org/abs/1510.02037, 2015.Google Scholar
- Kyle Croman, Christian Decker, Ittay Eyal, Adem Efe Gencer, Ari Juels, Ahmed Kosba, Andrew Miller, Prateek Saxena, Elaine Shi, Emin Gun Sirer, Dawn Song, and Roger Wattenhofer. On scaling decentralized blockchains (a position paper). Workshop on Bitcoin and Blockchain Research, 2016.Google Scholar
- M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. J. ACM, 27(2):228--234, April 1980. Google ScholarDigital Library
- Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382--401, July 1982. Google ScholarDigital Library
- Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation, pages 173--186. USENIX Association, 1999. Google ScholarDigital Library
- Sam Toueg, Kenneth J. Perry, and T. K. Srikanth. Fast distributed agreement (preliminary version). In Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, pages 87--101. ACM, 1985. Google ScholarDigital Library
- James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, J. J. Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, and Dale Woodford. Spanner: Google's globally distributed database. ACM Trans. Comput. Syst., aug 2013. Google ScholarDigital Library
- Lisa Glendenning, Ivan Beschastnikh, Arvind Krishnamurthy, and Thomas Anderson. Scalable consistency in scatter. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, SOSP '11, pages 15--28, New York, NY, USA, 2011. ACM. Google ScholarDigital Library
- Jason Baker, Chris Bond, James C. Corbett, JJ Furman, Andrey Khorlin, James Larson, Jean-Michel Leon, Yawei Li, Alexander Lloyd, and Vadim Yushprakh. Megastore: Providing scalable, highly available storage for interactive services. In Proceedings of the Conference on Innovative Data system Research (CIDR), pages 223--234, 2011.Google Scholar
- Intel. Intel distributed ledger. http://intelledger.github.io/, 2016.Google Scholar
- Chain Inc. Chain open standard: A secure blockchain protocol for high-scale financial networks. http://chain.com/os/, 2016.Google Scholar
- Rhett Creighton. Domus tower blockchain. http://domustower.com/domus-tower-blockchain-latest.pdf, 2016.Google Scholar
- David Mazieres. The stellar consensus protocol: A federated model for internet-level consensus. April 2015.Google Scholar
- Arthur Britto David Schwartz, Noah Youngs. The ripple protocol consensus algorithm. Ripple Labs Inc., 2014.Google Scholar
- Bitcoin client. https://github.com/bitcoin/bitcoin.Google Scholar
- Rachid Guerraoui, Florian Huc, and Anne-Marie Kermarrec. Highly dynamic distributed computing with byzantine failures. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC '13, 2013. Google ScholarDigital Library
- Gopal Pandurangan, Peter Robinson, and Amitabh Trehan. Self-healing deterministic expanders. CoRR, abs/1206.1522, 2012.Google Scholar
- John R. Douceur. The sybil attack. In Proceedings of 1st International Workshop on Peer-to-Peer Systems (IPTPS), 2002. Google ScholarDigital Library
- James Newsome, Elaine Shi, Dawn Song, and Adrian Perrig. The sybil attack in sensor networks: Analysis & defenses. In Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks, IPSN '04, pages 259--268, New York, NY, USA, 2004. ACM. Google ScholarDigital Library
- Baruch Awerbuch and Christian Scheideler. Robust random number generation for peer-to-peer systems. Theor. Comput. Sci., 410(6--7):453--466, feb 2009. Google ScholarDigital Library
- Bitcoin wiki. Proof of stake. https://en.bitcoin.it/wiki/Proof_of_Stake, 2015.Google Scholar
- Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Pietrzak. Proofs of space. Cryptology ePrint Archive, Report 2013/796, 2013. http://eprint.iacr.org/.Google Scholar
- Giuseppe Ateniese, Ilario Bonacina, Antonio Faonio, and Nicola Galesi. Proofs of space: When space is of the essence. Cryptology ePrint Archive, Report 2013/805, 2013. http://eprint.iacr.org/.Google Scholar
- Nancy Lynch. Distributed algorithms. Morgan Kaufmann, 1996. Google ScholarDigital Library
- Seth Gilbert, Calvin Newport, and Chaodong Zheng. Who are you? secure identities in ad hoc networks. In Distributed Computing, pages 227--242. Springer, 2014.Google ScholarCross Ref
- Juan Garay, Aggelos Kiayias, and Nikos Leonardos. The bitcoin backbone protocol: Analysis and applications. Cryptology ePrint Archive, Report 2014/765, 2014. http://eprint.iacr.org/.Google Scholar
- Jae Kwon. Tendermint: Consensus without mining.Google Scholar
- IBM. Ibm blockchain. http://www.ibm.com/blockchain/, 2016.Google Scholar
- Digital Asset Holdings. Digital asset. https://digitalasset.com/, 2016.Google Scholar
- Ethereum Foundation. Ethereum's white paper. https://github.com/ethereum/wiki/wiki/White-Paper, 2014.Google Scholar
- George Danezis and Sarah Meiklejohn. Centrally banked cryptocurrencies. Cryptology ePrint Archive, Report 2015/502, 2015. http://eprint.iacr.org/.Google Scholar
- Yonatan Sompolinsky and Aviv Zohar. Accelerating bitcoin's transaction processing. fast money grows on trees, not chains. Cryptology ePrint Archive, Report 2013/881, 2013. http://eprint.iacr.org/.Google Scholar
- Loi Luu, Jason Teutsch, Raghav Kulkarni, and Prateek Saxena. Demystifying incentives in the consensus computer. Cryptology ePrint Archive, Report 2015/702, 2015. http://eprint.iacr.org/.Google Scholar
- Thaddeus Dryja Joseph Poon. The bitcoin lightning network: Scalable off-chain instant payments. http://lightning.network/lightning-network-paper.pdf, 2015.Google Scholar
- Adam Back, Matt Corallo, Luke Dashjr, Mark Friedenbach, Gregory Maxwell, Andrew Miller, Andrew Poelstra, Jorge Timon, and Pieter Wuille. Enabling blockchain innovations with pegged sidechains. https://blockstream.com/sidechains.pdf, 2014.Google Scholar
- Pieter Wuille. Would sidechains help bitcoin scale? 2015.Google Scholar
- Buteri Vitalik, Wood Gavin, Zamfir Vlad, Coleman Jeff, Wampler-Doty Matthew, and Cohn John. Notes on scalable blockchain protocols (version 0.3.2). https://github.com/vbuterin/scalability_paper/raw/master/scalability.pdf, 2015.Google Scholar
- Gabriel Bracha. An O(log n) expected rounds randomized byzantine generals protocol. J. ACM, 34:910--920, October 1987. Google ScholarDigital Library
- Seth Gilbert and Dariusz R. Kowalski. Distributed agreement with optimal communication complexity. In Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, pages 965--977. Society for Industrial and Applied Mathematics, 2010. Google ScholarDigital Library
- Leslie Lamport. Fast paxos. Distributed Computing, 19(2):79--103, October 2006.Google ScholarDigital Library
- Allen Clement, Edmund Wong, Lorenzo Alvisi, Mike Dahlin, and Mirco Marchetti. Making byzantine fault tolerant systems tolerate byzantine faults. In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation, pages 153--168. USENIX Association, 2009. Google ScholarDigital Library
- Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. Zyzzyva: Speculative byzantine fault tolerance. ACM Trans. Comput. Syst., 27(4):7:1--7:39, January 2010. Google ScholarDigital Library
- Pierre-Louis Aublin, Rachid Guerraoui, Nikola Knezević, Vivien Quéma, and Marko Vukolić. The next 700 bft protocols. ACM Trans. Comput. Syst., 32(4):12:1--12:45, January 2015. Google ScholarDigital Library
- V. King, J. Saia, V. Sanwalani, and E. Vee. Towards secure and scalable computation in peer-to-peer networks. In Foundations of Computer Science, 2006. FOCS '06. 47th Annual IEEE Symposium on, pages 87--98, 2006. Google ScholarDigital Library
- Valerie King and Jared Saia. From almost everywhere to everywhere: Byzantine agreement with ~O(n3/2) bits. In Proceedings of the 23rd International Conference on Distributed Computing, pages 464--478. Springer-Verlag, 2009. Google ScholarDigital Library
- Valerie King, Steven Lonargan, Jared Saia, and Amitabh Trehan. Load balanced scalable byzantine agreement through quorum building, with full information. In Distributed Computing and Networking, volume 6522 of Lecture Notes in Computer Science, pages 203--214. Springer Berlin Heidelberg, 2011. Google ScholarDigital Library
- Nicolas Braud-Santoni, Rachid Guerraoui, and Florian Huc. Fast byzantine agreement. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, pages 57--64. ACM, 2013. Google ScholarDigital Library
- U. Feige. Noncryptographic selection protocols. In Foundations of Computer Science, 1999. 40th Annual Symposium on, pages 142--152, 1999. Google ScholarDigital Library
- Valerie King and Jared Saia. Breaking the $O(n^2)$ bit barrier: Scalable byzantine agreement with an adaptive adversary. J. ACM, 58:18:1--18:24, July 2011. Google ScholarDigital Library
- Jonathan Katz, Andrew Miller, and Elaine Shi. Pseudonymous broadcast and secure computation from cryptographic puzzles. Cryptology ePrint Archive, Report 2014/857, 2014. http://eprint.iacr.org/2014/857.Google Scholar
- Christian Decker, Jochen Seidel, and Roger Wattenhofer. Bitcoin meets strong consistency. In Proceedings of the 17th International Conference on Distributed Computing and Networking, ICDCN '16, pages 13:1--13:10, New York, NY, USA, 2016. ACM. Google ScholarDigital Library
- James Aspnes, Collin Jackson, and Arvind Krishnamurthy. Exposing computationally-challenged byzantine impostors. Department of Computer Science, Yale University, New Haven, CT, Tech. Rep, 2005.Google Scholar
- Marcin Andrychowicz and Stefan Dziembowski. Distributed cryptography based on the proofs of work. Cryptology ePrint Archive, Report 2014/796, 2014. http://eprint.iacr.org/2014/796.Google Scholar
- Wikipedia. Coupon collector's problem. https://en.wikipedia.org/wiki/Coupon_collector%27s_problem.Google Scholar
- Donald J. Newman. The double dixie cup problem. The American Mathematical Monthly, 67(1):58--61, 1960.Google ScholarCross Ref
- Christina Garman, Matthew Green, and Ian Miers. Decentralized anonymous credentials. Cryptology ePrint Archive, Report 2013/622, 2013. http://eprint.iacr.org/.Google Scholar
- Seth Gilbert and Nancy Lynch. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News, 33(2):51--59, June 2002. Google ScholarDigital Library
- Seth Gilbert and Nancy Lynch. Perspectives on the cap theorem. Computer, 45(2):30--36, February 2012. Google ScholarDigital Library
Index Terms
- A Secure Sharding Protocol For Open Blockchains
Recommendations
Improvements to Secure Computation with Penalties
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications SecurityMotivated by the impossibility of achieving fairness in secure computation [Cleve, STOC 1986], recent works study a model of fairness in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty ...
Founding Secure Computation on Blockchains
Advances in Cryptology – EUROCRYPT 2019AbstractWe study the foundations of secure computation in the blockchain-hybrid model, where a blockchain – modeled as a global functionality – is available as an Oracle to all the participants of a cryptographic protocol. We demonstrate both destructive ...
Amortizing Secure Computation with Penalties
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications SecurityMotivated by the impossibility of achieving fairness in secure computation [Cleve, STOC 1986], recent works study a model of fairness in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty ...
Comments