Algoritmos de correspondência de padrões em blockchain para redução de taxas de rede

Resumo A blockchain recebeu uma vasta quantidade de atenção nos últimos anos e ainda está crescendo. A segunda geração de blockchain, como Ethereum, permite a execução de praticamente qualquer programa em EVM, tornando-se um protocolo global para aplicativos distribuídos. O deployment de código e cada operação realizada em EVM custam a taxa de rede chamada gás, cujo preço varia e pode ser significativo. É por isso que a otimização de código e algoritmos bem escolhidos são cruciais na programação na blockchain. Este artigo avalia o uso de gás de vários algoritmos exatos de correspondência de padrões na EVM. Também propomos uma implementação eficiente dos algoritmos na linguagem Solidity/YUL. Avaliamos as taxas de gás de todos os algoritmos para diferentes parâmetros (como comprimento do padrão, tamanho do alfabeto e tamanho do texto). Mostramos uma redução significativa na taxa de gás e no tempo de execução, com até 22 vezes menos uso de gás e 55 vezes mais rápido em comparação com o StringUtils (uma biblioteca popular de strings em Solidity).