Utilização de Grafos de Nilcatenation na Identificação de Transações para Pruning em Blockchains
Abstract
blockchain technology was consolidated with its use in various areas of knowledge, mainly in the context of cryptocurrencies. However, there are still limitations to its wide adoption in various applications. A relevant limitation is the increasing size of blockchains, which causes both storage problems and leads to an increasing need for node synchronization time. In this context, this paper studies a solution for pruning in blockchains. This technique consists of removing transactions from the network without compromising the consistency of the blockchain. The proposed solution is based on nilcatenation graphs, whose objective is to identify a subgraph that can be removed without impiring the consistency of the network. Experimental results show that the proposed solution can more accurately identify transactions that can be removed (reduced up to 20% of the total transactions), when compared to current techniques (reduced up to 5% of the total transactions) that seek to find transaction cycles in these graphs to be removed.
References
Biggs, N., Lloyd, E. K., and Wilson, R. J. (1986). Graph Theory, 1736-1936. Oxford University Press.
Blockchain.com, t. . B. S. (2023).
Buterin, V. (2014). AOs, DACs, DAS and more: An incomplete terminology guide. [link].
Géraud, R., Naccache, D., and Roşie, R. (2017). Twisting lattice and graph techniques to compress transactional ledgers. In International Conference on Security and Privacy in Communication Systems, pages 108–127. Springer.
Gordon, N. (2020). A survey of blockchain storage requirement mitigation techniques.
Karp, R. M. (2011). Computational complexity of combinatorial and graph-theoretic problems. In Theoretical Computer Science, pages 97–184. Springer.
Nakamoto, S. (2009). Bitcoin: A peer-to-peer electronic cash system. [link].
Palm, E., Schelén, O., and Bodin, U. (2018). Selective blockchain transaction pruning and state derivability. In 2018 Crypto Valley Conference on Blockchain Technology (CVCBT), pages 31–40. IEEE.
Pech, M. (2017). Blockchains: How they work and why they’ll change the world. IEEE Spectrum.
Quan, L., Huang, Q., Zhang, S., and Wang, Z. (2019). Downsampling blockchain algorithm. In IEEE INFOCOM 2019-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pages 342–347. IEEE.
Subramanian, H. (2018). Decentralized blockchain-based electronic marketplaces. Communications of the ACM, 61(1):78–84.
Tapscott, D. and Tapscott, A. (2016). Blockchain revolution: How the technology behind bitcoin is changing money, business and the world. Portfolio Penguin.
Tarjan, R. (1971). Depth-first search and linear graph algorithms. In 12th Annual Symposium on Switching and Automata Theory (swat 1971), pages 114–121.
Wang, R. L. (2004). A genetic algorithm for subset sum problem. Neurocomputing, 57:463–468.
