Como implementar uma árvore Merkle no Solidity

Uma árvore Merkle é uma árvore binária que permite verificar de forma eficiente e segura o conteúdo de grandes estruturas de dados. O conceito desta árvore foi proposto e patenteado em 1982 por Ralph Merkle, um criptógrafo americano.

O comprimento do hash permanece o mesmo para qualquer quantidade de dados de entrada. Os vértices folhas contêm hashes de blocos de dados, enquanto os vértices internos incluem hashes da adição de valores em dois vértices filhos. Por sua vez, o vértice raiz compreende o hash de todo o conjunto de dados.

Teoria

Inicialmente, existe um conjunto de dados que não estão de forma alguma relacionados entre si. Para cada bloco de dados (no contexto de uma blockchain de transação), precisamos calcular um hash do bloco. O número de blocos de dados deve ser 2^N , porque à medida que a árvore é construída, os blocos anteriores são hash em pares a cada iteração. Um par de hashes é então agrupado e um novo hash é criado com base neles. O hash continuará enquanto houver algo para agrupar em cada nível e irá parar quando sobrar apenas um par do qual o hash raiz – a raiz Merkle – é obtido.

H(1-2) = keccak256(H(1) + H(2))

H(3-4) = keccak256(H(3) + H(4))

H(5-6) = keccak256(H(5) + H(6))

H(7-8) = keccak256(H(7) + H(8))

H(1-2-3-4) = keccak256(H(1-2) + H(3-4))

H(5-6-7-8) = keccak256(H(5-6) + H(7-8))

H(1-2-3-4-5-6-7-8) = keccak256(H(1-2-3-4) + H(5-6-7-8))

Assim que tivermos a raiz, podemos validar os dados. Se o hash raiz corresponder ao hash original, está tudo bem, os dados são válidos. Também é possível verificar com eficiência se determinados dados estão presentes na estrutura em árvore.

Digamos que queremos verificar se o hash H2 está presente na árvore. A prova será uma matriz de dados: H1 , H3-4 , H5-6-7-8 . Graças a esses hashes, podemos reconstruir o hash raiz:

H(1-2-3-4-5-6-7-8) = keccak256(keccak256(keccak256(H(1) + H(2)) + H(3-4)) + H(5-6-7-8))

Em seguida, comparamos o hash resultante com o original. Se corresponderem, significa que o hash H2 está presente na árvore.

Prática

Vamos agora ver como implementar uma árvore Merkle e validação de dados no Solidity.

Para simplificar, escreveremos o array de transações diretamente no blockchain, bem como o array de hashes. Como usaremos a função integrada keccak256 , que retorna um hash de 32 bytes, o tipo de dados da matriz de hashes será bytes32 . A matriz também terá um comprimento dinâmico. Em geral, o comprimento do array de hashes não será igual ao comprimento do array de transações, porque ele conterá os hashes produzidos. Poderíamos calcular o comprimento antecipadamente, mas por uma questão de simplificação do código não o faremos. Se desejar, você pode tornar public cada um desses arrays e ler os hashes das transações.

Produziremos hashes no construtor. O primeiro passo é contar os hashes dos blocos com transactions no loop. Então, em cada nível da árvore, o número de hashes é reduzido por um fator de 2. Como armazenaremos os hashes na matriz de hashes, os deslocamentos do índice devem ser armazenados separadamente. O iterador no loop interno é incrementado em 2 porque pegaremos alguns elementos ao calcular e adicionar hashes. Em abi.encodePacked desta vez adicionaremos 2 hashes cada um, aos quais definiremos os índices corretamente: para o elemento esquerdo – o valor do deslocamento de deslocamento atual + o índice no nível atual da árvore, e para o elemento direito – o mesmo + 1.

Então construímos a árvore, mas o interesse consiste em validar os dados. Para fazer isso, vamos escrever uma função validateTransaction que recebe uma transação e seu índice. Infelizmente, o Solidity não possui um método find para arrays, então é mais fácil apenas passar o índice da transação.

Primeiro, vamos calcular o hash da transação e criar um array de provas. Encontramos o número de provas dependendo do comprimento da matriz de transação e definimos o comprimento proofsIndexes . Depois disso, em cada nível da árvore, encontramos o elemento necessário, dependendo do índice, pegando o elemento direito ou esquerdo, tendo em conta os deslocamentos nos hashes . Em seguida, percorremos a matriz de índices de prova, verificando a paridade do índice e calculando o hash dependendo se o elemento está à esquerda ou à direita no par. Finalmente, comparamos o hash resultante com o hash raiz e retornamos o resultado.

Aplicativo

Existem várias aplicações de uma árvore Merkle em blockchain.

• Armazenamento de transações : No Bitcoin, por exemplo, um bloco de transação armazena apenas o merkle_root de suas transações. Isso reduz o tamanho do bloco e a carga na rede. Depois de acumular um certo número de transações, é possível excluir transações antigas para economizar espaço, mas os próprios blocos permanecem inalterados porque armazenam apenas a raiz da árvore.
• Mineração : Um bloco de bitcoin consiste em duas partes – o cabeçalho do bloco e a lista de transações. Para evitar ter que recalcular os hashes da transação a cada vez, eles são alinhados em uma árvore Merkle, após a qual o cabeçalho do bloco é hash em vez de todo o bloco, e um número nonce aleatório é obtido. Quando o bloco é enviado para outros nós, a raiz da lista de transações é calculada e, se não corresponder à raiz do cabeçalho, o bloco é rejeitado.
• Verificação : A essência da verificação é auditar sem precisar baixar todo o blockchain. O processo é bastante simplificado e também permite confirmar a existência de dados sem divulgar informações sobre os dados, o que pode ser útil para verificar informações sensíveis.

Resumo

Sem as árvores Merkle, os blockchains seriam muito complicados e as provas Merkle permitiriam a verificação econômica da autenticidade dos dados.

As árvores Merkle são usadas ativamente em blockchains (por exemplo, Bitcoin, Ethereum) para armazenar transações de forma eficiente, mas esta não é a única aplicação. Por exemplo, após o colapso da bolsa FTX, muitas bolsas implementaram um mecanismo de Prova de Reserva, que utiliza uma árvore Merkle.