Abstract
IOTA is one of the most promising distributed ledgers due to its performance, scalability, and fee-less transaction capability. The interaction with the IOTA ledger requires client software to perform complex logic. As this software is often running on low-power Internet of Things (IoT) devices, it is important for it to be highly optimized. Our work highlights the benefits of DAG-based distributed ledgers. We start with an overview of IOTA tip selection algorithms, including the Markov Chain Monte Carlo (MCMC) algorithm and time-based tip selection algorithm. The original IOTA Reference Implementation (IRI) of Cumulative Weight Calculation (CWC) is based on Breadth-First Search (BFS) algorithm. The main contribution of our paper is to show how the Depth-First Search (DFS) algorithm is a better alternative solution to the CWC problem. We describe a sample software implementation, a method for collecting a snapshot from the Tangle, and finally we discuss the experimental outcomes.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (white paper) (2008). https://bitcoin.org/bitcoin.pdf. Accessed 5 Feb 2022
Buterin, V.: A next-generation smart contract and decentralized application platform - Ethereum white paper (2014) https://www.ethereum.org/pdfs/EthereumWhitePaper.pdf. Accessed 5 Feb 2022
Halgamuge, M.N.: optimization framework for best approver selection method (BASM) and best tip selection method (BTSM) for IOTA tangle network: blockchain-enabled next generation Industrial IoT. Comput. Netw. 199, 108418 (2021). https://doi.org/10.1016/j.comnet.2021.108418
Cormen, T.H., Leiserson, C.E. Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge, pp. 594–623 (2009)
The official node software that runs on the IOTA Mainnet and Devnet. https://github.com/iotaledger/iri. Accessed 30 Dec 2021
IOTA - the tip selection process. https://legacy.docs.iota.org/docs/getting-started/0.1/network/tip-selection. Accessed 30 Dec 2021
Popov, S.: The tangle, April 30, 2018. Version 1.4.3. https://assets.ctfassets.net/r1dr6vzfxhev/2t4uxvsIqk0EUau6g2sw0g/45eae33637ca92f85dd9f4a3a218e1ec/iota1_4_3.pdf. Accessed 30 Dec 2021
Chrysalis (Path towards IOTA 1.5). https://blog.iota.org/chrysalis-b9906ec9d2de/. Accessed 5 Feb 2022
Towards full decentralization with IOTA 2.0, 2021. https://blog.iota.org/ path-towards-full-decentralization-with-iota-2-0/. Accessed 5 Feb 2022
Van Hijfte, S.: Blockchain Platforms: A Look at the Underbelly of Distributed Platforms. Morgan & Claypool Publishers, San Rafael, Synthesis Lectures on Computer Science (2020)
Ferenczi, A.: Sample implementation of DFS-based Algorithm for the CWC Problem in IOTA Distributed Ledger. https://github.com/andrasfe/iota-research. Accessed 5 Feb 2022
Wang, Q., Yu, J., Chen, S., Xiang, Y.: SoK: diving into DAG-based Blockchain Systems, CoRR, abs/2012.06128, 2020, arXiv:2012.06128. Accessed 20 Mar 2022
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Ferenczi, A., Bădică, C. (2022). An Implementation of Depth-First and Breadth-First Search Algorithms for Tip Selection in IOTA Distributed Ledger. In: Nguyen, N.T., Tran, T.K., Tukayev, U., Hong, TP., Trawiński, B., Szczerbicki, E. (eds) Intelligent Information and Database Systems. ACIIDS 2022. Lecture Notes in Computer Science(), vol 13757. Springer, Cham. https://doi.org/10.1007/978-3-031-21743-2_28
Download citation
DOI: https://doi.org/10.1007/978-3-031-21743-2_28
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-21742-5
Online ISBN: 978-3-031-21743-2
eBook Packages: Computer ScienceComputer Science (R0)