Árvore Merkle
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, as á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, no entanto. Em vez disso, cada transação é hash, então cada par de transações é concatenado e hash, 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.)
Visualizada, essa 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 “ramos” e o hash no topo como “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 timestamp, o alvo da dificuldade e o nonce) e, em seguida, é executada por meio de uma função hash para produzir o hash exclusivo do bloco: 000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b089594 no caso do bloco. Este hash não está realmente incluído no bloco relevante, mas no 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 130 gigabytes no final de agosto de 2017). Por exemplo, digamos que você queira verificar se a transação T D está incluída no bloco do diagrama acima. Se você tiver o hash raiz (H ABCDEFGH ), o processo é como um jogo de sudoku: você consulta a rede sobre H D e ele 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.
As árvores Merkle têm o nome de Ralph Merkle, que as 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.