💻 computer science

MHOT: Height-Optimized Authenticated Data Structure for Blockchain State Commitment

O artigo apresenta o \textsc{Mhot}, uma estrutura de dados autenticada com altura otimizada que substitui a Merkle Patricia Trie do Ethereum por indexação de bits discriminativa e provas hierárquicas para alcançar uma altura de árvore mínima, melhorar drasticamente o rendimento e o tamanho das provas, e fornecer resistência robusta contra ataques Nurgle sem exigir configuração confiável.

Autores originais: Sipeng Xie, Qianhong Wu, Minghang Li, Qiyuan Gao, Bo Qin, Qin Wang

Publicado 2026-06-11

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Sipeng Xie, Qianhong Wu, Minghang Li, Qiyuan Gao, Bo Qin, Qin Wang

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine uma blockchain como uma biblioteca massiva e global onde cada livro (transação) altera o estado de todo o edifício. Para provar que a biblioteca está organizada corretamente, os bibliotecários (validadores) têm que verificar um gigantesco "Índice" digital chamado State Root (Raiz de Estado).

Atualmente, a blockchain Ethereum utiliza um sistema chamado Merkle Patricia Trie (MPT). Imagine isso como um arquivo de gavetas onde cada gaveta é rotulada com um prefixo específico (como "A", "B", "C"). Se você quiser encontrar um arquivo, segue as letras. Mas aqui está o problema: se alguém adicionar um novo arquivo que compartilha um prefixo longo e monótono (como "A-B-C-D-E-F..."), o sistema tem que dividir a gaveta, adicionar mais prateleiras e tornar o caminho para o arquivo muito mais longo.

Este é o "Ataque Nurgle". É como uma pegadinha maliciosa de um brincalhão que sabe exatamente como o arquivo funciona. Eles podem inundar o sistema com arquivos que compartilham prefixos longos, forçando o sistema a construir uma torre de gavetas alta e instável apenas para armazenar alguns novos itens. Isso retarda toda a biblioteca e custa uma fortuna em energia (gas) para manter, mesmo que o brincalhão não pague quase nada.

A Nova Solução: MHOT (O Sistema de Arquivos "Inteligente")

Os autores apresentam o MHOT, uma nova forma de organizar esses dados que resolve o problema sem precisar de nenhuma nova matemática mágica ou de confiar em um terceiro.

Veja como o MHOT funciona, usando analogias simples:

1. Pare de seguir o Prefixo, Comece a Encontrar a Diferença

O sistema antigo (MPT) olha para as primeiras letras de um nome e diz: "Ah, isso vai na caixa 'A'". Se dois nomes começam com "Alex", eles vão na mesma caixa, mesmo que um seja "Alex" e o outro seja "Alexander".

O MHOT é mais inteligente. Ele pergunta: "Onde esses nomes realmente diferem?"

Se você tem "Alex" e "Alexander", o MHOT não se importa com o "Alex" compartilhado. Ele procura pela primeira letra onde eles se dividem (o 'n' vs. o 'a').
Ele constrói um "nó composto" (uma super-gaveta) que contém muitos itens de uma vez, organizados pelos bits exatos que os tornam únicos.
O Resultado: Não importa quantos nomes semelhantes você adicione, a torre não fica mais alta. Ela permanece curta e estável porque só se divide quando realmente precisa, não apenas porque há um prefixo compartilhado.

2. O Recibo de "Dois Níveis" (Provas Hierárquicas)

Quando você quer provar que um arquivo existe no sistema antigo, o bibliotecário tem que lhe entregar um recibo listando cada um dos arquivos irmãos em todas as gavetas pelas quais você passou. Se uma gaveta contém 32 arquivos, o recibo é enorme e pesado.

O MHOT utiliza um Recibo de Dois Níveis:

Nível 1: A estrutura principal da biblioteca.
Nível 2: Dentro de cada super-gaveta, os arquivos são organizados em sua própria mini-árvore.
A Magia: Em vez de listar todos os 32 irmãos, o recibo só precisa listar alguns hashes "irmãos" da mini-árvore (como um atalho logarítmico).
O Resultado: A prova (recibo) torna-se muito menor e mais leve, tornando a verificação mais rápida.

3. O Caminhão de Entrega em "Lote" (Batch Commit)

No sistema antigo, toda vez que você solta um único arquivo, o bibliotecário tem que recalcular o hash (a impressão digital digital) para cada uma das gavetas até o topo. Isso é como dirigir um caminhão de entrega até o correio para cada única carta.

O MHOT utiliza um Pipeline em Lote:

Ele coleta todas as mudanças de um bloco inteiro de tempo.
Ele calcula as impressões digitais em paralelo (como ter uma equipe de trabalhadores processando diferentes andares ao mesmo tempo).
Ele só escreve o estado final atualizado no disco rígido uma única vez.
O Resultado: A biblioteca processa as atualizações 9 vezes mais rápido e escreve 4 vezes menos dados no disco.

Por Que Isso Importa (Os Resultados)

O artigo testou o MHOT contra o sistema atual da Ethereum e alguns outros sistemas experimentais:

