Árvore de Merkle

Nesse artigo iremos aprender a criar uma aplicação utilizando a estrutura da árvore de merkle através da criação de um contrato inteligente.

O que é Árvore de Merkle?

É uma estrutura de dados dividida em várias camadas cuja finalidade é relacionar cada nó com uma única raiz associada a eles. Para conseguir isso, cada nó deve ser identificado com um identificador exclusivo (de hash). Esses nós iniciais, chamados de nós filhos (folha), são então associados a um nó superior chamado nó pai (ramificação). O nó pai terá um identificador exclusivo resultante do hash de seus nós filhos. Essa estrutura se repete até que o nó raiz ou raiz Merkle (raiz Merkle), cuja impressão está associada a todos os nós da árvore.

Graças a esta estrutura única, as árvores Merkle possibilitam relacionar uma grande quantidade de dados em um único ponto (Raiz Merkle). Desta forma, a verificação e validação desses dados podem se tornar muito eficientes, tendo que verificar apenas a Raiz Merkle em vez de toda a estrutura.

Trecho retirado do site academy.bitme.com, você pode ler o artigo completo em bit2me Academy

Aplicação da Árvore de Merkle na blockchain

Na blockchain, a árvore de merkle permite que você prove criptograficamente que um elemento está contido em um conjunto de elementos sem que seja necessário revelar o conjunto inteiro.

Confira abaixo um exemplo de aplicação:

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

contract MerkleProof {
    function verify(
        bytes32[] memory proof,
        bytes32 root,
        bytes32 leaf,
        uint index
    ) public pure returns (bool) {
        bytes32 hash = leaf;

        for (uint i = 0; i < proof.length; i++) {
            bytes32 proofElement = proof[i];

            if (index % 2 == 0) {
                hash = keccak256(abi.encodePacked(hash, proofElement));
            } else {
                hash = keccak256(abi.encodePacked(proofElement, hash));
            }

            index = index / 2;
        }

        return hash == root;
    }
}

contract TestMerkleProof is MerkleProof {
    bytes32[] public hashes;

    constructor() {
        string[4] memory transactions = [
            "alice -> bob",
            "bob -> dave",
            "carol -> alice",
            "dave -> bob"
        ];

        for (uint i = 0; i < transactions.length; i++) {
            hashes.push(keccak256(abi.encodePacked(transactions[i])));
        }

        uint n = transactions.length;
        uint offset = 0;

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

    function getRoot() public view returns (bytes32) {
        return hashes[hashes.length - 1];
    }

    /* verify
    3rd leaf
    0xdca3326ad7e8121bf9cf9c12333e6b2271abe823ec9edfe42f813b1e768fa57b

    root
    0xcc086fcc038189b4641db2cc4f1de3bb132aefbd65d510d817591550937818c7

    index
    2

    proof
    0x8da9e1c820f9dbd1589fd6585872bc1063588625729e7ab0797cfc63a00bd950
    0x995788ffc103b987ad50f5e5707fd094419eb12d9552cc423bd0cd86a3861433
    */
}

Testar no Remix