Árvore de Merkle
Árvore de hashes em que cada nó interno é o hash dos seus filhos. Conhecendo só o hash da raiz, dá para verificar a integridade de todo o conteúdo da árvore. Ralph Merkle, 1979.
Base de: Bitcoin (a raiz de Merkle das transações em cada bloco), Git (o hash do commit é a raiz das árvores de hashes), IPFS (endereçamento por conteúdo), Certificate Transparency, BitTorrent (verificação de pedaços), ZFS/Btrfs (integridade do sistema de arquivos). Prova de Merkle: mostrar O(log n) hashes para provar que uma folha específica está incluída. Árvores de Merkle esparsas e árvores de Verkle são variantes modernas. A patente expirou em 2002 → explosão de adoção desde então.