Visão geral
Uma árvore de Merkle (também chamada de árvore de hash) é uma estrutura de dados inventada por Ralph Merkle em 1979 que permite a verificação eficiente e segura do conteúdo de grandes conjuntos de dados. No Bitcoin, as árvores de Merkle são usadas para organizar todas as transações dentro de um bloco em uma estrutura hierárquica de hashes, culminando em uma única raiz Merkle armazenada no cabeçalho do bloco.
Estrutura
Nível 3 (Raiz): H(ABCD)
/ \
Nível 2: H(AB) H(CD)
/ \ / \
Nível 1: H(A) H(B) H(C) H(D)
| | | |
Nível 0: Tx A Tx B Tx C Tx D
(Folhas)
H() = hash SHA-256 duplo
Cada folha é o hash de uma transação. Cada nó interno é o hash de seus dois filhos concatenados. Isso continua subindo a árvore até que reste um único hash raiz.
Eficiência das provas Merkle
A principal vantagem das árvores de Merkle é que você pode provar que uma transação está incluída em um bloco sem baixar todas as transações. Uma prova Merkle para uma transação em um bloco com N transações requer apenas log2(N) hashes.
Para provar que Tx B está no bloco, você precisa:
1. H(A) — irmão no nível 1
2. H(CD) — irmão no nível 2
3. Raiz Merkle para comparar
Verificar: H(H(H(A) + H(B)) + H(CD)) == Raiz Merkle
Para um bloco com 4.000 transações, uma prova Merkle requer apenas cerca de 12 hashes em vez de todos os 4.000 hashes de transação. Isso permite que clientes SPV verifiquem a inclusão de transações com largura de banda mínima.
Equívocos comuns
As árvores de Merkle não criptografam dados — elas apenas fornecem verificação de integridade. Qualquer pessoa pode ver as transações; a árvore de Merkle simplesmente permite uma prova eficiente de que uma determinada transação foi incluída. Além disso, a implementação da árvore de Merkle do Bitcoin usa SHA-256 duplo (hasheando duas vezes), não SHA-256 simples.