Document Type : Research Article
Authors
School of Electrical and Computer Engineering, University of Tehran, Tehran, Iran
Abstract
The future of the IoT requires new methods of payment that can handle millions of transactions per second. IOTA cryptocurrency aims at providing such a solution. It uses a consensus algorithm based on directed acyclic graphs (DAG) that is called Tangle. A tip selection algorithm (TSA) is a part of Tangle that determine which unconfirmed blocks (tips) should be confirmed by new blocks. There is always a chance that a small number of valid blocks never get confirmed and become stale. If a significant part of blocks become stale, the Tangle is considered unstable. In this paper, we mathematically prove that a TSA is stable in all transaction rates if and only if the probability of selecting all tips is at least $1/2n$ in which $n$ is the total number of tips. Accordingly, we demonstrate that the MCMC TSA used in IOTA would not be stable in high transaction rates.
Keywords
[1] Satoshi Nakamoto. Bitcoin: A peer-to-peer electic cash system, 2008.
[2] Ittay Eyal, Adem Efe Gencer, Emin Gun Sirer, and Robbert Van Renesse. Bitcoin-ng: A scalable blockchain protocol. In 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16), pages 45–59, Santa Clara, CA, March 2016. USENIX Association.
[3] Joseph Poon and Thaddeus Dryja. The bitcoin lightning network: Scalable off-chain instant payments, 2016.
[4] Ali Dorri, Salil S. Kanhere, Raja Jurdak, and Praveen Gauravaram. Lsb: A lightweight scalable blockchain for iot security and anonymity. Journal of Parallel and Distributed Computing, 134:180–197, 2019.
[5] Yonatan Sompolinsky and Aviv Zohar. Secure high-rate transaction processing in bitcoin. In International Conference on Financial Cryptography and Data Security, pages 507–527. Springer, 2015.
[6] Serguei Popov. The tangle, 2016.
[7] Chenxing Li, Peilun Li, Dong Zhou, Wei Xu, Fan Long, and Andrew Yao. Scaling nakamoto consensus to thousands of transactions per second, 2018.
[8] Joanna Moubarak, Maroun Chamoun, and Eric Filiol. On distributed ledgers security and illegal uses. Future Generation Computer Systems, 113:183–195, 2020.
[9] Yoad Lewenberg, Yonatan Sompolinsky, and Aviv Zohar. Inclusive block chain protocols. In International Conference on Financial Cryptography and Data Security, pages 528–547. Springer, 2015.
[10] Paulo C. Bartolomeu, Emanuel Vieira, and Joaquim Ferreira. Iota feasibility and perspectives for enabling vehicular applications. In 2018 IEEE Globecom Workshops (GC Wkshps), pages 1–7, Dec 2018.
[11] Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar. Spectre: A fast and scalable cryptocurrency protocol. Cryptology ePrint Archive, Report 2016/1159, 2016. https://eprint.iacr. org/2016/1159.
[12] Yonatan Sompolinsky and Aviv Zohar. Phantom: A scalable blockdag protocol. Cryptology ePrint Archive, Report 2018/104, 2018. https://eprint.iacr.org/2018/104.
[13] Wellington Fernandes Silvano and Roderval Marcelino. Iota tangle: A cryptocurrency to communicate internet-of-things data. Future Generation Computer Systems, 112:307–319, 2020.
[14] Quentin Bramas. The stability and the security of the tangle, 2018.
[15] Anton Churyumov. Byteball: A decentralized system for storage and transfer of value, 2016.
[16] Colin LeMahieu. Nano: A feeless distributed cryptocurrency network, 2018.
[17] Yary Ribero and Daniel Raissar. Dagcoin whitepaper, 2020.
[18] Leemon Baird. The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance. Technical Report Tech Reports SWIRLDS-TR-2016-01, Swirlds, 2016.
[19] Yonatan Sompolinsky and Aviv Zohar. Accelerating bitcoin’s transaction processing. fast money grows on trees, not chains. Cryptology ePrint Archive, Report 2013/881, 2013. https://eprint.iacr.org/2013/881.
[20] Gavin Wood et al. Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper, 151(2014):1–32, 2014.
[21] Xavier Boyen, Christopher Carr, and Thomas Haines. Graphchain: A blockchain-free scalable decentralised ledger. In Proceedings of the 2nd ACM Workshop on Blockchains, Cryptocurrencies, and Contracts, BCC ’18, page 21–33, New
York, NY, USA, 2018. Association for Computing Machinery.
[22] Serguei Popov, Olivia Saa, and Paulo Finardi. Equilibria in the tangle. arXiv preprint arXiv:1712.05385, 2017.
[23] Bartosz Kusmierz, Philip Staupe, and Alon Gal.Extracting tangle properties in continuous time via large-scale simulations, 2018.
[24] Andrew Cullen, Pietro Ferraro, Christopher King, and Robert Shorten. On the resilience of dag-based distributed ledgers in iot applications. IEEE Internet of Things Journal, 7(8):7112–7122, Aug 2020.
[25] P. Ferraro, C. King, and R. Shorten. On the stability of unverified transactions in a dag-based distributed ledger. IEEE Transactions on Automatic Control, 65(9):3772–3783, 2020.
[26] Alon Elmaliah. iotaledger/iri, 2020.
[27] Gal Rogozinski. iotaledger/iri, 2020.
[28] Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1996.
[29] Juan Garay, Aggelos Kiayias, and Nikos Leonardos. The bitcoin backbone protocol: Analysis and applications. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology - EURO-CRYPT 2015, pages 281–310, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.
[30] Lei Yang, Vivek Bagaria, Gerui Wang, Mohammad Alizadeh, David Tse, Giulia Fanti, and Pramod Viswanath. Prism: Scaling bitcoin by 10,000x, 2020.
[31] Bartosz Kusmierz, William Sanders, Andreas Penzkofer, Angelo Capossele, and Alon Gal. Properties of the tangle for uniform random and random walk tip selection. In 2019 IEEE International Conference on Blockchain (Blockchain), pages 228–236, July 2019.
[32] Vitalik Buterin, Diego Hernandez, Thor Kamphefner, Khiem Pham, Zhi Qiao, Danny Ryan, Juhyeok Sin, Ying Wang, and Yan X Zhang. Combining ghost and casper, 2020.
[2] Ittay Eyal, Adem Efe Gencer, Emin Gun Sirer, and Robbert Van Renesse. Bitcoin-ng: A scalable blockchain protocol. In 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16), pages 45–59, Santa Clara, CA, March 2016. USENIX Association.
[3] Joseph Poon and Thaddeus Dryja. The bitcoin lightning network: Scalable off-chain instant payments, 2016.
[4] Ali Dorri, Salil S. Kanhere, Raja Jurdak, and Praveen Gauravaram. Lsb: A lightweight scalable blockchain for iot security and anonymity. Journal of Parallel and Distributed Computing, 134:180–197, 2019.
[5] Yonatan Sompolinsky and Aviv Zohar. Secure high-rate transaction processing in bitcoin. In International Conference on Financial Cryptography and Data Security, pages 507–527. Springer, 2015.
[6] Serguei Popov. The tangle, 2016.
[7] Chenxing Li, Peilun Li, Dong Zhou, Wei Xu, Fan Long, and Andrew Yao. Scaling nakamoto consensus to thousands of transactions per second, 2018.
[8] Joanna Moubarak, Maroun Chamoun, and Eric Filiol. On distributed ledgers security and illegal uses. Future Generation Computer Systems, 113:183–195, 2020.
[9] Yoad Lewenberg, Yonatan Sompolinsky, and Aviv Zohar. Inclusive block chain protocols. In International Conference on Financial Cryptography and Data Security, pages 528–547. Springer, 2015.
[10] Paulo C. Bartolomeu, Emanuel Vieira, and Joaquim Ferreira. Iota feasibility and perspectives for enabling vehicular applications. In 2018 IEEE Globecom Workshops (GC Wkshps), pages 1–7, Dec 2018.
[11] Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar. Spectre: A fast and scalable cryptocurrency protocol. Cryptology ePrint Archive, Report 2016/1159, 2016. https://eprint.iacr. org/2016/1159.
[12] Yonatan Sompolinsky and Aviv Zohar. Phantom: A scalable blockdag protocol. Cryptology ePrint Archive, Report 2018/104, 2018. https://eprint.iacr.org/2018/104.
[13] Wellington Fernandes Silvano and Roderval Marcelino. Iota tangle: A cryptocurrency to communicate internet-of-things data. Future Generation Computer Systems, 112:307–319, 2020.
[14] Quentin Bramas. The stability and the security of the tangle, 2018.
[15] Anton Churyumov. Byteball: A decentralized system for storage and transfer of value, 2016.
[16] Colin LeMahieu. Nano: A feeless distributed cryptocurrency network, 2018.
[17] Yary Ribero and Daniel Raissar. Dagcoin whitepaper, 2020.
[18] Leemon Baird. The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance. Technical Report Tech Reports SWIRLDS-TR-2016-01, Swirlds, 2016.
[19] Yonatan Sompolinsky and Aviv Zohar. Accelerating bitcoin’s transaction processing. fast money grows on trees, not chains. Cryptology ePrint Archive, Report 2013/881, 2013. https://eprint.iacr.org/2013/881.
[20] Gavin Wood et al. Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper, 151(2014):1–32, 2014.
[21] Xavier Boyen, Christopher Carr, and Thomas Haines. Graphchain: A blockchain-free scalable decentralised ledger. In Proceedings of the 2nd ACM Workshop on Blockchains, Cryptocurrencies, and Contracts, BCC ’18, page 21–33, New
York, NY, USA, 2018. Association for Computing Machinery.
[22] Serguei Popov, Olivia Saa, and Paulo Finardi. Equilibria in the tangle. arXiv preprint arXiv:1712.05385, 2017.
[23] Bartosz Kusmierz, Philip Staupe, and Alon Gal.Extracting tangle properties in continuous time via large-scale simulations, 2018.
[24] Andrew Cullen, Pietro Ferraro, Christopher King, and Robert Shorten. On the resilience of dag-based distributed ledgers in iot applications. IEEE Internet of Things Journal, 7(8):7112–7122, Aug 2020.
[25] P. Ferraro, C. King, and R. Shorten. On the stability of unverified transactions in a dag-based distributed ledger. IEEE Transactions on Automatic Control, 65(9):3772–3783, 2020.
[26] Alon Elmaliah. iotaledger/iri, 2020.
[27] Gal Rogozinski. iotaledger/iri, 2020.
[28] Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1996.
[29] Juan Garay, Aggelos Kiayias, and Nikos Leonardos. The bitcoin backbone protocol: Analysis and applications. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology - EURO-CRYPT 2015, pages 281–310, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.
[30] Lei Yang, Vivek Bagaria, Gerui Wang, Mohammad Alizadeh, David Tse, Giulia Fanti, and Pramod Viswanath. Prism: Scaling bitcoin by 10,000x, 2020.
[31] Bartosz Kusmierz, William Sanders, Andreas Penzkofer, Angelo Capossele, and Alon Gal. Properties of the tangle for uniform random and random walk tip selection. In 2019 IEEE International Conference on Blockchain (Blockchain), pages 228–236, July 2019.
[32] Vitalik Buterin, Diego Hernandez, Thor Kamphefner, Khiem Pham, Zhi Qiao, Danny Ryan, Juhyeok Sin, Ying Wang, and Yan X Zhang. Combining ghost and casper, 2020.
)