Velocidade: O MHOT é até 9 vezes mais rápido ao gravar novos dados.
Eficiência: Ele desperdiça 4 vezes menos espaço de armazenamento (Amplificação de Escrita).
Tamanho da Prova: Os "recibos" são 2 vezes menores, tornando mais fácil para dispositivos leves (como celulares) verificar a blockchain.
Segurança: Quando o brincalhão "Nurgle" tentou quebrar o sistema inundando-o com chaves semelhantes, o MHOT bloqueou completamente o ataque (0% de taxa de sucesso). O sistema antigo colapsou sob o ataque (99,97% de taxa de sucesso para o atacante).

A Conclusão

O artigo argumenta que não precisamos de uma nova magia criptográfica complexa (como configurações confiáveis ou matemática sofisticada) para resolver os problemas de escalabilidade da blockchain. Em vez disso, só precisamos de uma estrutura de dados melhor. Ao organizar os dados com base em onde as coisas realmente diferem, em vez de o que elas compartilham, e ao usar recibos inteligentes de "dois níveis", o MHOT torna a blockchain mais rápida, barata e imune a um tipo de ataque que a assombra há anos.

É um lembrete de que, às vezes, a melhor solução não é uma nova super-arma, mas uma maneira mais inteligente de organizar o arquivo.

Resumo Técnico: MHOT – Estrutura de Dados Autenticada com Altura Otimizada para Compromisso de Estado de Blockchain

1. Declaração do Problema

Em sistemas de blockchain modernos, particularmente o Ethereum, o cálculo da raiz de estado consome aproximadamente 70–80% do tempo total de processamento de blocos. A atual estrutura de dados autenticada (ADS) canônica, a Merkle Patricia Trie (MPT), sofre de duas limitações críticas:

