Provas de Merkle

Todas as resoluções devolvidas pela API vêm com uma prova de Merkle. Ela permite-lhe confrontar a resposta com uma raiz de estado em vez de confiar no servidor que a enviou.

A árvore

O PiNS guarda todos os nomes numa árvore de Merkle esparsa compacta sobre um espaço de chaves de 128 bits. A chave de um nome são os primeiros 16 bytes de SHA-256(domain_name), pelo que os nomes se distribuem uniformemente e ninguém pode escolher onde o seu nome cai.

«Compacta» significa que uma folha fica à menor profundidade em que o prefixo da sua chave é único, em vez de a uma profundidade fixa de 128. Numa árvore com alguns milhares de nomes, a maioria das provas tem apenas uma dúzia larga de hashes — pequena o suficiente para ser verificada num telemóvel, numa extensão do navegador ou dentro de uma carteira.

Duas consequências que convém conhecer antes de escrever um verificador:

• O comprimento da prova varia. Leia proof_depth da resposta; nunca presuma um tamanho fixo.
• Uma subárvore vazia são 32 bytes a zero a qualquer altura. Por isso a raiz de uma árvore vazia é toda a zeros: um indexador acabado de inicializar que reporte 0000…0000 está correto, não avariado.

O que contém uma prova

Campo	Significado
merkle_proof	hashes irmãos, [0] o mais profundo (o mais próximo da folha)
proof_depth	número de irmãos — tem de ser igual a merkle_proof.length
proof_terminal	o que está no fim do caminho: Occupied, Vacant ou Blocked
smt_root	a raiz que esses irmãos reconstroem

Presença e ausência

É o terminal que permite a uma prova afirmar «este nome não está registado» de forma tão convincente como «está»:

• Occupied — no fim do caminho está a folha própria da chave. O nome existe, e o registo que lhe deram é o que está na árvore.
• Vacant — ali está uma subárvore vazia. O nome não está registado.
• Blocked — essa posição é ocupada pela folha de um nome diferente. O nome não está registado; a resposta traz o registo que bloqueia para que possa verificar que ele produz o hash da folha ali encontrada e que a sua chave partilha mesmo o prefixo.

Sem Blocked, um indexador poderia esconder um registo alegando que um lugar estava vazio. Como o registo que bloqueia é incluído na íntegra, pode verificar a alegação em vez de a aceitar.

Verificar

Transforme o registo numa folha através de hash e depois dobre os irmãos de volta até à raiz, usando os bits da chave para decidir esquerda ou direita em cada passo. Se chegar a smt_root, o registo é exatamente aquilo com que a árvore se compromete.

Fica ainda uma pergunta: será smt_root a raiz verdadeira? Responda-lhe perguntando ao contrato âncora na BNB Smart Chain. Ambos os passos, com código testado em Python, PHP e JavaScript, estão em Verificar provas.