Árvores de Verkle

As Verkle Trees (um composto de "Vector commitment" e "Merkle Trees") são uma estrutura de dados que pode ser usada para melhorar os nós do Ethereum para que possam parar de armazenar grandes quantidades de dados de estado sem perder a capacidade de validar blocos.

Sem estado

As Verkle Trees são uma etapa essencial no caminho para clientes Ethereum sem estado. Os clientes sem estado são aqueles que não precisam armazenar todo o banco de dados de estado para validar os blocos recebidos. Em vez de usar a própria cópia local do estado do Ethereum para verificar os blocos, os clientes sem estado usam uma "testemunha" dos dados de estado que chegam com o bloco. Uma testemunha é uma coleção de partes individuais dos dados de estado necessários para executar um conjunto específico de transações e uma prova criptográfica de que a testemunha é realmente parte dos dados completos. A testemunha é usada em vez do banco de dados do estado. Para que isso funcione, as testemunhas precisam ser muito pequenas, de modo que possam ser transmitidas com segurança pela rede a tempo de serem processadas pelos validadores em um espaço de 12 segundos. A estrutura de dados de estado atual não é adequada, porque as testemunhas são muito grandes. As Verkle Trees resolvem esse problema ao permitir testemunhas pequenas, removendo uma das principais barreiras aos clientes sem estado.

O que é uma testemunha e por que precisamos dela?

A verificação de um bloco significa reexecutar as transações contidas no bloco, aplicar as alterações na trie de estado do Ethereum e calcular o novo hash raiz. Um bloco verificado é aquele cujo hash raiz de estado calculado é idêntico ao fornecido com o bloco (porque isso significa que o proponente do bloco realmente fez o cálculo que diz ter feito). Nos clientes Ethereum atuais, a atualização do estado exige acesso a toda a trie do estado, que é uma estrutura de dados grande que precisa ser armazenada localmente. Uma testemunha contém apenas os fragmentos dos dados de estado necessários para executar as transações no bloco. Um validador pode usar apenas esses fragmentos para verificar se o proponente do bloco executou as transações do bloco e atualizou o estado corretamente. Entretanto, isso significa que a testemunha precisa ser transferida entre pares na rede Ethereum com rapidez suficiente para ser recebida e processada por cada nó com segurança, em um espaço de 12 segundos. Se a testemunha for muito grande, alguns nós poderão levar muito tempo para fazer o download e acompanhar a cadeia. Essa é uma força centralizadora, pois significa que apenas nós com conexões rápidas à Internet podem participar da validação de blocos. Com as Verkle Trees, não há necessidade de ter o estado armazenado no disco rígido local; tudo que você precisa para verificar um bloco está no próprio bloco. Infelizmente, as testemunhas que podem ser produzidas a partir de Merkle tries são muito grandes para suportar clientes sem estado.

Por que as Verkle Trees permitem testemunhas menores?

A estrutura de uma Merkle Trie faz com que as testemunhas sejam muito grandes, grandes demais para serem transmitidas com segurança entre pares em um espaço de 12 segundos. Isso ocorre porque a testemunha é um caminho que conecta os dados, que são mantidos nas folhas, ao hash raiz. Para verificar os dados, é necessário ter não apenas todos os hashes intermediários que conectam cada folha à raiz, mas também todos os nós "irmãos". Cada nó na prova tem um irmão com o qual é feito o hash para criar o próximo hash na trie. São muitos dados. As Verkle Trees reduzem o tamanho da testemunha ao reduzir a distância entre as folhas da árvore e sua raiz, bem como ao eliminar a necessidade de fornecer nós irmãos para verificar o hash raiz. Será possível obter ainda mais eficiência de espaço usando um esquema eficiente de compromisso polinomial em vez do compromisso vetorial no estilo hash. O compromisso polinomial permite que a testemunha tenha um tamanho fixo, independentemente do número de folhas que ela comprove.

No esquema de compromisso polinomial, as testemunhas têm tamanhos gerenciáveis que podem ser facilmente transferidos na rede ponto a ponto. Isso permite que os clientes verifiquem as alterações de estado em cada bloco com uma quantidade mínima de dados.

Qual é a estrutura de uma Verkle Tree?

As Verkle Trees são pares (chave, valor) em que as chaves são elementos de 32 bytes compostos por uma stem (haste) de 31 bytes e um sufixo de um byte. Essas chaves são organizadas em nós de extensão e nós internos. Os nós de extensão representam uma única haste para 256 filhos com sufixos diferentes. Os nós internos também têm 256 filhos, mas eles podem ser outros nós de extensão. A principal diferença entre a Verkle Tress e a estrutura da Merkle Tree é que a de Verkle é muito mais plana, o que significa que há menos nós intermediários ligando uma folha à raiz e, portanto, menos dados necessários para gerar uma prova.

Leia mais sobre a estrutura das Verkle Trees(opens in a new tab)

Progresso atual

As redes de testes de Verkle Trees já estão em execução, mas ainda há atualizações pendentes consideráveis em clientes que são necessárias para oferecer suporte às Verkle Trees. Você pode ajudar a acelerar o progresso por meio da implantação de contratos nas redes de testes ou da execução de clientes de rede de testes.

Conheça a rede de testes do Beverly Hills Verkle(opens in a new tab)

Assista a Guillaume Ballet explicar a rede de testes Condrieu Verkle(opens in a new tab) (observe que a rede de testes Condrieu era uma prova de trabalho e agora foi substituída pela rede de testes Kaustinen(opens in a new tab)).

Leitura adicional

• Dankrad Feist explica as Verkle Trees no PEEPanEIP(opens in a new tab)
• Guillaume Ballet explica as Verkle Trees na ETHGlobal(opens in a new tab)
• "Como as Verkle Trees tornam o Ethereum simples e eficiente", por Guillaume Ballet na Devcon 6(opens in a new tab)
• Piper Merriam sobre clientes sem estado da ETHDenver 2020(opens in a new tab)
• Dankrad Fiest explica as Verkle Trees e a condição sem estado no podcast Zero Knowledge(opens in a new tab)
• Vitalik Buterin sobre Verkle Trees(opens in a new tab)
• Dankrad Feist sobre Verkle Trees(opens in a new tab)
• Documentação de EIO da Verkle Tree(opens in a new tab)