Hoje vamos analisar um tópico interessante — a implementação da árvore Merkle com um contrato inteligente (Solidity). Para que você pode usá-la? Bem, por exemplo, você pode implementar a lógica whitelist para uma coleção NFT.

Introdução

Suponha que tenhamos 8 transações combinadas em um bloco. Precisamos ter certeza:

1 ) que este bloco não foi adulterado

2 ) todas as transações nele foram realmente representadas

Para fazer dessa maneira - > Para cada transação ( ou qualquer outro dado ), calcule seu hash ( H _₁, H _₂ ... ). Isso será considerado como uma “folha”. Em seguida, produzimos um novo hash ( camada 2 ) com base em dois hashes e assim por diante em cada nível, até o hash Root.

Como podemos garantir que a transação ( por exemplo T _₅ ) está realmente no bloco ( Root )?

Temos um hash raiz que usaremos para comparar.

1. Pegamos os hashes da transação ( H _₅ e H _₆ ) e recalculamos o hash H _₅ - _₆
2. Tomamos os hashes ( H _₅ - _₆ e H _₇ - _₈ ) e recalculamos H _₅ - _₆ - _₇ - ₈
3. Tome ( H _₁ - _₂ - _₃ - _₄ e H _₅ - _₆ - _₇ - _₈ ), conte o novo hash raiz e compare-o com o original Raiz

Se os hashes raiz corresponderem , a transação estará correta e nada será alterado nela.

Observe que não precisamos de todos os hashes da transação.

Importante: O número de folhas na árvore não é arbitrário e é limitado ao seguinte valor 2ⁿ

O exemplo na foto a seguir não funcionará

Árvore Merkle escrevendo código da Solidity

A seguir, é apresentado o código que implementa uma árvore de hash usando um contrato inteligente escrito em solidity. Não tenha medo, vou desmontar esse código, abaixo 😉

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

contract MerkleTree {

//          ROOT
//        /      \
//    H1-2        H3-4
//    /  \        /  \
//  H1    H2    H3    H4 
//   |     |     |     |
//  TX1   TX2   TX3   TX4   

    bytes32[] public hashes;
    string[4] transactions = [
        "TX1: Scherlock -> John",
        "TX2: John -> Sherlock",
        "TX3: John -> Mary",
        "TX4: Mary -> Sherlock"
    ];

    constructor() {
        for(uint i = 0; i < transactions.length; i++) {
            hashes.push(makeHash(transactions[i]));  // H1 H2 H3 H4
        }

        uint count = transactions.length;  // number of leaves
        uint offset = 0;

        while(count > 0) {
            for(uint i = 0; i < count - 1; i += 2) {
                hashes.push(keccak256(
                    abi.encodePacked(
                        hashes[offset + i], hashes[offset + i + 1]
                    )
                ));
            }
            offset += count;
            count = count / 2;
        }
    }

    function verify(string memory transaction, uint index, bytes32 root, bytes32[] memory proof) public pure returns(bool) {
        bytes32 hash = makeHash(transaction);  // get hash transactions for check
        for(uint i = 0; i < proof.length; i++) {
            bytes32 element = proof[i];
            if(index % 2 == 0) {
                hash = keccak256(abi.encodePacked(hash, element));
            } else {
                hash = keccak256(abi.encodePacked(element, hash));
            }
            index = index / 2;
        }
        return hash == root;
    }

    function makeHash(string memory input) public pure returns(bytes32) {
        return keccak256(
            abi.encodePacked(input)
        );
    }
}

Considere as variáveis:

bytes32[] public hashes — uma matriz onde armazenaremos todos os nossos hashes, que representarão a árvore;

string[4] transactions = [...] — uma matriz de _strings _que imitará as transações. Isso pode ser qualquer tipo de dado;

Vamos escrever uma função de hash:

function makeHash(string memory input) public pure returns(bytes32){       
 return keccak256(
   abi.encodePacked(input)
 );
}

keccak256 retorna um hash com um comprimento predefinido de 32 bytes, mas ele precisa passar um valor codificado corretamente, o qual obtemos com abi.encodePacked ( ).

