Árvore Merkle - Merkle tree

Um exemplo de árvore hash binária. Hashes 0-0 e 0-1 são os valores de hash dos blocos de dados L1 e L2, respectivamente, e hash 0 é o hash da concatenação dos hashes 0-0 e 0-1.

Em criptografia e ciência da computação , uma árvore hash ou árvore Merkle é uma árvore em que cada nó folha é rotulado com o hash criptográfico de um bloco de dados, e cada nó não folha é rotulado com o hash criptográfico dos rótulos de seus nós filhos . As árvores de hash permitem a verificação eficiente e segura do conteúdo de grandes estruturas de dados . Árvores de hash são uma generalização de listas de hash e cadeias de hash .

Demonstrar que um nó folha é parte de uma determinada árvore hash binária requer a computação de um número de hashes proporcionais ao logaritmo do número de nós folha da árvore; isso contrasta com as listas hash, onde o número é proporcional ao próprio número de nós folha. As árvores Merkle são, portanto, um exemplo eficiente de esquema de compromisso criptográfico , no qual a raiz da árvore Merkle é vista como um compromisso e os nós de folha podem ser revelados e comprovados como parte do compromisso original.

O conceito de hash trees tem o nome de Ralph Merkle , que o patenteou em 1979.

Usos

As árvores de hash podem ser usadas para verificar qualquer tipo de dados armazenados, manipulados e transferidos dentro e entre computadores. Eles podem ajudar a garantir que os blocos de dados recebidos de outros pontos em uma rede ponto a ponto sejam recebidos intactos e inalterados e até mesmo a verificar se os outros pontos não mentem e enviam blocos falsos.

Árvores de hash são usadas na criptografia baseada em hash . Árvores de hash também são usadas nos sistemas de arquivos IPFS , Btrfs e ZFS (para combater a degradação de dados ); Protocolo Dat ; Protocolo Apache Wave ; Sistemas de controle de revisão distribuída Git e Mercurial ; o sistema de backup Tahoe-LAFS ; Zeronet ; as redes ponto a ponto Bitcoin e Ethereum ; a estrutura de Transparência de Certificados ; o gerenciador de pacotes Nix e descendentes como GNU Guix ; e vários sistemas NoSQL , como Apache Cassandra , Riak e Dynamo . Foram feitas sugestões para usar árvores de hash em sistemas de computação confiáveis .

A implementação inicial de Bitcoin de árvores Merkle por Satoshi Nakamoto aplica a etapa de compressão da função hash em um grau excessivo, o que é mitigado pelo uso de Árvores Fast Merkle.

Visão geral

Uma árvore hash é uma árvore de hashes em que as folhas são hashes de blocos de dados em, por exemplo, um arquivo ou conjunto de arquivos. Os nós mais acima na árvore são os hashes de seus respectivos filhos. Por exemplo, na imagem acima, o hash 0 é o resultado do hash da concatenação de hash 0-0 e hash 0-1 . Ou seja, hash 0 = hash (hash (0-0) + hash (0-1)) onde + denota concatenação.

A maioria das implementações de árvore de hash são binárias (dois nós filhos em cada nó), mas podem usar muito mais nós filhos em cada nó.

Normalmente, uma função de hash criptográfica , como SHA-2, é usada para o hashing. Se a árvore de hash precisar apenas proteger contra danos não intencionais, somas de verificação não seguras , como CRCs, podem ser usadas.

No topo de uma árvore hash há um hash superior (ou hash raiz ou hash mestre ). Antes de baixar um arquivo em uma rede p2p, na maioria dos casos, o hash principal é adquirido de uma fonte confiável, por exemplo, um amigo ou um site que é conhecido por ter boas recomendações de arquivos para baixar. Quando o hash superior está disponível, a árvore de hash pode ser recebida de qualquer fonte não confiável, como qualquer peer na rede p2p. Em seguida, a árvore de hash recebida é verificada em relação ao hash superior confiável e, se a árvore de hash estiver danificada ou falsa, outra árvore de hash de outra fonte será tentada até que o programa encontre uma que corresponda ao hash superior.

A principal diferença de uma lista hash é que um ramo da árvore hash pode ser baixado por vez e a integridade de cada ramo pode ser verificada imediatamente, mesmo que a árvore inteira ainda não esteja disponível. Por exemplo, na imagem, a integridade do bloco de dados L2 pode ser verificada imediatamente se a árvore já contém hash 0-0 e hash 1 por hash do bloco de dados e combinando iterativamente o resultado com hash 0-0 e então hash 1 e finalmente comparando o resultado com o hash superior . Da mesma forma, a integridade do bloco de dados L3 pode ser verificada se a árvore já tiver hash 1-1 e hash 0 . Isso pode ser uma vantagem, pois é eficiente dividir arquivos em blocos de dados muito pequenos, de forma que apenas pequenos blocos tenham que ser baixados novamente se forem danificados. Se o arquivo com hash for muito grande, essa árvore de hash ou lista de hash torna-se bastante grande. Mas se for uma árvore, um pequeno branch pode ser baixado rapidamente, a integridade do branch pode ser verificada e então o download dos blocos de dados pode começar.

Segundo ataque de pré-imagem

A raiz hash Merkle não indica a profundidade da árvore, permitindo um ataque de segunda pré-imagem em que um invasor cria um documento diferente do original que tem a mesma raiz hash Merkle. Para o exemplo acima, um invasor pode criar um novo documento contendo dois blocos de dados, onde o primeiro é hash 0-0 + hash 0-1 e o segundo é hash 1-0 + hash 1-1.

Uma correção simples é definida na Transparência do certificado : ao calcular hashes de nó folha, um byte 0x00 é adicionado aos dados de hash, enquanto 0x01 é adicionado ao cálculo de hashes de nó interno. Limitar o tamanho da árvore de hash é um pré-requisito de algumas provas formais de segurança e ajuda a tornar algumas provas mais restritas. Algumas implementações limitam a profundidade da árvore usando prefixos de profundidade de árvore de hash antes de hashes, portanto, qualquer cadeia de hash extraída é definida para ser válida apenas se o prefixo diminuir em cada etapa e ainda for positivo quando a folha for alcançada.

Hash de árvore tigre

O hash de árvore de tigre é uma forma amplamente usada de hash de árvore. Ele usa uma árvore hash binária (dois nós filhos em cada nó), geralmente tem um tamanho de bloco de dados de 1024 bytes e usa o hash Tiger .

Os hashes de árvore Tiger são usados nos protocolos de compartilhamento de arquivos P2P Gnutella , Gnutella2 e Direct Connect e em aplicativos de compartilhamento de arquivos como Phex , BearShare , LimeWire , Shareaza , DC ++ e Valknut.

Exemplo

Base32 :R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

URN :urn:tree:tiger:R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

ímã :magnet:?xt=urn:tree:tiger:R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

Veja também

Referências

Leitura adicional

Patente da árvore Merkle 4.309.569 - explica a estrutura da árvore hash e o uso dela para lidar com muitas assinaturas únicas
Formato Tree Hash EXchange (THEX) - uma descrição detalhada das árvores Tiger