No Solidity, às vezes você precisa adicionar uma grande quantidade de dados ao contrato inteligente. Adicionar uma grande quantidade de dados custa muito gás e, portanto, às vezes não é possível. Por exemplo, você precisa colocar milhares de usuários na lista de permissões ou adicionar milhares de endereços em um contrato de aquisição progressiva. Neste artigo, mostrarei como resolver essas tarefas com o uso de Árvores de Merkle.
Algoritmo da Árvore de Merkle
Árvores de Merkle nos permitem compactar uma lista de dados de qualquer tamanho em um único hash. O algoritmo de compactação funciona criando pares de elementos, somando os pares e fazendo hash das somas dos pares. Esse processo se repete, até que recebemos um único hash raiz.
Raiz da árvore de Merkle — Estrutura de hashes, terminando com um hash de todos os hashes na raiz.
Isso nos permite compactar uma lista de qualquer tamanho em um único hash de 256 bits. Mas, é claro, não podemos extrair o valor de volta do hash. Mas, felizmente, não precisamos fazer isto.
Ok, compactamos os dados em um hash. Agora podemos passar esse hash para um contrato inteligente. Isso nos custaria uma pequena quantidade de gás porque passar um hash de 256 bits em um contrato inteligente custa menos do que passar milhares deles. Agora estamos passando um.
Agora temos a lista (de forma compactada) em nosso contrato. Os valores na lista podem ser de qualquer tipo, seja um endereço, unidade ou um tipo mais complicado. Temos duas operações possíveis para fazer nesta lista e seus algoritmos correspondentes:
Modificar (Adicionar/Remover elemento, alterar detalhes de um elemento):
1) Alterar os dados off-chain
2) Recalcular o hash
3) Passar o novo hash para o contrato.
Leia (Verifique se o elemento existe, reúna os detalhes do elemento):
) Aceite como parâmetros: (dados do elemento, prova criptográfica de que este elemento está na lista)
2) Prove que este elemento existe no hash raiz, ou seja, na lista
3) Leia detalhes sobre o elemento passado como parâmetro.
4) Faça o que for necessário em seguida. (por exemplo, se for um contrato de aquisição progressiva - envie tokens para o endereço)
Sumário
1 . Algoritmo da Árvore de Merkle
2 . Como funciona a prova criptográfica para leitura
3 . A complexidade computacional da prova
4 . Conclusões
Como funciona a prova criptográfica para leitura
Como provamos que um elemento está na árvore de Merkle?
Hashes são necessários para obter o hash superior e provar que hK está no hash
Para provar que um elemento (hK na imagem) está no hash, temos que montar o hash novamente, e é obrigatório usar o hash hK durante a montagem porque queremos provar que hK está na lista. Se montarmos o hash superior com uso explícito do hash do elemento (hK), significa que o hash do elemento está contido no hash superior. Assim, uma função de contrato inteligente, que deseja verificar se um elemento está na raiz, deve recriar o hash raiz em si, usando o hash do elemento e outros hashes próximos a ele, e verificar se o resultado é o mesmo que o hash raiz. Se o resultado for o mesmo, significa que o hash raiz contém o hash do elemento.
Você pode pensar, qual é o sentido disso, se montarmos o hash novamente, precisaremos fazer o mesmo número de etapas, como o número de elementos, ou até mais? “Poderíamos ter adicionado esses elementos ao mapeamento”. Mas, na verdade, não precisamos de todos os elementos para montar o hash raiz. Como você pode ver na imagem acima, precisamos apenas ter esses nós (hashes), que nos permitem calcular o próximo nível da árvore.
Então, começamos com o elemento que devemos verificar — hK. Qual é o outro elemento que precisamos para ficar mais alto na árvore? Será o par do elemento (hL). Agora, subimos um nível - hKL. Qual é o próximo hash que precisamos? Do HIJ. Mas, como você pode ver, não precisávamos de hI e hJ, precisávamos apenas de hIJ. Então, salvamos 2 etapas — metade das etapas até agora. Tudo bem, temos hKL e hIJ, e chegamos ao próximo nível - hIJKL. Qual é o hash que precisamos para ficar mais alto? Do hMNOP, e podemos pegar seu hash, não precisamos do processamento extra dos 6 hashes abaixo dele. Mais uma vez, salvamos outra metade das etapas. Bom, vamos seguir, processamos hMNOP + hIJKL e agora estamos em hIJKLMNOP. O que nos custa para chegar ao próximo nível? uma etapa — combinando hIJKLMNOP com hABCDEFGH. Parabéns, chegamos ao hABCDEFGHIJKLMNOP agora, e podemos verificar, se o hash resultante é o mesmo, conforme registrado no contrato inteligente. Se for, significa que o hash hK está contido no hash hABCDEFGHIJKLMNOP superior.
A complexidade computacional da prova
Se precisarmos apenas de um passo para subir um nível na árvore - não é tão difícil calcular a complexidade. A complexidade de provar que um elemento está na árvore é a altura da árvore. Nesse caso, a altura é 4 e o número de elementos é 16. Isso significa que a complexidade de verificar se um elemento está na árvore é O(logN).
Isso significa que, no nível do contrato inteligente, as complexidades são as seguintes:
Modificar [lista inteira] - O(1) (precisamos substituir o valor do hash raiz em uma variável);
Ler - O(logN) (precisamos verificar se um elemento está na árvore, e então podemos continuar lendo seus detalhes e trabalhar com ele).
Exemplos
- Um contrato de aquisição progressiva, onde você precisa preencher 10.000 endereços que podem reivindicar tokens. Você não pode enviar 10.000 endereços nem para a matriz, nem para um mapeamento. Em vez disso, você pode armazenar os endereços off-chain e enviar apenas o hash raiz superior ao contrato inteligente. Quando uma pessoa deseja reivindicar, ela precisa apresentar a prova de Merkle (prova criptográfica que discutimos acima) e o valor de seu nó na árvore, que é o objeto {endereço, montante de tokens}. Depois de recriar o hash de nível superior com este objeto e outros hashes que a prova de Merkle contém, você pode ver se ele corresponde ao registrado no contrato inteligente. Se isso acontecer, significa que você pode ter certeza de que tal objeto {endereço, montante de tokens} existe na árvore. Em seguida, você pode enviar a eles os tokens que eles desejam reivindicar e registrar em um mapeamento que esse endereço já reivindicou seus tokens.
Nota: em um cenário on-chain tradicional, adicionar 10.000 endereços em um mapeamento custaria aproximadamente $ 50.000. Usando o hash raiz Merkle em vez de mapeamento, economizaríamos $ 50.000.
- Token NFT/ERC20, onde apenas os usuários da lista de permissões podem usar o token. Nesse cenário, poderíamos armazenar no hash, que armazena os endereços que podem usar o token, e toda vez que alguém quiser fazer uma transferência ou chamar alguma função que os marque como permitidos na lista de permissão, eles precisam fornecer uma prova de Merkle que comprove que eles estão na lista de permissões.
- Qualquer contrato com uma lista de permissão, não apenas NFT/ERC20, por exemplo, também uma plataforma de lançamento. Existem também muitas outras aplicações, estarei atualizando o artigo toda vez que encontrar um novo cenário em que possa ser útil.
Conclusões
Neste artigo, expliquei a você uma maneira de armazenar grandes quantidades de dados em uma única variável. Adicionar milhares de endereços, mesmo em uma única transação, a um mapeamento no Solidity custa muito gás, que pode até exceder os limites de gás do bloco. Na cadeia Ethereum, tal operação, se possível, custaria dezenas de milhares de dólares. Portanto, este padrão permite que os desenvolvedores trabalhem com grandes quantidades de dados no Solidity e encontrem soluções fáceis para problemas como listas de permissões de usuários para NFTs ou envio de endereços para um contrato de aquisição progressiva.
Este é apenas um padrão de correção de tal problema, e há mais. Vou explicá-los nos próximos artigos, e também vou criar artigos que mostrem nossa experiência na criação de contratos com estas soluções, que passaram por uma auditoria e foram para implantação, com alto número de usuários e alto Valor Total Bloqueado (TVL).
Se você tiver alguma dúvida sobre isto ou quiser que um projeto seja desenvolvido, você pode entrar em contato comigo:
Telegram — @RedDuckMV
Email — [email protected]
Este artigo foi escrito por RedDuck. Sua versão original pode ser encontrada aqui. Traduzido e adaptado por Marcelo Panegali.
Top comments (0)