Produziremos hashes no construtor:

1. Passe pela matriz de transações, faça hashes para todas as transações e adicione-os à matriz de hashes

constructor() {       
 for(uint i = 0; i < transactions.length; i++) {                  
   hashes.push(makeHash(transactions[i]));  // H1 H2 H3 H4       
 }
 ...
}

2). Agora precisamos combinar esses hashes.

Lembre-se de que o número de folhas é dividido pela metade em cada nível sucessivo.

Conte quantas folhas existem em um determinado momento uint count = transactions.length //number of leaves.

Vamos implementar o while(count > 0) loop {…} . Como vamos para um nível superior, precisamos adicionar uma nova variável uint offset = 0;

Para a combinação de hashes, implementamos o _for() _loop. A foto mostra a iteração do loop ( vermelho — primeira, segunda; verde — terceira; roxo — quarta iteração, não será executada ).

Foi assim que calculamos o hash Root e outros.

Verificar função

Vamos implementar a função de validação de transação. Suponha que queremos saber a autenticidade de T _₃ ( H _₃ ). Precisamos de 2 hashes ( H _₄, H _₁ - _₂ ) para fazer isso. Vamos armazenar esses elementos na matriz bytes32[] memory proof .

A variável bytes32 hash = makeHash(transaction); armazena o hash da transação que vamos verificar.

Em seguida, escrevemos um for() loop para percorrer a matriz de provas.

Observe que estamos verificando o element ( índice ) para paridade, porque se o elemento for par ( exemplo H _₃ ), temos que levar o elemento para a direita ( H _₄ ) e vice-versa para construir o hash total.

Dependendo da paridade do elemento, preenchemos as seguintes condições if-else:

function verify(...) public pure returns(bool) {     
 bytes32 hash = makeHash(transaction);
 for(uint i = 0; i < proof.length; i++) {           
   bytes32 element = proof[i]; 
   if(index % 2 == 0) {               
     hash = keccak256(abi.encodePacked(hash, element));
   } else {              
     hash = keccak256(abi.encodePacked(element, hash));
   }

Então temos que ir para o nível acima. Lembramos que isso reduz pela metade o número de elementos, por isso adicionamos index = index / 2; . No final, comparamos o hash Root original com o que contamos return hash == root; .

Verificação de funcionalidade

Vá para Remix, crie um novo arquivo na pasta /contratos e copie/cole o código deste repositório (não se esqueça de colocar uma estrela ⭐).

1 ) Compile este contrato.

2 ) Implemente o contrato.

3 ) Tente verificar a transação

Vou verificar a transação com o índice 2.

Você pode obter os hashes pelo botão hashes (você escreve o índice do hash desejado na entrada) após a implementação.

O hash root será o último elemento na matriz de hashes.

A matriz de prova para a transação com o índice 2 ( H _₃ ) incluirá hashes H _₄ e H _₁ - _₂.

Eu recebi os seguintes dados:

// transação expm: "TX3: John -> Mary"
// índice: 2
// root: 0x4aebbc948c21be9df7ac8d63e2f1c6d9a58998d4edfba9b192a6f8d4d7d07958
// H4: 0x69a40d72d1258df801a7ae1e36dd586717a112334f8d9ca4664a339168874ef5
// H1-2: 0x83d2dbc9a1246936e38d7f1d4de7709616ac8c32e5159f4a79b5587800249d24

Se eu colocar esses valores na chamada verify function (verificar função), eu recebo true (verdade). Se houver a menor alteração em qualquer dado vamos obter false (falso).

Ufa, isso foi realmente muito, mas agora você entende como implementar e como a Árvore Merkle funciona em um contrato inteligente. No futuro, eu poderia desmontar a implementação da lista de permissões (whitelist, allow list) usando a árvore Merkle.

Aguardo suas reações e comentários

Importante: este código não é feito para o mundo real, leia este artigo se você quiser criar airdrop/whitelist para sua coleção

Este artigo foi escrito por Alexandr Kumancev, e traduzido por Diogo Jorge. O artigo original pode ser encontrado aqui.