As árvores Merkle são usadas no mundo das criptomoedas como uma forma eficiente de provar a existência de um determinado valor dentro de um grande conjunto de valores e com armazenamento mínimo. Este artigo apresenta as árvores Merkle e mostra como as provas repetidas na mesma árvore podem ser reduzidas significativamente em tamanho armazenando vários níveis de ramificações em vez de apenas a raiz (conhecida como Merkle pollards).

Hashes

Uma função hash transforma um dado de tamanho variável (neste caso, o nome de uma fruta) em um valor de tamanho fixo (conhecido como hash). Um exemplo mostrando hashes de “Apple” e “Orange” é mostrado abaixo:

Figura 1: valores de hash

As funções de hash têm vários recursos, mas os mais importantes são que mesmo valores ligeiramente diferentes resultam em hashes muito diferentes, e que é matematicamente muito difícil ir do hash de volta ao valor (geralmente significando que não há método mais rápido do que adivinhar um valor, hash e ver se ele corresponde).

Árvores Merkle

Uma árvore Merkle é uma maneira de combinar vários valores e seus hashes para reduzi-los a um único valor de tamanho fixo.

No topo da árvore estão os valores, conhecidos como leaves (folhas). Cada folha é transformada em hash para criar uma ramificação de nível superior, e as ramificações adjacentes são agrupadas para criar as ramificações intermediárias. Eventualmente, isso resultará em um único hash, conhecido como raiz Merkle. Um exemplo gráfico de uma árvore Merkle é mostrado abaixo:

Figura 2: Uma árvore Merkle

O exemplo acima mostra uma árvore Merkle com 8 valores e 4 níveis; a raiz está na parte inferior rotulada d576…ffd9.

Como mencionado anteriormente, mesmo valores ligeiramente diferentes gerarão hashes muito diferentes. Esta mudança tem um impacto subsequente em todos os níveis da árvore e acabará por dar uma raiz diferente. Por exemplo, alterar o valor único “Peach” para “Pear” resulta em uma árvore Merkle alterada, conforme mostrado abaixo:

Figura 3: O impacto de uma única alteração na árvore (mostrado em cinza)

As árvores Merkle são reproduzíveis: dados os mesmos valores na mesma ordem, uma árvore Merkle sempre terá os mesmos hashes para os galhos e a raiz.

Caminhos Merkle

O caminho Merkle é simplesmente o conjunto de hashes do valor para a raiz Merkle. O exemplo abaixo mostra o caminho Merkle para o valor “Peach”:

Figura 4: O caminho Merkle para “Peach”

Provas Merkle

Uma prova Merkle é uma maneira de provar que um determinado valor faz parte de um conjunto de dados sem exigir que nenhum dos outros valores seja exposto.

Figura 5: Uma prova Merkle

Uma prova Merkle requer três coisas: um valor (mostrado em vermelho), os hashes intermediários (mostrado em verde) e a raiz Merkle (mostrado em azul). Para cada valor haverá um conjunto diferente de hashes intermediários.

As provas Merkle são comumente usadas em blockchains para mostrar que um valor está em um conjunto sem exigir que todo o conjunto seja armazenado na blockchain. Por exemplo, um contrato de token Ethereum pode ter um recurso de whitelist (lista de reservas) para permitir que contas selecionadas comprem tokens. Em vez de armazenar todas as contas da lista de permissões na blockchain, o que seria proibitivamente caro se houvesse muitos milhares de contas na lista de permissões, uma árvore Merkle das contas pode ser criada e apenas a raiz armazenada na blockchain.

Por exemplo, se a raiz for armazenada em um contrato inteligente, torna-se fácil para o contrato provar que uma conta está na lista de permissões: uma conta fornece os hashes intermediários (fornecidos de alguma maneira fora da cadeia pelo proprietário do contrato ao titular da conta) e o contrato inteligente faz o hash da conta com os hashes intermediários em ordem. Se o resultado corresponder à raiz Merkle, ele saberá que a conta está na lista de permissões.

Observe a relação entre os hashes no caminho Merkle e os hashes na prova mostrada nos dois últimos diagramas: cada hash na prova é irmão do hash no caminho no mesmo nível da árvore. Isso mostra graficamente que a prova permite recriar o caminho para o valor, e é por isso que o resultado final será a raiz Merkle.

