A árvore de hash de Merkle prova que um registro está em um arquivo gigante com um punhado de hashes

Provar que um registro faz parte de um grande conjunto de dados normalmente significava enviar o conjunto de dados. Isso é impraticável para um backup, um arquivo de transações ou um cache web.

A tese de 1979 e o artigo de 1989 de Merkle descrevem uma árvore na qual cada bloco é transformado em hash e os hashes são emparelhados até que reste uma única raiz. Verificar um membro exige os log-n hashes no caminho, e não o arquivo.

A árvore transforma um teste de pertinência em um teste de igualdade sobre a raiz, e uma alteração em qualquer lugar aparece como um caminho alterado. É assim que toda uma estrutura de dados pode ser atestada sem que cada byte seja visto.

Comprometer-se com as folhas calculando hashes em pares até uma única raiz

O tamanho da prova é logarítmico, então a verificação permanece barata nos maiores conjuntos de dados.

A raiz compromete-se com o conjunto de dados inteiro, então qualquer adulteração é detectada.

Um verificador precisa apenas da raiz e de um caminho curto, e não da confiança no servidor.

É uma cadeia de hashes unidirecionais, então nenhuma informação sobre os dados é divulgada.

Para provar um fato sobre um todo enorme, não envie o todo. Reduza-o a um único digest, depois forneça apenas o caminho curto que conecta a única afirmação a esse digest.

As árvores de Merkle são fundamentais no Git, nas blockchains de criptomoedas, na transparência de certificados e no armazenamento distribuído. Elas permitem que um cliente verifique uma pequena parte de um grande armazenamento não autenticado confiando apenas em uma única raiz curta.