Árvores de Merkle

Uma árvore de Merkle binária

Em criptografia e ciência da computação, árvores de dispersão ou árvores de Merkle são um tipo de estrutura de dados que contém uma árvore de informações resumidas sobre um pedaço maior de dados - por exemplo, um arquivo - usado para verificar seu conteúdo. Árvores de Merkle são uma extensão das listas de dispersão, que por sua vez são uma extensão de Hash. Árvores de Merkle nas quais a função de dispersão subjacente é Tiger são freqüentemente chamadas de árvores Tiger ou árvores de dispersão Tiger.

Usos

Árvores de Merkle podem ser usadas para proteger qualquer tipo de dados armazenados, manuseados e transferidos dentro e entre computadores. Atualmente, o principal uso de árvores de Merkle é para garantir que blocos de dados recebidos de outros pares em uma rede ponto-a-ponto são recebidos intactos e inalterados, e até mesmo para verificar se os outros pares não mentem e enviam blocos falsos. Sugestões foram feitas para o uso de árvores de Merkle em sistemas de Computação Confiável. A Sun Microsystems tem usado árvores de dispersão no sistema de arquivos ZFS. Árvores de Merkle são usadas no protocolo Google Wave (que foi descontinuado em 2010), sistema de controle de versão distribuído Git e em sistema de backup tarsnap.

Árvores de Merkle foram inventadas em 1979 por Ralph Merkle. O objetivo inicial era tornar possível o manuseio eficientemente de muitas assinaturas de Lamport de tempo-único. Assinaturas de Lamport são consideradas seguras, mesmo se computadores quânticos tornarem-se realidade. Infelizmente, cada chave de Lamport só pode ser usada para assinar uma única mensagem. Mas combinadas com árvores de Merkle, elas podem ser usadas para muitas mensagens e, em seguida, tornar-se um esquema de assinatura digital bastante eficiente.

Como as árvores de Merkle funcionam

Uma árvore de Merkle é uma árvore binária de dispersão onde as folhas são separações de blocos de dados em um arquivo ou conjunto de arquivos. Os nós localizados mais acima na árvore são as dispersões de seus respectivos filhos. Por exemplo, na imagem dispersão 0 é o resultado da dispersão 0-0 e depois, dispersão 0-1 hash. Ou seja, dispersão 0 = dispersão(dispersão 0-0 || dispersão 0-1), onde || denota a concatenação.

As implementações de árvore de Merkle na sua maioria são binárias (dois nós filhos em cada nó), mas podem muito bem usar mais nós filhos em cada nó.

Normalmente, uma função de embaralhamento criptográfico como SHA-1, Whirlpool, ou Tiger é usada para a dispersão. Se a árvore de Merkle só precisa proteger contra danos involuntários, somas de verificação (checksums) muito menos seguras, como CRCs podem ser usadas.

No topo de uma árvore de Merkle há uma dispersão superior (ou dispersão de raiz ou dispersão mestre). Antes de baixar um arquivo em uma rede p2p, na maioria dos casos, a dispersão superior é adquirida de uma fonte confiável, por exemplo, um amigo ou um site reconhecido por ter boas recomendações de arquivos para download. Quando a dispersão superior está disponível, a árvore de Merkle pode ser recebida de qualquer fonte não-confiável, como qualquer ponto na rede p2p. Aí então a árvore de Merkle recebida é comparada com a dispersão superior confiável, e verifica-se se a árvore de Merkle está danificada ou falsa, outra árvore de Merkle vinda de outra fonte será testada até o programa encontrar uma que corresponda à dispersão superior.

A principal diferença de uma lista de dispersão é que pode-se baixar um ramo da árvore de Merkle por vez e a integridade de cada ramo pode ser verificada imediatamente, embora a árvore toda ainda não esteja disponível. Isto pode ser uma vantagem, uma vez que é eficiente separar os arquivos em blocos muito pequenos de dados, de modo que apenas pequenos blocos tenham que ser baixados novamente caso sejam danificados. Se o arquivo de dispersão é muito grande, a árvore de Merkle ou lista de dispersão torna-se bastante grande. Mas se for uma árvore, um pequeno ramo pode ser baixado rapidamente, a integridade do ramo pode ser verificada, e então o download de blocos de dados pode ser iniciado.

Existem vários truques adicionais, benefícios e detalhes sobre árvores de Merkle. Veja as referências e ligações externas abaixo para informações mais detalhadas.

Árvore de dispersão Tiger

Árvore de dispersão Tiger é uma forma amplamente utilizada da árvore de Merkle. Árvore de dispersão Tiger usa uma árvore de dispersão (dois nós filhos em cada nó), geralmente, tem um tamanho de bloco de dados de 1024-bytes e são seguras pela criptografia de dispersão Tiger.

Árvores de dispersão Tiger são usadas nos protocolos de compartilhamento de arquivos Direct Connect P2P, Gnutella e Gnutella2 e em aplicações de compartilhamento de arquivos, tais quais Phex, BearShare, LimeWire, Shareaza, DC++ e Valknut.

Ver também

• Tabela de dispersão

Referências

• Merkle tree patent 4,309,569 (em inglês) – Explica tanto a estrutura da árvore de dispersão quanto seu uso para o manuseio de muitas assinaturas descartáveis.
• Tree Hash EXchange format (THEX) (em inglês) – Uma descrição detalhada de árvores Tiger.
• Efficient Use of Merkle Trees (em inglês) – RSA Data Security, Inc. Explicação do propósito original das árvores de Merkle: lidar com muitas assinaturas descartáveis de Lamport.

Ligações externas

• https://web.archive.org/web/20070317045032/http://www.codeproject.com/cs/algorithms/thexcs.asp – código-fonte Tiger Tree Hash (TTH) em C# – por Gil Schmidt (em inglês)
• http://sourceforge.net/projects/tigertree/ – Implementações Tiger Tree Hash (TTH) em C e Java (em inglês)
• RHash, ferramenta de linha de comando de código aberto, que pode calcular ligações TTH. (em inglês)