Carimbo temporal com árvore de Merkle: explicação

Se alguma vez se perguntou como um serviço pode registar temporalmente ficheiros na Bitcoin sem custos, quando uma transação Bitcoin não é gratuita, a resposta é uma árvore de Merkle. Vale a pena compreender este mecanismo, pois o compromisso que ele implica é a principal diferença entre os serviços de registo temporal disponíveis no mercado.

O problema que resolve

Escrever um hash num registo distribuído custa dinheiro — uma taxa de transação, paga na moeda da cadeia. Se cada ficheiro precisar da sua própria transação, cada registo temporal tem um custo mínimo fixo.

Agrupar muitos hashes numa única transação elimina esse custo mínimo. A dificuldade reside em fazer isso mantendo a capacidade de qualquer pessoa provar que o seu hash específico estava no grupo, sem publicar todo o lote.

Como funciona uma árvore de Merkle

Pegue num conjunto de hashes. Agrupe-os aos pares e faça o hash de cada par. Volte a agrupar os resultados e faça o hash desses novos pares. Continue até restar apenas um hash.

h(A)  h(B)   h(C)  h(D)
   \  /         \  /
  h(AB)         h(CD)
      \        /
       h(ABCD)   ← a raiz de Merkle

Esse valor final é a raiz de Merkle, e compromete-se com todas as entradas. Altere qualquer um dos hashes originais e a raiz muda completamente.

Apenas a raiz vai para a cadeia. Uma transação, independentemente do número de ficheiros no lote.

Provar que o seu ficheiro foi incluído

Para demonstrar que h(A) está sob a raiz, não precisa da árvore inteira. Precisa apenas dos irmãos ao longo do caminho desde a sua folha até ao topo — neste caso, h(B) e h(CD). Qualquer pessoa pode recalcular:

h( h( h(A), h(B) ), h(CD) ) == a raiz na cadeia?

Essa pequena lista de irmãos é a prova de Merkle ou prova de inclusão. Para um lote de um milhão de ficheiros, são cerca de vinte hashes, porque o comprimento do caminho cresce com o logaritmo do tamanho do lote, e não com o próprio lote.

Isto é genuinamente elegante. É o mecanismo subjacente ao OpenTimestamps e à maioria dos carimbos temporais gratuitos.

O que perde

Três coisas, todas operacionais e não criptográficas.

Deve guardar o ficheiro de prova. A cadeia contém a raiz, não o seu hash. Sem o caminho dos irmãos, não há forma de ligar o seu ficheiro à transação. Perde a prova e o registo temporal desaparece — a transação sozinha não lhe será útil.

Há geralmente um atraso e um passo extra. Os lotes fecham segundo um calendário. Até que o lote seja confirmado e validado, a sua prova está incompleta e, em alguns desenhos, deve regressar mais tarde para a "atualizar". Muitas pessoas nunca o fazem e descobrem anos depois.

A verificação exige explicação. Recalcular um caminho de Merkle é uma operação simples para um programador, mas uma surpresa desagradável para qualquer outra pessoa. Um registo cuja verificação requer um tutorial é um registo mais fraco perante um público não técnico.

A alternativa: uma transação cada

A outra abordagem consiste em escrever cada hash na sua própria transação. É o que fazemos: o hash do seu conteúdo vai para os dados de entrada de uma transação Ethereum dedicada, onde qualquer pessoa o pode ler no Etherscan usando "Ver como UTF-8".

Nenhuma das opções é criptograficamente mais forte. Uma prova de Merkle é exatamente tão sólida quanto uma escrita direta. A diferença reside inteiramente no que acontece depois, com uma pessoa que não é si, a segurar um artefacto que não compreende.

Qual escolher

Se está a registar temporalmente em volume, tem conforto técnico e é fiável na guarda dos ficheiros, o agrupamento é excelente e o preço é imbatível.

Se está a registar temporalmente um pequeno número de documentos importantes e o eventual destinatário é um cliente, uma seguradora ou um tribunal, pagar por uma escrita direta compra-lhe uma prova sem riscos e sem necessidade de explicações.

O agrupamento é também a forma sensata de oferecer um nível gratuito, informação útil ao comparar preços: um serviço que cobra centavos por certificado está quase certamente a usar agrupamento, e um que cobra dólares provavelmente não o está.