Utilização de Grafos de Nilcatenation na Identificação de Transações para Pruning em Blockchains

Igor da Silva Bonomo; Eduardo Alchieri

doi:10.5753/wtf.2023.796

Igor da Silva Bonomo UnB
Eduardo Alchieri UnB

DOI: https://doi.org/10.5753/wtf.2023.796

Resumo

A tecnologia blockchain se consolidou com sua utilização em diversas áreas do conhecimento, tendo seu uso maior nas criptomoedas. Porém, ainda existem limitações para a sua ampla utilização em diversas aplicações. Uma limitação relevante é o tamanho crescente das blockchains, o que causa tanto problemas de armazenamento quanto leva a uma necessidade crescente de tempo para sincronização de nós. Neste contexto, este artigo estuda uma solução para pruning em blockchains. Essa técnica consiste em remover transações da rede sem prejudicar a consistência da blockchain. A solução proposta é baseada em grafos de nilcatenation, cujo objetivo é identificar um subgrafo que pode ser removido sem comprometer a consistência da rede. Resultados experimentais mostram que a solução proposta consegue identificar de forma mais precisa as transações que podem ser removidas (chegando a uma redução de até 20% das transações), quanto comparado com técnicas atuais (conseguiram fornecer até 5% de redução) que buscam encontrar ciclos de transações nestes grafos que podem ser removidas.

Referências

Amaral, C. A. T. et al. (2020). Algoritmos para o problema de nilcatenation com aplicação na detecção de lavagem de dinheiro em criptomoedas.

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 Roş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.