Como pode ser visto acima, alguns benefícios do uso de provas Merkle são:

• o armazenamento on-chain necessário é muito menor do que se armazenar valores
• o conjunto completo de valores não é exposto ao armazená-los publicamente on-chain
• o custo de confirmar a presença de um valor específico no conjunto de valores pela confirmação de uma prova pode ser menor (mais rápido e mais barato) do que verificar o conjunto

Provas repetidas

No exemplo acima, cada conta envia apenas a única prova necessária para verificar se está na lista de permissões. Um uso alternativo de árvores Merkle é como parte de provas probabilísticas de conhecimento (comumente conhecidas como STARKs), onde cada prova aumenta a probabilidade de que o criador da árvore Merkle (conhecida como o prover) conheça todos os valores que compõem a árvore. Nesta situação, o prover geralmente gera centenas de provas contra uma única árvore Merkle contendo dezenas ou mesmo centenas de milhares de valores. A raiz Merkle e as provas são enviadas juntas para um verificador para confirmar sua validade.

Examinando provas repetidas no contexto de nosso exemplo original, abaixo estão três provas contra a mesma árvore:

Figuras 6,7,8: Provas repetidas usando a mesma raiz Merkle

Pode-se ver que, no total, enviar a raiz Merkle (uma vez) mais as provas envolve o envio de 10 hashes: um para a raiz e três para cada uma das provas.

Isso pode ser mais eficiente? Pode-se observar que no primeiro nível da árvore, onde existem apenas dois valores c0b7 … da30 e 6ff9 … 8e3d, as provas estão enviando um total de três hashes (um por prova). E se a raiz Merkle fosse estendida para fornecer não apenas o nível mais baixo, mas também o próximo nível acima?

Figuras 9,10,11: Provas repetidas usando uma raiz Merkle estendida

Pode-se ver que, no total, o envio da raiz Merkle estendida (uma vez) mais as provas agora envolve o envio de 9 hashes: três para a raiz e dois para cada uma das provas. Embora essa redução pareça pequena, ela aumenta significativamente à medida que o número de provas aumenta.

Merkle pollards

Chamamos uma raiz Merkle estendida de Merkle pollard. É definido como a raiz Merkle mais um número de níveis de ramificações intermediárias. A ordem de um Merkle pollard é o número de ramos acima da raiz que formam o pollard (um merkle pollard de ordem 0 de uma árvore é equivalente à raiz). Um Merkle pollard de ordem 1 contém um nível de ramificações intermediárias, conforme mostrado abaixo:

Figura 12: Uma ordem 1 Merkle pollard

Um Merkle pollard de ordem 2 contém dois níveis de ramificações intermediárias, conforme mostrado abaixo:

Figura 13: Uma ordem 2 Merkle pollard

Em situações onde há muitas provas repetidas contra a mesma árvore Merkle, usar um Merkle pollard diminui o tamanho da prova (já que há menos hashes por prova) e o tempo necessário para verificar a prova (pois há menos hashes necessários para ser calculado por verificação). A matemática para calcular a ordem ideal de um Merkle pollard é simplesmente o piso do logaritmo de base 2 do número de provas. Uma tabela de ordens inferiores, juntamente com a economia de espaço e tempo resultante para uma árvore de exemplo com 4.096 valores, é mostrada abaixo:

A economia com o uso de Merkle pollards pode aumentar rapidamente. Por exemplo, um teste de prova STARK usando raízes Merkle em 564 KB foi reduzido usando Merkle pollards para 346 KB, uma redução de 40%. Houve também reduções no tempo de transmissão e verificação da prova.

Exemplo de implementação

Uma implementação de uma árvore Merkle com pollards para a linguagem Go pode ser encontrada em https://github.com/wealdtech/go-merkletree.

Multiprovas esparsas de Merkle

As multiprovas esparsas de Merkle são uma alternativa ao pollarding que fornece provas com eficiência de espaço para vários valores na mesma árvore Merkle. As multiprovas esparsas de Merkle têm restrições e requisitos diferentes dos Merkle pollards e são examinadas em detalhes em um artigo separado.

Este artigo foi escrito por Jim McDonald e traduzido por Diogo Jorge. O artigo original pode ser encontrado aqui.