Merkle Tree

O que é uma árvore Merkle?

Uma árvore Merkle é uma estrutura de dados usada em aplicativos de ciência da computação. Em bitcoin e outras criptomoedas, Árvores Merkle servem para codificar dados de blockchain de forma mais eficiente e segura.

Eles também são chamados de "árvores hash binárias".

Quebrando a Árvore Merkle

No blockchain do bitcoin, um bloco de transações é executado por meio de um algoritmo para gerar um hash, que é uma sequência de números e letras que pode ser usada para verificar se um determinado conjunto de dados é o mesmo que o conjunto original de transações, mas não para obter o conjunto original de transações. O software do Bitcoin não executa todo o bloco de dados de transações - representando 10 minutos de transações em média - por meio da função hash de uma só vez, Contudo. Em vez, cada transação é hash, então, cada par de transações é concatenado e misturado, e assim por diante até que haja um hash para todo o bloco. (Se houver um número ímpar de transações, uma transação é duplicada e seu hash é concatenado com ele mesmo.)

Visualizado, esta estrutura se assemelha a uma árvore. No diagrama abaixo, "T" designa uma transação, "H" um hash. Observe que a imagem é altamente simplificada; um bloco médio contém mais de 500 transações, não oito.

Os hashes na linha inferior são chamados de "folhas, "os hashes intermediários como" branches, "e o hash no topo como a" raiz ". A raiz Merkle de um determinado bloco é armazenada no cabeçalho:por exemplo, a raiz Merkle do bloco # 482819 é e045b18e7a3d708d686717b4f44db2099aabcad9bebf968de5f7271b458f71c8. A raiz é combinada com outras informações (a versão do software, o hash do bloco anterior, o carimbo de data / hora, o alvo de dificuldade, e o nonce) e, em seguida, execute uma função hash para produzir o hash exclusivo do bloco:000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b089594 no caso do bloco # 482819. Este hash não está realmente incluído no bloco relevante, mas o próximo; é distinto da raiz Merkle.

A árvore Merkle é útil porque permite que os usuários verifiquem uma transação específica sem baixar o blockchain inteiro (mais de 350 gigabytes no final de junho de 2021). Por exemplo, digamos que você deseja verificar se a transação T _D está incluído no bloco do diagrama acima. Se você tiver o hash de raiz (H _ABCDEFGH ), o processo é como um jogo de sudoku:você consulta a rede sobre H _D , e retorna H _C , H _AB, e H _EFGH . A árvore Merkle permite que você verifique se tudo é contabilizado com três hashes:dado H _AB , H _C , H _EFGH, e a raiz H _ABCDEFGH , H _D (o único hash ausente) deve estar presente nos dados.

Árvores Merkle têm o nome de Ralph Merkle, que os propôs em um artigo de 1987 intitulado "Uma assinatura digital baseada em uma função de criptografia convencional". Merkle também inventou o hashing criptográfico.