Vulnerabilidade Estrutural a Ataques Nurgle: A MPT utiliza indexação de prefixo fixo, onde cada nível da árvore consome um número fixo de bits de chave contíguos. Esta estrutura permite que adversários explorem prefixos comuns longos (via colisões de hash) para inflar artificialmente as profundidades de caminho. O "ataque Nurgle" (S&P '24) demonstra que um atacante pode degradar o desempenho do sistema e aumentar os custos de I/O com um custo de gas negligenciável, forçando a trie a materializar caminhos comprimidos em estruturas mais profundas.
O Trade-off Span–Prova: Para mitigar o crescimento da profundidade, poder-se-ia aumentar o "span" (bits consumidos por nível). No entanto, em tries baseadas em prefixos, aumentar o span aumenta exponencialmente o "fanout" (número de slots de filhos, $2^{span}$ ). Isso força um trade-off: um span alto limita a altura, mas infla o tamanho do nó e da prova exponencialmente; um span baixo mantém as provas compactas, mas deixa a árvore vulnerável a ataques de aprofundamento.

Alternativas existentes como Verkle Tries ou LVMT desacoplam o tamanho da prova do fanout usando compromissos vetoriais (técnicas algébricas). No entanto, estas requerem cerimônias de configuração confiável (trusted setup), introduzem custos de verificação aritmética mais elevados e frequentemente carecem de suporte nativo para provas de intervalo essenciais para a sincronização de estado.

2. Metodologia: MHOT

Os autores propõem o MHOT (Height-Optimized Authenticated Data Structure), uma ADS persistente, baseada em hash, que alcança a otimização de altura sem configuração confiável ou criptografia especializada. O MHOT adapta a estrutura da Height-Optimized Trie (HOT) para o compromisso de estado de blockchain através de quatro mecanismos principais:

A. Indexação por Bit Discriminativo (Fundação Estrutural)

Ao contrário da MPT, que consome prefixos contíguos fixos, o MHOT ramifica-se em bits discriminativos. Um bit discriminativo é uma posição onde pelo menos duas chaves em uma subárvore diferem.

Acoplamento Linear: Esta abordagem acopla o span e o fanout linearmente, em vez de exponencialmente. Um nó composto com fanout $k$ consome até $k-1$ bits discriminativos, enquanto um nó baseado em prefixo com o mesmo fanout requer $\log_2 k$ bits contíguos.
Span Adaptativo: Os nós adaptam-se à distribuição real das chaves. Regiões densas usam menos bits por nó; regiões esparsas usam mais. Isso garante uma altura de árvore comprovadamente mínima para qualquer conjunto de chaves dado.
Resistência ao Nurgle: Como a estrutura é determinada pela divergência real das chaves e não por prefixos fixos, inserções adversárias com prefixos compartilhados são absorvidas via reestruturação interna (ex: leaf pushdown, parent pull-up) sem necessariamente aumentar a altura global da árvore.

B. Provas Hierárquicas (Otimização de Prova)

Hashear diretamente $k$ filhos em um nó composto resultaria em um overhead de prova de $O(k)$ . O MHOT introduz uma construção Merkle de dois níveis:

Camada Inter-nó: Conecta nós compostos.
Camada Intra-nó: Cada nó composto mantém uma árvore Merkle binária interna sobre seus $k$ filhos.

Resultado: Provar a participação de um filho requer apenas $O(\log k)$ hashes de irmãos da árvore interna, reduzindo o tamanho da prova de uma dependência linear no fanout para logarítmica. Isso quebra a dependência linear do tamanho da prova em relação ao span.

C. Persistência Endereçável por Conteúdo

Para suportar o compromisso de estado de blockchain, o MHOT modifica o design original do HOT em memória:

Identificadores Determinísticos: Os nós são identificados pelo hash de seu conteúdo serializado (endereçável por conteúdo), garantindo determinismo estrutural (conjuntos de chaves idênticos geram árvores idênticas) e minimização de confiança.
Copy-on-Write (CoW): Modificações criam novos nós, invalidando os hashes dos ancestrais, consistente com a semântica de estado de blockchain.

D. Pipeline de Commit em Lote

Para lidar com o custo computacional de rehashear caminhos:

Hashing Diferido: O cálculo de hash é adiado até o commit do bloco. Os nós usam IDs temporários durante a fase de transação.
Paralelismo Estratificado por Altura: No momento do commit, os nós são finalizados em lotes ordenados por altura (folhas para a raiz). Como nós na mesma altura não possuem dependências de dados, os cálculos de hash podem ser paralelizados eficientemente.
Layout Amigável a LSM-Tree: As chaves de armazenamento são prefixadas pelo número da versão do bloco e altura, permitindo gravações sequenciais em lote e compactação eficiente.

3. Principais Contribuições

Identificação do Acoplamento Span–Prova: O artigo identifica o acoplamento exponencial entre span e fanout em tries baseadas em prefixos como a causa raiz da incapacidade de garantir simultaneamente uma altura máxima limitada e provas compactas.
Instanciação do MHOT: Adapta o HOT para uso em blockchain, fornecendo uma ADS com altura otimizada que resiste a distribuições de chaves adversárias via rastreamento de bits discriminativos e nós compostos de alto fanout, utilizando apenas compromissos de hash padrão.
Provas Hierárquicas: Uma construção Merkle de dois níveis inovadora que reduz o overhead de prova por nó de $O(k)$ para $O(\log k)$ , permitindo provas compactas mesmo com alto fanout.
HOT Persistente: Resolve o problema aberto de implantação em disco do HOT ao introduzir indexação endereçável por conteúdo e um pipeline de commit paralelo.
Avaliação Abrangente: Benchmarks do MHOT contra MPT, RainBlock e LVMT sob cargas de trabalho da mainnet do Ethereum.

4. Resultados Experimentais

Avaliado em cargas de trabalho da mainnet do Ethereum (blocos 13.5M–13.51M) e conjuntos de dados sintéticos:

Throughput: O MHOT alcança até 9× mais throughput de escrita que a MPT (260k ops/s vs. 29k ops/s com 100k chaves) e supera o LVMT e o RainBlock por margens significativas.
Amplificação de Escrita: O MHOT reduz a amplificação de escrita em 4× comparado à MPT (0.9–1.6 vs. 2.7–4.8) devido ao flushing em lote e redução da profundidade da árvore.
Tamanho da Prova: As provas do MHOT são 2× menores que as da MPT (1.1–1.4 KB vs. 2.3–2.9 KB) devido à sua estrutura de prova hierárquica.
Resistência ao Ataque Nurgle: Sob um cenário de ataque de pior caso onde um adversário controla todo o orçamento de gas de um bloco (aprox. 15.000 inserções):
- MPT: 99.97% de taxa de sucesso em aumentar as profundidades das chaves alvo.
- MHOT: 0% de taxa de sucesso. A estrutura absorve colisões via reestruturação interna sem propagar aumentos de profundidade.
Latência de Verificação: A verificação do MHOT opera em microssegundos (comparável à MPT), enquanto o LVMT (dependendo de pairings KZG) incorre em latência de milissegundos (3–4 ordens de magnitude mais lenta).

5. Significância e Alegações

O artigo argumenta que a otimização de altura, em vez da introdução de novas primitivas criptográficas, é a abstração chave para um compromisso de estado de blockchain escalável e resiliente a ataques.

Soluções Estruturais vs. Criptográficas: O MHOT demonstra que os trade-offs entre altura da árvore, tamanho da prova e resistência a ataques podem ser resolvidos estruturalmente através da indexação por bits discriminativos, evitando as suposições de confiança e os altos custos de verificação de esquemas de compromisso vetorial (Verkle, LVMT).
Imediata Implementabilidade: Ao depender exclusivamente de funções de hash padrão (Keccak-256 ou Blake3) e princípios de autenticação Merkle existentes, o MHOT oferece um caminho para melhor desempenho e segurança sem exigir hard forks para cerimônias de configuração confiável ou mudanças na verificação algébrica.
Resiliência: Os resultados sugerem que otimizar a altura e a adaptabilidade da estrutura de dados é suficiente para neutralizar o vetor de ataque Nurgle, que anteriormente parecia exigir contramedidas econômicas ou criptográficas.

Os autores concluem que o design cuidadoso da estrutura de dados pode melhorar fundamentalmente a escalabilidade e a robustez do compromisso de estado de blockchain, oferecendo uma alternativa prática ao padrão atual da MPT.